导语:
本文主要介绍了关于python创建平衡二叉树的方法的相关知识,包括创建一个平衡二叉树,以及平衡二叉树应用这些编程知识,希望对大家有参考作用。
1、生成平衡树的核心是partial_tree方法。
它接受一个序列和一个数字作为参数,并递归返回一个序列。其中第一个是结构树,第二个是书中没有包含的元素。
2. 实现的总体思路是,将每个传入的序列分为左半部分、顶点和右半部分,直到不能进一步分裂,然后逐层返回,最后组合成一棵平衡二叉树。
实例
"""
list_to_tree方法将有序列表转化为平衡二叉树
一棵二叉树分为树顶点、左子树、右子树,其中左子树的值都比树顶节点小,右子树的值都比树顶点大
"""
def make_tree(entry, left, right):
# 创建树的方法
return (entry, left, right)
def entry(tree):
# 获取树的顶点
return tree[0]
def left_branch(tree):
# 获取左子树
return tree[1]
def right_branch(tree):
# 获取右子树
return tree[2]
def list_to_tree(elements):
return partial_tree(elements, len(elements))[0]
def partial_tree(elts, n):
if n == 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))
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
本文为原创文章,版权归知行编程网所有,欢迎分享本文,转载请保留出处!
你可能也喜欢
- ♥ python写入文件时如何覆盖原始写入10/02
- ♥ 如何在 Python 中使用偏函数?11/26
- ♥ python中的temp是什么09/02
- ♥ python判断一个字符是否在另一个字符串中09/02
- ♥ python中如何通过循环遍历分离数据01/02
- ♥ Python中的运算符有哪些10/29
内容反馈