python创建平衡二叉树的方法

python创建平衡二叉树的方法

1、生成平衡树的核心是partial_tree方法。

它以一个序列和数字为参数,通过递归的方式返回一个序列。其中第一个是结构树,第二个是不包含在书中的元素。

2、实现的整体思路是,每次传入的序列分为左半部分、顶点和右半部分,直到不能继续拆分,然后逐层返回,最后组合成一棵平衡的二叉树。

实例

"""
list_to_tree方法将有序列表转化为平衡二叉树
一棵二叉树分为树顶点、左子树、右子树,其中左子树的值都比树顶节点小,右子树的值都比树顶点大
"""

defmake_tree(entry,left,right):
#创建树的方法
return(entry,left,right)

defentry(tree):
#获取树的顶点
returntree[0]

defleft_branch(tree):
#获取左子树
returntree[1]

defright_branch(tree):
#获取右子树
returntree[2]

deflist_to_tree(elements):
returnpartial_tree(elements,len(elements))[0]

defpartial_tree(elts,n):
ifn==0:
return((),elts)
else:
left_size=(n-1)2
left_result=partial_tree(elts,left_size)
left_tree=left_result[0]
non_left_elts=left_result[1]
right_size=n-(left_size+1)
this_entry=non_left_elts[0]
right_result=partial_tree(non_left_elts[1:],right_size)
right_tree=right_result[0]
remaing_elts=right_result[1]
#print("entry",this_entry)
#print("left_tree",left_tree)
#print("right_tree",right_tree)
return(make_tree(this_entry,left_tree,right_tree),remaing_elts)

if__name__=="__main__":
tree=list_to_tree((1,3,5,7,9))
print("生成的平衡二叉树为:",tree)
print("树的顶点:",entry(tree))
print("树的左子树:",left_branch(tree))
print("树的右子树:",right_branch(tree))

以上就是python创建平衡二叉树的方法,希望对大家有所帮助。更多Python学习指路:Python基础教程