山大《數(shù)據(jù)結(jié)構(gòu)》實驗指導04樹和二叉樹

1、實驗四 樹和二叉樹一 實驗任務1）二叉樹的表示與實現(xiàn)2）Huffman編碼二 實驗目的1）掌握二叉樹的類型定義和結(jié)構(gòu)特點。2）掌握二叉樹的鏈式存儲表示和實現(xiàn)。3）掌握赫夫曼樹及其應用三 實驗原理1二叉樹的定義所謂二叉樹，是指結(jié)點的一個有限集合，它或為空集，或為滿足下列性質(zhì)的非空集合：有且只有一個根結(jié)點，其余結(jié)點分成左右兩個互不相交的集合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僅含一個數(shù)據(jù)元素，則R為空集，否則RH，H滿足關(guān)

2、系：(1) T中存在唯一的一個結(jié)點，它沒有前驅(qū)，稱為樹的根，用root表示，在集合D中用a1表示；(2) 若D中元素個數(shù)大于1，對于任意的數(shù)據(jù)元素ajD且j2，存在唯一的數(shù)據(jù)元素aiD，有H；(3) 若D中元素個數(shù)大于1，對于任意的數(shù)據(jù)元素aiD，僅存在不多于2個數(shù)據(jù)元素aj,akD且j, ki，有 , H，其中，若jK，則稱aj為ai的左孩子節(jié)點，ak為ai的右孩子節(jié)點。基本操作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é)點的值。操作結(jié)果：若找到該結(jié)點，則函數(shù)返回TRUE，否則返回FALSE。Assign(T, e, value);初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。操作結(jié)果：若找到該結(jié)點，結(jié)點e賦值為value，則函數(shù)返回TRUE，否則返回FALSE。Parent(T, e, P);初始條件：二叉樹T存在，e是需尋找的結(jié)點的

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

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

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

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

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

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

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