1. 树的概念树是一种非线性的层次型数据结构不像数组、链表是一条直线而是一层一层往下分叉像现实中的倒着长的树。2. 树的基本话术1根节点树最顶部唯一的节点没有父节点2父 / 子节点上层是父下层分叉出来的是子3叶子节点没有子节点的末端节点4层次根是第 1 层往下层数递增5高度层级的最大值3. 树的实现3.1 树的嵌套列表实现def binary_tree(r): # 创建根节点 return [r,[],[]] # 二维数组表示树 def insert_left(root,new_branch): # 插入左子树 t root.pop(1) if len(t) 1: root.insert(1,[new_branch,t,[]]) else: root.insert(1,[new_branch,[],[]]) return root def insert_right(root,new_branch): # 插入右子树 t root.pop(2) if len(t) 1: root.insert(2,[new_branch,[],t]) else: root.insert(2,[new_branch,[],[]]) return root def get_root_val(root): # 查看根节点 return root[0] def set_root_val(root,new_val): # 设置根节点参数 root[0] new_val def get_left_child(root): # 查看左子树 return root[1] def get_right_child(root): # 查看右子树 return root[2]3.2 树的链式表达class Binarytree: def __init__(self,root_obj): self.key root_obj self.left_child None self.right_child None def insert_left(self,new_node): if self.left_child None: self.left_child Binarytree(new_node) else: t Binarytree(new_node) t.left_child self.left_child self.left_child t def insert_right(self,new_node): if self.right_child None: self.right_child Binarytree(new_node) else: t Binarytree(new_node) t.right_child self.right_child self.right_child t def get_right_child(self): return self.right_child def get_left_child(self): return self.left_child def set_root_val(self,obj): self.key obj def get_root_val(self): return self.key4. 树的遍历4.1 前序遍历顺序根节点→左子树→右子树def pre_order(tree): # 前序遍历 if tree: print(tree.get_root_val()) pre_order(tree.get_left_child()) pre_order(tree.get_right_child())4.2 中序遍历顺序左子树→根节点→右子树def in_order(tree): # 中序遍历 if tree ! None: in_order(tree.get_left_child()) print(tree.get_root_val()) in_order(tree.get_right_child())4.3 后序遍历顺序左子树→右子树→根节点def post_order(tree): # 后序遍历 if tree ! None: post_order(tree.get_left_child()) post_order(tree.get_right_child()) print(tree.get_root_val())5. 树的应用5.1 全括号表达式解析任务1从全括号表达式构建表达式解析树2利用表达式解析式对表达式求值3从表达式解析树恢复原表达式的字符串形式思路1遇到左括号则创建左子树用于存储数据并将指针指向左子树指针下沉2整个操作过程遵循后进先出原则创建栈用来保存指针位置确保操作顺序正确不遗漏3遇到数值则设置当前指针位置节点的值并将指针上移4遇到右括号则只执行剔除栈中的指针位置的操作代码如下def build_parse_tree(fpexp): # 全括号表达式 fplist fpexp.split() # 分隔全括号表达式返回列表 pStack Stack() eTree Binarytree() # 创建根节点 pStack.push(eTree) # 存入栈底最后最运算 currentTree eTree # 当前节点 for i in fplist: if i (: currentTree.insert_left() # 创建左子树 pStack.push(currentTree) # 记录当前节点位置 currentTree currentTree.get_left_child() # 将当前节点指向左子树 elif i not in [,-,*,/,)]: # 遍历到操作数时 currentTree.set_root_val(int(i)) # 设置当前节点的操作数 parent pStack.pop() currentTree parent # 当前节点返回上一个节点 elif i in [,-,*,/]: # 遍历到操作符时 currentTree.set_root_val(i) # 设置当前节点的操作符 currentTree.insert_right() # 创建右子树 pStack.push(currentTree) # 记录当前节点位置 currentTree currentTree.get_right_child() # 将当前节点下沉到右子树 elif i ): # 消除栈中的节点位置一轮全括号解析结束 currentTree pStack.pop() else: raise ValueError return eTree5.2 递归求值函数递归原则1基本结束条件叶节点为最简单的子树没有左右子节点其根节点的数据项即为子表达式树的值。2缩小规模将表达式树分为左子树、右子树。3调用自身分别调用evaluate函数计算左子树和右子树的值然后将左右子树的值依根节点的操作符进行计算从而得到表达式的值。import operator def evaluate(parse_tree): # 递归解析法 opers {:operator.add, -:operator.sub, *:operator.mul, /:operator.truediv,} leftC parse_tree.get_left_child() rightC parse_tree.get_right_child() if leftC and rightC: fn opers[parse_tree.get_root_val()] return fn(evaluate(leftC),evaluate(rightC)) else: return parse_tree.get_root_val()