python创建平衡二叉树的方法
小妮浅浅
2021-10-21 09:43:105221浏览 · 0收藏 · 0评论
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创建平衡二叉树的方法,希望对大家有所帮助。更多Python学习指路:python基础教程
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
关注公众号,随时随地在线学习
相关文章