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的遞歸插入

回答

相關問題