二叉排序树的创建与使用

根据大家的意见，从这个题目开始，以后都会简单注释，这样更方便大家阅读，如果还有什么不懂的地方，可以留言！

描述

二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有的结点值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；（3）它的左右子树也分别为二叉排序树。现要求根据输入的元素值，构造一棵二叉排序树，并输出其先序遍历、中序遍历和后序遍历结果。

输入

输入第一行为测试用例个数n，接下来为n个测试用例，每个测试用例占两行，其中第一行为元素个数m，第二行为m个需要构造成二叉排序树的元素值。

输出

每个测试用例用三行输出，其中第一行输出先序遍历结果，第二行输出中序遍历结果，第三行输出后序遍历结果。各元素之间用一个空格隔开。

样例输入

1
5
8 4 2 6 4

样例输出

8 4 2 6 4
2 4 4 6 8
2 4 6 4 8

#include<iostream>
using namespace std;
typedef int KeyType;
typedef struct node    
{
    KeyType data;
    struct node *rd,*ld;
}*LNode;
LNode p;
int f=0;
int Init(LNode &t)   //创建一棵空树
{
    t= new node;      
    t->data=0;
    t->rd=t->ld=NULL;
}
int create(LNode &t,int key)   //这个是根据二叉排序数的性质而写的，在这里用到了递归调用，使代码大幅度的简单化了
{
    if(t==NULL){return 0;}    
    if(key<t->data){p=t;create(t->ld,key);}//判断他的大小，区分左右，利用P记住当前位置
     else {p=t;create(t->rd,key);} 
}
int insert(LNode &p,int key)//根据上一个函数，通过p写入数据
{
    LNode s = new node;      
    s->data=key;s->ld=s->rd=NULL;
    if(key>=p->data)p->rd=s;
    else            p->ld=s;
}
void preorder(LNode t)   //先序输出
{
    if(t)
    {
        if(f==0){cout<<t->data;f=1;}
        else cout<<" "<<t->data;
        preorder(t->ld);
        preorder(t->rd);
    }
}
void inorder(LNode t)     //中序输出
{
    if(t)
    {
        inorder(t->ld);
        if(f==0){cout<<t->data;f=1;}
        else cout<<" "<<t->data;
        inorder(t->rd);
    }
}
void postorder(LNode t)   //后序输出
{
    if(t)
    {

        postorder(t->ld);
        postorder(t->rd);
        if(f==0){cout<<t->data;f=1;}
        else cout<<" "<<t->data;
    }
}
int main()
{
    LNode t;
    int n,m,key;
    cin>>n;
    while(n--)
    {
         Init(t);
        cin>>m;
        cin>>key;
        t->data=key;
        for(int i=1;i<m;i++){
            cin>>key;
            create(t,key);
            insert(p,key);
        }
        f=0;preorder(t);cout<<endl;//在输出的时候，因为有个空格问题要注意，所以在这里我定义了一个f，进行处理
        f=0;inorder(t);cout<<endl;
        f=0;postorder(t);cout<<endl;
    }
   return 0;
}