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

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

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

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

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

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

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

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

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

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

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