题目描述
深度遍历一棵二叉树有先序，中序和后序三种方式，并且根据遍历序列能确定一棵二叉树，要唯一确定一棵二叉树至少需要两种遍历序列 先序+中序 或 后序+中序，（先序+后序无法唯一确定） 现在给定你一棵二叉树的先序和中序序列，请你构造出这棵二叉树，并且输出其层序遍历结果输入
输入包含多组测试数据
对每组测试数据:
第一行为一个正整数n（0<n<=100）代表二叉树节点个数
第二行为这棵树的先序遍历序列
第三行为其中序遍历序列
（每个节点为整型数字）
当读到文件结尾时输入结束.
输出
对每组测试数据
在一行中输出这棵树的层序遍历结果 中间用空格隔开，最后一个数字后面不得有空格。
样例输入
8
7 10 4 3 1 2 8 11
4 10 3 1 7 11 8 2
样例输出
7 10 2 4 3 8 1 11
（由于本人能力问题，且处于大一阶段，所以只能用C语言的队列数据结构把二叉树按层序输出，
这就相当于花费了大量的精力，其实这里按照c++中输出会简单很多，因为c++中有很多函数是
已经确定好了的，所以不用像c语言一样在编一遍，）
#include<stdio.h>
#include<stdlib.h>
int n;
int xian[105];
int zhong[105];
typedef struct Btree { //二叉树的结构定义
int data;
struct Btree* left;
struct Btree* right;
}Btree;
typedef struct LinkQueueNode { //链队列类型定义
Btree *data;
struct LinkQueueNode *next;
}LKQueNode;
typedef struct LKQueue {
LKQueNode *front,*rear;
}LKQue;
void InitQueue (LKQue *LQ) { //初始化队列
LKQueNode *p;
p = (LKQueNode* )malloc (sizeof (LKQueNode));
LQ->front = p;
LQ->rear = p;
(LQ->front)->next = NULL;
}
int EmptyQueue (LKQue *LQ) { //判断队列是否为空
if (LQ->front == LQ->rear)
return 1;
else
return 0;
}
void EnQueue (LKQue *LQ,Btree* x) { // 入队列
LKQueNode *p;
p = (LKQueNode* )malloc (sizeof (LKQueNode));
p->data = x;
p->next = NULL;
(LQ->rear)->next = p;
LQ->rear = p;
}
int OutQueue (LKQue *LQ) { // 出队列
LKQueNode *s;
if (EmptyQueue(LQ)) {
exit(0);
return 0;
}
else {
s = (LQ->front)->next;
(LQ->front)->next = s->next;
if (s->next == NULL)
LQ->rear = LQ->front;
free(s);
return 1;
}
}
Btree* GetHead(LKQue *LQ) { //取队列首元素
LKQueNode *p;Btree *q;
if (EmptyQueue(LQ))
return q;
else {
p = LQ->front->next;
return p->data;
}
}
int ans[105];
int count;
void Visit (Btree* p) { //访问结点的数值
ans[count++] = p->data;
}
void levelorder (Btree* bt) { // 层次遍历
LKQue Q;Btree* p;
InitQueue(&Q);
if (bt != NULL) {
EnQueue (&Q,bt);
while (!EmptyQueue(&Q)) {
p = GetHead (&Q);
OutQueue (&Q);
Visit (p);
if (p->left != NULL) EnQueue (&Q,p->left);
if (p->right != NULL) EnQueue (&Q,p->right);
}
}
}
int findindex(int *zhong,int x,int len) {
for (int i = 0; i < len; i++) {
if (zhong[i] == x)
return i;
}
}
Btree* build (int *xian,int *zhong,int len) { //由先序和中序构建二叉树
if (len <= 0) return NULL;
Btree* tmp = (Btree* )malloc (sizeof (Btree));
tmp->data = xian[0];
int index = findindex(zhong,xian[0],len);
tmp->left = build (xian+1,zhong,index);
tmp->right = build (xian+index+1,zhong+index+1,len-index-1);
return tmp;
}
int main () {
int n;
while (scanf ("%d",&n)!=EOF) {
for (int i = 0; i < n; i++)
scanf ("%d",&xian[i]);
for (int i = 0; i < n; i++)
scanf ("%d",&zhong[i]);
Btree *root = build (xian,zhong,n);
count = 0;
levelorder (root);
for (int i = 0; i < n; i++) {
if (i == 0) printf ("%d",ans[i]);
else printf (" %d",ans[i]);
}
printf ("\n");
}
return 0;
}