• 技术文章 >Python技术 >Python基础教程

    python创建平衡二叉树的方法

    小妮浅浅小妮浅浅2021-09-11 10:39:16原创130

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

    专题推荐:python 平衡二叉树
    品易云
    上一篇:python捕获异常的原因 下一篇:python如何配置文件路径

    相关文章推荐

    • python中MRO原则的使用• python命令行模式的使用流程• python算术运算符的扩展功能• python不同类型的对象特点• python有哪些数组叠加函数• python数组分割的函数• python中INF值的介绍• Python requests如何发送请求• python requests读取服务器响应• python requests响应内容的三种方法• python requests发送不同类型的数据• python requests检测响应状态码• python requests重定向的操作• python requests的超时使用• python捕获异常的原因

    全部评论我要评论

  • 取消发布评论
  • 

    Python学习网