BSTの再帰的挿入

Question

ループを使用してBSTに挿入する機能を作成しました。完全に正常に動作しています。 今、iamが再帰を使用してそれを行うときに、なぜそれが正しく動作しているのかわからないのですが、論理は正しいと思います。新しいノードが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; 
} 

私はそれを動作させるためにアルゴリズムを変更する必要があります教えてください。

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 ::ヘッドを設定することはありません。したがって、BST :: get_headは常にnullを返します。

これを修正する方法の1つは、ノードを返すための挿入のための方法です。あなたのケースではルートノードになり、BST :: headをこの値に設定します。

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

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

正常に動作します.jsut新しいノードが挿入されるたびにヘッドノードを更新し、更新された現在のノードを返す。

Answer 4

ただ、参照パラメータとして、あなたの入力ポインタを作る

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

としてあなたの関数を変更します。

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

希望は、このコードは、メインから問題