C语言 在二叉树中插入节点 - 将迭代转换为递归

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中插入节点吗？如果不是因为rootnot 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);
}