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

Question

При реализации методов add_node и search для двоичного дерева, я получаю RecursionError: превышена максимальная глубина рекурсии

Код:

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


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

    def add_node(self, node, value):
        node = self.root
        if node is not None:
            if not node.value:
                node.value = value
            elif not node.left:
                node.left = value
            elif not node.right:
                node.right = value
            else:
                node.left = self.add_node(node.left, value)
        else:
            self.root = TreeNode(value)

    def search(self, value):
        node = self.root
        found = False
        while node is not None:
            if node.value == value:
                found = True
            if node.left:
                found = node.left.search(value)
            if node.right:
                found = found or node.left.search(value)
        return found



def main():
    binary_tree = BinaryTree()
    binary_tree.add_node(binary_tree.root, 200)
    binary_tree.add_node(binary_tree.root, 300)
    binary_tree.add_node(binary_tree.root, 100)
    binary_tree.add_node(binary_tree.root, 30)
    binary_tree.traverse_inorder(binary_tree.root)
    print(binary_tree.search(200))


if __name__ == '__main__':
    main()

Ошибка:

Traceback (most recent call last):
  File ".\binary_tree_test20.py", line 51, in <module>
    main()
  File ".\binary_tree_test20.py", line 45, in main
    binary_tree.add_node(binary_tree.root, 30)
  File ".\binary_tree_test20.py", line 22, in add_node
    node.left = self.add_node(node.left, value)
  File ".\binary_tree_test20.py", line 22, in add_node
    node.left = self.add_node(node.left, value)
  File ".\binary_tree_test20.py", line 22, in add_node
    node.left = self.add_node(node.left, value)
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

Answer 1

Это лекарство, которое я могу вам дать.

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

def _add_node(node, value):
    if not node.value:
        node.value = value
    elif not node.left:
        node.left = TreeNode(value)
    elif not node.right:
        node.right = TreeNode(value)
    else:
        _add_node(node.left, value)

class BinaryTree:
    # ...

    def add_node(self, value):
        node = self.root
        if node is not None:
            _add_node(node, value)
        else:
            self.root = TreeNode(value)

    # ...



def main():
    binary_tree = BinaryTree()
    binary_tree.add_node(200)
    binary_tree.add_node(300)
    binary_tree.add_node(100)
    binary_tree.add_node(30)

Хотя я рекомендую только расширить определение TreeNode без определения BinaryTree.

Answer 2

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

Кроме того, строка node.left = self.add_node(node.left, value) ожидает, что add_node возвратит новый узел, но ваш метод не возвращает что-нибудь. Когда он обновляет существующий узел, он должен просто вернуть измененный узел; если он создает новый узел, он возвращает этот узел.

    def add_node(self, node, value):
        if node is not None:
            if not node.value:
                node.value = value
            elif not node.left:
                node.left = value
            elif not node.right:
                node.right = value
            else:
                node.left = self.add_node(node.left, value)
            return node
        else:
            return TreeNode(value)

Вы бы назвали этот метод следующим образом:

binary_tree.root = binary_tree.add_node(binary_tree.root, 30)