嘿,我正在准备考试,我可以使用一些帮助 . 任务是从叶子的值数组(从左到右)构建二进制和树(父节点键是子键的总和),其总是2 ^ n长 . 我首先将数组转换为节点数组 . 然后我做了一个递归函数,它结合了对并在一个新创建的节点数组上调用它自己 . 有没有更好的方法来完成这项任务?也许一个“到位”?例如
输入:[1,2,3,4]
输出:
10
/
3 7
/ \ /
1 2 3 4
class SumTree:
def __init__(self):
self.root = None
class Node:
def __init__(self):
self.key = 0
self.parent = None
self.left = None
self.right = None
def makeNode(key):
n = Node()
n.key = key
return n
def buildSumTree(array):
for i in range(len(array)):
array[i] = makeNode(array[i])
tree = SumTree()
tree.root = buildSumTree_rec(array)
return tree
def buildSumTree_rec(array):
if len(array) == 1 :
return array[0]
else:
a = []
for i in range(0, len(array) // 2, 2):
n = makeNode(array[i].key + array[i + 1].key)
n.left = array[i]
n.right = array[i + 1]
array[i].parent = n
array[i + 1].parent = n
a.append(n)
return buildSumTree_rec(a)
3 回答
通常是这样的:
以下代码构建从树叶到根的树 . 它重复将两个子节点连接到新创建的父节点,直到只剩下一个节点 .
成对迭代基于:Iterating over every two elements in a list
此实现仅存储叶子而不存储任何其他内容,因此不使用额外的内存来存储节点 . 它也不会改变叶子,即不进行任何改变,只进行读取操作 . 所有其他信息都是即时计算的 . 目前输出是基本的,每深度一行 .