插入二叉樹的一個節點 - 轉換迭代遞歸

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