python——有序表生成平衡二叉树

这是《计算机程序的构造和解释》p108练习2.64的一段代码，我将其转换为了python代码

"""
 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))

执行结果：

这个生成平衡树的核心是partial_tree这个方法，它以一个序列和数字为参数，通过递归的方式返回一个一个序列，其中第一项为构造的树，第二项为没有包含在书中的元素；它实现的整体思路每次把传入的序列分为左半部分、顶点、右半部分，一直递归直到无法继续拆分，然后逐层返回最终组合成一棵平衡二叉树。