插入二叉树的一个节点 - 转换迭代递归

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