c++ - 为什么使用本地指针不起作用

Question

inline void insert(node *root, int value)
{
    if(!root)
    {
        root = new node();
        root->value = value;
    }
    else
    {
        node *itr = root;
        while(1)
        {
            if(itr->value > value)
                itr = itr->left;
            else
                itr = itr->right;
            if(!itr)
            {
                itr = new node();
                itr->value = value; 

                break;
            }

        }
    }
}

//像这样调用插入函数

node *head = 0;
insert(head, 5);
insert(head, 10);
insert(head, 3);
insert(head, 1);
insert(head, 4);

我知道这段代码行不通，因为 insert 函数中的 'itr' 是一个局部变量，因此它不会反射(reflect)方法之外的树。但是，我不清楚为什么它不起作用。尽管“itr”是局部变量，但“itr”指向的位置与“root”指向的位置相同。此外，我取消引用它以移动“左”或“右”，所以我认为它应该有效。

我认为这是按值传递指针与指针传递指针的基本问题，但我找不到关于为什么我不能使用指针的局部变量更改树的明确解释。

Answer 1

假设你有

int x = 0;
int y = x;
y = 3478;

你会期望 x 也包含 3478 吗？
我知道你不会，你的 root 和 itr 也是如此。

这是一个经典的纸笔问题(大多数指针问题都是)，当您遇到这样的问题时，绝对值得拔掉一些枯树。

这是你的一个案例的 ASCII 版本，你想在右边插入，右边是 NULL。
箭头表示各个变量指向的位置。

函数开始:

           ____
root ---> |    |
          ------
           / \
          /   \
       left   NULL

---

itr = root;    
           ____
root ---> |    | <--- itr
          ------
           / \
          /   \
       left   NULL

---

itr = itr->right;
           ____
root ---> |    | 
          ------
           / \
          /   \
       left   NULL <--- itr

---

if (!itr)
    itr = new node();

           ____
root ---> |    | 
          ------
           / \
          /   \                   ____
       left   NULL      itr ---> |    |
                                  ----

如您所见，输入树根本没有被修改，您只是在其外部分配了一个新节点并将其留在那里。

这会起作用:

           ____
root ---> |    | <--- itr
          ------
           / \
          /   \
       left   NULL

---

   if (!itr->right)
   {
       itr->right = new node()
   }


           ____
root ---> |    | <--- itr
          ------
           / \
          /   \
       left   ____
             |    |
              ----

铅笔和纸是找出指针的最佳方法。