python 实现二叉树

本文不涉及二叉树概念的详细讲解，而着重利用 python 实现二叉树，其中穿插代码讲解。

其它数据结构：链表、栈和队列。

在链表中，一个节点只能有一个后继节点和前驱节点。而在 树中，一个节点可以有多个后继节点，但只能有一个前驱节点。节点的 度表示有几个后继节点， 树的度是最大的节点的度。二叉树是度为 2 的树。

在树中，没有前驱节点的节点称为根节点，没有后继节点的节点称为叶子节点。前驱节点也称为父节点，后继节点也称为子节点。具有相同父节点的节点称为兄弟节点。

节点

每个节点有两个后继节点，分别为左子节点和右子节点。

class Node():
    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None

构造树

每个树有个根节点。

class Tree():
    def __init__(self):
        self.root = None

层遍历

树具有一个层次结构，从根节点最高层到最低层，每层从左向右遍历。需要借助队列实现。

def level_travel(self):
    if self.root == None:
        return 

    queue = [self.root]
    while queue:
        cur = node = queue.pop(0)
        print(cur.elem, end=" ")
        if cur.lchild != None:
            queue.append(cur.lchild)
        if cur.rchild != None:
            queue.append(cur.rchild)

添加节点

树具有一个层次结构，我们在每层按照从左至右的方向添加节点。我们从第一层开始，依次判断根节点是否有左子节点和右子节点，如果没有，则添加；如果有，则转到第二层。以此类推。实现上与层遍历有点类似。

def add(self, item):
    node = Node(item)

    # 如果节点为空
    if self.root == None:
        self.root = node
        return

    queue = [self.root]
    while queue:
        cur = queue.pop(0)
        if cur.lchild == None:
            cur.lchild = node
            return 
        else:
            queue.append(cur.lchild)
        if cur.rchild == None:
            cur.rchild = node
            return 
        else:
            queue.append(cur.rchild)

先序遍历

先序遍历是先遍历根节点，再遍历左子树，最后遍历右子树。对于遍历子树而言，也是遍历子树的根节点，再遍历子树的左子树，最后遍历子树的右子树。可以用递归实现。

def preorder_travel(self, node):
    # 如果节点为空
    if node == None:
        return
    
    print(node.elem， end=" ")
    self.preorder_travel(node.lchild)
    self.preorder_travel(node.rchild)

中序遍历

中序遍历则先遍历左子树，再遍历根节点，最后遍历右子树。

def inorder_travel(self, node):
    # 如果节点为空
    if node == None:
        return
    self.inorder_travel(node.lchild)
    print(node.elem, end=" ")
    self.inorder_travel(node.rchild)

后序遍历

后续遍历先遍历左子树，再遍历右子树，最后遍历根节点。

def postorder_travel(self, node):
    # 如果节点为空
    if node == None:
        return
    
    self.postorder_travel(node.lchild)
    self.postorder_travel(node.rchild)
    print(node.elem, end=" ")

测试

if __name__ == "__main__":
    t = Tree()
    t.add(0)
    t.add(1)
    t.add(2)
    t.add(3)
    t.add(4)
    t.add(5)
    t.add(6)
    t.add(7)
    t.add(8)
    t.add(9)

    t.level_travel()
    print()
    t.preorder_travel(t.root)
    print()
    t.inorder_travel(t.root)
    print()
    t.postorder_travel(t.root)
    print()