Description
已知一棵二叉树的前序遍历和中序遍历, 求二叉树的后序遍历和层序遍历.
Input
输入数据有多组, 第一行是一个整数 t (t<1000), 代表有 t 组测试数据. 每组包括两个长度小于 50 的字符串, 第一个字符串表示二叉树的先序遍历序列, 第二个字符串表示二叉树的中序遍历序列.
Output
每组第一行输出二叉树的后序遍历序列, 第二行输出二叉树的层次遍历序列.
- Sample
- Input
- 2
- abdegcf
- dbgeafc
- xnliu
- lnixu
- Output
- dgebfca
- abcdefg
- Linux
- xnuli
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- char a[1005],b[1005];
- struct node
- {
- int date;
- struct node *l,*r;
- };
- struct node *creat(int len,char a[51],char b[51])
- {int i;
- struct node *root;
- if(len==0)
- {
- return NULL;
- }
- root=(struct node*)malloc(sizeof(struct node));
- root->date=a[0];
- for(i=0;i<len;i++)
- {
- if(b[i]==a[0])
- break;
- }
- root->l=creat(i,a+1,b);
- root->r=creat(len-i-1,a+i+1,b+i+1);
- return root;
- };
- void cengxu(struct node * root)
- {
- struct node * temp[100]; // 关键中间变量存放每一层的数据
- int in = 0, out = 0;
- temp[in++] = root; // 每次把这一层存入, 然后输出的时候就把他的左右节点存入
- while(in> out) // 例如一颗完全二叉树 abcdefg 输出 a 的时候把 bc 放入, 输出 b 的时候把 b
- { // 的孩子放入也就是 de, 再输出 c 并且放入孩子 fg, 依次这样, 达到层序的要求
- if(temp[out])
- {
- printf("%c",temp[out]->date);
- temp[in++] = temp[out]->l;
- temp[in++] = temp[out]->r;
- }
- out++;
- }
- }
- void houxu(struct node *root)
- {
- if(root)
- {
- houxu(root->l);
- houxu(root->r);
- printf("%c",root->date);
- }
- }
- int main()
- {int n,len;
- scanf("%d",&n);
- struct node *root;
- while(n--)
- {
- scanf("%s",a);
- scanf("%s",b);
- len=strlen(a);
- root=creat(len,a,b);
- houxu(root);
- printf("\n");
- cengxu(root);
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3507533.html