欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1086 Tree Traversals Again (25)

程序员文章站 2022-03-18 11:20:51
...

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.

1086 Tree Traversals Again (25)\ 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

思路 :

用栈的形式给出一棵二叉树的建立的顺序,求这棵二叉树的后序遍历。

Push的次序即是先序序列,pop的次序即是中序序列

则根据先序序列和中序序列构建一棵树。

C++:

#include "stack"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
const int maxn=50;
struct node
{
	int data;
	node* lchild,* rchild;
};
int pre[maxn],in[maxn],post[maxn];
int n;
node* create(int prel,int prer,int inl,int inr){
	if (prel>prer)//先序序列长度小于0
	{
		return NULL;
	}
	node* root=new node;
	root->data=pre[prel];
	int k;
	//在左子树中寻找根结点
	for (k=inl;k<=inr;k++)
	{
		if (in[k]==pre[prel])
		{
			break;
		}
	}
	int numleft=k-inl;//左子树的个数
	//返回左子树的根结点地址,赋值给root的左指针
	root->lchild=create(prel+1,prel+numleft,inl,k-1);
	//返回右子树的根结点地址,赋值给root的右指针
	root->rchild=create(prel+numleft+1,prer,k+1,inr);
	return root;
}
int num=0;
void postorder(node* root){
	if (root==NULL)
	{
		return;
	}
	postorder(root->lchild);
	postorder(root->rchild);
	printf("%d",root->data);
	num++;
	if (num<n)printf(" ");
}
int main(){
	scanf("%d",&n);
	char str[5];
	stack<int> st;
	int x,preIndex = 0,Inindex = 0;
	for (int i=0;i<2*n;i++)
	{
		scanf("%s",str);
		if (strcmp(str,"Push")==0)
		{
			scanf("%d",&x);
			pre[preIndex++]=x;
			st.push(x);
		}else
		{
			in[Inindex++]=st.top();
			st.pop();
		}
	}
	node* root=create(0,n-1,0,n-1);
	postorder(root);
	return 0;
}