Сумма всех узлов двоичного дерева

Question

Я пытаюсь написать программу для вычисления суммы всех узлов (включая корень) в двоичном дереве (не в двоичном дереве поиска), представленном списком списков.Я концептуально понимаю, что рекурсивный подход к этому является лучшим способом сделать это, но просто не могу понять код.Пока что мой код:

class BinaryTree:
    def __init__(self,rootObj, leftChild = None, rightChild = None):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
        self.node=[rootObj, leftChild, rightChild]
    def getrightChild(self):
        return self.rightChild
    def getleftChild(self):
        return self.leftChild
    def setRootObj(self,obj):
        self.key = obj
    def getRootObj(self):
        return self.key
    def sumTree(BinaryTree):
        if BinaryTree is None: return 0
        return sumTree(BinaryTree.leftChild) \ 
             + sumTree(BinaryTree.rightChild)\
             + BinaryTree.rootObj

print(sumTree([8,[],[]]))
print(sumTree([9, [6, [ ], [ ]], [65, [ ], [ ]]]))

Answer 1

Ну, из того, что я прочитал из этого кода, ваш рекурсивный алгоритм правильный. Однако в нем содержится много синтаксических ошибок, а также других семантических ошибок, которые делают невозможным правильную работу.

Вот что я вижу:

• Вы создали класс BinaryTree, но никогда не создавали его экземпляр. sumTree([...]) пытается вычислить ту сумму списка, которая не будет работать, потому что вы хотите, чтобы она делала это для объекта BinaryTree. Вам нужно проанализировать этот список и сначала создать экземпляр BinaryTree. (Может быть, tree = BinaryTree(*write your list here*), может быть. Но вы должны сделать так, чтобы ваш метод __init__() разрешал такое прохождение списка, конечно. См. Следующий пункт.)
• Ваш метод __init__() принимает BinaryTree объекты в качестве параметров, поэтому ваши списки не анализируются.
• В методе __init__() вы устанавливаете для обоих потомков значение None, поэтому у узла no никогда не будет дочерних узлов.
• При вызове метода sumTree() необходимо указать контекст. Это должно быть BinaryTree.sumTree(..). Вам все еще нужно создать экземпляр двоичного дерева, который будет передан методу sumTree.
• В методе sumTree() вы пытаетесь получить доступ к члену rootObj - который не существует, потому что вы назвали его key.

Помимо ошибок, я хотел бы указать на некоторые "запахи кода", если хотите.

• Вы должны переименовать параметр метода sumTree() в другое имя класса.
• В python нет необходимости в методах Getter. Вы можете получить доступ к членам напрямую. Если вы все еще хотите определить более сложное поведение get / set, вам следует взглянуть на python properties .
• Элемент node никогда не используется.

Answer 2

Вам не нужны все геттеры . Вы можете просто использовать методы доступа к объектам, например, tree_a.left_child. Во-вторых, вы не создали BinaryTree из своих детей, а это значит, что не имеет смысла запускать sum_tree на них. Прочитайте следующий код и убедитесь, что вы понимаете, что происходит.

Уверен, что то, что вы на самом деле хотите, это

class BinaryTree:
    def __init__(self, root, left_child=None, right_child=None):
        self.root = root
        self.left_child = None if not left_child else BinaryTree(*left_child)
        self.right_child = None if not right_child else BinaryTree(*right_child)
        self.node = [root, left_child, right_child]

    def set_root(self, root):
        self.root = root

    def sum_tree(self):
        tree_sum = 0
        if self.left_child:
            tree_sum += self.left_child.sum_tree()
        if self.right_child:
            tree_sum += self.right_child.sum_tree()

        return tree_sum + self.root

tree_a = BinaryTree(8)
tree_b = BinaryTree(9, [6, [], []], [65, [], []])
print(tree_a.sum_tree())
# 8
print(tree_b.sum_tree())
# 80
print(tree_b.left_child.node)
# [6, [], []]

Answer 3

Будьте осторожны,

self.key = rootObj
self.leftChild = None
self.rightChild = None

являются атрибутами объекта, поэтому вы не можете получить к ним доступ напрямую через ваш класс.Вы должны создать экземпляр типа

obj = BinaryTree(...)

, а затем вызвать метод

obj.sumTree(...)

Для вашего алгоритма суммирования самый простой способ вычислить сумму по вашему пути будет выглядеть примерно так:

class BinaryTree:       

    @classmethod
    def calc_sum(cls, list_tree):
        print(list_tree)
        if list_tree:
            left_node_value = BinaryTree.calc_sum(list_tree[1])
            right_node_value = BinaryTree.calc_sum(list_tree[2])
            return list_tree[0] + left_node_value + right_node_value
        return 0        

value = BinaryTree.calc_sum([9, [6, [ ], [ ]], [65, [ ], [ ]]])
print(value)