Chèn đệ quy BST

Question

Tôi đã thực hiện một chức năng để chèn vào BST bằng cách sử dụng vòng lặp và nó hoạt động hoàn toàn tốt. Bây giờ, khi iam viết để làm điều đó bằng cách sử dụng đệ quy tôi không biết tại sao nó không hoạt động đúng, tuy nhiên logic là chính xác theo tôi. Có vẻ như không có newnode đang được thêm vào cây BST và đứng đầu của cây sau khi ra khỏi chức năng chèn một lần nữa trở thành 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; 
} 

Hãy cho tôi biết tôi nên thay đổi gì trong thuật toán để làm cho nó hoạt động.

Answer 1

Trong chèn của bạn chức năng

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

bạn phân bổ một nút mới nhưng không bao giờ đặt BST :: đối đầu mới phân bổ. Vì vậy, BST :: get_head sẽ luôn trả về null.

Một cách để khắc phục điều này là chèn để trả về một nút. Đây sẽ là nút gốc trong trường hợp của bạn và đặt đầu BST :: thành giá trị này.

Answer 2

Lần đệ quy của bạn có vẻ ổn nhưng bạn không thực sự thêm nút vào bất kỳ đâu! Bạn chỉ cần recurse thông qua cây.

Sửa Bạn có thể thay đổi phương pháp insert để có một con trỏ đến một con trỏ, như thế này:

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

Và trong chính gọi nó là như thế này:

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

Answer 3

bạn nên cố gắng này

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

nó hoạt động tốt .... jsut cập nhật nút đầu mỗi lần khi một nút mới được chèn vào và nút đó sẽ trả về nút hiện tại được cập nhật.

Answer 4

Chỉ cần thay đổi chức năng của bạn như

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

làm cho con trỏ đầu vào của bạn như một tham số tham khảo.

Answer 5

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

hy vọng mã này giải quyết vấn đề của bạn