时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：3260

解决：1385

题目描述：

    输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入：

    输入第一行包括一个整数n(1<=n<=100)。

    接下来的一行包括n个整数。

输出：

    可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。

    每种遍历结果输出一行。每行最后一个数据之后有一个空格。

样例输入：

51 6 5 9 8

样例输出：

1 6 5 9 8 1 5 6 8 9 5 8 9 6 1

提示：

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

来源：

下面是cpp的代码，参考朋友的。尽量改成c

#include
       
        #include
        
         #include
         
          using namespace std;struct node{    int key;    node *lc;    node *rc;};void Insert(int x,node *&p){    if(p==NULL)    {        p=new node;        p->key=x;        p->lc=NULL;        p->rc=NULL;    }    else if(p->key>x)        Insert(x,p->lc);    else if(p->key
          
           rc);    else if(p->key==x)return ;}node* create(int n){    int a;    node* F=NULL;    while(n--)    {        cin >>a;        Insert(a,F);    }    return F;}void pre_order(node * p){    if(p!=NULL)    {        cout << p->key << " ";        pre_order(p->lc);        pre_order(p->rc);    }}void in_order(node * p){    if(p!=NULL)    {        in_order(p->lc);        cout << p->key << " ";        in_order(p->rc);    }}void post_order(node * p){    if(p!=NULL)    {        post_order(p->lc);        post_order(p->rc);         cout << p->key << " ";    }}void Free(node * p){    if(p!=NULL)    {        Free(p->lc);        Free(p->rc);        free(p);    }}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        node *R=create(n);        pre_order(R);        cout << endl;        in_order(R);        cout << endl;        post_order(R);        cout << endl;        Free(R);    }    return 0;}
          
         
        
       

下面是c语言的

#include
     
      #include
      
       struct node{    int key;    node *lc;    node *rc;};void Insert(int x,node *&p){    if(p==NULL)    {        p=new node;        p->key=x;        p->lc=NULL;        p->rc=NULL;    }    else if(p->key>x)        Insert(x,p->lc);    else if(p->key
       
        rc);    else if(p->key==x)return ;}node* create(int n,node *&F){    int a;    F=NULL;    while(n--)    {        scanf("%d",&a);        Insert(a,F);    }    return F;}void pre_order(node * p){    if(p!=NULL)    {        printf("%d ",p->key);        pre_order(p->lc);        pre_order(p->rc);    }}void in_order(node * p){    if(p!=NULL)    {        in_order(p->lc);        printf("%d ",p->key);        in_order(p->rc);    }}void post_order(node * p){    if(p!=NULL)    {        post_order(p->lc);        post_order(p->rc);        printf("%d ",p->key);    }}void Free(node * p){    if(p!=NULL)    {        Free(p->lc);        Free(p->rc);        free(p);    }}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        node *R;        create(n,R);        pre_order(R);        printf("\n");        in_order(R);        printf("\n");        post_order(R);        printf("\n");        Free(R);    }    return 0;}
       
      
     

很奇怪的一点，在dev c++上c编译通过，但是OJ上却是编译错误。

考虑到c++兼容c，所以讲上述代码用c++编译，AC。

好吧，不明觉厉。

下面是自己写的c代码,除了引用，其他都是c

1 #include 
     
       2 #include 
      
        3 typedef struct BTNode 4 { 5     int data; 6     struct BTNode *lchild; 7     struct BTNode *rchild; 8      9 }BTNode;10 void preorder(BTNode *p) 11 {12     if(p!=NULL)13     {14         printf("%d ",p->data);15         16         preorder(p->lchild);17         preorder(p->rchild);18     }19 }20 void inorder(BTNode *p) 21 {22     if(p!=NULL)23     {24         preorder(p->lchild);25         printf("%d ",p->data);26         preorder(p->rchild);27     }28 }29 void postorder(BTNode *p) 30 {31     if(p!=NULL)32     {33         preorder(p->lchild);34         preorder(p->rchild);35         printf("%d ",p->data);36     }37 }38 39 void myinsert(int num,BTNode *&p)40 {    41     printf("num==%d,p==%p\n",num,p);42     if(p==NULL)43     {44         p=new BTNode;45         p->data=num;46         p->lchild=NULL;47         p->rchild=NULL;    48     }49     else if((p->data)
       
        rchild);51     else if((p->data)>num)52         myinsert(num,p->lchild);53 }54 void create(BTNode *&p,int n)55 {56     p=NULL;57     int num;58     while(n--)59     {60         scanf("%d",&num);61         myinsert(num,p);62     63         64     }65     66 }67 void myfree(BTNode *p)68 {69     if(p!=NULL)70     {71         myfree(p->lchild);72         myfree(p->rchild);73         free(p);74     }75 }76 77 int main(void)78 {79     int n,n2;80     int i;81     scanf("%d",&n2);82     for(i=0;i
       
      
     

代码略有不同，会打印出每次递归p所指向的地址以及赋值的元素，方便理解：递归每次完成后指针p都返回根结点。另外多组测试案例这个功能随手用n2次代替了，懒得改了