03-树3 Tree Traversals Again 分数 25 作者 陈越
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 (≤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
代码长度限制：16 KB 时间限制：400 ms 内存限制：64 MB
题目解析：
本质是根据一棵树的先序遍历结果和中序遍历结果，求解这棵树的后序遍历结果。
在树的遍历中，知中序和先序可求唯一后序；知中序和后序可求唯一先序；知先序和后序不可求唯一中序。
关键点1：根据输入获得先序遍历结果和中序遍历结果
关键点2：根据先序和中序遍历结果输出后序遍历结果
下面将演示建树和不建树两种情况
代码展示：
不建树的情况
// 根据先序遍历与中序遍历求后序遍历
# include<stdio.h>
# include<string.h>
# define MAXSIZE 5
void Solve(int preL, int inL, int postL, int n, int pre[], int in[], int post[]);
int main(){
// 一共有多少个结点
int N;
scanf("%d",&N);
// 创建一个堆栈
int Stack[N];
int Rear = -1;
// 分别创建前、中、后序遍历的结果数组
int Pre[N],In[N],Post[N];
int PreRear = -1;
// count作为弹出元素的计数
int num, count = 0;
while(count!=N){
char handle[MAXSIZE];
scanf("%s",handle);
if(!strcmp(handle,"Push")){
// 接受一个数字并压入栈
scanf("%d",&num);
Stack[++Rear] = num;
// 前序遍历数组记录
Pre[++PreRear] = num;
}else{
// 出栈并在中序遍历中进行记录
num = Stack[Rear--];
In[count++] = num;
}
}
// 有了前序与中序遍历结果，接下来通过递归函数求后序遍历结果
Solve(0,0,0,N,Pre,In,Post);
int i;
for(i=0;i<N;i++){
if(i!=N-1)printf("%d ",Post[i]);
else printf("%d",Post[i]);
}
}
void Solve(int preL, int inL, int postL, int n, int pre[], int in[], int post[]){
if(n==0)return;
if(n==1){
post[postL] = pre[preL];
return;
}
// 先序的第一个放在给定后序的最后一个
int root = pre[preL];
post[postL+n-1] = root;
// 找出左子树的范围
int i;
for(i=0;i<n;i++){
if(in[inL+i]==root)break;
}
// 左子树要处理的的结点数
int L = i;
// 右子树要处理的结点数
int R = n-L-1;
// 递归处理
Solve(preL+1, inL, postL,L,pre,in,post);
Solve(preL+L+1,inL+L+1,postL+L,R,pre,in,post);
return;
}
建树的情况：
# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# define MAXNODE 30
# define MAXLENGTH 5
typedef struct TreeNode* Tree;
struct TreeNode{
int data;
Tree left;
Tree right;
};
void PostOrder(Tree root,int data);
void CreateTree(int left1,int right1,int left2,int right2,int Pre[],int In[], Tree root);
int main(){
// 创建一个堆栈
int Stack[MAXNODE];
int SHead = -1;
// 接收结点个数
int N;
scanf("%d",&N);
getchar();
// 分别创建一个用来记录先序和中序遍历结果的数组
int PreArray[N],InArray[N];
int PreHead=-1, InHead=-1;
// 接收操作输入，因为有出入栈，因此共有2*N次操作
int i,num;
char* str = (char*)malloc(sizeof(char)*MAXLENGTH);
for(i=0;i<2*N;i++){
scanf("%s",str);
if(strcmp(str,"Push")==0){
// 入栈
scanf("%d",&num);
getchar();
Stack[++SHead] = num;
// 记录先序
PreArray[++PreHead] = num;
}else{
// 出栈
num = Stack[SHead--];
// 记录中序
InArray[++InHead] = num;
}
}
// 创建根结点
Tree root = (Tree)malloc(sizeof(struct TreeNode));
root->data = PreArray[0];
root->left = NULL;
root->right = NULL;
// 构建树
CreateTree(0,N-1,0,N-1,PreArray,InArray,root);
// 后序输出遍历结果，为了格式化输出因此传入根结点的值作为判读依据
PostOrder(root,root->data);
return 0;
}
// 递归后序遍历树
void PostOrder(Tree root,int data){
if(root){
PostOrder(root->left,data);
PostOrder(root->right,data);
if(root->data == data)printf("%d",root->data);
else printf("%d ",root->data);
}
return;
}
// 根据先序和后序构建一棵树；left1与right1表示先序序列的范围；left2与right2表示后序序列的范围
void CreateTree(int left1,int right1,int left2,int right2,int Pre[],int In[], Tree root){
// 首先找到根结点在中序中的位置
int i,index;
for(i=left2;i<=right2;i++){
if(root->data == In[i]){
index = i;
break;
}
}
// 如果根结点有左孩子
if(index!=left2){
// 创建一个左孩子结点
Tree left_son = (Tree)malloc(sizeof(struct TreeNode));
left_son->data = Pre[left1+1];
left_son->left = NULL;
left_son->right = NULL;
root->left = left_son;
// 递归构建这个左孩子结点
CreateTree(left1+1,index-left2+left1,left2,index-1,Pre,In,left_son);
}
// 如果根结点有右孩子
if(index!=right2){
Tree right_son = (Tree)malloc(sizeof(struct TreeNode));
right_son->data = Pre[index-left2+left1+1];
right_son->left = NULL;
right_son->right = NULL;
root->right = right_son;
// 递归构建这个右孩子结点
CreateTree(index-left2+left1+1,right1,index+1,right2,Pre,In,right_son);
}
return;
}
运行结果：
两种情况均可通过测试点
