1

我正在制作一个试图将 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函数实际上并没有改变tree的根，我只是不明白为什么。

非常感谢您的帮助。

4

2 回答 2

2

你的代码：

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了两个隐喻。最好称它们为belowand above，或leftand right。后一种选择很常见。

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

于 2012-11-13T03:28:01.910 回答
1

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

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

于 2012-11-13T03:34:46.157 回答