递归创建二叉树(C版)

1. 明确每一步重复的任务:创建父结点，连接子结点
（1）申请一块树节点的内存空间
（2）将用户输入的数据赋值给申请的树节点
（3）确认申请树节点的左右子节点，在此处递归调用
2. 确认递归的形参和返回值
函数形式1：
若形参为空void，必定要返回值。返回当前结点地址，以便父结点连接；
函数形式2：
若形参为节点的地址，可以不用返回值，但是必须要用C++的引用特性；
综上，可以有两种函数形式的递归实现。本文主要针对C语言，所以只能使用函数形式1。至于函数形式2会在文章最后分享出来，供大家参考。
3. 确认递归结束条件：
由于是用户输入，所以应针对用户的输入做结束条件。比如如果是字符二叉数，可以把’#’等任意一个字符作结束条件；如果是整型二叉树，可以将<0的数据作为结束条件。

代码：
二叉树结点定义：

typedef struct BinaryTreeNode{
	int data;
	struct BinaryTreeNode *lchild, *rchild;//左右孩子指针 
}BinaryTreeNode, *pBinaryTreeNode;

生成二叉树函数：

pBinaryTreeNode CreatBinaryTree()
{
	pBinaryTreeNode node;
	int _data;

	scanf("%d", &_data);

	//确认递归的结束的条件
	if (_data < 0)//当用户输入<0时，递归结束
		return nullptr;

	//申请一块树节点内存
	node = (pBinaryTreeNode)malloc(sizeof(BinaryTreeNode));
	node->data = _data;

	//连接左右子结点
	node->lchild = CreatBinaryTree();//生成左子树 
	node->rchild = CreatBinaryTree();//生成右子树 
	return node;
}

注意输入的时候，每个数据用空格隔开。如对于如下的二叉树，应该输入：
1 2 -1 4 -1 -1 3 -1 5 -1 -1

至于打印处生成的二叉数，本文不在赘述，在文章C语言实现二叉树的非递归中序遍历中，我分享了C语言版的中序遍历方法，可以用来打印生成的二叉树，感兴趣的朋友可以看看。

附：函数形式2的二叉树生成函数

void CreatBinaryTree(pBinaryTreeNode& root)
{
	int _data;
	scanf("%d", &_data);

	//确认递归的结束的条件,由于是用户输入节点，当用户输入<0时，递归结束
	if (_data < 0){
		root = nullptr;//节点为空，此处必须写空，不然系统会分配一个不为空的地址
		return;
	}

	root = (pBinaryTreeNode)malloc(sizeof(BinaryTreeNode));
	root->data = _data;

	CreatBinaryTree(root->lchild);//生成左子树 
	CreatBinaryTree(root->rchild);//生成右子树 
}

本人水平有限，欢迎各位朋友批评指正。