成品网站w灬源码1688永久网站_衡阳网站_宁波seo外包推广排名_国内外搜索引擎大全

---

一、树的遍历

树的遍历Tree Traversals

• 对一个数据集中的所有数据项进行访问的操作称为遍历Traversal
• 按照对节点访问次序的不同来区分3种遍历
  • 前序遍历（preorder）：先访问根节点，再递归地前序访问左子树、最后前序访问右子树；
  • 中序遍历（inorder）：先递归地中序访问左子树，再访问根节点，最后中序访问右子树；
  • 后序遍历（postorder）：先递归地后序访问左子树，再后序访问右子树，最后访问根节点。

树的遍历：递归算法代码

def preorder(tree: BinaryTree):"""前序遍历"""if tree:print(tree.get_root_val(), end=" ")preorder(tree.get_left_child())preorder(tree.get_right_child())def inorder(tree: BinaryTree):"""中序遍历"""if tree:inorder(tree.get_left_child())print(tree.get_root_val(), end=" ")inorder(tree.get_right_child())def postorder(tree: BinaryTree):"""后序遍历"""if tree:postorder(tree.get_left_child())postorder(tree.get_right_child())print(tree.get_root_val(), end=" ")

测试：对下图分别进行前中后序遍历

my_tree = BinaryTree("a")
my_tree.insert_left("b")
my_tree.insert_right("c")
my_tree.get_right_child().set_root_val("hello")
my_tree.get_left_child().insert_left("d")
print(my_tree)print("\n前序遍历：")
preorder(my_tree)
print("\n中序遍历：")
inorder(my_tree)
print("\n后序遍历：")
postorder(my_tree)### 输出结果
[a, [b, [d, None, None], None], [hello, None, None]]前序遍历：
a b d hello
中序遍历：
d b a hello
后序遍历：
d b hello a

二、树的应用-表达式解析树

表达式解析树

• 将表达式表示为树结构：叶节点保存操作数，内部节点保存操作符
• 表达式层次决定计算的优先级：越底层的表达式，优先级越高
• 树中每个子树都表示一个子表达式。将子树替换为子表达式值的节点，即可实现求值

建立表达式解析树-算法

• 从左到右扫描全括号表达式的每个单词，依据规则建立解析树
  • 如果当前单词是"("：为当前节点添加一个新节点作为其左子节点，当前节点下降为这个新节点
  • 如果当前单词是操作符"+,-,/,*"：将当前节点的值设为此符号，为当前节点添加一个新节点作为其右子节点，当前节点下降为这个新节点
  • 如果当前单词是操作数：将当前节点的值设为此，当前节点上升到父节点
  • 如果当前单词是")"：则当前节点上升到父节点

示例：全括号表达式(3+(4*5))解析树的建立过程

建立表达式解析树-实现

• 创建左右子树可调用insertLeft/Right；当前节点设置值，可以调用setRootVal；下降到左右子树可调用getLeft/RightChild
• 上升到父节点功能：用一个栈来记录跟踪父节点，当前节点下降时，将下降前的节点push入栈；当前节点需要上升到父节点时，pop出栈的节点

def build_parse_tree(expression):"""BinaryTree类：使用链表法实现Stack类：参考《线性结构与栈》中的定义"""root = BinaryTree("")s = Stack()# 将全括号表达式分割成列表。约定：操作数是一位数expr_list = list(expression)s.push(root)cur_node = rootfor i in expr_list:if i == "(":cur_node.insert_left("")s.push(cur_node)cur_node = cur_node.get_left_child()elif i in ["+", "-", "*", "/"]:cur_node.set_root_val(i)cur_node.insert_right("")s.push(cur_node)cur_node = cur_node.get_right_child()elif i == ")":cur_node = s.pop()else:# 操作数cur_node.set_root_val(i)cur_node = s.pop()return rootexpression = "(3+(4*5))"
parse_tree = build_parse_tree(expression)
print(parse_tree)### 输出结果
[+, [3, None, None], [*, [4, None, None], [5, None, None]]]

从表达式解析树生成全括号中缀表达式

• 采用中序遍历递归算法，来生成全括号中缀表达式

def print_expr(parse_tree: BinaryTree):"""中序遍历-生成全括号中缀表达式"""res = ""if parse_tree:if parse_tree.get_left_child() and parse_tree.get_right_child():# 左子树res = "(" + print_expr(parse_tree.get_left_child())# 根节点res = res + str(parse_tree.get_root_val())# 右子树res = res + print_expr(parse_tree.get_right_child()) + ")"else:res = res + str(parse_tree.get_root_val())return resexpression = "(3+(4*5))"
parse_tree = build_parse_tree(expression)
print(parse_tree)
print(print_expr(parse_tree))### 输出结果
[+, [3, None, None], [*, [4, None, None], [5, None, None]]]
(3+(4*5))

三、树的应用-表达式解析树求值

表达式解析树求值-递归算法一

• 二叉树是一个递归数据结构，用递归算法对表达式解析树求值
  • 基本结束条件：叶节点是最简单的子树，没有左右子节点，其根节点的数据项即为子表达式树的值
  • 缩小规模：将表达式树分为左子树、右子树，即为缩小规模
  • 分别计算左子树和右子树的值，然后将左右子树的值依根节点的操作符进行计算，从而得到表达式的值

def evaluate(parse_tree: BinaryTree):left_child = parse_tree.get_left_child()right_child = parse_tree.get_right_child()if left_child and right_child:return str(# eval方法用来计算字符串表达式的值eval(evaluate(left_child) + parse_tree.get_root_val() + evaluate(right_child)))else:return parse_tree.get_root_val()expression = "(3+(4*5))"
parse_tree = build_parse_tree(expression)
print(parse_tree)
res = evaluate(parse_tree)
print(res)### 输出结果
[+, [3, None, None], [*, [4, None, None], [5, None, None]]]
23

表达式解析树求值-递归算法二

• 采用与后序遍历相似的方式

def postorder_eval(parse_tree: BinaryTree):if parse_tree:res1 = postorder_eval(parse_tree.get_left_child())res2 = postorder_eval(parse_tree.get_right_child())if res1 and res2:return str(eval(res1 + parse_tree.get_root_val() + res2))else:return parse_tree.get_root_val()expression = "(3+(4*5))"
parse_tree = build_parse_tree(expression)
print(parse_tree)
print(postorder_eval(parse_tree))### 输出结果
[+, [3, None, None], [*, [4, None, None], [5, None, None]]]
23

---

您正在阅读的是《数据结构与算法Python版》专栏！关注不迷路~