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