Итеративная вставка значений в двоичное дерево - PullRequest
Новая
       19

Итеративная вставка значений в двоичное дерево

1 голос
/ 19 апреля 2020

У меня проблема с вставкой элемента в двоичное дерево итеративно . Рекурсия работает нормально.

Это мой текущий код: 

class SearchTree:
    def __init__(self, value):
        self.empty = True
        self.value = value
        self.left = None
        self.right = None

    def is_empty(self):
        return self.empty

    def get_value(self):
        return self.value

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

    def elem(self, value):
        if self.is_empty():
            return False
        elif value < self.value:
            return self.left.elem(value)
        elif value > self.value:
            return self.right.elem(value)
        else:
            return True

    def add_recursive(self, value):
        if self.is_empty():
            self.empty = False
            self.value = value
            self.left = SearchTree(value)
            self.right = SearchTree(value)
            return True
        else:
            if value < self.value:
                return self.left.add_recursive(value)
            elif value > self.value:
                return self.right.add_recursive(value)
            else:
                return False

    def add_iterative(self, value):
        new_node = SearchTree(value)
        x = self
        y = None
        while x.empty is False:
            y = x
            if value < x.value:
                x = x.left
            else:
                x = x.right
        if y is None:
            self.empty = False
            self.value = value
            self.left = SearchTree(value)
            self.right = SearchTree(value)
            return True
        elif value < y.value:
            y.left = new_node
        elif value > y.value:
            y.right = new_node
        else:
            return False

    def __str__(self):
        if self.is_empty():
            return ""
        else:
            return "(" + str(self.left) + "," + str(self.value) + "," + str(self.right) + ")"

И это тестовый файл: 

import random
from searchtree import SearchTree

l = []
for i in range(10):
    l.append(random.randint(0, 10))

st_re = SearchTree(10)
st_it = SearchTree(10)

for r in l:
    st_re.add_recursive(r)
    st_it.add_iterative(r)

print(l)
print(st_re)
print(st_it)

Текущий вывод, который я получаю:

случайный список: [1, 7, 6, 5, 7, 5, 10, 1, 4, 8]

двоичное дерево добавлено рекурсивно :(, 1, (((((,, 4, ), 5,), 6,), 7, (((, 8,), 10,)))

двоичное дерево добавляется итеративно: (, 1,)

Не могу найти ни одного решение, чтобы заставить его работать, кто-нибудь может помочь?

...