时间戳

首页 > 解决方案 > 在 Python 中删除二叉树节点。为什么 self != parent.left 或 parent.right？

python - 在 Python 中删除二叉树节点。为什么 self != parent.left 或 parent.right？

问题描述

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

功能程序，它以：

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

标签： pythonalgorithmbinary-treebinary-search-treebinary-search

解决方案

第二个片段失败的原因是它没有改变什么parent.left或parent.right引用。

该remove()方法完全是关于更改树结构，因此您想要更改parent.left或parent.right引用什么。更改self引用的内容不会改变树中的任何内容。

Ned Batchelder的强制性链接

推荐阅读