《二叉排序樹與平衡二叉樹的實(shí)現(xiàn)課程設(shè)計(jì)(總17頁(yè)).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《二叉排序樹與平衡二叉樹的實(shí)現(xiàn)課程設(shè)計(jì)(總17頁(yè)).doc（18頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、攀枝花學(xué)院本科學(xué)生課程設(shè)計(jì)任務(wù)書題目二叉排序樹與平衡二叉樹的實(shí)現(xiàn)1、課程設(shè)計(jì)的目的1) 使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?) 使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計(jì)的能力。3） 使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。2、課程設(shè)計(jì)的內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)要求、工作要求等）(1) (1)以回車(n)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；(2)對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；(3)計(jì)算二叉排序樹T查找成功的平均查找長(zhǎng)度,輸出結(jié)

2、果；(4)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無(wú)x”；(5)用數(shù)列L，生成平衡的二叉排序樹BT:當(dāng)插入新元素之后，發(fā)現(xiàn)當(dāng)前的二叉排序樹BT不是平衡的二叉排序樹，則立即將它轉(zhuǎn)換成新的平衡的二叉排序樹BT； (6)計(jì)算平衡的二叉排序樹BT的平均查找長(zhǎng)度，輸出結(jié)果。3、主要參考文獻(xiàn)1劉大有等，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），高等教育出版社2嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社3William Ford，William Topp，Data Structure with C+清華大學(xué)出版社4蘇仕華等，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，機(jī)械工業(yè)出版社4、課

3、程設(shè)計(jì)工作進(jìn)度計(jì)劃第1天 完成方案設(shè)計(jì)與程序框圖 第2、3天 編寫程序代碼第4天 程序調(diào)試分析和結(jié)果第5天 課程設(shè)計(jì)報(bào)告和總結(jié)指導(dǎo)教師（簽字）日期年 月 日教研室意見：年 月 日學(xué)生（簽字）： 接受任務(wù)時(shí)間： 年 月 日注：任務(wù)書由指導(dǎo)教師填寫。課程設(shè)計(jì)（論文）指導(dǎo)教師成績(jī)?cè)u(píng)定表題目名稱二叉排序樹與平衡二叉樹的實(shí)現(xiàn)評(píng)分項(xiàng)目分值得分評(píng)價(jià)內(nèi)涵工作表現(xiàn)20%01學(xué)習(xí)態(tài)度6遵守各項(xiàng)紀(jì)律，工作刻苦努力，具有良好的科學(xué)工作態(tài)度。02科學(xué)實(shí)踐、調(diào)研7通過(guò)實(shí)驗(yàn)、試驗(yàn)、查閱文獻(xiàn)、深入生產(chǎn)實(shí)踐等渠道獲取與課程設(shè)計(jì)有關(guān)的材料。03課題工作量7按期圓滿完成規(guī)定的任務(wù)，工作量飽滿。能力水平35%04綜合運(yùn)用知識(shí)的能力1

4、0能運(yùn)用所學(xué)知識(shí)和技能去發(fā)現(xiàn)與解決實(shí)際問(wèn)題，能正確處理實(shí)驗(yàn)數(shù)據(jù)，能對(duì)課題進(jìn)行理論分析，得出有價(jià)值的結(jié)論。05應(yīng)用文獻(xiàn)的能力5能獨(dú)立查閱相關(guān)文獻(xiàn)和從事其他調(diào)研；能提出并較好地論述課題的實(shí)施方案；有收集、加工各種信息及獲取新知識(shí)的能力。06設(shè)計(jì)（實(shí)驗(yàn)）能力，方案的設(shè)計(jì)能力5能正確設(shè)計(jì)實(shí)驗(yàn)方案，獨(dú)立進(jìn)行裝置安裝、調(diào)試、操作等實(shí)驗(yàn)工作，數(shù)據(jù)正確、可靠；研究思路清晰、完整。07計(jì)算及計(jì)算機(jī)應(yīng)用能力5具有較強(qiáng)的數(shù)據(jù)運(yùn)算與處理能力；能運(yùn)用計(jì)算機(jī)進(jìn)行資料搜集、加工、處理和輔助設(shè)計(jì)等。08對(duì)計(jì)算或?qū)嶒?yàn)結(jié)果的分析能力（綜合分析能力、技術(shù)經(jīng)濟(jì)分析能力）10具有較強(qiáng)的數(shù)據(jù)收集、分析、處理、綜合的能力。成果質(zhì)量45%0

5、9插圖（或圖紙）質(zhì)量、篇幅、設(shè)計(jì)（論文）規(guī)范化程度5符合本專業(yè)相關(guān)規(guī)范或規(guī)定要求；規(guī)范化符合本文件第五條要求。10設(shè)計(jì)說(shuō)明書（論文）質(zhì)量30綜述簡(jiǎn)練完整，有見解；立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理；實(shí)驗(yàn)正確，分析處理科學(xué)。11創(chuàng)新10對(duì)前人工作有改進(jìn)或突破，或有獨(dú)特見解。成績(jī)指導(dǎo)教師評(píng)語(yǔ)指導(dǎo)教師簽名： 年月日摘要及關(guān)鍵字 本程序中的數(shù)據(jù)采用“樹形結(jié)構(gòu)”作為其數(shù)據(jù)結(jié)構(gòu)。具體采用的是“二叉排序樹”。二叉排序樹（又稱二叉查找樹）：(1)若左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2)若右子樹不空，則右子樹上所有節(jié)點(diǎn)均大于它的根結(jié)點(diǎn)的值；(3)它的左右子樹分別為二叉排序樹。二叉平衡樹：若

6、不是空樹，則(1)左右子樹都是平衡二叉樹；(2)左右子樹的深度之差的絕對(duì)值不超過(guò)1。本次實(shí)驗(yàn)是利用二叉排序樹和平衡二叉樹達(dá)到以下目的：(1)以回車(n)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；(2)對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；(3)計(jì)算二叉排序樹T查找成功的平均查找長(zhǎng)度,輸出結(jié)果；(4)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無(wú)x”；(5)用數(shù)列L，生成平衡的二叉排序樹BT:當(dāng)插入新元素之后，發(fā)現(xiàn)當(dāng)前的二叉排序樹BT不是平衡的二叉排序樹，則立即將它轉(zhuǎn)換成新的平衡的二叉排序樹BT； (6)計(jì)算平衡的二叉排序樹BT的平

7、均查找長(zhǎng)度，輸出結(jié)果。關(guān)鍵字：數(shù)列L,結(jié)點(diǎn),二叉排序樹,平衡二叉樹目錄摘要 31 緒論 51.1 課程設(shè)計(jì)的目的 51.2 相關(guān)知識(shí)的闡述 51.2.1一位數(shù)組的存儲(chǔ)結(jié)構(gòu) 5 1.2.2建立二叉排序樹 51.2.3中序遍歷二叉樹 51.2.4平均查找長(zhǎng)度 61.2.5平均二叉樹（AVL樹） 61.2.6平衡因子 7 1.2.7平衡二叉樹的調(diào)整方法 72 方案設(shè)計(jì) 8 2.1 模塊功能83 算法設(shè)計(jì) 8 3.1 算法流程圖 84 詳細(xì)設(shè)計(jì) 10 4.1 主程序 10 4.2 定義二叉樹結(jié)構(gòu) 11 4.3 建立二叉樹 114.3.1二叉排序樹的查找114.3.2二叉排序樹的插入11 4.4 中序遍

8、歷12 4.5 平均查找長(zhǎng)度12 4.6 刪除節(jié)點(diǎn)12 4.7 判斷平衡二叉樹 135 調(diào)試分析 14 5.1 時(shí)間復(fù)雜度的分析14 5.2 運(yùn)行結(jié)果 14 5.3 結(jié)果分析 156 課程設(shè)計(jì)總結(jié) 16參考文獻(xiàn) 17 1 緒論1.1 課程設(shè)計(jì)的目的(1)使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?2)使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計(jì)的能力。(3)使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。1.2 相關(guān)知識(shí)的闡述1.2.1 一維數(shù)組的存儲(chǔ)結(jié)構(gòu)建立二插排序樹

9、，首先用一個(gè)一維數(shù)組記錄下讀入的數(shù)據(jù)，然后再用邊查找邊插入的方式將數(shù)據(jù)一一對(duì)應(yīng)放在完全二叉樹相應(yīng)的位置，為空的樹結(jié)點(diǎn)用“0” 補(bǔ)齊。1.2.2 建立二叉排序樹 二叉排序樹是一種動(dòng)態(tài)樹表。其特點(diǎn)是：樹的結(jié)構(gòu)通常不是一次生成的，而是在查找過(guò)程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的節(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子節(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。插入算法：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)；判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入；若二叉樹為空，則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。1.2.3 中序

10、遍歷二叉樹中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則(1)中序遍歷左子樹（L）；(2)訪問(wèn)根結(jié)點(diǎn)（V）；(3)中序遍歷右子樹（R）。中序遍歷二叉樹也采用遞歸函數(shù)的方式，先訪問(wèn)左子樹2i,然后訪問(wèn)根結(jié)點(diǎn)i,最后訪問(wèn)右子樹2i+1.先向左走到底再層層返回，直至所有的結(jié)點(diǎn)都被訪問(wèn)完畢。1.2.4 平均查找長(zhǎng)度計(jì)算二叉排序樹的平均查找長(zhǎng)度時(shí)，采用類似中序遍歷的遞歸方式，用s記錄總查找長(zhǎng)度，j記錄每個(gè)結(jié)點(diǎn)的查找長(zhǎng)度，s置初值為0，采用累加的方式最終得到總查找長(zhǎng)度s。平均查找長(zhǎng)度就等于s/i(i為樹中結(jié)點(diǎn)的總個(gè)數(shù))。假設(shè)在含有n(n=1)個(gè)關(guān)鍵字的序列中，i個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵字，n-i-

11、1個(gè)關(guān)鍵字大于第一個(gè)關(guān)鍵字，則由此構(gòu)造而得的二叉排序樹在n個(gè)記錄的查找概率相等的情況下，其平均查找長(zhǎng)度為： ASL(n,i)=1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)/n其中P(i)為含有i個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長(zhǎng)度，則P(i)+1為查找左子樹中每個(gè)關(guān)鍵字時(shí)所用比較次數(shù)的平均值，P（n-i-1）+1為查找右子樹中每個(gè)關(guān)鍵字時(shí)所用比較次數(shù)的平均值。又假設(shè)表中n個(gè)關(guān)鍵字的排列是“隨機(jī)”的，即任一個(gè)關(guān)鍵字在序列中將是第1個(gè)，或第2個(gè)，或第n個(gè)的概率相同，則可對(duì)上式從i等于0至n-1取平均值。最終會(huì)推導(dǎo)出： 當(dāng)n=2時(shí)，ASL(n)=2(11/n)ln(n)由此可見，在隨

12、機(jī)的情況下，二叉排序樹的平均查找長(zhǎng)度和log（n）是等數(shù)量級(jí)的。另外，含有n個(gè)結(jié)點(diǎn)的二叉排序樹其判定樹不是惟一的。對(duì)于含有同樣一組結(jié)點(diǎn)的表，由于結(jié)點(diǎn)插入的先后次序不同，所構(gòu)成的二叉排序樹的形態(tài)和深度也可能不同。而在二叉排序樹上進(jìn)行查找時(shí)的平均查找長(zhǎng)度和二叉樹的形態(tài)有關(guān)：在最壞情況下，二叉排序樹是通過(guò)把一個(gè)有序表的n個(gè)結(jié)點(diǎn)依次插入而生成的，此時(shí)所得的二叉排序樹蛻化為棵深度為n的單支樹，它的平均查找長(zhǎng)度和單鏈表上的順序查找相同，亦是(n+1)/2。在最好情況下，二叉排序樹在生成的過(guò)程中，樹的形態(tài)比較勻稱，最終得到的是一棵形態(tài)與二分查找的判定樹相似的二叉排序樹，此時(shí)它的平均查找長(zhǎng)度大約是lgn。插入、刪除和查找算法的時(shí)間復(fù)雜度均為O(lgn)。1.2.5 平衡