九度题目1201:二叉排序树

  1. 云栖社区>
  2. 博客>
  3. 正文

九度题目1201:二叉排序树

光仔december 2014-05-17 12:03:00 浏览1089
展开阅读全文
题目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;
}

网友评论

登录后评论
0/500
评论
光仔december
+ 关注