由二叉樹的先序序列和中序序列建構二叉樹

構造思想：

假設目前處理先序序列

pre

的處理區間是

[a,b]

,中序序列

in

處理的區間是

[c,d]

。

例如：

string pre = "123456789";
	string in = "325416879";
           

pre

的處理區間是

[0,8]

,中序序列

in

處理的區間是

[0,8]

若

a<b

,則以

pre[a]

建立二叉樹的根結點，然後搜尋

in[c,d]

,找到

in[i] == pre[a]

的位置

i

,進而把中序序列分為兩個中序子序列

in[c,i-1]

和

in[i+1,d]

,前者有

i-1-c+1 = i - c

個元素，後者有

d-(i+1) +1

個元素。再分别以

pre[a+1,a+i-c]

和

in[c,i-1]

遞歸構造根的左子樹（

pre[a]

為根，不用 再處理）,以

pre[a+i-c+1,b]

和

in[i+1,d]

遞歸構造根的右子樹。

注：為什麼以

pre[a+1,a+i-c]

和

in[c,i-1]

遞歸構造根的左子樹，,以

pre[a+i-c+1,b]

和

in[i+1,d]

遞歸構造根的右子樹？

因為先序周遊和中序周遊的共同點是後通路右子樹，是以

i

前面的在

pre

裡除了

pre[a]

都是左子樹，有

i-c

個元素。

代碼：

#include<iostream>
#include<string>
#include<vector>
#include<queue> 

using namespace std;

struct TreeNode
{
	char data;
	TreeNode *lchild,*rchild;
};

void createBinTree_pre_in(TreeNode *&root,string pre,string in,int a,int b,int c,int d)
{//由二叉樹的先序序列和中序序列建構二叉樹
	if(a <= b)
	{
		root = new TreeNode();		//建立根節點 
		root->data = pre[a];
		root->lchild = NULL;
		root->rchild = NULL;
		int i;
		for(i = c; i <= d; i++)		//中序序列中查找根的位置，此處為i 
		{
			if(in[i] == pre[a])
				break;
		}
		createBinTree_pre_in(root->lchild,pre,in,a+1,a+i-c,c,i-1);	//遞歸建左子樹 
		createBinTree_pre_in(root->rchild,pre,in,a+i-c+1,b,i+1,d);	//遞歸建右子樹 
	}
}

void levelOrder(TreeNode* root)		//利用隊列實作二叉樹的層次周遊 
{
	queue<TreeNode*>que;
	TreeNode* p = root;
	que.push(p);
	while(!que.empty())
	{
		p = que.front();   que.pop();
		cout<<p->data;
		if(p->lchild != NULL)
		{
			que.push(p->lchild);
		}
		if(p->rchild != NULL)
		{
			que.push(p->rchild);
		}
	} 
}
int main()				//test
{
	TreeNode *root;
	string pre = "123456789";
	string in = "325416879";
	createBinTree_pre_in(root,pre,in,0,8,0,8);
	levelOrder(root);
	return 0;
}
           

參考：

《資料結構C語言描述第2版》—殷人昆