第一篇：實驗10 二叉樹的基本操作

浙江大學城市學院實驗報告

課程名稱

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

實驗項目名稱

實驗十

二叉樹的基本操作

實驗成績

指導老師（簽名）

日期

一.實驗目的和要求

1、掌握二叉樹的鏈式存儲結(jié)構(gòu)。

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

3、進一步掌握遞歸算法的設計方法。

二.實驗內(nèi)容

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

二叉樹二叉鏈表存儲表示如下： struct BTreeNode {

ElemType data;

// 結(jié)點值域

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

①void InitBTree(BTreeNode *&BT);

//初始化二叉樹BT

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

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

③int EmptyBTree(BTreeNode *BT);

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

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

//查找二叉樹BT中值為x的結(jié)點，若查找成功返回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、選做：實現(xiàn)以下說明的操作函數(shù)，要求把函數(shù)添加到頭文件binary_tree.h中，并在主函數(shù)文件test4_1.cpp中添加相應語句進行測試。①void LevelOrder(BTreeNode *BT)//二叉樹的層序遍歷

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

3、填寫實驗報告，實驗報告文件取名為report10.doc。

4、上傳實驗報告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h到Ftp服務器上自己的文件夾下。

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

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

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

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

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

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

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

思路：根據(jù)廣義表表示的”(”,”)”和”,”等字符來構(gòu)建二叉樹，用棧S來存儲根結(jié)點指針，用p來接收當前結(jié)點值數(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é)點，若查找成功返回1，否則返回0

思路：類似于前序遍歷，若空樹則返回0。若根結(jié)點值等于查找值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ù)：void ClearBTree(BTreeNode *&BT)

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

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

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

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

四.實驗結(jié)果與分析

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

測試數(shù)據(jù)：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 結(jié)果分析：針對該二叉樹，程序輸出深度為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é)點d為根結(jié)點的子樹深度為3，正確。

五.心得體會

（記錄實驗感受、上機過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）

【附錄----源程序】

第二篇：實驗8 二叉樹的基本操作

實驗8 二叉樹的基本操作

班級: 學號:

一、題目

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

節(jié)點的元素(key)是正整數(shù)，且互不相同。可能給出這樣一個虛擬的樹更有利于理解輸入。是的，我們的輸入是上圖的先序遍歷；

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

【輸入】

擴展的二叉樹的先序遍歷 【輸出】

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

二、程序清單

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

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

五、心得體會

第三篇：實驗三 二叉樹基本操作與應用實驗

實驗三

二叉樹基本操作與應用實驗

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

第一部分 基本操作實驗

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

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

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

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

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

7.求二叉樹的深度

[說明]

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

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

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

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

第二部分 二叉樹應用實驗

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

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

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

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

心得體會

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

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

第四篇：實驗3 - 二叉樹的建立及基本操作

實驗三

實驗目的：

二叉樹的建立及基本操作

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

實驗要求：

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

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

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

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

通過輸入擴展的先序序列建立一棵二叉樹，即，二叉樹中結(jié)點為空時應輸入*符號表示。[測試數(shù)據(jù)] 由學生自己確定，注意邊界數(shù)據(jù)。

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

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

實驗心得體會：

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

第五篇：實驗5_二叉樹

贛南師范大學數(shù)學與計算機科學學院

實 驗 報 告 冊

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

實驗項目名稱： 實驗5.二叉樹 實驗學時： 4 學生學號與姓名： 實驗地點： 數(shù)計樓四樓 實驗日期： 年 月 日 指導老師：

實驗5 二叉樹

一、實驗目的和要求

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

二、實驗儀器和設備

Visual C++ 6.0

三、實驗內(nèi)容與過程

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

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

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

四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）

五、實驗體會（遇到問題及解決辦法，編程后的心得體會）