[数据结构] python 二叉树的遍历

二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。

二叉树节点的定义：

class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None  # 左孩子
        self.rchild = None  # 右孩子

二叉树的遍历方式有：

1. 前序遍历（也称先序遍历）：根、左、右

2. 中序遍历：左、根、右

3. 后续遍历：左、右、根

4. 层次遍历：一层一层的从左往右遍历

如何遍历？

如给下图做先序遍历，每个节点都可以当做一棵树来遍历，先序遍历方法为：根、左、右

先找到树的根E，E的左边为A，A又可以当做根，A的左边没有，A的右边是C，C又可以当根，C的左边为B，C的右边为D，B和D都可以当做根，但是B和D下面没什么东西了，所以可以往回走，发现A、C、D、B的结点都走完了，E还剩右边没有走，按照同样的方法走一边就行。

其他遍历的过程也是一样的，只不过是遍历方法不一样而已。同样的过程就可以推出这棵树的各种遍历了。

所以，该树的

前序遍历（根、左、右）为：EACBDGF

中序遍历（左、根、右）为：ABCDEGF

后续遍历（左、右、根）为：BDCAFGE

层次遍历为：EAGCFBD

代码思路：

前序遍历（根、左、右）：四行代码就可以了

1. 判断根是否存在，根不存在就不能执行下去了！！

2. 先输出根

3. 递归调用右子树，输出右子树的根

4. 递归调用左子树，输出左子树的根

代码如下：

def pre_order(root):
    if root:
        print(root.data, end=",")
        pre_order(root.lchild)
        pre_order(root.rchild)

同理，中序遍历（左、根、右）代码如下，方法一样过程不一样：

def in_order(root):
    if root:
        in_order(root.lchild)
        print(root.data, end=",")
        in_order(root.rchild)

同理，后序遍历（左、右、根）代码如下，方法一样过程不一样：

def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data, end=",")

层次遍历：

层次遍历需要用队列来做，需要导入deque方法。

代码思路如下：

1. 创建一个空队列，将根节点加入队列

2. 当输出一个节点时，队列就少一个结点，所以需要循环来做，循环条件为队不为空

3. 用一个节点变量来保存出队结点，输出变量的data

4. 如果该结点存在左孩子，将左孩子加入队列，如果存在右孩子，将右孩子加入队列

因为层次遍历是从左往右遍历，所以左孩子一定要加入队列在右孩子前面

代码如下：

from collections import deque
def level_order(root):
    queue = deque()
    queue.append(root)
    while len(queue) > 0:
        node = queue.popleft()
        print(node.data, end=",")
        if node.lchild:
            queue.append(node.lchild)
        if node.rchild:
            queue.append(node.rchild)

整体代码为：

from collections import deque

class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None  # 左孩子
        self.rchild = None  # 右孩子

a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')

e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f

root = e

def pre_order(root):
    if root:
        print(root.data, end=",")
        pre_order(root.lchild)
        pre_order(root.rchild)

def in_order(root):
    if root:
        in_order(root.lchild)
        print(root.data, end=",")
        in_order(root.rchild)

def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data, end=",")

def level_order(root):
    queue = deque()
    queue.append(root)
    while len(queue) > 0:
        node = queue.popleft()
        print(node.data, end=",")
        if node.lchild:
            queue.append(node.lchild)
        if node.rchild:
            queue.append(node.rchild)

pre_order(root)
print(end="n")
in_order(root)
print(end="n")
post_order(root)
print(end="n")
level_order(root)

输出结果为：

E,A,C,B,D,G,F,
A,B,C,D,E,G,F,
B,D,C,A,F,G,E,
E,A,G,C,F,B,D,