數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--樹的應(yīng)用

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p><b>　　設(shè)計(jì)題目：樹的應(yīng)用</b></p><p>　　年 級 </p><p>　　班

2、 級 </p><p>　　姓 名 </p><p>　　學(xué) 號 </p><p>　　指導(dǎo)教師 </p&

3、gt;<p>　　起止時(shí)間 12—9—24-----------9—28 </p><p>　　2012--2013 年 一 學(xué)期</p><p><b>　　一．實(shí)習(xí)目的</b></p><p>　　更加深入的理解、掌握數(shù)據(jù)結(jié)構(gòu)的一些算法并加以實(shí)現(xiàn)，提高自身的地動手實(shí)踐能力，培養(yǎng)更好的團(tuán)隊(duì)合作能力。&l

4、t;/p><p>　　二．問題描述（具體任務(wù)）</p><p>　　設(shè)計(jì)、創(chuàng)建一棵樹，實(shí)現(xiàn)樹與二叉樹的互相轉(zhuǎn)換以及對樹的遞歸 非遞歸先序遍歷，樹的遞歸非遞歸后序遍歷以及樹的非遞歸層次遍歷的操作。</p><p><b>　　三．需求分析</b></p><p>　　1、本演示程序中，可以輸入任意個(gè)節(jié)點(diǎn)構(gòu)造你想要的樹，本程序構(gòu)

5、造時(shí)默認(rèn)的是一個(gè)三度的樹，也就是在創(chuàng)建樹時(shí)所默認(rèn)的是每個(gè)節(jié)點(diǎn)都有三個(gè)孩子，但是你可以通過鍵盤輸入#號來讓某些節(jié)點(diǎn)為空，以此來創(chuàng)建讓您滿意的樹。</p><p>　　2、程序以用戶和計(jì)算機(jī)對話的形式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入要?jiǎng)?chuàng)建樹的節(jié)點(diǎn)值，然后通過程序執(zhí)行輸出結(jié)果。</p><p>　　3、程序的執(zhí)行命令包括：</p><p>&

6、lt;b>　?。?）樹的創(chuàng)建模塊</b></p><p>　?。?）樹與二叉樹相互轉(zhuǎn)換模塊</p><p>　?。?）樹的先序、后序、層次遍歷（遞歸與非遞歸算法）</p><p><b>　　4、測試數(shù)據(jù)：</b></p><p>　?。?）測試數(shù)據(jù)由用戶從鍵盤上任意輸入。</p><

7、;p>　　四．算法設(shè)計(jì)思想及流程圖</p><p>　　（1）根據(jù)老師所提供的課程設(shè)計(jì)題目及要求我們將程序分了9個(gè)模塊，通過主程序調(diào)用相應(yīng)的模塊來實(shí)現(xiàn)課程的操作。</p><p>　　五．C++語言源代碼</p><p>　　#include <iostream></p><p>　　using namespace std;

8、</p><p>　　#define m 3</p><p>　　typedef char ElemType;</p><p>　　typedef struct Node {</p><p>　　ElemType data;</p><p>　　struct Node* child[m];</p><

9、;p>　　}Node,*Tree;</p><p>　　typedef struct BiTNode{</p><p>　　ElemType data;</p><p>　　struct BiTNode*lchild,*rchild;</p><p>　　}BiTNode,*BiTree;</p><p>　　t

10、ypedef struct stack { //棧結(jié)構(gòu)定義</p><p>　　BiTree data[100]; //data 元素類型為 指針</p><p>　　int top; //棧頂指針</p><p>　　}seqstack;</p><p>　　/

11、/ 按前序遍歷 創(chuàng)建一棵度數(shù)為3的樹的遞歸算法</p><p>　　void createtree(Tree &p) {</p><p><b>　　int i;</b></p><p><b>　　char ch;</b></p><p>　　if((ch=getchar())==

12、9;#') p=NULL; //建立一棵空樹</p><p><b>　　else {</b></p><p>　　p=(Tree)malloc(sizeof(Node)); </p><p>　　p->data=ch;</p><p>　　for(i=0;i<m;i++)</p&g

13、t;<p>　　createtree(p->child[i]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//樹轉(zhuǎn)化為二叉樹</b></p><p>　　BiTree TreetoBiTre

14、e(Tree &p) {</p><p><b>　　int i;</b></p><p>　　if(p==NULL)</p><p>　　return NULL;</p><p>　　BiTNode* q=(BiTNode*)malloc(sizeof(ElemType)) ;//創(chuàng)建根節(jié)點(diǎn)----------

15、--------------------------------------------------</p><p>　　q->data =p->data;</p><p>　　q->lchild=NULL;</p><p>　　q->rchild=NULL;</p><p>　　if(p->child[0]!=

16、NULL){</p><p>　　q->lchild=TreetoBiTree(p->child[0]);//把樹的第一個(gè)孩子賦給二叉樹的左孩子</p><p>　　BiTNode* r=q->lchild;</p><p>　　if(p->child[1]!=NULL) {</p><p>　　for(i=1;i&l

17、t;m;i++) {</p><p>　　if(p->child[i]!=NULL) {</p><p>　　r->rchild=TreetoBiTree(p->child [i]);</p><p>　　r=r->rchild;</p><p><b>　　}</b></p>&l

18、t;p><b>　　else</b></p><p><b>　　return q;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else if(p->child[2]!=NULL

19、){</p><p>　　r->rchild=TreetoBiTree(p->child [2]);</p><p>　　r=r->rchild;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>&

20、lt;b>　　return q;</b></p><p><b>　　}</b></p><p>　　else if((p->child[1]!=NULL)){</p><p>　　q->lchild=TreetoBiTree(p->child[1]); //把樹的第二個(gè)孩子賦給二叉樹的左孩子</

21、p><p>　　BiTNode* r=q->lchild;</p><p>　　if(p->child[2]!=NULL) {</p><p>　　r->rchild=TreetoBiTree(p->child [2]);</p><p><b>　　}</b></p><p>

22、;<b>　　else</b></p><p><b>　　return q;</b></p><p><b>　　}</b></p><p>　　else if(p->child[2]!=NULL) {</p><p>　　q->lchild=TreetoBiTr

23、ee(p->child[1]); //把樹的第三個(gè)孩子賦給二叉樹的左孩子</p><p><b>　　}</b></p><p><b>　　return q;</b></p><p><b>　　}</b></p><p><b>　　//二叉樹轉(zhuǎn)換為樹&

24、lt;/b></p><p>　　Tree BiTreetoTree(BiTree &q) {</p><p><b>　　int i;</b></p><p>　　if(q==NULL)return NULL;</p><p>　　Node* p=(Node*)malloc(sizeof(ElemType

25、));</p><p>　　p->data=q->data;//根賦值</p><p>　　for(i=0;i<m;i++) {</p><p>　　p->child[i]=NULL;</p><p><b>　　}</b></p><p>　　if(q->lchil

26、d!=NULL) {</p><p>　　p->child[0]=BiTreetoTree(q->lchild);</p><p>　　BiTNode* r=q->lchild ;</p><p>　　for(i=1;i<m;i++) {</p><p>　　if(r->rchild!=NULL) {</p

27、><p>　　p->child[i]=BiTreetoTree(r->rchild );</p><p>　　r=r->rchild ;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}&l

28、t;/b></p><p><b>　　return p;</b></p><p><b>　　}</b></p><p>　　void push(seqstack* s,BiTree p) { //進(jìn)棧</p><p>　　s->data[++s->t

29、op]=p;</p><p><b>　　}</b></p><p>　　BiTree pop(seqstack* s) { //出棧</p><p>　　if(s->top!=-1) { //非遞歸遍歷中，top初始值為-1</p><p><b>　　s-

30、>top--;</b></p><p>　　return (s->data[s->top+1]);</p><p><b>　　}</b></p><p><b>　　else </b></p><p>　　return NULL;</p><p&g

31、t;<b>　　}</b></p><p>　　//二叉樹中序遍歷 (樹的后序非遞歸遍歷)非遞歸 算法</p><p>　　void inorder1(BiTree p) {</p><p>　　seqstack s;</p><p><b>　　s.top=-1;</b></p>&

32、lt;p>　　while((p!=NULL)||(s.top!=-1)) {</p><p>　　while(p) {</p><p>　　push(&s,p); </p><p>　　p=p->lchild; //子樹根結(jié)點(diǎn)全部進(jìn)棧</p><p><b>　　}</b>

33、</p><p>　　if(s.top!=-1) {</p><p>　　p=pop(&s);</p><p>　　printf("%c",p->data); //輸出根結(jié)點(diǎn)，其實(shí)也就是左孩子或右孩子(沒有孩子的根結(jié)點(diǎn)是它父親的左或右孩子）</p><p>　　p=p->rchild;

34、 //進(jìn)入右孩子訪問</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void visit(char ch)</p><p>　　{cout<<

35、ch;}</p><p>　　//二叉樹先序遍歷非遞歸算法</p><p>　　void PreOrderPrint(BiTree p) {</p><p>　　seqstack s;</p><p>　　s.top=-1; //top初始值為-1</p><p>

36、　　while((p!=NULL)||(s.top!=-1)) { // 當(dāng)前處理的子樹 不為空，或棧不為空，則循環(huán)</p><p>　　while(p) {</p><p>　　visit(p->data); //訪問當(dāng)前子樹根結(jié)點(diǎn)</p><p><b>　　s.top++;</b></p

37、><p>　　s.data[s.top]=p; //當(dāng)前子樹根結(jié)點(diǎn)進(jìn)棧(因?yàn)檫€要訪問右子樹)</p><p>　　p=p->lchild; //訪問此根結(jié)點(diǎn) 左孩子</p><p>　　} //循環(huán)直到遍歷完當(dāng)前子樹根結(jié)點(diǎn)，和其左孩子</p><p>　　if(s.

38、top>-1) {</p><p>　　p=pop(&s); //當(dāng)前子樹跟結(jié)點(diǎn)出棧</p><p>　　p=p->rchild; //訪問其右孩子</p><p><b>　　}</b></p><p><b>　　}&l

39、t;/b></p><p><b>　　} </b></p><p>　　//樹的前序遍歷遞歸算法</p><p>　　void preorder(Tree p) { //P為指向樹根的指針</p><p><b>　　int i;</b></p><p&

40、gt;　　if(p!=NULL) { //樹不為空</p><p>　　printf("%c",p->data); //輸出根節(jié)點(diǎn)的值</p><p>　　for(i=0;i<m;i++) //依次遞歸實(shí)現(xiàn)各子樹的前序遍歷</p><p>　　preorder(p->

41、child[i]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//樹的后序遍歷的遞歸算法</p><p>　　void postorder(Tree p) {</p><p><b>　　int i;<

42、;/b></p><p>　　if(p!=NULL) {</p><p>　　for(i=0;i<m;i++) //依次遞歸實(shí)現(xiàn)個(gè)子樹的后序遍歷</p><p>　　postorder(p->child[i]);</p><p>　　printf("%c",p->data);

43、 //輸出根節(jié)點(diǎn)的值</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//樹的非遞歸層次遍歷</p><p>　　void level(Tree t) {</p><p>　　Tree queue

44、[20]; //存放等待訪問的節(jié)點(diǎn)隊(duì)列,每個(gè)元素都是指針型</p><p>　　int f=0,r=0,i; //f,r 分別是隊(duì)頭,隊(duì)尾指針</p><p><b>　　Tree p;</b></p><p>　　queue[0]=t;</p><p>　　while(f<=r) {</p>

45、<p>　　p=queue[f];</p><p><b>　　f++;</b></p><p>　　printf("%c",p->data); //訪問隊(duì)頭元素</p><p>　　for(i=0;i<m;i++) //剛被訪問的元素的所有子節(jié)點(diǎn)依次進(jìn)隊(duì)</p>

46、<p>　　if(p->child[i]) {</p><p><b>　　++r;</b></p><p>　　queue[r]=p->child[i];</p><p><b>　　}</b></p><p><b>　　}</b></p>

47、<p><b>　　}</b></p><p>　　void main() {</p><p>　　system("color 1F"); //設(shè)置控制臺的背景色為藍(lán)色 </p><p>　　printf("\t\t**********************************\n"

48、);</p><p>　　printf("\t\t 第五組實(shí)驗(yàn)內(nèi)容：樹的應(yīng)用 \n");</p><p>　　printf("\t\t 組員：趙攀攀，張姣姣，聶永勝 \n");</p><p>　　printf("\t\t*******************

49、***************\n");</p><p><b>　　Tree T;</b></p><p><b>　　Tree T1;</b></p><p><b>　　BiTree p;</b></p><p>　　printf("=====輸入要?jiǎng)?chuàng)

50、建的樹=====:\n");</p><p>　　createtree(T);//創(chuàng)建 一棵樹</p><p>　　printf("\n樹的先序遞歸遍歷:");</p><p>　　preorder(T);</p><p>　　printf("\n樹的后序遞歸遍歷:");</p>

51、<p>　　postorder(T);</p><p>　　printf("\n樹的層序非遞歸遍歷:");</p><p><b>　　level(T);</b></p><p>　　printf("\n");</p><p>　　printf("\n====

52、=樹轉(zhuǎn)換為二叉樹=====\n");</p><p>　　p=TreetoBiTree(T);</p><p>　　printf("\n二叉樹先序非遞歸遍歷(樹的先序非遞歸):");</p><p>　　PreOrderPrint(p);</p><p>　　printf("\n二叉樹中序非遞歸遍歷(樹

53、的后序非遞歸):");</p><p>　　inorder1(p);</p><p>　　printf("\n");</p><p>　　printf("\n=====二叉樹轉(zhuǎn)換為樹=====\n");</p><p>　　T1=BiTreetoTree(p);</p><

54、p>　　printf("\n按先序遞歸遍歷此樹:");</p><p>　　preorder(T1);</p><p>　　printf("\n");</p><p>　　printf("\n按后序遞歸遍歷此樹:");</p><p>　　postorder(T1);</

55、p><p>　　printf("\n");</p><p>　　printf("\n按層次非遞歸遍歷此樹:");</p><p>　　level(T1);</p><p>　　printf("\n");</p><p><b>　　return ;<

56、;/b></p><p><b>　　}</b></p><p>　　六．測試分析（運(yùn)行結(jié)果）</p><p>　　比如說輸入以下內(nèi)容：</p><p>　　RAD###E####B###CFG###H###K#####</p><p><b>　　將會輸出下面內(nèi)容：</b&

57、gt;</p><p>　　樹的先序遞歸遍歷：RADEBCFGHK</p><p>　　樹的后序遞歸遍歷：DEABGHKFCR</p><p>　　樹的層次非遞歸遍歷：RABCDEFGHK</p><p>　　====樹轉(zhuǎn)換為二叉樹====</p><p>　　二叉樹先序非遞歸遍歷（樹的先序非遞歸）：RADEBCFGH

58、K</p><p>　　二叉樹中序非遞歸遍歷（樹的后序非遞歸）：DEABGHKFCR</p><p>　　====二叉樹轉(zhuǎn)換為樹====</p><p>　　按先序遞歸遍歷此樹：RADEBCFGHK</p><p>　　按按后序遞歸遍歷此樹：DEABGHKFCR</p><p>　　按按后序遞歸遍歷此樹: RABCDE

59、FGHK</p><p>　　七．總結(jié)（收獲及體會）</p><p><b>　　1、收獲及體會；</b></p><p>　　在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課的時(shí)候，對一些算法的設(shè)計(jì)和應(yīng)用并不是太理解，而且不知道怎么結(jié)合實(shí)際去實(shí)現(xiàn)這些算法，這次課程設(shè)計(jì)，我們通過各種途徑去掌握了解樹的應(yīng)用各個(gè)分塊的算法并加以實(shí)現(xiàn)，使我們對樹的各種操作得到了很好的掌握，剛開

60、始時(shí)一直在選用樹的存儲結(jié)構(gòu)上產(chǎn)生了意見分歧，一直糾結(jié)徘徊在是用孩子兄弟法還是孩子法來創(chuàng)建，最后考慮到后面的遍歷操作，我們統(tǒng)一了意見，決定采用孩子法。在編程過程中我們遇到了很多問題，最終都是通過資料的查詢及小組成員的討論攻克了一個(gè)又一個(gè)的難題，在此期間我們充分認(rèn)識到了團(tuán)隊(duì)合作的重要性，這對于以后我們的工作起到了一個(gè)很好的磨礪機(jī)會。這次的實(shí)習(xí)讓我們收獲到的不僅僅是知識的積累與鞏固，更重要的是對團(tuán)隊(duì)合作的認(rèn)識。</p><

61、p>　　2、在此部分最后部分注明每位同學(xué)所做的具體工作。</p><p>　　對于此次課程設(shè)計(jì)，我們小組做了明確的分工，在程序的9個(gè)模塊中，聶永勝同學(xué)主要負(fù)責(zé)樹的創(chuàng)建，樹轉(zhuǎn)換為二叉樹及二叉樹轉(zhuǎn)換為樹三個(gè)模塊，張姣姣同學(xué)負(fù)責(zé)樹的先序遞歸遍歷，樹的后序遞歸遍歷以及主程序?qū)Ω鱾€(gè)模塊的融合三個(gè)模塊，趙攀攀同學(xué)負(fù)責(zé)樹的先序，后序，層次的非遞歸遍歷三個(gè)模塊，在每個(gè)人將其工作任務(wù)完成后再將自己的編程思想講授給另外兩個(gè)同學(xué)