python-3.x 删除BST的根 _大数据知识库

我试图删除make函数，删除BST的任何元素。一切正常，除了当我试图删除树的根的情况下（根我的意思是打印树预订时列表的第一个元素）。当我试图删除该元素时，没有删除任何内容。我不知道是什么原因导致这个问题。

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

    def insert(self, value):
        if not self.value:
            self.value = value
            return
        if value < self.value:
            if self.left:
                self.left.insert(value)
                return
            self.left = Node(value)
            return
        if value > self.value:
            if self.right:
                self.right.insert(value)
                return
            self.right = Node(value)

    def pre_order(self, values):
        if self.value is not None:
            values.append(self.value)
        if self.left is not None:
            self.left.pre_order(values)
        if self.right is not None:
            self.right.pre_order(values)
        return values

    def delete(self, value):
        if self == None:
            return self
        if value < self.value:
            self.left = self.left.delete(value)
            return self
        if value > self.value:
            self.right = self.right.delete(value)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.value = min_larger_node.val
        self.right = self.right.delete(min_larger_node.value)
        return self

l = [1, 2, 3, 4, 5, 6]
BST = Node()
for i in l:
    BST.insert(i)

before_deleting = []
print(BST.pre_order(before_deleting))

BST.delete(1)

after_deleting = []
print(BST.pre_order(after_deleting))

除了当我试图删除树根的时候
这是因为根节点由BST变量表示，当调用delete时，没有任何东西被分配给该变量。
但还有更多的问题：

如果你调用delete方法时使用了一个在树中找不到的值，就会发生异常，因为对self.left.delete(value)的调用会在self.left是None的时刻进行。你可以通过调用该方法来避免这种情况，就像它是一个静态方法一样：Node.delete(self.left, value) .
当您在一个有两个子节点的节点上调用delete时，self.value = min_larger_node.val上发生错误。没有val属性。它应该是value。
如果用insert(0)将值0添加到树中，它可能会被覆盖。例如，如果输入是[2, 0, 1]，树最终将只有2和1。这是因为对not self.value条件的特殊处理（见下文）。
即使将BST.delete()的结果赋回BST名称，最终也会得到一个空树，其中BST是None，然后调用BST上的任何方法（如BST.pre_order()）都将失败并返回错误。
通过初始化树，您已经通过添加值为None的虚拟节点解决了前面的问题，这也是为什么您的代码中有此not self.value条件的原因-但它破坏了树的正确功能。您不应该有这样的虚拟节点，而是将空树视为没有**节点的树，而不是具有虚拟节点。相反，创建第二个类，它将处理可能为根设置的None值。
这不是一个大问题，但必须将一个列表作为参数传递给pre_order并不好。如果该方法自己创建列表并返回它，那就更好了。使用生成器根据前序遍历生成值也更Python化。

这是如何工作的：

class Node:
    def __init__(self, value):  # No special None value (removed default)
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        # No special condition for detecting dummy nodes here.
        if not self:
            return Node(value)
        if value < self.value:
            self.left = Node.insert(self.left, value)
        elif value > self.value:
            self.right = Node.insert(self.right, value)
        return self

    def delete(self, value):
        if not self:
            return self
        if value < self.value:
            self.left = Node.delete(self.left, value)  # Safe for when None
            return self
        if value > self.value:
            self.right = Node.delete(self.right, value)
            return self
        if not self.right:
            return self.left
        if not self.left:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.value = min_larger_node.value
        self.right = self.right.delete(min_larger_node.value)
        return self

    def pre_order(self):  # generator
        if self:
            yield from Node.pre_order(self.left)
            yield from Node.pre_order(self.right)
            yield self.value

class BST:  # Container class for managing the root
    def __init__(self):
        self.root = None  # An empty tree has no nodes: no dummies!

    def insert(self, value):
        self.root = Node.insert(self.root, value)    

    def delete(self, value):
        self.root = Node.delete(self.root, value)
    
    def pre_order(self):  # generator
        return Node.pre_order(self.root)

lst = [4, 2, 6, 1, 3, 5, 7]
tree = BST()
for value in lst:
    tree.insert(value)

tree.delete(4)

print(*tree.pre_order())  # 1 3 2 7 6 5

python-3.x 删除BST的根

1条答案

相关问题

热门标签

最新问答