HRBUST 2040 二叉树的遍历
2024-09-01 21:03:53
给出一棵二叉树的中序和前序遍历,输出它的后序遍历。
Input
本题有多组数据,输入处理到文件结束。
每组数据的第一行包括一个整数n,表示这棵二叉树一共有n个节点。
接下来的一行每行包括n个整数,表示这棵树的中序遍历。
接下来的一行每行包括n个整数,表示这棵树的前序遍历。
3<= n <= 100
Output
每组输出包括一行,表示这棵树的后序遍历。
Sample Input
7
4 2 5 1 6 3 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 ;
}
最新文章
- IE浏览器测试
- 老王讲自制RPC框架.(一.前言与技术选型)
- 一个资深iOS开发者对于React Native的看法
- 使用js使某个按钮在5秒内不能重复点击
- h5在线状态监测
- maven增加Spring
- BeX5平台简明部署过程
- C#单例模式的三种写法
- mysql管理员操作
- Jquery插件写法及extentd函数
- C#自定义事件:属性改变引发事件示例
- 关于php文件读取的一些学习记录
- PTA 第二周作业 张乐
- C# 解析json数据出现---锘縖
- BeautifulSoup总结
- Git初始化及配置
- 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
- python------面向对象进阶 异常处理
- c# 对html字符串进行编码
- B. Forgery