递归插入BST [英] Recursive insertion of BST

问题描述

我已经制作了一个使用循环插入BST的函数，它工作得很好. 现在，当我使用递归编写该代码时，我不知道为什么它不能正常工作，但是根据我的逻辑是正确的.似乎没有将newnode添加到BST树中，并且从插入函数中退出后，树的头部再次变为NULL.

I have made a function for insertion in BST using loops and it is working perfectly fine. Now, when iam writing to do it using recursion i don't know why it's not working properly, however the logic is correct according to me. It seems that no newnode is being added to the BST tree and head of the tree after coming out of the insertion function is again becoming 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;
}

请告诉我在算法上应该做些什么才能使其起作用.

Please tell me what should i change in the algorithm to make it work.

推荐答案

您的递归看起来不错，但实际上您没有在任何地方 add 节点！您只是在树上递归.

Your recursion looks fine, but you don't actually add the node anywhere! You just recurse through the tree.

编辑，您可以更改insert方法以将指针指向指针，如下所示:

Edit You can change the insert method to take a pointer to a pointer, like this:

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);
    }
}

在主调用中这样子:

BST.insert(arr[i], &BST.get_head());  // Note the ampersand (&)

这篇关于递归插入BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！