给出一棵二叉树的中序和前序遍历,输出它的后序遍历。
Input

本题有多组数据,输入处理到文件结束。

每组数据的第一行包括一个整数n,表示这棵二叉树一共有n个节点。

接下来的一行每行包括n个整数,表示这棵树的中序遍历。

接下来的一行每行包括n个整数,表示这棵树的前序遍历。

3<= n <= 100

Output

每组输出包括一行,表示这棵树的后序遍历。
Sample Input
7
4 2 5 1 6 3 7

1 2 4 5 3 6 7

Sample Output

4 5 2 6 7 3 1 
 
这里后序遍历写了一个非递归,嗯,为考研做准备。
代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int Data;
struct Node *Left,*Right;
}Node;
int q[],z[];///q记录前序遍历 z记录中序遍历
Node* creatNode() {
Node *node = (Node *)malloc(sizeof(Node));
if(node == NULL) exit();
node -> Left = node -> Right = NULL;
return node;
}
Node* rTree(int q1,int q2,int z1,int z2) {
Node *node = creatNode();
node -> Data = q[q1];
for(int i = z1;i <= z2;i ++) {
if(z[i] == q[q1]) {
if(i != z1) node -> Left = rTree(q1 + ,q1 + i - z1,z1,i - );
if(i != z2) node -> Right = rTree(q1 + i - z1 + ,q2,i + ,z2);//右儿子构建
break;
}
}
return node;
}
//void postOrder(Node *node) {
// if(node == NULL) return;
// postOrder(node -> Left);
// postOrder(node -> Right);
// printf("%d ",node -> Data);
//}
//void postOrder(Node *node) {///下标标记
// Node *s[100];
// char num[100] = {0};
// int c = 0;
// s[c ++] = node;
// while(c) {
// Node *temp = s[c - 1];
// if(num[c - 1]) {
// num[c - 1] = 0;
// printf("%d ",s[-- c] -> Data);
// }
// else {
// num[c - 1] = 1;
// if(temp -> Right) {
// s[c ++] = temp -> Right;
// }
// if(temp -> Left) {
// s[c ++] = temp -> Left;
// }
// }
// }
//}
void postOrder(Node *node) {///前驱结点判断
Node *s[],*la;
int c = ;
s[c ++] = node;
while(c) {
Node *temp = s[c - ];
if(temp -> Left == temp -> Right && temp -> Left == NULL || la == temp -> Left || la == temp -> Right) {
printf("%d ",s[-- c] -> Data);
la = temp;
}
else {
if(temp -> Right && la != temp -> Right) {
s[c ++] = temp -> Right;
}
if(temp -> Left && la != temp -> Left) {
s[c ++] = temp -> Left;
}
}
}
}
int main() {
int n;
Node *tree;
while(~scanf("%d",&n)) {
for(int i = ;i < n;i ++) {
scanf("%d",&z[i]);
}
for(int i = ;i < n;i ++) {
scanf("%d",&q[i]);
}
tree = rTree(,n - ,,n - );
postOrder(tree);
putchar('\n');
}
return ;
}

最新文章

  1. IE浏览器测试
  2. 老王讲自制RPC框架.(一.前言与技术选型)
  3. 一个资深iOS开发者对于React Native的看法
  4. 使用js使某个按钮在5秒内不能重复点击
  5. h5在线状态监测
  6. maven增加Spring
  7. BeX5平台简明部署过程
  8. C#单例模式的三种写法
  9. mysql管理员操作
  10. Jquery插件写法及extentd函数
  11. C#自定义事件:属性改变引发事件示例
  12. 关于php文件读取的一些学习记录
  13. PTA 第二周作业 张乐
  14. C# 解析json数据出现---锘縖
  15. BeautifulSoup总结
  16. Git初始化及配置
  17. mysql----------mysql5.7.11导入sql文件时报错This function has none of DETERMINISTIC, NO SQL, or READS SQL DATA in its declaration and binary logging is enabled
  18. python------面向对象进阶 异常处理
  19. c# 对html字符串进行编码
  20. B. Forgery

热门文章

  1. ANR无法生成traces.txt文件
  2. 第2部分 Elasticsearch查询-请求体查询、排序
  3. 【ARM-Linux开发】【CUDA开发】NVIDIA Jetson TX2 进阶:QtCreator安装
  4. Kafka Connect简介
  5. linux 使用 Python 画图工具matplotlib 提示display 错误
  6. 解决GitHub下载慢或下载失败问题
  7. 前端向后端获取数据的三种方法:ajax、axios、fetch
  8. linux 压缩文件 查找
  9. C++函数形参与实参交换
  10. Linux基础(11)原始套接字