基于Python3的数据结构与算法 - 18 二叉树的遍历

一、二叉树的概遍历

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

节点定义： 

class BiTreeNode:
    def __init__(self, datta)：
        self.data = data
        self.lchild = None
        self.rchild = None

按照上图结构，自定义一个二叉树 

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

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

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

root = e   # 根节点
print(root.lchild.rchild.data)

二叉树的遍历方式：

• 前序遍历：EACBDGF

取出根节点，将左边子树当作一个整体，遍历左子树；然后再将右子树当作一个整体，遍历右子树（递归）

• 中序遍历：ABCDEGF

先递归左子树，再访问根节点，再递归右子树

• 后序遍历：BDCAFGE
• 层次遍历： EAGCFBD（一层一层的横着遍历，使用队列写）

四种遍历方法的带啊吗如下所示：

def pre_order(root):
    if root:   # 如果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)