Вычислить сумму целых чисел в двоичном дереве кортежей с помощью Python

Question

Мне было особенно трудно понять эту концепцию, и мой профессор не очень хорошо освещал эту тему.Проблема требует, чтобы я написал функцию, которая вычисляет сумму целых чисел, которые составляют двоичное дерево из кортежей.

Мне предоставляется следующий код:

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

Если вы поможете мне понять, как решить эту проблему, я получу вашу вечную благодарность!

Answer 1

Если вы забудете все о кортежах и других деталях реализации и сосредоточитесь на деревьях,

• Если дерево пустое, сумма будет равна 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]

Answer 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