无法更改函数调用之外的节点参数

Question

我正在尝试将int插入节点到树中。据我所知，我的插入函数完美工作，但在函数之外，就像它从未发生过。这里是我的代码：

lcrs.h：

using namespace std; 
#include <cstdlib> 
#include <iostream> 

class node{ 
     public: 
     int data; 
     node *right; 
     node *below; 

     node() 
     { 
       right = NULL; 
       below = NULL; 
     } 
}; 

class lcrs{ 
     public: 
     node *root; 
     bool search(int, node*); 
     void print(node*); 
     void insert(int, node*); 
     int getHeight(node*); 

     lcrs() 
     { 
       root = NULL; 
     } 
}; 

而且lcrs.cpp：

using namespace std; 
#include "lcrs.h" 

bool lcrs::search(int x, node *b) 
{ 
     if(b == NULL) 
       return false; 
     else 
     { 
       if(b->data == x) 
         return true; 
       else 
       { 
         return search(x, b->right) || search(x, b->below); 
       } 
     } 
} 

void lcrs::print(node *z) 
{ 
     if(z->right == NULL && z->below == NULL) 
     { 
       cout << z->data << endl; 
     } 
     else if(z->below == NULL && z->right != NULL) 
     { 
       cout << z->data << ", "; 
       print(z->right); 
     } 
     } 
     else if(z->below != NULL && z->right == NULL) 
     { 
       cout << z->data << ", "; 
       print(z->below); 
     } 
     else 
     { 
       print(z->right); 
       print(z->below); 
     } 
} 

void lcrs::insert(int x, node *a) 
{ 
     if(a == NULL) 
     { 
       node *newnode; 
       newnode = new node; 
       newnode->data = x; 
       a = newnode; 
       cout << a->data << endl; 
     } 
     else if(a->data < x) 
     { 
       if(a->right != NULL) 
       { 
         insert(x, a->right); 
       } 
       else 
         a->right->data = x; 
     } 
     else 
     { 
       if(a->below != NULL) 
       { 
         insert(x, a->below); 
       } 
       else 
       { 
         a->below->data = x; 
       } 
     } 
} 

int lcrs::getHeight(node *h) 
{ 
     int height = 0; 
     if(h->below != NULL) 
     { 
       height ++; 
       return getHeight(h->below); 
     } 
     else 
       return height; 
} 

最后我的main.cpp：

using namespace std; 
#include <iostream> 
#include <cstdlib> 
#include <cstring> 
#include "lcrs.h" 

int main() 
{ 
char *temp1; 
char *temp2; 
temp1 = new char; 
temp2 = new char; 

lcrs tree; 

do{ 
     cout << "LCRS> "; 
     cin >> temp1; 
     if(strcmp(temp1, "quit") == 0) 
     { 
       return 0; 
     } 
     if(strcmp(temp1, "insert") == 0) 
     {  cin >> temp2; 
       bool error; 
       for(int i=0; i<strlen(temp2)-1; i++) 
       { 
         if(!isdigit(temp2[i])) 
         { 
           cout << "Error!" << endl; 
           error = true; 
         } 
       } 
       if(!error) 
       { 
         tree.insert(atoi(temp2), tree.root); 
         if(tree.root == NULL) 
           cout << "Root is null." << endl; 
         else 
           cout << tree.root->data << endl; 
       } 
     } 
     else if(strcmp(temp1, "height") == 0) 
     { 
       if(tree.root == NULL) 
         cout << "-1" << endl; 
       else 
         cout << tree.getHeight(tree.root); 
     } 
     else if(strcmp(temp1, "preorder") == 0) 
     { 
       tree.print(tree.root); 
     } 
}while(strcmp(temp1, "quit") !=0); 

return 0; 
} 

所以，我明白，我insert函数实际上并没有改变root的树，我只是不明白为什么。

非常感谢您的帮助。

Answer 1

您的代码：

void lcrs::insert(int x, node *a) 
{ 
     if(a == NULL) 
     { 
       node *newnode; 
       newnode = new node; 
       newnode->data = x; 
       a = newnode; 

↑这种分配不更新实际的参数，因为它是按值传递。

   cout << a->data << endl; 
     } 
     else if(a->data < x) 
     { 
       if(a->right != NULL) 
       { 
         insert(x, a->right); 
       } 
       else 
         a->right->data = x; 

↑在这里你知道（已确保），a->right是一个空指针。取消参考零点指针产生未定义的行为。例如崩溃。

 } 
     else 
     { 
       if(a->below != NULL) 
       { 
         insert(x, a->below); 
       } 
       else 
       { 
         a->below->data = x; 
       } 

↑在这里你知道（已经确保）a->below是一个空指针。取消参考零点指针产生未定义的行为。例如崩溃。 } }

作为一般性评论，below和right混合了两个隐喻。最好称它们为below和above或left和right。后一种选择非常普遍。

而不是通过引用传递节点指针（以解决非更新问题），请考虑将其作为函数结果返回。

Answer 2

您正在将指针传递给按值传递;要通过参考，您需要使用void lcrs::insert(int x, node * & a)，它通过引用a而不是a本身。会发生什么情况是指向该节点的指针被复制到本地变量中，在该函数内引用为a。然后该函数可以自由地更改副本（甚至是它指向的内存），但是当函数返回时，调用者不知道副本发生了什么，因为它仍然在查看原始内容。

通过引用传递，调用方和被调用函数都使用相同的事物，而不是一个使用副本，另一个使用原始方法。