c++ - 我应该如何定义一个返回指针引用的函数？ (引用指针与指向指针的指针)

Question

我想实现如下功能:删除二叉搜索树中某个值的节点。我想分两步完成:1.找到值的节点2.删除节点。

//Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

为了简化问题，假设要删除的节点是一片叶子，那么我们可以直接删除。

我实现了返回树节点指针引用的搜索功能，所以我可以直接改变树结构而不需要跟踪父节点。但它不起作用(节点未删除)。

TreeNode *&searchBST(TreeNode *&root, int val)
{
    if (!root)
        return root;
    if (root->val == val)
        return root;
    else if (root->val > val)
    {
        return searchBST(root->left, val);
    }
    else
    {
        return searchBST(root->right, val);
    }
}

我还实现了返回指向 treenode 指针的搜索函数，它可以工作。

TreeNode **searchBST(TreeNode *&root, int val)
{
    if (!root)
        return &root;
    if (root->val == val)
        return &root;
    else if (root->val > val)
    {
        return searchBST(root->left, val);
    }
    else
    {
        return searchBST(root->right, val);
    }
}

完整代码:

#include <iostream>
using namespace std;

//Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode *&searchBST(TreeNode *&root, int val)
{
    if (!root)
        return root;
    if (root->val == val)
        return root;
    else if (root->val > val)
    {
        return searchBST(root->left, val);
    }
    else
    {
        return searchBST(root->right, val);
    }
}
TreeNode *deleteNode(TreeNode *root, int key)
{
    TreeNode *node = searchBST(root, key);
    if (!node)
        return root;
    node = NULL;
    return root;

}
int main()
{
    TreeNode n1(1), n2(0), n3(2);
    n1.left = &n2;
    n1.right = &n3;
    TreeNode *res = deleteNode(&n1, 2);
    return 0;
}

有效代码:

#include <iostream>
using namespace std;

//Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode **searchBST(TreeNode *&root, int val)
{
    if (!root)
        return &root;
    if (root->val == val)
        return &root;
    else if (root->val > val)
    {
        return searchBST(root->left, val);
    }
    else
    {
        return searchBST(root->right, val);
    }
}
TreeNode *deleteNode(TreeNode *root, int key)
{
    TreeNode **node = searchBST(root, key);
    if (!node)
        return root;
    *node = NULL;
    return root;
}
int main()
{
    TreeNode n1(1), n2(0), n3(2);
    n1.left = &n2;
    n1.right = &n3;
    TreeNode *res = deleteNode(&n1, 2);
    if (res->right != NULL)
        cout << res->right->val << endl;
    return 0;
}

Answer 1

How should I define a function that return reference to a pointer?

你写的方式TreeNode *&searchBST(TreeNode *&root, int val)很好。你的问题的前提是错误的:你的工作版本和非工作版本之间的区别不是 searchBST但是deleteNode .

这里:

TreeNode *deleteNode(TreeNode *root, int key)
{
    TreeNode *node = searchBST(root, key);
    if (!node)
        return root;
    node = NULL;
    return root;

}

node是局部变量并赋值 NULL它对实际的树没有任何影响。

另一方面:

TreeNode *deleteNode(TreeNode *root, int key)
{
    TreeNode **node = searchBST(root, key);
    if (!node)
        return root;
    *node = NULL;
    return root;
}

node是指向您存储在树中的实际指针的指针。因此，您可以取消引用它以分配给树中的指针。

how can I free the space of the node I deleted?

你没有!

delete *node doesn't work.

为什么要用delete ？你从未使用过 new ，因此你也不应该使用 delete释放内存。主要内容:

int main()
{
    TreeNode n1(1), n2(0), n3(2);
    //...
}   // <---

n1 , n2和 n3使用自动存储并在它们超出范围时被销毁(即当 main 返回时，在 <--- )。