Двоичное дерево не показывает присутствующие узлы Python - PullRequest
Новая
       11

Двоичное дерево не показывает присутствующие узлы Python

1 голос
/ 16 февраля 2020

Я пытаюсь реализовать двоичное дерево с методами insert и preorder.

После добавления элементов в дерево отображается только один элемент.

Может кто-нибудь сообщить мне, где я ошибаюсь.

Ниже приведен код: 

class Node(object):

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = None
        self.right = None

    def __repr__(self):
        return '{}'.format(self.value)

class BinaryTree(object):

    def __init__(self, root=None):
        self.root = root

    def add(self, value):
        val = self.root
        if not val:
            self.root = value
            val = value

        elif not val.left:
            val = value
        elif not val.right:
            val = value
        else:
            self.left = val.left.add(value)
        return val

    def preorder(self):
        val = self.root
        if not val: # this will handle the case when root node is None.
            return 
        print(val)
        if val.left:
            val.left.preorder()
        if val.right:
            val.right.preorder()


def main():

    binary_tree = BinaryTree()

    print("Adding nodes to the tree")
    for i in range(1, 11):
        node = Node(i)
        binary_tree.add(node)

    print("Printing preorder...")
    binary_tree.preorder()

if __name__ == '__main__':
    main()

Выход 

Adding nodes to the tree
Printing preorder...
1

1 Ответ

0 голосов
/ 16 февраля 2020

Ваш код содержит несколько разных ошибок. Некоторые из них касаются того, как вы модифицируете self.root (или не можете), другие связаны с попытками рекурсии для неправильных типов.

Первая проблема, которая заключается в том, почему ваш код завершается сбоем без вывода сообщений, связана с ваш BinaryTree.add метод, который ничего не делает, когда дерево пусто. Проблема состоит в том, что вы инициализируете локальную переменную val равной вашему root узлу (если он у вас есть), а затем позже привязываете ее к другому значению. Но это никогда не меняет значение root, только локальную переменную val.

Я предлагаю вам избавиться от val все вместе, а вместо этого читать и писать self.root напрямую. Тогда вы действительно добьетесь некоторого прогресса и увидите другие проблемы.

Вот начало: 

def add(self, value):
    if self.root is None:
        self.root = value
    elif self.root.left.left is None:
        self.root.left = value
    ...

Другие упомянутые мной проблемы похожи, хотя одна встречается в BinaryTree.add а другой в BinaryTree.preorder. Проблема в том, что вы пытаетесь вызвать один и тот же метод (add или preorder) на одном из дочерних элементов вашего root узла. Но узлы являются Node экземплярами и не имеют методов, которые вы определили в классе BinaryTree.

Эта проблема не имеет такого очевидного решения, как предыдущий. Одна идея может состоять в том, чтобы переместить логи c для методов в класс Node (где вы можете легко выполнить рекурсию) и оставить только код обработки пустого дерева в методах BinaryTree (все остальное делегируется root узел).

...