九度题目1201：二叉排序树

题目1201：二叉排序树
时间限制：1 秒内存限制：32 兆特殊判题：否提交：3008解决：1262
题目描述：
    输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入：
    输入第一行包括一个整数n(1=n=100)。
    接下来的一行包括n个整数。
输出：
    可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
    每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输入：
5
1 6 5 9 8
样例输出：
1 6 5 9 8 
1 5 6 8 9 
5 8 9 6 1 
提示：
输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
来源：
2005年华中科技大学计算机保研机试真题




AC代码：
ps：这一回算是正儿八经学一回指针了。。。。

#include<stdio.h>
#include<string.h>
struct node
{
   int data;
   struct node *Ltree;
   struct node *Rtree;  
};
//Node *head;就是Node*head=0;head沒指向任何對象.
//Node *head=new Node；head指向一個Node型的對象.
node *head=new node(); //申请二叉树的指针且分配了结构体空间 
//前序遍历 
void PreOrder(node *head)
{
        if(head)
        {
                printf("%d ",head->data);
                PreOrder(head->Ltree);
                PreOrder(head->Rtree);
        }
}
//中序遍历
void InOrder(node *head)
{
        if(head)
        {
                InOrder(head->Ltree);
                printf("%d ",head->data);;
                InOrder(head->Rtree);
        }
}


//后序遍历
void PostOrder(node *head)
{
        if(head)
        {
                PostOrder(head->Ltree);
                PostOrder(head->Rtree);
                printf("%d ",head->data);
        }
}
//撤销二叉树
void deleteTree(node *head)
{
        if(head)
        {
                deleteTree(head->Ltree);
                deleteTree(head->Rtree);
                delete head;
        }
}
//建立二叉排序树
void buildBinarySortTree(node *head,int elem[],int length)
{
     node *p,*pre;
     int flagLeftOrRight;
     int success;
     
     head->data=elem[0];
     head->Ltree=NULL;
     head->Rtree=NULL;
     
     for(int i=1;i<length;i++)
     {
        success=0;
        pre=NULL;
        p=head;
        while(p)//寻找插入的位置 
        {
           pre=p;
           if(p->data==elem[i])//查找成功
           {
              success=1;
              break; 
           }     
           else if(p->data<elem[i])
           {
              p=p->Rtree;
              flagLeftOrRight=1;
           }
           else
           {
               p=p->Ltree;
               flagLeftOrRight=0;
           }
        }
        
        if(!success)
        {
           p=new node();//生成新节点 
           p->data=elem[i];
           p->Ltree=NULL;
           p->Rtree=NULL;
           
           if(flagLeftOrRight==0)
           {
              pre->Ltree=p;
           } 
           else if(flagLeftOrRight==1)
           {
              pre->Rtree=p;
           }
        }
     }
}
int main()
{
    int i,j,n,m;
    int elem[110];
    while(scanf("%d",&n)!=EOF)
    {
       for(i=0;i<n;i++)
       {
          scanf("%d",&elem[i]);
       }
       buildBinarySortTree(head,elem,n); 
       
       PreOrder(head);
       puts("");
       InOrder(head);
       puts("");
       PostOrder(head);
       puts("");
    }
    return 0;
}