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

    python创建平衡二叉树的方法

    小妮浅浅小妮浅浅2021-10-21 09:43:10原创5044

    1、生成平衡树的核心是partial_tree方法。

    它以一个序列和数字为参数,通过递归的方式返回一个序列。其中第一个是结构树,第二个是不包含在书中的元素。

    2、实现的整体思路是,每次传入的序列分为左半部分、顶点和右半部分,直到不能继续拆分,然后逐层返回,最后组合成一棵平衡的二叉树。

    实例

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    """

     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电脑。

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

    相关文章推荐

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

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网