python如何创建平衡二叉树

本篇内容介绍了“python如何创建平衡二叉树”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

创新互联建站致力于互联网品牌建设与网络营销,包括成都网站设计、网站建设、SEO优化、网络推广、整站优化营销策划推广、电子商务、移动互联网营销等。创新互联建站为不同类型的客户提供良好的互联网应用定制及解决方案,创新互联建站核心团队10多年专注互联网开发,积累了丰富的网站经验,为广大企业客户提供一站式企业网站建设服务,在网站建设行业内树立了良好口碑。

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如何创建平衡二叉树
分享URL:http://ybzwz.com/article/iihecd.html