当前位置: 首页 > 图灵资讯 > 行业资讯> python创建平衡二叉树的方法

python创建平衡二叉树的方法

来源:图灵python
时间: 2024-06-18 09:38:08

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基础教程

本文教程操作环境:windows7系统Python 3.9.1,DELL G3电脑。