Пользовательский двоичный объект дерева в Python

Question

Я пытаюсь написать собственный класс бинарного дерева.У меня уже есть узел:

class Node:

def __init__(self, value, **kwargs):
    self.value = value
    self.kwargs = kwargs

    for key, value in kwargs.items():
        setattr(self, key, value)

def __str__(self):
    main_str = '{value: ' + str(self.value)
    for key, value in self.kwargs.items():
        main_str += ', ' + str(key) + ': ' + str(value)
    main_str += '}'

    return main_str

Узел использует kwargs, потому что я использую его также для других целей.У меня проблема в древовидном классе:

from models.node import Node
class BinarySearchTree:

    def __init__(self):
        self.root = None

    def add_element(self, value):
        node = Node(value, left=None, right=None)

        if not self.root:
            self.root = node

        else:
            self.__add_element_recursive(self.root, value)

    def __add_element_recursive(self, parent, value):

        if not parent:
            node = Node(value, left=None, right=None)
            parent = node

        elif value > parent.value:
            self.__add_element_recursive(parent.right, value)

        else:
            self.__add_element_recursive(parent.left, value)

Это явно не работает, потому что параметры в python передаются не как ссылки, а как новые экземпляры.Например, я знаю, что это будет работать в C ++, потому что я могу просто передавать указатели на методы.

Как создать метод для добавления значения в дерево?Я думаю, что я мог бы упустить что-то действительно очевидное здесь.

Answer 1

Вам необходимо прикрепить созданный узел к ветви дерева.

попробуйте это:

def __add_element_recursive(self, parent, value):
    if value > parent.value:
        if parent.right: # there's a right node: lets go there
            self.__add_element_recursive(parent.right, value)
        else: # No node: we have found our spot
            parent.right = Node(value, left=None, right=None)
    elif parent.left: # There's a left node...lets go there
        self.__add_element_recursive(parent.left, value)
    else: # No node: we have found our spot
        parent.left = Node(value, left=None, right=None)