二叉树Python实现

此二叉树我们用列表来表示它的节点

例如：

a[2,None,None],它表示的是根节点为2，没有子节点，a[0]为根节点，a[1]为左子节点，a[2]为右子节点。

数据结构介绍完，然后进行构造二叉树

#build binary tree function
#二叉树实现
#构建二叉树
def Bintree(data,left=None,right=None):
    return [data,left,right]
#判断二叉树是否为空树，返回的是一个布尔值
def is_empty_Bintree(btree):
    return btree is None
#返回树的根
def root(btree):
    return btree[0]
def left(btree):
    return btree[1]
def right(btree):
    return btree[2]
#插入一个根节点
def set_root(btree,data):
    btree[0] =data
def set_left(btree,left):
    btree[1]=left
def set_right(btree,right):
    btree[2]=right

构造树的函数已经完成，下面是树的构造

t=Bintree(2, Bintree(4), Bintree(8))

print(t)

输出结果为：

[2, [4, None, None], [8, None, None]]

此二叉树为：

Center

下面构造一棵复杂的二叉树：

set_left(left(t),Bintree(5))
set_right(left(t),Bintree(6))
set_left(left(left(t)),Bintree(9))
print(t)

输出为：

[2, [4, [5, [9, None, None], None], [6, None, None]], [8, None, None]]

此树为：

Center 1

接下来进行二叉树的遍历

（下面用的递归实现的二叉树遍历）

1、先序遍历（先根节点，再左节点，后右节点）

代码实现：

def Through(tree):
    if((is_empty_Bintree(tree))==False):
        a=root(tree)
        if a==None:pass
        else:
            print(a)
        Through(left(tree))
        Through(right(tree))
    return None        # Through(right(tree))
Through(t)

遍历的顺序为：

245968

2、中序遍历（先左节点，再根节点，后右节点）

#中序遍历

def Through(tree):
    if((is_empty_Bintree(tree))==False):
        Through(left(tree))
        a=root(tree)
        if a==None:pass
        else:
            print(a)
        Through(right(tree))
    return None        # Through(right(tree))
Through(t)

遍历的顺序为：954628

3、后序遍历（先左节点，再右节点，后根节点）

def Through(tree):
    if((is_empty_Bintree(tree))==False):
        Through(left(tree))
        Through(right(tree))
        a=root(tree)
        if a==None:pass
        else:
            print(a)
    return None        # Through(right(tree))
Through(t)