数据结构之二叉树及四种遍历方法

如果树中每个节点最多只有两个子节点，这样的树就称为“二叉树”。二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。

代码示例

1、二叉树的定义

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')

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

print(e.lchild.rchild.data)

2、二叉树的遍历

1) 前序遍历

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

pre_order(root)  # E,A,C,B,D,G,F

2) 中序遍历

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

in_order(root)  # A,B,C,D,E,G,F

3) 后序遍历

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

post_order(root)  # B,D,C,A,F,G,E

3、层次遍历

from collections import deque

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

level_order(root)  # E,A,G,C,F,B,D