第一篇：實(shí)驗(yàn)8 二叉樹的基本操作

實(shí)驗(yàn)8 二叉樹的基本操作

班級(jí): 學(xué)號(hào):

一、題目

由數(shù)字序列生成二叉樹 假設(shè)我們有這樣的二叉樹：

節(jié)點(diǎn)的元素(key)是正整數(shù)，且互不相同?？赡芙o出這樣一個(gè)虛擬的樹更有利于理解輸入。是的，我們的輸入是上圖的先序遍歷；

即,要求根據(jù)1 3 0 2 0 0 4 5 0 0 0這樣的輸入，構(gòu)造出一棵只含有正整數(shù)節(jié)點(diǎn)的二叉樹。

【輸入】

擴(kuò)展的二叉樹的先序遍歷 【輸出】

構(gòu)造的簡(jiǎn)單樹的節(jié)點(diǎn)個(gè)數(shù) 【樣例輸入】 3 0 2 0 0 4 5 0 0 0 【樣例輸出】

二、程序清單

三、程序調(diào)試過(guò)程中所出現(xiàn)的錯(cuò)誤

四、運(yùn)行結(jié)果（界面）：

五、心得體會(huì)

第二篇：實(shí)驗(yàn)三 二叉樹基本操作與應(yīng)用實(shí)驗(yàn)

實(shí)驗(yàn)三

二叉樹基本操作與應(yīng)用實(shí)驗(yàn)

第三次實(shí)驗(yàn)主要包括兩部分內(nèi)容：1.二叉樹基本操作實(shí)驗(yàn)；2.二叉樹應(yīng)用—赫夫曼樹與赫夫曼編碼實(shí)驗(yàn)?；静僮靼ù鎯?chǔ)結(jié)構(gòu)建立和遍歷算法，本文只給出部分參考程序，請(qǐng)大家盡量完成多數(shù)基本操作。

第一部分 基本操作實(shí)驗(yàn)

[問(wèn)題描述] 二叉樹采用二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編程實(shí)現(xiàn)二叉樹的如下基本操作

1．按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；

2．對(duì)這棵二叉樹進(jìn)行遍歷：先序、中序、后序以及層次遍歷序列，分別輸出結(jié)點(diǎn) 的遍歷序列；

3．求二叉樹的深度，結(jié)點(diǎn)數(shù)目，葉結(jié)點(diǎn)數(shù)目； [數(shù)據(jù)描述] ／／二叉樹的二叉鏈表存儲(chǔ)表示 先序遍歷二叉樹遞歸算法

6.層次遍歷二叉樹的非遞歸算法

7.求二叉樹的深度

[說(shuō)明]

1．按先序次序輸入二叉樹中結(jié)點(diǎn)的值，用‘#’表示空樹，對(duì)每一個(gè)結(jié)點(diǎn)應(yīng)當(dāng)確定其左右子樹的值(為空時(shí)必須用特定的空字符占位)，故執(zhí)行此程序時(shí)，最好先在紙上畫出你想建立的二叉樹，每個(gè)結(jié)點(diǎn)的左右子樹必須確定。若為空，則用特定字符標(biāo)出，然后再按先序輸入這棵二叉樹的字符序列。

2．為了簡(jiǎn)化程序的書寫量，以及程序的清晰性，對(duì)結(jié)點(diǎn)的訪問(wèn)以一條輸出語(yǔ)句表示，若有更復(fù)雜的或多種訪問(wèn)，可以將結(jié)點(diǎn)的訪問(wèn)編寫成函數(shù)，然后通過(guò)函數(shù)指針進(jìn)行函數(shù)的調(diào)用。讀者若有興趣，可自行編寫。

3．c語(yǔ)言函數(shù)參數(shù)傳遞，都是以“傳值”的方式，故在設(shè)計(jì)函數(shù)時(shí)，必須注意參數(shù)的傳遞。若想通過(guò)函數(shù)修改實(shí)際參數(shù)的值，則必須用指針變量作參數(shù)。具體設(shè)計(jì)時(shí)；讀者一定要把指針變量及指針變量指向的值等概念弄清楚。

4．完整參考程序只給出了部分遍歷算法，對(duì)于其他算法，請(qǐng)讀者參照示例，自行編程完成，以加深學(xué)習(xí)體會(huì)。對(duì)于二叉鏈表的建立也是如此，示例中只是給出了先序法建立過(guò)程，讀者可自行練習(xí)中序、后序二叉鏈表建立法，葉子結(jié)點(diǎn)或二叉樹結(jié)點(diǎn)總數(shù)求法等。

第二部分 二叉樹應(yīng)用實(shí)驗(yàn)

---------郝夫曼樹與郝夫曼編碼

[問(wèn)題描述] 利用HuffMan編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接受端將傳來(lái)的數(shù)據(jù)編碼進(jìn)行譯碼(復(fù)原)。對(duì)于有些信道，每端都需要一個(gè)完整的編／譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個(gè)Huffman的編／譯碼系統(tǒng)。給定一組權(quán)值{7，9，5，6，10，l，13，15，4，8}．構(gòu)造一棵赫夫曼樹，并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。

Huffman編碼存在磁盤文件中。提出這些要求，是給讀者一定的思考空間和提高自己的編程能力的機(jī)會(huì)。讀者需要注意類c語(yǔ)言描述的算法在轉(zhuǎn)變?yōu)镃源程序時(shí)關(guān)于函數(shù)參數(shù)的處理以及其他變量的定義與使用方法。

2．讀者可參考此程序，實(shí)現(xiàn)Huffman編／譯碼系統(tǒng)的其他算法，以進(jìn)一步加深理解和體會(huì)。

心得體會(huì)

(1)通信領(lǐng)域的編碼問(wèn)題曾經(jīng)對(duì)許多的通信技術(shù)專家形成了困擾，后來(lái)人們對(duì)樹型數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識(shí)之后，才有效地解決了通信的編碼需求。它不僅使通信編碼的長(zhǎng)度縮短，更實(shí)際的意義是使整個(gè)電文的長(zhǎng)度大大縮短了，從而迅速地提高了通信的效率。

(2)樹型數(shù)據(jù)結(jié)構(gòu)不僅使各類實(shí)際應(yīng)用問(wèn)題找到了一種有效解決途徑，而且它也對(duì)計(jì)算機(jī)科學(xué)技術(shù)本身的發(fā)展起到了非常重要的作用，如在編譯原理過(guò)程中的編碼問(wèn)題，使得編譯系統(tǒng)提高了速度。

第三篇：實(shí)驗(yàn)3 - 二叉樹的建立及基本操作

實(shí)驗(yàn)三

實(shí)驗(yàn)?zāi)康模?/p>

二叉樹的建立及基本操作

本次實(shí)驗(yàn)的主要目的是熟練掌握二叉樹的定義、三序（先序、中序、后序）遍歷方法，并用遍歷思想求解具體二叉樹應(yīng)用問(wèn)題。通過(guò)程序?qū)崿F(xiàn)，體會(huì)遞歸算法的優(yōu)缺點(diǎn)。

實(shí)驗(yàn)要求：

用C語(yǔ)言編程實(shí)現(xiàn)二叉樹的基本操作，并完成下述函數(shù)功能：(1)CreateBiTree()：根據(jù)先序遍歷序列生成一棵二叉樹(2)Depth()：求此二叉樹的深度

(3)CountLeaf()：統(tǒng)計(jì)該二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)(4)InOrderTraverse()：中序遍歷二叉樹(5)PostOrderTraverse()：后序遍歷二叉樹

在主函數(shù)main()中調(diào)用各個(gè)子函數(shù)完成單鏈表的基本操作。例： void main(){ BiTree T;CreateBiTree(T);int d= Depth(T);printf(“深度為%d”, d);int num= CountLeaf(T);printf(“葉子結(jié)點(diǎn)個(gè)數(shù)為%d”, num);InOrderTraverse(T);PostOrderTraverse(T);} //注意函數(shù)調(diào)用時(shí)，只傳遞參數(shù)名稱，不需要傳遞參數(shù)類型和&符號(hào)。

[實(shí)現(xiàn)提示] 采用特殊符號(hào)，如*號(hào)表示空樹的情況。

通過(guò)輸入擴(kuò)展的先序序列建立一棵二叉樹，即，二叉樹中結(jié)點(diǎn)為空時(shí)應(yīng)輸入*符號(hào)表示。[測(cè)試數(shù)據(jù)] 由學(xué)生自己確定，注意邊界數(shù)據(jù)。

程序檢查時(shí)，由老師提供用于建樹的初始輸入序列。

程序源碼：（后付紙）程序運(yùn)行結(jié)果：

實(shí)驗(yàn)心得體會(huì)：

有一些概念不明白，看書之后弄懂了，仔細(xì)看了二叉樹遍歷的知識(shí)點(diǎn)，問(wèn)了同學(xué)有了思路。熟悉了二叉樹的基本操作，掌握了二叉樹實(shí)現(xiàn)。

第四篇：實(shí)驗(yàn)10 二叉樹的基本操作

浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告

課程名稱

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

實(shí)驗(yàn)項(xiàng)目名稱

實(shí)驗(yàn)十

二叉樹的基本操作

實(shí)驗(yàn)成績(jī)

指導(dǎo)老師（簽名）

日期

一.實(shí)驗(yàn)?zāi)康暮鸵?/p>

1、掌握二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

2、掌握在二叉鏈表上的二叉樹操作的實(shí)現(xiàn)原理與方法。

3、進(jìn)一步掌握遞歸算法的設(shè)計(jì)方法。

二.實(shí)驗(yàn)內(nèi)容

1、按照下面二叉樹二叉鏈表的存儲(chǔ)表示，編寫頭文件binary_tree.h，實(shí)現(xiàn)二叉鏈表的定義與基本操作實(shí)現(xiàn)函數(shù)；編寫主函數(shù)文件test4_1.cpp，驗(yàn)證頭文件中各個(gè)操作。

二叉樹二叉鏈表存儲(chǔ)表示如下： struct BTreeNode {

ElemType data;

// 結(jié)點(diǎn)值域

BTreeNode *lchild , *rchild;// 定義左右孩子指針 };基本操作如下：

①void InitBTree(BTreeNode *&BT);

//初始化二叉樹BT

②void CreateBTree(BTreeNode *&BT, char *a);

//根據(jù)字符串a(chǎn)所給出的廣義表表示的二叉樹建立二叉鏈表存儲(chǔ)結(jié)構(gòu)

③int EmptyBTree(BTreeNode *BT);

//檢查二叉樹BT是否為空，空返回1，否則返回0 ④int DepthBTree(BTreeNode *BT);//求二叉樹BT的深度并返回該值

⑤int FindBTree(BTreeNode *BT, ElemType x);

//查找二叉樹BT中值為x的結(jié)點(diǎn)，若查找成功返回1，否則返回0

⑥void PreOrder(BTreeNode *BT);//先序遍歷二叉樹BT ⑦void InOrder(BTreeNode *BT);//中序遍歷二叉樹BT ⑧void PostOrder(BTreeNode *BT);

//后序遍歷發(fā)二叉樹BT

⑨void PrintBTree(BTreeNode *BT);

//輸出二叉樹BT ⑩void ClearBTree(BTreeNode *&BT);

//清除二叉樹BT

2、選做：實(shí)現(xiàn)以下說(shuō)明的操作函數(shù)，要求把函數(shù)添加到頭文件binary_tree.h中，并在主函數(shù)文件test4_1.cpp中添加相應(yīng)語(yǔ)句進(jìn)行測(cè)試。①void LevelOrder(BTreeNode *BT)//二叉樹的層序遍歷

②int Get_Sub_Depth(BTreeNode *T , ElemType x)//求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度

3、填寫實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告文件取名為report10.doc。

4、上傳實(shí)驗(yàn)報(bào)告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h到Ftp服務(wù)器上自己的文件夾下。

三.函數(shù)的功能說(shuō)明及算法思路

（包括每個(gè)函數(shù)的功能說(shuō)明，及一些重要函數(shù)的算法實(shí)現(xiàn)思路）函數(shù)：void InitBTree(BTreeNode *&BT)功能：初始化二叉樹BT 思路：將BT指向NULL

函數(shù)：void CBTree(BTreeNode *&BT)功能：輸入二叉樹

思路：按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符）特殊字符 $ 表示空樹

函數(shù)：void PBTree(BTreeNode *BT,int n)功能：橫向打印二叉樹

思路：先遞歸輸出右子樹，按層次輸出空格和“---”控制格式，再輸出當(dāng)前結(jié)點(diǎn)值，最后遞歸左子樹

函數(shù)：void CreateBTree(BTreeNode *&BT, char *a)功能：根據(jù)字符串a(chǎn)所給出的廣義表表示的二叉樹建立二叉鏈表存儲(chǔ)結(jié)構(gòu)

思路：根據(jù)廣義表表示的”(”,”)”和”,”等字符來(lái)構(gòu)建二叉樹，用棧S來(lái)存儲(chǔ)根結(jié)點(diǎn)指針，用p來(lái)接收當(dāng)前結(jié)點(diǎn)值數(shù)據(jù)并鏈接為棧頂元素的左/右孩子

函數(shù)：int EmptyBTree(BTreeNode *BT)功能：檢查二叉樹BT是否為空，空返回1，否則返回0 思路：返回判斷BT是否指向NULL

函數(shù)：int DepthBTree(BTreeNode *BT)功能：求二叉樹BT的深度并返回該值

思路：若一棵二叉樹為空，則它的深度為0，否則它的深度等于左子樹和右子樹中的最大深度加1

函數(shù)：int FindBTree(BTreeNode *BT, ElemType x)功能：查找二叉樹BT中值為x的結(jié)點(diǎn)，若查找成功返回1，否則返回0

思路：類似于前序遍歷，若空樹則返回0。若根結(jié)點(diǎn)值等于查找值x則返回1，否則先調(diào)用函數(shù)本身查找左子樹，還未找到則再查找右子樹，所有操作完成均為找到，則返回0

函數(shù)：void PreOrder(BTreeNode *BT)功能：先序遍歷二叉樹BT 思路：使用“根左右”的順序遍歷二叉樹

函數(shù)：void InOrder(BTreeNode *BT)功能：中序遍歷二叉樹BT 思路：使用“左根右”的順序遍歷二叉樹

函數(shù)：void PostOrder(BTreeNode *BT)

功能：后序遍歷二叉樹BT 思路：使用“左右根”的順序遍歷二叉樹

函數(shù)：void PrintBTree(BTreeNode *BT)

功能：輸出二叉樹BT 思路：按照廣義表表示方法輸出二叉樹（與輸入時(shí)相同）

函數(shù)：void ClearBTree(BTreeNode *&BT)

功能：清除二叉樹BT 思路：按照先子樹后根結(jié)點(diǎn)的順序刪除二叉樹

函數(shù)（選作）：void LevelOrder(BTreeNode *BT)功能：二叉樹的層序遍歷

思路：初始化一個(gè)空隊(duì)列，若二叉樹為空，則空操作；否則，樹根指針入隊(duì)列。當(dāng)隊(duì)列非空時(shí)循環(huán)：出隊(duì)首元素，并輸出該元素（指針）所指結(jié)點(diǎn)的值；且若該結(jié)點(diǎn)存在左右孩子，則左右孩子指針進(jìn)隊(duì)列。輸出結(jié)果就是層序遍歷序列

函數(shù)（選作）：求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度 功能：int Get_Sub_Depth(BTreeNode *T , ElemType x)思路：在FindBTree函數(shù)的基礎(chǔ)上修改，將找到結(jié)點(diǎn)時(shí)的返回值改為調(diào)用DepthBTree求出以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹深度即可

四.實(shí)驗(yàn)結(jié)果與分析

（包括運(yùn)行結(jié)果截圖、結(jié)果分析等）

測(cè)試數(shù)據(jù)：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 結(jié)果分析：針對(duì)該二叉樹，程序輸出深度為4，正確；查找值f能夠找到，正確；先序遍歷結(jié)果為a b c d e f g h i，正確；中序遍歷結(jié)果為c b a f e g d h i，正確；后續(xù)遍歷結(jié)果為c b f g e I h d a，正確；輸出二叉樹的結(jié)果與輸入一致，正確；使用先序輸入二叉樹和橫向輸出部分正確。選作部分，層序遍歷結(jié)果為a b d c e h f g i，正確；以結(jié)點(diǎn)d為根結(jié)點(diǎn)的子樹深度為3，正確。

五.心得體會(huì)

（記錄實(shí)驗(yàn)感受、上機(jī)過(guò)程中遇到的困難及解決辦法、遺留的問(wèn)題、意見(jiàn)和建議等。）

【附錄----源程序】

第五篇：實(shí)驗(yàn)5_二叉樹

贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院

實(shí) 驗(yàn) 報(bào) 告 冊(cè)

課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)

實(shí)驗(yàn)項(xiàng)目名稱： 實(shí)驗(yàn)5.二叉樹 實(shí)驗(yàn)學(xué)時(shí)： 4 學(xué)生學(xué)號(hào)與姓名： 實(shí)驗(yàn)地點(diǎn)： 數(shù)計(jì)樓四樓 實(shí)驗(yàn)日期： 年 月 日 指導(dǎo)老師：

實(shí)驗(yàn)5 二叉樹

一、實(shí)驗(yàn)?zāi)康暮鸵?/p>

（1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問(wèn)題的方法。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++ 6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程

1.建立一棵二叉樹。對(duì)此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。

2.在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。3.在第一題基礎(chǔ)上，求二叉樹的深度。

程序清單： 1.2.3.贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）