數(shù)據(jù)結(jié)構(gòu),第六章 二叉樹,課件函試題

1、第六章 二叉樹n6.1 二叉樹的定義與性質(zhì)n6.2 二叉樹的基本操作與存儲(chǔ)實(shí)現(xiàn)n6.3 二叉樹的遍歷n6.4 線索二叉樹n6.5 樹和森林n6.6 哈夫曼樹（赫夫曼樹）6.1.1 二叉樹的基本概念1、定義：二叉樹是由n(n=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。 二叉樹是有序的，將左右子樹顛倒，就形成 一個(gè)不同的二叉樹。二叉樹具有5種基本形態(tài)，如下圖：n6.1 樹的定義與性質(zhì)(a)空二叉樹A(b)左右子樹為空的樹AB(c)右子樹為空的二叉樹AB(d) 左子樹為空的二叉樹ACB (e)包含左右子樹的二叉樹2、二叉樹的相關(guān)

2、概念：l結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。l葉結(jié)點(diǎn):度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)。l分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。一棵樹的結(jié)點(diǎn)除葉子節(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。l左孩子、右孩子、雙親、兄弟：樹中一個(gè)結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子。在二叉樹中，左子樹的根稱為左孩子，右子樹的根稱為右孩子。這個(gè)結(jié)點(diǎn)稱為他孩子結(jié)點(diǎn)的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。l路徑、路徑長(zhǎng)度：如果一棵樹的一串結(jié)點(diǎn)n1,n2,nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的父結(jié)點(diǎn)(1i k)，就把n1,n2,nk稱為一條由n1 nk的路徑，這條路徑的長(zhǎng)度是k-1.l祖先、子孫

3、：在樹中，如果有一條路徑從結(jié)點(diǎn)M到結(jié)點(diǎn)N,那么M就稱為N的祖先，而N就稱為M的子孫。l結(jié)點(diǎn)的層數(shù)：規(guī)定樹的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1.l樹的深度：樹中所有結(jié)點(diǎn)的最大層數(shù)稱為數(shù)的深度。l樹的度：樹中所有結(jié)點(diǎn)度的最大值稱為該樹的度。l滿二叉樹：滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹稱為滿二叉樹。一棵二叉樹稱為滿二叉樹。123456789 10 11 12 13 14 15l完全二叉樹：深度為k的，有n個(gè)結(jié)點(diǎn)

4、的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上到下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i的結(jié)點(diǎn)與滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為滿二叉樹。abcdefghij完全二叉樹的特點(diǎn)：完全二叉樹的特點(diǎn)：(1)(1)葉子結(jié)點(diǎn)只能在層次最大的兩層上出現(xiàn)。葉子結(jié)點(diǎn)只能在層次最大的兩層上出現(xiàn)。(2)(2)對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次 為為m m，則其左分支下的子孫上的最大層次必為，則其左分支下的子孫上的最大層次必為m+1m+1。6.1.2 二叉樹的性質(zhì)n性質(zhì)1：一棵非空二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i=1)。采用歸納法證明此性質(zhì)。 當(dāng)i=

5、1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1=20 =1,命題成立。 現(xiàn)在假定對(duì)所有的j，1=j=1)。 分析：深度為k的二叉樹的最大的結(jié)點(diǎn)為二叉樹中每層上的最大結(jié)點(diǎn)數(shù)之和。 由性質(zhì)1得到每層i上的最大結(jié)點(diǎn)數(shù)為2i-1，那么 所有結(jié)點(diǎn)數(shù)為 = 2k 1k11 - i2in性質(zhì)3：對(duì)任何一棵二叉樹，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0n21。 設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為n1，二叉樹中總結(jié)點(diǎn)數(shù)為N，因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2，所以其結(jié)點(diǎn)總數(shù)：Nn0n1n2 （61) 再看二叉樹中的分支數(shù)，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)進(jìn)入分支，設(shè)B為二叉樹中的分支總數(shù)，則有：NB1。由于這些分支都是由度

6、為1和2的結(jié)點(diǎn)發(fā)出的，所以有： Bn1+2*n2即得，NB1n12*n21 （62)由式（61）和（62）得到： n0+n1+n2=n1+2*n2+1 n0n21n性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 1 符號(hào) x 表示不大于x的最大整數(shù)。 證明：假設(shè)此二叉樹的深度為k，則根據(jù)性質(zhì)2及完全二叉樹的定義得到： 2k-11n2k-1 或 2k-1n2k 取對(duì)數(shù)得到：k1log2nk 因?yàn)閗是整數(shù)。所以有： k 1。logn2 logn2n性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（從第1層到第 +1層，每層從左到右),則對(duì)任一結(jié)點(diǎn)i（1=i1，則其雙親是結(jié)點(diǎn) i/2 。 （2）如

7、果2in，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子是結(jié)點(diǎn)2i。 （3）如果2i1n，則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i1。logn2例1：二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-1例2：一棵高度為5的二叉樹中最少含有_ 個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)；例3：在一棵非空二叉樹中,度為2的結(jié)點(diǎn)個(gè)數(shù)為5,度為0的結(jié)點(diǎn)個(gè)數(shù) ( ) A4 B5 C6 D7例4：9根據(jù)二叉樹的定義可知二叉樹共有（ ）種不同的形態(tài)。(A) 4 (B) 5 (C) 6 (D) 7D531性質(zhì)性質(zhì)2性質(zhì)性質(zhì)1性質(zhì)性質(zhì)3CBn6.2 二叉樹的基本操作與存儲(chǔ)實(shí)現(xiàn)6.2.1二叉

8、樹的存儲(chǔ)1、順序存儲(chǔ)結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu) 它是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。一般它是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。一般是按照二叉樹結(jié)點(diǎn)從上至下，從左到右的順序存儲(chǔ)。是按照二叉樹結(jié)點(diǎn)從上至下，從左到右的順序存儲(chǔ)。ABCDEFGHIJABD EFG HCIJ01345 67892完全二叉樹的順序存儲(chǔ) 對(duì)于一般的二叉樹，如果仍按從上到下和從左到右的順序?qū)渲械慕Y(jié)點(diǎn)順序存儲(chǔ)在一維數(shù)組中，需添加一些不存在的空節(jié)點(diǎn)，使它變成一個(gè)完全二叉樹。ABCEFGJAB D E C F一般二叉樹的順序存儲(chǔ) GABCDEFG 結(jié)論：顯然這種需增加許多空結(jié)點(diǎn)才能將一棵二叉樹改造成一棵完全二叉樹的存儲(chǔ)

9、，會(huì)造成空間的大量浪費(fèi)，不宜采用順序存儲(chǔ)結(jié)構(gòu)，滿二叉樹和完全二叉樹比較適合順序存儲(chǔ)。2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 所謂二叉鏈表存儲(chǔ)結(jié)構(gòu)，是指用鏈表來(lái)表示一棵二叉樹，即用鏈來(lái)指示元素的邏輯關(guān)系。通常有下面兩種形式：（1）二叉鏈表存儲(chǔ) 鏈中每個(gè)結(jié)點(diǎn)由3個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來(lái)給出結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)：lchild data rchild 存儲(chǔ)二叉樹經(jīng)常用二叉鏈表法，如下圖：ABC D E F GH lchildDatarchild頭指針bt不帶頭結(jié)點(diǎn)的二叉鏈表 二叉鏈表也可以帶頭結(jié)點(diǎn)的方式存放，如下圖：ABC D E F GH lchildDatarchild頭結(jié)點(diǎn)指針b

10、t帶頭結(jié)點(diǎn)的二叉鏈表 二叉鏈表存儲(chǔ)表示為：typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree 結(jié)點(diǎn)結(jié)構(gòu)：lchild data rchild（2）三叉鏈表存儲(chǔ) 鏈中每個(gè)結(jié)點(diǎn)由4個(gè)域組成，結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)： 其中，data、lchild以及rchild這三個(gè)域和二叉鏈表結(jié)構(gòu)相同；parent域向該結(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。這種結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)；但是相對(duì)于二叉鏈表，三叉鏈表增加了空間開銷。lchild data rch

11、ildparent 三叉鏈表存儲(chǔ) lchild data rchildparentADEBCF typedef struct TriTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): :三叉鏈表的存儲(chǔ)表示可描述為: :6.2.2二叉樹的基本操作及實(shí)現(xiàn)1、二叉樹的基本操作 InitBiTree(bt); /建立一棵空二叉樹建立一棵

12、空二叉樹 Create(x,lbt,rbt); /生成一棵以生成一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域?yàn)楦Y(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹信息，以二叉樹lbt和和rbt為左子樹和右子樹的二叉為左子樹和右子樹的二叉樹。樹。 InsertLChild(bt, x, parent); /將數(shù)據(jù)信息為將數(shù)據(jù)信息為x的結(jié)的結(jié)點(diǎn)插入到二叉樹點(diǎn)插入到二叉樹bt中作為結(jié)點(diǎn)中作為結(jié)點(diǎn)parent的左孩子結(jié)點(diǎn)。的左孩子結(jié)點(diǎn)。如果原來(lái)結(jié)點(diǎn)如果原來(lái)結(jié)點(diǎn)parent原來(lái)有左孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)原來(lái)有左孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)parent原來(lái)的左孩子結(jié)點(diǎn)作為結(jié)點(diǎn)原來(lái)的左孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x的左孩子結(jié)點(diǎn)。的左孩子結(jié)點(diǎn)。DeleteLChild(bt,

13、parent); /在結(jié)點(diǎn)在結(jié)點(diǎn)bt中刪除結(jié)點(diǎn)中刪除結(jié)點(diǎn)parent的左子樹。的左子樹。 Search(bt，x); /在二叉樹在二叉樹bt中查找數(shù)據(jù)元素中查找數(shù)據(jù)元素x。 Traverse(bt); /按某種方式遍歷二叉樹按某種方式遍歷二叉樹bt的全部結(jié)點(diǎn)。的全部結(jié)點(diǎn)。2、算法實(shí)現(xiàn)、算法實(shí)現(xiàn) int InitBiTree(BiTNode bt); /建立一棵空二叉樹建立一棵空二叉樹 bt = new BiNode; if(!bt) return 0; /沒(méi)有存儲(chǔ)空間返回0 bt-lchild=NULL; bt-rchild=NULL; return 1; /返回成功代碼1main() BiT

14、ree t; Initiate(&t); 二叉樹的遍歷是按照某種順序訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，是每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。 二叉樹的三個(gè)基本組成單元是：根結(jié)點(diǎn)、左子樹和右子樹。 假如以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，遍歷整個(gè)二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為： DLR先（根）序遍歷， LDR中（根）序遍歷， LRD后（根）序遍歷。n6.3二叉樹的遍歷1、先序遍歷二叉樹的操作定義為：若二叉樹為空，則遍歷結(jié)束；否則（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。例如圖中所示的二叉

15、樹表達(dá)式若先序遍歷此二叉樹,按訪問(wèn)結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來(lái),其先序序列為： -+a*b-cd/ef*a/b-dcfe2、中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹。例如圖中所示的二叉樹表達(dá)式按中序遍歷,其中序序列為： a+b*c-d-e/f*a/b-dcfe3、后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問(wèn)根結(jié)點(diǎn)。例如圖中所示的二叉樹表達(dá)式按后序遍歷,其后序序列為： abcd-*+ef/-*a/b-dcfe4、層次遍歷二叉樹的操作定義為： 從二叉樹的第一

16、層開始，從上至下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。例如圖中所示的二叉樹表達(dá)式按層次遍歷,其層次序列為： -+/a*efb-cd*a/b-dcfeABCDEFGHK例如:先序先序序列: 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 當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí),只能找到結(jié)點(diǎn)的左右孩子的信息,而不能在任一序列中找到結(jié)點(diǎn)的前驅(qū)與后繼信息,這種信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到,為了能保存所需的信息,可增加兩個(gè)標(biāo)志域。 若該結(jié)點(diǎn)的左子樹不空，若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子

17、樹，且左標(biāo)志域的值為“指針 Link”或0；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索 Thread”或1 。n6.4線索二叉樹lchildLTagdataRTagrchild 若該結(jié)點(diǎn)的右子樹不空，若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為 “指針 Link”或0；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索 Thread”或1。即: 0 lchild 域指示結(jié)點(diǎn)的左孩子 1 lchild 域指示結(jié)點(diǎn)的前驅(qū) 0 rchild 域指示結(jié)點(diǎn)的右孩子 1 rchild 域指示結(jié)點(diǎn)的后繼 以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)

18、構(gòu),叫做線索鏈表,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索。加上線索的二叉樹稱之為線索二叉樹。n6.4線索二叉樹ltag =rtag= n6.4線索二叉樹ABDCGFE(a)先序線索二叉樹GABDCFE(b)中序線索二叉樹ABDCGFE(c)后序線索二叉樹例如：例如：0100A01B10D11G00C11E11Fbt中序線索二叉樹存儲(chǔ)n6.5 樹和森林6.5.1 樹的定義及相關(guān)術(shù)語(yǔ) 樹是n(n0)個(gè)有限數(shù)據(jù)水元素的集合。當(dāng)n=0時(shí)稱這棵樹為空樹。在一棵非空樹T中 : 有一個(gè)特殊的數(shù)據(jù)元素稱為樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。 若n1,除根結(jié)點(diǎn)以外的其余數(shù)據(jù)元素被分成m(m0) 個(gè)互不相交的集合T1,

19、T2,Tm，其中每一個(gè)集合Ti(1i m)本身又是一棵樹。樹T1,T2,Tm稱為這個(gè)根節(jié)點(diǎn)的子樹。 樹的定義可以描述為二元組的形式 T=(D,R) 其中，D為樹T中結(jié)點(diǎn)的集合，R為樹中結(jié)點(diǎn)之間關(guān)系的集合。n6.5 樹和森林 6.5.1 樹的定義 當(dāng)樹為空樹時(shí)，D=；當(dāng)樹T不為空樹時(shí)，有 D=root DF 其中，D為樹T中結(jié)點(diǎn)的集合，R為樹中結(jié)點(diǎn)之間關(guān)系的集合。DF可由下式表示 DF= D1 D2 Dm且且Di Dj=(ij,1i m, 1j m)當(dāng)樹T中結(jié)點(diǎn)個(gè)數(shù)n 1時(shí)，時(shí)，R=；當(dāng)樹T中結(jié)點(diǎn)個(gè)數(shù)n1時(shí)，有R=,1,2,m,其中，root為樹T的根結(jié)點(diǎn)root的子樹的Ti的根結(jié)點(diǎn)。 如圖是一

20、棵有9個(gè)結(jié)點(diǎn)的樹，即T=A,B,C,H,I,結(jié)點(diǎn)A為樹T的根結(jié)點(diǎn)，除根結(jié)點(diǎn)A的其余結(jié)點(diǎn)分為兩個(gè)不相交的集合T1=B,D,E,F,H,I和T2=C，G，構(gòu)成了結(jié)點(diǎn)A的兩棵子樹，T1和T2本身也分別是一棵樹。例如，子樹T1的根結(jié)點(diǎn)為B，其余結(jié)點(diǎn)又分為3個(gè)不相交的集合：T11=D, T12=F,H,I和T13=E。 T11, , T12, T13構(gòu)成了子樹T1的根結(jié)點(diǎn)B的三棵子樹。如此繼續(xù)分為更小的樹。ABCDFGHIE 從樹的定義和上圖的示例可以看出，樹具有下面兩個(gè)特點(diǎn)： 樹的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。樹中所有結(jié)點(diǎn)可以有零個(gè)或者多個(gè)后繼結(jié)點(diǎn)。由此可知下圖均不是

21、樹結(jié)構(gòu)：ABDECGFABDECGF 6.5.2 相關(guān)術(shù)語(yǔ) (1)有序樹和無(wú)序樹，如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，即若交換了某結(jié)點(diǎn)各子樹的相對(duì)位置，則構(gòu)成不同的樹，稱這棵樹為有序樹；反之，則稱為無(wú)序樹。 (2)森林，零棵或有限棵不相交的樹的集合稱為森林。 任何一棵樹，刪去根結(jié)點(diǎn)就變成了森林。 6.5.3 樹的表示 1、直觀表示法 ABCDEF G H I JMKL2、嵌套集合表示法 所謂嵌套集合是指一些集合的集體，對(duì)于其中任何兩個(gè)集合，或者不相交，或者一個(gè)包含另一個(gè)。用嵌套集合的形式表示樹，就是將根節(jié)點(diǎn)視為一個(gè)大的集合，其若干棵樹、子樹構(gòu)成這個(gè)大集合中若干個(gè)互不相交的子集，如此嵌套

22、下去，即構(gòu)成了一棵樹的嵌套集合表示。 ABKELFDHMJICG嵌套集合表示法嵌套集合表示法ABCDEF G H I JMKL3、廣義表表示法 將根作為由子樹森林組成的表的名字寫在表的左邊，這樣依次將樹表示出來(lái)。ABCDEF G H I JMKL（A(B(E,F(K,L),C(G),D(H,I,J(M)廣義表表示法廣義表表示法4、凹入表示法 每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)矩形，所有結(jié)點(diǎn)的矩形都是右對(duì)齊，根結(jié)點(diǎn)用最長(zhǎng)的矩形表示，同一層的結(jié)點(diǎn)的矩形長(zhǎng)度相同，層次越高，矩形長(zhǎng)度越短。 ABCDEF G H I JMKLABCDEKLFGHIJM凹入表示法凹入表示法6.5.4樹的存儲(chǔ)結(jié)構(gòu) 樹的存儲(chǔ)有多種方式，既可以

23、采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)不但要求存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)信息，還要能唯一反應(yīng)樹中各節(jié)點(diǎn)之間的邏輯關(guān)系。1、雙親表示法 用一組連續(xù)的存儲(chǔ)空間(一維數(shù)組)存儲(chǔ)樹中各個(gè)結(jié) 點(diǎn)，數(shù)組中的一個(gè)元素表示樹中一個(gè)結(jié)點(diǎn)，數(shù)組元素 為結(jié)構(gòu)體類型，其中包括結(jié)點(diǎn)本身的信息和結(jié)點(diǎn)的雙 親結(jié)點(diǎn)在數(shù)組中的序號(hào)。雙親表示法雙親表示法:序號(hào)dataABCDEFGHIparent-100111244ABCDEFGHI一棵樹結(jié)構(gòu)data parent結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)：#define MAX_TREE_SIZE 100 typedef struct PTNode Elem data; int parent;

24、/ 雙親位置域 PTNode; 樹結(jié)構(gòu)樹結(jié)構(gòu):typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;存儲(chǔ)表示如下：存儲(chǔ)表示如下：2、孩子表示法(1)多重鏈表法 每個(gè)結(jié)點(diǎn)包括一個(gè)結(jié)點(diǎn)信息域和多個(gè)指針域，每 個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)，通過(guò)各個(gè)指針 域值反應(yīng)出樹中各節(jié)點(diǎn)之間的邏輯關(guān)系。結(jié)點(diǎn)的指針域的設(shè)置有兩種方法： 每個(gè)結(jié)點(diǎn)指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度數(shù)。 每個(gè)結(jié)點(diǎn)指針域的個(gè)數(shù)等于樹的度。每個(gè)節(jié)點(diǎn)指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度數(shù)。ABCDEABCDEFGHI一棵樹結(jié)構(gòu)每個(gè)節(jié)點(diǎn)指針域的個(gè)數(shù)等于樹的度數(shù)。AF (

25、2)孩子鏈表表示法由一個(gè)與結(jié)點(diǎn)數(shù)一樣大小的一維數(shù)組存放結(jié)點(diǎn)，數(shù)組的每個(gè)元素有兩個(gè)域組成，一個(gè)域用來(lái)存放結(jié)點(diǎn)信息，另一個(gè)域用來(lái)存放指針，這個(gè)指針指向由該結(jié)點(diǎn)孩子組成的單鏈表的首地址。 序號(hào) data firstchildABCDEFGHI12345678typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu)孩子結(jié)點(diǎn)結(jié)構(gòu): :孩子鏈表存儲(chǔ)表示孩子鏈表存儲(chǔ)表示描述為描述為: :child nextdata firstchild typedef struct Elem data; ChildPtr firstchil

26、d; / 孩子鏈的頭指針 CTBox;雙親結(jié)點(diǎn)結(jié)：雙親結(jié)點(diǎn)結(jié)： 3、雙親孩子表示法是將雙親表示法和孩子鏈表法相結(jié)合的結(jié)果。孩子結(jié)點(diǎn)組成單鏈表，同時(shí)用一維數(shù)組順序存儲(chǔ)樹中的各結(jié)點(diǎn)，數(shù)組元素包括結(jié)點(diǎn)本身信息和結(jié)點(diǎn)孩子結(jié)點(diǎn)鏈表頭指針和雙親結(jié)點(diǎn)在數(shù)組中的序號(hào)。 序號(hào)datafirstchildABCDEFGHI12345678parent-100111244 3、孩子兄弟表示法在樹中每個(gè)結(jié)點(diǎn)除其信息域外，再增加兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)的指針。 AFtypedef struct CSNode Elem data; struct CSNode *firstchild, *next

27、sibling; CSNode, *CSTree;結(jié)點(diǎn)存儲(chǔ)表示結(jié)點(diǎn)存儲(chǔ)表示描述為描述為: :結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): : firstchild data nextsibling6.5.5樹、森林與二叉樹的轉(zhuǎn)換 1、樹轉(zhuǎn)換為二叉樹 對(duì)于一棵無(wú)序樹，樹中結(jié)點(diǎn)的各孩子的次序是無(wú)關(guān)緊要的，而二叉樹終結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)是有區(qū)別的。為了避免發(fā)生混淆，約定樹的每一個(gè)孩子結(jié)點(diǎn)按從左到右的順序編號(hào)。如下圖，根結(jié)點(diǎn)A有B、C、D三個(gè)孩子，可以認(rèn)為結(jié)點(diǎn)B為A的第一個(gè)孩子結(jié)點(diǎn)，結(jié)點(diǎn)C為A的第二個(gè)孩子結(jié)點(diǎn)，結(jié)點(diǎn)D為A的第三個(gè)孩子結(jié)點(diǎn)。ABDCEFG 將一棵樹轉(zhuǎn)換為二叉樹的方法如下： (1)樹中所有相鄰兄弟之間加一條連線 (

28、2)對(duì)樹中每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線。 (3)以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之結(jié)構(gòu)層次分明。ABDCEFGABDCEFGABDCEFG 由轉(zhuǎn)換可知，在二叉樹中，左分支上的各由轉(zhuǎn)換可知，在二叉樹中，左分支上的各節(jié)點(diǎn)在原來(lái)的樹中是父子關(guān)子，而右分支上的節(jié)點(diǎn)在原來(lái)的樹中是父子關(guān)子，而右分支上的各結(jié)點(diǎn)在原來(lái)的樹中是兄弟關(guān)系。由于樹的根各結(jié)點(diǎn)在原來(lái)的樹中是兄弟關(guān)系。由于樹的根結(jié)點(diǎn)沒(méi)有兄弟，所以變換后的二叉樹的根結(jié)點(diǎn)結(jié)點(diǎn)沒(méi)有兄弟，所以變換后的二叉樹的根結(jié)點(diǎn)的右孩子必為空。的右孩子必為空。2、森林轉(zhuǎn)換為二叉樹方法描述為： F = ( T1, T2, , Tm )是森林

29、，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B = (root，LB, RB)。l若 F = ，m=0,則 B = ；l若F ，B的根root即為森林中第一棵樹的根ROOT( T1 ) ； B的左子樹LB是從T1中根結(jié)點(diǎn)的子樹森林F1=T11, T12, , T1m 轉(zhuǎn)換成的二叉樹；其右子樹RB是從森林F= T1, T2, , Tm 轉(zhuǎn)換而成的二叉樹。 將森林轉(zhuǎn)換為二叉樹的方法如下： (1)將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹 (2)第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連起來(lái)以后，此時(shí)所得到的二叉樹就是森林轉(zhuǎn)換得到的二叉樹。ABCDFE

30、JGHIKABCDFEJGHIKABCDFEJGHIK3、由二叉樹轉(zhuǎn)換為森林方法描述為：如果B=(root,LB,RB)是一棵二叉樹，則按如下規(guī)則轉(zhuǎn)換成森林F= ( T1, T2, , Tm )l若 B = B = ， 則 F = F = ；l若 B ，則森林中的第一棵樹T1的根ROOT(TROOT(T1 1) )即即是B的根root；T1中根結(jié)點(diǎn)的子樹森林F1是由B的左子樹LB轉(zhuǎn)換而成的森林；F中除T T1 1外其余樹組成的森林F= T1, T2, , Tm 是由B的右子樹RB轉(zhuǎn)換而成的森林。具體方法為：（1）結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子都與該節(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連

31、起來(lái)。（2）刪去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子節(jié)點(diǎn)的連線。（3）整理（1）、（2）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。由二叉樹轉(zhuǎn)換為森林由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換過(guò)程：ABCDFEGHIABCDFEGHI(a)一棵二叉樹(b)加連線ABCDFEGHI(c)去掉與右孩子的連線FEGHIABC D(d)還原后的森林樹的遍歷可有三條搜索路徑樹的遍歷可有三條搜索路徑: :按層次遍歷按層次遍歷: :先根先根( (次序次序) )遍歷遍歷: :后根后根( (次序次序) )遍歷遍歷: : 若樹不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根若樹不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。遍歷各棵子樹。 若樹不空，則

32、先依次后根遍歷各棵子樹，然若樹不空，則先依次后根遍歷各棵子樹，然后訪問(wèn)根結(jié)點(diǎn)。后訪問(wèn)根結(jié)點(diǎn)。 若樹不空，則自上而下自左至右訪問(wèn)樹若樹不空，則自上而下自左至右訪問(wèn)樹中每個(gè)結(jié)點(diǎn)。中每個(gè)結(jié)點(diǎn)。6.5.6樹和森林的遍歷樹和森林的遍歷1 1、樹的遍歷、樹的遍歷先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：A B C E F G D后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：B E G F C D A層次遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：層次遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：A B C D E F G ABCDEFG B C DE F G H I J K1 1森林中第一棵樹的根森林中第一棵樹的根結(jié)點(diǎn)；結(jié)點(diǎn)；2 2森

33、林中第一棵樹的子森林中第一棵樹的子樹森林；樹森林；3 3森林中其它樹構(gòu)成的森森林中其它樹構(gòu)成的森林。林。森林由三部分構(gòu)成：森林由三部分構(gòu)成：2 2、森林的遍歷、森林的遍歷 若森林不空，則若森林不空，則l訪問(wèn)訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)；l先序遍歷先序遍歷森林中第一棵樹的子樹森林；l先序遍歷先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。(1)(1)先序遍歷森林先序遍歷森林即：依次從左至右依次從左至右對(duì)森林中的每一棵樹樹進(jìn)行先先根遍歷根遍歷。(2)(2)中序遍歷中序遍歷若森林不空，則若森林不空，則l中序遍歷中序遍歷森林中第一棵樹的子樹森林；l訪問(wèn)訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)；l中序遍歷中序遍歷森林

34、中(除第一棵樹之外)其 余樹構(gòu)成的森林。即：依次從左至右依次從左至右對(duì)森林中的每一棵樹樹進(jìn)行后根后根遍歷遍歷。 B C DE F G H I J K例如例如： 先序遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：先序遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：B E F C D G H I J K后序遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：后序遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：E F B C I J K H G Dn6.6哈夫曼樹(霍夫曼樹) 6.6.1 哈夫曼樹的基本概念 哈夫曼樹，也稱最優(yōu)二叉樹，是指對(duì)于一組帶有確定權(quán)值的葉子結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹。l路徑長(zhǎng)度路徑長(zhǎng)度：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱

35、做路徑長(zhǎng)度。l樹的路徑長(zhǎng)度樹的路徑長(zhǎng)度：是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。l結(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)上權(quán)的乘積。l樹的帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度：根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和 WPL(T) = wklk (對(duì)所有葉子結(jié)點(diǎn)) 在所有含 n 個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的 m 叉樹中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值帶權(quán)路徑長(zhǎng)度取最小值的樹，稱為“最優(yōu)樹最優(yōu)樹”或者“哈夫曼樹哈夫曼樹”。(a)WPL(T)= 72+52+22+42=36(b)WPL(T)= 73+53+42+21=46(c)WPL(T)= 71+52+23+43

36、=35 如何構(gòu)建最優(yōu)樹？樹的帶全路徑長(zhǎng)度：樹的帶全路徑長(zhǎng)度： 哈夫曼樹依據(jù)這一特點(diǎn)提出了這種方法，基本思想是：n根據(jù)給定的 n 個(gè)權(quán)值 w1, w2, , wn，構(gòu)造 n 棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合F = T1, T2, , Tn。n在 F 中選取其根結(jié)點(diǎn)的權(quán)值為最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；n從F中刪去這兩棵樹，同時(shí)將新建立的二叉樹加入到集合F中；n重復(fù)(2)和(3)兩步，直至 F 中只含一棵樹為止。這棵樹便是哈夫曼樹。9例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 56275

37、2769779613527 7575796713527 757 720952720671329注意：注意： 初始森林中的初始森林中的n n棵二叉樹，每棵樹有一個(gè)孤立的棵二叉樹，每棵樹有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子結(jié)點(diǎn)，它們既是根，又是葉子 n n個(gè)葉子的哈夫曼樹要經(jīng)過(guò)個(gè)葉子的哈夫曼樹要經(jīng)過(guò)n-1n-1次合并，產(chǎn)生次合并，產(chǎn)生n-1n-1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹中共有個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹中共有2n-12n-1個(gè)結(jié)個(gè)結(jié)點(diǎn)。點(diǎn)。 哈夫曼樹是嚴(yán)格的二叉樹，沒(méi)有度數(shù)為哈夫曼樹是嚴(yán)格的二叉樹，沒(méi)有度數(shù)為1 1的分支的分支結(jié)點(diǎn)。結(jié)點(diǎn)。6.6.2 6.6.2 哈夫曼編碼哈夫曼編碼1 1、不

38、等長(zhǎng)編碼、不等長(zhǎng)編碼 這種編碼方式的特點(diǎn)這種編碼方式的特點(diǎn): :每個(gè)字符的編碼每個(gè)字符的編碼長(zhǎng)度相同長(zhǎng)度相同。 設(shè)字符集只含有設(shè)字符集只含有4 4個(gè)字符個(gè)字符A A，B B，C C，D D，用兩位二進(jìn)，用兩位二進(jìn)制表示的編碼分別為制表示的編碼分別為0000，0101，1010，1111。若現(xiàn)在電文為：。若現(xiàn)在電文為：ABACCDAABACCDA，則應(yīng)發(fā)送二進(jìn)制序列：，則應(yīng)發(fā)送二進(jìn)制序列：0001001010110000010010101100，總長(zhǎng)度為總長(zhǎng)度為1414位。當(dāng)接收方接收到這段電文后，將按兩位位。當(dāng)接收方接收到這段電文后，將按兩位一段進(jìn)行譯碼。一段進(jìn)行譯碼。這種編碼的特點(diǎn)這種編碼的

39、特點(diǎn): : 譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。2. 2. 不等長(zhǎng)編碼不等長(zhǎng)編碼 在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡可能地少，在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡可能地少，可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng)的，使用頻度較可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng)的，使用頻度較高高的字符分配一個(gè)相對(duì)比較的字符分配一個(gè)相對(duì)比較短短的編碼，使用頻度較的編碼，使用頻度較低低的字符分配一個(gè)比較的字符分配一個(gè)比較長(zhǎng)長(zhǎng)的編碼。的編碼。例如，可以為例如，可以為A A，B B，C C，D D四個(gè)字符分別分配四個(gè)字符分別分配0 0，0000，1 1，0101，并可將上述電

40、文用二進(jìn)制序列：，并可將上述電文用二進(jìn)制序列：000011010000011010發(fā)送，發(fā)送，其長(zhǎng)度只有其長(zhǎng)度只有9 9個(gè)二進(jìn)制位。個(gè)二進(jìn)制位。 但隨之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后但隨之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后無(wú)法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面無(wú)法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面4 4個(gè)個(gè)0 0是是4 4個(gè)個(gè)A A，1 1個(gè)個(gè)B B、2 2個(gè)個(gè)A A，還是，還是2 2個(gè)個(gè)B B，即譯碼不唯一，因此這種編碼，即譯碼不唯一，因此這種編碼方法不可使用。方法不可使用。3 3、哈夫曼編碼、哈夫曼編碼 利用哈夫曼樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編利用哈夫曼樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所

41、得的碼，并且構(gòu)造所得的哈夫曼編碼哈夫曼編碼是一種是一種最優(yōu)前綴編碼最優(yōu)前綴編碼，即：使所傳即：使所傳電文的總長(zhǎng)度最短電文的總長(zhǎng)度最短。哈夫曼編碼的構(gòu)造方法：哈夫曼編碼的構(gòu)造方法：（1 1）利用字符集中每個(gè)字符的使用頻率作為權(quán)值構(gòu)造）利用字符集中每個(gè)字符的使用頻率作為權(quán)值構(gòu)造一個(gè)哈夫曼樹；一個(gè)哈夫曼樹；（2 2）從根結(jié)點(diǎn)開始，為到每個(gè)葉子結(jié)點(diǎn)路徑上的左分）從根結(jié)點(diǎn)開始，為到每個(gè)葉子結(jié)點(diǎn)路徑上的左分支賦予支賦予0 0，右分支賦予，右分支賦予1 1，并從根到葉子方向形成該葉，并從根到葉子方向形成該葉子結(jié)點(diǎn)的編碼。子結(jié)點(diǎn)的編碼。1152978142331000115582900011184219000

42、11100010011001111110111111010Weight parent lchild rchild 1 2 3 4 5 6 7 8 9101112131415529870000000000000000000000000000000000000000000001423311999178101034151111128191414121313151552942581002101161412130HTHT數(shù)組數(shù)組哈夫曼編碼存儲(chǔ)結(jié)構(gòu)哈夫曼編碼存儲(chǔ)結(jié)構(gòu): :HCHC12345678001111111111111110000000015, 29, 7, 8, 14, 23, 3, 111. 熟

43、練掌握二叉樹的結(jié)構(gòu)特性二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。2. 熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。3. 遍歷二叉樹遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法遞歸算法，靈活運(yùn)用遍靈活運(yùn)用遍歷算法歷算法實(shí)現(xiàn)二叉樹的其它操作。層次遍歷層次遍歷是按另一種搜索策略進(jìn)行的遍歷。4. 理解二叉樹線索化的實(shí)質(zhì)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過(guò)程線索化過(guò)程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹的線索化過(guò)程線索化過(guò)程是基于基于對(duì)二叉樹進(jìn)行遍歷遍歷，為相應(yīng)的遍

44、歷提供為相應(yīng)的遍歷提供了方便方便。5. 熟悉樹的樹的各種存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握掌握 1 至 2 種建立建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法存儲(chǔ)結(jié)構(gòu)的方法。6. 學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作實(shí)現(xiàn)樹的各種操作的算法。7. 了解最優(yōu)樹的特性最優(yōu)樹的特性，掌握建立最優(yōu)樹建立最優(yōu)樹和哈夫曼編碼和哈夫曼編碼的方法。n1 1）在一棵二叉樹上第）在一棵二叉樹上第4 4層的結(jié)點(diǎn)數(shù)最多是層的結(jié)點(diǎn)數(shù)最多是_。 A.4 B.8 C.32 D.12A.4 B.8 C.32 D.12n2) 2) 在深度為在深度為5 5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為_。 A.32 B.31 C.16 D.15A.32 B.31 C.16 D.15n3) 3) 在深度為在深度為5 5的二叉樹中，至多有的二叉樹中，至多有_個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。n A.32 B.31 C.16 D.15A.32 B.31 C.16 D.15n4 4）在具有）在具有10 10 個(gè)結(jié)點(diǎn)的樹中，其邊的樹目為個(gè)結(jié)點(diǎn)的