数据结构之二叉树——遍历（递归与非递归）
定义
二叉树，一个有穷的结点集合。这个集合可以为空，如果不为空，则它是由根结点和称其为左子树和右子树的两个不相交的二叉树组成。
二叉树有五种基本形态：
顺序存储
完全二叉树可以使用顺序存储结构，按从上至下，从左到右顺序存储，如果一颗完全二叉树如下：
那么顺序存储可以为：
由上面的结构，可以得到，n个结点的完全二叉树的结点父子关系：
非根结点（序号i>1）的父节点的序号为⌊i/2⌋
结点（序号为i）的左孩子结点的序号为2i(如果2i>n，则没有左孩子)
结点（序号为i）的右孩子结点的序号为2i+1(如果2i+1>n，则没有右孩子)
一般二叉树也可以使用顺序存储，只是会造成空间的浪费。
链式存储
由于一般的二叉树使用顺序存储结构，容易造成空间的浪费，因此可以使用链式存储。其结构如下
class TreeNode: def __init__(self, x, left=None, right=None): self.val = x # 值 self.left = left # 左孩子 self.right = right # 右孩子 复制代码
遍历
由于二叉树不是线性结构，因此它的遍历也就不像数组或者链表那么简单，它需要沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。
前序遍历
前序遍历的遍历过程：
访问根结点
先序遍历其左子树
先序遍历其右子树
使用递归的方式实现如下：
def pre_order_traversal(root: TreeNode): if root: print(root.val) pre_order_traversal(root.left) pre_order_traversal(root.right) 复制代码
该树的前序遍历为：A B D F E C G H I
中序遍历
中序遍历的遍历过程：
中序遍历其左子树
访问根结点
中序遍历其右子树
递归代码
def in_order_traversal(root: TreeNode): if root: in_order_traversal(root.left) print(root.val) in_order_traversal(root.right) 复制代码
该树的中序序遍历为：D B E F A G H C I
后序遍历
后序遍历的遍历过程：
后序遍历其左子树
后序遍历其右子树
访问根结点
递归代码
def post_order_traversal(root: TreeNode): if root: post_order_traversal(root.left) post_order_traversal(root.right) print(root.val) 复制代码
该树的后序序遍历为：D E F B H G I C A
遍历的思考
从上面三幅图的访问路径，可以看出，不论是前，中，后序遍历，在遍历过程中经过结点的路线都是一样的，只是访问各结点的时机不同
下图使用ⓧ，☆，△三种符号分别标记出，前序，中序，后序访问各结点的时刻
非递归中序遍历
使用递归的方式可以比较容易的写出遍历算法，那么如果不用递归呢？
我们知道，递归的实现需要借助栈，那么可以用栈+循环的方式来实现遍历算法。
以中序遍历为列：
遇到一个结点，因为不知道是否还有左子树，因此将它压栈，并去遍历它的左子树
当它的左子树遍历完了，从栈顶弹出这个结点并访问它
然后转向这个结点的右子树继续遍历，相当于又回到第一步，直到遍历完整棵树
仍然以上面的二叉树为例，来看看非递归的中序遍历的运行过程：
结点A，压栈
A有左结点B，B压栈
B有左结点D，D压栈
结点D，没有左结点，则弹出栈顶元素D，并访问
转向D的右子树，但是D没有右子树，因此继续弹出栈顶元素B并访问，
转向B的右结点F，F压栈
F有左结点E，E压栈
E没有左结点，弹出栈顶元素E并访问
转向E的右结点，没有，继续弹出F
转向F的右结点，没有，继续弹出A
转向A的右结点C，C压栈
C有左结点G，G压栈
G没有左结点，弹出G并访问
转向G的右结点H，H压栈
H没有左结点，弹出H并访问
H没有右结点，继续弹出，弹出C访问
转向C的右结点I，I压栈
I没有左结点，弹出I访问
转向I的右结点，没有，栈也为空，遍历结束
def in_order_traversal(root: TreeNode): stack = [] while root or stack: while root: stack.append(root) root = root.left if stack: node = stack.pop() print(node.val) root = node.right 复制代码
非递归前序遍历
中序遍历是在第二次经过结点的时候，才访问该结点的，因此参照中序遍历的非递归算法，把print语句移到第一次经过结点时，就访问该结点，那么非递归前序遍历的实现也就出来了。
def pre_order_traversal(root: TreeNode): stack = [] while root or stack: while root: stack.append(root) print(node.val) root = root.left if stack: node = stack.pop() root = node.right 复制代码
非递归后序遍历
非递归后序遍历比较复杂，而且实现的方式也有多种，这里提供一个比较好理解的标记法。根据后序遍历的定义，要先访问完左子树，再访问完右子树，最后才访问根结点，那么还是套之前的代码结构，但是做个标记，在弹出元素的时候，判断是否有右结点或者右结点是否被访问过，如果满足则访问该结点，不满足就将它再次压回栈中，并转向它的右结点
def post_order_traversal(root: TreeNode): stack = [] visited_node = None # 前一个被访问的结点 while root or stack: while root: stack.append(root) root = root.left if stack: node = stack.pop() if not node.right or node.right == visited_node: # 没有右孩子或者右孩子已经被访问了，才访问该结点 print(node.val) visited_node = node else: # 否则就将该结点重新压回栈了，并转向它的右结点 stack.append(node) root = node.right 复制代码
层次遍历
二叉树的遍历，除了上面三种之外，还有一种层次遍历，即一层一层的访问
该树的层次遍历：A B C D F G I E H
算法实现可以借助队列实现，先根结点入队，然后：
从队列中取出一个元素
访问该元素
如果该元素有左、右结点，则将其左右结点顺序入队
直到队列为空
def level_order_traversal(root: TreeNode): queue = [root] while queue: node = queue.pop(0) print(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) 复制代码
总结
实际上二叉树的遍历核心问题：二维结构的线性化，当访问一个结点的时候，还需要访问其左右结点，但是访问左结点之后，如果再返回访问其右结点？ 因此需要一个存储结构保存暂时不访问的结点，那么存储结构可以为栈，或者队列，对应的就有前，中，后，层次遍历的出现。
二叉树的遍历有许多应用，比如：输出二叉树中的叶子结点，求二叉树的高度等等，因此遍历对二叉树来说是十分重要的。
作者：sako
链接：https://juejin.cn/post/6844903959866376200