去除 BST 的根

Question

我正在尝试删除 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))

Answer 1

除了我尝试删除树根的情况外

这是因为根节点由您的

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

  并不是一件好事。如果该方法自己创建列表并返回它会更好。使用生成器根据预序遍历生成值也更像 pythonic。

这是如何工作的：

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