Chinaunix首页 | 论坛 | 博客
  • 博客访问: 537231
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-11-15 10:45:10

/*
Description

根据输入重构一个二叉树,输出按不同顺序遍历的节点序列


数据输入:

第一行是一个整数N(1<=N<=20),表示有多少个测试例子,以下每行是一个测试例子。每个测试例子第一个是一个整数M,
表示输出的遍历顺序,其中M=0,表示前序;M=1,表示中序;M=2,表示后序。然后是一个字符序列,
字符序列由A-Z和#表示,A-Z表示节点,#表示空。如果字符所在字符串的位置为i(i为正整数,位置从1开始计数),
则位置为i*2,i*2+1的节点为它的子节点。如果i*2,i*2+1超过字符串长度,表示子节点为空。


数据输出:

每行输出一个例子的结果。一个字符串,中间无空格。
 
Sample Input

2
0 AB#CD####EF
1 AB#CD####EF

 
Sample Output

ABCDEF
CBEDFA
*/



点击(此处)折叠或打开

  1. #include<stdio.h>

  2. void preorderTraverse(int count,int inCount,char* p,int i);
  3. void inorderTraverse(int count,int inCount,char* p,int i);
  4. void postorderTraverse(int count,char* p,int i);

  5. int main(void)
  6. {
  7.     int cases,n,count,i;
  8.     char c,temp;
  9.     char p[10000];
  10.     
  11.     scanf("%d",&cases);
  12.     
  13.     while(cases--)
  14.     {
  15.         i = 1;
  16.         p[0] = 'a';
  17.         count = 0;
  18.         scanf("%d",&n);
  19.         temp = getchar();
  20.     
  21. //        p++;
  22.         
  23.         while((c = getchar()) != '\n')
  24.         {
  25.             p[i++] = c;
  26.             count++;
  27.         }

  28.         if(0 == n)
  29.         {
  30.             preorderTraverse(count,count,p,1);
  31.         }
  32.         else if(1 == n)
  33.         {
  34.             inorderTraverse(count,count,p,1);
  35.         }
  36.         else if(2 == n)
  37.         {
  38.             postorderTraverse(count,p,1);
  39.         }

  40.         printf("\n");
  41.        
  42.     }
  43.     return 0;
  44. }


  45. //编写先序遍历函数
  46. void preorderTraverse(int count,int inCount,char* p,int i)
  47. {
  48. //    printf("%d",count);
  49.     if(0 == inCount || 0 == count)
  50.     {
  51.         return;
  52.     }
  53.         
  54.     inCount--;

  55.     char temp = p[i];
  56.     
  57.     if(temp != '#')
  58.     {
  59.         printf("%c",temp);
  60.     }
  61.     if(2 * i <= count)
  62.     {
  63.         preorderTraverse(count,inCount,p,2*i);
  64.     }

  65.     if(2 * i + 1 <= count)
  66.     {
  67.         preorderTraverse(count,inCount,p,2*i+1);
  68.     }
  69. }


  70. //编写中序遍历
  71. void inorderTraverse(int count,int inCount,char*p,int i)
  72. {
  73.     if(0 == inCount || 0 == count)
  74.     {
  75.         return;
  76.     }

  77.     char temp = p[i];

  78.     inCount--;

  79.     if(2 * i <= count)
  80.     {
  81.         inorderTraverse(count,inCount,p,2*i);
  82.     }

  83.     if('#' != temp)
  84.     {
  85.         printf("%c",temp);
  86.     }

  87.     if(2 * i + 1 <= count)
  88.     {
  89.         inorderTraverse(count,inCount,p,2*i+1);
  90.     }

  91. }

  92. //编写后续遍历 这里不要inCount这个变量
  93. void postorderTraverse(int count,char*p,int i)
  94. {
  95.     if(0 == count)
  96.     {
  97.         return;
  98.     }

  99.     char temp = p[i];
  100.     
  101.     if(2 * i <= count)
  102.     {
  103.         postorderTraverse(count,p,2*i);
  104.     }

  105.     if(2 * i + 1 <= count)
  106.     {
  107.         postorderTraverse(count,p,2*i+1);
  108.     }

  109.     if('#' != temp)
  110.     {
  111.         printf("%c",temp);
  112.     }
  113. }

阅读(1132) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~