《數(shù)據(jù)結(jié)構(gòu)與算法》課件chap06

1、第六章 樹和二叉樹 第六章 樹和二叉樹6.1 樹的有關(guān)概念6.2 二叉樹6.3 二叉樹的遍歷6.4 遍歷的應(yīng)用6.5 線索二叉樹6.6 樹和森林6.7 哈夫曼樹及應(yīng)用6.1 樹的有關(guān)概念1. 樹的概念2. 樹的應(yīng)用3. 樹的表示樹的有關(guān)術(shù)語5 樹的基本操作1樹的概念 樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，討論的是層次和分支關(guān)系。樹是n個結(jié)點(diǎn)的有限集合，在任一棵非空樹中：（1）有且僅有一個稱為根的結(jié)點(diǎn)。（2）其余結(jié)點(diǎn)可分為個互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。樹是遞歸結(jié)構(gòu)，在樹的定義中又用到了樹的概念JIACBDHGFEKLM例：下面的圖是一棵樹T=A, B, C,

2、 D, E, F, G, H, I, J，K，L，MA是根，其余結(jié)點(diǎn)可以劃分為3個互不相交的集合： T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。 例如 對于 T11，B是根，其余結(jié)點(diǎn)可以劃分為2個互不相交的集合： T11=E，K，L，T12=F，T11,T12 是B 的子樹。JIACBDHGFEKLM從邏輯結(jié)構(gòu)看：1）樹中只有根結(jié)點(diǎn)沒有前趨；2）除根外，其余結(jié)點(diǎn)都有且僅一個前趨；3）樹的結(jié)點(diǎn)，可以有零個或多個后繼；6）除根外的其他結(jié)點(diǎn)，都存在唯一條從根到該結(jié)點(diǎn)的路徑；5）樹是一種分枝結(jié)構(gòu) （除了一個稱

3、為根的結(jié)點(diǎn)外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。JIACBDHGFEKLM2樹的應(yīng)用1）樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象例1家族族譜 設(shè)某家庭有13個成員A、B、C、D、E、F、G、H、I、J，K，L，M他們之間的關(guān)系可下圖所示的樹表示：例2單位行政機(jī)構(gòu)的組織關(guān)系JIACBDHGFEKLM2）樹是常用的數(shù)據(jù)組織形式 有些應(yīng)用中數(shù)據(jù)元素之間并不存在間分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。例3 計(jì)算機(jī)的文件系統(tǒng) 不論是DOS文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹的形式來組織的。文件夾1 文件夾n 文件1 文件2文件夾11 文件夾12

4、文件11 文件12C3 樹的表示1）圖示表示 2）二元組表示3）嵌套集合表示 6）凹入表示法（類似書的目錄）5）廣義表表示AEDHJIKLMDGCABEKLFCGDHMJI（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）樹的 基本術(shù)語 樹的結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向子樹的分支；孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；雙親結(jié)點(diǎn)：B 結(jié)點(diǎn)是A 結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B 結(jié)點(diǎn)的雙親；兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)；祖先結(jié)點(diǎn): 從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn) 子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫JIACBDHGFEKLM樹的 基本術(shù)語

5、結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依此類推；樹的深度：樹中最大的結(jié)點(diǎn)層結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個數(shù)樹的度： 樹中最大的結(jié)點(diǎn)度。葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn)；分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；有序樹：子樹有序的樹，如：家族樹；無序樹：不考慮子樹的順序；森林；互不相交的樹集合；森林和樹之間的聯(lián)系是：一棵樹去掉根 ，其子樹構(gòu)成一個森林；一個森林增加一個根結(jié)點(diǎn)成為樹。JIACBDHGFEKLM5 樹的基本操作 樹的應(yīng)用很廣，應(yīng)用不同基本操作也不同。下面列舉了樹的一些基本操作：1）initiate (T); T 樹的初始化，包括建樹。2） root (T); 求T 樹的根。3）pare

6、nt (T , x ): 求T 樹中 x 結(jié)點(diǎn)的雙親結(jié)點(diǎn)。6）Child (T, x, i )： 求 T 樹中 x 結(jié)點(diǎn)的第 i 個孩子結(jié)點(diǎn)。5）right_sibling (T, x ): 求T 樹中 x 結(jié)點(diǎn)的右兄弟6）insert_Child (y, i, x ): 將根為 x 的子樹置為 y 結(jié)點(diǎn)的第 i 個孩子7） del_child (x, i); 刪除 x 結(jié)點(diǎn)的第i 個孩子8）traverse (T); 遍歷T樹。按某個次序依次訪問樹中每一個結(jié)點(diǎn)，并使每個結(jié)點(diǎn)都被訪問且只被訪問一次。9）clear (T); 置空T 樹 6.2 二 叉 樹 樹是一種分枝結(jié)構(gòu)的對象，在樹的概念中，

7、對每一個結(jié)點(diǎn)孩子的個數(shù)沒有限制，因此樹的形態(tài)多種多樣，本章我們主要討論一種最簡單的樹二叉樹。6.2 二叉樹一 二叉樹的概念二 二叉樹的性質(zhì)三 二叉樹的存儲結(jié)構(gòu)一 二叉樹的概念1 二叉樹的定義二叉樹： 或?yàn)榭諛洌蛴筛皟深w不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。說明1）二叉樹中每個結(jié)點(diǎn)最多有兩顆子樹；二叉樹每個結(jié)點(diǎn)度小于等于2;2）左、右子樹不能顛倒有序樹;3）二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念; A F G E D C B A F G E D C B (a)、(b)是不同的二叉樹， (a)的左子樹有四個結(jié)點(diǎn)，(b)的左子樹有兩個結(jié)點(diǎn)，(a) A G E

8、D B C F(b) 2 二叉樹的基本形態(tài)(a)空樹(b)僅有根(c) 右子樹空(e) 左子樹空(d) 左、右子樹均在3應(yīng)用舉例例1 可以用二叉樹表示表達(dá)式 a+b*(c-d)-e/f e d c b f a + * / - -二 二叉樹性質(zhì)性質(zhì)1 在二叉樹的第i 層上最多有2i-1個結(jié)點(diǎn)性質(zhì)2 深度為k的二叉樹最多有 2k-1 個結(jié)點(diǎn)性質(zhì)3 設(shè)二叉樹葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)n2，則n0 = n2 +1 A F G E D C B兩種特殊的二叉樹滿二叉樹：如果深度為k的二叉樹，有2k-1個結(jié)點(diǎn)則稱為滿二叉樹； A G F E D C B A C BK=3的滿二叉樹K=2的滿二叉樹完全二叉

9、樹：如果一顆二叉樹只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大，并且最下層結(jié)點(diǎn)都集中在該層的最左端，則稱為完全二叉樹； A E D C B G A E D C B(a)(c)(b)、(b)完全二叉樹(c) 不是完全二叉樹 A G F E D C B下面是兩個關(guān)于完全二叉樹的性質(zhì)性質(zhì)6 具有n個結(jié)點(diǎn)的完全二叉樹的深度為：trunc(log2 n)+1. trunc(x)為取整函數(shù)。對完全二叉樹的結(jié)點(diǎn)編號：從上到下，每一層從左到右 A F E D C B123656性質(zhì)5：在完全二叉樹中編號為i的結(jié)點(diǎn)1）若有左孩子，則左孩編號為2i2）若有右孩子，則右孩子結(jié)點(diǎn)編號為2i+13）若有雙親，則雙親結(jié)點(diǎn)編號為tru

10、nc(i/2)三二叉樹存貯結(jié)構(gòu) 1 二叉樹的順序結(jié)構(gòu)滿二叉樹或完全二叉樹的順序結(jié)構(gòu)用一組連續(xù)的內(nèi)存單元，按編號順序依次存儲完全二叉樹的元素.例如，用一維數(shù)組bt 存放一棵完全二叉樹，將標(biāo)號為 i 的結(jié)點(diǎn)的數(shù)據(jù)元素存放在分量 bti-1中。存儲位置隱含了樹中的關(guān)系，樹中的關(guān)系是通過完全二叉樹的性質(zhì)實(shí)現(xiàn)的。例如，bt5（i=6)的雙親結(jié)點(diǎn)標(biāo)號是k=trunc(i/2)=3,雙親結(jié)點(diǎn)所對應(yīng)的數(shù)組分量btk-1=bt2順序結(jié)構(gòu)圖示 0 1 2 3 6 5 6 7 m-1 A B C D E F A F E D C B123656非完全二叉樹的順序結(jié)構(gòu) 按完全二叉樹的形式補(bǔ)齊二叉樹所缺少的那些結(jié)點(diǎn)，對二

11、叉樹結(jié)點(diǎn)編號,將二叉樹原有的結(jié)點(diǎn)按編號存儲到內(nèi)存單元“相應(yīng)”的位置上。但這種方式對于畸形二叉樹，浪費(fèi)較大空間。 A F G E D C B1672653810 A F G E D C B90 1 2 3 6 5 6 7 8 9 10 m-1A B C D E 0 F 0 0 G2 二叉鏈表 二叉鏈表中每個結(jié)點(diǎn)包含三個域：數(shù)據(jù)域、左指針域、右指針域 A F E D C BStruct node int data; struct node *lch,*rch;二叉鏈表圖示 D A B C E F A F E D C B3 三叉鏈表 三叉鏈表中每個結(jié)點(diǎn)包含四個域：數(shù)據(jù)域、雙親指針域、左指針域、右指針

12、域Struct node int data; struct node *lch,*rch,*parent;ABDFEC6.3 二叉樹的遍歷 一. 二叉樹的遍歷方法 二. 遍歷的遞歸算法 三. 遍歷的非遞歸算法6.3 二叉樹的遍歷遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn)，而且每個結(jié)點(diǎn)僅被訪問一次。訪問：含義很廣，可以是對結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。 遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。 如何訪問二叉樹的每個結(jié)點(diǎn)， 而且每個結(jié)點(diǎn)僅被訪問一次？二叉樹的遍歷方法 二叉樹由根、左子樹、右子樹三部分組成 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子

13、樹令：L：遍歷左子樹 T：訪問根結(jié)點(diǎn) R：遍歷右子樹 有六種遍歷方法： T L R，L T R，L R T， T R L，R T L，R L T 約定先左后右,有三種遍歷方法： T L R、L T R、L R T ，分別稱為 先序遍歷、中序遍歷、后序遍歷 A F G E D C B 先序遍歷（T L R） 若二叉樹非空 （1）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹； （3）先序遍歷右子樹； 先序遍歷序列：A,B,D,E,G,C,F A F G E D C B例：先序遍歷右圖所示的二叉樹 （1）訪問根結(jié)點(diǎn)A （2）先序遍歷左子樹：即按 T L R 的順序遍歷左子樹 （3）先序遍歷右子樹：即按 T L

14、 R 的順序遍歷右子樹中序遍歷（L T R）若二叉樹非空（1）中序遍歷左子樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷右子樹 中序遍歷序列： D,B,G,E,A,C,F A F G E D C B例：中序遍歷右圖所示的二叉樹 （1）中序遍歷左子樹：即按 L T R 的順序遍歷左子樹 （2）訪問根結(jié)點(diǎn)A （3）中序遍歷右子樹：即按 L T R 的順序遍歷右子樹后序遍歷（L R T）若二叉樹非空（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結(jié)點(diǎn) 后序遍歷序列： D,G,E,B,F,C,A例：后序遍歷右圖所示的二叉樹 （1）后序遍歷左子樹：即按 L R T 的順序遍歷左子樹 （2）后序遍歷右子樹：即按 L

15、 R T 的順序遍歷右子樹 （3）訪問根結(jié)點(diǎn)A A F G E D C B e d c b f a + * / - - 后序遍歷序列：a,b,c,d,-,*,+,e,f,/,- 中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f 先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f例：先序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹 若二叉樹非空 （1）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹 （3）先序遍歷右子樹；二. 遍歷的遞歸算法先序遍歷（T L R）的定義：上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束 基本項(xiàng)（也叫終止項(xiàng)）若二叉樹非空 遞歸項(xiàng) （1）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹

16、（3）先序遍歷右子樹；先序遍歷遞歸算法 void prev (NODE *root) if (root!=NULL) printf(“%d,”, root-data)； prev(root-lch); prev(root-rch); 先序序列為 + * a b c / d e稱為前綴表達(dá)式 a + * / d / -root e b c a*(b-c)+d/e2 中序遍歷遞歸算法void mid (NODE *root) if (root!=NULL) prev(root-lch); printf(“%d,”, root-data)； prev(root-rch); 中序序列為 a * b c

17、+ d / e稱為中綴表達(dá)式你能寫出后序遍歷遞歸算法了吧 a + * / d / -root e b c a*(b-c)+d/e3 后序遍歷遞歸算法void prev (NODE *root) if (root!=NULL) prev(root-lch); prev(root-rch); printf(“%d,”, root-data)； 后序序列為 a b c * d e / + 稱為后綴表達(dá)式 a + * / d / -root e b c a*(b-c)+d/e對每個結(jié)點(diǎn)，在訪問完后，沿其左鏈一直訪問下來，直到左鏈為空，這時(shí)，所有已被訪問過的結(jié)點(diǎn)進(jìn)棧。然后結(jié)點(diǎn)出棧，對于每個出棧結(jié)點(diǎn)，即表

18、示該結(jié)點(diǎn)和其左子樹已被訪問結(jié)束，應(yīng)該訪問該結(jié)點(diǎn)的右子樹。（1）當(dāng)前指針指向根結(jié)點(diǎn)。（2）打印當(dāng)前結(jié)點(diǎn)，當(dāng)前指針指向其左孩子并進(jìn)棧，重復(fù)（2），直到左孩子為NULL（3）依次退棧，將當(dāng)前指針指向右孩子（6）若棧非空或當(dāng)前指針非NULL，執(zhí)行（2）；否則結(jié)束。三. 二叉樹遍歷的非遞歸算法遞歸算法邏輯清晰、易懂，但在實(shí)現(xiàn)時(shí)，由于函數(shù)調(diào)用棧層層疊加，效率不高，故有時(shí)考慮非遞歸算法。 1 先序遍歷（T L R）的非遞歸算法。先序遍歷的非遞歸算法void prev (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) p

19、rintf(“%d,”, root-data) ; nodetop=p;top+; p=p-lch; if (top0) top - -; p=nodetop; p=p-rch; while(top0|p!=NULL); d b e a * - / c + d b a * - / c + erootpnode 6563210topprintf(“%c,”, root-data);+nodetop=p;top+;topp=p-lch;pprintf(“%c,”, root-data);*nodetop=p;top+;topp=p-lch;pprintf(“%c,”, root-data) ;an

20、odetop=p;top+;topp=p-lch;pif (top0)top - -;topp=nodetop;pp=p-rch;ptopppprintf(“%c,”, root-data) ;-nodetop=p;top+;topp=p-lch;pbtopptop - -; p=nodetop; p=p-rch;topptoppppcprintf(“%c,”, root-data)nodetop=p;top+;topp=p-lch;ptop - -;topp=nodetop;pp=p-rchtopppprintf(“%d,”, root-data) ;/nodetop=p;top+;topp

21、=p-lch;d中序遍歷的非遞歸算法void min (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) nodetop=p;top+;p=p-lch; if (top0) top - -; p=nodetop; printf(“%d,”, root-data) ; p=p-rch; while(top0|p!=NULL); d b e a * - / c + a + * / d / -root e b c a*(b-c)+d/e+*a-bc/de + * a b - c d / e + / e d *-

22、+ b + c由遍歷序列恢復(fù)二叉樹任意一棵二叉樹結(jié)點(diǎn)的先序序列和中序序列都是唯一的。反過來，若已知結(jié)點(diǎn)的先序序列和中序序列，能否確定這棵二叉樹呢 ? 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹 如果同時(shí)已知二叉樹的中序序列“cbdaegf”，則會如何？ 二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根a b c d e f gc b d a e g f例如:aab bccddeeffggabcdefg先序序列中序序列6.4 遍歷的應(yīng)用 遍歷是二叉樹的基本操作：二叉樹許多操作可在遍歷過程中完成，本節(jié)再例子舉幾個二叉樹遍歷應(yīng)用實(shí)例。例1

23、 編寫 求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法輸入：二叉樹的二叉鏈表結(jié)果：二叉樹的葉子結(jié)點(diǎn)個數(shù) D A B C E F rootvoid leaf(NODE *root)/采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹的葉子結(jié)點(diǎn)/的個數(shù)。本算法在先序遍歷二叉樹的過程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個數(shù)/第一 次被調(diào)用時(shí)，n=0 與先序遍歷算法比較一下！if(root!=NULL) if(root-lch= =NULL&root-rch= =NULL) n=n+1; /若root所指結(jié)點(diǎn)為葉子, 則累加 leaf(root-lch); leaf(root-rch); 比較先序遍歷算法和計(jì)算葉子結(jié)點(diǎn)算法，有什么相同

24、和不同？結(jié)構(gòu)類似函數(shù)名不同訪問結(jié)點(diǎn)時(shí)調(diào)用printf( )訪問結(jié)點(diǎn)時(shí)統(tǒng)計(jì)葉子結(jié)點(diǎn)的個數(shù)void prev (NODE *root) if (root!=NULL) printf(“%d,”, root-data)； prev(root-lch); prev(root-rch); void leaf(NODE *root) if(root!=NULL) if(root-lch= =NULL&root-rch= =NULL) n=n+1; leaf(root-lch); leaf(root-rch); 例2 建立二叉鏈表 輸入：二叉樹的先序序列 結(jié)果：二叉樹的二叉鏈表 A F E D C B*A

25、B D * F * * * C E * * *基本思想：輸入（在空子樹處添加字符*的二叉樹的）先序序列（設(shè)每個元素是一個字符）按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接輸入（在空子樹處添加空格字符的二叉樹的）先序序列（設(shè)每個元素是一個字 符）按先序遍歷的順序，建立二叉鏈表，并將該二叉鏈表根結(jié)點(diǎn)指針賦給rootNODE *create_tree(NODE *root) char ch; scanf (&ch); if (ch= = ) root=NULL; / 若ch= = * 則root=NULL返回 else / 若ch! = * root=( NODE * )malloc

26、(sizeof(NODE) ; root-data = ch; / 建立（根）結(jié)點(diǎn) root-lch=create_tree(root-lch); /構(gòu)造左子樹鏈表，并將左子樹根結(jié)點(diǎn)指針賦 給（根）結(jié)點(diǎn) 的左孩子域 root-rch=create_tree(root-rch); /構(gòu)造右子樹鏈表，并將右子樹根/結(jié)點(diǎn)指針賦給（根）結(jié)點(diǎn) 的右孩子域 return (root); D A B C E F T 先序序列：A B D F C E（在空子樹處添加*的二叉樹的）先序序列： A B D F C E A F E D C B A F E D C B小 結(jié) 1 二叉樹： 或?yàn)榭諛洌蛴筛皟深w不相交

27、的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹； 2 二叉樹即可以用順序結(jié)構(gòu)存儲，也可用鏈?zhǔn)浇Y(jié)構(gòu)存儲；3 遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn)，每個結(jié)點(diǎn)僅被訪問一次。 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹，本課程介紹了三種遍歷算法：先序遍歷、中序遍歷、后序遍歷；6.5 線索二叉樹 何謂線索二叉樹？ 線索鏈表的遍歷算法 如何建立線索鏈表？一、何謂線索二叉樹？遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個線性序列。ABCDEFGHK例如:先序序列: A B C D E F G H K中序序列: B D C A H G K F E后序序列: D C B H K G F E A在序列中

28、，除第一個結(jié)點(diǎn)外，每個結(jié)點(diǎn)有且僅有一個直接前驅(qū)結(jié)點(diǎn)；除最后一個結(jié)點(diǎn)外，每個結(jié)點(diǎn)有且僅有一個直接后繼結(jié)點(diǎn)。但是，二叉樹中每個結(jié)點(diǎn)在這個序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹的存儲結(jié)構(gòu)中并沒有反映出來，只能在對二叉樹遍歷的動態(tài)過程中得到這些信息。 一個具有n個結(jié)點(diǎn)的二叉樹若采用二叉鏈表存儲結(jié)構(gòu)，在2n個指針域中只有n1個指針域是用來存儲結(jié)點(diǎn)孩子的地址，而另外n1個指針域存放的都是NULL。因此，可以利用某結(jié)點(diǎn)空的左指針域（lchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接前驅(qū)結(jié)點(diǎn)的存儲地址，利用結(jié)點(diǎn)空的右指針域（rchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接后繼結(jié)點(diǎn)的存儲地址；對于那些非空的

29、指針域，則仍然存放指向該結(jié)點(diǎn)左、右孩子的指針。這樣，就得到了一棵線索二叉樹。指向該線性序列中的“前驅(qū)”和 “后繼” 的指針，稱作“線索”與其相應(yīng)的二叉樹，稱作 “線索二叉樹”包含 “線索” 的存儲結(jié)構(gòu)，稱作 “線索鏈表”A B C D E F G H K D C B E 對線索鏈表中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中增加兩個標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹， 且左標(biāo)志域的值為“指針 Link”； 否則，Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“線索 Thread” 。若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹， 且右標(biāo)志域的

30、值為 “指針 Link”；否則，rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“線索 Thread”。 如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;線索鏈表的類型描述： typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索二、線索鏈表的遍歷算法: for

31、( p = firstNode(T); p; p = Succ(p) ) Visit (p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。例如: 對中序線索化鏈表的遍歷算法 中序遍歷的第一個結(jié)點(diǎn) ？ 在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn)。若無右子樹，則為后繼線索所指結(jié)點(diǎn)；否則為對其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個結(jié)點(diǎn)。void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根結(jié)點(diǎn) while (p != T)

32、 / 空樹或遍歷結(jié)束時(shí)，p=T while (p-LTag=Link) p = p-lchild; / 第一個結(jié)點(diǎn) while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 訪問后繼結(jié)點(diǎn) p = p-rchild; / p進(jìn)至其右子樹根 / InOrderTraverse_Thr 在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre, 并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(qū)。三、如何建立線索鏈表？void InThreading(BiThrTr

33、ee p) if (p) / 對以p為根的非空二叉樹進(jìn)行線索化 InThreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅(qū)線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驅(qū) InThreading(p-rchild); / 右子樹線索化 / if / InThreadingStatus InOrderThreading(BiThrTree &Thrt, Bi

34、ThrTree T) / 構(gòu)建中序線索鏈表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加頭結(jié)點(diǎn) return OK; / InOrderThreading if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 處理最后一個結(jié)點(diǎn) pre-RTa

35、g = Thread; Thrt-rchild = pre; 6.7 樹的應(yīng)用 6.7.1 二叉排序樹 6.7.2 哈夫曼樹以及應(yīng)用1. 二叉排序樹的定義 一種特殊的二叉樹，它的每個結(jié)點(diǎn)數(shù)據(jù)中都有一個關(guān)鍵值，并有如下性質(zhì)：對于每個結(jié)點(diǎn)，1)如果其左子樹非空，則左子樹的所有結(jié)點(diǎn)的關(guān)鍵值都小于該結(jié)點(diǎn)的關(guān)鍵值；2)如果其右子樹非空，則右子樹的所有結(jié)點(diǎn)的關(guān)鍵值都大于該結(jié)點(diǎn)的關(guān)鍵值。 6045671256758二叉排序樹6.7.1 二叉排序樹二叉排序樹的優(yōu)點(diǎn):查找效率高，增、刪方便；對二叉排序樹進(jìn)行中序遍歷，將得到一個按結(jié)點(diǎn)關(guān)鍵值遞增有序的中序線性序列；被廣泛用來作為動態(tài)查找的數(shù)據(jù)結(jié)構(gòu)。中序遍歷二叉樹：

36、4512860675675中序遍歷序列：8 12 4556606775有序序列 2. 二叉排序樹的查找（靜態(tài)查找） 在二叉排序樹中進(jìn)行查找，將要查找的值從樹根開始比較，1）若與根的關(guān)鍵值相等，則查找成功；2）若比根值小，則到左子樹找；3）若比根值大，則到右子樹找，直到查找成功或查找子樹為空（失?。?045671256758二叉排序樹假設(shè)要查找關(guān)鍵字的值=56的結(jié)點(diǎn)：查找成功！二叉排序樹的查找遞歸算法：NODE *search(int x, NODE *root) if (root= =NULL)|(root-data= =x) return(root); if(root-datarch);

37、else return(search(x,root-lch);3. 二叉排序樹的插入和生成 插入：二叉排序樹的插入是一個動態(tài)的查找過程。例如，要插入關(guān)鍵值 x ，首先在樹中查找，若不存在則插入。因?yàn)椴檎沂〉那闆r是一直查到查找路徑的末端，仍然不存在x ，則待插入結(jié)點(diǎn)必作為樹葉插入樹中。6045671256758二叉排序樹例如:x=50不存在!50二叉排序樹的插入遞歸算法：NODE *insert(NODE *p, NODE *root) if (root= =NULL) return(p); if(p-datadata) root-lch=insert(p,root-lch); else ro

38、ot-rch=insert(p,root-rch); return(root);main( ) int aMAX=65,26,53,65,12,26,90; NODE *new, *head=NULL; int i; for (i=0;idata=ai; new-lch=new-rch=NULL; head=insert(new,head); 6. 二叉排序樹的刪除 刪除：首先查找到要刪除的結(jié)點(diǎn),刪除后二叉排序樹的中序序列仍然是按關(guān)鍵值遞增有序。分三種情況:（1）若*p結(jié)點(diǎn)是葉子，則直接刪除。即：將雙親結(jié)點(diǎn)指向它的指針設(shè)置為空。（f-rch=NULL)6065671256758刪除樹葉結(jié)點(diǎn)*p

39、fp6. 二叉排序樹的刪除 6045671256758刪除單分支結(jié)點(diǎn)*pfp（2）若*p為單分支結(jié)點(diǎn)，則只需用它唯一子樹的根去繼承它的位置。(f-lch=p-rch)56606. 二叉排序樹的刪除 63456726587512刪除兩分支結(jié)點(diǎn)*pfp（3）若*p為雙分支結(jié)點(diǎn)，用左子樹中序遍歷的最后一個結(jié)點(diǎn)(左子樹的最右結(jié)點(diǎn)）替換*p。首先，沿*p的左子樹的右鏈，查找到右指針域?yàn)榭盏慕Y(jié)點(diǎn)*s，然后用*s的數(shù)據(jù)替換*p的數(shù)據(jù)，最后,刪除*s結(jié)點(diǎn)35305060ss_f6360二叉排序樹的刪除結(jié)點(diǎn)算法：NODE *del( NODE *root, int x) NODE *p, *f, *s, *s_

40、f; if (root= =NULL) return(root); f=NULL; p=root; while(p!=NULL & p-data!=x) if(p-datax) if (p-lch!=NULL) f=p;p=p-lch; else break; else if(p-rch!=NULL)f=p;p=p-rch; else break; if( p= =NULL| p-data!=x) return(root); if (p=root)return;/*刪除葉子結(jié)點(diǎn)*/if (p-lch= =NULL & p-rch=NULL) if( f=NULL) free(p); retur

41、n(NULL); if ( f-lch=p) f-lch=NULL; else f-rch=NULL; free(p);return(root); /*刪除單分支結(jié)點(diǎn)*/if (p-lch=NULL) if (f=NULL) root=prch;free(p);return(root); if(f-lch= =p) f-lch=p-rch; else f-rch=p-rch; free(p);return(root); if (p-rch=NULL) if (f=NULL) root=p-lch;free(p);return(root); if(f-lch= =p) f-lch=p-lch;

42、else f-rch=p-lch; free(p);return(root); /*刪除雙分支結(jié)點(diǎn)*/s-f=p;s=p-lch; while (s-rch!=NULL) s_f=s;s=s-rch; p-data=s-data; if(s-lch=NULL) s_f-rch=NULL; else s_f-rch=s-lch; free(s);return(root);1 . 哈夫曼樹的概念路徑：從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的若干個分支;路徑長度：路徑上的分支數(shù)目稱為路徑長度；結(jié)點(diǎn)的路徑長度：從根到該結(jié)點(diǎn)的路徑長度樹的路徑長度：樹中所有葉子結(jié)點(diǎn)的路徑長度之和；一般記為PL。6.7.2 哈夫曼樹(

43、最優(yōu)樹）及應(yīng)用116.7.2 哈夫曼樹(最優(yōu)樹）及應(yīng)用在結(jié)點(diǎn)數(shù)相同的條件下，完全二叉樹是路徑最短的二叉樹。73256688325766非完全二叉樹完全二叉樹PL=2*1+3*2+2*3=14 PL=2*1+4*2+1*3=13結(jié)點(diǎn)的權(quán)：根據(jù)應(yīng)用的需要可以給樹的結(jié)點(diǎn)賦權(quán)值；結(jié)點(diǎn)的帶權(quán)路徑長度：從根到該結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)權(quán)的乘積；樹的帶權(quán)路徑長度=樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑之和；通常記作 WPL= wi Li BDACAC DB7 5 2 66752哈夫曼樹：假設(shè)有n個權(quán)值(w1 , w2 , , wn )，構(gòu)造有n個葉子結(jié)點(diǎn)的嚴(yán)格二叉樹，每個葉子結(jié)點(diǎn)有一個 wi 作為它的權(quán)值。則帶權(quán)路徑長度

44、最小的嚴(yán)格二叉樹稱為哈夫曼樹。BDACC AD7 5 2 66752AC DB6752CA BD6752BWPL=7*2+5*2+2*2+6*2=36WPL=7*1+5*2+2*3+6*3=35WPL=7*3+5*3+2*1+6*2=66WPL=7*1+5*2+2*3+6*3=35要使二叉樹WPL小,就須在構(gòu)造樹時(shí), 將權(quán)值大的結(jié)點(diǎn)靠近根.2. 應(yīng)用舉例在求得某些判定問題時(shí)，利用哈夫曼樹獲得最佳判定算法。例 編制一個將百分制轉(zhuǎn)換成五分制的程序。 最直觀的方法是利用if語句來的實(shí)現(xiàn)?？捎枚鏄涿枋雠卸ㄟ^程。a 80a 90不及格良好中等及格優(yōu)秀a 60a 70按圖的判定過程:轉(zhuǎn)換一個分?jǐn)?shù)所需的比

45、較次數(shù)= 從根到對應(yīng)結(jié)點(diǎn)的路徑長度轉(zhuǎn)換10000個分?jǐn)?shù)所需的總比較次數(shù)= 10000 (0.05 1+0.15 2+0.6 3+0.3 6+0.1 6） 二叉樹的帶權(quán)路徑長度a 80a 90不及格良好中等及格優(yōu)秀a 60a 70分?jǐn)?shù) 0-59 60-69 70-79 80-89 90-100比例數(shù) 0.05 0.15 0.60 0.30 0.10設(shè)有10000個百分制分?jǐn)?shù)要轉(zhuǎn)換，設(shè)學(xué)生成績在5個等級以上的分布如下：構(gòu)造以分?jǐn)?shù)的分布比例為權(quán)值的哈夫曼樹3 .哈夫曼樹的構(gòu)造構(gòu)造哈夫曼樹的步驟：1)根據(jù)給定的n個權(quán)值 ，構(gòu)造n棵只有一個根結(jié)點(diǎn)的二叉樹， n個權(quán)值分別是這些二叉樹根結(jié)點(diǎn)的權(quán)。設(shè)F是由這

46、n棵二叉樹構(gòu)成的集合2)在F中選取兩棵根結(jié)點(diǎn)樹值最小的樹作為左、右子樹，構(gòu)造一顆新的二叉樹，置新二叉樹根的權(quán)值=左、右子樹根結(jié)點(diǎn)權(quán)值之和；3)從F中刪除這兩顆樹，并將新樹加入F；4)重復(fù) 2)、3)，直到F中只含一顆樹為止；603060155 101530例：構(gòu)造以W=（5，15，60，30，10）為權(quán)的哈夫曼樹。305 1015606030155 1015603030155 1015哈夫曼樹中權(quán)值小的結(jié)點(diǎn)離根遠(yuǎn)權(quán)值大的結(jié)點(diǎn)離根近601003060155 1015306.7.2 哈夫曼編碼 在進(jìn)行數(shù)據(jù)通訊時(shí)，涉及數(shù)據(jù)編碼問題。所謂數(shù)據(jù)編碼就是數(shù)據(jù)與二進(jìn)制字符串的轉(zhuǎn)換。例如：郵局發(fā)電報(bào)： 例 要

47、傳輸?shù)脑臑锳BACCDA等長編碼 A：00 B：01 C：10 D：11發(fā)送方：將ABACCDA 轉(zhuǎn)換成 00010010101100接收方：將 00010010101100 還原為 ABACCDA不等長編碼 A：0 B：00 C：1 D：01發(fā)送方：將ABACCDA 轉(zhuǎn)換成 000011010接收方：000011010 轉(zhuǎn)換成 原文 電文（二進(jìn)制字符串） 原文發(fā)送方接收方AAAACCDABBCCDAA的編碼是B的前綴設(shè) A：0 B：110 C：10 D：111發(fā)送方：將ABACCDA 轉(zhuǎn)換成 0110010101110 總長度是13所得的譯碼是唯一的前綴編碼： 任何字符編碼不是其它字符編碼

48、的前綴可利用二叉樹設(shè)計(jì)前綴編碼：例 某通訊系統(tǒng)只使用8種字符a、b、c、d、e、f、g、h，其使用頻率分別為0.05, 0.29, 0.07, 0.08, 0.16, 0.23, 0.03, 0.11，利用二叉樹設(shè)計(jì)一種不等長編碼： 1）構(gòu)造以 a、b、c、d、e、f、g、h為葉子結(jié)點(diǎn)的二叉樹； 2）將該二叉樹所有左分枝標(biāo)記1，所有右分枝標(biāo)記0； 3）從根到葉子結(jié)點(diǎn)路徑上標(biāo)記作為葉子結(jié)點(diǎn)所對應(yīng)字符的編碼；a: 0110b: 10c: 1110d: 1111e: 110f: 00g: 0111h: 01029195862100158 7 3 5 8 11231629構(gòu)造以字符使用頻率作為權(quán)值的哈

49、夫曼樹如何得到使二進(jìn)制串總長最短編碼？返回目錄 6.6 樹和森林 樹的存儲結(jié)構(gòu) 樹和二叉樹的轉(zhuǎn)換 樹的遍歷 森林 一樹的存貯結(jié)構(gòu)1 雙親表示法采用一組連續(xù)空間存儲樹的結(jié)點(diǎn),通過保存每個結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置，表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。 雙親表示類型定義 #define MAX 100struct node char data; int parent; /雙親位置域; typedef struct node NODE;NODE treeMAX;IACBHGFED 9 A 0 B 1 C 1 D 2 E 2 F 3 G 5 H 5 I 50123656789data parent 結(jié)點(diǎn)數(shù)2、孩子表示法通過保存每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置，表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。 A B C D E F G H I