c++ - 无法在函数调用之外更改节点参数

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;
}

所以我明白我的插入函数实际上并没有改变树的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。后一种选择很常见。

与其通过引用传递节点指针(以修复非更新问题)，不如考虑将其作为函数结果返回。