第5章 樹和二叉樹-25春-250314

Email:lidongmei@李冬梅北京林業(yè)大學(xué)信息學(xué)院樹和二叉樹第5章數(shù)據(jù)結(jié)構(gòu)（C語言版）（第3版）線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹集合

——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系圖形結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖邏輯結(jié)構(gòu)樹結(jié)構(gòu)的應(yīng)用樹形結(jié)構(gòu)（非線性結(jié)構(gòu)）：結(jié)點(diǎn)之間有分支，具有層次關(guān)系掌握二叉樹的基本概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)熟練掌握二叉樹的前、中、后序遍歷方法了解線索化二叉樹的思想熟練掌握：哈夫曼樹的實(shí)現(xiàn)方法、構(gòu)造哈夫曼編碼的方法掌握：森林與二叉樹的轉(zhuǎn)換，樹的遍歷方法01OPTION02OPTION03OPTION04OPTION05OPTIONtarget目標(biāo)樹（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛洌╪

=

0）；或?yàn)榉强諛洌瑢?duì)于非空樹T：樹的定義12有且僅有一個(gè)稱之為根的結(jié)點(diǎn)；除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分為m（m＞0）個(gè)互不相交的有限集T1,T2,…,Tm,其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（SubTree）。樹是n個(gè)結(jié)點(diǎn)的有限集T1T2T3樹的定義凹入表示嵌套集合廣義表樹的其它表示方式有序樹無序樹——即根結(jié)點(diǎn)(沒有前驅(qū))——即終端結(jié)點(diǎn)(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個(gè)數(shù))——結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）——結(jié)點(diǎn)各子樹可互換位置。基本術(shù)語

根葉子

森林——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)雙親孩子兄弟堂兄弟祖先子孫基本術(shù)語線性結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素

無前驅(qū)最后一個(gè)數(shù)據(jù)元素

無后繼

其它數(shù)據(jù)元素

一個(gè)前驅(qū)，一個(gè)后繼樹形結(jié)構(gòu)和線性結(jié)構(gòu)的對(duì)比樹結(jié)構(gòu)根結(jié)點(diǎn)(只有一個(gè))無雙親葉子結(jié)點(diǎn)(可以有多個(gè))

無孩子其它結(jié)點(diǎn)一中間結(jié)點(diǎn)

一個(gè)雙親，多個(gè)孩子一對(duì)一一對(duì)多二叉樹（BinaryTree）是n（n≥0）個(gè)結(jié)點(diǎn)所構(gòu)成的集合，它或?yàn)榭諛洌╪

=

0）；或?yàn)榉强諛?，?duì)于非空樹T：二叉樹的定義（1）有且僅有一個(gè)稱之為根的結(jié)點(diǎn)；（2）除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)分為兩個(gè)互不相交的子集T1和T2，分別稱為T的左子樹和右子樹，且T1和T2本身又都是二叉樹。普通樹（多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實(shí)現(xiàn)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹？二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性。二叉樹的定義二叉樹基本特點(diǎn)：結(jié)點(diǎn)的度小于等于2有序樹（子樹有序，不能顛倒）二叉樹的五種不同形態(tài)二叉樹的定義具有3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？普通樹呢？

練習(xí)5種/2種目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 數(shù)據(jù)壓縮問題將數(shù)據(jù)文件轉(zhuǎn)換成由0、1組成的二進(jìn)制串，稱之為編碼字符編碼字符編碼字符編碼a00a0a0b01b10b01c10c110c010d11d111d111（a）等長(zhǎng)編碼方案（b）不等長(zhǎng)編碼方案1（c）不等長(zhǎng)編碼方案2利用二叉樹求解表達(dá)式的值以二叉樹表示表達(dá)式的遞歸定義如下：(a+b*(c-d)-e/f)的二叉樹（1）若表達(dá)式為數(shù)或簡(jiǎn)單變量，則相應(yīng)二叉樹中僅有一個(gè)根結(jié)點(diǎn)，其數(shù)據(jù)域存放該表達(dá)式信息；（2）若表達(dá)式為“第一操作數(shù)運(yùn)算符第二操作數(shù)”的形式，則相應(yīng)的二叉樹中以左子樹表示第一操作數(shù)，右子樹表示第二操作數(shù)，根結(jié)點(diǎn)的數(shù)據(jù)域存放運(yùn)算符（若為一元運(yùn)算符，則左子樹為空），其中，操作數(shù)本身又為表達(dá)式。目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 ADTBinaryTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于數(shù)據(jù)元素的說明④……//關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個(gè)二叉樹的抽象數(shù)據(jù)類型定義

CreateBiTree(&T,definition)

初始條件；definition給出二叉樹T的定義。

操作結(jié)果：按definition構(gòu)造二叉樹T。PreOrderTraverse(T)

初始條件：二叉樹T存在。

操作結(jié)果：先序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問一次。InOrderTraverse(T)

初始條件：二叉樹T存在。

操作結(jié)果：中序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問一次。PostOrderTraverse(T)

初始條件：二叉樹T存在。

操作結(jié)果：后序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問一次。二叉樹的抽象數(shù)據(jù)類型定義目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)性質(zhì)1:在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)提問：第i層上至少有

個(gè)結(jié)點(diǎn)？性質(zhì)2:深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)提問：深度為k時(shí)至少有

個(gè)結(jié)點(diǎn)？1k性質(zhì)3:對(duì)于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)n0必定為n2＋1（即n0=n2+1）二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。（特點(diǎn)：每層都“充滿”了結(jié)點(diǎn)）特殊形態(tài)的二叉樹完全二叉樹：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)只有最后一層葉子不滿，且全部集中在左邊思考這棵樹是滿二叉樹嗎？不是。葉子不在同一層上，且最后一層結(jié)點(diǎn)個(gè)數(shù)不滿。滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多。滿二叉樹在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多。思考是否是完全二叉樹？練習(xí)一棵完全二叉樹有5000個(gè)結(jié)點(diǎn)，可以計(jì)算出其葉結(jié)點(diǎn)的個(gè)數(shù)是（）。2500性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為[log2n]＋1k層nk-1層2k?1?1＜n≤2k?1或2k?1≤n＜2kk?1≤log2n＜k，因?yàn)閗是整數(shù)所以k=

log2n

+

1二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)性質(zhì)5:對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為i

的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1；其雙親的編號(hào)必為i/2。二叉樹的順序存儲(chǔ)實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素。DATAPARENTLCHILDRCHILD二叉樹的鏈?zhǔn)酱鎯?chǔ)ABCDEFG二叉鏈表typedefstruct

BiNode{

TElemTypedata;

struct

BiNode*lchild,*rchild;//左右孩子指針}BiNode,*BiTree;ABCDEFG^^^^^^^^分析：必有2n個(gè)鏈域。除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只會(huì)有n－1個(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)。空指針數(shù)目＝2n－(n-1)=n+1在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有

個(gè)空指針域練習(xí)ABCDEFG^^^^^^^^n+1

三叉鏈表ABCDEFGABCDEFG^^^^^^^^^lchilddataparentrchildtypedefstruct

TriTNode

{TelemTypedata;

struct

TriTNode

*lchild,*parent,*rchild;

}TriTNode,*TriTree;目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 遍歷二叉樹和線索二叉樹遍歷定義指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。遍歷用途它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。DLRDLRLDRLRDDRLRDLRLD遍歷規(guī)則先左后右先序遍歷：中序遍歷：后序遍歷：ABCDEABDECDBEACDEBCA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根遍歷規(guī)則+*A*/EDCB先序遍歷+**/ABCDE前綴表示中序遍歷A/B*C*D+E中綴表示后序遍歷AB/C*D*E+后綴表示層序遍歷+*E*D/CAB用二叉樹表示算術(shù)表達(dá)式DLRADLRDLR>B>>D>>CDLRADBC先序遍歷序列：ABDC若二叉樹為空，則空操作否則

訪問根結(jié)點(diǎn)(D)

前序遍歷左子樹(L)

前序遍歷右子樹(R)遍歷的算法實(shí)現(xiàn)－先序遍歷則三種遍歷算法可寫出:遍歷的算法實(shí)現(xiàn)－－用遞歸形式格外簡(jiǎn)單！longFactorial(longn){if(n==0)return1;//基本項(xiàng)

elsereturnn*Factorial(n-1);//歸納項(xiàng)}回憶:StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉樹

else{

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

PreOrderTraverse(T->lchild);//遞歸遍歷左子樹

PreOrderTraverse(T->rchild);//遞歸遍歷右子樹

}}

先序遍歷算法StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{

cout<<T->data;

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC遍歷的算法實(shí)現(xiàn)－中序遍歷若二叉樹為空，則空操作否則:

中序遍歷左子樹(L)

訪問根結(jié)點(diǎn)(D)

中序遍歷右子樹(R)ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDACStatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉樹

else{

InOrderTraverse(T->lchild);//遞歸遍歷左子樹

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

InOrderTraverse(T->rchild);//遞歸遍歷右子樹

}}

中序遍歷算法遍歷的算法實(shí)現(xiàn)－后序遍歷若二叉樹為空，則空操作否則

后序遍歷左子樹(L)

后序遍歷右子樹(R)

訪問根結(jié)點(diǎn)(D)ADBC

LRDLRDLRDA>>D>>CLRDB后序遍歷序列：DBCAStatusPostOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉樹

else{

PostOrderTraverse(T->lchild);//遞歸遍歷左子樹

PostOrderTraverse(T->rchild);//遞歸遍歷右子樹

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

}}

后序遍歷算法StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{

cout<<T->data;

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);}}

StatusPostOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

cout<<T->data;}}StatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{

InOrderTraverse(T->lchild);

cout<<T->data;

InOrderTraverse(T->rchild);}}遍歷算法的分析如果去掉輸出語句，從遞歸的角度看，三種算法是完全相同的，或說這三種算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過3次。AFEDCBG第1次經(jīng)過時(shí)訪問＝先序遍歷第2次經(jīng)過時(shí)訪問＝中序遍歷第3次經(jīng)過時(shí)訪問＝后序遍歷遍歷算法的分析AFEDCBG時(shí)間效率:O(n)

//每個(gè)結(jié)點(diǎn)只訪問一次空間效率:O(n)

//棧占用的最大輔助空間遍歷算法的分析AFEDCBG時(shí)間效率:O(n)

//每個(gè)結(jié)點(diǎn)只訪問一次空間效率:O(n)

//棧占用的最大輔助空間遍歷算法的分析建立一個(gè)棧；根結(jié)點(diǎn)進(jìn)棧，遍歷左子樹；根結(jié)點(diǎn)出棧，輸出根結(jié)點(diǎn)，遍歷右子樹。中序遍歷非遞歸算法（算法5.2）在中序遍歷過某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的根以及右子樹？中序遍歷非遞歸算法（算法5.2）StatusInOrderTraverse(BiTreeT){ BiTreep;InitStack(S);p=T; while(p||!StackEmpty(S)){ if(p){ Push(s,p);p=p->lchild; } else{ Pop(s,q); printf(“%c”,q->data);p=q->rchild;}} returnOK;}時(shí)間復(fù)雜度為O(n)ABCDEFGA^B^C^D^E^F^^G^按先序遍歷序列建立二叉樹的二叉鏈表

例：已知先序序列為：

ABCDEGF（動(dòng)態(tài)演示）二叉樹的建立（算法5.3）voidCreateBiTree(BiTree&T）{cin>>ch;if(ch==’#’)T=NULL; //遞歸結(jié)束，建空樹else{T=newBiTNode;T-＞data=ch; //生成根結(jié)點(diǎn)

CreateBiTree(T-＞lchild);//遞歸創(chuàng)建左子樹

CreateBiTree(T-＞rchild);//遞歸創(chuàng)建右子樹

} }

二叉樹的建立（算法5.3）時(shí)間復(fù)雜度為O(n)復(fù)制二叉樹二叉樹遍歷算法的應(yīng)用如果是空樹，遞歸結(jié)束；否則，申請(qǐng)新結(jié)點(diǎn)空間，復(fù)制根結(jié)點(diǎn)遞歸復(fù)制左子樹遞歸復(fù)制右子樹算法5.4

intCopy(BiTreeT,BiTree&NewT){if(T==NULL){//如果是空樹返回0NewT=NULL;return0;}else{NewT=newBiTNode;NewT->data=T->data;Copy(T->lChild,NewT->lchild);Copy(T->rChild,NewT->rchild);}}時(shí)間復(fù)雜度為O(n)計(jì)算二叉樹結(jié)點(diǎn)總數(shù)二叉樹遍歷算法的應(yīng)用如果是空樹，則結(jié)點(diǎn)個(gè)數(shù)為0；否則，結(jié)點(diǎn)個(gè)數(shù)為左子樹的結(jié)點(diǎn)個(gè)數(shù)+右子樹的結(jié)點(diǎn)個(gè)數(shù)再+1。算法5.6

intNodeCount(BiTreeT){if(T==NULL)return0; elsereturn

NodeCount(T->lchild)+NodeCount(T->rchild)+1;}時(shí)間復(fù)雜度為O(n)計(jì)算二叉樹葉子結(jié)點(diǎn)總數(shù)二叉樹遍歷算法的應(yīng)用如果是空樹，則葉子結(jié)點(diǎn)個(gè)數(shù)為0；否則，為左子樹的葉子結(jié)點(diǎn)個(gè)數(shù)+右子樹的葉子結(jié)點(diǎn)個(gè)數(shù)。？？？intLeadCount(BiTreeT){ if(T==NULL) //如果是空樹返回0 return0; if(T->lchild==NULL&&T->rchild==NULL) return1;//如果是葉子結(jié)點(diǎn)返回1 elsereturnLeafCount(T->lchild)+LeafCount(T->rchild);}計(jì)算二叉樹深度二叉樹遍歷算法的應(yīng)用如果是空樹，則深度為0；否則：遞歸計(jì)算左子樹的深度記為m遞歸計(jì)算右子樹的深度記為n深度則為m與n的較大者加1

重要結(jié)論若二叉樹中各結(jié)點(diǎn)的值均不相同，則：由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一確定一棵二叉樹。練習(xí)已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG

和DECBHGFA，請(qǐng)畫出這棵二叉樹。①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（A）；②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹子孫（BDCE），其右部必全部是右子樹子孫（FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。練習(xí)中序遍歷：BDCEAFHG

后序遍歷：DECBHGFAABBFF（BDCE）（FHG）ABF

（DCE）

（HG）CDEGH二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。思考線索化二叉樹在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域ABCDEFG^^^^^^^^普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從第一個(gè)結(jié)點(diǎn)開始就能很快“順藤摸瓜”而遍歷整個(gè)樹例如中序遍歷結(jié)果：BDCEAFHG，實(shí)際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子線索化二叉樹如何保存這類信息？線索化二叉樹兩種解決方法增加兩個(gè)域：fwd和bwd；利用空鏈域（n+1個(gè)空鏈域）線索化二叉樹兩種解決方法利用二叉鏈表中的空指針域：如果某個(gè)結(jié)點(diǎn)的左孩子為空，則將空的左孩子指針域改為指向其前驅(qū)；如果某結(jié)點(diǎn)的右孩子為空，則將空的右孩子指針域改為指向其后繼——這種改變指向的指針稱為“線索”加上了線索的二叉樹稱為線索二叉樹(ThreadedBinaryTree)對(duì)二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫線索化為了避免混淆，增加兩個(gè)標(biāo)志域lchildLTagdataRTagrchild線索化二叉樹若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；01OPTION若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。02OPTIONLTag:若LTag=0,lchild域指向左孩子；

若LTag=1,lchild域指向其前驅(qū)。RTag:若RTag=0,rchild域指向右孩子；

若RTag=1,rchild域指向其后繼。

lchildLTagdataRTagrchild線索化二叉樹ABCDEABDCET先序序列：ABCDE00001111^11

lchild

LTagdataRTag

rchild先序線索二叉樹LTag=0,lchild域指向左孩子

LTag=1,lchild域指向其前驅(qū)RTag=0,rchild域指向右孩子

RTag=1,rchild域指向其后繼

ABCDEABDCET中序序列：BCAED00001111^11^

lchild

LTagdataRTag

rchild中序線索二叉樹

lchild

LTagdataRTag

rchildABCDEABDCET后序序列：CBEDA0000111111^后序線索二叉樹線索化二叉樹的幾個(gè)術(shù)語線索化對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程線索二叉樹加上線索的二叉樹（圖形式樣）線索鏈表加上線索二叉鏈表線索指向結(jié)點(diǎn)前驅(qū)和后繼的指針畫出以下二叉樹對(duì)應(yīng)的中序線索二叉樹。該二叉樹中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,G練習(xí)ABCGEIDHFroot懸空？懸空？為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)對(duì)應(yīng)的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)如圖所示：注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G練習(xí)00A00C00B11E11F11G00D11I11H0--root0畫出與二叉樹對(duì)應(yīng)的中序線索二叉樹2825405560330854因?yàn)橹行虮闅v序列是：5540256028083354對(duì)應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。NILNIL練習(xí)目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 樹的存儲(chǔ)結(jié)構(gòu)－－二叉鏈表表示法typedefstruct

CSNode{

ElemTypedata;structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;樹與二叉樹的轉(zhuǎn)換（長(zhǎng)子長(zhǎng)兄）樹與二叉樹的轉(zhuǎn)換（右孩子變兄弟）森林與二叉樹的轉(zhuǎn)換（1）森林轉(zhuǎn)換成二叉樹方法--把每棵樹轉(zhuǎn)換為二叉樹；--第一棵二叉樹不動(dòng)，從第二棵樹開始，把后一棵樹的根結(jié)點(diǎn)作為前一棵樹的根結(jié)點(diǎn)的右孩子，用線連接起來。森林與二叉樹的轉(zhuǎn)換樹的存儲(chǔ)結(jié)構(gòu)－－二叉鏈表表示法

樹

二叉樹

對(duì)應(yīng)

存儲(chǔ)

存儲(chǔ)

解釋

解釋樹與森林的遍歷

樹樹的遍歷先根遍歷：若樹不空，則先訪問根結(jié)點(diǎn)，依次先根遍歷各棵子樹。后根遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。按層次遍歷：若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。

先根遍歷：ABCDE后根遍歷：BDCEA層次遍歷：ABCED樹與森林的遍歷森林的遍歷--先序遍歷若森林不空，則：訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林。即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行先根遍歷。樹與森林的遍歷森林的遍歷--中序遍歷若森林不空，則：中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林。即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行后根遍歷。目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 游戲中主角的生命值d，有這樣的條件判定：當(dāng)怪物碰到主角后，怪物的反應(yīng)遵從下規(guī)則:哈夫曼樹及其應(yīng)用

if(d<100)state=嘲笑，單挑;

elseif(d<200)state=單挑;

elseif(d<300)state=嗜血魔法;

elseif(d<500)state=呼喚同伴;

elsestate=逃跑;哈夫曼樹及其應(yīng)用分析主角生命值d的特點(diǎn)，即預(yù)測(cè)出每種條件占總條件的百分比，將這些比值作為權(quán)值來構(gòu)造最優(yōu)二叉樹（哈夫曼樹），作為判定樹來設(shè)定算法。提高效率哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用if(d>=200)&&(d<300)state=嗜血魔法;

elseif(d>=300)&&(d<500)state=呼喚同伴;

elseif(d>=100)&&(d<200)state=單挑;

elseif(d<100)state=嘲笑，單挑;

elsestate=逃跑;if(d<100)state=嘲笑，單挑;

elseif(d<200)state=單挑;

elseif(d<300)state=嗜血魔法;

elseif(d<500)state=呼喚同伴;

elsestate=逃跑;在遠(yuǎn)程通訊中，要將待傳字符轉(zhuǎn)換成二進(jìn)制的字符串，怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？ABACCDA000110010101100000011010哈夫曼樹應(yīng)用實(shí)例－－哈夫曼編碼出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼關(guān)鍵：要設(shè)計(jì)長(zhǎng)度不等的編碼，則必須使任一字符的編碼都不是另一個(gè)字符的編碼的前綴－前綴編碼

0000AAAAABABB重碼ABACCDA000011010哈夫曼樹應(yīng)用實(shí)例－－哈夫曼編碼哈夫曼樹應(yīng)用實(shí)例－－哈夫曼編碼ACBD000111采用二叉樹設(shè)計(jì)前綴編碼左分支用“0”右分支用“1”A—0B—110C—10D—111

0110010101110ABACCDA分解接收字符串：遇“0”向左，遇“1”向右；一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符，反復(fù)由根出發(fā)，直到譯碼完成。0110010101110ACBD000111ABACCDA特點(diǎn)：每一碼都不是另一碼的前綴，絕不會(huì)錯(cuò)譯!稱為前綴碼哈夫曼編碼的譯碼過程哈夫曼樹的構(gòu)造debacfg路徑01由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑長(zhǎng)度02路徑上的分支數(shù)目a→e的路徑長(zhǎng)度＝2樹的帶權(quán)路徑長(zhǎng)度04樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和WPL=

wklk

k=1n帶權(quán)路徑長(zhǎng)度03結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積哈夫曼樹05帶權(quán)路徑長(zhǎng)度最小的樹dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*2+5*2+2*2+4*2=36權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹哈夫曼樹的構(gòu)造滿二叉樹不一定是哈夫曼樹哈夫曼樹中權(quán)越大的葉子離根越近具有相同帶權(quán)結(jié)點(diǎn)的哈夫曼樹不唯一a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4哈夫曼樹的構(gòu)造過程操作要點(diǎn)：對(duì)權(quán)值的合并、刪除與替換，總是合并當(dāng)前值最小的兩個(gè)基本思想：使權(quán)大的結(jié)點(diǎn)靠近根基本思想：概率大的字符用短碼，小的用長(zhǎng)碼，構(gòu)造哈夫曼樹哈夫曼編碼的構(gòu)造例：某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，其出現(xiàn)頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。148464220001113301TBACST

00B

01A

10C

110S

111例5.2根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹。在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中。重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。哈夫曼樹的構(gòu)造過程typedefstruct{intweght;intparent,lch,rch;}*HuffmanTree;哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)（算法5.10）采用順序存儲(chǔ)結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組結(jié)點(diǎn)類型定義一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹有

個(gè)結(jié)點(diǎn)2n-1初始化HT[1..2n-1]：lch=rch=parent=0哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)01OPTION02OPTION進(jìn)行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1在HT[1..i-1]中選兩個(gè)未被選過的weight最小的兩個(gè)結(jié)點(diǎn)HT[s1]和HT[s2](從parent=0的結(jié)點(diǎn)中選)修改HT[s1]和HT[s2]的parent值：parent=i置HT[i].weight=HT[s1].weight+HT[s2].weight，lch=s1,rch=s2例:設(shè)n=4,w={70,50,20,40}試設(shè)計(jì)huffmancode(m=2*4-1=7)哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)a70b50c20d40weightparentlchrch170000250000320000440000567weightparentlchrch17070025060032050044050056063461107257180016例:設(shè)n=4,w={70,50,20,40}試設(shè)計(jì)huffmancode(m=2*4-1=7)哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)a70b50c20d40weightparentlchrch170000250000320000440000567weightparentlchrch17000025000032050044050056003460007000例:設(shè)n=4,w={70,50,20,40}試設(shè)計(jì)huffmancode(m=2*4-1=7)哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)a70b50c20d40weightparentlchrch170000250000320000440000567weightparentlchrch17000025060032050044050056063461100257000例:設(shè)n=4,w={70,50,20,40}試設(shè)計(jì)huffmancode(m=2*4-1=7)哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)a70b50c20d40weightparentlchrch170000250000320000440000567weightparentlchrch17070025060032050044050056063461107257180016weightparentlchrch170000250000320000440000567哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)voidCreatHuffmanTree(HuffmanTree

HT,intn){if(n<=1)return;m=2*n-1;HT=newHTNode[m+1];//0號(hào)單元未用，HT[m]表示根結(jié)點(diǎn)

for(i=1;i<=m;++i){HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}for(i=1;i<=n;++i)cin>>HT[i].weight;

哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);//選擇兩個(gè)其雙親域?yàn)?，且權(quán)值最小的結(jié)點(diǎn)，并返回它們?cè)贖T中的序號(hào)s1和s2HT[s1].parent=i;HT[s2].parent=i;//表示從F中刪除s1,s2HT[i].lch=s1;HT[i].rch=s2;//s1,s2分別作為i的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//i的權(quán)值為左右孩子權(quán)值之和}}

weightparentlchrch17000025000032050044050056003460007000時(shí)間復(fù)雜度為O(n2)例:設(shè)n=8,w={5,29,7,8,14,23,3,11}試設(shè)計(jì)huffmancode(m=2*8-1=15)哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)

weightparentlch

rch1．．．８９．．15529781423311000000000000000000000000000000000000000000000構(gòu)造Huffmantree后,HT為:哈夫曼樹構(gòu)造算法的實(shí)現(xiàn)WeightParentLchrch1．．．８９．．155297814233119141010121391100000000000000008151929425810011

12

13

14

15

15

013856274910

11

12

1413哈夫曼編碼構(gòu)造算法的實(shí)現(xiàn)哈夫曼編碼構(gòu)造算法的實(shí)現(xiàn)a70b50c20d40a

0b

10c

110d

111for(i=1;i<=n;++i){ //逐個(gè)字符求哈夫曼編碼

start=n-1;c=i;f=HT[i].parent; while(f!=0){ //從葉子結(jié)點(diǎn)開始向上回溯，直到根結(jié)點(diǎn)

--start; //回溯一次start向前指一個(gè)位置

if(HT[f].lchild==c)cd[start]=’0’; //結(jié)點(diǎn)c是f的左孩子，則生成代碼0elsecd[start]=’1’; //結(jié)點(diǎn)c是f的右孩子，則生成代碼1c=f;f=HT[f].parent; //繼續(xù)向上回溯

} //求出第i個(gè)字符的編碼weightparentlchrch17070025060032050044050056063461107257180016voidCreatHuffmanCode(HuffmanTreeHT,HuffmanCode&HC,intn){//從葉子到根逆向求每個(gè)字符的赫夫曼編碼，存儲(chǔ)在編碼表HC中HC=newchar*[n+1]; //分配n個(gè)字符編碼的頭指針向量cd=newchar[n]; //分配臨時(shí)存放編碼的動(dòng)態(tài)數(shù)組空間cd[n-1]=’\0’; //編碼結(jié)束符for(i=1;i<=n;++i){ //逐個(gè)字符求哈夫曼編碼

start=n-1;c=i;f=HT[i].parent; while(f!=0){ //從葉子結(jié)點(diǎn)開始向上回溯，直到根結(jié)點(diǎn)

--start; //回溯一次start向前指一個(gè)位置

if(HT[f].lchild==c)cd[start]=’0’; //結(jié)點(diǎn)c是f的左孩子，則生成代碼0elsecd[start]=’1’; //結(jié)點(diǎn)c是f的右孩子，則生成代碼1c=f;f=HT[f].parent; //繼續(xù)向上回溯

} //求出第i個(gè)字符的編碼

HC[i]=newchar[n-start]; //為第i

個(gè)字符編碼分配空間

strcpy(HC[i],&cd[start])；//將求得的編碼從臨時(shí)空間cd復(fù)制到HC的當(dāng)前行中

}deletecd; //釋放臨時(shí)空間}//CreatHuffanCode哈夫曼編碼構(gòu)造算法的實(shí)現(xiàn)時(shí)間復(fù)雜度為O(n2)哈夫曼編碼是不等長(zhǎng)編碼。哈夫曼編碼是前綴編碼，即任一字符的編碼都不是另一字符編碼的前綴。哈夫曼編碼樹中沒有度為1的結(jié)點(diǎn)。若葉子結(jié)點(diǎn)的個(gè)數(shù)為n，則哈夫曼編碼樹的結(jié)點(diǎn)總數(shù)為2n-1。發(fā)送過程：根據(jù)由哈夫曼樹得到的編碼表送出字符數(shù)據(jù)接收過程：按左0、右1的規(guī)定，從根結(jié)點(diǎn)走到一個(gè)葉結(jié)點(diǎn)，完成一個(gè)字符的譯碼。反復(fù)此過程，直到接收數(shù)據(jù)結(jié)束。哈夫曼編碼的幾點(diǎn)結(jié)論哈夫曼樹的前沿知識(shí)應(yīng)用—Word2Vec隱藏層到輸出層的映射就是通過哈夫曼樹的向下搜索逐步完成的哈夫曼樹的所有內(nèi)部結(jié)點(diǎn)類似神經(jīng)網(wǎng)絡(luò)隱藏層的神經(jīng)元詞典確定情況下，通過詞頻構(gòu)建哈夫曼樹，并獲得每個(gè)詞的哈夫曼編碼。葉節(jié)點(diǎn)的每個(gè)詞對(duì)應(yīng)一個(gè)唯一編碼，左子樹為1，右子樹為0。其實(shí)就是用多個(gè)獨(dú)立的二分類代替了softmax的作用，假設(shè)原來softmax計(jì)算量為V，變成了Log2V。高頻詞靠近根結(jié)點(diǎn)，可以用更少的時(shí)間找到。chatGPT內(nèi)部原理之TransformerVaswaniA,ShazeerN,ParmarN,etal.Attentionisallyouneed[J].Advancesinneuralinformationprocessingsystems,2017,30.chatGPT內(nèi)部原理之TransformerVaswaniA,ShazeerN,ParmarN,etal.Attentionisallyouneed[J].Advancesinneuralinformationprocessingsystems,2017,30.chatGPT內(nèi)部原理之TransformerchatGPT內(nèi)部原理之TransformerTheanimaldidn’tcrossthestreetbecauseitwastootiredTheanimaldidn’tcrossthestreetbecauseitwastoonarrow目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 在一些問題中，需將n個(gè)不同的元素劃分為若干個(gè)不相交的集合。初始時(shí)，每個(gè)元素各自構(gòu)成一個(gè)單獨(dú)的集合，然后按照特定規(guī)則，將屬于同一組元素的集合合并。其間要反復(fù)執(zhí)行查找和合并兩種關(guān)鍵操作。并查集的定義適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集。查找（Find)：用于確定某一元素所屬的集合合并（Union）:將一個(gè)集合并入另一個(gè)集合并查集的定義并查集（Union-findSet），亦稱為不相交集合，核心在于動(dòng)態(tài)維護(hù)元素的歸屬關(guān)系。支持查找和合并兩種關(guān)鍵操作，采用樹結(jié)構(gòu)表示元素及其所屬子集的關(guān)系。并查集的定義

并查集的應(yīng)用例如，判斷10個(gè)人(編號(hào)0-9)之間是否存在親戚關(guān)系。已知1與2、5與6、3與4、1與4、5與8之間存在親戚關(guān)系，判斷2與3之間是否存在親戚關(guān)系。輸入關(guān)系集合初始狀態(tài){0},{1},{2},{3},{4},{5},{6},{7},{8},{9}12{0},{1,2},{3},{4},{5},{6},{7},{8},{9}56{0},{1,2},{3},{4},{5,6},{7},{8},{9}34{0},{1,2},{3,4},{5,6},{7},{8},{9}14{0},{1,2,3,4},{5,6},{7},{8},{9}58{0},{1,2,3,4},{5,6,8},{7},{9}并查集的實(shí)現(xiàn)并查集實(shí)現(xiàn)方法有多種:數(shù)組、鏈表或樹等。樹的雙親表示法是一種常用的并查集實(shí)現(xiàn)方法。樹的雙親表示法將每個(gè)集合表示為一棵樹，樹的每個(gè)結(jié)點(diǎn)代表集合中的一個(gè)單元素，而所有集合的全集合則構(gòu)成一個(gè)森林。并查集的實(shí)現(xiàn)初始化：每個(gè)元素構(gòu)成一個(gè)單獨(dú)的集合，每個(gè)元素的父結(jié)點(diǎn)指針指向自身（即-1）。voidInit_UFSet(intUFSet[],

intsize){//初始化并查集for(inti=0;i<size;i++)UFSet[i]=-1;//每個(gè)由單個(gè)元素組成的集合}時(shí)間復(fù)雜度為O(n)并查集的實(shí)現(xiàn)查找：從待查元素x出發(fā)，沿著雙親指針向上查找，直到找到根結(jié)點(diǎn)（雙親指針為負(fù)值的結(jié)點(diǎn)）。intFind_UFSet(intUFSet[],

intx){//查找元素x所屬的集合while(UFSet[x]>=0)//循環(huán)尋找元素x的根x=UFSet[x];returnx;}查找結(jié)點(diǎn)2時(shí)間復(fù)雜度為O(n)并查集的實(shí)現(xiàn)合并：利用查找操作分別找到兩個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)Root1和Root2，若兩個(gè)結(jié)點(diǎn)不屬于同一集合，則將根結(jié)點(diǎn)Root2鏈接到另一個(gè)根結(jié)點(diǎn)Root1下。voidUnion_UFSet(intUFSet[],

intRoot1,intRoot2){//將兩個(gè)子集合并Root1=Find_UFSet(UFSet,

Root1);Root2=Find_UFSet(UFSet,

Root2);if(Root1==Root2)return;else{UFSet[Root1]+=UFSet[Root2];

UFSet[Root2]=Root1;//將根Root2鏈接到另一根Root1下面}}時(shí)間復(fù)雜度為O(n)并查集的實(shí)現(xiàn)合并結(jié)點(diǎn)1和3合并：利用查找操作分別找到兩個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)Root1和Root2，若兩個(gè)結(jié)點(diǎn)不屬于同一集合，則將根結(jié)點(diǎn)Root2鏈接到另一個(gè)根結(jié)點(diǎn)Root1下。并查集的實(shí)現(xiàn)

并查集的實(shí)現(xiàn)并查集的優(yōu)化：路徑壓縮是一種優(yōu)化方法，將查找路徑上的結(jié)點(diǎn)直接指向根結(jié)點(diǎn)，降低樹的深度，提高查找效率。intCompressionFind(intUFSet[],intx){//遞歸實(shí)現(xiàn)路徑壓縮if(UFSet[x]＜0)//找到根結(jié)點(diǎn)returnx;returnUFSet[x]=CompressionFind(UFSet,UFSet[x]);//路徑壓縮，提高查找效率}時(shí)間復(fù)雜度為O(n)并查集的實(shí)現(xiàn)優(yōu)化查找結(jié)點(diǎn)3并查集的優(yōu)化：路徑壓縮是一種優(yōu)化方法，將查找路徑上的結(jié)點(diǎn)直接指向根結(jié)點(diǎn)，降低樹的深度，提高查找效率。并查集的實(shí)現(xiàn)路徑壓縮后的樹

目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 利用二叉樹求解表達(dá)式的值運(yùn)算符棧OPTR，來暫存已經(jīng)掃描到的還未處理的運(yùn)算符。每?jī)蓚€(gè)操作數(shù)和一個(gè)運(yùn)算符就可以建立一棵表達(dá)式二叉樹，而該二叉樹又可以作為另一個(gè)運(yùn)算符結(jié)點(diǎn)的一棵子樹。表達(dá)式樹棧EXPT，來暫存已建立好的表達(dá)式樹的根結(jié)點(diǎn)，以便其作為另一個(gè)運(yùn)算符結(jié)點(diǎn)的子樹而被引用。表達(dá)式樹的創(chuàng)建---【算法步驟】①初始化OPTR棧和EXPT棧，“#”壓入OPTR棧。②

讀入第一個(gè)字符ch，如果表達(dá)式?jīng)]有掃描完畢至“#”或OPTR的棧頂元素不為“#”時(shí)，則循環(huán)執(zhí)行以下操作：若ch不是運(yùn)算符，則以ch為根創(chuàng)建一棵只有根結(jié)點(diǎn)的樹，且將該樹根結(jié)點(diǎn)壓入EXPT棧，讀入下一字符ch；若ch是運(yùn)算符，則根據(jù)OPTR的棧頂元素和ch的優(yōu)先級(jí)比較結(jié)果，做不同的處理：利用二叉樹求解表達(dá)式的值小于，則ch壓OPTR棧，讀入下一字符ch；大于，則彈出OPTR棧頂運(yùn)算符，從EXPT棧彈出兩個(gè)表達(dá)式子樹的根結(jié)點(diǎn)，以該運(yùn)算符為根結(jié)點(diǎn)，以EXPT棧中彈出的第二個(gè)子樹作為左子樹，以EXPT棧中彈出的第一個(gè)子樹作為右子樹，創(chuàng)建一棵新二叉樹，并將該樹根結(jié)點(diǎn)壓入EXPT棧；等于，則OPTR的棧頂元素是“(”且ch是“)”，這時(shí)彈出OPTR棧頂?shù)摹?”，括號(hào)匹配成功，讀入下一字符ch。利用二叉樹求解表達(dá)式的值利用二叉樹求解表達(dá)式的值voidCreateExpTree(BiTree&T,BiTreea,BiTreeb,charch){T=newBiTNode; T->data=ch; T->lchild=a;T->rchild=b;}時(shí)間復(fù)雜度為O(n)①設(shè)lvalue和rvalue記錄左子樹和右子樹的值，初始均為0。②

如果當(dāng)前結(jié)點(diǎn)為葉子（結(jié)點(diǎn)為操作數(shù)），則返回該結(jié)點(diǎn)的數(shù)值，否則（結(jié)點(diǎn)為運(yùn)算符）執(zhí)行以下操作：遞歸計(jì)算左子樹的值記為lvalue；遞歸計(jì)算右子樹的值記為rvalue；根據(jù)當(dāng)前結(jié)點(diǎn)運(yùn)算符的類型，將lvalue和rvalue進(jìn)行相應(yīng)運(yùn)算并返回。利用二叉樹求解表達(dá)式的值-算法步驟利用二叉樹求解表達(dá)式的值時(shí)間復(fù)雜度為O(n)目錄導(dǎo)航Contents5.15.25.35.45.55.65.75.85.95.10樹和二叉樹的定義案例引入樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林哈夫曼樹及其應(yīng)用并查集及其應(yīng)用案例分析與實(shí)現(xiàn)LeetCode算法練習(xí)題 【算法練習(xí)題5.1】LeetCode872葉子相似的樹【問題描述】給定兩棵根結(jié)點(diǎn)分別為root1和root2的樹，判斷兩棵樹是否葉相似，如果是，則返回true，否則返回false。葉相似是指兩棵二叉樹的葉值序列相同，葉值序列為一棵二叉樹上所有葉子從左向右順序排列形成的序列。例如，右圖所示二叉樹的葉值序列為(6,7,4,9,8)?！舅惴ň毩?xí)題5.1】LeetCode872葉子相似的樹【輸入輸出示例】輸入：root1=[3,5,1,6,2,9,8,NULL,NULL,7,4]root2=[3,5,1,6,7,4,2,NULL,NULL,NULL,NULL,NULL,NULL,9,8]根結(jié)點(diǎn)分別root1和root2的二叉樹右圖所示。輸出：true【算法練習(xí)題5.1】LeetCode872葉子相似的樹【問題分析】判斷兩棵樹是否為空，若為空，則返回true。否則利用先序遍歷方法遍歷二叉樹，分別得到兩棵二叉樹的葉值序列，然后判斷兩棵樹的葉值序列是否相同。若不相等，則兩棵二叉樹一定不是葉相似的。若相等，則遍歷兩個(gè)葉值序列，判斷其中的值是否完全相同，以判定兩棵二叉樹是否葉相似?！舅惴ň毩?xí)題5.1】LeetCode872葉子相似的樹

【算法描述】【算法練習(xí)題5.1】LeetCode