摘要：
}node*creat{inti,n,key;scanf;for{scanf;t=Insert;}returnt;}voidInOrder//中序遍历输出{if(t!=NULL){InOrder;printf;InOrder;}}intmain(){node*t=NULL;t=creat;InOrder;return0;}数组实现：定义left[],right[]作为标记，记录但前节点是哪个点的左（右）孩子比如我们要对4，3，8，6，1。排序排好序后的二叉树如图：把这个过程在纸上用笔走一遍，你就会一目了然。
VonGang原创，转载请注明：http://www.cnblogs.com/vongang/
二叉排序数的（递归）定义：1、若左子树非空，则左子树所有节点的值均小于它的根节点；2、若右子树非空，则右子树所有节点的值均大于于它的根节点；3、左右子树也分别为二叉排序树。
如图：
链表实现（比较简单）：
View Code #include <stdio.h>
#include <malloc.h>
typedef structnode
{
intdata;
structnode *lchild;
structnode *rchild;
}node;
voidInit(node *t)
{
t =NULL;
}
node *Insert(node *t , intkey)
{
if(t ==NULL)
{
node *p;
p =(node *)malloc(sizeof(node));
p->data =key;
p->lchild =NULL;
p->rchild =NULL;
t =p;
}
else
{
if(key <t->data)
t->lchild =Insert(t->lchild, key);
else
t->rchild =Insert(t->rchild, key);
}
returnt; //important!}
node *creat(node *t)
{
inti, n, key;
scanf("%d", &n);
for(i =0; i <n; i++)
{
scanf("%d", &key);
t =Insert(t, key);
}
returnt;
}
voidInOrder(node *t) //中序遍历输出{
if(t !=NULL)
{
InOrder(t->lchild);
printf("%d ", t->data);
InOrder(t->rchild);
}
}
intmain()
{
node *t =NULL;
t =creat(t);
InOrder(t);
return0;
}
数组实现（这个有意思）：
定义left[], right[]作为标记，记录但前节点是哪个点的左（右）孩子
比如我们要对 4，3， 8，6，1。排序排好序后的二叉树如图：
把这个过程在纸上用笔走一遍，你就会一目了然。
My Code：
#include <stdio.h>
#include <string.h>#defineN 1000intl[N], r[N], key[N], flag, root;
voidinsert(intindex, intx)
{
if(x <=key[index])
{
if(l[index] ==-1) l[index] =flag;
elseinsert(l[index], x);
}
else
{
if(r[index] ==-1) r[index] =flag;
elseinsert(r[index], x);
}
}
voidInOrder(intindex)
{
if(l[index] !=-1) InOrder(l[index]);
printf("%d ", key[index]);
if(r[index] !=-1) InOrder(r[index]);
}
intmain()
{
inti, x, n;
memset(l, -1, sizeof(l));
memset(r, -1, sizeof(r));
scanf("%d", &n);
root =-1;
flag =0;
for(i =0; i <n; i++)
{
scanf("%d", &x);
if(root ==-1) key[++root] =x;
else
{
key[++flag] =x;
insert(root, x);
}
}
InOrder(root);
return0;
}