我一直很难理解这个概念,我的教授没有很好地涵盖这个主题。这个问题需要我写一个函数来计算组成由元组组成的二叉树的整数的和。
我提供了以下代码:
node_one = (None, 1, None)
node_two = (node_one, 2, node_one)
node_three = (node_two, 3, None)
node_four = (node_three, 4, node_three)
我需要编写一个函数,接受node_four作为参数,并返回树中整数的计数,如下所示:
def TreeSum(t):
#fill in
TreeSum(node_four) # This should return 18
如果你能帮我了解如何解决这个问题,我将永远感激你!
如果您忘记了元组和其他实现细节,而专注于树,
- 如果树为空,则总和为0
- 否则,它是"这个节点"中的数字和子树的总和
在Python中:
def tree_sum(t):
return 0 if is_empty(t) else data(t) + tree_sum(left(t)) + tree_sum(right(t))
请注意,这与树的表示方式完全无关。
现在我们可以为"元组树"添加与树相关的函数:
def is_empty(t):
return t is None
def data(t):
return t[1]
def left(t):
return t[0]
def right(t):
return t[2]
我解决了提示!以下是行之有效的解决方案:
sum = 0
def TreeSum(t):
global sum
for i in range(len(t)):
if t[i] == node_three:
TreeSum(node_three)
elif t[i] == node_two:
TreeSum(node_two)
elif t[i] == node_one:
TreeSum(node_one)
elif t[i] == None:
pass
else:
sum += t[i]
return sum
TreeSum(node_four) # This should return 18