上傳人：鼠***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：沃**（實(shí)名認(rèn)證）

IP屬地：上海

IP屬地：上海 上傳時(shí)間：2022-06-23 格式：PPTX 頁(yè)數(shù)：212 大?。?.07MB 積分：20 舉報(bào) 版權(quán)申訴

1、樹樹: : 是是 n(n0) n(n0) 個(gè)結(jié)點(diǎn)的有限集合個(gè)結(jié)點(diǎn)的有限集合(jh)(jh)。如果該集合如果該集合(jh)(jh)為空，稱為空樹。在任意為空，稱為空樹。在任意一棵非空樹中一棵非空樹中: :ABCDEFKLGHIJM樹的定義樹的定義(dngy)1)1) 有且僅有一個(gè)特定有且僅有一個(gè)特定(tdng)(tdng)的稱為根結(jié)點(diǎn)的稱為根結(jié)點(diǎn) ( root ) ( root ) 的結(jié)點(diǎn)的結(jié)點(diǎn); ;2)2) 2) 2) 其他結(jié)點(diǎn)可分為若干個(gè)其他結(jié)點(diǎn)可分為若干個(gè)互不相交的子集互不相交的子集, ,而且每一而且每一個(gè)子集本身又是一棵樹個(gè)子集本身又是一棵樹, ,稱稱為根的子樹。為根的子樹。遞歸定義遞歸

2、定義第1頁(yè)/共212頁(yè)第一頁(yè)，共212頁(yè)。結(jié)點(diǎn)結(jié)點(diǎn)(ji din):(ji din):結(jié)點(diǎn)結(jié)點(diǎn)(ji din)(ji din)的度的度: :樹的度樹的度: :葉子葉子(y zi)(y zi)結(jié)點(diǎn)結(jié)點(diǎn): :分支結(jié)點(diǎn)分支結(jié)點(diǎn): :數(shù)據(jù)元素?cái)?shù)據(jù)元素+ +若干指向子樹的若干指向子樹的分支分支結(jié)點(diǎn)分支的個(gè)數(shù)結(jié)點(diǎn)分支的個(gè)數(shù), ,即子樹的數(shù)目即子樹的數(shù)目如：如：A A的度的度-3-3；B B的度的度-2-2；K K的度的度-0-0；樹中所有結(jié)點(diǎn)的度的最大值樹中所有結(jié)點(diǎn)的度的最大值 如：樹的度為如：樹的度為3 3；度為零的結(jié)點(diǎn)，也稱終端結(jié)點(diǎn)度為零的結(jié)點(diǎn)，也稱終端結(jié)點(diǎn)如例：如例：K K，L L，F(xiàn) F，G G，

3、M M，I I，J J為終端結(jié)點(diǎn)為終端結(jié)點(diǎn)度大于零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)如例：如例：A,B,C,D,EA,B,C,D,E基本術(shù)語(yǔ)基本術(shù)語(yǔ)612345第2頁(yè)/共212頁(yè)第二頁(yè)，共212頁(yè)。森林：是森林：是 m m（m0m0）棵互不相交）棵互不相交(xingjio)(xingjio)的樹的集合的樹的集合ArootBEFKLCGDHIJMF第3頁(yè)/共212頁(yè)第三頁(yè)，共212頁(yè)。線性結(jié)構(gòu)線性結(jié)構(gòu)(jigu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)(jigu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素(yun s)(yun s) ( (無(wú)前驅(qū)無(wú)前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無(wú)前驅(qū)無(wú)前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼無(wú)后繼)

4、多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無(wú)后繼無(wú)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )第4頁(yè)/共212頁(yè)第四頁(yè)，共212頁(yè)。7.2 7.2 二叉樹二叉樹第5頁(yè)/共212頁(yè)第五頁(yè)，共212頁(yè)。 二叉樹或?yàn)榭諛?；或是由一個(gè)二叉樹或?yàn)榭諛?；或是由一個(gè)(y )根結(jié)點(diǎn)加上兩棵分別稱為左和右根結(jié)點(diǎn)加上兩棵分別稱為左和右子樹的、互不交的二叉樹組成。子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)(ji din)左子樹右子樹EF特點(diǎn)：特點(diǎn)：1 1）每個(gè)結(jié)點(diǎn)）每個(gè)結(jié)點(diǎn)最多只有兩最多只有兩棵子樹；棵

5、子樹；2 2）兩顆子樹）兩顆子樹有左右有左右(zuyu)(zuyu)之分，順序之分，順序不能換。不能換。第6頁(yè)/共212頁(yè)第六頁(yè)，共212頁(yè)。二叉樹的五種二叉樹的五種(w zhn)基本形態(tài)：基本形態(tài)：N空樹空樹只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)(ji din)NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右左右(zuyu)子樹子樹均不為均不為空樹空樹第7頁(yè)/共212頁(yè)第七頁(yè)，共212頁(yè)。特殊特殊(tsh)的二叉樹：滿二叉樹的二叉樹：滿二叉樹滿二叉樹：指的是深度滿二叉樹：指的是深度(shnd)為為k且含且含有有2k-1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。123456789 10 11 12 13

6、 14 151234567深度深度(shnd)為為3，節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)數(shù)=23-1=7深度為深度為4，節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)數(shù)=24-1=15特點(diǎn)：特點(diǎn)：1）每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)；）每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)； 2）葉子結(jié)點(diǎn)都在最后一層。）葉子結(jié)點(diǎn)都在最后一層。第8頁(yè)/共212頁(yè)第八頁(yè)，共212頁(yè)。完全二叉樹：樹中所含的完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din)和滿二叉樹中編號(hào)為和滿二叉樹中編號(hào)為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)(ji din)一一對(duì)應(yīng)。一一對(duì)應(yīng)。12345612345612345特點(diǎn)：特點(diǎn)：1）除了最下一層外其余）除了最下一層外其余(qy)各層都是各層都是滿的；滿的

7、； 2）最下一層的結(jié)點(diǎn)都集中在該層的左側(cè)。）最下一層的結(jié)點(diǎn)都集中在該層的左側(cè)。12345678 9 10特殊特殊(tsh)的二叉樹：完全二叉樹的二叉樹：完全二叉樹第9頁(yè)/共212頁(yè)第九頁(yè)，共212頁(yè)。 性質(zhì)性質(zhì)(xngzh) 1 ：滿二叉樹的第：滿二叉樹的第 i 層上有層上有2i-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i1)用歸納法證明用歸納法證明(zhngmng)： 歸納基：歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明歸納證明(zhngmng)：i = 1 時(shí)，只有一個(gè)(y )根結(jié)點(diǎn)， 2i-1 = 20 = 1；假設(shè)第假設(shè)第j j層有層有2 2j-1j-1結(jié)點(diǎn)，命題成立結(jié)點(diǎn)，命題成立; ;第第j層的每個(gè)結(jié)點(diǎn)都有層

8、的每個(gè)結(jié)點(diǎn)都有2個(gè)結(jié)點(diǎn)，則第個(gè)結(jié)點(diǎn)，則第(j+1)層上的結(jié)點(diǎn)數(shù)層上的結(jié)點(diǎn)數(shù)=2*2j-1=2j=2(j+1)-1。二叉樹的性質(zhì)二叉樹的性質(zhì)1234 5 6 7第10頁(yè)/共212頁(yè)第十頁(yè)，共212頁(yè)。 性質(zhì)性質(zhì)(xngzh) 1的推論：在二叉樹的第的推論：在二叉樹的第 i 層上至多有層上至多有2i-1 個(gè)個(gè)結(jié)點(diǎn)結(jié)點(diǎn) (i1)。第11頁(yè)/共212頁(yè)第十一頁(yè)，共212頁(yè)。性質(zhì)性質(zhì) 2 ：深度為：深度為 k 的滿二叉樹共有的滿二叉樹共有(n yu) 2k-1 個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k1）。）。證明證明(zhngmng)： 基于上一條性質(zhì)基于上一條性質(zhì)(xngzh)，深度為，深度為 k 的滿的滿二叉樹上的結(jié)點(diǎn)

9、數(shù)為：二叉樹上的結(jié)點(diǎn)數(shù)為： 20+21+ +2k-1 = 2k-1性質(zhì)性質(zhì) 2的推論的推論 ：深度為深度為 k 的二叉樹上最多的二叉樹上最多有有 2k-1 個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k1）第12頁(yè)/共212頁(yè)第十二頁(yè)，共212頁(yè)。 性質(zhì)性質(zhì) 3 ：設(shè)二叉樹葉子：設(shè)二叉樹葉子(y zi)結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n0，度為度為 2 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2 ，則必存在關(guān)系式：，則必存在關(guān)系式： n0 = n2+1。性質(zhì)性質(zhì)(xngzh)4(xngzh)4：具有：具有 n n 個(gè)結(jié)點(diǎn)的完全二個(gè)結(jié)點(diǎn)的完全二叉樹的深度為叉樹的深度為 log2nlog2n +1 +1第13頁(yè)/共212頁(yè)第十三頁(yè)，共212頁(yè)。性質(zhì)性質(zhì) 5

10、5 ：對(duì)于具有：對(duì)于具有n n個(gè)結(jié)點(diǎn)的完全二叉樹，如果個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照按照(nzho)(nzho)從上到下和從左至右的順序?qū)纳系较潞蛷淖笾劣业捻樞驅(qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從二叉樹中的所有結(jié)點(diǎn)從 1 1 至至 n n進(jìn)行編號(hào)，則對(duì)進(jìn)行編號(hào)，則對(duì)于任意的序號(hào)為于任意的序號(hào)為 i i 的結(jié)點(diǎn)，有：的結(jié)點(diǎn)，有：若若 i1 i1，則序號(hào)為，則序號(hào)為i i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為i/2i/2；如果；如果i=1i=1，則該結(jié)點(diǎn)是根，無(wú)雙親，則該結(jié)點(diǎn)是根，無(wú)雙親; ; 若若 2i=n 2in 2in 則該結(jié)點(diǎn)無(wú)左孩子；則該結(jié)點(diǎn)無(wú)左孩子； 若若 2i+1=n 2i+1n2i+1

11、n，則序號(hào)為，則序號(hào)為i i的結(jié)點(diǎn)無(wú)右孩子的結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)。結(jié)點(diǎn)。第14頁(yè)/共212頁(yè)第十四頁(yè)，共212頁(yè)。二叉樹的存儲(chǔ)二叉樹的存儲(chǔ)(cn ch)結(jié)構(gòu)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)(cn (cn ch)ch)表示表示一、一、 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示(biosh)第15頁(yè)/共212頁(yè)第十五頁(yè)，共212頁(yè)。 用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素元素, , 以結(jié)點(diǎn)存儲(chǔ)的相對(duì)位置表示結(jié)點(diǎn)之間的以結(jié)點(diǎn)存儲(chǔ)的相對(duì)位置表示結(jié)點(diǎn)之間的關(guān)系關(guān)系(gun x)(gun x)。 為了正確地反映結(jié)點(diǎn)之間的關(guān)系為了正確地反映結(jié)點(diǎn)之間的關(guān)系(gun

12、 (gun x),x),任何二叉樹都必須按照完全二叉樹的形任何二叉樹都必須按照完全二叉樹的形式來(lái)存儲(chǔ)式來(lái)存儲(chǔ). . 這種存儲(chǔ)方式對(duì)某些二叉樹的存儲(chǔ)這種存儲(chǔ)方式對(duì)某些二叉樹的存儲(chǔ)會(huì)造成存儲(chǔ)空間的浪費(fèi)。會(huì)造成存儲(chǔ)空間的浪費(fèi)。順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)(jigu)第16頁(yè)/共212頁(yè)第十六頁(yè)，共212頁(yè)。 在高級(jí)語(yǔ)言中在高級(jí)語(yǔ)言中, ,可以可以(ky)(ky)用一維數(shù)組用一維數(shù)組來(lái)描述這種順序存儲(chǔ)結(jié)構(gòu)。來(lái)描述這種順序存儲(chǔ)結(jié)構(gòu)。例如：例如：ABCDFABCDE完全(wnqun)二叉樹的順序存儲(chǔ)存儲(chǔ)位置123456數(shù)據(jù)元素ABCDEF一般(ybn)二叉樹的存儲(chǔ)存儲(chǔ)位置123456數(shù)據(jù)元素ABCDNOTES

13、:代表空元素 第17頁(yè)/共212頁(yè)第十七頁(yè)，共212頁(yè)。#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)二叉樹的最大結(jié)點(diǎn)數(shù)TElemType SqBiTreeMAX_TREE_SIZE; / 1號(hào)單元號(hào)單元(dnyun)存儲(chǔ)根結(jié)點(diǎn)存儲(chǔ)根結(jié)點(diǎn)例如例如(lr): A B D C E F 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEF第18頁(yè)/共212頁(yè)第十八頁(yè)，共212頁(yè)。練習(xí)練習(xí)(linx)(linx)：1已知一棵完全二叉樹有已知一棵完全二叉樹有64個(gè)葉子結(jié)點(diǎn)，則該樹可能達(dá)個(gè)葉子結(jié)點(diǎn)，則該樹可能達(dá)到的最大深度為（）到的最大深度為（） A7B

14、8 C9D102若一棵二叉樹有若一棵二叉樹有11個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)是（）的結(jié)點(diǎn)個(gè)數(shù)是（） A10B11 C12D不確定的不確定的已知一棵二叉樹的順序存儲(chǔ)序列為：已知一棵二叉樹的順序存儲(chǔ)序列為：aebfcd，則：，則： 1）e的左孩子的左孩子(hi zi)是哪個(gè)結(jié)點(diǎn)？右孩子是哪個(gè)結(jié)點(diǎn)？右孩子(hi zi)是哪是哪個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？ 2）d的雙親是哪個(gè)結(jié)點(diǎn)？的雙親是哪個(gè)結(jié)點(diǎn)？答案：B答案：A答案：1）沒(méi)有(mi yu)左孩子；右孩子是f；2）b；第19頁(yè)/共212頁(yè)第十九頁(yè)，共212頁(yè)。練習(xí)練習(xí)(linx)(linx)：3 3假設(shè)一棵二叉樹的順序存儲(chǔ)

15、結(jié)構(gòu)如圖所示，請(qǐng)假設(shè)一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)如圖所示，請(qǐng)回答下列問(wèn)題：回答下列問(wèn)題：（1 1）哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？）哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？（2 2）哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？）哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？（3 3）哪些結(jié)點(diǎn)是）哪些結(jié)點(diǎn)是H H的祖先？的祖先？（4 4）哪些結(jié)點(diǎn)是）哪些結(jié)點(diǎn)是B B的兄弟的兄弟(xingd)(xingd)？（5 5）樹的深度是多少？）樹的深度是多少？ A B C D E H 1 2 3 4 5 6 7 8 9 10 11 12 13 14A AD,HD,HA,C,EA,C,EC C4 4第20頁(yè)/共212頁(yè)第二十頁(yè)，共212頁(yè)。二、二叉樹的鏈?zhǔn)酱鎯?chǔ)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)(cn ch)(

16、cn ch)表示表示1. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表第21頁(yè)/共212頁(yè)第二十一頁(yè)，共212頁(yè)。二叉鏈結(jié)構(gòu)二叉鏈結(jié)構(gòu) 每個(gè)結(jié)點(diǎn)包含三個(gè)域每個(gè)結(jié)點(diǎn)包含三個(gè)域: : 數(shù)據(jù)域和左右指針數(shù)據(jù)域和左右指針(zhzhn)(zhzhn)域域, ,如下表所示如下表所示lchilddatarchildADEBCF root二叉鏈表二叉鏈表第22頁(yè)/共212頁(yè)第二十二頁(yè)，共212頁(yè)。struct BTNode datatype data; struct BTNode *lchild, *rchild; Typedef BTNode *BTree;將二叉樹類型BTree定義為指向二叉鏈表結(jié)點(diǎn)(ji d

17、in)結(jié)構(gòu)的指針類型。lchild data rchild結(jié)點(diǎn)結(jié)點(diǎn)(ji din)結(jié)構(gòu)結(jié)構(gòu):C 語(yǔ)言的類型(lixng)描述如下:第23頁(yè)/共212頁(yè)第二十三頁(yè)，共212頁(yè)。三叉鏈表三叉鏈表 三叉鏈表結(jié)構(gòu)：每個(gè)結(jié)點(diǎn)除包含數(shù)據(jù)域和左右指三叉鏈表結(jié)構(gòu)：每個(gè)結(jié)點(diǎn)除包含數(shù)據(jù)域和左右指針域外針域外,還包含一個(gè)指向還包含一個(gè)指向(zh xin)其雙親結(jié)點(diǎn)的指其雙親結(jié)點(diǎn)的指針域。針域。rootADEBCF parent lchild data rchild第24頁(yè)/共212頁(yè)第二十四頁(yè)，共212頁(yè)。 struct TriTNode / 結(jié)點(diǎn)結(jié)構(gòu) datatype data; struct TriTNode

18、*lchild, *rchild; / 左右孩子(hi zi)指針 struct TriTNode *parent; /雙親指針 typedef TriTNode *TriTree;parent lchild data rchild結(jié)點(diǎn)結(jié)點(diǎn)(ji din)結(jié)構(gòu)結(jié)構(gòu):C 語(yǔ)言的類型描述(mio sh)如下:第25頁(yè)/共212頁(yè)第二十五頁(yè)，共212頁(yè)。v 在這兩種結(jié)構(gòu)中在這兩種結(jié)構(gòu)中, ,只需要給出指向根結(jié)點(diǎn)只需要給出指向根結(jié)點(diǎn)的指針的指針, ,即可訪問(wèn)即可訪問(wèn)(fngwn)(fngwn)樹中任意一個(gè)樹中任意一個(gè)結(jié)點(diǎn)結(jié)點(diǎn). .v 盡管在二叉表中無(wú)法由結(jié)點(diǎn)直接找到其雙盡管在二叉表中無(wú)法由結(jié)點(diǎn)直接找到

19、其雙親，但由于二叉鏈表的結(jié)構(gòu)靈活，操作方便，親，但由于二叉鏈表的結(jié)構(gòu)靈活，操作方便，對(duì)于一般情況下的二叉樹，甚至比順序存儲(chǔ)對(duì)于一般情況下的二叉樹，甚至比順序存儲(chǔ)結(jié)構(gòu)還節(jié)省空間。因此二叉鏈表是最常用的結(jié)構(gòu)還節(jié)省空間。因此二叉鏈表是最常用的二叉樹存儲(chǔ)方式。二叉樹存儲(chǔ)方式。v 今后，我們今后，我們(w men)(w men)所涉及到的二叉所涉及到的二叉樹，如不加特別說(shuō)明均采用二叉鏈表存儲(chǔ)。樹，如不加特別說(shuō)明均采用二叉鏈表存儲(chǔ)。說(shuō)明說(shuō)明(shumng)第26頁(yè)/共212頁(yè)第二十六頁(yè)，共212頁(yè)。二叉樹的遍歷二叉樹的遍歷(bin l)第27頁(yè)/共212頁(yè)第二十七頁(yè)，共212頁(yè)。 遍歷二叉樹是指按照一定遍

20、歷二叉樹是指按照一定(ydng)(ydng)的規(guī)律對(duì)二叉樹中的每個(gè)結(jié)的規(guī)律對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)，訪問(wèn)且僅訪問(wèn)一次的處理過(guò)程。點(diǎn)，訪問(wèn)且僅訪問(wèn)一次的處理過(guò)程?！霸L問(wèn)訪問(wèn)”的含義可以很廣，如：求結(jié)點(diǎn)的度、的含義可以很廣，如：求結(jié)點(diǎn)的度、層次、輸出結(jié)點(diǎn)的信息層次、輸出結(jié)點(diǎn)的信息(xnx)等等。等等。第28頁(yè)/共212頁(yè)第二十八頁(yè)，共212頁(yè)。“遍歷遍歷”是任何類型均有的操作，是任何類型均有的操作， 1）對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑）對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)橐驗(yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼每個(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。，故不需要另加討論。 2）而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有

21、兩個(gè)）而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在后繼，則存在(cnzi)如何遍歷即按什么樣的搜如何遍歷即按什么樣的搜索路徑進(jìn)行遍歷的問(wèn)題。索路徑進(jìn)行遍歷的問(wèn)題。 第29頁(yè)/共212頁(yè)第二十九頁(yè)，共212頁(yè)。 對(duì)對(duì)“二叉樹二叉樹”而言，可以把二叉樹看成由三個(gè)基而言，可以把二叉樹看成由三個(gè)基本單元組成本單元組成: 根結(jié)點(diǎn)根結(jié)點(diǎn)(D)、左子樹、左子樹(L)、右子樹、右子樹(R),并且并且規(guī)定左子樹上的所有結(jié)點(diǎn)應(yīng)該在右子樹上的所有結(jié)點(diǎn)規(guī)定左子樹上的所有結(jié)點(diǎn)應(yīng)該在右子樹上的所有結(jié)點(diǎn)之前之前(zhqin)被訪問(wèn)被訪問(wèn),由此可以得到三種遍歷順序由此可以得到三種遍歷順序:先先序遍歷序遍歷(DLR)、中序

22、遍歷、中序遍歷(LDR)、后序遍歷、后序遍歷(LRD)先序的遍歷先序的遍歷(bin l)算法算法中序的遍歷中序的遍歷(bin l)算法算法后后序的遍歷算法遍歷算法遍歷算法第30頁(yè)/共212頁(yè)第三十頁(yè)，共212頁(yè)。 若二叉樹為空樹，則空操作；否則若二叉樹為空樹，則空操作；否則(fuz)， （1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)； （2）先序遍歷左子樹；）先序遍歷左子樹； （3）先序遍歷右子樹。）先序遍歷右子樹。先序的遍歷先序的遍歷(bin l)算法：算法：ABCDEGF先序遍歷(bin l)：A B D E G C F第31頁(yè)/共212頁(yè)第三十一頁(yè)，共212頁(yè)。 若二叉樹為空樹，則空操作；否則，若二叉樹

23、為空樹，則空操作；否則， （1）中序遍歷左子樹；）中序遍歷左子樹； （2）訪問(wèn)）訪問(wèn)(fngwn)根結(jié)點(diǎn)；根結(jié)點(diǎn)； （3）中序遍歷右子樹。）中序遍歷右子樹。中序的遍歷中序的遍歷(bin l)算法：算法：ABCDEGF中序遍歷(bin l)：D B G E A C F第32頁(yè)/共212頁(yè)第三十二頁(yè)，共212頁(yè)。 若二叉樹為空樹，則空操作若二叉樹為空樹，則空操作(cozu)；否則，；否則， （1）后序遍歷左子樹；）后序遍歷左子樹； （2）后序遍歷右子樹；）后序遍歷右子樹； （3）訪問(wèn)根結(jié)點(diǎn)。）訪問(wèn)根結(jié)點(diǎn)。后序的遍歷后序的遍歷(bin l)算法：算法：ABCDEGF后序(hu x)遍歷：D G E

24、B F C A第33頁(yè)/共212頁(yè)第三十三頁(yè)，共212頁(yè)。ABCEDGFH先序遍歷(bin l)：中序遍歷(bin l)：后序(hu x)遍歷：A B D G C E H FB G D A H E C FG D B H E F C A例題例題第34頁(yè)/共212頁(yè)第三十四頁(yè)，共212頁(yè)。中序遍歷(bin l)：先序遍歷(bin l)：后序(hu x)遍歷：a + b * c d e / f- + a * b c d / e fa b c d - * + e f / -例題例題+/e*bfacd( ( )第35頁(yè)/共212頁(yè)第三十五頁(yè)，共212頁(yè)。根據(jù)根據(jù)(gnj)遍歷序列畫遍歷序列畫二叉樹二叉樹

25、 由一棵二叉樹的先序序列和中序序列或中由一棵二叉樹的先序序列和中序序列或中序和后序能夠唯一序和后序能夠唯一(wi y)確定一棵二叉樹。確定一棵二叉樹。 先序序列先序序列(xli)：A B C D E F G H I 中序序列中序序列(xli)：B C A E D G H F IABDECFIGH第36頁(yè)/共212頁(yè)第三十六頁(yè)，共212頁(yè)。練習(xí)練習(xí)(linx)已知一棵二叉樹的先序序列已知一棵二叉樹的先序序列(xli)和中序序列和中序序列(xli)，請(qǐng)畫出該二叉樹。，請(qǐng)畫出該二叉樹。 先序序列先序序列(xli)：A B C D E F G H I J 中序序列中序序列(xli)：C B E D F

26、 A H G J IABGHDIJCEF第37頁(yè)/共212頁(yè)第三十七頁(yè)，共212頁(yè)。樹和森林樹和森林(snln) (snln) 第38頁(yè)/共212頁(yè)第三十八頁(yè)，共212頁(yè)。樹的存儲(chǔ)樹的存儲(chǔ)(cn ch)結(jié)構(gòu)結(jié)構(gòu)一、雙親一、雙親(shungqn)(shungqn)表表示法示法二、孩子二、孩子(hi zi)(hi zi)鏈表鏈表表示法表示法三、樹的二叉鏈表三、樹的二叉鏈表( (孩子孩子- -兄弟）兄弟） 存儲(chǔ)表示法存儲(chǔ)表示法第39頁(yè)/共212頁(yè)第三十九頁(yè)，共212頁(yè)。樹的雙親樹的雙親(shungqn)(shungqn)表示法表示法 以一組連續(xù)空間以一組連續(xù)空間( (數(shù)組數(shù)組) )存儲(chǔ)樹的結(jié)點(diǎn)存儲(chǔ)樹

27、的結(jié)點(diǎn), ,同時(shí)在每同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親(shungqn)(shungqn)結(jié)點(diǎn)在數(shù)組中的位置結(jié)點(diǎn)在數(shù)組中的位置. . typedef struct datatype data; int parent; Node; typedef Node Tree MAX_NODE_NUM #define MAX_NODE_NUM 100C C語(yǔ)言的類型語(yǔ)言的類型(lixng)(lixng)描述描述: :ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent第40頁(yè)/共212頁(yè)第四十頁(yè)，共212頁(yè)。孩

28、子孩子(hi zi)表示法表示法 存儲(chǔ)每個(gè)結(jié)點(diǎn)及其孩子信息存儲(chǔ)每個(gè)結(jié)點(diǎn)及其孩子信息(xnx)(xnx)。每個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)形成該結(jié)點(diǎn)的孩子鏈表。的所有孩子結(jié)點(diǎn)形成該結(jié)點(diǎn)的孩子鏈表。ABCDEFG0 A1 B 2 C 3 D 4 E 5 F 6 G 65123孩子孩子(hi zi)(hi zi)鏈表鏈表0 A1 B 2 C 3 D 4 E 5 F 6 G -1 0 0 0 2 2 46 4 5 1 2 3帶雙親的孩子鏈表帶雙親的孩子鏈表4第41頁(yè)/共212頁(yè)第四十一頁(yè)，共212頁(yè)。孩子孩子(hi zi)-(hi zi)-兄弟表示法兄弟表示法struct TreeNode datat

29、ype data; struct TreeNode *children; struct TreeNode *next;typedef struct Tree;C C語(yǔ)言的類型語(yǔ)言的類型(lixng)(lixng)描述描述: :結(jié)點(diǎn)結(jié)點(diǎn)(ji din)結(jié)構(gòu)結(jié)構(gòu): 每個(gè)結(jié)點(diǎn)除其信息域外，再增加兩個(gè)分別指向該每個(gè)結(jié)點(diǎn)除其信息域外，再增加兩個(gè)分別指向該結(jié)點(diǎn)的結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)和和下一個(gè)兄弟結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)的指針。的指針。childrendatanext第42頁(yè)/共212頁(yè)第四十二頁(yè)，共212頁(yè)。孩子孩子(hi zi)-(hi zi)-兄弟表示法兄弟表示法第43頁(yè)/共212頁(yè)第四十三頁(yè)

30、，共212頁(yè)。樹、森林樹、森林(snln)(snln)與二與二叉樹叉樹之間的轉(zhuǎn)換之間的轉(zhuǎn)換 第44頁(yè)/共212頁(yè)第四十四頁(yè)，共212頁(yè)。 將樹轉(zhuǎn)換成二叉樹的方法將樹轉(zhuǎn)換成二叉樹的方法加線：在兄弟之間加一連線加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除(q ch)其與其其與其余孩子之間的關(guān)系余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定(ydng)為空第45頁(yè)/共212頁(yè)

31、第四十五頁(yè)，共212頁(yè)。將二叉樹轉(zhuǎn)換成樹將二叉樹轉(zhuǎn)換成樹加線：若加線：若p p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p p的右孩子，右的右孩子，右孩子的右孩子，孩子的右孩子，沿分支找到的所有沿分支找到的所有(suyu)(suyu)右孩子，右孩子，都與都與p p的雙親用線連起來(lái)的雙親用線連起來(lái)抹線：抹掉原二叉樹中雙親與右孩子之間的連線抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI第46頁(yè)/共212頁(yè)第四十六頁(yè)，共212頁(yè)。AB

32、CDEFGHIABCDEFGHI 樹的先序遍歷和后序遍歷可以借用二叉樹樹的先序遍歷和后序遍歷可以借用二叉樹的先序遍歷和中序遍歷的算法的先序遍歷和中序遍歷的算法(sun f)來(lái)實(shí)現(xiàn)來(lái)實(shí)現(xiàn)。先序序列先序序列(xli)(xli)：ABEFGCDHIABEFGCDHI后序序列后序序列(xli)(xli)：EFGBCHIDAEFGBCHIDA先序序列先序序列(xli)(xli)：ABEFGCDHIABEFGCDHI中序序列中序序列(xli)(xli)：EFGBCHIDAEFGBCHIDA后序序列后序序列(xli)(xli)：GFEIHDCBAGFEIHDCBA樹樹二叉樹二叉樹第47頁(yè)/共212頁(yè)第四十七

33、頁(yè)，共212頁(yè)。森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點(diǎn)用線相連(xin lin)以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第48頁(yè)/共212頁(yè)第四十八頁(yè)，共212頁(yè)。二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點(diǎn)抹線：將二叉樹中根結(jié)點(diǎn)(ji din)與其右孩子連線，及與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹變成孤立的二叉樹還原：將孤立的二叉樹還原成樹還原：將孤立的二叉樹還

34、原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第49頁(yè)/共212頁(yè)第四十九頁(yè)，共212頁(yè)。 由此，樹和森林的各種操作(cozu)均可與二叉樹的各種操作(cozu)相對(duì)應(yīng)。 應(yīng)當(dāng)注意的是，和樹對(duì)應(yīng)的二叉樹，其左、右子樹的概念(ginin)已改變?yōu)椋?左是孩子，右是兄弟第50頁(yè)/共212頁(yè)第五十頁(yè)，共212頁(yè)。 把下面把下面(xi mian)的樹轉(zhuǎn)化成二叉樹。的樹轉(zhuǎn)化成二叉樹。ABCDEFGHI練習(xí)練習(xí)(linx)KLJABCDEFGHIJKL第51頁(yè)/共212頁(yè)第五十一頁(yè)，共212頁(yè)。哈夫曼樹與哈夫曼編碼哈夫曼樹與哈夫曼編碼(bin m)(bin m) 第

35、52頁(yè)/共212頁(yè)第五十二頁(yè)，共212頁(yè)。相關(guān)相關(guān)(xinggun)概概念念樹的路徑樹的路徑(ljng)長(zhǎng)度定義為：長(zhǎng)度定義為： 樹中每個(gè)結(jié)點(diǎn)的路徑樹中每個(gè)結(jié)點(diǎn)的路徑(ljng)長(zhǎng)度之和。長(zhǎng)度之和。 結(jié)點(diǎn)的路徑長(zhǎng)度定義為：結(jié)點(diǎn)的路徑長(zhǎng)度定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支(fnzh)的數(shù)的數(shù)目。目。 樹的帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度定義為：定義為： 樹中所有樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度長(zhǎng)度之和之和 WPL(T) = wklk (對(duì)所有葉子結(jié)點(diǎn)對(duì)所有葉子結(jié)點(diǎn)) 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度定義為：定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度與結(jié)點(diǎn)

36、上權(quán)從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。的乘積。第53頁(yè)/共212頁(yè)第五十三頁(yè)，共212頁(yè)。設(shè)：a,b,c,d 的權(quán)值為： a=7, b=5, c=2, d=4;下面三棵不同的樹的帶權(quán)路徑(ljng)長(zhǎng)度為： (7+5+4+2）*2=36 (7+5)*3+4*2+2=46 7+5*2+(2+4)*3=35 第3棵樹的帶權(quán)路徑(ljng)長(zhǎng)度最小。第54頁(yè)/共212頁(yè)第五十四頁(yè)，共212頁(yè)。最優(yōu)二叉樹 :設(shè)有n個(gè)權(quán)值w1,w2,w3,.,wn,構(gòu)造有n個(gè)葉子結(jié)點(diǎn)的二叉樹,每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi,則其中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱為最優(yōu)二叉樹(赫夫曼樹).赫夫曼樹的應(yīng)用：判定問(wèn)題。 例

37、：將學(xué)生(xu sheng)的百分制變成五級(jí)分制：設(shè)學(xué)生(xu sheng)的成績(jī)分布在五個(gè)等級(jí)上是不均勻的。分?jǐn)?shù)分?jǐn)?shù)0-590-5960-6960-6970-7970-7980-8980-8990-10090-100五級(jí)分制五級(jí)分制不及格不及格及格及格中中良良優(yōu)優(yōu)比例比例0.050.050.150.150.40.40.30.30.10.1第55頁(yè)/共212頁(yè)第五十五頁(yè)，共212頁(yè)。二、如何二、如何(rh)構(gòu)造最優(yōu)樹構(gòu)造最優(yōu)樹赫夫曼算法:(1)根據(jù)給定的n個(gè)權(quán)值w1,w2,w3,.,wn構(gòu)成n棵二叉樹的集合F=T1,T2,T3,.,Tn,其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn),其左右子

38、樹均為空.(2)在集合F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造(guzo)一棵新的二叉樹,新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和.(3)在集合F中刪除這兩棵樹,同時(shí)將新得到的二叉樹加入F中.(4)重復(fù)步驟(2)、(3),直到F中只含一棵樹為止,這棵樹就是一棵赫夫曼樹.第56頁(yè)/共212頁(yè)第五十六頁(yè)，共212頁(yè)。9例如(lr): 已知權(quán)值 W= 5, 6, 2, 9, 7 56275276976713952795271667132900001111000111100101(1)根據(jù)給定的n個(gè)權(quán)值w1,w2,w3,.,wn構(gòu)成n棵二叉樹的集合F=T1,T2,T3,.,Tn,其中

39、每棵二叉樹Ti中只有一個(gè)(y )帶權(quán)為wi的根結(jié)點(diǎn),其左右子樹均為空.(2)在集合(jh)F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹,新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和.(3)在集合F中刪除這兩棵樹,同時(shí)將新得到的二叉樹加入F中.(4)重復(fù)步驟(2)、(3),直到F中只含一棵樹為止,這棵樹就是一棵赫夫曼樹.第57頁(yè)/共212頁(yè)第五十七頁(yè)，共212頁(yè)。哈夫曼編碼 通信中的信息傳遞問(wèn)題：在傳遞信息時(shí)，如何在能夠識(shí)別的前提下，使傳遞的字符數(shù)最少。例： 電報(bào)中的報(bào)文 “ABACCDA” 四個(gè)字符的編碼問(wèn)題。兩位編碼： 00 01 10 11 如果用不同長(zhǎng)度的編碼：

40、例用 0 1 00 01 前綴編碼:對(duì)于不等長(zhǎng)編碼,若任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴,則這種編碼稱為前綴編碼.前綴編碼使得字符編碼的平均長(zhǎng)度最短.赫夫曼編碼是一種前綴編碼.赫夫曼編碼的方法(fngf): (1)把字符出現(xiàn)的頻率作為權(quán)值,根據(jù)這些權(quán)值構(gòu)造一棵赫夫曼樹. (2)約定在赫夫曼樹中,左分支表示字符0,右分支表示字符1,則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上的分支字符組成的字符串即為該葉子結(jié)點(diǎn)字符的編碼.第58頁(yè)/共212頁(yè)第五十八頁(yè)，共212頁(yè)。 已知某系統(tǒng)在通信聯(lián)系中只可能出現(xiàn)已知某系統(tǒng)在通信聯(lián)系中只可能出現(xiàn)8 8種字符：種字符：abcdefghabcdefgh，其概率分別為，其

41、概率分別為0.050.05，0.290.29， 0.07 0.07， 0.080.08， 0.14 0.14，0.23,0.030.23,0.03，0.110.11，試據(jù)此構(gòu)造哈，試據(jù)此構(gòu)造哈夫曼樹，要求：夫曼樹，要求： 1) 1)畫出構(gòu)造哈夫曼樹的過(guò)程畫出構(gòu)造哈夫曼樹的過(guò)程(guchng)(guchng)； 2) 2)求每個(gè)字符的哈夫曼編碼。求每個(gè)字符的哈夫曼編碼。例題例題(lt)哈夫曼編碼哈夫曼編碼(bin m)：a: 0110b: 10c: 1110d: 1111bfhagcd2311e5291437801000000111111e: 110f: 00g: 0111h: 010第59頁(yè)/

42、共212頁(yè)第五十九頁(yè)，共212頁(yè)。 設(shè)權(quán)值序列為設(shè)權(quán)值序列為8，5，3，4，7，據(jù)此構(gòu)造，據(jù)此構(gòu)造(guzo)一棵哈夫曼一棵哈夫曼樹。畫出構(gòu)造樹。畫出構(gòu)造(guzo)哈夫曼樹過(guò)程。哈夫曼樹過(guò)程。 練習(xí)練習(xí)(linx)58347第60頁(yè)/共212頁(yè)第六十頁(yè)，共212頁(yè)。習(xí)習(xí) 題題 一一第61頁(yè)/共212頁(yè)第六十一頁(yè)，共212頁(yè)。1. 假定( jidng)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。 A15 B16 C17 D472. 深度為5的二叉樹至多有_個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 103. 對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，

43、則_ 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1答案(d n)：B C D第62頁(yè)/共212頁(yè)第六十二頁(yè)，共212頁(yè)。4.二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面(qin mian)，這種說(shuō)法_。 5. A. 正確 B. 錯(cuò)誤6.5. 某二叉樹的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是_。7.A. bdgcefha B. gdbecfha 8.C. bdgaechf D. gdbehfca9.6. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_。10. A. 只有右子樹上

44、的所有結(jié)點(diǎn) 11. B. 只有右子樹上的部分結(jié)點(diǎn)12. C. 只有左子樹上的部分結(jié)點(diǎn) 13. D. 只有左子樹上的所有結(jié)點(diǎn)答案(d n)：A D A第63頁(yè)/共212頁(yè)第六十三頁(yè)，共212頁(yè)。7. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論_是正確的。 A.樹的先根遍歷序列與其(yq)對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B.樹的后根遍歷序列與其(yq)對(duì)應(yīng)的二叉樹的后序遍歷序列相同 C.樹的先根遍歷序列與其(yq)對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D.以上都不對(duì)答案(d n)：A第64

45、頁(yè)/共212頁(yè)第六十四頁(yè)，共212頁(yè)。8. 有一棵樹如圖所示，回答下面的問(wèn)題： 這棵樹的根結(jié)點(diǎn)是_； 這棵樹的葉子(y zi)結(jié)點(diǎn)是_； 結(jié)點(diǎn)k3的度是_； 這棵樹的度是_； 這棵樹的深度是_； 結(jié)點(diǎn)k3的子女是_； 結(jié)點(diǎn)k3的父結(jié)點(diǎn)是_；k1 k7k5k2k4k6k31. k1 k2,k5,k7,k4 2 3 4 k5,k6 k1 第65頁(yè)/共212頁(yè)第六十五頁(yè)，共212頁(yè)。9.9.一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)(jigu)(jigu)，存儲(chǔ)于數(shù)組，存儲(chǔ)于數(shù)組t t中，如圖所示，則該二叉樹的鏈接中，如圖所示，則該二叉樹的鏈接表示形式為表示形式為_ _

46、 _。10. 深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)。至多有_個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開始(kish)），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是_。1 12 23 34 45 56 67 78 89 9 1010 1111 1212 1313 1414 1515 1616 1717 1818 1919 2020 2121e ea af fd dg gc cj jl lh hb beaEfjcdlghb 2 k-1 、 2 k-1 、 2 k-1第66頁(yè)/共212頁(yè)第六十六頁(yè)，共212頁(yè)。11.根據(jù)二叉樹的定義，具有( jyu)三個(gè)結(jié)點(diǎn)的二叉樹有5種不同的形態(tài)，請(qǐng)將它們分別畫出。假設(shè)

47、一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請(qǐng)畫出該樹。aaaaacccccbbbbbbEBEFAECDKGHIJ圖6.12第67頁(yè)/共212頁(yè)第六十七頁(yè)，共212頁(yè)。 以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點(diǎn)權(quán)值，畫出構(gòu)造Huffman樹的每一步圖示，計(jì)算( j sun)其帶權(quán)路徑長(zhǎng)度為。 假設(shè)用于通訊的電文僅有八個(gè)字母(a,b,c,d,e,f,g,h)組成，字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼。62372519181312109674

48、5圖6.16 Huffman樹第68頁(yè)/共212頁(yè)第六十八頁(yè)，共212頁(yè)。習(xí)題習(xí)題(xt)二二1. 三個(gè)結(jié)點(diǎn)( ji din)的二叉樹的基本形態(tài)有 種，三個(gè)結(jié)點(diǎn)( ji din)的樹的基本形態(tài)有 種。2一棵具有64個(gè)結(jié)點(diǎn)( ji din)的完全二叉樹的高度為 。 3. 設(shè)一棵二叉樹的先序遍歷序列為ABCDFEGH，中序遍歷序列為BAFDCGEH，請(qǐng)完成下列要求： 1）畫出該二叉樹； 2）寫出該二叉樹的后序遍歷序列； 3）將該二叉樹轉(zhuǎn)換成森林；第69頁(yè)/共212頁(yè)第六十九頁(yè)，共212頁(yè)。習(xí)題習(xí)題(xt)4. 已知一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下圖所示，圖中“0”表示(biosh)不存在的結(jié)點(diǎn)， 1）

49、畫出該二叉樹； 2）求該二叉樹的先序遍歷序列和中序遍歷序列； 3）將該二叉樹轉(zhuǎn)換成一棵樹。5. 設(shè)字符集為A，B，C，D，E，其對(duì)應(yīng)的權(quán)值為7，5，2，4，9，據(jù)此構(gòu)造哈夫曼樹，要求： 1）畫出構(gòu)造哈夫曼樹過(guò)程； 2）求每個(gè)字符的哈夫曼編碼；A B 0 C D 0 0 E 0 F G第70頁(yè)/共212頁(yè)第七十頁(yè)，共212頁(yè)。本章本章(bn zhn)復(fù)習(xí)要復(fù)習(xí)要點(diǎn)點(diǎn)1、樹的基本概念；、樹的基本概念；結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹的度、葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)、路徑、孩結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹的度、葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)、路徑、孩子、雙親、結(jié)點(diǎn)的層次、樹的深度、兄弟、堂兄弟子、雙親、結(jié)點(diǎn)的層次、樹的深度、兄弟、堂兄弟2、二叉

50、樹的基本概念：二叉樹、滿二叉樹、完全二叉樹；、二叉樹的基本概念：二叉樹、滿二叉樹、完全二叉樹；3、二叉樹的、二叉樹的5個(gè)性質(zhì)；個(gè)性質(zhì)；4、具有、具有3個(gè)結(jié)點(diǎn)的二叉樹的個(gè)結(jié)點(diǎn)的二叉樹的5種形態(tài)；種形態(tài)；3個(gè)結(jié)點(diǎn)的樹的個(gè)結(jié)點(diǎn)的樹的2種的種的形態(tài)；形態(tài)；5、理解二叉樹的順序存儲(chǔ)結(jié)構(gòu)；根據(jù)二叉樹的順序存儲(chǔ)結(jié)、理解二叉樹的順序存儲(chǔ)結(jié)構(gòu)；根據(jù)二叉樹的順序存儲(chǔ)結(jié)構(gòu)畫二叉樹；構(gòu)畫二叉樹；6、二叉樹的先序、中序和后序遍歷；根據(jù)先序和中序遍歷、二叉樹的先序、中序和后序遍歷；根據(jù)先序和中序遍歷的序列畫二叉樹；的序列畫二叉樹；7、構(gòu)造、構(gòu)造(guzo)哈夫曼樹，寫出哈夫曼編碼；哈夫曼樹，寫出哈夫曼編碼；8、樹、森林、

51、二叉樹的互相轉(zhuǎn)換；、樹、森林、二叉樹的互相轉(zhuǎn)換；第71頁(yè)/共212頁(yè)第七十一頁(yè)，共212頁(yè)。 1. B 2. B 3. C 4. C 1. 由于(yuy)二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說(shuō)法_。 A. 正確 B. 錯(cuò)誤 2. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。 A15 B16 C17 D47 3. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有_種。 A. 3 B. 4 C. 5 D. 6 4. 按照二叉樹的定義，具有3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有_種。 A. 5 B. 6 C. 30 D. 32 第72頁(yè)/共2

52、12頁(yè)第七十二頁(yè)，共212頁(yè)。5. C 7. D 8. A 5. 深度為5的二叉樹至多有_個(gè)結(jié)點(diǎn)。 A. 16 B. 32 C. 31 D. 10 7. 對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則_ 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1 8. 任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序_。 A.不發(fā)生(fshng)改變 B.發(fā)生(fshng)改變 C.不能確定 D.以上都不對(duì) 第73頁(yè)/共212頁(yè)第七十三頁(yè)，共212頁(yè)。9. C 10. A 11. D 9. 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那

53、么該二叉樹的后序?yàn)開。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面(qin mian)，這種說(shuō)法_。 A. 正確 B. 錯(cuò)誤 11. 某二叉樹的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是_。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 第74頁(yè)/共212頁(yè)第七十四頁(yè)，共212頁(yè)。1. A 15. B 12. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_。 A. 只有右子樹上的所有

54、結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn) C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn) 15設(shè)a,b為一棵二叉樹上的兩個(gè)(lin )結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 。 Aa在b的右方Ba在b的左方 Ca是b的祖先Da是b的子孫 第75頁(yè)/共212頁(yè)第七十五頁(yè)，共212頁(yè)。 16. 已知某二叉樹的后序(hu x)遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_。 A. acbed B. decab C. deabc D. cedba第76頁(yè)/共212頁(yè)第七十六頁(yè)，共212頁(yè)。 18. 如圖6.3所示的4棵二叉樹，_不是(b shi)完全二叉樹。(A) (B) (

55、C) (D) 圖6.3(A) (B) (C) (D)圖6.3第77頁(yè)/共212頁(yè)第七十七頁(yè)，共212頁(yè)。 第八章第八章 圖圖第78頁(yè)/共212頁(yè)第七十八頁(yè)，共212頁(yè)。第79頁(yè)/共212頁(yè)第七十九頁(yè)，共212頁(yè)。第80頁(yè)/共212頁(yè)第八十頁(yè)，共212頁(yè)。第81頁(yè)/共212頁(yè)第八十一頁(yè)，共212頁(yè)。 第82頁(yè)/共212頁(yè)第八十二頁(yè)，共212頁(yè)。第83頁(yè)/共212頁(yè)第八十三頁(yè)，共212頁(yè)。1235687410796671231516ABDCE60304535804075第84頁(yè)/共212頁(yè)第八十四頁(yè)，共212頁(yè)。 第85頁(yè)/共212頁(yè)第八十五頁(yè)，共212頁(yè)。習(xí)習(xí) 題題1. 在一個(gè)圖中，所有頂點(diǎn)的度

56、數(shù)之和等于所有邊數(shù)的_倍。 A. 1/2 B. 1 C. 2 D. 4 2. 任何一個(gè)無(wú)向連通圖的最小生成樹 。 A.只有(zhyu)一棵B.有一棵或多棵 C.一定有多棵D.可能不存在3. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的_倍。 A. 1/2 B. 1 C. 2 D. 4答案(d n)： C B B第86頁(yè)/共212頁(yè)第八十六頁(yè)，共212頁(yè)。4. 一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有_條邊。 A. n B. n(n-1) C. n(n-1)/2 D. 2n5. 具有4個(gè)頂點(diǎn)的無(wú)向完全圖有_條邊。 A. 6 B. 12 C. 16 D. 206. 具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有(

57、yn yu)_條邊才能確保是一個(gè)連通圖。 A. 5 B. 6 C. 7 D. 87. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要_條邊。 A. n B. n+1 C. n-1 D. n/2CAAC第87頁(yè)/共212頁(yè)第八十七頁(yè)，共212頁(yè)。圖的存儲(chǔ)圖的存儲(chǔ)(cn ch)表示表示一、圖的數(shù)組一、圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲(chǔ)存儲(chǔ)(cn ch)(cn ch)表示表示二、圖的鄰接二、圖的鄰接(ln ji)(ln ji)表存儲(chǔ)表示表存儲(chǔ)表示第88頁(yè)/共212頁(yè)第八十八頁(yè)，共212頁(yè)。圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲(chǔ)存儲(chǔ)(cn ch)(cn ch)表示表示鄰接矩陣表示

58、頂點(diǎn)間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有 n 個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是如下(rxi)的n階方陣。Aij=0 (i,j)E(G)1 (i,j)E(G)第89頁(yè)/共212頁(yè)第八十九頁(yè)，共212頁(yè)。2）有向圖鄰接矩陣不一定對(duì)稱(duchn)；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n3）無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和4）有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和圖的鄰接矩陣的性質(zhì)圖的鄰接矩陣的性質(zhì)(xngzh)(xngzh)1）無(wú)向(w xin)圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向(w xin)圖需存儲(chǔ)空間為n(n+1)/2

59、第90頁(yè)/共212頁(yè)第九十頁(yè)，共212頁(yè)。 網(wǎng)的鄰接矩陣網(wǎng)的鄰接矩陣A ij=wij 若 或 （vi,vj） E(G)0 反之 0 0 1 0 0 30 100 0 0 5 0 0 0 0 0 0 50 0 0 A= 0 0 0 0 0 10 0 0 0 20 0 60 0 0 0 0 0 0 第91頁(yè)/共212頁(yè)第九十一頁(yè)，共212頁(yè)。21435BADCE0111110010100011100010100edgesAdjMatrix0111100000000010100000000edgesAdjMatrix第92頁(yè)/共212頁(yè)第九十二頁(yè)，共212頁(yè)。 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。方法是對(duì)

60、圖中的每一個(gè)頂點(diǎn)建立一個(gè)依附于該頂點(diǎn)的邊的表。而表頭結(jié)點(diǎn)用一順序結(jié)構(gòu)(向量(xingling)）的形式存儲(chǔ)。DBACFE012345 A 1 4 B 0 4 5 C 3 5 D 2 5 E 0 1 F 1 2 30 1 2 3 4 5圖的鄰接表存儲(chǔ)圖的鄰接表存儲(chǔ)(cn ch)表示表示第93頁(yè)/共212頁(yè)第九十三頁(yè)，共212頁(yè)。例題例題(lt)：畫出下圖的鄰接表畫出下圖的鄰接表v1v2v3v4v1 v2 v3 v4 21113 4 4 24 3 第94頁(yè)/共212頁(yè)第九十四頁(yè)，共212頁(yè)。表中，對(duì)每個(gè)頂點(diǎn)表中，對(duì)每個(gè)頂點(diǎn)(dngdin)，鏈接的，鏈接的是指向該頂點(diǎn)是指向該頂點(diǎn)(dngdin)的弧