第一篇：實驗5_二叉樹
贛南師范大學數學與計算機科學學院
實 驗 報 告 冊
課程名稱：算法與數據結構
實驗項目名稱： 實驗5.二叉樹 實驗學時： 4 學生學號與姓名： 實驗地點： 數計樓四樓 實驗日期： 年 月 日 指導老師：
實驗5 二叉樹
一、實驗目的和要求
（1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應用二叉樹遞歸遍歷思想解決問題的方法。
二、實驗儀器和設備
Visual C++ 6.0
三、實驗內容與過程
1.建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。
2.在第一題基礎上，求二叉樹中葉結點的個數。3.在第一題基礎上，求二叉樹的深度。
程序清單： 1.2.3.贛南師范大學數學與計算機科學學院
四、實驗結果與分析（程序運行結果及其分析）
五、實驗體會（遇到問題及解決辦法，編程后的心得體會）
第二篇：第四次實驗--二叉樹遍歷
一、二叉鏈表的聲明.BinaryNode
public T data;
//數據域，存儲數據元素
public BinaryNode
//鏈域，分別指向左、右孩子結點
//構造結點，參數分別指定元素和左、右孩子結點
publicBinaryNode(T data, BinaryNode
{ this.data = data;this.left = left;this.right = right;
}
public BinaryNode(T data)
//構造指定值的葉子結點
{ this(data, null, null);
} publicBinaryNode()
{ this(null, null, null);
}
//可聲明以下方法 public String toString()
{ returnthis.data.toString();
}
public boolean equals(Object obj)
//比較兩個結點值是否相等，覆蓋Object
//類的equals(obj)方法
{ returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode
}
public booleanisLeaf()
//判斷是否葉子結點
{ returnthis.left==null &&this.right==null;
} } 二、二叉樹中的遍歷方法的聲明.BinaryTree
public BinaryNode
//根結點，結點結構為二叉鏈表
public BinaryTree()
//構造空二叉樹
{ this.root=null;
}
public booleanisEmpty()
//判斷二叉樹是否空
{ returnthis.root==null;
}
//二叉樹的先根、中根和后根次序遍歷算法
public void preOrder()
//先根次序遍歷二叉樹
{ System.out.print(“先根次序遍歷二叉樹：
”);preOrder(root);//調用先根次序遍歷二叉樹的遞歸方法 System.out.println();
}
public void preOrder(BinaryNode
//先根次序遍歷以p結點為根的子二叉
//遞歸方法
{ if(p!=null)
//若二叉樹不空
{ System.out.print(p.data.toString()+“ ”);//訪問當前結點
preOrder(p.left);
//按先根次序遍歷當前結點的左子樹，//遞歸調用 preOrder(p.right);
//按先根次序遍歷當前結點的右子樹
//遞歸調用
}
}
public String toString()
//返回先根次序遍歷二叉樹所有結點的描述字符串
{ returntoString(root);
}
private String toString(BinaryNode
//返回先根次序遍歷以p為根的子樹描述字
//符串，遞歸算法
{ if(p==null)return “";
return p.data.toString()+” “ + toString(p.left)+ toString(p.right);//遞歸調用
}
public void inOrder()
//中根次序遍歷二叉樹
{ System.out.print(”中根次序遍歷二叉樹：
“);inOrder(root);System.out.println();
}
public void inOrder(BinaryNode
//中根次序遍歷以p結點為根的子二叉
//遞歸方法
{ if(p!=null)
{ inOrder(p.left);
//中根次序遍歷左子樹，遞歸調用 System.out.print(p.data.toString()+” “);inOrder(p.right);
//中根次序遍歷右子樹，遞歸調用
}
}
public void postOrder()
//后根次序遍歷二叉樹
{ System.out.print(”后根次序遍歷二叉樹：
“);postOrder(root);System.out.println();
}
public void postOrder(BinaryNode
//后根次序遍歷以p結點為根的子二叉樹，//遞歸方法
{ if(p!=null)
{ postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+” “);
}
}
public BinaryTree(T[] prelist, T[] inlist)
//以先根和中根序列構造二叉樹
{ this.root = create(prelist, inlist, 0, 0, prelist.length);
} //以先根和中根序列創建一棵子樹，子樹根結點值是prelist[preStart]，n指定子序列長度.//返回所創建子樹的根結點
privateBinaryNode
{ System.out.print(”prelist:“);print(prelist, preStart, n);System.out.print(”，inlist:“);print(inlist, inStart, n);System.out.println();
if(n<=0)return null;
T elem=prelist[preStart];
//根結點值 BinaryNode
//創建葉子結點 inti=0;while(i //在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i); //創建左子樹 p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//創建右子樹 return p; } private void print(T[] table, int start, int n) { for(inti=0;i } public BinaryTree(T[] prelist) //以標明空子樹的先根序列構造二叉樹 { this.root = create(prelist); } //以標明空子樹的先根序列構造一棵子二叉樹，子樹的根值是prelist[i]，返回所創建子樹的根結點 privateinti=0;privateBinaryNode { BinaryNode { T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因為T不一定是String { p = new BinaryNode //創建葉子結點 p.left = create(prelist); //創建p的左子樹 p.right = create(prelist); //創建p的右子樹 } } return p; } } 三、運行程序 .BinaryTree_make //運用二叉鏈表及先根和中根遍歷確立并構造二叉樹 public class BinaryTree_make { public static BinaryTree //構造給定的一棵二叉樹 { BinaryTree BinaryNode } public static void main(String args[]) { BinaryTree //先根次序遍歷二叉樹 bitree.inOrder();//中根遍歷 bitree.postOrder(); //后根遍歷 String[] prelist = {”A“,”B“,”D“,”G“,”C“,”E“,”F“,”H“};//采用先根中根兩種遍歷 String[] inlist = {”D“,”G“,”B“,”A“,”E“,”C“,”H“,”F"}; //確定一顆二叉樹 BinaryTree bitree1.preOrder();// 先根遍歷 bitree1.inOrder();//中根遍歷 bitree1.postOrder(); } } //后根遍歷 四、運行結果 五、實驗內容 1.根據圖示的二叉樹，運用二叉鏈表及先中根遍歷構造二叉樹，并在控制臺上顯示出二叉樹：先中后根遍歷 六、附加實驗內容 在上述實驗中，只通二叉鏈表及先根和中根遍歷確立構造二叉樹。沒有給出中根和后根遍歷二叉樹的方法。現要求同學們寫出中根和后根遍歷確立二叉樹的方法（只寫方法）。 七、實驗報告要求 1.運行結果需要截圖，寫出補充方法體的內容，附加實驗只給方法即可。 2.心得體會不可為空（可寫對此次實驗的看法，亦可寫自己近來學習數據結構的感受等等，內容不限） 實驗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)樹型數據結構不僅使各類實際應用問題找到了一種有效解決途徑，而且它也對計算機科學技術本身的發展起到了非常重要的作用，如在編譯原理過程中的編碼問題，使得編譯系統提高了速度。 實驗三 實驗目的： 二叉樹的建立及基本操作 本次實驗的主要目的是熟練掌握二叉樹的定義、三序（先序、中序、后序）遍歷方法，并用遍歷思想求解具體二叉樹應用問題。通過程序實現，體會遞歸算法的優缺點。 實驗要求： 用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);} //注意函數調用時，只傳遞參數名稱，不需要傳遞參數類型和&符號。 [實現提示] 采用特殊符號，如*號表示空樹的情況。 通過輸入擴展的先序序列建立一棵二叉樹，即，二叉樹中結點為空時應輸入*符號表示。[測試數據] 由學生自己確定，注意邊界數據。 程序檢查時，由老師提供用于建樹的初始輸入序列。 程序源碼：（后付紙）程序運行結果： 實驗心得體會： 有一些概念不明白，看書之后弄懂了，仔細看了二叉樹遍歷的知識點，問了同學有了思路。熟悉了二叉樹的基本操作，掌握了二叉樹實現。第三篇：實驗8 二叉樹的基本操作
第四篇：實驗三 二叉樹基本操作與應用實驗
第五篇：實驗3 - 二叉樹的建立及基本操作
點擊咨詢 