c++ - 用于插入操作的二叉搜索树代码问题

Question

在我的插入函数中，我无法从我的根节点访问左、右节点，终端输出证明了这一点。导致错误的原因。

代码主体:

#include<iostream>

class Node {
    public:
    int key; int data;
    Node * left;
    Node* right;
    Node (int key, int data):key(key),data(data),right(nullptr),left(nullptr){std::cout<<"ooga booga"<<std::endl;}

    //Recursive function to insert an key into BST
    void insert( int key,int data)
    {
        std::cout<<"reached here.Current node now has key="<<this->key<<" while input key is "<<key <<std::endl;
        // if the root is null, create a new node an return it
        if (this == nullptr)
        {
            std::cout<<"in 1st if block "<<this->key<<std::endl;    
            this->key=key;
            this->data=data;
            return;
        }

        // if given key is less than the root node, recur for left subtree
        if (key < this->key)
        {   
            std::cout<<"in 2nd if block "<<this->key<<std::endl;    
            left->insert(key, data);
            std::cout<<"in else block 2"<<this->key<<std::endl;
        }

        // if given key is more than the root node, recur for right subtree
        else
        {
            std::cout<<"in else block "<<this->key<<std::endl;  
            right->insert(key, data);}
            std::cout<<"in else block 2"<<this->key<<std::endl; 
            return;
        }

// A utility function to do inorder traversal of BST 
void inorder() 
{ 
    if (this != nullptr) 
    { 
        this->left->inorder(); 
        printf("%d \n", this->key); 
        this->right->inorder(); 
    } 
} 



};


// Driver Program to test above functions 
int main() 
{ 
    /* Let us create following BST 
              50 
           /     \ 
          30      70 
         /  \    /  \ 
       20   40  60   80 */
    Node *root=new Node(50,10); 
    std::cout<<root<<std::endl;
    std::cout<<root->left<<std::endl;
    //root=nullptr;
    std::cout<<"reached here"<<std::endl;
    std::cout<<"reached here.Root now has key="<<root->key<<std::endl;
    root->insert( 0,10); 
    root->insert( 20,10); 
    root->insert( 40,10); 
    root->insert( 70,10); 
    root->insert(  60,10); 
    root->insert( 80,10); 
    std::cout<<"reached here 2"<<std::endl;
    // print inoder traversal of the BST 
    root->inorder(); 

    return 0; 
} 

输出:

ooga booga
0x7fffc10c6e70
0
reached here
reached here.Root now has key=50
reached here.Current node now has key=50 while input key is 0
in 2nd if block 50
Segmentation fault (core dumped)

Answer 1

总体总结:

您正在使用 left=nullptr 和 right=nullptr 创建 Node 对象。

您实际上从未将这些left 和right 指针初始化为新节点。

在尝试访问left->insert之前，您必须先创建一个新节点。