BST的递归插入

我已经使用循环在BST中插入了一个函数，它工作得很好。现在，当iam使用递归进行写操作时，我不知道为什么它不能正常工作，但根据我的逻辑是正确的。看起来没有newnode被添加到BST树和插入函数出来后树的头部再次变为NULL。BST的递归插入

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

请告诉我在算法中应该改变什么才能使其工作。

来源

2011-11-18 Zohaib

在你插入功能

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 ::头新分配的头。所以BST :: get_head将总是返回null。

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

来源

2011-11-18 14:32:00

但IAM发送头指针从主，因此电流将相同递归的一审头。 – Zohaib

您正在按值传递一个节点*。如果你通过引用BST ::头将被正确更新 –

但我想保持BST头私人。 – Zohaib

你的递归看起来不错，但你实际上并没有加上节点的任何地方！你只是在树上递归。

编辑您可以更改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 (&)

来源

2011-11-18 14:33:51

@Zohaib不，你只是创建一个新的节点，你不会把它添加到树中。 –

Does'nt this statement：current = newnode;会将newnode添加到树中。 – Zohaib

@Zohaib哎呀，错过它。我认为缩进不太好。 –

你应该试试这个

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

它工作正常.... jsut每次插入新节点时更新头节点，并且它将返回更新的当前节点。

来源

2016-01-03 06:29:29

只要改变你的功能

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

让您的输入指针为参考参数。

来源

2016-11-12 06:34:32 hankaixyz

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

希望这段代码解决您的问题

来源

2017-04-29 08:49:30

BST的递归插入

回答

相关问题