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

Question

问题在于最后的删除步骤（在最后的 else 语句中）以及如何重新分配父节点对子节点的引用。代码来自 Mark Allen Weiss Data structures and Algorithm analysis in C++ 一书。整个代码参考：https://users.cis.fiu.edu/~weiss/dsaa_c++3/code/BinarySearchTree.h

据我对程序的理解，节点指针t指向要删除的节点
然后将该指针复制到节点指针 oldNode，然后 t 指向一个子节点（如果有的话）（在本例中是由于 findMin 而产生的右子节点） .
然后删除oldNode指向的节点。
但是指向的父节点的父节点指针(parent->left或parent->right如何oldNode)赋值给指向t?
指向的子节点 t?

的条件赋值会发生这种情况吗

方法如下：

 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类型指针的引用。也就是说，它是到 parent 的 left/right 节点指针的引用。

我做了一个简单的图表给你，因为“一图抵千言”。

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

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

How does the following Binary Search Tree node removal method work?

c++

binary-tree