第一篇：實驗5_二叉樹

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

實 驗 報 告 冊

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

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

實驗5 二叉樹

一、實驗?zāi)康暮鸵?/p>

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

二、實驗儀器和設(shè)備

Visual C++ 6.0

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

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

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

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

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

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

第二篇：第四次實驗--二叉樹遍歷

一、二叉鏈表的聲明.BinaryNode public class BinaryNode //二叉樹的二叉鏈表結(jié)點類，泛型T指//定結(jié)點的元素類型 {

public T data;

//數(shù)據(jù)域，存儲數(shù)據(jù)元素

public BinaryNode left, right;

//鏈域，分別指向左、右孩子結(jié)點

//構(gòu)造結(jié)點，參數(shù)分別指定元素和左、右孩子結(jié)點

publicBinaryNode(T data, BinaryNode left, BinaryNode right)

{ this.data = data;this.left = left;this.right = right;

}

public BinaryNode(T data)

//構(gòu)造指定值的葉子結(jié)點

{ this(data, null, null);

} publicBinaryNode()

{ this(null, null, null);

}

//可聲明以下方法 public String toString()

{ returnthis.data.toString();

}

public boolean equals(Object obj)

//比較兩個結(jié)點值是否相等，覆蓋Object

//類的equals(obj)方法

{ returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode)obj).data);

}

public booleanisLeaf()

//判斷是否葉子結(jié)點

{ returnthis.left==null &&this.right==null;

} } 二、二叉樹中的遍歷方法的聲明.BinaryTree public class BinaryTree {

public BinaryNode root;

//根結(jié)點，結(jié)點結(jié)構(gòu)為二叉鏈表

public BinaryTree()

//構(gòu)造空二叉樹

{ this.root=null;

}

public booleanisEmpty()

//判斷二叉樹是否空

{ returnthis.root==null;

}

//二叉樹的先根、中根和后根次序遍歷算法

public void preOrder()

//先根次序遍歷二叉樹

{ System.out.print(“先根次序遍歷二叉樹：

”);preOrder(root);//調(diào)用先根次序遍歷二叉樹的遞歸方法 System.out.println();

}

public void preOrder(BinaryNode p)

//先根次序遍歷以p結(jié)點為根的子二叉

//遞歸方法

{ if(p!=null)

//若二叉樹不空

{ System.out.print(p.data.toString()+“ ”);//訪問當(dāng)前結(jié)點

preOrder(p.left);

//按先根次序遍歷當(dāng)前結(jié)點的左子樹，//遞歸調(diào)用 preOrder(p.right);

//按先根次序遍歷當(dāng)前結(jié)點的右子樹

//遞歸調(diào)用

}

}

public String toString()

//返回先根次序遍歷二叉樹所有結(jié)點的描述字符串

{ returntoString(root);

}

private String toString(BinaryNode p)

//返回先根次序遍歷以p為根的子樹描述字

//符串，遞歸算法

{ if(p==null)return “";

return p.data.toString()+” “ + toString(p.left)+ toString(p.right);//遞歸調(diào)用

}

public void inOrder()

//中根次序遍歷二叉樹

{ System.out.print(”中根次序遍歷二叉樹：

“);inOrder(root);System.out.println();

}

public void inOrder(BinaryNode p)

//中根次序遍歷以p結(jié)點為根的子二叉

//遞歸方法

{ if(p!=null)

{ inOrder(p.left);

//中根次序遍歷左子樹，遞歸調(diào)用 System.out.print(p.data.toString()+” “);inOrder(p.right);

//中根次序遍歷右子樹，遞歸調(diào)用

}

}

public void postOrder()

//后根次序遍歷二叉樹

{ System.out.print(”后根次序遍歷二叉樹：

“);postOrder(root);System.out.println();

}

public void postOrder(BinaryNode p)

//后根次序遍歷以p結(jié)點為根的子二叉樹，//遞歸方法

{ if(p!=null)

{ postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+” “);

}

}

public BinaryTree(T[] prelist, T[] inlist)

//以先根和中根序列構(gòu)造二叉樹

{ this.root = create(prelist, inlist, 0, 0, prelist.length);

} //以先根和中根序列創(chuàng)建一棵子樹，子樹根結(jié)點值是prelist[preStart]，n指定子序列長度.//返回所創(chuàng)建子樹的根結(jié)點

privateBinaryNode create(T[] prelist, T[] inlist, intpreStart, intinStart, int n)

{ 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];

//根結(jié)點值 BinaryNode p=new BinaryNode(elem);

//創(chuàng)建葉子結(jié)點 inti=0;while(i

//在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i);

//創(chuàng)建左子樹 p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//創(chuàng)建右子樹 return p;

} private void print(T[] table, int start, int n)

{ for(inti=0;i

}

public BinaryTree(T[] prelist)

//以標明空子樹的先根序列構(gòu)造二叉樹

{ this.root = create(prelist);

}

//以標明空子樹的先根序列構(gòu)造一棵子二叉樹，子樹的根值是prelist[i]，返回所創(chuàng)建子樹的根結(jié)點 privateinti=0;privateBinaryNode create(T[] prelist)

{ BinaryNode p = null;if(i

{

T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因為T不一定是String

{

p = new BinaryNode(elem);

//創(chuàng)建葉子結(jié)點 p.left = create(prelist);

//創(chuàng)建p的左子樹 p.right = create(prelist);

//創(chuàng)建p的右子樹

}

} return p;

}

}

三、運行程序

.BinaryTree_make //運用二叉鏈表及先根和中根遍歷確立并構(gòu)造二叉樹

public class BinaryTree_make {

public static BinaryTree make()

//構(gòu)造給定的一棵二叉樹

{ BinaryTreebitree=new BinaryTree();//創(chuàng)建空二叉樹

BinaryNodechild_f, child_d, child_b, child_c;//創(chuàng)建4個二叉鏈表域 child_d = new BinaryNode(”D“, null, new BinaryNode(”G“));child_b = new BinaryNode(”B“, child_d, null);child_f = new BinaryNode(”F“, new BinaryNode(”H“), null);child_c = new BinaryNode(”C“, new BinaryNode(”E“), child_f);bitree.root = new BinaryNode(”小唐“, child_b, child_c);//創(chuàng)建根結(jié)點 returnbitree;

} public static void main(String args[])

{ BinaryTreebitree = make();bitree.preOrder();

//先根次序遍歷二叉樹 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 = new BinaryTree(prelist, inlist);

bitree1.preOrder();// 先根遍歷

bitree1.inOrder();//中根遍歷

bitree1.postOrder();

} }

//后根遍歷

四、運行結(jié)果

五、實驗內(nèi)容

1.根據(jù)圖示的二叉樹，運用二叉鏈表及先中根遍歷構(gòu)造二叉樹，并在控制臺上顯示出二叉樹：先中后根遍歷

六、附加實驗內(nèi)容

在上述實驗中，只通二叉鏈表及先根和中根遍歷確立構(gòu)造二叉樹。沒有給出中根和后根遍歷二叉樹的方法?，F(xiàn)要求同學(xué)們寫出中根和后根遍歷確立二叉樹的方法（只寫方法）。

七、實驗報告要求

1.運行結(jié)果需要截圖，寫出補充方法體的內(nèi)容，附加實驗只給方法即可。

2.心得體會不可為空（可寫對此次實驗的看法，亦可寫自己近來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的感受等等，內(nèi)容不限）

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

實驗8 二叉樹的基本操作

班級: 學(xué)號:

一、題目

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

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

即,要求根據(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é)果（界面）：

五、心得體會

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

實驗三

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

第三次實驗主要包括兩部分內(nèi)容：1.二叉樹基本操作實驗；2.二叉樹應(yīng)用—赫夫曼樹與赫夫曼編碼實驗?；静僮靼ù鎯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é)點應(yīng)當(dāng)確定其左右子樹的值(為空時必須用特定的空字符占位)，故執(zhí)行此程序時，最好先在紙上畫出你想建立的二叉樹，每個結(jié)點的左右子樹必須確定。若為空，則用特定字符標出，然后再按先序輸入這棵二叉樹的字符序列。

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

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

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

第二部分 二叉樹應(yīng)用實驗

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

[問題描述] 利用HuffMan編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接受端將傳來的數(shù)據(jù)編碼進行譯碼(復(fù)原)。對于有些信道，每端都需要一個完整的編／譯碼系統(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)不僅使各類實際應(yīng)用問題找到了一種有效解決途徑，而且它也對計算機科學(xué)技術(shù)本身的發(fā)展起到了非常重要的作用，如在編譯原理過程中的編碼問題，使得編譯系統(tǒng)提高了速度。

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

實驗三

實驗?zāi)康模?/p>

二叉樹的建立及基本操作

本次實驗的主要目的是熟練掌握二叉樹的定義、三序（先序、中序、后序）遍歷方法，并用遍歷思想求解具體二叉樹應(yīng)用問題。通過程序?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é)點為空時應(yīng)輸入*符號表示。[測試數(shù)據(jù)] 由學(xué)生自己確定，注意邊界數(shù)據(jù)。

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

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

實驗心得體會：

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