python - 迭代地在二叉树中插入值

Question

我在迭代地在二叉树中插入元素时遇到问题。递归工作正常。

这是我当前的代码：

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,)

我找不到任何解决方案让它工作，有人可以帮忙吗？

标签： pythonalgorithmbinary-tree