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.key

4. 树的遍历

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 eTree

5.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()