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);//建右子樹