二叉树删除函数实现求助：基于Minimum函数修复Del方法

原问题 #

已实现Python二叉树类，包含Add、Find、Minimum、Nastepnik等可正常运行的方法，尝试基于Minimum实现Del节点删除功能，但代码无法正常运行，推测问题出在Minimum的使用逻辑上，同时对类的使用存在困惑。

可正常运行的二叉树类代码 #

class node(object):
    def __init__(self, number=None, par=None):
        self.number=number
        self.left=None
        self.right=None
        self.parent=par

class tree(object):
    def __init__(self):
        self.dummy=node()
    def Add(self, num, nd=None):
        if(nd==None):
            nd=self.dummy.right
        if(nd==None):# jeśli drzewo było puste
            self.dummy.right=node(num, par=self.dummy)
            return
        if(nd.number>num):
            if(nd.left==None):
                nd.left=node(num, par=nd)
                return
            else:
                self.Add( num, nd.left)
                return
        else:
            if(nd.right==None):
                nd.right=node(num, par=nd)
                return
            else:
                self.Add( num, nd.right)

    def Find(self, num_to_search, _node="nic"):
        if(_node=="nic"):
            _node=self.dummy.right
        if(_node==None):
            return None
        if(_node.number==num_to_search):
            return _node
        if(_node.number>num_to_search):
            return self.Find(num_to_search, _node.left)
        return self.Find(num_to_search, _node.right)

    def PrintID(self, _node="nic"):
        if _node=="nic":
            _node=self.dummy.right
        if _node==None:
            return
        self.PrintID(_node.left)
        print(_node.number, end=",")
        self.PrintID(_node.right)

    def KeysSum(self, _node="nic"): #suma kluczy
        if _node=="nic":
            _node=self.dummy.right
        if _node==None:
            return 0
        return self.KeysSum(_node.left)+self.KeysSum(_node.right)+_node.number
        
    def Height(self, _node="nic"): #wysokość 
        if _node=="nic":
            _node=self.dummy.right
        if _node==None:
            return 0
        right=self.Height(_node.right)+1
        left=self.Height(_node.left)+1
        if right>left:
            return right
        else:
            return left

    def Myk(self, _node="nic", depth=0): #rysuje drzewo
        if _node=="nic":
            _node=self.dummy.right
        if _node==None:
            return
        self.Myk(_node.right, depth+1)
        for i in range(depth):
            print("  ",end="")
        print(_node.number)
        self.Myk(_node.left, depth+1)
        
    def Minimum(self, _node="nic"): #zwraca węzeł o najmniejszym kluczu
        if _node=="nic":
            _node=self.dummy.right
        if _node==None:
            return
        else:   
            while _node.left != None:
                _node=_node.left
            return _node

    def Nastepnik(self, _node="nic"):
        if _node==None:
            return None
        if _node.right!=None:
            return self.Minimum(_node.right)
        par=_node.parent
        while par!=None and _node==par.right:
            _node=par
            par=_node.parent
        return par

原错误Del函数代码 #

def Del(self, _node):
        if _node==None:
            return
        if _node.right==None and _node.left==None:
            if _node==par.right:
                par.right=None
            if _node==par.left:
                par.left=None
            return
        if _node.right!=None and _node.left==None:
            if _node==par.right:
                par.right=_node.right
                _node.right.parent=par
            if _node==par.left:
                par.left=_node.left
                _node.right.parent=par
            return
        if _node.right==None and _node.left!=None:
            if _node==par.right:
                par.right=_node.left
                _node.left.parent=par
            if _node==par.left:
                par.left=_node.right
                _node.left.parent=par
            return
        if _node.right!=None and _node.left!=None:
            if _node==par.right:
                par.right=_node.right
                _node.right.parent=par
                self.Minimum(par)=_node.left
                _node.left.parent=self.Minimum(par)
            if _node==par.left:
                par.left=_node.left
                _node.left.parent=par
                self.Minimum(par)=_node.left
                _node.left.parent=self.Minimum(par)
            return

修复后的Del方法 #

将以下代码替换原错误的Del函数，作为tree类的方法：

def Del(self, _node):
    if _node is None:
        return
    
    par = _node.parent  # 获取当前节点的父节点，解决未定义变量问题

    # 情况1：当前节点是叶子节点（无左右子节点）
    if _node.left is None and _node.right is None:
        if _node == par.left:
            par.left = None
        else:
            par.right = None
        return
    
    # 情况2：只有右子节点
    if _node.left is None:
        child = _node.right
        if _node == par.left:
            par.left = child
        else:
            par.right = child
        child.parent = par
        return
    
    # 情况3：只有左子节点
    if _node.right is None:
        child = _node.left
        if _node == par.left:
            par.left = child
        else:
            par.right = child
        child.parent = par
        return
    
    # 情况4：有两个子节点，找后继节点（右子树的最小节点）
    successor = self.Minimum(_node.right)
    # 把后继节点的值赋值给要删除的节点
    _node.number = successor.number
    # 删除后继节点（后继要么是叶子，要么只有右子节点，复用前面的逻辑）
    self.Del(successor)

问题点说明与修复思路 #

1. 未定义par变量：原代码直接使用par但未从_node.parent获取，修复时先定义par = _node.parent。
2. 单节点替换赋值错误：原代码在左节点存在的情况下错误赋值par.left=_node.right，修复后统一获取对应子节点（左或右），正确替换父节点的指针。
3. 双节点逻辑完全错误：原代码试图给self.Minimum(par)赋值，这是语法错误且逻辑混乱。正确做法是利用Minimum找到右子树的最小节点（即后继），将其值覆盖到要删除的节点，再递归删除后继节点（因为后继节点的结构简单，只有右子节点或无节点）。
4. 代码冗余优化：合并重复判断逻辑，让代码更简洁易读。

内容的提问来源于stack exchange，提问作者Ashton