A1086 Tree Traversals Again (25 point(s))

建树，中序非递归方式赋值，后序遍历

1. 原文

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.

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

2. 解析

建树

push-指向 左子树 root->lchild=temp;

pop-指向 右子树 root->rchild=temp;

⚠️注意记录第一个结点tree=root

3. AC代码

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
struct node{
  int data;
  node *lchild,*rchild;
};
node* newNode(int x){
	node* root=new node;
	root->data=x;
	root->lchild=root->rchild=NULL;
	return root;
}
int key=0;
void postorder(node* root){
	if (root==NULL)
	{
		return;
	}
	postorder(root->lchild);
	postorder(root->rchild);
	if (key==0)
	{
		printf("%d",root->data);
		key++;
	}else{
		printf(" %d",root->data);
	}

}
char str[5];
stack<node*> s;
int main(){
	int n,x;
	scanf("%d",&n);
	node *root=NULL;
	node *tree=NULL;
	scanf("%s",str);
	if (strcmp(str,"Pop")==0)
	{
		return 0;
	}else{
		scanf("%d",&x);
		root=newNode(x);
		tree=root;
		s.push(root);
	}
	int flag=0;
	for (int i = 1; i < n*2; ++i)
	{
		scanf("%s",str);
		if (strcmp(str,"Push")==0)
		{
			scanf("%d",&x);
			node *temp=newNode(x);
			s.push(temp);
			if (flag==0)
			{
				root->lchild=temp;
			}else{
				root->rchild=temp;
				flag=0;
			}	
			root=temp;
		}else{
			node *temp=s.top();
			s.pop();
			root=temp;
			flag=1;
		}
	
	}
	postorder(tree);
	return 0;
}