删除 Python 中的一个二叉树节点。为什么 self != parent.left 或 parent.right？

Question

我有两个非常相似的程序，它们具有相同的目的（在 class 中删除一个节点作为二叉树方法）。其中只有一个工作。如果你告诉我原因，我会很高兴。

函数式程序，结尾为：

elif parent.left == self:
     parent.left = self.left if self.left is not None else self.right
            
elif parent.right == self:
     parent.right = self.left if self.left is not None else self.right

但是还有另一个程序不起作用并以：

结尾

elif parent.left == self:
     self = self.left if self.left is not None else self.right
                
elif parent.right == self:
     self = self.left if self.left is not None else self.right

那么为什么 self != parent.left 或 parent.right？

这是两个完整的方法：

#It works
def remove(self, value, parent=None):
    if value < self.value:
        if self.left is not None:
            self.left.remove(value, self)
            
    elif value > self.value:
        if self.right is not None:
            self.right.remove(value, self)
            
    else:                                                    
        if self.left is not None and self.right is not None: 
            self.value = self.right.getMinValue()
            self.right.remove(self.value, self)
            
        elif parent is None:
            if self.left is not None:
                self.value = self.left.value
                self.right = self.left.right
                self.left = self.left.left
            elif self.right is not None:
                self.value = self.right.value
                self.left = self.right.left
                self.right = self.right.right
            else:
                pass
            
        elif parent.left == self:
            parent.left = self.left if self.left is not None else self.right
            
        elif parent.right == self:
            parent.right = self.left if self.left is not None else self.right
#It does not
def remove(self, value, parent=None):
        if value < self.value:
            if self.left is not None:
                self.left.remove(value, self)
                
        elif value > self.value:
            if self.right is not None:
                self.right.remove(value, self)
        
        else:
            if self.left is not None and self.right is not None:
                self.value = self.right.getMinValue()
                self.right.remove(self.value, self)
                
            elif parent is None:
                if self.left is not None:
                    self.value = self.left.value
                    self.right = self.left.right
                    self.left = self.left.left
                elif self.right is not None:
                    self.value = self.right.value
                    self.left = self.right.left
                    self.right = self.right.right
                else:
                    pass
            
            elif parent.left == self:
                self = self.left if self.left is not None else self.right
                
            elif parent.right == self:
                self = self.left if self.left is not None else self.right

Answer 1

第二个片段失败的原因是它没有改变 parent.left 或 parent.right 所指的内容。

remove() 方法就是改变树结构，所以你想改变 parent.left 或 parent.right 所指的内容。更改 self 所指的内容不会改变树中的任何内容。

强制性 link 至 Ned Batchelder

删除 Python 中的一个二叉树节点。为什么 self != parent.left 或 parent.right？

Deleting a binary tree node in Python. Why self != parent.left or parent.right?

python

algorithm

binary-tree

binary-search

binary-search-tree