數據結構六樹

1、第六章 樹和二叉樹 樹是一類重要的非線性數據結構，是以分支關系定義的層次結構6.1 樹的定義定義定義：樹(tree)是n(n0)個結點的有限集T，其中：有且僅有一個特定的結點，稱為樹的根(root)當n1時，其余結點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：樹中至少有一個結點根樹中各子樹是互不相交的集合A只有根結點的樹ABCDEFGHIJKLM有子樹的樹根子樹基本術語結點(node)表示樹中的元素，包括數據項及若干指向其子樹的分支結點的度(degree)結點擁有的子樹數葉子(leaf)度為0的結點孩子(child)結點

2、子樹的根稱為該結點的孩子雙親(parents)孩子結點的上層結點叫該結點的兄弟(sibling)同一雙親的孩子樹的度一棵樹中最大的結點度數結點的層次(level)從根結點算起，根為第一層，它的孩子為第二層深度(depth)樹中結點的最大層次數森林(forest)m(m0)棵互不相交的樹的集合ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F，G，M，I，J結點A的孩子：B，C，D結點B的孩子：E，F結點I的雙親：D結點L的雙親：E結點B，C，D為兄弟結點K，L為兄弟樹的度：3結點A的層次：1結點M的層次：4樹的深度：4結點F，G為堂兄弟結點A是結點F，G的祖先

3、6.2 二叉樹定義定義：二叉樹是n(n0)個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成特點每個結點至多有二棵子樹(即不存在度大于2的結點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結點的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空二叉樹性質性質1：) 1(21iii個結點層上至多有在二叉樹的第證明：用歸納法證明之 i=1時，只有一個根結點， 是對的 假設對所有j(1j1，則其雙親是i/2l (2) 如果2in，則結點i無左孩子；如果2in，則其左孩子是2il (3) 如果2i+1n，則結點i無右孩

4、子；如果2i+1n，則其右孩子是2i+11log2nn深度為個結點的完全二叉樹的具有l(wèi)性質l性質4：6.3 樹的存儲結構樹的存儲結構雙親表示法實現：定義結構數組存放樹的結點，每個結點含兩個域：數據域：存放結點本身信息雙親域：指示本結點的雙親結點在數組中位置特點：找雙親容易，找孩子難typedef struct node datatype data; int parent;JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0號單元不用或存結點個數如何找孩子結點v孩子表示法v多重鏈表：每個結點有多個指針域，分別指向其子樹的根v結點同

5、構：結點的指針個數相等，為樹的度Dv結點不同構：結點指針個數不等，為該結點的度ddata child1 child2 . childDdata degree child1 child2 . childdl孩子鏈表：每個結點的孩子結點用單鏈表存儲，再用含n個元素的結構數組指向每個孩子鏈表孩子結點：typedef struct node int child; /該結點在表頭數組中下標 struct node *next; /指向下一孩子結點 JD;表頭結點：typedef struct tnode datatype data; /數據域 struct node *fc; /指向第一個孩子結點 TD

6、; TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結點l帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiv孩子兄弟表示法（二叉樹表示法）v實現：用二叉鏈表作樹的存儲結構，鏈表中每個結點的兩個指針域分別指向其第一個孩子結點和下一個兄弟結點v特點v操作容易v破壞了樹的層次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a

7、b c d e f g h i二叉樹的存儲結構順序存儲結構實現：按滿二叉樹的結點層次編號，依次存放二叉樹中的數據元素特點：結點間關系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v鏈式存儲結構v二叉鏈表typedef struct BiTNode datatype data; struct BiTNode *lchild, *rchild; BiTNode; * BiTree;lchild data rchild ABCDEFG在n個結點的二叉鏈表中，有n+1個空指針域 AB C D

8、 E F Gl三叉鏈表typedef struct TriTNode datatype data; struct node *lchild, *rchild, *parent; TriTNode, TriTree;lchild data parent rchildABCDEFG A B C D E F G樹與二叉樹轉換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對應存儲存儲解釋解釋v將樹轉換成二叉樹v加線：在兄弟之間加一連線v抹線：對每個結點，除了其左孩子外，去除其與其余孩子之間的關系v旋轉：以樹的根結點為軸心，將整樹順時針轉45ABCDEFGHI

9、ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉換成的二叉樹其右子樹一定為空v將二叉樹轉換成樹v加線：若p結點是雙親結點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來v抹線：抹掉原二叉樹中雙親與右孩子之間的連線v調整：將結點按層次排列，形成樹結構ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIv森林轉換成二叉樹v將各棵樹分別轉換成二叉樹v將每棵樹的根結點用線相連v以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹型結構ABCDEFGHIJABCDEFGHIJABC

10、DEFGHIJABCDEFGHIJv二叉樹轉換成森林v抹線：將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹v還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6.4 樹和二叉樹的遍歷樹的遍歷遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結點的一個線性排列常用方法先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二層，第n層

11、的結點ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO二叉樹的遍歷方法先序遍歷：先訪問根結點,然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結點按層次遍歷：從上到下、從左到右訪問各結點DLRLDR、LRD、DLRRDL、RLD、DRL-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：- + a * b - c d / e f-+a*b-cd/

12、ef- +a *b - c d/e f-+a*b-c d/e fADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:算法的遞歸定義是：算法的遞歸定義是：若二叉樹為空，則遍歷結束；否則若二叉樹為空，則遍歷結束；否則 中序遍歷左子樹中序遍歷左子樹(遞歸調用本算法遞歸調用本算法)； 訪問根結點；訪問根結點； 中序遍歷右子樹中序遍歷右子樹(遞歸調用本算法遞歸調用本算法)。v中序遍歷的遞歸算法中序遍歷的遞歸算法void InorderTraverse(BTNode *T) if (T!=NULL) InorderTraverse(T-Lchild) ;visit

13、(T-data) ; /* 訪問根結點訪問根結點 */InorderTraverse(T-Rchild) ; 中序遍歷非遞歸算法思路：中序遍歷非遞歸算法思路：設設T是指向二叉樹根結點的指針是指向二叉樹根結點的指針變量，非遞歸算法是：變量，非遞歸算法是：若二叉樹為空，則返回；否則，若二叉樹為空，則返回；否則，令令p=T 若若p不為空，不為空，p進棧，進棧， p=p-Lchild ； 否則否則(即即p為空為空)，退棧到，退棧到p，訪，訪問問p所指向的結點；所指向的結點； p=p-Rchild ，轉，轉(1)；直到?？諡橹埂Ｖ钡綏？諡橹?。中序遍歷的非遞歸算法：中序遍歷的非遞歸算法：#define M

14、AX_NODE 50void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走向左走到底到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 訪問結點，向右一步訪問結點，向右一步 /while; l中序遍歷的非遞歸算法執(zhí)行過程中序遍歷的非遞歸算法執(zhí)行過程ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABC

15、DEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：C(4)pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：C B E Gp(10)ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)

16、ABCDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪問：C B E G D F Ap=NULL(15)ADBCD L RAD L RD L RBDCD L R算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則遍歷結束；否則若二叉樹為空，則遍歷結束；否則 訪問根結點；訪問根結點； 先序遍歷左子樹先序遍歷左子樹(遞歸調用本算法遞歸調用本算法)； 先序遍歷右子樹先序遍歷右子樹(遞歸調用本算法遞歸調用本算法)。先序遍歷:先序遍歷序列：A B D Cv先序遍歷的遞歸算法先序遍歷的遞歸算法void PreorderTraverse(BTNode *T) if (T!=NULL)

17、 visit(T-data) ; /* 訪問根結點訪問根結點 */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 說明：說明：visit()函數是訪問結點的數據域，其要求視具體問題而定。樹采函數是訪問結點的數據域，其要求視具體問題而定。樹采用二叉鏈表的存儲結構，用指針變量用二叉鏈表的存儲結構，用指針變量T來指向。來指向。void PreorderTraverse(BTNode *T) if (T!=NULL) printf(%dt,bt-data);/* 訪問根結點訪問根結點 */PreorderTraverse(T-Lchil

18、d) ;PreorderTraverse(T-Rchild) ; 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C先序遍歷的非遞歸算法先序遍歷的非遞歸算法設設T是指向二叉樹根結點的指針是指向二叉樹根結點的指針變量，非遞歸算法是：變量，非遞歸算法是：若二叉樹為空

19、，則返回；否則，若二叉樹為空，則返回；否則，令令p=T； 訪問訪問p所指向的結點；所指向的結點； q=p-Rchild ，若，若q不為空，不為空，則則q進棧；進棧； p=p-Lchild ，若，若p不為空，不為空，轉轉(1)，否則轉，否則轉(4)； 退棧到退棧到p ，轉，轉(1)，直到?？眨钡綏？諡橹埂橹?。先序遍歷的非遞歸算法先序遍歷的非遞歸算法void PreorderTraverse( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) visit( p- data ) ; q=p-Rchild ; if ( q!=NULL

20、 ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /while中序遍歷的非遞歸算法：中序遍歷的非遞歸算法：void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走到底向左走到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 訪問結點，訪問結點，向右一步向右一步 /wh

21、ile ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:B算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則遍歷結束；否則若二叉樹為空，則遍歷結束；否則 后序遍歷左子樹后序遍歷左子樹(遞歸調用本算法遞歸調用本算法)； 后序遍歷右子樹后序遍歷右子樹(遞歸調用本算法遞歸調用本算法) ； 訪問根結點訪問根結點 。v后序遍歷的遞歸算法后序遍歷的遞歸算法void PostorderTraverse(BTNode *T) if (T!=NULL) PostorderTraverse(T-Lchild) ;PostorderTraverse(T-Rchil

22、d) ; visit(T-data) ; /* 訪問根結點訪問根結點 */ 遍歷二叉樹的算法中基本操作是訪問結點，因遍歷二叉樹的算法中基本操作是訪問結點，因此，無論是哪種次序的遍歷，對有此，無論是哪種次序的遍歷，對有n個結點的二叉?zhèn)€結點的二叉樹，其時間復雜度均為樹，其時間復雜度均為O(n) 。后序遍歷的非遞歸算法后序遍歷的非遞歸算法 在后序遍歷中，根結點是最在后序遍歷中，根結點是最后被訪問的。因此，在遍歷過程后被訪問的。因此，在遍歷過程中，當搜索指針指向某一根結點中，當搜索指針指向某一根結點時，不能立即訪問，而要先遍歷時，不能立即訪問，而要先遍歷其左子樹，此時根結點進棧。當其左子樹，此時根結點

23、進棧。當其左子樹遍歷完后再搜索到該根其左子樹遍歷完后再搜索到該根結點時，還是不能訪問，還需遍結點時，還是不能訪問，還需遍歷其右子樹。所以，此根結點還歷其右子樹。所以，此根結點還需再次進棧，當其右子樹遍歷完需再次進棧，當其右子樹遍歷完后再退棧到到該根結點時，才能后再退棧到到該根結點時，才能被訪問。被訪問。 因此，設立一個狀態(tài)標志變因此，設立一個狀態(tài)標志變量量tag ：0 ： 結點暫不能訪問結點暫不能訪問1 ： 結點可以被訪問結點可以被訪問tag= 其次，設兩個堆棧S1、S2 ，S1保存結點，S2保存結點的狀態(tài)標志變量tag 。S1和S2共用一個棧頂指針。 設T是指向根結點的指針變量，非遞歸算法是

24、：若二叉樹為空，則返回；否則，令p=T； 第一次經過根結點p，不訪問： p進棧S1 ， tag 賦值0，進棧S2，p=p-Lchild 。 若p不為空，轉(1)，否則，取狀態(tài)標志值tag ： 若tag=0：對棧S1，不訪問，不出棧；修改S2棧頂元素值(tag賦值1) ，取S1棧頂元素的右子樹，即p=S1top-Rchild ，轉(1)； 若tag=1：S1退棧，訪問該結點；直到?？諡橹?。算法實現：算法實現：#define MAX_NODE 50void PostorderTraverse( BTNode *T) BTNode *S1MAX_NODE ,*p=T ;int S2MAX_NODE

25、, top=0 , bool=1 ;if (T=NULL) printf(“Binary Tree is Empty!n”) ;else do while (p!=NULL) S1+top=p ; S2top=0 ; p=p-Lchild ; if (top=0) bool=0 ; else if (S2top=0) p=S1top-Rchild ; S2top=1 ; else p=S1top ; top- ; visit( p-data ) ; p=NULL ; /* 使循環(huán)繼續(xù)進行而不至于死使循環(huán)繼續(xù)進行而不至于死循環(huán)循環(huán) */ while (bool!=0) ;層次遍歷二叉樹層次遍歷二

26、叉樹 層次遍歷二叉樹，是從根結點開始遍歷，按層次次層次遍歷二叉樹，是從根結點開始遍歷，按層次次序序“自上而下，從左至右自上而下，從左至右”訪問樹中的各結點。訪問樹中的各結點。 為保證是按層次遍歷，必須設置一個隊列，初始化為保證是按層次遍歷，必須設置一個隊列，初始化時為空。時為空。 設設T是指向根結點的指針變量，層次遍歷非遞歸算是指向根結點的指針變量，層次遍歷非遞歸算法是：法是：若二叉樹為空，則返回；否則，令若二叉樹為空，則返回；否則，令p=T，p入隊；入隊； 隊首元素出隊到隊首元素出隊到p；訪問訪問p所指向的結點；所指向的結點； 將將p所指向的結點的左、右子結點依次入隊。直到隊所指向的結點的左

27、、右子結點依次入隊。直到隊空為止?？諡橹?。#define MAX_NODE 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ;int front=0 , rear=0 ;if (p!=NULL) Queue+rear=p; /* 根結點入隊根結點入隊 */while (frontdata ); if (p-Lchild!=NULL) Queue+rear=p; /* 左結點入隊左結點入隊 */ if (p-Rchild!=NULL) Queue+rear=p; /* 左結點入隊左結點入隊 */ v遍歷算法應用v

28、“遍歷”是二叉樹最重要的基本操作，是各種其它操作的基礎，二叉樹的許多其它操作都可以通過遍歷來實現。如建立二叉樹的存儲結構、求二叉樹的結點數、求二叉樹的深度等。v按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：v A B C D E G F l求二叉樹深度算法ABCDEFG A B C D E F G l統(tǒng)計二叉樹中葉子結點個數算法（1）按先序遍歷方式建立二叉鏈表）按先序遍歷方式建立二叉鏈表 對一棵二叉樹進行對一棵二叉樹進行“擴充擴充”，就可以得到有該二叉，就可以得到有該二叉樹所擴充的二叉樹。樹所擴充的二叉樹。ABCDEFG(a) 二叉樹二叉樹T1(b) T1的擴充二叉樹的擴充二叉樹T2AB

29、CDEFG? 二叉樹的擴充方法是：在二叉樹中結點的每一個空鏈二叉樹的擴充方法是：在二叉樹中結點的每一個空鏈域處增加一個擴充的結點域處增加一個擴充的結點(總是葉子結點，用方框總是葉子結點，用方框“”表示表示)。對于二叉樹的結點值：。對于二叉樹的結點值： 是是char類型：擴充結點值為類型：擴充結點值為“？”； 是是int類型：擴充結點值為類型：擴充結點值為0或或-1； 下面的算法是二叉樹的前序創(chuàng)建的遞歸算法，讀入一下面的算法是二叉樹的前序創(chuàng)建的遞歸算法，讀入一棵二叉樹對應的擴充二叉樹的前序遍歷的結點值序列。每棵二叉樹對應的擴充二叉樹的前序遍歷的結點值序列。每讀入一個結點值就進行分析：讀入一個結點

30、值就進行分析： 若是擴充結點值：令根指針為若是擴充結點值：令根指針為NULL； 若是若是(正常正常)結點值：動態(tài)地為根指針分配一個結點，將結點值：動態(tài)地為根指針分配一個結點，將該值賦給根結點，然后遞歸地創(chuàng)建根的左子樹和右子樹。該值賦給根結點，然后遞歸地創(chuàng)建根的左子樹和右子樹。利用先序序列創(chuàng)建二叉鏈表算法實現：利用先序序列創(chuàng)建二叉鏈表算法實現：#define NULLKY ?#define MAX_NODE 50typedef struct BTNode char data ;struct BTNode *Lchild , *Rchild ;BTNode ;BTNode *Preorder_Cr

31、eate_BTree(BTNode *T) /* 建立鏈式二叉樹，返回指向根結點的指針變量建立鏈式二叉樹，返回指向根結點的指針變量 */ char ch ; ch=getchar() ; getchar(); if (ch=NULLKY) T=NULL; return(T) ; else T=(BTNode *)malloc(sizeof(BTNode) ;Tdata=ch ;Preorder_Create_BTree(T-Lchild) ;Preorder_Create_BTree(T-Rchild) ;return(T) ; 當希望創(chuàng)建圖當希望創(chuàng)建圖6-10(a)所示的二叉樹時，輸入的字符

32、序列應當是：所示的二叉樹時，輸入的字符序列應當是：ABD?E?G?CF?（2）求二叉樹的葉子結點數）求二叉樹的葉子結點數 可以直接利用先序遍歷二叉可以直接利用先序遍歷二叉樹算法求二叉樹的葉子結點數。樹算法求二叉樹的葉子結點數。只要將先序遍歷二叉樹算法中只要將先序遍歷二叉樹算法中visit()函數簡單地進行修改就可以函數簡單地進行修改就可以。#define MAX_NODE 50int search_leaves( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) if (p-Lchild=NULL) & (p-Rchild

33、=NULL ) num+ ; q=p-Rchild ; if ( q!=NULL ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /whilereturn(num) ;（3）求二叉樹的深度）求二叉樹的深度 利用層次遍歷算法可以直接求得利用層次遍歷算法可以直接求得二叉樹的深度。二叉樹的深度。算法實現：算法實現：#define MAX_NODE 50int search_depth( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int front=0 , rear=0, depth=0, level ;/* l

34、evel總是指向訪問層的最后一總是指向訪問層的最后一個結點在隊列的位置個結點在隊列的位置 */if (T!=NULL) Queue+rear=p; /* 根結根結點入隊點入隊 */level=rear ; /* 根是第根是第1層的最層的最后一個節(jié)點后一個節(jié)點 */while (frontLchild!=NULL) Queue+rear=p; /* 左結點入隊左結點入隊 */ if (p-Rchild!=NULL) Queue+rear=p; /* 左結點入隊左結點入隊 */ if (front=level) /* 正訪問的是當前層的最后一個結點正訪問的是當前層的最后一個結點 */ depth+

35、 ; level=rear ; 遍歷二叉樹是按一定的規(guī)則將樹中的結點排列成一個線性序列，即是對非線性結構的線性化操作。如何找到遍歷過程中動態(tài)得到的每個結點的直接前驅和直接后繼(第一個和最后一個除外)?如何保存這些信息? 設一棵二叉樹有n個結點，則有n-1條邊(指針連線) ， 而n個結點共有2n個指針域(Lchild和Rchild) ，顯然有n+1個空閑指針域未用。則可以利用這些空閑的指針域來存放結點的直接前驅和直接后繼信息。對結點的指針域做如下規(guī)定： 6.5線索二叉樹線索二叉樹 若結點有左孩子，則若結點有左孩子，則Lchild指向其左孩子，否指向其左孩子，否則，指向其直接前驅；則，指向其直接前

36、驅； 若結點有右孩子，則若結點有右孩子，則Rchild指向其右孩子，否指向其右孩子，否則，指向其直接后繼；則，指向其直接后繼；為避免混淆為避免混淆,對結點結構加以改進，增加兩個標志對結點結構加以改進，增加兩個標志域，如圖所示。域，如圖所示。Lchild Ltag data Rchild Rtag線索二叉樹的結點結構線索二叉樹的結點結構0：Lchild域指示結點的左孩子1 1：LchildLchild域指示結點的前驅域指示結點的前驅Ltag=0 0：RchildRchild域指示結點的右孩子域指示結點的右孩子1 1：RchildRchild域指示結點的后繼域指示結點的后繼Rtag= 用這種結點結

37、構構成的二叉樹的存儲結構；叫做線索鏈表；指向結點前驅和后繼的指針叫做線索；按照某種次序遍歷，加上線索的二叉樹稱之為線索二叉樹。線索二叉樹的結點結構與示例typedef struct BiThrNode ElemType data;struct BiTreeNode *Lchild , *Rchild ; int Ltag , Rtag ;BiThrNode ; AFHIEGBDC(a) 二叉樹 (b) 先序線索樹的邏輯形式先序線索樹的邏輯形式 結點序列：結點序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序線索樹的邏輯形式后序線索樹的邏輯形式 結點序列：結點序列：DBGEHIFCA(

38、c) 中序線索樹的邏輯形式中序線索樹的邏輯形式 結點序列：結點序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1 (e) 中序線索樹的鏈表結構中序線索樹的鏈表結構說明：畫線索二叉樹時，實線表示指針，指向其左、右孩子；說明：畫線索二叉樹時，實線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅或直接后繼。虛線表示線索，指向其直接前驅或直接后繼。 在線索樹上進行遍歷，只要先找到序列中的第一個結點，在線索樹上進行遍歷，只要先找到序列中的第一個結點，然后就可以依

39、次找結點的直接后繼結點直到后繼為空為止。然后就可以依次找結點的直接后繼結點直到后繼為空為止。 如何在線索樹中找結點的直接后繼如何在線索樹中找結點的直接后繼? ? 樹中所有葉子結點的右鏈都是線索。右鏈直接樹中所有葉子結點的右鏈都是線索。右鏈直接指示了結點的直接后繼，如結點指示了結點的直接后繼，如結點G G的直接后繼是結點的直接后繼是結點E E。 樹中所有非葉子結點的右鏈都是指針。根據中序樹中所有非葉子結點的右鏈都是指針。根據中序遍歷的規(guī)律，非葉子結點的直接后繼是遍歷其右子樹遍歷的規(guī)律，非葉子結點的直接后繼是遍歷其右子樹時訪問的第一個結點，即右子樹中最左下的時訪問的第一個結點，即右子樹中最左下的(

40、 (葉子葉子) )結結點。如結點點。如結點C C的直接后繼：沿右指針找到右子樹的根的直接后繼：沿右指針找到右子樹的根結點結點F F，然后沿左鏈往下直到，然后沿左鏈往下直到Ltag=1Ltag=1的結點即為的結點即為C C的直的直接后繼結點接后繼結點H H。 如何在線索樹中找結點的直接前驅?若結點的Ltag=1，則左鏈是線索，指示其直接前驅；否則，遍歷左子樹時訪問的最后一個結點(即沿左子樹中最右往下的結點) 為其直接前驅結點。 對于后序遍歷的線索樹中找結點的直接后繼比較復雜，可分以下三種情況： 若結點是二叉樹的根結點：其直接后繼為空； 若結點是其父結點的左孩子或右孩子且其父結點沒有右子樹：直接后

41、繼為其父結點； 若結點是其父結點的左孩子且其父結點有右子樹：直接后繼是對其父結點的右子樹按后序遍歷的第一個結點。6.5.1 線索化二叉樹線索化二叉樹 二叉樹的線索化指的是依照某種遍歷次序二叉樹的線索化指的是依照某種遍歷次序使二叉樹成為線索二叉樹的過程。使二叉樹成為線索二叉樹的過程。 線索化的過程就是在遍歷過程中修改空指針線索化的過程就是在遍歷過程中修改空指針使其指向直接前驅或直接后繼的過程。使其指向直接前驅或直接后繼的過程。 仿照線性表的存儲結構，在二叉樹的線索鏈仿照線性表的存儲結構，在二叉樹的線索鏈表上也添加一個頭結點表上也添加一個頭結點head，頭結點的指針域，頭結點的指針域的安排是：的安

42、排是： Lchild域：指向二叉樹的根結點；域：指向二叉樹的根結點； Rchild域：指向中序遍歷時的最后一個結點域：指向中序遍歷時的最后一個結點； 二叉樹中序序列中的第一個結點二叉樹中序序列中的第一個結點Lchild指針指針域和最后一個結點域和最后一個結點Rchild指針域均指向頭結點指針域均指向頭結點head。 如同為二叉樹建立了一個雙向線索鏈表，如同為二叉樹建立了一個雙向線索鏈表，對一棵線索二叉樹既可從頭結點也可從最后對一棵線索二叉樹既可從頭結點也可從最后一個結點開始按尋找直接后繼進行遍歷。顯一個結點開始按尋找直接后繼進行遍歷。顯然，這種遍歷不需要堆棧，如圖然，這種遍歷不需要堆棧，如圖6

43、-126-12所示。所示。結點類型定義結點類型定義#define MAX_NODE 50#define MAX_NODE 50typedef enmuLink , Thread PointerTag ;typedef enmuLink , Thread PointerTag ;/ /* * Link=0 Link=0表示指針，表示指針， Thread=1 Thread=1表示線索表示線索 * */ /typedef struct BiThrNodetypedef struct BiThrNode ElemType data; ElemType data;struct BiTreeNode st

44、ruct BiTreeNode * *Lchild , Lchild , * *Rchild ; Rchild ; PointerTag Ltag , Rtag ;PointerTag Ltag , Rtag ;BiThrNode;BiThrNode;(a) 二叉樹二叉樹(b) 中序線索樹的邏輯形式中序線索樹的邏輯形式AFHIEGBDCNILNILAFHIEGBDC中序線索二叉樹及其存儲結構中序線索二叉樹及其存儲結構(c) 中序線索二叉鏈表 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1Thrt 0 1head 1 先序線索化二叉樹先

45、序線索化二叉樹 void preorder_Threading(BiThrNode *T) BiThrNode *last=NULL, *p=T ;InitStack(S); while (p!=NULL) if (p-Lchild!=NULL) p-Ltag=0 else p-Ltag=1 ; p-Lchild=last ; if (p-Rchild!=NULL) push(S, p-Rchild) ; if (last!=NULL)if (last-Rchild!=NULL) last-Rtag=0 ;else last-Rtag=1 ; last-Rchild=p ; last=p ;p

46、=p-Lchild;if (p=NULL) pop(S,p) ;/ /whileLast-Rtag=1; /* 最后一個結點是葉子結最后一個結點是葉子結點點 */先序遍歷的非遞歸算法先序遍歷的非遞歸算法void PreorderTraverse( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) visit( p- data ) ; q=p-Rchild ; if ( q!=NULL ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /while2 中序線索化二叉樹中序線索化二叉

47、樹void inorder_Threading(BiThrNode *T) BiThrNode *last=NULL, *p=T ; InitStack(S);while (p!=NULL| !StackEmpty(S)if (p!=NULL) push(S,p); p=p-Lchild; else pop(S,p) ; if (p-Lchild!=NULL) p-Ltag=0 ; else p-Ltag=1 ; p-Lchild=last ; if (last!=NULL) if (last-Rchild!=NULL) last-Rtag=0 ; else last-Rtag=1 ; las

48、t-Rchild=p ; last=p ; p=p-Rchild; last-Rtag=1; /* 最后一個結點是葉子結最后一個結點是葉子結點點 */中序遍歷的非遞歸算法：中序遍歷的非遞歸算法：void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走到底向左走到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 訪問結點，

49、向右訪問結點，向右一步一步 /while 6.5.2 線索二叉樹的遍歷線索二叉樹的遍歷 在線索二叉樹中，由于有線索存在，在某在線索二叉樹中，由于有線索存在，在某些情況下可以方便地找到指定結點在某種遍歷些情況下可以方便地找到指定結點在某種遍歷序列中的直接前驅或直接后繼。此外，在線索序列中的直接前驅或直接后繼。此外，在線索二叉樹上進行某種遍歷比在一般的二叉樹上進二叉樹上進行某種遍歷比在一般的二叉樹上進行這種遍歷要容易得多，不需要設置堆棧，且行這種遍歷要容易得多，不需要設置堆棧，且算法十分簡潔。算法十分簡潔。1 先序線索二叉樹的先序遍歷先序線索二叉樹的先序遍歷void preorder_Thread

50、_bt(BiThrNode *T) BiThrNode *p=T ;while (p!=NULL) visit(p-data) ; if (p-Ltag=0) p=p-Lchild ; else p=p-Rchild 在先序線索二叉樹中找結點后繼的方法：在先序線索二叉樹中找結點后繼的方法：（1）若）若Ltag=0, 則則Lchild域直接指向其后繼域直接指向其后繼（2）若）若Ltag=1, 則則Rchild域直接指向其后繼域直接指向其后繼2 中序線索二叉樹的中序遍歷中序線索二叉樹的中序遍歷void inorder_Thread_bt(BiThrNode *T) BiThrNode *p ;if

51、 (T!=NULL) p=T;while (p-Ltag=0 ) p=p-Lchild; /* 尋找最左的結點尋找最左的結點 */while (p!=NULL) visit(p-data) ; if (p-Rtag=1) p=p-Rchild ; /* 通過右線索找通過右線索找到后繼到后繼 */ else /* 否則，右子樹的最左結點否則，右子樹的最左結點為后繼為后繼 */ p=p-Rchild ; while (p-Ltag=0 ) p=p-Lchild; /else /while/if 在中序線索二叉樹中找結點后繼的方法：在中序線索二叉樹中找結點后繼的方法：（1）若）若Rtag=1, 則則

52、Rchild域直接指向其后繼域直接指向其后繼（2）若）若Rtag=0, 則結點的后繼應是其右子樹則結點的后繼應是其右子樹的左鏈尾（的左鏈尾（Ltag=1)的結點的結點拓展思考：拓展思考：在中序線索二叉樹中找結點前驅的方法：在中序線索二叉樹中找結點前驅的方法：（1）若）若Ltag=1, 則則Lchild域直接指向其前驅域直接指向其前驅（2）若）若Ltag=0, 則結點的前驅應是其左子則結點的前驅應是其左子樹的右鏈尾（樹的右鏈尾（Rtag=1)的結點的結點中序線索樹的邏輯形式中序線索樹的邏輯形式AFHIEGBDCNILNIL中序線索二叉樹及其存儲結構中序線索二叉樹及其存儲結構(c) 中序線索二叉鏈

53、表 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結點的中序線索二叉樹 0 1頭結點：Ltag=0, Lchild指向根結點Rtag=1, Rchild指向遍歷序列中最后一個結點遍歷序列中第一個結點的Lchild域和最后一個結點的Rchild域都指向頭結點 A B D C ET中序序列：BCAED中序線索二叉樹00001111116.6 二叉樹的應用哈夫曼樹哈夫曼樹(Huffman)帶權路徑長度最短的樹定義路徑：從樹中一個結點到另一個結點

54、之間的分支構成這兩個結點間的路徑長度：路徑上的分支數樹的路徑長度：從樹根到每一個結點的路徑長度之和樹的帶權路徑長度：樹中所有帶權結點的路徑長度之和結點到根的路徑長度權值其中：記作：kknkkklwlwwpl1lHuffman樹設有n個權值w1,w2,wn，構造一棵有n個葉子結點的二叉樹，每個葉子的權值為wi,則wpl最小的二叉樹叫例 有4個結點，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL1

55、vHuffman樹應用v最佳判定樹等級分數段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a2n-1 */ typedef structint Weight ; /* 權值域權值域 */int Parent , Lchild , Rchild ; HTNode ;(2) Huffman樹的生成樹的生成算法實現算法實現void Create_Huffman(int n, HTNode HT , int m)

56、 /* 創(chuàng)建一棵葉子結點數為創(chuàng)建一棵葉子結點數為n的的Huffman樹樹 */ int w ; int k , j ;for (k=1 ; km ; k+) if (k=n) printf(“n Please Input Weight : w=?”); scanf(“%d”, &w) ;HTk.weight=w ; /* 輸入時，所有葉子結點都有權值輸入時，所有葉子結點都有權值 */else HTk.weight=0; /* 非葉子結點沒有權非葉子結點沒有權值值 */HTk.Parent=HTk.Lchild=HTk.Rchild=0 ; /* 初始化向量初始化向量HT */ for

57、(k=n+1; km ; k+) int w1=32767 , w2=w1 ; /* w1 , w2分別保存權值最小的兩個權值分別保存權值最小的兩個權值 */ int p1=0 , p2=0 ; /* p1 , p2保存兩個最小權值的下標保存兩個最小權值的下標 */for (j=1 ; j=k-1 ; j+) if (HTk.Parent=0) /* 尚未合并尚未合并 */ if (HTj.Weightw1) w2=w1 ; p2=p1 ; w1=HTj.Weight ; p1=j ; else if (HTj.Weightw2) w2=HTj.Weight ; p2=j ; /* 找到權值最小的兩個值及其下標找到權值最小的兩個值及其下標 */HTk.Lchild=p1 ; HTk.Rchild=p2 ;HTk.weight=w1+w2 ;HTp1.Parent=k ; HTp2.Parent=k ; 說明：生成說明：生成Huffman樹后，樹的根結點的下標是樹后，樹的根結點的下標是2n-1 ，即，即m-1 。(3) Huffman編碼算法編碼算法 根據出現頻度根據出現頻度(權值權值)Weight，對葉子結點的，對葉子結點的Huffman編碼有編碼有