二叉排序樹的實(shí)現(xiàn)[最終版]-資料下載頁
2025-06-16 00:24本頁面
【正文】 arrayTimes[i] = (double)(finish start)/CLOCKS_PER_SEC。 Student st = findStudentInArray(students, id)。 start = clock()。 for(int k = 0。 k NUM。 k++){ find(st, randTree)。 } finish = clock()。 treeTimes[i] = (double)(finish start)/CLOCKS_PER_SEC。 } for(int i = 0。 i 5。 i++){ printf(學(xué)號(hào)%d的數(shù)組查找用了%f秒\n,ids[i], arrayTimes[i])。 } double arrTime = average(arrayTimes)。 printf(平均時(shí)間為%f\n,arrTime)。 for(int i = 0。 i 5。 i++){ printf(學(xué)號(hào)%d的二叉樹查找用了%f秒\n,ids[i], treeTimes[i])。 } double treeTime = average(treeTimes)。 printf(平均時(shí)間為%f\n,treeTime)。經(jīng)過幾次的測(cè)試，如下圖，發(fā)現(xiàn)數(shù)組查找的時(shí)間基本為二叉樹查找的一倍，顯然在這種這種情況下，二叉樹的查找效率比數(shù)組快。 情況二：考慮一種極端的情況，二叉樹按照學(xué)號(hào)的升序或者降序來插入學(xué)生，為了比較，數(shù)組也是按照升序來儲(chǔ)存。這樣會(huì)使二叉樹變成一條由左節(jié)點(diǎn)或者右節(jié)點(diǎn)組成的長(zhǎng)鏈。這種情況下，二叉樹中的查找時(shí)間就是O(n^2)，和數(shù)組的遍歷查找時(shí)間處于同一個(gè)數(shù)量級(jí)。但由于二叉樹中的查找是指針操作，比數(shù)組操作慢，故二叉樹效率會(huì)低。以下為測(cè)試代碼，先生成一個(gè)50元素的Student數(shù)組，數(shù)組中元素的學(xué)號(hào)ID從0開始，遞增到49。int a[50]。 for(int i = 0。 i 50。 i++) a[i] = i。 Student students[50]。 genStudentArray(students, a)。 Tree tree = makeStudentTree(students)。 testTime(students, tree)。其中testTime()函數(shù)中的代碼為測(cè)試代碼，和上一種情況的代碼一樣，現(xiàn)在只關(guān)注測(cè)試時(shí)間就行了，測(cè)試的時(shí)間如下。可以看到，在這種極端情況下，二叉樹的查找效率十分差，比數(shù)組查找慢一倍多。情況三：二叉樹元素插入的順序是隨機(jī)的，數(shù)組按學(xué)號(hào)升序儲(chǔ)存學(xué)生，但這次數(shù)組的查找算法不同，考慮到數(shù)組中的下標(biāo)就是學(xué)號(hào)，可以直接通過學(xué)號(hào)ID映射到數(shù)組下標(biāo)來查找。如果是這樣，顯然是數(shù)組最快。但這種查找算法不太現(xiàn)實(shí)，因?yàn)楝F(xiàn)實(shí)中的學(xué)號(hào)都是很大的，需要很大的數(shù)組來儲(chǔ)存。因此，為了更一般，這里用二分查找來在有序的數(shù)組中查找學(xué)生。二分查找的代碼如下：Student binSearchArray(Student students[50], int id){ int hight = 49。 int low = 0。 int min。 while(low hight){ min = (hight + low)/2 + 1。 if(id students[min]id){ hight = min 1。 }else if(id students[min]id) { low = min + 1。 }else{ return students[min]。 } } return students[hight]。}生成測(cè)試數(shù)據(jù)的代碼如下： int a[50]。 for(int i = 0。 i 50。 i++) a[i] = i。 Student students[50]。 genStudentArray(students, a)。 Student randStudents[50]。//隨機(jī)的學(xué)生數(shù)組，用于生成隨機(jī)樹 genRandArray(a)。 genStudentArray(randStudents, a)。 Tree tree = makeStudentTree(randStudents)。 printf(層序遍歷\n)。 levelOrderTraversal(tree)。 printf(\n)。 testBinTime(students, tree)。其中testBinTime()函數(shù)的測(cè)試代碼中，把遍歷數(shù)組查找的方法換成了二分查找的方法。測(cè)試結(jié)果如下圖，可以看出，這種情況下，數(shù)組的效率比二叉樹要好： 數(shù)據(jù)測(cè)試與結(jié)果1. 測(cè)試二叉樹的數(shù)據(jù)插入與樹的即時(shí)打印。測(cè)試代碼如下： int in,count。 SearchTree searchTree = NULL。 printf(請(qǐng)輸入你要輸入數(shù)字的個(gè)數(shù)：\n)。 if(scanf(%d,amp。count) == 1){ for(int i = 0。i count。i++){ printf(請(qǐng)輸入第%d個(gè)元素\n,i)。 if(scanf(%d,amp。in) == 1){ searchTree = insertTreeNode(in,searchTree)。 printTree(searchTree)。 } } } printf(前序遍歷\n)。 preorderTraversal(searchTree)。 printf(\n)。 printf(中序遍歷\n)。 inorderTraversal(searchTree)。 printf(\n)。 printf(后序遍歷\n)。 postorderTraversal(searchTree)。 printf(\n)。 printf(層序遍歷\n)。 levelOrderTraversal(searchTree)。 printf(\n)。 printTree(searchTree)。測(cè)試結(jié)果如圖所示：2. 測(cè)試二叉樹和數(shù)組的查找效率。該部分的測(cè)試見上面解決方案與關(guān)鍵代碼處的圖片。 總結(jié)與改進(jìn)。這次實(shí)驗(yàn)收獲很多，總結(jié)為以下幾點(diǎn):1) 在考慮把遞歸函數(shù)轉(zhuǎn)化為非遞歸時(shí)，可以從考慮從循環(huán)操作中的一致性操作入手。2) 在儲(chǔ)存非遞歸操作的元素時(shí)，思維不一定局限于只用一個(gè)棧，也可以用兩個(gè)，或者用隊(duì)列，或者兩個(gè)結(jié)合來用。3) 分析問題要多角度分析，比如分析二叉樹與數(shù)組的查找效率時(shí)，就可以分多種情況進(jìn)行。4) 打印二叉樹的方法不是很好。沒有考慮到當(dāng)樹的高度很高時(shí)，屏幕空間不足的問
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1