《排序二叉樹的應用數(shù)據(jù)結構專業(yè)課程設計報告.doc》由會員分享，可在線閱讀，更多相關《排序二叉樹的應用數(shù)據(jù)結構專業(yè)課程設計報告.doc（30頁珍藏版）》請在匯文網(wǎng)上搜索。

1、排序二叉樹的應用數(shù)據(jù)結構專業(yè)課程設計報告數(shù)據(jù)結構課程設計報告題目 : 排序二叉樹的應用一、設計任務1、 程序在運行時，可以執(zhí)行有關排序二叉樹的操作：如插入一個元素、刪除一個元素、查找一個元素、打印一個元素等。2、 用遞歸算法遍歷二叉樹。二 、設計分析1 、 二叉樹是n（n=0）個結點的有限集合，它或為空樹（n=0），或由一個根結點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。二叉樹是一個遞歸定義。一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。對滿二叉樹的結點進行連續(xù)編號，約定編號從根結點起，自上而下，自左而右。2 、 二叉樹的存儲結構1） 順序存儲結構：二叉樹可以采用順序存貯結

2、構，即用一維數(shù)組來存放二叉樹的數(shù)據(jù)元素。它是按照滿二叉樹的結點層次編號層次來依次存放二叉樹中的數(shù)據(jù)元素。2）鏈式存儲結構：設計不同的結點結構可構成不同形式的鏈式存儲結構。在本程序中，采用順序存儲結構，對二叉樹進行插人、刪除、查找、遍歷等操作。3 、 二叉樹的建立已知一棵二叉樹，共有n個結點，建立的方法如下：1） 照完全二叉樹的編號方法，對該二叉樹進行編號。2） 次輸入一個結點的值x和該結點的編號k，動態(tài)申請一塊空間來存放該結點，空間的地址為p。3） 把p值賦給adrk中。4） 如果k=1，轉到5；否則，把p的值填入其父結點的指針域中。p的父結點地址為adrk/2，若k為偶數(shù)，則做adrk/2-

3、lc=p；若為奇數(shù)，則做adrk/2-rc=p。5） 重復24，直到全部頂點數(shù)據(jù)輸入完為止。4 、 遍歷二叉樹，即如何按某條搜索路徑尋訪樹中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。一棵非空二叉樹是由根結點（D）、左子樹（L）和右子樹（R）三個基本部分組成。要遍歷這三個基本部分，可以有六種可能的順序。若限定先左后右，則只有三種情況：先序遍歷（DLR）、中序遍歷（LDR）、后序遍歷（LRD）。在本程序中，遍歷二叉樹函數(shù)的核心是以一個簡單的case語句來實現(xiàn)的。5 、 二叉樹的插入操作：這個操作首先生成一個新的結點結構，把數(shù)據(jù)存入新結點，然后搜索二叉樹尋找插入結點的位置，再把新結點連接

4、到二叉樹。把這個操作定義為一個函數(shù)，其函數(shù)名為instree。6 、 二叉樹中元素的查找：在許多情況下，我們需要在一棵已知的二叉樹中查找某個元素，以確定樹中是否存在這個元素。這種查找與鏈表數(shù)據(jù)結構中查找成員的情況極類似。查找函數(shù)名字定義為membertree。7 、 從二叉樹中刪除一個成員：進行成員刪除操作時，首先必須用遞歸函數(shù)遍歷這棵樹，找到這個元素。當找到這個元素之后，還要考慮以下四種不同的情況：刪除一個終端結點；刪除只有一個左孩子的結點；刪除只有一個右孩子的結點；刪除帶有兩個孩子的結點。刪除函數(shù)名字定義為deltree。8 、 在主函數(shù)main( )中，除了初始化指針tp之外，用循環(huán)語句

5、while(1)在屏幕上顯示出主菜單：I Insert an element into treeDDelete an element from the treeFFind a member in the treePPrint the treeQQuit用戶可以根據(jù)自己的需要，從鍵盤鍵入不同的合法字母（例如I），而進入不同的樹處理函數(shù)進行處理。不同樹處理函數(shù)的選擇是通過簡單的switchcase語句來實現(xiàn)，其中包括了若錯技術。如果用戶從鍵盤輸入的不是I，D，F(xiàn)，P，Q這些合法字符，則程序會先告訴用戶輸入出錯，讓用戶重新輸入，直到輸入選擇正確為止。三 、設計思路1 、主函數(shù)main() ：由cas

6、e語句組成，支持程序選擇，當運行時，可以執(zhí)行有關二叉樹的操作：如插入一個元素、刪除一個元素、查找一個元素、打印一個元素等。2 、主要的樹函數(shù)的說明部分1）void prttree(treeptr tnode,int t)；/打印樹。該函數(shù)在屏幕上打印出存放在樹中的元素，如果是空樹，則無輸出。參數(shù)：tnode-指向根結點的指針； t-打印方式：0：前序 1：中序 2：后序（用遞歸算法遍歷二叉樹）。 2）treeptr instree(char *s,int key,treeptr tnode)；/插入一個元素。該函數(shù)把一個元素插入到二叉樹中。參數(shù)：s,key-接收插入數(shù)據(jù)； tnode-是指向根

7、結點的指針。3）treeptr membertree(char *s,treeptr tnode)；/查找一個元素。該函數(shù)測定樹中的指定元素，如果元素是樹中的成員，則函樹返回該元素，否則返回NULL指針.。參數(shù)：s-指向要找的那個串的指針；tnode-指向樹根結點的指針。4）treeptr deltree(char *s,treeptr tnode)；/刪除一個元素。該函數(shù)刪除一個結點。參數(shù)：s-要刪除的結點的數(shù)據(jù)域的值； tnode-指向根結點的指針。5）treeptr findinspos(char *s,treeptr tnode)；/該函數(shù)尋找一個元素要插入的位置。開 始四 、流程圖輸

8、 入ch1、main( ) 函 數(shù) I P D F Q 其exit 它輸入s,key 輸 入輸 入 s s printf tp!=NULL tp=deltree Y N (s,tp) t=membe -tree(s,tp) printf printf break Yt!=NULLN 輸 入 printf printf任 意 數(shù)輸 入 i break輸 入 任 意 數(shù)prttree(tp,i)break輸入任意數(shù)break結 束 2、主 要 樹 函 數(shù)1） prttree( ) 函 數(shù) 開 始 tnode Y !=NULL Nt 0 1 2prttree(tnodprttree(tnodepri

9、ntf-e-left,t) -left,t)prttree(tnod printfprttree(tnod-e-left,t)-e-right,t)prttree(tnod prttree(tnod-e-right,t) -e-right,t)printf結 束2) instree( ) 函 數(shù)開 始 為t1分配空 間 Y t1=NULL N printf t1-right=NULLprintft1-left=NULLreturnt1-key(tnode) =key strcpy(t1-data,s)Ytnode=NULL N returnt2=findinspos(s,tonde) (t1) Y (strcmp(t2-data,s)right=t1 t2-left=t1return(tnode)結 束3) membertree( ) 函 數(shù) 開 始 t=tnode Nt!=NULL Ycmp=strcmp(t-data,s)Y cmp=0 Nreturn(t)Y cmpright t=t-left return(NULL)結 束4) findinspos( ) 函 數(shù)開 始Y(strcmp(tnode-data,s)=0NY tnode-left=NULL NYtnode-right=NULL N return(tnode) findinspos(s,tnode-