數(shù)據(jù)結(jié)構(gòu)六樹

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

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

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

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

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

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

7、b c d e f g h i二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素特點：結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v鏈?zhǔn)酱鎯Y(jié)構(gòu)v二叉鏈表typedef struct BiTNode datatype data; struct BiTNode *lchild, *rchild; BiTNode; * BiTree;lchild data rchild ABCDEFG在n個結(jié)點的二叉鏈表中，有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樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對應(yīng)存儲存儲解釋解釋v將樹轉(zhuǎn)換成二叉樹v加線：在兄弟之間加一連線v抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系v旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45ABCDEFGHI

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

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

11、的結(jié)點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二叉樹的遍歷方法先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點按層次遍歷：從上到下、從左到右訪問各結(jié)點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中序遍歷:算法的遞歸定義是：算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則若二叉樹為空，則遍歷結(jié)束；否則 中序遍歷左子樹中序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 訪問根結(jié)點；訪問根結(jié)點； 中序遍歷右子樹中序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)。v中序遍歷的遞歸算法中序遍歷的遞歸算法void InorderTraverse(BTNode *T) if (T!=NULL) InorderTraverse(T-Lchild) ;visit

13、(T-data) ; /* 訪問根結(jié)點訪問根結(jié)點 */InorderTraverse(T-Rchild) ; 中序遍歷非遞歸算法思路：中序遍歷非遞歸算法思路：設(shè)設(shè)T是指向二叉樹根結(jié)點的指針是指向二叉樹根結(jié)點的指針變量，非遞歸算法是：變量，非遞歸算法是：若二叉樹為空，則返回；否則，若二叉樹為空，則返回；否則，令令p=T 若若p不為空，不為空，p進(jìn)棧，進(jìn)棧， p=p-Lchild ； 否則否則(即即p為空為空)，退棧到，退棧到p，訪，訪問問p所指向的結(jié)點；所指向的結(jié)點； p=p-Rchild ，轉(zhuǎn)，轉(zhuǎn)(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 訪問結(jié)點，向右一步訪問結(jié)點，向右一步 /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算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則遍歷結(jié)束；否則若二叉樹為空，則遍歷結(jié)束；否則 訪問根結(jié)點；訪問根結(jié)點； 先序遍歷左子樹先序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 先序遍歷右子樹先序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)。先序遍歷:先序遍歷序列：A B D Cv先序遍歷的遞歸算法先序遍歷的遞歸算法void PreorderTraverse(BTNode *T) if (T!=NULL)

17、 visit(T-data) ; /* 訪問根結(jié)點訪問根結(jié)點 */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 說明：說明：visit()函數(shù)是訪問結(jié)點的數(shù)據(jù)域，其要求視具體問題而定。樹采函數(shù)是訪問結(jié)點的數(shù)據(jù)域，其要求視具體問題而定。樹采用二叉鏈表的存儲結(jié)構(gòu)，用指針變量用二叉鏈表的存儲結(jié)構(gòu)，用指針變量T來指向。來指向。void PreorderTraverse(BTNode *T) if (T!=NULL) printf(%dt,bt-data);/* 訪問根結(jié)點訪問根結(jié)點 */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先序遍歷的非遞歸算法先序遍歷的非遞歸算法設(shè)設(shè)T是指向二叉樹根結(jié)點的指針是指向二叉樹根結(jié)點的指針變量，非遞歸算法是：變量，非遞歸算法是：若二叉樹為空

19、，則返回；否則，若二叉樹為空，則返回；否則，令令p=T； 訪問訪問p所指向的結(jié)點；所指向的結(jié)點； q=p-Rchild ，若，若q不為空，不為空，則則q進(jìn)棧；進(jìn)棧； p=p-Lchild ，若，若p不為空，不為空，轉(zhuǎn)轉(zhuǎn)(1)，否則轉(zhuǎn)，否則轉(zhuǎn)(4)； 退棧到退棧到p ，轉(zhuǎn)，轉(zhuǎn)(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 訪問結(jié)點，訪問結(jié)點，向右一步向右一步 /wh

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

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

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

24、：若二叉樹為空，則返回；否則，令p=T； 第一次經(jīng)過根結(jié)點p，不訪問： p進(jìn)棧S1 ， tag 賦值0，進(jìn)棧S2，p=p-Lchild 。 若p不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標(biāo)志值tag ： 若tag=0：對棧S1，不訪問，不出棧；修改S2棧頂元素值(tag賦值1) ，取S1棧頂元素的右子樹，即p=S1top-Rchild ，轉(zhuǎn)(1)； 若tag=1：S1退棧，訪問該結(jié)點；直到?？諡橹埂Ｋ惴▽崿F(xiàn)：算法實現(xiàn)：#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ù)進(jìn)行而不至于死使循環(huán)繼續(xù)進(jìn)行而不至于死循環(huán)循環(huán) */ while (bool!=0) ;層次遍歷二叉樹層次遍歷二

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

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

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

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

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

31、eate_BTree(BTNode *T) /* 建立鏈?zhǔn)蕉鏄洌祷刂赶蚋Y(jié)點的指針變量建立鏈?zhǔn)蕉鏄?，返回指向根結(jié)點的指針變量 */ 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) ; 當(dāng)希望創(chuàng)建圖當(dāng)希望創(chuàng)建圖6-10(a)所示的二叉樹時，輸入的字符

32、序列應(yīng)當(dāng)是：所示的二叉樹時，輸入的字符序列應(yīng)當(dāng)是：ABD?E?G?CF?（2）求二叉樹的葉子結(jié)點數(shù)）求二叉樹的葉子結(jié)點數(shù) 可以直接利用先序遍歷二叉可以直接利用先序遍歷二叉樹算法求二叉樹的葉子結(jié)點數(shù)。樹算法求二叉樹的葉子結(jié)點數(shù)。只要將先序遍歷二叉樹算法中只要將先序遍歷二叉樹算法中visit()函數(shù)簡單地進(jìn)行修改就可以函數(shù)簡單地進(jìn)行修改就可以。#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）求二叉樹的深度）求二叉樹的深度 利用層次遍歷算法可以直接求得利用層次遍歷算法可以直接求得二叉樹的深度。二叉樹的深度。算法實現(xiàn)：算法實現(xiàn)：#define MAX_NODE 50int search_depth( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int front=0 , rear=0, depth=0, level ;/* l

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

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

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

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

38、c) 中序線索樹的邏輯形式中序線索樹的邏輯形式 結(jié)點序列：結(jié)點序列：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) 中序線索樹的鏈表結(jié)構(gòu)中序線索樹的鏈表結(jié)構(gòu)說明：畫線索二叉樹時，實線表示指針，指向其左、右孩子；說明：畫線索二叉樹時，實線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅(qū)或直接后繼。虛線表示線索，指向其直接前驅(qū)或直接后繼。 在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個結(jié)點，在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個結(jié)點，然后就可以依

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

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

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

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

43、-126-12所示。所示。結(jié)點類型定義結(jié)點類型定義#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中序線索二叉樹及其存儲結(jié)構(gòu)中序線索二叉樹及其存儲結(jié)構(gòu)(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; /* 最后一個結(jié)點是葉子結(jié)最后一個結(jié)點是葉子結(jié)點點 */先序遍歷的非遞歸算法先序遍歷的非遞歸算法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; /* 最后一個結(jié)點是葉子結(jié)最后一個結(jié)點是葉子結(jié)點點 */中序遍歷的非遞歸算法：中序遍歷的非遞歸算法：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 訪問結(jié)點，

49、向右訪問結(jié)點，向右一步一步 /while 6.5.2 線索二叉樹的遍歷線索二叉樹的遍歷 在線索二叉樹中，由于有線索存在，在某在線索二叉樹中，由于有線索存在，在某些情況下可以方便地找到指定結(jié)點在某種遍歷些情況下可以方便地找到指定結(jié)點在某種遍歷序列中的直接前驅(qū)或直接后繼。此外，在線索序列中的直接前驅(qū)或直接后繼。此外，在線索二叉樹上進(jìn)行某種遍歷比在一般的二叉樹上進(jìn)二叉樹上進(jìn)行某種遍歷比在一般的二叉樹上進(jìn)行這種遍歷要容易得多，不需要設(shè)置堆棧，且行這種遍歷要容易得多，不需要設(shè)置堆棧，且算法十分簡潔。算法十分簡潔。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 在先序線索二叉樹中找結(jié)點后繼的方法：在先序線索二叉樹中找結(jié)點后繼的方法：（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; /* 尋找最左的結(jié)點尋找最左的結(jié)點 */while (p!=NULL) visit(p-data) ; if (p-Rtag=1) p=p-Rchild ; /* 通過右線索找通過右線索找到后繼到后繼 */ else /* 否則，右子樹的最左結(jié)點否則，右子樹的最左結(jié)點為后繼為后繼 */ p=p-Rchild ; while (p-Ltag=0 ) p=p-Lchild; /else /while/if 在中序線索二叉樹中找結(jié)點后繼的方法：在中序線索二叉樹中找結(jié)點后繼的方法：（1）若）若Rtag=1, 則則

52、Rchild域直接指向其后繼域直接指向其后繼（2）若）若Rtag=0, 則結(jié)點的后繼應(yīng)是其右子樹則結(jié)點的后繼應(yīng)是其右子樹的左鏈尾（的左鏈尾（Ltag=1)的結(jié)點的結(jié)點拓展思考：拓展思考：在中序線索二叉樹中找結(jié)點前驅(qū)的方法：在中序線索二叉樹中找結(jié)點前驅(qū)的方法：（1）若）若Ltag=1, 則則Lchild域直接指向其前驅(qū)域直接指向其前驅(qū)（2）若）若Ltag=0, 則結(jié)點的前驅(qū)應(yīng)是其左子則結(jié)點的前驅(qū)應(yīng)是其左子樹的右鏈尾（樹的右鏈尾（Rtag=1)的結(jié)點的結(jié)點中序線索樹的邏輯形式中序線索樹的邏輯形式AFHIEGBDCNILNIL中序線索二叉樹及其存儲結(jié)構(gòu)中序線索二叉樹及其存儲結(jié)構(gòu)(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帶頭結(jié)點的中序線索二叉樹 0 1頭結(jié)點：Ltag=0, Lchild指向根結(jié)點Rtag=1, Rchild指向遍歷序列中最后一個結(jié)點遍歷序列中第一個結(jié)點的Lchild域和最后一個結(jié)點的Rchild域都指向頭結(jié)點 A B D C ET中序序列：BCAED中序線索二叉樹00001111116.6 二叉樹的應(yīng)用哈夫曼樹哈夫曼樹(Huffman)帶權(quán)路徑長度最短的樹定義路徑：從樹中一個結(jié)點到另一個結(jié)點

54、之間的分支構(gòu)成這兩個結(jié)點間的路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和結(jié)點到根的路徑長度權(quán)值其中：記作：kknkkklwlwwpl1lHuffman樹設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫例 有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹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樹應(yīng)用v最佳判定樹等級分?jǐn)?shù)段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a2n-1 */ typedef structint Weight ; /* 權(quán)值域權(quán)值域 */int Parent , Lchild , Rchild ; HTNode ;(2) Huffman樹的生成樹的生成算法實現(xiàn)算法實現(xiàn)void Create_Huffman(int n, HTNode HT , int m)

56、 /* 創(chuàng)建一棵葉子結(jié)點數(shù)為創(chuàng)建一棵葉子結(jié)點數(shù)為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 ; /* 輸入時，所有葉子結(jié)點都有權(quán)值輸入時，所有葉子結(jié)點都有權(quán)值 */else HTk.weight=0; /* 非葉子結(jié)點沒有權(quán)非葉子結(jié)點沒有權(quán)值值 */HTk.Parent=HTk.Lchild=HTk.Rchild=0 ; /* 初始化向量初始化向量HT */ for

57、(k=n+1; km ; k+) int w1=32767 , w2=w1 ; /* w1 , w2分別保存權(quán)值最小的兩個權(quán)值分別保存權(quán)值最小的兩個權(quán)值 */ int p1=0 , p2=0 ; /* p1 , p2保存兩個最小權(quán)值的下標(biāo)保存兩個最小權(quán)值的下標(biāo) */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 ; /* 找到權(quán)值最小的兩個值及其下標(biāo)找到權(quán)值最小的兩個值及其下標(biāo) */HTk.Lchild=p1 ; HTk.Rchild=p2 ;HTk.weight=w1+w2 ;HTp1.Parent=k ; HTp2.Parent=k ; 說明：生成說明：生成Huffman樹后，樹的根結(jié)點的下標(biāo)是樹后，樹的根結(jié)點的下標(biāo)是2n-1 ，即，即m-1 。(3) Huffman編碼算法編碼算法 根據(jù)出現(xiàn)頻度根據(jù)出現(xiàn)頻度(權(quán)值權(quán)值)Weight，對葉子結(jié)點的，對葉子結(jié)點的Huffman編碼有編碼有