數(shù)據(jù)結(jié)構(gòu)課設(shè)任務(wù)書-文庫(kù)吧
2025-06-02 16:58 本頁(yè)面
【正文】 int y。 int num。}BTNode。 ： 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可惟一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合。 基本操作P： node*createBTNode(BTNode*amp。t,char*str) 操作結(jié)果：先序遍歷創(chuàng)建二叉樹。 PreOrder(BTNode*t,int m,int v) 初始條件：二叉樹存在； 操作結(jié)果：先序遍歷二叉樹。 inOrder(BTNode*t,int m,int v) 初始條件：二叉樹存在； 操作結(jié)果：中序遍歷二叉樹。 postOrder(BTNode*t,int w,int v) 初始條件：二叉樹存在； 操作結(jié)果：后序遍歷二叉樹。 node*DrawOriginTree(BTNode*t,char*str,int x,int y) 初始條件：二叉樹存在； 操作結(jié)果：將二叉樹用圖形表示出來(lái)。 rgcreate() 操作結(jié)果：人工輸入二叉樹序列。 sjcreate() 操作結(jié)果：隨機(jī)生成二叉樹序列。 ： 用戶在主界面中選擇出輸入模塊，繼續(xù)執(zhí)行小界面中的其他模塊。 ： 主界面 人工輸入 隨機(jī)生成 退出 用戶提示界面后序遍歷中序遍歷先序遍歷 ： 主界面： main() 用戶選擇界面 人工輸入模塊： rgcreate() 用戶手動(dòng)輸入二叉樹序列 隨機(jī)生成模塊： sjcreate() 系統(tǒng)隨機(jī)產(chǎn)生二叉樹序列 先序遍歷模塊： PreOrder(） 系統(tǒng)界面用圖的形式將二叉樹的先 序遍歷顯示出來(lái) 中序遍歷模塊： inOrder() 系統(tǒng)界面用圖的形式將二叉樹的中序遍歷顯示出來(lái) 后序遍歷模塊： postOrder() 系統(tǒng)界面用圖的形式將二叉樹的后序遍歷顯示出來(lái) 退出模塊： exit（0） 退出程序三、詳細(xì)設(shè)計(jì)： ： 開始int top=1,k,j=0。charch。t=NULL。ch=*str。 ch!=39。\039。No Yesdefault:p=(BTNode*)malloc(sizeof(BTNode))。plchild=prchild=NULL。pdata=chcase 39。,39。: k=2。case 39。)39。: top。case’(39。:top++。st[top]=p。k=1。 t==NULL Yes t=p。 Nocase2:st[top]rchild=p。case1:st[top]lchild=p。 str++。ch=*str。 return t。 結(jié)束： 開始int i=0,x=90,x1,x2,y1,y2。 char ch。int top=1,c,w,d。 t!=NULL No Yes top++。 st[top]=t。 top1 No Yes p=st[top]。top。ch=pdata。i++。 prchild!=NULL top++。 st[top]=prchild。plchild!=NULL top++。 st[top]=plchild。 結(jié)束 ： 開始int flag,top=1。char ch。 t!=NULL No top++。st[top]=t。 Yestlchild!=NULL t=tlchild。 No Yes p=NULL；flag=1。top!=1 amp。amp。 flag Not=st[top]。 trchild==p Yes Noch=tdata。i++。top。p=t。trchild!=NULL t=trchild。flag=0。 top!=1 Yes 結(jié)束： int top=1。 開始 b!=NULL? No top1 top1||p!=NULL Yes p=st[top]。top。p=prchild。 printf(%c,pdata)。 p=prchild。 printf(%c,pdata)。 p=prchild。top++。st[top]=p。p=plchild。 結(jié)束： ： （1)創(chuàng)建二叉樹的部分，用ch掃描str，有四種字符：ch=39。(39。:表示前面剛創(chuàng)建的節(jié)點(diǎn)*p存在孩子節(jié)點(diǎn)，需要將其進(jìn)棧，以便建立它和其孩子節(jié)點(diǎn)的關(guān)系，然后開始處理左孩子，k=1，其后創(chuàng)建的節(jié)點(diǎn)作為它的左孩子節(jié)點(diǎn)。ch=39。)39。:表示創(chuàng)建完畢，將其退棧。ch=39。,39。:開始處理?xiàng)ｍ敼?jié)點(diǎn)的右孩子結(jié)點(diǎn)。 ： (1)先序遍歷過(guò)程是先訪問(wèn)根節(jié)點(diǎn)，在訪問(wèn)左子樹，最后才是右子樹。因此，先將根節(jié)點(diǎn)進(jìn)棧，在棧不空的情況下循環(huán)：出棧p,訪問(wèn)*p節(jié)點(diǎn)，若其右孩子結(jié)點(diǎn)不空將右孩子節(jié)點(diǎn)進(jìn)棧，若其左孩子節(jié)點(diǎn)不空再將其左孩子節(jié)點(diǎn)進(jìn)棧。 ： （1）中序遍歷過(guò)程是先訪問(wèn)二叉樹的最左下方節(jié)點(diǎn)，其基本思路是先找到二叉樹的開始節(jié)點(diǎn)，將其訪問(wèn)，再處理其右子樹。用指針指向當(dāng)前要處理的節(jié)點(diǎn)。先掃描根節(jié)點(diǎn)的所有左節(jié)點(diǎn)，并將它們一一進(jìn)棧，當(dāng)無(wú)左節(jié)點(diǎn)時(shí)表示棧頂節(jié)點(diǎn)無(wú)左子樹，然后出棧這個(gè)節(jié)點(diǎn)，并訪問(wèn)，將p指向剛出棧節(jié)點(diǎn)的右孩子，對(duì)右子樹進(jìn)行同樣的處理。如此重復(fù)操作，直到?？諡橹?。 ： （1）后序遍歷過(guò)程是先訪問(wèn)左子樹，然后訪問(wèn)右子樹，最后訪問(wèn)根節(jié)點(diǎn)。采用一個(gè)棧保存需要返回的節(jié)點(diǎn)指針，先掃描根節(jié)點(diǎn)的所有左孩子節(jié)點(diǎn)并一一進(jìn)棧，出棧一個(gè)節(jié)點(diǎn)*t作為當(dāng)前節(jié)點(diǎn),然后掃描該節(jié)點(diǎn)的右子樹。當(dāng)一個(gè)
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1