精選文檔二叉排序樹與平衡二叉樹的實(shí)現(xiàn)

攀枝花學(xué)院學(xué)生課程設(shè)計(jì)（論文）題目：二叉排序樹與平衡二叉樹的實(shí)現(xiàn)學(xué)生姓名：學(xué)號(hào)：所在院(系)：計(jì)算機(jī)學(xué)院專業(yè)：班級(jí)：指導(dǎo)教師：職稱：年月日攀枝花學(xué)院教務(wù)處制攀枝花學(xué)院本科學(xué)生課程設(shè)計(jì)任務(wù)書題目二叉排序樹與平衡二叉樹的實(shí)現(xiàn)1、課程設(shè)計(jì)的目的使學(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é)果；(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é)出版社［3］WilliamFord，WilliamTopp，《DataStructurewithC++》清華大學(xué)出版社［4］蘇仕華等，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，機(jī)械工業(yè)出版社4、課程設(shè)計(jì)工作進(jìn)度計(jì)劃第1天完成方案設(shè)計(jì)與程序框圖第2、3天編寫程序代碼第4天程序調(diào)試分析和結(jié)果第5天課程設(shè)計(jì)報(bào)告和總結(jié)指導(dǎo)教師（簽字）日期年月日教研室意見(jiàn)：年月日學(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í)的能力10能運(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%09插圖（或圖紙）質(zhì)量、篇幅、設(shè)計(jì)（論文）規(guī)范化程度5符合本專業(yè)相關(guān)規(guī)范或規(guī)定要求；規(guī)范化符合本文件第五條要求。10設(shè)計(jì)說(shuō)明書（論文）質(zhì)量30綜述簡(jiǎn)練完整，有見(jiàn)解；立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理；實(shí)驗(yàn)正確，分析處理科學(xué)。11創(chuàng)新10對(duì)前人工作有改進(jìn)或突破，或有獨(dú)特見(jiàn)解。成績(jī)指導(dǎo)教師評(píng)語(yǔ)指導(dǎo)教師簽名：年月日摘要：二叉排序樹：(1)若左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2)若右子樹不空，則右子樹上所有節(jié)點(diǎn)均大于它的根結(jié)點(diǎn)的值；(3)它的左右子樹分別為二叉排序樹。二叉平衡樹：若不是空樹，則(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的平均查找長(zhǎng)度，輸出結(jié)果。關(guān)鍵字：數(shù)列L,結(jié)點(diǎn),二叉排序樹,平衡二叉樹目錄TOC\o"1-3"\h\u14588對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果； 221712摘要： 419149第一章分析 677241.1功能描述 632300第二章系統(tǒng)設(shè)計(jì) 6257322.1基本概念介紹 68292樹的概念 6230972.3插入結(jié)點(diǎn) 8301542.4刪除結(jié)點(diǎn) 921402第一章編碼 10178113.1總體編碼 10139823.2總流程圖 1179103.3以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理 1226442bf=RH 1211628其他旋轉(zhuǎn)類推 1221829第二章測(cè)試 12245404.1創(chuàng)建平衡二叉樹測(cè)試 12161034.2插入結(jié)點(diǎn)測(cè)試 14219544.3刪除結(jié)點(diǎn)測(cè)試 1491984.4中序遍歷二叉樹 1513604第五章體會(huì) 1712927參考文獻(xiàn)： 17 第一章分析1.1描述平衡二叉樹（BalancedBinaryTree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。構(gòu)造與調(diào)整方法平衡二叉樹的常用算法有紅黑樹、AVL、Treap、伸展樹等。最小二叉平衡樹的節(jié)點(diǎn)的公式如下F(n)=F(n-1)+F(n-2)+1這個(gè)類似于一個(gè)遞歸的數(shù)列，可以參考Fibonacci數(shù)列1是根節(jié)點(diǎn)F(n-1)是左子樹的節(jié)點(diǎn)數(shù)量F(n-2)是右子數(shù)的節(jié)點(diǎn)數(shù)量。通過(guò)本程序的設(shè)計(jì)編寫所要求達(dá)到的目的是：充分理解和掌握二叉樹、平衡二叉樹的相關(guān)概念和知識(shí)。掌握平衡二叉樹的生成、結(jié)點(diǎn)刪除、插入等操作過(guò)程。并實(shí)現(xiàn)從鍵盤上輸入一系列數(shù)據(jù)（整型），建立一棵平衡二叉樹。任意插入或刪除一個(gè)結(jié)點(diǎn)后仍然要求構(gòu)成平衡二叉樹。按先序和中序遍歷輸出這棵平衡二叉樹。第二章系統(tǒng)設(shè)計(jì)2.1基本概念介紹樹的概念樹（Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）A個(gè)互不相交的有限集T1，T2Tm，其中每一個(gè)集合又是一棵樹，并且稱為根的子樹（SubTree）。ABCBCEDEDFFGGHH圖1是有8個(gè)結(jié)點(diǎn)的樹，其中A是根，其余結(jié)點(diǎn)分成2個(gè)子集：T1={B，D}，T2={C，E，F(xiàn)，G，H}；T1和T2都是根A的子樹，且本身也是一棵樹。平衡二叉樹的概念形態(tài)勻稱的二叉樹稱為平衡二叉樹(Balancedbinarytree)：若T是一棵非空二叉樹，其左、右子樹分別為TL和TR，令hl和hr分別為左、右子樹的深度。當(dāng)且僅當(dāng)①TL、TR都是平衡二叉樹；②｜hl－h(huán)r｜≤1；時(shí)，則T是平衡二叉樹?！纠咳鐖D1-2所示：AAAAAACBCBCBCBCBCBEFDDEFDDHGHG（a）平衡二叉樹（b）非平衡二叉樹圖1-2平衡二叉樹與非平衡二叉樹圖2-7平衡二叉樹的生成過(guò)程2.3插入結(jié)點(diǎn)在平衡二叉排序樹BBST上插入一個(gè)新數(shù)據(jù)元素e的遞規(guī)算法可以描述如下：若BBST為空樹，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)作為BBST的根結(jié)點(diǎn)，樹的深度增加1；若e的關(guān)鍵字和BBST的根結(jié)點(diǎn)的關(guān)鍵字相等，則不進(jìn)行插入；若e的關(guān)鍵字小于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的左子樹中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的左子樹上，并且當(dāng)插入之后的左子樹深度增加1時(shí)，分別就下列情況處理之：BBST的根結(jié)點(diǎn)的平衡因子為－1（右子樹深度大于左子樹深度）：則將根結(jié)點(diǎn)的平衡因子更改為0，BBST的深度不變；BBST的根結(jié)點(diǎn)的平衡因子為0（左，右子樹深度相等）：則將根結(jié)點(diǎn)的平衡因子更改為1，BBST的深度增加1；BBST的根結(jié)點(diǎn)的平衡因子為1（左子樹深度大于右子樹深度）：若BBST的左子樹根結(jié)點(diǎn)的平衡因子為1，則需要進(jìn)行單向右旋平衡處理，并且在右旋處理之后將根結(jié)點(diǎn)和右子樹根結(jié)點(diǎn)的平衡因子更改為0，樹的深度不變；若BBST的左子樹根結(jié)點(diǎn)的平衡因子為－1，這需進(jìn)行先向左后向右的雙向旋轉(zhuǎn)平衡處理，并且在旋轉(zhuǎn)處理之后，修改根結(jié)點(diǎn)和其左、右子樹根結(jié)點(diǎn)的平衡因子，樹的深度不變；若e的關(guān)鍵字大于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的右子樹中不存在和e相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的右子樹上，并且當(dāng)插入之后的右子樹深度增加1時(shí)，分別就不同情況處理。2.4刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)過(guò)程與插入結(jié)點(diǎn)的操作類似，基本過(guò)程是：平衡二叉樹--找到要?jiǎng)h除的結(jié)點(diǎn)--刪除一個(gè)結(jié)點(diǎn)--變成二叉樹--旋轉(zhuǎn)--變回平衡二叉樹。具體過(guò)程將詳細(xì)設(shè)計(jì)中的代碼。2.5中序遍歷右遍歷的定義可知，中序遍歷二叉樹的遞規(guī)算法可以定義為：若二叉樹為空，則空操作；否則中序遍歷左子樹訪問(wèn)根結(jié)點(diǎn)中序遍歷右子樹如中序遍歷圖2-8的二叉樹，結(jié)點(diǎn)的訪問(wèn)順序?yàn)椋篴→b→c→d→e→f→g圖2-8編碼3.1總體編碼#include"stdio.h"#include"string.h"#include<stdlib.h>#defineMax20//結(jié)點(diǎn)的最大個(gè)數(shù)typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定義二叉樹的結(jié)點(diǎn)類型typedefBinTNode*BinTree;//定義二叉樹的指針intNodeNum,leaf;//NodeNum為結(jié)點(diǎn)數(shù)，leaf為葉子數(shù)//==========基于先序遍歷算法創(chuàng)建二叉樹==============//=====要求輸入先序序列，其中加入虛結(jié)點(diǎn)"#"以示空指針的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL);//讀入#，返回空指針else{T=(BinTNode*)malloc(sizeof(BinTNode));//生成結(jié)點(diǎn)T->data=ch;T->lchild=CreatBinTree();//構(gòu)造左子樹T->rchild=CreatBinTree();//構(gòu)造右子樹return(T);}}//========NLR先序遍歷=============voidPreorder(BinTreeT){if(T){printf("%c",T->data);//訪問(wèn)結(jié)點(diǎn)Preorder(T->lchild);//先序遍歷左子樹Preorder(T->rchild);//先序遍歷右子樹}}//========LNR中序遍歷===============voidInorder(BinTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);}}//==========LRN后序遍歷============voidPostorder(BinTreeT){if(T){Postorder(T->lchild);Postorder(T->rchild);printf("%c",T->data);}}//=====采用后序遍歷求二叉樹的深度、結(jié)點(diǎn)數(shù)及葉子數(shù)的遞歸算法========inthl,hr,max;TreeDepth(BinTreeT){if(T){hl=TreeDepth(T->lchild);//求左深度hr=TreeDepth(T->rchild);//求右深度max=hl>hr?hl:hr;//取左右深度的最大值NodeNum=NodeNum+1;//求結(jié)點(diǎn)數(shù)if(hl==0&&hr==0)leaf=leaf+1;//若左右深度為0，即為葉子。return(max+1);}elsereturn(0);}//====利用"先進(jìn)先出"（FIFO）隊(duì)列，按層次遍歷二叉樹==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p;//定義結(jié)點(diǎn)的指針數(shù)組cqcq[1]=T;//根入隊(duì)while(front!=rear){front=(front+1)%NodeNum;p=cq[front];//出隊(duì)printf("%c",p->data);//出隊(duì)，輸出結(jié)點(diǎn)的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;//左子樹入隊(duì)}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild;//右子樹入隊(duì)}}}//==========主函數(shù)=================voidmain(){BinTreeroot;inti,depth;printf("\n");printf("CreatBin_Tree；Inputpreorder:");//輸入完全二叉樹的先序序列，//用#代表虛結(jié)點(diǎn)，如ABD###CE##F##root=CreatBinTree();//創(chuàng)建二叉樹，返回根結(jié)點(diǎn)do{//從菜單中選擇遍歷方式，輸入序號(hào)。printf("\t**********select************\n");printf("\t1:PreorderTraversal\n");printf("\t2:IorderTraversal\n");printf("\t3:Postordertraversal\n");printf("\t4:PostTreeDepth,Nodenumber,Leafnumber\n");printf("\t5:LevelDepth\n");//按層次遍歷之前，先選擇4，求出該樹的結(jié)點(diǎn)數(shù)。printf("\t0:Exit\n");printf("\t*******************************\n");scanf("%d",&i);//輸入菜單序號(hào)（0-5）switch(i){case1:printf("PrintBin_treePreorder:");Preorder(root);//先序遍歷break;case2:printf("PrintBin_TreeInorder:");Inorder(root);//中序遍歷break;case3:printf("PrintBin_TreePostorder:");Postorder(root);//后序遍歷break;case4:depth=TreeDepth(root);//求樹的深度及葉子數(shù)printf("BinTreeDepth=%dBinTreeNoden