当前位置: 代码迷 >> 综合 >> PAT1086 Tree Traversals Again (25)(树的遍历)
  详细解决方案

PAT1086 Tree Traversals Again (25)(树的遍历)

热度:30   发布时间:2024-01-16 13:19:29.0

题意:

用栈的形式给出一棵树建立的顺序,要求输出后序遍历

思路:

push的顺序就是先序遍历,pop出的顺序就是中序遍历,所以直接用二叉树先序和中序遍历转后序即可。主要记录一下模板

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 10000;
vector<int> inOrder,preOrder,postOrder;
stack<int> tree;/*先序中序转后序*/
void post(int root, int left, int right) {if (left > right) return;int i = left;while (i < right&&inOrder[i] != preOrder[root]) i++;post(root+1, left, i - 1);post(root+1+i-left, i + 1, right);postOrder.push_back(preOrder[root]);
}int main() {int n;scanf("%d", &n);string s;int num;while(inOrder.size()<n) {cin >> s;if (s[1] == 'u') {scanf("%d", &num);tree.push(num);preOrder.push_back(num);} else {int temp = tree.top();tree.pop();inOrder.push_back(temp);}}post(0, 0, n - 1);for (int i = 0; i < n; i++) {if (i == 0) {printf("%d",postOrder[i]);} else {printf(" %d",postOrder[i]);}}return 0;
}

后序中序求先序:

#include <cstdio>
using namespace std;
int post[] = {3, 4, 2, 6, 5, 1};
int in[] = {3, 2, 4, 1, 6, 5};
void pre(int root, int start, int end) {if(start > end) return ;int i = start;while(i < end && in[i] != post[root]) i++;printf("%d ", post[root]);pre(root - 1 - end + i, start, i - 1);pre(root - 1, i + 1, end);
}int main() {pre(5, 0, 5);return 0;
}

 

  相关解决方案