python实现二叉树，以及二叉树的遍历

Myth丶恋晨 2022-06-11 04:52 210阅读 0赞

# 二叉树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)

到此就结束了

希望对你有所帮助

[Center]: /images/20220611/b20680b7784c4ef4944de1981bc1480b.png
[Center 1]: /images/20220611/73dcbf45ff1a45ff8bdcc58c4305d303.png