用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

我认为您的搜索函数的第三个 "else" 可能有错误的不等式： else if(dataToSearch >= rootAdd->data){ 搜索（rootAdd->left，dataToSearch）；

Answer 2

在

void insert(tree* RootAddress, int DataToInsert)

tree* RootAddress 是按值传递的。 "Wait a sec!"你说。 "That's a pointer dude! Get off the crack!" 指向的 tree ，如果有的话，通过引用传递，但是指针本身...只是一个副本。

这意味着

RootAddress = createNode(DataToInsert);

将新的 tree 分配给副本。来源 tree 不知道副本现在指向其他地方。

解决方案：

void insert(tree* & RootAddress, int DataToInsert)

通过引用传递指针。

接下来，

search(rootAdd->right, dataToSearch);

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

return false;

并且对于第一个节点之后的任何节点始终 returns 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;

之前是必要的

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

和

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

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

}

或聚合初始化

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

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

Implementing Binary Search Tree in C++, search does not work. Trying to print the elements of the node causes output to crash

c++

binary-tree

binary-search-tree

data-structures