本篇内容介绍了“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))
“python如何创建平衡二叉树”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4592076/blog/4413491