がバイナリツリーにノードを挿入します -

Question

繰り返し質問再帰するために反復変換：

を最近、私は（バイナリ検索ツリー）データ構造を読んでいる、私は非常によく再帰を理解し、同様にそれをトレースすることができます。

私はいつも私のために働いた、つまりループでプログラムを書いてから、ループをなくして再帰関数を書くアプローチを使いました。基本条件はループ終了条件と同じです。

しかし、私のループメソッドを使わないで書くと、失敗に終わります。 バイナリ検索ツリーにノードを挿入するための再帰関数を書くことができませんでした（ただし、解を参照して正しく理解しましたが）。

親切に私を導く、それを改善する方法は？

#include<stdio.h> 
#include<stdlib.h> 
struct node 
{ 
    int data; 
    struct node *left;//To store the address of the left child 
    struct node *right;//To store the address of the Right child 
}; 
struct node * root; 
struct node *createnewnode(int x) 
{ 
    struct node *n=(struct node *)malloc(sizeof(struct node)); 
    n->data=x; 
    n->left=NULL; 
    n->right=NULL; 
    return n; 
} 
void Insert(int x) 
{ 
    struct node *a,*b; 
    struct node *temp=root; 
    if(root==NULL) 
     root=createnewnode(x); 
    else 
    { 
     while(1) 
     { 
      if(x<=temp->data) 
       { 
       if(temp->left!=NULL) 
        temp=temp->left; 
       else 
       { 
        a=createnewnode(x); 
        temp->left=a; 
        break; 
       } 
       } 
      else 
       { 
       if(temp->right!=NULL) 
        temp=temp->right; 
       else 
       { 
        a=createnewnode(x); 
        temp->right=a; 
        break; 
       } 
       } 
     } 
    } 

} 
int main() 
{ 
    root==NULL;//Empty Tree 
    Insert(15); 
    Insert(10); 
    Insert(20); 
    Insert(25); 
    return 0; 
} 

編集：以前のコードを投稿していないため申し訳ありません。 これはノードを挿入するために書いたコードですが、これを再帰的メソッドに変換するにはどうすればいいですか？

Answer 1

再帰挿入は、常に次の質問をします。現在のノードにノードを挿入することはできますか？root？ rootがnot nullであるからではない場合は、左または右のサブツリーで再帰する必要があるかどうかを確認し、Insertを再帰的に呼び出す必要があります。

次のようなものはあなたにそれを

Node* Insert(Node* root, int x) { 
    if (root == NULL) 
    return createnewnode(x); 
    else 
    if (x <= root->data) 
     root->left=Insert(root->left); 
    else 
     root->right=Insert(root->right); 
}