c++ - 在递归中修改调用指针时出现问题

Question

所以我正在研究 BST，构建删除工具。

我的代码序列似乎工作正常 - Save 不更新父节点或根节点，并将将它发送到已删除节点地址的指针设置为 NULL。

我将一个指针传递给我的 Erase 和 RemoveNode 函数中的指针，以便直接影响实际导致递归调用的左、右或根数据成员。在遍历代码时，它在 remove 函数中将 *N 设置为 NULL，但这并未反射(reflect)在调用对象的数据中。我使用指针的指针方法不正确吗？如果是这样，有没有一种方法可以递归删除并能够在链接被破坏时修改先前的节点？

节点结构:

struct tNode
{
    tNode(int n)
    {
        data = n; 
        left = NULL; 
        right = NULL;
    }

    //Works, cleans all linked objects. 
    //Must remember to null links when removing wanted nodes
    ~tNode(void)
    {
        //cout << "Deleting " << data << endl;
        delete left;
        delete right;
    }

    // Data members
    int data;
    tNode* left;
    tNode* right;
};

在树上递归的橡皮擦函数:

    void BinSearchTree::Erase(int n, tNode** N)
    {
        tNode* node = *N;
        if (root)
        {
            if (node->data > n) // post order, to avoid moving many times over
            {
                if (node->left)
                {
                    Erase(n, &node->left);
                }
            }
            else
            {
                if (node->right)
                {
                    Erase(n, &node->right);
                }
            }

            if (node->data == n)
            {
                RemoveNode(&node);
            }
        }
    }

以及处理实际删除的 RemoveNode 函数:

void BinSearchTree::RemoveNode(tNode** N)
{
    tNode* node = *N;
    if (!node->left && !node->right) // is leaf
    {
        delete node; // remove node
        size--;
        *N = NULL; // null pointer for above node/structure
    }
    else if (!node->left) // right child
    {
        tNode* temp = node->right; // to strip out copied node when finished
        node->data = node->right->data; // copy right node into current node
        node->right = node->right->right;
        node->left = node->right->left;

        temp->right = NULL; // NULL because node destructor is recursive
        temp->left = NULL; // ^^
        delete temp;
        size--;
    }
    else if (!node->right) // left child
    {
        tNode* temp = node->left; // to strip out copied node when finished
        node->data = node->left->data; // copy left node into current node
        node->right = node->left->right;
        node->left = node->left->left;

        temp->right = NULL; // NULL because node destructor is recursive
        temp->left = NULL; // ^^
        delete temp;
        size--;
    }
    else // 2 children
    {
        tNode* temp = node->right; // find ideal child -> left-most right child
        tNode* parent = NULL; // keep track of owner of ideal child
        while (temp->left)
        {
            parent = temp;
            temp = temp->left;
        }

        node->data = temp->data; // copy ideal child to root
        if (parent)
        {
            parent->left = temp->right; // case that left-most child has right child of it's own
        }
        RemoveNode(&temp);
        size--;
    }
}

Answer 1

我想我看到了。当您从 Erase() 调用 RemoveNode() 时，您将值 &node 传递给它。改为传入 N。

事情是这样的:tNode* node = *N; 行在堆栈上创建了一个局部变量。 *N 的拷贝。虽然该变量与 *N 具有相同的值(一开始)，但它存储在内存中的不同位置:node 在堆栈上，而 *N 在某处在堆中。

因此，由于您将 &node 传递给 RemoveNode()，因此 node 发生了变化。不是 *N - 它在其他地方。但是，如果您传入，您将更改您想要的内容。

希望对您有所帮助!

PS:如果不清楚，请告诉我!写双指针可能比使用它们更难......