下面的二叉搜索树节点移除方法是如何工作的？

Question

问题在于最后的删除步骤（在最后的else语句中）以及如何重新分配父节点对子节点的引用。代码来自Mark Allen Weiss的《C++中的数据结构和算法分析》一书。整个代码的引用:https://users.cis.fiu.edu/~weiss/dsaa_c++3/code/binarysearchtree.h

根据我对程序的理解，节点指针t指向要删除的节点。
然后将该指针复制到节点指针oldNode，然后t指向子节点（如果有）（在本例中，由于findMin是右子节点）。
然后删除oldNode指向的节点。
但是如何将父节点指针（oldNode指向的节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父节点的父

方法如下：

 void remove( const Comparable & x, BinaryNode * & t )
    {
        if( t == NULL )
            return;   // Item not found; do nothing
        if( x < t->element )
            remove( x, t->left );
        else if( t->element < x )
            remove( x, t->right );
        else if( t->left != NULL && t->right != NULL ) // Two children
        {
            t->element = findMin( t->right )->element;
            remove( t->element, t->right );
        }
        else
        {
            BinaryNode *oldNode = t;
            t = ( t->left != NULL ) ? t->left : t->right;
            delete oldNode;
        }
    }

//findMin method used in the above routine

BinaryNode * findMin( BinaryNode *t ) const
    {
        if( t == NULL )
            return NULL;
        if( t->left == NULL )
            return t;
        return findMin( t->left );
    }



 

Answer 1

在remove函数的签名中，binarynode*&t是对binarynode类型指针的引用。也就是说，它是对父节点的左/右节点指针的引用。

我为你做了一个简单的图表，因为“一图胜过千言万语”。

因此，基本上，它首先将引用所引用的实际指针（橙色箭头）保存到oldnode中，然后将被引用的变量（红点）设置为指向下一个子节点的指针（绿色箭头），跳过oldnode，最后删除oldnode。