【PTA】Tree Traversals Again
题目如下:
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2 lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
Push Push Push Pop Pop Push Pop Pop Push Push Pop Pop
Sample Output:
分析:
题意很简单,给你一个用栈遍历某棵树的顺序。并给出这个树的后序遍历。
不妨看一下例子:Push进栈的有:1 2 3 4 5 6
而对应Pop出栈的是:3 2 4 1 6 5
发现很眼熟,如果对树的遍历很敏感的话。你会发现进栈的顺序是树的先序遍历。而出栈的顺序是中序遍历。
暂且不讨论原因何在,就按这个思路,把树建起来,后序遍历输出即可。
关键是,怎么建树?
我的思路如下:按照题意,建立一个栈,两个数组pre,middle:用来保留先序遍历序列与中序遍历序列。
处理Push和Pop的接受输入。当Push时,把对应数据计入先序遍历序列的对应下标。并把数据压栈。
当Pop是,把栈顶元素计入中序遍历序列的对应下标。并弹栈。
这样输入结束后,我们就有了先序与中序序列。接下来的问题就变为:利用先序序列和中序序列还原二叉树,并后序输出。
教材例题了,方法不多述了。关键步骤在注释中有提到。
代码如下:
#include <bits/stdc++.h> #define MAX 101 typedef struct TNode { int data; struct TNode *left; struct TNode *right; }TNode; }; }; int ps,pe,ms,me; ; ; TNode* CreateTree(int ps,int pe,int ms,int me) { int i; if(ps>pe) return NULL; //查找根节点在中序序列中位置 for( i=ms;i<=me;i++) { if(middle[i]==pre[ps]) break; } TNode *r = new TNode; //若第i个位置为根节点,则i-起始位置=左子树个数 int num1=i-ms; r->data=pre[ps]; //左子树对应:先序序列:根节点往后一个~根节点+左子树个数 // 中序序列:起始位置(中序:左根右)~根节点位置(即i) r->left=CreateTree(ps+,ps+num1,ms,i-); //右子树对应:先序序列:左子树位置+1~ 列尾 // 中序序列:根节点+1~列尾 r->right=CreateTree(ps+num1+,pe,i+,me); return r; } //后序遍历输出 void PostOrder(TNode *r) { if(r==NULL) return; PostOrder(r->left); PostOrder(r->right); printf("%d",r->data); count++; if(count <total) printf(" "); } int main(void) { scanf("%d",&total); std::stack<int> a; int tmp; ]; ; //前序序列下标 ; //中序序列下标 ;i<*total;i++) { scanf("%s",tmps); ) { scanf("%d",&tmp); pre[pn]=tmp; pn++; a.push(tmp); } else { middle[mn]=a.top(); mn++; a.pop(); } } TNode* root = CreateTree(, total-, , total-); PostOrder(root); ; }
最新文章
- DirectX HLSL相关基础
- 执行robot framework 的测试用例 命令行pybot使用方式
- android源码在线查看
- sqlserver 保留小数方法
- telnet 时代的 bbs
- oracle exp imp
- 创建、更新、删除文档。 --- Mongodb权威指南阅读。
- VS2010关于error LNK1123: 转换到 COFF 期间失败: 文件无效或损坏
- RH253读书笔记(10)-Appendix A Installing Software
- phpQuery 无法解析 html 结构
- IIS部署网站时常见问题解决
- Docker Register安装与基本认证
- SQL企业级面试题
- jeecg入门操作—树型表单开发
- JConsole监控Linux上的Tomcat
- 【算法和数据结构】_16_小算法_IntToStr: 将整型数据转换为字符串
- Pycharm配置
- STM8串口初始化寄存器配置
- 【转载】CodeLite汉化
- Linux下查找大文件,大目录的方法