03-树3 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.

c486f1028c321c58791dfd96c8247fad.png

Figure 1 Input Specification: Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N 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: 6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop Sample Output: 3 4 2 6 5 1

忙活了半天，没写出来，先记录一下思想，免得下来再做忘记了，同时也供你们借鉴

题意我是读懂了，二叉树的非递归遍历中有一些堆栈的操作，题目正是给出了这些堆栈的操作，然后要我们反推出树，后面后序遍历出这棵树，只要我们把树推出来就成功了百分之九十九，问题是太难了。。。我才刚刚把非递归中序遍历的算法弄懂，现在就要反推。。。。其实大多数的时候我都机智的一批后面发现简直就是脑残（(｡･∀･)ﾉﾞ）首先，我想到了我只要把题目的堆栈操作数操作一遍不就得到了中序遍历的结果了吗？？？加上我之前看的一篇博客介绍的前序遍历建二叉树，，完美！！后来，我发现根据一种遍历顺序是不能建出一棵树的。。。。。。就到这把，下次再写

再一次闪亮登场。。。。

IMG20191110145859.jpg

//这里我还是用我自己写的链栈来写，而且还是顺序栈，我记得链式的我好像没去写。。。但是不久我应该要用stl里面的模板了把
//我发现我写的栈在vs上不能运行， 最后教材上的也是（武汉大学李春葆的数据结构）不过书上也说了他们的编译环境是dev，那这里我就用stl上的模板把
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int pre[50], in[50], post[50];
void solve(int prel, int inl, int postl, int n) {
	//使用递归一定要注意掌握思想，我们要做的只需要求出根节点，那么根节点怎么求，很明显线序遍历的跟节点就是数组第一个数，
	//然后把他放在后续遍历中的最后一个位置就行了，这样就求出了根节点。需要思考两个问题，1那么中序遍历的数组呢？2我们只求出了第一个根节点
	//剩下的节点怎么求？？？我也不知道怎么求，但是递归关心过程，我们只需要把从n到n-1衔接好就行。再来看函数接口，对应二叉树，我们需要带入两边
	//分别递归求其子树的根节点，这时in数组就起到了作用。
	int i, l, r;
	if (n == 0)return;
	if (n == 1) { post[postl] = pre[prel]; return; }
	post[postl + n - 1] = pre[prel];
	for ( i = 0; i < n; i++) {
		if (in[inl + i] == pre[prel])
			break;
	}
	l = i; r = n - l - 1;
	solve(prel+1, inl, postl, l);
	solve(prel + l + 1, inl + l + 1, postl + l, r);
}
int main() {
	int prel = 0, inl = 0;
	stack<int>s;
	int n, data;
	string tmp;
	cin >> n;
	for (int i = 0; i < n*2; i++) {
		cin >> tmp;
		if (tmp[1] == 'u') {
			cin >> data;
			pre[prel++] = data;
			s.push(data);
		}
		else {
			data = s.top();
			in[inl++] = data;
			s.pop();
		}
	}
	//接下来根据前序遍历的pre和中序遍历的in来求出后序遍历，根本不用建树
	solve(0, 0, 0, n);
	for (int i = 0; i < n-1; i++) {
		cout << post[i] << " ";
	}
	cout << post[n - 1];
}

废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：03-树3 Tree Traversals Again