廣工數(shù)據(jù)結(jié)構(gòu)課設(shè)-平衡二叉樹演示(文檔尾部含源碼下載地址)

課程設(shè)計報告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計學(xué)院計算機學(xué)院專業(yè)班級計科9班學(xué)號學(xué)生姓名指導(dǎo)教師蘇慶2023年7月6日需求分析程序《平衡二叉樹的演示》是對平衡二叉樹的創(chuàng)立、插入、刪除、查找、合并、分裂功能的實現(xiàn)，以及用凹入表的形式將其展示給用戶。輸入的形式是數(shù)字，無論對功能的選那么還是對數(shù)據(jù)的錄入，都是以數(shù) 字的形式進行輸入，無需使用文件保存數(shù)據(jù)。輸入值得范圍在使用過程 中會有說明。輸出的形式是在Dos界面進行輸出，程序所能到達的功能：A.創(chuàng)立一棵非空平衡二叉樹B.創(chuàng)立一棵空的平衡二叉樹C.向平衡二叉樹中添加結(jié)點D.從平衡二叉樹中刪除結(jié)點E.在平衡二叉樹中查找結(jié)點F.以凹入表的形式輸出一棵二叉樹G.以括號表示法輸出一棵二叉樹附加功能：F.合并兩棵平衡二叉樹H.分裂一棵平衡二叉樹概要設(shè)計本程序涉及到的數(shù)據(jù)類型有：鏈棧，鏈隊列，平衡二叉樹，結(jié)構(gòu)體數(shù)組〔2〕主程序是負(fù)責(zé)對各個功能進行展示，然后根據(jù)輸入來選擇進行相對應(yīng) 的功能，代碼如下：intmain(){ intm; BBSTreeT=NULL; SetColor(); InitView(); printf("\n\t\t\t請輸入你的選擇："); scanf("%d",&m); getchar(); while(1){ switch(m){ case1: T=item_1(); break; case2: item_2(T); break; case3: item_3(T); break; case4: item_4(T); break; case5: item_5(T); break; case6: item_6(); break; case7: item_7(); break; } if(m==8){ item_8(); break; }elseif(m>8||m<1){ system("CLS"); InitView(); printf("\n\t\t\t輸入錯誤，請重新輸入!!\n"); } printf("\n\t\t\t請輸入你的選擇："); scanf("%d",&m); getchar(); } return0;}各模塊之間的關(guān)系三、詳細(xì)設(shè)計數(shù)據(jù)類型的定義/*存放輸入數(shù)據(jù)的數(shù)組結(jié)構(gòu)體*/typedefstructArrayNode{RcdTypedata;ArrayNode*next;}ArrayNode,*Array;/*平衡二叉樹結(jié)構(gòu)體*/typedefstructBBSTNode{RcdTypedata;intbf;BBSTNode*lchild,*rchild;}BBSTNode,*BBSTree;/*鏈隊列結(jié)構(gòu)體*/typedefstructLQNode{BBSTreeelem;structLQNode*next;}LQNode,*QueuePtr;/*隊列結(jié)點結(jié)構(gòu)體*/typedefstruct{QueuePtrfront;QueuePtrrear;}LQueue;/*棧結(jié)點結(jié)構(gòu)體*/typedefstructLSNode{BBSTreedata;//數(shù)據(jù)域structLSNode*next;//指針域}LSNode,*LStack;//結(jié)點和鏈棧類型偽代碼：建樹操作beginBBSTreeTArrayaa=GetInputToArray();//獲取到輸入的數(shù)組Whilea!=NULL{InsertAVL(T,a->data)a=>a->next}EndB.插入結(jié)點beginif(NULL==T){T->data=eT->bf=EHT->lchild=NULLT->rchild=NULL}elseif(e==T->data){//書中已存在和e相等的結(jié)點returnFALSE;}elseif(e<T->data){if(!InsertAVL(T->lchild,e))returnFALSE;if(TRUE==taller){switch(T->bf){caseLH:LeftBalance(T);taller=FALSE; break;caseEH:T->bf=LH;taller=TRUE;break;caseRH:T->bf=EH;taller=FALSE;break;}}}else{if(FALSE==InsertAVL(T->rchild,e))returnFALSE;if(TRUE==taller){switch(T->bf){caseLH:T->bf=EH;taller=FALSE;break;caseEH:T->bf=RH;taller=TRUE;break;caseRH:RightBalance(T);taller=FALSE; break;}}}returnTRUE;EndC.刪除操作begin//當(dāng)被刪結(jié)點是有兩個孩子，且其前驅(qū)結(jié)點是左孩子時，tag=1staticinttag=0;if(t==NULL){returnFALSE;//如果不存在元素，返回失敗}elseif(e==t->data){BBSTNode*q=NULL;//如果該結(jié)點只有一個孩子，那么將自子樹取代該結(jié)點if(t->lchild==NULL){q=t;t=t->rchild;free(q);shorter=TRUE;}elseif(t->rchild==NULL){q=t;t=t->lchild;free(q);shorter=TRUE;}//如果被刪結(jié)點有兩個孩子，那么找到結(jié)點的前驅(qū)結(jié)點，//并將前驅(qū)結(jié)點的值賦給該結(jié)點，然后刪除前驅(qū)結(jié)點else{q=t->lchild;while(q->rchild){q=q->rchild;}t->data=q->data;if(t->lchild->data==q->data){tag=1;}DeleteAVL(t->lchild,q->data,shorter);if(tag==1){BBSTreer=t->rchild;if(NULL==r)t->bf=0;else{switch(r->bf){caseEH:t->bf=-1;break;default:RightBalance(t);break;}}}}}elseif(e<t->data){//左子樹中繼續(xù)查找if(!DeleteAVL(t->lchild,e,shorter)){returnFALSE;}//刪除完結(jié)點之后，調(diào)整結(jié)點的平衡因子if(shorter&&(tag==0)){switch(t->bf){caseLH:t->bf=EH;shorter=TRUE;break;caseEH:t->bf=RH;shorter=FALSE;break;//如果本來就是右子樹較高，刪除之后就不平衡，需要做右平衡操作caseRH:RightBalance(t);//右平衡處理if(t->rchild->bf==EH)shorter=FALSE;elseshorter=TRUE;break;}}}elseif(e>t->data){//右子樹中繼續(xù)查找if(!DeleteAVL(t->rchild,e,shorter)){returnFALSE;}//刪除完結(jié)點之后，調(diào)整結(jié)點的平衡因子if(shorter&&(tag==0)){switch(t->bf){caseLH:LeftBalance(t);//左平衡處理if(t->lchild->bf==EH)shorter=FALSE;elseshorter=TRUE;break;caseEH:t->bf=LH;shorter=FALSE;break;caseRH:t->bf=EH;shorter=TRUE;break;}}if(tag==1){intdepthLeft=BBSTreeDepth(t->lchild);intdepthRight=BBSTreeDepth(t->rchild);t->bf=depthLeft-depthRight;}}returnTRUE;EndD.查找操作Beginif(T==NULL)returnNULL;if(e==T->data){returnT;}elseif(e>T->data){returnSearchAVL(T->rchild,e);}else{returnSearchAVL(T->lchild,e);}EndE.合并操作BeginStatustaller=TRUE;Arraya=NULL;a=GetArrayFromTree(T2);while(a!=NULL){taller=TRUE;InsertAVL(T1,a->data,taller);a=a->next;}returnT1;EndF.分裂操作BeginArraya=NULL;Statustaller;a=GetArrayFromTree(Tt1);//獲取到樹轉(zhuǎn)化為的數(shù)組if(Tt1==NULL)returnFALSE;else{while(a!=NULL){if(a->data<=x){taller=TRUE;InsertAVL(Tt2,a->data,taller);a=a->next;}else{taller=TRUE;InsertAVL(Tt3,a->data,taller);a=a->next;}}}returnTRUE;End關(guān)系圖建樹操作B.添加結(jié)點操作C.刪除結(jié)點操作D.查找結(jié)點操作E.合并操作F.分裂操作調(diào)試分析調(diào)試過程中所遇到的問題：運行過程中程序停止運行。遇到這個情況一開始我以為是編譯器有問題，但是換了個編譯器還是同樣的問題，后來我上網(wǎng)查詢了有關(guān)資料，大概明白了是自己的代碼出現(xiàn)了問題。所以只能將新增的代碼注釋掉，一條一條測試，調(diào)試過程很漫長，最后才發(fā)現(xiàn)是內(nèi)存泄露和空指針異常，將指針不適用之后指向為NULL，才把問題解決了。經(jīng)驗和體會在做一個比擬大的程序過程中，應(yīng)該學(xué)會邊編寫程序邊運行，即當(dāng)你完成了一個比擬小的功能時便對其調(diào)試，這樣有助于我們高效地完成工程，而且在調(diào)試BUG的過程也可以大大減小其難度。必須要有良好的編程習(xí)慣。首先編碼風(fēng)格一定要標(biāo)準(zhǔn)，這樣不僅有利于讀者和編程者對代碼的閱讀，更有利于對代碼的維護。其次要對代碼要細(xì)心，比擬一些指針的初始化和不需要時指為空，這些都是可以極大減少我們出現(xiàn)BUG的幾率。寫的程序一定要人性化，現(xiàn)在的應(yīng)用都講究與人交互的重要性，其防止不了使用各種炫酷的圖形界面，但我們要考慮的是，即便是C語言，沒有什么圖形界面，我們也一定要考慮人性化的問題。使用說明本程序的可執(zhí)行文件是：平衡二叉樹的演示.exe雙擊exe文件，進入主界面：然后我們應(yīng)該先創(chuàng)立一棵非空二叉樹或者是空的二叉樹，輸入1或者2， 按回車鍵，此處我們輸入1，如下：此時，程序提示我們輸入樹的序列，我們可以以此輸入數(shù)字，不同數(shù)字用 空格隔開，按回車表示輸入完成，例如，我們輸入102030405060回車， 得到如下，程序提示我們創(chuàng)立成功，并輸出了該平衡二叉樹，此時按任意 鍵返回。返回到了首頁，此時我們可以輸入3，往此樹中添加結(jié)點，按回車確認(rèn)。此時，程序會把平衡二叉樹展示出來，然后提示用戶輸入要刪除的元素