5樹5.1樹的概述5.2二叉樹基礎(chǔ)5.3二叉樹的遍歷5.4二叉樹遍歷算法的應(yīng)用5.5哈夫曼樹與哈夫曼編碼5.6樹與森林5.7并查集5.8在線題目求解學(xué)習(xí)目標(biāo)1.記憶和理解樹和二叉樹的基礎(chǔ)知識。2.熟練掌握并運用二叉樹的遍歷算法。3.理解哈夫曼編碼相關(guān)概念及相關(guān)算法，熟練掌握構(gòu)造哈夫曼樹及編碼的方法。4.掌握樹、森林與二叉樹之間相互轉(zhuǎn)換的方法。5.運用樹結(jié)構(gòu)求解具體問題。5樹5.1樹的概述定義樹是n（n>=0）個數(shù)據(jù)元素（結(jié)點）的有限集，它或為空樹（n=0），或為非空樹，對于非空樹：（1）有且僅有一個稱為根root的結(jié)點；（2）當(dāng)n>1時，其余結(jié)點可分為m（m>0）個互不相交的有限集T1,T2,…,Tm，其中每一個子集又是一棵樹，稱為根root的子樹。A為根，包含三棵子樹，分別以B、C和D為根。5.1樹的概述術(shù)語結(jié)點：數(shù)據(jù)元素+若干指向子樹的分支，右圖中根結(jié)點A包含數(shù)據(jù)元素A和3個指向子樹的分支，結(jié)點B包含數(shù)據(jù)元素B和2個指向子樹的分支。結(jié)點的度：結(jié)點所包含的分支的個數(shù)，右圖中結(jié)點A的度為3，結(jié)點B的度為2。樹的度：樹中所有結(jié)點的度的最大值，右圖中的樹的度為3。葉子結(jié)點：度為零的結(jié)點，即不包含指向子樹的分支的結(jié)點，也稱葉子或葉結(jié)點，上圖中結(jié)點K、L、F、G、M、I和J都是葉子。5.1樹的概述術(shù)語分支結(jié)點：度大于零的結(jié)點，右圖中A、B、C、D、E和H都是分支結(jié)點。從根到結(jié)點的路徑：由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成，右圖中結(jié)點A、B、E和K及其分支A→B、B→E和E→K構(gòu)成從根結(jié)點A到結(jié)點K的路徑。5.1樹的概述術(shù)語孩子結(jié)點：也稱子結(jié)點或孩子，某結(jié)點所包含的分支所指向的結(jié)點稱為該結(jié)點的子結(jié)點，相應(yīng)的該結(jié)點稱為其分支所指向結(jié)點的父結(jié)點（也稱雙親結(jié)點或雙親），右圖中結(jié)點B、C和D是根結(jié)點A的孩子，而A是B、C和D的父結(jié)點。兄弟結(jié)點：也稱兄弟，雙親相同的結(jié)點互為兄弟，例如右圖中結(jié)點B、C和D互為兄弟。堂兄弟：雙親的雙親相同的結(jié)點互為堂兄弟，上圖中結(jié)點F、G和H互為堂兄弟。5.1樹的概述術(shù)語祖先結(jié)點：從根結(jié)點到某結(jié)點的雙親結(jié)點所構(gòu)成路徑上的結(jié)點都是該結(jié)點的祖先結(jié)點，右圖中A、B和E都是結(jié)點K的祖先結(jié)點。子孫結(jié)點：某結(jié)點的所有分支所指向的子樹上的所有結(jié)點都是該結(jié)點的子孫結(jié)點，右圖中結(jié)點E、F、K和L都是結(jié)點B的子孫。結(jié)點的層次：結(jié)點所處的層次，設(shè)根結(jié)點的層次為1，其他結(jié)點層次等于其雙親結(jié)點的層次加1，上圖中結(jié)點A的層次為1，結(jié)點B、C和D的層次為2，結(jié)點K、L和M的層次為4，其他結(jié)點的層次為3。5.1樹的概述術(shù)語樹的深度：或稱樹的高度，指樹中葉子結(jié)點所在的最大層次，右圖中的樹深度為4。有序樹：子樹之間存在確定的次序關(guān)系，例如二叉樹是有序樹，其子樹有左、右之分。無序樹：子樹之間不存在確定的次序關(guān)系。森林：是m（m≥0）棵互不相交的樹構(gòu)成的集合，m=0時是空森林。任何一棵非空樹可以表示為一個二元組(root，F(xiàn))，其中，root被稱為根結(jié)點，F(xiàn)被稱為子樹森林，上圖的樹包含一個根結(jié)點A和三棵分別以結(jié)點B、C、D為根的子樹森林。5.1樹的概述術(shù)語表5-1列出了樹和線性結(jié)構(gòu)的結(jié)構(gòu)特點對比情況。樹的基本操作包含創(chuàng)建、遍歷、查找、插入結(jié)點和刪除結(jié)點等。5.2二叉樹基礎(chǔ)定義與術(shù)語二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹且互不相交的二叉樹組成。二叉樹的五種基本形態(tài)如下圖所示，分別為空樹、只含根結(jié)點、左子樹為空樹、右子樹為空樹和左右子樹均不為空樹。5.2二叉樹基礎(chǔ)定義與術(shù)語具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？n個結(jié)點的二叉樹共有種形態(tài)？具有3個結(jié)點的普通樹可能有幾種不同形態(tài)？n個結(jié)點的有序樹與n-1個結(jié)點的二叉樹具有相同的形態(tài)數(shù)。52卡特蘭數(shù)5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)性質(zhì)1：二叉樹第i(i≥1)層上至多有2i-1個結(jié)點。思考：二叉樹存在第i（i≥1）層，則該層上至少有幾個結(jié)點？證明：采用歸納法。已知i=1時，只有一個根結(jié)點，即2i-1=

20=1；設(shè)對所有的j（1≤j<i）命題成立，則第j=i-1層至多有2i-2

個結(jié)點；由于二叉樹上每個結(jié)點至多有兩個孩子，則第

i

層的結(jié)點數(shù)至多有2i-2×2=2i-1

個。5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹上至多含2k-1個結(jié)點（k≥1）。思考：深度為k（k≥1）的二叉樹至少有幾個結(jié)點？證明：基于性質(zhì)1，深度為k

的二叉樹上的結(jié)點數(shù)至多為

20+21+……+2k-1=2k-1。5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)性質(zhì)3：對任何一棵二叉樹，若它含有n0個葉子結(jié)點和n2個度為2的結(jié)點，則有n0=n2+1。思考：二叉樹中結(jié)點的度可能為多少？證明：設(shè)二叉樹中度為1的結(jié)點數(shù)為n1，則結(jié)點總數(shù)

n=n0+n1+n2；設(shè)二叉樹上的分支總數(shù)為b，因度為1的結(jié)點產(chǎn)生1個分支，度為2的結(jié)點產(chǎn)生2個分支，則有b=n1+2n2，又因根結(jié)點無分支指向它，而其他結(jié)點都由一個分支指向，故有b=n-1=n0+n1+n2-1=n1+2n2，由此可得n0=n2+1。5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)滿二叉樹是指深度為k且含有2k-1個結(jié)點的二叉樹。滿二叉樹的每一層結(jié)點數(shù)達(dá)到最多。對滿二叉樹中的結(jié)點從上往下、從左往右編號，深度為4的滿二叉樹如下：5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)完全二叉樹是指樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。完全二叉樹或者是滿二叉樹，或者由滿二叉樹刪去最底層的最右側(cè)的若干個結(jié)點得到。深度為4的一棵完全二叉樹：5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)思考：深度為k的完全二叉樹至少幾個結(jié)點，至多幾個結(jié)點？性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為

。證明：設(shè)完全二叉樹的深度為

k，則根據(jù)第二條性質(zhì)得2k-1≤n≤2k-1，有2k-1≤n<2k，即滿足k-1≤log2

n<k，因為

k

只能是整數(shù)，因此，k=5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)性質(zhì)5：若對含

n個結(jié)點的完全二叉樹從上到下，從左至右進(jìn)行1至n的編號，則對于完全二叉樹中任意一個編號為

i

的結(jié)點，有：思考：共有5001個結(jié)點的完全二叉樹有幾個葉子結(jié)點？（1）若i=1，則該結(jié)點是二叉樹的根結(jié)點，無雙親；否則，編號為

的結(jié)點為其雙親；（2）若2i>n，則該結(jié)點無左孩子，否則，編號為2i

的結(jié)點為其左孩子；（3）若2i+1>n，則該結(jié)點無右孩子，否則，編號為2i+1的結(jié)點為其右孩子。5.2二叉樹基礎(chǔ)二叉樹的性質(zhì)關(guān)于性質(zhì)5的說明：（1）編號為i與i+1的結(jié)點在同一層（2）編號為i與i+1的結(jié)點在不同層（設(shè)為第k層和第k+1層）5.2二叉樹基礎(chǔ)二叉樹的存儲結(jié)構(gòu)二叉樹可以采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。二叉樹的順序存儲結(jié)構(gòu)是用一維數(shù)組存儲二叉樹各個結(jié)點的數(shù)據(jù)元素，對于左右孩子的存儲位置，可把二叉樹當(dāng)作缺了一些結(jié)點的完全二叉樹，編號為i的結(jié)點存儲在下標(biāo)為i-1的存儲單元。二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)采用二叉鏈表表示，結(jié)點包含數(shù)據(jù)域data，左孩子指針域lchild，右孩子指針域rchild。5.2二叉樹基礎(chǔ)二叉樹的順序存儲結(jié)構(gòu)下圖所示二叉樹的順序存儲結(jié)構(gòu)對于下標(biāo)為i結(jié)點，若左孩子存在則其下標(biāo)為2i+1，若右孩子存在則其下標(biāo)為2i+2若雙親存在則其下標(biāo)為5.2二叉樹基礎(chǔ)二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲表示constintMaxTreeSize=100;//二叉樹的最大結(jié)點數(shù)typedefcharTElemType;

//為類型char取別名為TElemTypeTElemTypebt[MaxTreeSize];//0號單元存儲根結(jié)點順序存儲結(jié)構(gòu)有什么優(yōu)缺點？順序存儲結(jié)構(gòu)適用于哪些二叉樹？5.2二叉樹基礎(chǔ)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)采用二叉鏈表表示，結(jié)點包含數(shù)據(jù)域data，左孩子指針域lchild，右孩子指針域rchild如左下二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是如右下的二叉鏈表5.2二叉樹基礎(chǔ)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)在n個結(jié)點的二叉鏈表中，有幾個空指針域？5.2二叉樹基礎(chǔ)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Φ慕Y(jié)點結(jié)構(gòu)BiTNodetypedefcharElemType;//若改數(shù)據(jù)域類型，則把char改為相應(yīng)類型structBiTNode{//結(jié)點結(jié)構(gòu)

ElemTypedata;

//

結(jié)點數(shù)據(jù)域

BiTNode*lchild,*rchild;//左、右孩子指針

//帶3個參數(shù)的構(gòu)造函數(shù)

BiTNode(ElemTypee,BiTNode*left,BiTNode*right){

data=e;

lchild=left;

rchild=right;

}

BiTNode(){}

//無參構(gòu)造函數(shù)};5.2二叉樹基礎(chǔ)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)函數(shù)名為BiTNode的兩個成員函數(shù)是兩個構(gòu)造函數(shù)。構(gòu)造函數(shù)與結(jié)構(gòu)體類型同名，且無返回類型，在定義或創(chuàng)建變量時自動調(diào)用，并按所提供的參數(shù)自動初始化數(shù)據(jù)成員。例如，以下語句創(chuàng)建一個數(shù)據(jù)域為字符A，左、右孩子指針為空指針的

結(jié)點：BiTNode*root=newBiTNode('A',NULL,NULL);//調(diào)用3個參數(shù)的構(gòu)造函數(shù)在定義了帶參構(gòu)造函數(shù)之后，為避免無法使用類似語句“BiTNodenode;”直接定義變量，應(yīng)顯式定義無參構(gòu)造函數(shù)。5.3二叉樹的遍歷遍歷基礎(chǔ)知識二叉樹的遍歷是指順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次?！霸L問”的含義可以很廣，如：輸出、統(tǒng)計或修改結(jié)點的信息。對二叉樹而言，可以有三種搜索路徑：（1）先上后下的按層次遍歷；（2）先左（子樹）后右（子樹）的遍歷；（3）先右（子樹）后左（子樹）的遍歷。層次遍歷是指從第一層開始，從上往下逐層從左到右訪問二叉樹中的結(jié)點。5.3二叉樹的遍歷遍歷基礎(chǔ)知識右圖中的二叉樹的層次遍歷序列是什么？ABCDEFG層次遍歷的算法思想：借助具有先進(jìn)先出特性的數(shù)據(jù)結(jié)構(gòu)“隊列”，首先把根結(jié)點指針入隊；然后，當(dāng)隊列非空反復(fù)執(zhí)行：取隊頭元素并使之出隊，輸出其數(shù)據(jù)域，若其左孩子指針非空則入隊，若其右孩子指針非空則入隊。先左后右的遍歷和先右后左的遍歷是帶有遞歸思想的遍歷。5.3二叉樹的遍歷遍歷基礎(chǔ)知識若把“二叉樹”的根、左子樹和右子樹分別記作D、L和R，則有6種遍歷方案：DLR、LDR、LRD、DRL、RDL和RLD。由于先左后右和先右后左在本質(zhì)上并沒有差別，一般采用先左后右的處理方案，對應(yīng)的三種遍歷分別稱為先序遍歷（DLR）、中序遍歷（LDR）和后序遍歷（LRD）。先序遍歷算法思想：若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。上圖二叉樹的先序遍歷序列：ABDEGCF5.3二叉樹的遍歷遍歷基礎(chǔ)知識中序遍歷算法思想：若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。后序遍歷算法思想：若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。上圖二叉樹的中序遍歷序列：DBGEACF上圖二叉樹的后序遍歷序列：DGEBFCA5.3二叉樹的遍歷遍歷算法實現(xiàn)先序遍歷的遞歸實現(xiàn)//先序遍歷以T為根結(jié)點指針的二叉樹，輸出各結(jié)點數(shù)據(jù)域的值voidPreOrder(BiTNode*T){

//先序遍歷

if(!T)return;

//若是空樹，則返回

cout<<T->data;//訪問根結(jié)點

PreOrder(T->lchild);

//先序遍歷左子樹

PreOrder(T->rchild);

//先序遍歷右子樹}5.3二叉樹的遍歷遍歷算法實現(xiàn)中序遍歷的遞歸實現(xiàn)//中序遍歷以T為根結(jié)點指針的二叉樹，輸出各結(jié)點數(shù)據(jù)域的值voidInOrder(BiTNode*T){//中序遍歷

if(!T)return;

//若是空樹，則返回

InOrder(T->lchild);

//中序遍歷左子樹

cout<<T->data;//訪問根結(jié)點

InOrder(T->rchild);

//中序遍歷右子樹}5.3二叉樹的遍歷遍歷算法實現(xiàn)后序遍歷的遞歸實現(xiàn)//后序遍歷以T為根結(jié)點指針的二叉樹，輸出各結(jié)點數(shù)據(jù)域的值voidPostOrder(BiTNode*T){//后序遍歷

if(!T)return;

//若是空樹，則返回

PostOrder(T->lchild);

//后序遍歷左子樹

PostOrder(T->rchild);

//后序遍歷右子樹

cout<<T->data;//訪問根結(jié)點}5.3二叉樹的遍歷遍歷算法實現(xiàn)對于這三個遞歸算法，如果去掉輸出語句，從遞歸的角度看，三種算法是完全相同的，或說這三種算法的訪問路徑是相同的，只是訪問結(jié)點的時機(jī)不同。在遍歷的過程中，每個結(jié)點會被經(jīng)過3次。先序遍歷在第1次經(jīng)過結(jié)點時訪問該結(jié)點，中序遍歷在第2次（從左子樹回溯）經(jīng)過結(jié)點時訪問該結(jié)點，后序遍歷在第3次（從右子樹回溯）經(jīng)過結(jié)點時訪問該結(jié)點。因為每個結(jié)點只訪問一次，時間復(fù)雜度可用O(n)衡量；由于遞歸算法隱式使用棧，若n個結(jié)點的樹高為n，則棧占用的最大輔助空間為O(n)，所以最壞空間復(fù)雜度為O(n)。5.3二叉樹的遍歷遍歷算法實現(xiàn)中序遍歷的非遞歸實現(xiàn)

中序遍歷訪問的第一個結(jié)點是最左側(cè)（無左孩子）的結(jié)點，因此在未找到該結(jié)點時不斷把左孩子指針入棧。

首先用一個指針（設(shè)為p）指向根結(jié)點，當(dāng)p非空或棧非空時重復(fù)執(zhí)行：若p非空，則先把p入棧，再使p指向其左孩子；否則（p為空）取棧頂元素賦給p并輸出其所指結(jié)點的數(shù)據(jù)域再使之出棧，接著使p往右指向右孩子。5.3二叉樹的遍歷遍歷算法實現(xiàn)中序遍歷的非遞歸實現(xiàn)

voidInOrderTraverse(BiTNode*T){//中序遍歷的非遞歸算法

BiTNode*p=T;stack<BiTNode*>S;//輔助棧

while(p!=NULL||!S.empty()){

if(p!=NULL){

//(子樹)根指針入棧，遍歷左子樹

S.push(p);

p=p->lchild;

}else{

//(子樹)根指針退棧，遍歷右子樹

p=S.top();

S.pop();

cout<<p->data;

p=p->rchild;

}

}}5.4二叉樹遍歷算法的應(yīng)用統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想：在遍歷二叉樹的過程中判斷結(jié)點是否葉子，是則計數(shù)器增1。采用先序遍歷的思想，若當(dāng)前指針為NULL則返回0；否則判斷當(dāng)前結(jié)點是否滿足葉子的條件，是則計數(shù)器增1，再遞歸調(diào)用自身統(tǒng)計左、右子樹中的葉子并累加到計數(shù)器中。5.4二叉樹遍歷算法的應(yīng)用統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法實現(xiàn)//統(tǒng)計以T為根結(jié)點指針的二叉樹的葉子數(shù)intCountLeaf(BiTNode*T){

if(T==NULL)return0;//

若是空樹則返回0

intcnt=0;

//

計數(shù)器清0

//

若滿足葉子的條件，則葉子數(shù)增1

if(T->lchild==NULL&&T->rchild==NULL)

cnt++;

cnt+=CountLeaf(T->lchild);

//遍歷左子樹

cnt+=CountLeaf(T->rchild);

//遍歷右子樹

returncnt;}如何修改本算法求解度為1或2的結(jié)點數(shù)？5.4二叉樹遍歷算法的應(yīng)用求二叉樹的深度算法基本思想：二叉樹的深度等于其左、右子樹深度的最大值加1。先分別求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右子樹深度的大者，然后加1。采用后序遍歷的思想，在求得左、右子樹深度后取其中的大者加1返回。5.4二叉樹遍歷算法的應(yīng)用求二叉樹的深度算法實現(xiàn)//返回以T為根結(jié)點指針的二叉樹的深度intDepth(BiTNode*T){

if(!T)return0;

//

若是空樹則返回0

intdepthLeft=Depth(T->lchild);//遍歷左子樹

intdepthRight=Depth(T->rchild);//遍歷右子樹

//深度為左、右子樹深度的大者再加1

return1+max(depthLeft,depthRight);}5.4二叉樹遍歷算法的應(yīng)用根據(jù)帶虛結(jié)點的先序遍歷序列建立二叉樹以字符串的形式定義一棵二叉樹：“根左子樹右子樹”，以數(shù)據(jù)元素表示結(jié)點，若結(jié)點為空，該結(jié)點為虛結(jié)點，以特殊符號（如“@”）表示。帶虛結(jié)點的字符串對應(yīng)一棵完全二叉樹，其中，若左子樹或右子樹為空樹，則以特殊字符表示。例如：

以字符串“A@@”表示只含一個根結(jié)點A的二叉樹；

以字符串“AB@C@@D@@”表示如下二叉樹。5.4二叉樹遍歷算法的應(yīng)用根據(jù)帶虛結(jié)點的先序遍歷序列建立二叉樹算法思想：設(shè)以字符串s表示帶虛結(jié)點的先序遍歷序列，則可逐個取得s中的字符，若為特殊字符，則返回空指針，否則用該字符創(chuàng)建一個結(jié)點并用一個指針指向（設(shè)為p），再用該字符之后的剩余字符構(gòu)成的字符串遞歸創(chuàng)建該結(jié)點的左、右子樹，最后返回指針p。5.4二叉樹遍歷算法的應(yīng)用根據(jù)帶虛結(jié)點的先序遍歷序列建立二叉樹算法實現(xiàn)//按字符串s創(chuàng)建二叉樹，返回根結(jié)點指針BiTNode*CreateBiTree(string&s){

if(s[0]=='@'){

//遇到特殊字符

s=s.substr(1);//去掉s的第一個字符

returnNULL;

//返回空指針

}

BiTNode*p=newBiTNode;//創(chuàng)建根結(jié)點

p->data=s[0];

//處理根結(jié)點數(shù)據(jù)域

s=s.substr(1);

//取s中去掉第一個字符后的剩余子串

p->lchild=CreateBiTree(s);//處理左子樹

p->rchild=CreateBiTree(s);

//處理右子樹

returnp;}5.4二叉樹遍歷算法的應(yīng)用根據(jù)帶虛結(jié)點的先序遍歷序列建立二叉樹上述算法需逐個去掉s的首字符，即需要返回變化后的s，因此s作為引用參數(shù)。調(diào)用示例：stringdef="ABC@@DE@G@@F@@@";BiTNode*bt=CreateBiTree(def);5.4二叉樹遍歷算法的應(yīng)用二叉樹的確定僅知二叉樹的先序遍歷序列（先序序列）不能唯一確定一棵二叉樹。由先序序列和中序序列確定一棵二叉樹的方法：

由二叉樹的先序序列確定根（從左往右掃描，第一個出現(xiàn)的為根）；在中序序列中找到該根并得到其左、右子樹序列；對左、右子樹序列按相同的方法做。由后序序列和中序序列確定一棵二叉樹的方法：

由二叉樹的后序序列確定根（從右往左掃描，第一個出現(xiàn)的為根）；在中序序列中找到該根并得到其左、右子樹序列；對左、右子樹序列按相同的方法做。

5.4二叉樹遍歷算法的應(yīng)用二叉樹的確定例5.4.1由先序序列和中序序列確定二叉樹已知二叉樹的先序遍歷序列：ABCDEFG，

中序遍歷序列：CBDAEGF，要求畫出該二叉樹。5.4二叉樹遍歷算法的應(yīng)用二叉樹的確定例5.4.2由后序序列和中序序列確定二叉樹已知二叉樹的后序遍歷序列：DECBHGFA，

中序遍歷序列：BDCEAFHG，要求畫出該二叉樹。5.4二叉樹遍歷算法的應(yīng)用二叉樹的確定根據(jù)先序序列和中序序列確定二叉樹的算法思想

設(shè)先序序列存放在pre數(shù)組中，中序序列存放在in數(shù)組中，先取pre數(shù)組的首元素pre[0]為根，然后在in數(shù)組中找到pre[0]，設(shè)其下標(biāo)為i；則中序序列中in[0]~in[i-1]構(gòu)成根結(jié)點pre[0]的左子樹，共i個結(jié)點，對應(yīng)先序序列中的pre[1]~pre[i]；中序序列中in[i+1]~in[n-1]構(gòu)成根結(jié)點pre[0]的右子樹，共n-i-1個結(jié)點，對應(yīng)先序序列中的pre[i+1]~pre[n-1]。因此，可用pre[0]為數(shù)據(jù)元素創(chuàng)建根結(jié)點，以pre[1]~pre[i]、in[0]~in[i-1]分別為根結(jié)點的左子樹的先序序列和中序序列創(chuàng)建根結(jié)點的左子樹，以pre[i+1]~pre[n-1]、in[i+1]~in[n-1]分別為根結(jié)點的右子樹的先序序列和中序序列創(chuàng)建根結(jié)點的右子樹。5.4二叉樹遍歷算法的應(yīng)用二叉樹的確定根據(jù)先序序列和中序序列確定二叉樹的算法實現(xiàn)//參數(shù)pre是存放先序序列的數(shù)組，in是存放中序序列的數(shù)組，n為結(jié)點總數(shù)；//返回根結(jié)點指針BiTNode*createBT(char*pre,char*in,intn){

if(n==0)returnNULL;//若結(jié)點數(shù)為0，則返回NULL

charroot=pre[0];

//取得二叉樹的根

inti;

for(i=0;i<n;i++){

if(in[i]==root)break;//找到中序序列的分割位置

}

char*preLeft=pre+1;

//左子樹的先序序列

char*preRight=pre+i+1;

//右子樹的先序序列

5.4二叉樹遍歷算法的應(yīng)用二叉樹的確定根據(jù)先序序列和中序序列確定二叉樹的算法實現(xiàn)

char*inLeft=in;

//左子樹的中序序列

char*inRight=in+i+1;

//右子樹的中序序列

//i為左子樹的結(jié)點數(shù),n-i-1為右子樹的結(jié)點數(shù)//遞歸處理左子樹

BiTNode*left=createBT(preLeft,inLeft,i);

//遞歸處理右子樹BiTNode*right=createBT(preRight,inRight,n-i-1);

BiTNode*p=newBiTNode(root,left,right);//創(chuàng)建根結(jié)點

returnp;

//返回根結(jié)點指針}5.5哈夫曼樹與哈夫曼編碼哈夫曼樹基礎(chǔ)知識哈夫曼（Huffman）樹是帶權(quán)路徑長度（WeightedPathLength，WPL）最短的二叉樹，也稱最優(yōu)二叉樹。哈夫曼編碼在數(shù)據(jù)壓縮等方面很有應(yīng)用價值。路徑：從一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑。路徑長度：路徑上的分支數(shù)目稱作路徑長度。樹的路徑長度：樹根到每個結(jié)點的路徑長度之和。5.5哈夫曼樹與哈夫曼編碼哈夫曼樹基礎(chǔ)知識樹的帶權(quán)路徑長度（WPL）：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。設(shè)樹中共有m個葉子，第k個葉子的權(quán)重為，從根結(jié)點到第k個葉子的路徑長度為，則WPL=5×2+2×3+4×3+7×2+9×2=60WPL=7×4+9×4+5×3+4×2+2×1=895.5哈夫曼樹與哈夫曼編碼哈夫曼樹基礎(chǔ)知識在所有含n個葉子結(jié)點且其權(quán)值相同的二叉樹中，必存在一棵其帶權(quán)路徑長度為最小值的，稱為“哈夫曼樹”。哈夫曼樹的構(gòu)造算法：（1）根據(jù)給定的n個權(quán)值{w1，w2，…，wn}，構(gòu)造n棵二叉樹的森林：F={T1，T2，…，Tn}，其中，每棵二叉樹中均只含一個帶權(quán)值為wi的根結(jié)點，其左、右子樹為空樹；（2）在F中選取其根結(jié)點的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；（3）從F中刪去這兩棵樹，同時加入剛生成的新樹；（4）重復(fù)（2）和（3）兩步，直至F中只含一棵樹為止。5.5哈夫曼樹與哈夫曼編碼哈夫曼樹基礎(chǔ)知識例5.5.1哈夫曼樹的構(gòu)造已知權(quán)值集合W={5，6，2，9，7}，請構(gòu)造一棵哈夫曼樹。初始森林第1次合并第2次合并第3次合并第4次合并WPL=(2+5)×3+(6+7+9)×2=65WPL=29+13+16+7=655.5哈夫曼樹與哈夫曼編碼哈夫曼樹基礎(chǔ)知識哈夫曼編碼是一種最優(yōu)前綴編碼。前綴編碼是指任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。哈夫曼編碼構(gòu)造方法：對哈夫曼樹中的左分支寫0，右分支寫1；則對于某個葉結(jié)點而言，從根結(jié)點到該葉結(jié)點的路徑上的0或1序列構(gòu)成該葉結(jié)點所對應(yīng)字符的哈夫曼編碼。哈夫曼樹構(gòu)造哈夫曼編碼得到哈夫曼編碼集：{00，01，11，100，101}5.5哈夫曼樹與哈夫曼編碼哈夫曼樹及其編碼的算法實現(xiàn)采用順序存儲結(jié)構(gòu)實現(xiàn)哈夫曼樹及其編碼。字符集的元素結(jié)構(gòu)structElemtype{//字符集的元素結(jié)構(gòu)（原始信息）

chardata;

//字符

intweight;

//權(quán)重};哈夫曼樹的結(jié)點結(jié)構(gòu)structHTNode{//哈夫曼樹的結(jié)點結(jié)構(gòu)

chardata;//字符

intweight;//權(quán)重

intparent,lchild,rchild;//父結(jié)點，左孩子，右孩子

stringcode;//編碼};5.5哈夫曼樹與哈夫曼編碼哈夫曼樹及其編碼的算法實現(xiàn)構(gòu)造哈夫曼樹的算法實現(xiàn)//根據(jù)w數(shù)組提供的n個字符及權(quán)值，建立哈夫曼樹的算法HTNode*createHuffmanTree(Elemtype*w,intn){

HTNode*ht=newHTNode[2*n];

//0號單元未用

inti,p1,p2;

for(i=1;i<=n;i++){

//葉結(jié)點初始化

ht[i].data=w[i].data;

ht[i].weight=w[i].weight;

ht[i].parent=ht[i].lchild=ht[i].rchild=0;

}

for(i=n+1;i<2*n;i++){

//非葉結(jié)點初始化

ht[i].weight=ht[i].parent=ht[i].lchild=ht[i].rchild=0;

}5.5哈夫曼樹與哈夫曼編碼哈夫曼樹及其編碼的算法實現(xiàn)構(gòu)造哈夫曼樹的算法實現(xiàn)

for(i=n+1;i<2*n;i++){

//進(jìn)行n-1次合并，產(chǎn)生n-1個新結(jié)點

Select(ht,1,i,p1,p2);//區(qū)間[1,i)選擇權(quán)重最小的兩個

ht[p1].parent=ht[p2].parent=i;

//構(gòu)造新的結(jié)點i

ht[i].lchild=p1;

ht[i].rchild=p2;

ht[i].weight=ht[p1].weight+ht[p2].weight;

}

returnht;}5.5哈夫曼樹與哈夫曼編碼哈夫曼樹及其編碼的算法實現(xiàn)構(gòu)造哈夫曼樹的算法實現(xiàn)voidSelect(HTNode*ht,intfrom,intto,int&p1,int&p2){

ht[0].weight=INT_MAX,p1=0;

for(inti=from;i<to;i++){

if(ht[i].parent!=0)continue;

if(ht[i].weight<ht[p1].weight)p1=i;

}

ht[p1].parent=to,p2=0;

for(inti=from;i<to;i++){

if(ht[i].parent!=0)continue;

if(ht[i].weight<ht[p2].weight)p2=i;

}}5.5哈夫曼樹與哈夫曼編碼哈夫曼樹及其編碼的算法實現(xiàn)構(gòu)造哈夫曼編碼的算法實現(xiàn)//構(gòu)造哈夫曼編碼的算法voidCreateHuffmanCode(HTNode*ht,intn){

ht[2*n-1].code="";

//根的編碼為空串//從根開始訪問n-1個非葉結(jié)點，構(gòu)造它們左右子樹的編碼

for(inti=2*n-1;i>n;i--){

//處理n-1個非葉結(jié)點

intleft=ht[i].lchild; //取得父結(jié)點i（下標(biāo)）的左孩子下標(biāo)

intright=ht[i].rchild; //取得父結(jié)點i（下標(biāo)）的右孩子下標(biāo)

ht[left].code=ht[i].code+"0"; //左孩子編碼

ht[right].code=ht[i].code+"1"; //右孩子編碼

}}5.6樹與森林樹的存儲表示樹的常用存儲結(jié)構(gòu)包括雙親表示法、孩子表示法、孩子兄弟表示法等。雙親表示法：用一個結(jié)構(gòu)體（包含數(shù)據(jù)域data和雙親域parent）數(shù)組存儲樹，其中，根結(jié)點存放在下標(biāo)為0的位置，其雙親設(shè)為特殊值-1，其他結(jié)點依序存放數(shù)組中，雙親域存放其雙親的下標(biāo)。

雙親表示法容易找到各個結(jié)點的雙親結(jié)點?！安⒉榧辈捎秒p親表示法（一維整型數(shù)組存儲雙親的下標(biāo)）。5.6樹與森林樹的存儲表示孩子表示法：也稱為孩子鏈表表示法，即把某結(jié)點的所有孩子（下標(biāo)）構(gòu)成為一個鏈表。這種存儲結(jié)構(gòu)包含兩部分，第一部分是用結(jié)構(gòu)體數(shù)組存儲各個結(jié)點（含數(shù)據(jù)元素及指向第一個孩子的指針），第二部分是由每個結(jié)點的孩子鏈表構(gòu)成。

孩子表示法容易找到各個結(jié)點的孩子結(jié)點。若同時希望方便找到雙親結(jié)點，則可為結(jié)構(gòu)體數(shù)組增加一個雙親域。5.6樹與森林樹的存儲表示孩子兄弟法：也稱為左孩子-右兄弟鏈表表示法，即采用二叉鏈表來存儲樹，二叉鏈表中結(jié)點的左指針指向樹中該結(jié)點的第一個孩子，右指針指向該結(jié)點右側(cè)的第一個兄弟。

通過孩子兄弟法可以把樹轉(zhuǎn)換為二叉樹存儲，從而便于把對樹的操作轉(zhuǎn)換為對其所對應(yīng)的二叉樹的操作。5.6樹與森林二叉樹與森林之間的轉(zhuǎn)換森林轉(zhuǎn)換為二叉樹：（1）把森林中的每棵樹根據(jù)“左孩子-右兄弟鏈表”的存儲結(jié)構(gòu)轉(zhuǎn)換為二叉樹；（2）從后往前依次把第i（i≥2）棵二叉樹鏈接為第i-1棵二叉樹的根結(jié)點的右子樹。例5.6.1森林轉(zhuǎn)換為二叉樹把右圖所示的森林轉(zhuǎn)換為二叉樹。5.6樹與森林二叉樹與森林之間的轉(zhuǎn)換例5.6.1森林轉(zhuǎn)換為二叉樹森林中的每棵樹都轉(zhuǎn)換為一棵二叉樹二叉樹依次鏈接到前一棵二叉樹的根結(jié)點上5.6樹與森林二叉樹與森林之間的轉(zhuǎn)換二叉樹轉(zhuǎn)換為森林：（1）依次斷開（各棵）二叉樹根結(jié)點與其右孩子之間的分支得到若干棵二叉樹；（2）把每棵二叉樹根據(jù)“左孩子-右兄弟鏈表”的存儲結(jié)構(gòu)還原為樹。例5.6.2二叉樹轉(zhuǎn)換為森林把右圖所示的二叉樹轉(zhuǎn)換為森林。5.6樹與森林二叉樹與森林之間的轉(zhuǎn)換例5.6.2二叉樹轉(zhuǎn)換為森林依次斷開二叉樹根結(jié)點與其右孩子之間的分支各二叉樹還原為樹5.6樹與森林樹與森林的遍歷樹的遍歷包括先根（序）遍歷、后根（序）遍歷和層次遍歷先根遍歷思想：若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。后根遍歷思想：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。層次遍歷思想：若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。例5.6.3樹的遍歷序列寫出右圖所示的樹的先根遍歷、后根遍歷和層次遍歷序列。先根遍歷序列：ABEFCDGHIJK后根遍歷序列：EFBCIJKHGDA層次遍歷序列：ABCDEFGHIJK5.6樹與森林樹與森林的遍歷森林由三部分構(gòu)成：（1）森林中第一棵樹的根結(jié)點（如右圖中的B）；（2）森林中第一棵樹的子樹森林（如右圖中的E、F）；（3）森林中其他樹構(gòu)成的森林（如右圖中以C、D為根的樹）森林的遍歷主要包括先序遍歷和中序遍歷。森林的先序遍歷思想如下：若森林不空，則（1）訪問森林中第一棵樹的根結(jié)點；（2）先序遍歷森林中第一棵樹的子樹森林；（3）先序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林。5.6樹與森林樹與森林的遍歷森林的先序遍歷：依次從左至右對森林中的每一棵樹進(jìn)行先根遍歷。右圖中的森林的先序遍歷序列為BEFCDGHIJK。森林的中序遍歷思想如下：若森林不空，則（1）中序遍歷森林中第一棵樹的子樹森林；（2）訪問森林中第一棵樹的根結(jié)點；（3）中序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林。森林的中序遍歷：依次從左至右對森林中的每一棵樹進(jìn)行后根遍歷。右上圖中的森林的中序遍歷序列為EFBCIJKHGD。5.6樹與森林樹與森林的遍歷可以把樹和森林的遍歷轉(zhuǎn)換為對應(yīng)二叉樹的遍歷。樹、森林的遍歷和二叉樹遍歷的對應(yīng)關(guān)系如表5-2所示：5.7并查集并查集基礎(chǔ)并查集，也稱不相交集合（DisjointSet），將編號分別為1…n的n個元素劃分為若干個不相交集合，在每個集合中，選擇其中某個元素代表其所在的集合。并查集常見操作：（1）合并兩個集合；（2）查找某元素屬于哪個集合。并查集中的每個集合可用一棵樹（采用雙親表示法存儲）表示。若用數(shù)組P[n+1]（n為元素個數(shù)，下標(biāo)從1開始用）表示并查集的存儲結(jié)構(gòu)，則有：（1）若P[i]=i，則表示i是某個集合（樹）的根；（2）若P[i]=j（j!=i），表示j是i的父結(jié)點。5.7并查集并查集基礎(chǔ)示例，P數(shù)組如下：則包含3個集合（樹），具體如下：5.7并查集并查集基礎(chǔ)若要查某個結(jié)點所屬的集合，則當(dāng)P[x]!=x時反復(fù)執(zhí)行x=P[x]。對于并操作，若兩個結(jié)點x、y的父結(jié)點fx、fy不同，則可把P[fy]置為fx。一開始可把每個結(jié)點視為一個集合。并查集算法實現(xiàn)constintN=1001;

//數(shù)組長度，最大的結(jié)點數(shù)+1intP[N];

//存放父結(jié)點下標(biāo)，從1開始用voidInit(intn){

//初始化，每個結(jié)點作為一個集合

for(inti=1;i<=n;i++)

{

P[i]=i;

}}5.7并查集并查集基礎(chǔ)并查集算法實現(xiàn)intFind(intx){

//查操作

inty=x;

//暫存原結(jié)點

while(P[x]!=x){//尋找根結(jié)點,最終x就是該集合的根結(jié)點

x=P[x];

//把x置為其父結(jié)點

}

while(y!=x){

//路徑壓縮，當(dāng)還未找到根結(jié)點x時執(zhí)行

intt=P[y];

//暫存結(jié)點y的父結(jié)點

P[y]=x;

//把結(jié)點y的父結(jié)點置為根結(jié)點x

y=t;

//下次繼續(xù)處理y原來的父結(jié)點

}

returnx;

//返回根結(jié)點}5.7并查集并查集基礎(chǔ)并查集算法實現(xiàn)boolUnion(intx,inty){

//并操作

intfx,fy;

//存放x,y的根結(jié)點

fx=Find(x);

//查找x的父結(jié)點保存在fx中

fy=Find(y);

//查找x的父結(jié)點保存在fy中

if(fx==fy)returnfalse;//若x、y在同一集合，則不能并

P[fy]=fx;

//完成并操作，把結(jié)點fy的父結(jié)點置為fx

returntrue;

//返回true表示正常完成并操作}5.8在線題目求解例5.8.1二叉樹的建立與遍歷

根據(jù)帶虛結(jié)點的先序序列建立二叉樹，輸出該二叉樹的中序、后序遍歷序列。輸入:

測試數(shù)據(jù)有多組，處理到文件尾。每組測試數(shù)據(jù)在一行中輸入一個字符串（不含空格且長度不超過80），表示二叉樹的先序遍歷序列，其中字符'*'表示虛結(jié)點（對應(yīng)的子樹為空）。輸出:

對于每組測試，分別在兩行輸出所建立二叉樹的中序遍歷序列和后序遍歷序列。5.8在線題目求解例5.8.1二叉樹的建立與遍歷輸入樣例:HDA**C*B**GF*E***輸出樣例:ADCBHFEGABCDEFGH解析：根據(jù)帶虛結(jié)點的先序序列建立二叉樹可調(diào)用5.4節(jié)中的CreateBiTree算法，二叉樹的中序、后序遍歷可調(diào)用5.3.2小節(jié)的InOrder算法和PostOrder算法。5.8在線題目求解例5.8.1二叉樹的建立與遍歷#include<iostream>#include<string>usingnamespacestd;

structBiTNode{

chardata;

BiTNode*lchild,*rchild;};5.8在線題目求解例5.8.1二叉樹的建立與遍歷BiTNode*CreateBiTree(string&s){

if(s[0]=='*'){

//遇到特殊字符*

s=s.substr(1);

//去掉首字符

returnNULL;

//返回空指針

}

BiTNode*p=newBiTNode;

//創(chuàng)建根結(jié)點

p->data=s[0];

//處理根結(jié)點數(shù)據(jù)

s=s.substr(1);

//去掉首字符

p->lchild=CreateBiTree(s);

//處理左子樹

p->rchild=CreateBiTree(s);

//處理右子樹

returnp;}5.8在線題目求解例5.8.1二叉樹的建立與遍歷voidInOrder(BiTNode*T){

//中序遍歷

if(T==NULL)return;

//若為空樹則返回

InOrder(T->lchild);

//中序遍歷左子樹

cout<<T->data;

//輸出根結(jié)點數(shù)據(jù)

InOrder(T->rchild);

//中序遍歷右子樹}

voidPostOrder(BiTNode*T){

//后序遍歷

if(T==NULL)return;

//若為空樹則返回

PostOrder(T->lchild);

//后序遍歷左子樹

PostOrder(T->rchild);

//后序遍歷右子樹

cout<<T->data;

//輸出根結(jié)點數(shù)據(jù)}5.8在線題目求解例5.8.1二叉樹的建立與遍歷intmain(){

strings;

while(cin>>s){

BiTNode*root=CreateBiTree(s);

InOrder(root);

cout<<endl;

PostOrder(root);

cout<<endl;

}

return0;}5.8在線題目求解例5.8.2二叉樹

二叉樹采用二叉鏈表存儲，要求根據(jù)給定的先序遍歷序列和中序遍歷序列建立二叉樹，并輸出后序遍歷序列、結(jié)點總數(shù)、葉子數(shù)、度為1的結(jié)點數(shù)、度為2的結(jié)點數(shù)。輸入:

測試數(shù)據(jù)有多組，處理到文件尾。每組測試數(shù)據(jù)的第一行輸入結(jié)點數(shù)n（1≤n≤10），第二、三行各輸入n個整數(shù)，分別表示二叉樹的先序遍歷序列和中序遍歷序列。輸出:

對于每組測試，在一行上分別輸出該二叉樹的后序遍歷序列，結(jié)點總數(shù)，葉子數(shù)，度為1的結(jié)點數(shù)，度為2的結(jié)點數(shù)。每兩個數(shù)據(jù)之間留一個空格。5.8在線題目求解例5.8.2二叉樹輸入樣例:9124735896472185936101247893561074982156103輸出樣例:74289563194237984210653110352解析：根據(jù)給定的先序遍歷序列和中序遍歷序列建立二叉樹可使用5.4節(jié)的createBT算法（數(shù)組類型改為int），之后進(jìn)行后序遍歷、基于遍歷算法統(tǒng)計葉子數(shù)、度為1和度為2的結(jié)點數(shù)及結(jié)點總數(shù)。5.8在線題目求解例5.8.2二叉樹#include<iostream>usingnamespacestd;

structBiTNode{

intdata;

BiTNode*lchild,*rchild;

BiTNode(intc,BiTNode*left,BiTNode*right){

data=c;

lchild=left;

rchild=right;

}};5.8在線題目求解例5.8.2二叉樹//根據(jù)先序序列pre、中序序列in建立二叉樹，n為結(jié)點總數(shù)BiTNode*CreateBT(int*pre,int*in,intn){

if(n==0)returnNULL;

charroot=pre[0];

inti;

for(i=0;i<n;i++)

if(in[i]==root)break;

int*preleft=pre+1;

int*preright=pre+i+1;

int*inleft=in;

int*inright=in+i+1;

BiTNode*left=CreateBT(preleft,inleft,i);

BiTNode*right=CreateBT(preright,inright,n-i-1);

BiTNode*p=newBiTNode(root,left,right);

returnp;}5.8在線題目求解例5.8.2二叉樹voidPostOrder(BiTNode*p){

//后序遍歷

if(!p)return;

PostOrder(p->lchild);

PostOrder(p->rchild);

cout<<p->data<<"";}

intCountAll(BiTNode*p){

//統(tǒng)計結(jié)點總數(shù)

if(!p)return0;

returnCountAll(p->lchild)+CountAll(p->rchild)+1;}5.8在線題目求解例5.8.2二叉樹intCountLeaf(BiTNode*p){

//統(tǒng)計葉子數(shù)

if(!p)return0;

if(p->lchild==NULL&&p->rchild==NULL)return1;

elsereturnCountLeaf(p->lchild)+CountLeaf(p->rchild);}

intCountSingle(BiTNode*p){

//統(tǒng)計度為1的結(jié)點總數(shù)

if(!p)return0;

intcnt=0;

if((p->lchild&&!p->rchild)||(!p->lchild&&p->rchild))cnt=1;

cnt+=CountSingle(p->lchild);

cnt+=CountSingle(p->rchild);

returncnt;}5.8在線題目求解例5.8.2二叉樹intCountBoth(BiTNode*p){

//統(tǒng)計度為2的結(jié)點總數(shù)

if(!p)return0;

intcnt=0;

if(p->lchild&&p->rchild)cnt=1;

cnt+=CountBoth(p->lchild);

cnt+=CountBoth(p->rchild);

returncnt;}5.8在線題目求解例5.8.2二叉樹intmain(){

intn;

while(cin>>n){

intpre[n];

intin[n];

for(inti=0;i<n;i++)cin>>pre[i];

for(inti=0;i<n;i++)cin>>in[i];

BiTNode*p=CreateBT(pre,in,n);

PostOrder(p);

cout<<CountAll(p)<<""<<CountLeaf(p)<<"";

cout<<CountSingle(p)<<""<<CountBoth(p)<<endl;

}

return0;}5.8在線題目求解例5.8.3生物進(jìn)化

在研究生物進(jìn)化時，常用一種類似樹狀分支的圖形來概括各種（類）生物之間的親緣關(guān)系。

這里采用有根樹描述生物之間的親緣關(guān)系。有根樹是具有方向的樹，選擇其中某個確定的結(jié)點，將其作為樹中所有物種的共同祖先（根）。有根樹這種結(jié)構(gòu)在計算機(jī)科學(xué)中極為常見，尤其適用表述層次結(jié)構(gòu)。下面就是在計算機(jī)科學(xué)中常見的有根樹的示意圖（注意：這里把樹根放在了圖的頂部，樹葉放在了底部）。

給定2種生物的種類，請判斷它們具有哪一個相同的祖先，當(dāng)然由于樹根一定滿足這個要求，可能的答案不唯一，這里只要求給出離這2種生物最近的祖先。

例如：對于左圖，2和3的最近祖先是10，而9和7的最近祖先是8，特別需要注意，10和11的最近祖先是10。5.8在線題目求解例5.8.3生物進(jìn)化輸入:

首先輸入一個整數(shù)T，表示測試數(shù)據(jù)的組數(shù)，然后是T組測試數(shù)據(jù)。每組測試數(shù)據(jù)第一行輸入一個整數(shù)n（2≤n≤1000），表示結(jié)點總數(shù)（結(jié)點編號從1到n），然后是n-1個整數(shù)對a、b（1≤a，b≤n，且a≠b），表示a是b的父結(jié)點（直接祖先）。請注意，n個結(jié)點（物種）的有根樹恰好具有n-1條邊。接下來是最多不超過1000次的詢問（各占一行），每個詢問包含2個互不相同的整數(shù)c、d（1≤c，d≤n），請你求解c、d的最近祖先。當(dāng)c、d同時為0時，表示本組測試結(jié)束。具體格式請參看輸入樣例。輸出:

對于每組測試，每次查詢輸出一行，包含一個整數(shù)，表示求得的最近祖先。5.8在線題目求解例5.8.3生物進(jìn)化輸入樣例:1523515254135100輸出樣例:55解析：在并查集的查操作中，需要從一個結(jié)點出發(fā)找到根結(jié)點，若在查找過程中把該結(jié)點及其祖先結(jié)點保存起來，則查找兩個結(jié)點的公共祖先很容易求得。因此，可以通過修改并查集的代碼求解本例。5.8在線題目求解例5.8.3生物進(jìn)化#include<iostream>usingnamespacestd;constintN=1001;

//數(shù)組長度，最大的結(jié)點數(shù)+1intP[N];

//存放父結(jié)點下標(biāo)，從1開始用voidInit(intn){

//初始化，每個結(jié)點作為一個集合

for(inti=1;i<=n;i++)

P[i]=i;}//在找x的根結(jié)點的過程中把x及其祖先逐個存放在a數(shù)組中，祖先個數(shù)用引用參數(shù)cnt返回voidFind(intx,inta[],int&cnt){

//查操作

while(P[x]!=x){

//尋找根結(jié)點,最終x就是該集合的根結(jié)點

a[cnt++]=x;

//x存放在a數(shù)組中

x=P[x];

//把x置為其父結(jié)點

}

a[cnt++]=x;

//把根結(jié)點存在a數(shù)組中}5.8在線題目求解例5.8.3生物進(jìn)化voidUnion(intx,inty){//并操作，依題意把x作為y的父結(jié)點

P[y]=x;

}intmain(){

intT;

cin>>T;

while(T--){

intn,i;

cin>>n;

Init(n);