二叉搜索树的递归插入

Question

我已经编写了一个使用循环进行二叉搜索树插入的函数，它完美地运行着。 现在，当我尝试使用递归来完成插入时，我不知道为什么它不能正常工作，但是根据我的逻辑，它是正确的。似乎没有新节点被添加到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;
}

请告诉我应该在算法中进行哪些更改才能使其正常工作。

- Zohaib

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设置为此值。

- parapura rajkumar

---

但是我从主函数发送头指针，因此在递归的第一个实例中，当前指针将与头指针相同。 - Zohaib

你正在按值传递一个node*。如果你按引用传递它，BST::head将被正确更新。 - parapura rajkumar

但是我想将二叉搜索树的头节点保持为私有。 - Zohaib

@Zohaib：对你来说，private是指它永远不会改变吗？ - PlasmaHH

如果你想保持事物的私密性... Node 应该是 BST 的类私有，而 BST 只应暴露迭代器以遍历树。 - parapura rajkumar

Answer 2

你的递归看起来没问题，但你实际上没有在任何地方添加节点！你只是通过树进行递归。

编辑：你可以将insert方法更改为接受指向指针的指针，像这样：

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 (&)

- Some programmer dude

---

@Zohaib 不，你只需要创建一个新节点，而不是将其添加到树中。 - Some programmer dude

这个语句：current=newnode; 不会将 newnode 添加到树中吗？ - Zohaib

@Zohaib 哎呀，我看错了。我的意见是缩进不太好。 - Some programmer dude

@Zohaib 是的，我这里有点累了，今天结束了，知道什么出了问题，稍后再看看。 - Some programmer dude

Answer 3

你应该尝试这个

             node  tree:: insert ( int key , node * current )  {

                     if ( ! current ) {
                           node * newnode = new node ;
                           newnode -> key = key;
                           current = newnode ;
                      }
                    else if ( key < current -> key )  {
                        current -> left = insert ( key , current ->left 
                         }
                    else 
                       current -> right = insert ( key , current->right )
                return current ;
               }

它运行良好...每当插入新节点时，只需更新头节点，它将返回更新后的当前节点。

- user5457519

Answer 4

void insertNode_recursive(int value, TreeNode *current)
{
    if (current == NULL)
    {
        if (current == NULL && isEmpty())
        {
            TreeNode *new_node = new TreeNode(value);
            current = new_node;
            root = new_node;
        }
        else
        {
            TreeNode *new_node = new TreeNode(value);
            current = new_node;
        }
    }
    else
    {
        if (value < current->getValue())
        {
            insertNode_recursive(value, current->getLeft());
        }
        else if (value > current->getValue())
        {
            insertNode_recursive(value, current->getRight());
        }
        else
        {
            cout << "\nDuplicate Value are Not Allowed\n";
        }
    }
}

这段代码用于递归打印树节点，非常有用。

- Muhammad Abubakar

Answer 5

只需将您的函数更改为

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

将您的输入指针作为引用参数。

- hankaixyz

Answer 6

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

node* root=NULL;

node* create(node* head,int val){
    if(head==NULL){
        node* nn=new node;
        nn->data=val;
        nn->left=NULL;
        nn->right=NULL;
        head=nn;
    }
    else if(val<head->data)
        head->left=create(head->left,val);
    else if(val>head->data)
        head->right=create(head->right,val);
    return head;
}

int main(){
    int num=0;
    cout<<"Enter value in tree or press -1 to Exit\n";
    while(num!=-1){
        cin>>num;
        if(num==-1){
            cout<<"\nTree Created\n";
            break;
        }
        else{
            root=create(root,num);
        }
    }
}

希望这段代码能解决你的问题。

- Aditi Saini