c++ - BST的递归插入

Question

我已经使用循环在 BST 中创建了一个插入函数，它工作得很好。 现在，当我使用递归编写它时，我不知道为什么它不能正常工作，但是根据我的逻辑是正确的。似乎没有新节点被添加到 BST 树中，并且从插入函数出来后的树头再次变为 NULL。

#include <iostream>
using namespace std;

class node{
public:
   int data;
   node *right;
   node *left;
   node(){
      data=0;
      right=NULL;
      left=NULL;
   }
};

class tree{
   node *head;
   int maxheight;
   void delete_tree(node *root);
public:
   tree(){head=0;maxheight=-1;}
   void pre_display(node* root);
   node* get_head(){return head;}
   void insert(int key,node* current);
};

void tree::insert(int key,node *current){
   if(current==NULL)
   {
      node *newnode=new node;
      newnode->data=key;
      current=newnode;
   }
   else{
      if(key<current->data)
         insert(key,current->left);
      else
         insert(key,current->right);
   }
   return;
}

void tree::pre_display(node *root){
   if(root!=NULL)
   {
      cout<<root->data<<" ";
      pre_display(root->left);
      pre_display(root->right);
   }
}

int main(){
   tree BST;
   int arr[9]={17,9,23,5,11,21,27,20,22},i=0;

   for(i=0;i<9;i++)
   BST.insert(arr[i],BST.get_head());

   BST.pre_display(BST.get_head());
   cout<<endl;

   system("pause");
   return 0;
}

请告诉我应该如何更改算法才能使其正常工作。

Answer 1

在您的插入函数中

void tree::insert(int key,node *current){
    if(current==NULL)
    {
        node *newnode=new node;
        newnode->data=key;
        current=newnode;
    }
    else{
        if(key<current->data)
            insert(key,current->left);
        else
            insert(key,current->right);
    }
    return;
}

您分配了一个新节点，但从未将 BST::head 设置为新分配的头。所以 BST::get_head 将始终返回 null。

解决这个问题的一种方法是让插入返回一个节点。在您的情况下，这将是根节点并将 BST::head 设置为此值。