c++ - 用C++实现二叉搜索树，搜索不起作用。尝试打印节点的元素会导致输出崩溃

Question

我正在尝试用 C++ 实现二叉搜索树。这是我写的代码。在我尝试搜索它们时提供一些输入后，除了根节点的值外，在每种情况下输出都为“false”。当我试图检查循环是否正确匹配节点中的值时，程序崩溃了。然而，如果不打印，程序只会输出负数而不会崩溃。我哪里搞砸了？

#include<iostream>
using namespace std;

struct tree {
    int data;
    tree* left;
    tree* right;
};

class BST{

public:
    tree* rootTreeNode = NULL;

    tree* createNode(int incomingData){
        tree* newNode = new tree();
        newNode->data = incomingData;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

    void insert(tree* RootAddress, int DataToInsert){
        if(RootAddress == NULL) {
            if(rootTreeNode == NULL) {
                rootTreeNode = createNode(DataToInsert);
            }
            else {
                RootAddress = createNode(DataToInsert);
            }
        } else if(DataToInsert > RootAddress->data) {
            insert(RootAddress->right, DataToInsert);

        } else if(DataToInsert <= RootAddress->data) {
            insert(RootAddress->left, DataToInsert);
        }
    }



    bool search(tree* rootAdd, int dataToSearch){

        if(rootAdd == NULL) {
            return false;
        }

        else if(rootAdd->data == dataToSearch){
            return true;
        }
        else if(dataToSearch > rootAdd->data ){
            search(rootAdd->right, dataToSearch);
        }
        else if(dataToSearch <= rootAdd->data){
            search(rootAdd->left, dataToSearch);
        }
        return false;
    }


    void disp(){
        tree * curr = rootTreeNode;

        while(1){
            cout << curr->data <<endl;

            int ch;

            cout << "Enter 1 for left and 2 for right" <<endl;
            cin >> ch;

            if(ch == 1){
                curr = curr->left;
            }else if(ch == 2){
                curr = curr->right;
            } else if(ch == 3){
                break;
            }
        }
    }

};




int main() {
    BST BinartSearchTree;

    while(1) {
    int c;
    cout << "Enter (1) to insert a value.\nEnter (2) to search value.\nEnter (3) to Check the tree.\n.=> ";
    cin >> c;

    if(c == 1){
        int input;
        cout << "Enter your Data: ";
        cin >> input;

        BinartSearchTree.insert(BinartSearchTree.rootTreeNode, input);

    } else if(c==2){
        int x;
        bool result;
        cout << "Enter element you wanna search: ";
        cin >> x;
        result = BinartSearchTree.search(BinartSearchTree.rootTreeNode, x);
        if(result) {
            cout << "The given data Exists in the tree\n\n";
        } else {
            cout <<"The Data ain't in the tree\n\n";
        }
    } else if(c==3){
        BinartSearchTree.disp();
    }


    }
}

Answer 1

在

void insert(tree* RootAddress, int DataToInsert)

tree* RootAddress按值传递。 “等一下!”你说。 “那是指针老兄!离开裂缝!” tree指向，如果有的话，通过引用传递，但指针本身......只是一个拷贝。

这意味着

RootAddress = createNode(DataToInsert);

分配新的 tree一份。出处tree不知道拷贝现在指向其他地方。

解决方案:

void insert(tree* & RootAddress, int DataToInsert)

通过引用传递指针。

下一步，

search(rootAdd->right, dataToSearch);

不对 search 返回的值做任何事情无论是否找到该值，该函数都会落入

return false;

并且总是为第一个之后的任何节点返回 false。不是很有用。

解决方案:

bool search(tree* rootAdd, int dataToSearch){

    if(rootAdd == NULL) {
        return false;
    }

    else if(rootAdd->data == dataToSearch){
        return true;
    }
    else if(dataToSearch > rootAdd->data ){
        return search(rootAdd->right, dataToSearch);
    }
    else if(dataToSearch < rootAdd->data){
        return search(rootAdd->left, dataToSearch);
    }
}

其他说明:

void disp()

不检查以确保迭代不会离开树的末端。 curr 的测试不是 NULL在 cout << curr->data <<endl; 之前是必需的

此外，树迭代的引导将使调试变得异常烦人。如果这是类作业的一部分，请与教师确认这是他们真正想要的。如果这是出于您自己的恶意目的，您可能通过实现一种常见的遍历算法并打印整个列表来更好地服务于您。

和

考虑更换 tree* createNode(int incomingData)与合适的 Tree构造函数

tree(int incomingData): data(incomingData), left(nullptr), right(nullptr)
{

}

或聚合初始化

rootTreeNode = new tree{DataToInsert, nullptr, nullptr};