山大《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)04樹(shù)和二叉樹(shù)

1、實(shí)驗(yàn)四 樹(shù)和二叉樹(shù)一 實(shí)驗(yàn)任務(wù)1）二叉樹(shù)的表示與實(shí)現(xiàn)2）Huffman編碼二 實(shí)驗(yàn)?zāi)康?）掌握二叉樹(shù)的類型定義和結(jié)構(gòu)特點(diǎn)。2）掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)。3）掌握赫夫曼樹(shù)及其應(yīng)用三 實(shí)驗(yàn)原理1二叉樹(shù)的定義所謂二叉樹(shù)，是指結(jié)點(diǎn)的一個(gè)有限集合，它或?yàn)榭占?，或?yàn)闈M足下列性質(zhì)的非空集合：有且只有一個(gè)根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成左右兩個(gè)互不相交的集合TL、TR，且TL、TR均為二叉樹(shù)。二叉樹(shù)的抽象數(shù)據(jù)類型定義如下：ADT BinaryTree 數(shù)據(jù)對(duì)象D：D=ai | aiElemSet, i=1,2, ,n, n0數(shù)據(jù)關(guān)系R：若D為空集，則稱為空二叉樹(shù)。若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則RH，H滿足關(guān)

2、系：(1) T中存在唯一的一個(gè)結(jié)點(diǎn)，它沒(méi)有前驅(qū)，稱為樹(shù)的根，用root表示，在集合D中用a1表示；(2) 若D中元素個(gè)數(shù)大于1，對(duì)于任意的數(shù)據(jù)元素ajD且j2，存在唯一的數(shù)據(jù)元素aiD，有H；(3) 若D中元素個(gè)數(shù)大于1，對(duì)于任意的數(shù)據(jù)元素aiD，僅存在不多于2個(gè)數(shù)據(jù)元素aj,akD且j, ki，有 , H，其中，若jK，則稱aj為ai的左孩子節(jié)點(diǎn)，ak為ai的右孩子節(jié)點(diǎn)?；静僮鱌：InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹(shù)T。CreateBiTree(&T, tree);初始條件：tree給出二叉樹(shù)T的表示形式。操作結(jié)果：按tree構(gòu)造二叉樹(shù)T。BiTreeEmpty(T);初始

3、條件：二叉樹(shù)T存在。操作結(jié)果：若T為空樹(shù)，則返回TRUE，否則返回FALSE。BiTreeDepth(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：返回T的根。Value(T, e);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE。Assign(T, e, value);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，結(jié)點(diǎn)e賦值為value，則函數(shù)返回TRUE，否則返回FALSE。Parent(T, e, P);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的

4、值。操作結(jié)果：若樹(shù)中存在值為e的結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點(diǎn)，用P返回雙親結(jié)點(diǎn)的位置，若結(jié)點(diǎn)為根結(jié)點(diǎn)，則P返回空。LeftChild(T, e, P);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若樹(shù)中存在值為e的結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點(diǎn)，用P返回左孩子結(jié)點(diǎn)的位置，若結(jié)點(diǎn)無(wú)左孩子結(jié)點(diǎn)，則P返回空。RightChild(T, e, P);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若樹(shù)中存在值為e的結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點(diǎn)，用P返回右孩子結(jié)點(diǎn)的位置，若結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，則P返

5、回空。DelBiTreeNode(&T，P);初始條件：二叉樹(shù)T存在，P指向該二叉樹(shù)中的一個(gè)結(jié)點(diǎn)。操作結(jié)果：刪除P所指向的結(jié)點(diǎn)及其子樹(shù)。TraverseBiTree(T, visit( );初始條件：二叉樹(shù)T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit( )一次且至多一次。一旦visit( )失敗，則操作失敗。ClearBiTree(&T);初始條件：二叉樹(shù)T存在。操作結(jié)果：將二叉樹(shù)T清空。ADT BinaryTree2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常采用二叉鏈表形式，即在每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，分別為數(shù)據(jù)域data、左指針域left和

6、右指針域right。其中，數(shù)據(jù)域用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素，left和right用來(lái)分別存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)的存儲(chǔ)位置。二叉鏈表的結(jié)點(diǎn)類型可定義為：typedef struct BiTreeNodeElemType data;struct BiTreeNode *left;struct BiTreeNode *right; BiTreeNode, * BiTreePtr;3二叉樹(shù)的遍歷二叉樹(shù)的遍歷是二叉樹(shù)中最重要的運(yùn)算，也是各種操作的基礎(chǔ)。二叉樹(shù)的遍歷是指按照某個(gè)搜索路徑尋訪樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。在遍歷的過(guò)程中，可以對(duì)結(jié)點(diǎn)進(jìn)行各種操作。根據(jù)二叉樹(shù)的遞歸定義，

7、一棵非空二叉樹(shù)由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)組成，因此，遍歷一棵二叉樹(shù)可以分解為三個(gè)問(wèn)題：訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)。若分別用D、L、R表示上述三個(gè)子問(wèn)題，則可能有DLR、LDR、LRD、DRL、RDL、RLD幾種情況。若限定先左后右，則只有前3種情況：（1）DLR，此時(shí)訪問(wèn)根結(jié)點(diǎn)的操作在遍歷左、右子樹(shù)之前，故稱之為先序遍歷或先根遍歷；（2）LDR，此時(shí)訪問(wèn)根結(jié)點(diǎn)的操作在遍歷左子樹(shù)之后、右子樹(shù)之前，故稱之為中序遍歷或中根遍歷；（3）LRD，此時(shí)訪問(wèn)根結(jié)點(diǎn)的操作在遍歷左、右子樹(shù)之后，故稱之為后序遍歷或后根遍歷。4赫夫曼樹(shù)n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)稱作赫夫

8、曼樹(shù)。權(quán)值越大的結(jié)點(diǎn)離根越近的二叉樹(shù)才是最優(yōu)二叉樹(shù)。赫夫曼樹(shù)構(gòu)造算法，具體敘述如下：(1) 給定n個(gè)權(quán)值w1, w2, , wn，對(duì)應(yīng)n個(gè)結(jié)點(diǎn)，構(gòu)成具有n棵二叉樹(shù)的森林F=T1, T2, , Tn，其中每棵二叉樹(shù)Ti（1in）都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左右子樹(shù)均為空。(2) 在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為一棵新樹(shù)的左、右子樹(shù)，且置新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。(3) 從F中刪除構(gòu)成新樹(shù)的那兩棵樹(shù)，同時(shí)把新樹(shù)加入F中。(4) 重復(fù)(2)和(3)，直到F中只含有一棵樹(shù)為止，此樹(shù)就是赫夫曼樹(shù)。5赫夫曼編碼若要設(shè)計(jì)長(zhǎng)短不等的編碼，則要求字符集中任一個(gè)字符的編碼都

9、不是另一個(gè)字符的編碼的前綴，這種編碼稱做前綴編碼。為了使不等長(zhǎng)編碼為前綴編碼，可用該字符集中的每個(gè)字符作為葉子結(jié)點(diǎn)生成一棵編碼二叉樹(shù)，將每個(gè)字符出現(xiàn)的次數(shù)作為字符結(jié)點(diǎn)的權(quán)值賦予該結(jié)點(diǎn)上，求出此樹(shù)的最小帶權(quán)路徑長(zhǎng)度，也就是傳送電文的最短長(zhǎng)度。因此，求傳送電文的最短長(zhǎng)度問(wèn)題就轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點(diǎn)且由字符的出現(xiàn)頻率作為其權(quán)值所產(chǎn)生的赫夫曼樹(shù)的問(wèn)題。四 實(shí)驗(yàn)設(shè)備、儀器、工具與資料 微機(jī)、VC五 實(shí)驗(yàn)內(nèi)容（1）實(shí)驗(yàn)任務(wù)1：二叉樹(shù)建立和遍歷編制C程序?qū)崿F(xiàn)下列功能：1）建立二叉樹(shù)。2）按先序、中序、后序方式遍歷二叉樹(shù)。程序的基本要求：采用二叉鏈表存儲(chǔ)結(jié)構(gòu)表示二叉樹(shù)；通過(guò)二叉樹(shù)廣義表輸入所

10、有結(jié)點(diǎn)建立二叉樹(shù)；通過(guò)遞歸算法實(shí)現(xiàn)二叉樹(shù)的遍歷并輸出結(jié)點(diǎn)數(shù)據(jù)信息。（2）實(shí)驗(yàn)任務(wù)2：赫夫曼編碼從鍵盤(pán)上輸入n個(gè)字符及其權(quán)值，編制C程序建立赫夫曼樹(shù)，并編碼輸出。六 實(shí)驗(yàn)步驟（1）實(shí)驗(yàn)預(yù)習(xí)1）預(yù)習(xí)本實(shí)驗(yàn)原理中關(guān)于二叉樹(shù)的定義、二叉鏈表存儲(chǔ)表示。2）分析掌握教材9399頁(yè)中的算法4-14-4、算法4-74-7，為完成實(shí)驗(yàn)任務(wù)1做好準(zhǔn)備。3）預(yù)習(xí)本實(shí)驗(yàn)原理中關(guān)于赫夫曼樹(shù)、赫夫曼編碼的含義及赫夫曼樹(shù)的構(gòu)造方法。4）分析掌握教材112115頁(yè)中的算法4-144-15，為完成實(shí)驗(yàn)任務(wù)2做好準(zhǔn)備。（2）實(shí)驗(yàn)步驟1）問(wèn)題分析。充分地分析和理解此實(shí)驗(yàn)任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫(xiě)出每個(gè)子程序（過(guò)程或函數(shù)）的規(guī)格說(shuō)明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計(jì)。3）詳細(xì)設(shè)計(jì)。詳細(xì)設(shè)計(jì)的目的是對(duì)子程序（過(guò)程或函數(shù)）的進(jìn)一步求精。用 IF 、WHILE和賦值語(yǔ)句等，以及自然語(yǔ)言寫(xiě)出算法的框架。利用自然語(yǔ)言的目的是避免陷入細(xì)節(jié)。4）編碼。在詳細(xì)設(shè)計(jì)的基礎(chǔ)上，對(duì)詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精，用C語(yǔ)言表示出來(lái)。5）在VC環(huán)境下調(diào)試程序。七 實(shí)驗(yàn)報(bào)告要求實(shí)驗(yàn)報(bào)告包含程序開(kāi)發(fā)過(guò)程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說(shuō)明：?jiǎn)栴}描述，求解的問(wèn)題是什么