正好前几天被一个学弟问了一下数据结构里的二叉树的问题，这毕竟也是老黄历了，翻了翻之前的博客，WordPress的数据库一团糟，当时写的好几篇文章全是乱码，明明密码是对的结果硬是提示错误。还是想办法重新写一个吧，之前用的C语言，也已经忘得差不多了，这次用Python重新写一写，顺带测试一下新的水印功能((#.#))

1. 引言

二叉树遍历：是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次

二叉树的遍历方式分为：前序遍历、中序遍历、后序遍历、层序遍历

image-20210114031110150

2. 原理及代码实现

例图都是我手画的，由于涉及到后续代码，我给每个节点加上了a[i]的下标方便理解

2.1 前序遍历

2.1.1前序遍历原理

image-20210114033647532

前序遍历的公式为：根节点 → 左子树 → 右子树

那么，结果就为：A→B→D→G→H→C→E→I→F

啰嗦一点：从A到B再到D，D有两个子树，从左到右遍历GH，然后转向A的另一个子树C，然后遍历Ed左子树，然而左子树为空，继而遍历I，最后回过头遍历Cd另一个子树F，遍历结束。

2.1.2 前序遍历代码实现

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

# 递归
qianxu = []
def PreOrder(root):
    if not root:
        return None
    qianxu.append(root.val)
    PreOrder(root.left)
    PreOrder(root.right)

# 非递归
def Pre_Order(root):
    data = []
    stack = []
    cur = root
    while cur or stack:
        while cur: # 若当前节点不为空
            data.append(cur.val) # 得到当前节点值
            stack.append(cur) # 压入栈中
            cur = cur.left # 去往左子树
        top = stack.pop() # 来到这里，说明当前节点为空，也就是当前节点的父节点无左子树，取出栈顶元素也就是当前节点的父节点
        cur = top.right # 往右子树的方向，若右子树为空则看栈是不是空，若栈不为空，再取出栈顶节点，访问其右子树
    return data

if __name__ == '__main__':
    a1 = TreeNode('A')
    a2 = TreeNode('B')
    a3 = TreeNode('C')
    a4 = TreeNode('D')
    a5 = TreeNode('E')
    a6 = TreeNode('F')
    a7 = TreeNode('G')
    a8 = TreeNode('H')
    a9 = TreeNode('I')
    a1.left = a2
    a1.right = a3
    a2.left = a4
    a3.left = a5
    a3.right = a6
    a4.left = a7
    a4.right = a8
    a5.right = a9
    PreOrder(a1)
    print('递归方法的前序遍历结果为:',qianxu)
    print('非递归方法的前序遍历结果为: {}'.format(Pre_Order(a1)))
# 输出
递归方法的前序遍历结果为: ['A', 'B', 'D', 'G', 'H', 'C', 'E', 'I', 'F']
非递归方法的前序遍历结果为: ['A', 'B', 'D', 'G', 'H', 'C', 'E', 'I', 'F']

2.2 中序遍历

2.2.1中序遍历原理

image-20210114033647532

中序遍历的公式为： 左子树 → 根节点→ 右子树

那么，结果就为：G→D→H→B→A→E→I→C→F

啰嗦一点：从左子树G开始遍历到根节点D，再遍历H，再遍历根节点BA，再从E的左节点(空)开始遍历，遍历至E再遍历I，继而遍历根节点C，最后遍历F。

2.2.2 中序遍历代码实现

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

# 递归
zhongxu = []
def InOrder(root):
    if not root:
        return None
    InOrder(root.left)
    zhongxu.append(root.val)
    InOrder(root.right)

# 非递归
def In_Order(root):
    data = []
    stack = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        top = stack.pop()
        data.append(top.val)
        cur = top.right
    return data

if __name__ == '__main__':
    a1 = TreeNode('A')
    a2 = TreeNode('B')
    a3 = TreeNode('C')
    a4 = TreeNode('D')
    a5 = TreeNode('E')
    a6 = TreeNode('F')
    a7 = TreeNode('G')
    a8 = TreeNode('H')
    a9 = TreeNode('I')
    a1.left = a2
    a1.right = a3
    a2.left = a4
    a3.left = a5
    a3.right = a6
    a4.left = a7
    a4.right = a8
    a5.right = a9
    InOrder(a1)
    print('递归方法的中序遍历结果为: ',zhongxu)
    print('非递归方法的中序遍历结果为: {}'.format(In_Order(a1)))
# 输出
递归方法的中序遍历结果为:  ['G', 'D', 'H', 'B', 'A', 'E', 'I', 'C', 'F']
非递归方法的中序遍历结果为: ['G', 'D', 'H', 'B', 'A', 'E', 'I', 'C', 'F']

2.3 后序遍历

2.3.1后序遍历原理

image-20210114033647532

后序遍历的公式为： 左子树 → 右子树→ 根节点

那么，结果就为：G→H→D→B→I→E→F→C→A

啰嗦一点：从G到H再到根节点D和B，从E的空左子树到I，再到根节点E和F，最后到C和A。

2.3.2 后序遍历代码实现

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

# 递归
houxu = []
def PastOrder(root):
    if not root:
        return None
    PastOrder(root.left)
    PastOrder(root.right)
    houxu.append(root.val)

# 非递归
def Past_Order(root):
    data = []
    stack = []
    stack.append(root)
    while stack:
        node = stack.pop()
        if not node:
            continue
        stack.append(node.left)
        stack.append(node.right)
        data.append(node.val)
    return data[::-1]

if __name__ == '__main__':
    a1 = TreeNode('A')
    a2 = TreeNode('B')
    a3 = TreeNode('C')
    a4 = TreeNode('D')
    a5 = TreeNode('E')
    a6 = TreeNode('F')
    a7 = TreeNode('G')
    a8 = TreeNode('H')
    a9 = TreeNode('I')
    a1.left = a2
    a1.right = a3
    a2.left = a4
    a3.left = a5
    a3.right = a6
    a4.left = a7
    a4.right = a8
    a5.right = a9
    PastOrder(a1)
    print('递归方法的后序遍历结果为: ',houxu)
    print('非递归方法的后序遍历结果为: {}'.format(Past_Order(a1)))
# 输出
递归方法的后序遍历结果为:  ['G', 'H', 'D', 'B', 'I', 'E', 'F', 'C', 'A']
非递归方法的后序遍历结果为: ['G', 'H', 'D', 'B', 'I', 'E', 'F', 'C', 'A']

2.4 层序遍历

2.4.1层序遍历原理

image-20210114041626155

层序遍历的原理为： 从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问

那么，结果就为：A→B→C→D→E→F→G→H→I

啰嗦一点：看图吧~这个是最简单的了

2.4.2 层序遍历代码实现

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
# 非递归
def Level_Order(root):
    if not root:
        return
    data = []
    queue = []
    queue.append(root)
    while queue: # 队列不为空，说明还没遍历完
        front = queue.pop(0) # 队列先进先出
        if front.left:
            queue.append(front.left) # 进左子节点
        if front.right:
            queue.append(front.right) # 进有右子节点
        data.append(front.val)
    return data

if __name__ == '__main__':
    a1 = TreeNode('A')
    a2 = TreeNode('B')
    a3 = TreeNode('C')
    a4 = TreeNode('D')
    a5 = TreeNode('E')
    a6 = TreeNode('F')
    a7 = TreeNode('G')
    a8 = TreeNode('H')
    a9 = TreeNode('I')
    a1.left = a2
    a1.right = a3
    a2.left = a4
    a3.left = a5
    a3.right = a6
    a4.left = a7
    a4.right = a8
    a5.right = a9
    print('非递归方法的后序遍历结果为: {}'.format(Level_Order(a1)))
# 输出
非递归方法的后序遍历结果为: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']

Q.E.D.

print("种一棵树最好的时间是十年前，其次是现在")