一.代码程序：

首先我们看下代码

#include <stdio.h>
#include <stdlib.h>

typedef int TElemtype;

typedef struct BiNode
{
	TElemtype data;//数据域
	struct BiNode * rchild ; // 指向右孩子的指针
	struct BiNode * lchild ; //指向左孩子的指针

}BiNode;

BiNode * Insert(BiNode *root,BiNode *p)
{
	if(root == NULL)
	{
		return p;
	}
	if(p == NULL)
	{
		return root;
	}
	//1 查找位置 
	BiNode *pf = root ;//遍历树
	BiNode *pk = NULL;//pk指向查找路径上的最后一个节点
	while(pf)
	{
		if(p->data < pf->data)
		{
			pk=pf;
			pf=pf->lchild;
		}
		else if(p->data > pf->data)
		{
			pk=pf;
			pf=pf->rchild;
		}
		else
			return root;
	}

	if(p->data < pk->data)
		pk->lchild=p;
	else if(p->data > pk->data)
		pk->rchild=p;
	
	return root;
}
void pre_order(BiNode *t)
{
	if(t!= NULL)
	{
		printf("%d ",t->data);
		pre_order(t->lchild);
		pre_order(t->rchild);
	}
}

void mid_order(BiNode *t)
{
	if(t!= NULL)
	{
		mid_order(t->lchild);
		printf("%d ",t->data);
		mid_order(t->rchild);
	}
}

void post_order(BiNode *t)
{
	if(t!= NULL)
	{
		post_order(t->lchild);
		post_order(t->rchild);
		printf("%d ",t->data);
	}
}


int main()
{
	BiNode * root =NULL;
	int d;
	while(1)
	{
		scanf("%d",&d);
		if(d==-1)
		{
			break;
		}
		BiNode *p =malloc(sizeof(*p));
		p->data =d;
		p->rchild =NULL;
		p->lchild =NULL;
		root=Insert(root,p);
	}
	//遍历树 
	printf("前序:");
	pre_order(root);
	printf("\n");

	printf("中序:");
	mid_order(root);
	printf("\n");

	printf("后序:");
	post_order(root);
	printf("\n");

	return 0;
}

二.分块解析：

（1）建立结点：

BiNode * root =NULL;
int d;
while(1)
{
	scanf("%d",&d);
	if(d==-1)
	{
		break;
	}
	BiNode *p =malloc(sizeof(*p));
	p->data =d;
	p->rchild =NULL;
	p->lchild =NULL;
	root=Insert(root,p);
}

结点的结构体变量：

typedef struct BiNode
{
	TElemtype data;//数据域
	struct BiNode * rchild ; // 指向右孩子的指针
	struct BiNode * lchild ; //指向左孩子的指针

}BiNode;

其中建立结点代码段中的?root=Insert(root,p)?是通过函数调用以及循环语句来把第一个输入的结点作为根结点，再通过之后的比较，来使后面的结点分配位置（左小右大）。

连接代码如下：

BiNode * Insert(BiNode *root,BiNode *p)
{
	if(root == NULL)
	{
		return p;
	}
	if(p == NULL)
	{
		return root;
	}
	//1 查找位置 
	BiNode *pf = root ;//遍历树
	BiNode *pk = NULL;//pk指向查找路径上的最后一个节点
	while(pf)
	{
		if(p->data < pf->data)
		{
			pk=pf;
			pf=pf->lchild;
		}
		else if(p->data > pf->data)
		{
			pk=pf;
			pf=pf->rchild;
		}
		else
			return root;
	}

	if(p->data < pk->data)
		pk->lchild=p;
	else if(p->data > pk->data)
		pk->rchild=p;
	
	return root;
}

其中先定义两个指针，一个用来遍历树，第二个用来存比完大小最后的结点的位置。

BiNode *pf = root ；

BiNode *pk = NULL;

?然后通过这两个指针来进行结点的插入。代码如下：

while(pf)
{
	if(p->data < pf->data)
	{
		pk=pf;
		pf=pf->lchild;
	}
	else if(p->data > pf->data)
	{
		pk=pf;
		pf=pf->rchild;
	}
	else
		return root;
}

if(p->data < pk->data)
	pk->lchild=p;
else if(p->data > pk->data)
	pk->rchild=p;
	
return root;

首先通过while循环找到插入位置，再通过比较大小，看插左还是右。

（3）遍历输出：

void pre_order(BiNode *t)
{
	if(t!= NULL)
	{
		printf("%d ",t->data);
		pre_order(t->lchild);
		pre_order(t->rchild);
	}
}

void mid_order(BiNode *t)
{
	if(t!= NULL)
	{
		mid_order(t->lchild);
		printf("%d ",t->data);
		mid_order(t->rchild);
	}
}

void post_order(BiNode *t)
{
	if(t!= NULL)
	{
		post_order(t->lchild);
		post_order(t->rchild);
		printf("%d ",t->data);
	}
}

通过递归的方法实现。