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

實驗8 二叉樹的基本操作

班級: 學號:

一、題目

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

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

即,要求根據1 3 0 2 0 0 4 5 0 0 0這樣的輸入，構造出一棵只含有正整數節點的二叉樹。

【輸入】

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

構造的簡單樹的節點個數 【樣例輸入】 3 0 2 0 0 4 5 0 0 0 【樣例輸出】

二、程序清單

三、程序調試過程中所出現的錯誤

四、運行結果（界面）：

五、心得體會

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

實驗三

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

第三次實驗主要包括兩部分內容：1.二叉樹基本操作實驗；2.二叉樹應用—赫夫曼樹與赫夫曼編碼實驗。基本操作包括存儲結構建立和遍歷算法，本文只給出部分參考程序，請大家盡量完成多數基本操作。

第一部分 基本操作實驗

[問題描述] 二叉樹采用二叉鏈表作存儲結構，試編程實現二叉樹的如下基本操作

1．按先序序列構造一棵二叉鏈表表示的二叉樹T；

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

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

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

7.求二叉樹的深度

[說明]

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

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

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

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

第二部分 二叉樹應用實驗

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

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

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

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

心得體會

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

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

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

實驗三

實驗目的：

二叉樹的建立及基本操作

本次實驗的主要目的是熟練掌握二叉樹的定義、三序（先序、中序、后序）遍歷方法，并用遍歷思想求解具體二叉樹應用問題。通過程序實現，體會遞歸算法的優缺點。

實驗要求：

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

(3)CountLeaf()：統計該二叉樹中葉子結點的個數(4)InOrderTraverse()：中序遍歷二叉樹(5)PostOrderTraverse()：后序遍歷二叉樹

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

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

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

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

程序源碼：（后付紙）程序運行結果：

實驗心得體會：

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

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

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

課程名稱

數據結構基礎

實驗項目名稱

實驗十

二叉樹的基本操作

實驗成績

指導老師（簽名）

日期

一.實驗目的和要求

1、掌握二叉樹的鏈式存儲結構。

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

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

二.實驗內容

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

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

ElemType data;

// 結點值域

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

①void InitBTree(BTreeNode *&BT);

//初始化二叉樹BT

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

//根據字符串a所給出的廣義表表示的二叉樹建立二叉鏈表存儲結構

③int EmptyBTree(BTreeNode *BT);

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

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

//查找二叉樹BT中值為x的結點，若查找成功返回1，否則返回0

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

//后序遍歷發二叉樹BT

⑨void PrintBTree(BTreeNode *BT);

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

//清除二叉樹BT

2、選做：實現以下說明的操作函數，要求把函數添加到頭文件binary_tree.h中，并在主函數文件test4_1.cpp中添加相應語句進行測試。①void LevelOrder(BTreeNode *BT)//二叉樹的層序遍歷

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

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

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

三.函數的功能說明及算法思路

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

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

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

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

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

函數：void CreateBTree(BTreeNode *&BT, char *a)功能：根據字符串a所給出的廣義表表示的二叉樹建立二叉鏈表存儲結構

思路：根據廣義表表示的”(”,”)”和”,”等字符來構建二叉樹，用棧S來存儲根結點指針，用p來接收當前結點值數據并鏈接為棧頂元素的左/右孩子

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

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

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

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

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

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

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

函數：void PostOrder(BTreeNode *BT)

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

函數：void PrintBTree(BTreeNode *BT)

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

函數：void ClearBTree(BTreeNode *&BT)

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

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

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

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

四.實驗結果與分析

（包括運行結果截圖、結果分析等）

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

五.心得體會

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

【附錄----源程序】

第五篇：實驗5_二叉樹

贛南師范大學數學與計算機科學學院

實 驗 報 告 冊

課程名稱：算法與數據結構

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

實驗5 二叉樹

一、實驗目的和要求

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

二、實驗儀器和設備

Visual C++ 6.0

三、實驗內容與過程

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

2.在第一題基礎上，求二叉樹中葉結點的個數。3.在第一題基礎上，求二叉樹的深度。

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

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

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