1、精選優質文檔-傾情為你奉上精選優質文檔-傾情為你奉上專心-專注-專業專心-專注-專業精選優質文檔-傾情為你奉上專心-專注-專業數據結構實驗報告姓名邱麗學號專業班級計算機六班指導教師張先宜實驗時間 2016.1實驗地點機房305查找實驗目的(1) 掌握順序表的查找方法，尤其是二分查找方法。(2) 掌握二叉排序樹的建立及查找。 查找是軟件設計中的最常用的運算，查找所涉及到的表結構的不同決定了查找的方法及其性能。二分查找是順序表的查找中的最重要的方法，應能充分理解其實現方法和有關性能，并能借助其判定樹結構來加深理解。二叉排序樹結構在實驗時具有一定的難度，可結合二叉樹的有關內容和方法來實現。實驗內容和

2、要求編寫算法實現下列問題的求解。(1) 對下列數據表，分別采用二分查找算法實現查找，給出查找過程依次所比較的元素（的下標），并以二分查找的判定樹來解釋。 第一組測試數據：數據表為 (1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,26,30,35,40,45,50,100)查找的元素分別為： 2，8，20, 30，50，5，15，33，110 第二組數據：數據表為 (2,3,5,7,8,10,12,15,18,20,22,25,30,35,40,45,50,55,60, 80,100)查找的元素分別為： 22，8，80，3，100，1，13，120(

3、2) 設計出在二叉排序樹中插入結點的算法，在此基礎上實現構建二叉排序樹的算法。 測試數據：構建二叉排序樹的輸入序列如下： 第一組數據：100，150，120，50，70，60，80，170，180，160，110，30，40，35，175 第二組數據：100，70，60，80，150，120，50，160，30，40，170，180，175，35(3) 設計算法在二叉排序樹中查找指定值的結點。測試數據：在任務中第一組測試數據所構造的二叉排序樹中，分別查找下列元素： 150，70，160，190，10，55，175 (4) 設計算法在二叉排序樹中刪除特定值的結點。測試數據：在任務(1)中第一組測

4、試數據所構造的二叉排序樹中，分別刪除下列元素：30，150，100(5) 已知整型數組A1.26遞增有序，設計算法以構造一棵平衡的二叉排序樹來存放該數組中的所有元素。測試數據：數組元素分別為：第一組數據：（1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26）第二組數據：（1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,277,302,328）算法設計二分查找算法書上已給出；遞歸算法：樹空時插入第一個結點為根結點，其后插入的結點與其比較之，若比根結點小就插入左子樹反之插入右子樹。樹不空時遞歸查找左右子樹，若查到則返回值，當遍歷樹后仍未查找到該值，則返回查找失敗。先是查找到刪除結點的位置，用指針記住其父結點位置。刪除結點分情況進行：1、當前結點只有左子樹時直接將父結點與當前結點孩子結點鏈接，刪除當前結點，2、當前結點只有右子樹時直接用右子樹的根結點替換，3、當左右子樹均存在時由當前結點的直接前驅替代。對數組中的數據逐個讀入，第一個為當前根結點，后面插入的比它大的為右孩子，比它小的為左孩子，并設置標記，和記錄對應高度，根據左右高度差，選擇平衡操作。 運行和測試總結和心得查