Pat 1020

1.题意

（1）给出一棵二叉树的中序序列，以及后序序列，求出该树的层次遍历顺序序列。

2.分析

对于这种题目，我们自己可以很快给出答案，但是要是精确的用代码表示出来，却又有一番难度，难处在于：

（1）我们该怎么将我们的思维转换成这种直接的代码，根据两个序列建成一个二叉树，然后根据层序输出二叉树。

（2）先来看题意中的一个后序序列以及中序序列：

number     7

postPrder  2 3 1 5 7 6 4

inOrder      1  2 3 4 5 6 7

我们自己来分析建树步骤：

Step1:后序序列中最后一个肯定是根节点（如果连这个都不清楚的话，麻烦多看两边书……

Strep2:在中序序列中找到这个根节点值，从而将其左右两边分成左子树与右子树。

Step3:对其左子树以及右子树进行Step1,Step2操作，直到该根节点德左子树或者右子树为NULL时，返回根节点值。

Step4:最后一步简单，就是对其使用队列+二叉树，即可得到层序遍历结果。

3.编写代码

根据以上分析，我们大概就已经知道这么一个过程是什么样子：

（1）要使用递归过程建树；

（2）要返回不同的区间值；

（3）……等等

4.源代码

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
#define maxSize 100
#define null NULL


typedef struct BiTree{
	struct BiTree *lChild,*rChild;//左右子树指针 
	int data;//数据域 
};


int number;
int postOrder[maxSize];
int inOrder[maxSize];

//从二叉树中找出结点并建树
//注意返回的是二叉树的头结点指针 
BiTree* foundData(int postLeft,int postRight,int inLeft,int inRight){

	if(postRight < postLeft){
		return null;
	} 
	int i ;
	int root;//根节点的值 
	int rootIndex;//根节点在中序数组中的下标 
	
	root = postOrder[postRight];//找到root 
	BiTree *T;
	T = new BiTree;//指向具体的结点 
	
	T->data = root;  
	
	//注意细节！for循环边界取值 
	for(i = inLeft;i <= inRight;i++){
		if(inOrder[i] == postOrder[postRight]){
			rootIndex = i;//记录下标 
			break;
		}	
	}
	int leftNodeNumber ;//表示左子树包含的结点个数 
	leftNodeNumber =  rootIndex - inLeft;//注意是减去inLeft,而非postLeft 
	
	T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 
	T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树 
	return T;
}

//前序遍历 
void preTraverseBiTree(BiTree *T){
	if(T == null){
		return ;
	}
	printf("%d ",T->data);
	preTraverseBiTree(T->lChild);
	preTraverseBiTree(T->rChild);	
}

//使用层次遍历（BFS） 
void BfsBiTree(BiTree *T){
	int count = 0;//输出计数 
	queue <BiTree*> q;//使用队列存储指针结点 
	q.push(T);//首先将根节点入队
	while(!q.empty()){//当队列非空时 			
		BiTree* now = q.front();//得到队首 
		q.pop(); //将根结点出队
		count ++;
		if(count < number )		printf("%d ",now->data); //输出 
		else printf("%d",now->data); 
		if(now->lChild!=null)		q.push(now->lChild);//左子树入队 --->注意这里是now，而非是T!! 
		if(now->rChild!=null)     q.push(now->rChild);//右子树入队 
	} 
}

int main(){	
	scanf("%d",&number);
	int i;
	for(i = 0;i< number;i++){
		scanf("%d",&postOrder[i]);
	}	
	//输入inOrder 
	for(i = 0;i< number;i++){
		scanf("%d",&inOrder[i]);
	}	
	BiTree *T;
	T = foundData(0,number-1,0,number-1); //返回作为根节点
	//preTraverseBiTree(T);//前序遍历二叉树
	BfsBiTree(T);
}
/*
4
2 3 1 4
1 2 3 4
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
**/            

5.总结

（1）

T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 
	T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树            

为整个代码的关键所在，关键之处在于：

1）明白一个递归过程的调用

2）确定范围值得选取 

（2）对于上述的取区间的问题，我们首先应该对一个复杂的表达式抽取出一般项，然后对其一般项进行操作；.检验方法：试用多个特殊的项来对总结的表达式进行检验，判断一般项的正确性。 

T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 
T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树 	           

我们将其区间合并一下得到：【postLeft,postLeft + leftNodeNumber -1,postLeft + leftNodeNumber,postRight -1】与【inLeft,rootIndex - 1,rootIndex + 1,inRight】是不是仔细想想就发现竟然是一个完整的区间！！！到这里大家终于明白了递归就是将一个大问题分解成很多小问题，然后这些小问题合并就是大问题分解的逆过程。如果知道了这一点，就会理解这个区间取值是怎么取的。希望大家好运！

T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树