二叉樹課程設(shè)計(jì)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：22 大小：155.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩21頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　目錄　　1 問題描述1　　2 需求分析1　　3 概要設(shè)計(jì)1　　3．1模塊劃分………………

2、……………………………………….1　　4 詳細(xì)設(shè)計(jì)………6　　4．1 主要模塊流程圖………………………………………………………………7　　4．2 數(shù)據(jù)類型的定義………………………………………………8　　4．3 主要模塊的算法描述…………………………………………8<

3、/p>　　5 測(cè)試分析14　　6 課程設(shè)計(jì)總結(jié)17　　參考文獻(xiàn)18　　附錄（源程序清單）19　　1 問題描述</p&

4、gt;　　建立一棵二叉樹；再以廣義表表示法輸出這棵二叉樹；然后對(duì)該樹進(jìn)行先序、中序、后序遍歷及層次遍歷。　　要求：　　（1）采用二叉鏈表存儲(chǔ)二叉樹；　?。?）先序、中序、后序遍歷設(shè)計(jì)非遞歸算法。

5、　　2 需求分析　　二叉樹一種數(shù)據(jù)結(jié)構(gòu)，用于保存和處理樹狀的數(shù)據(jù)，比如家譜。他的應(yīng)用極為廣泛，因?yàn)楦鶕?jù)數(shù)據(jù)結(jié)構(gòu)的理論，任何復(fù)雜的樹夠可以轉(zhuǎn)換為二叉中并進(jìn)行處理，二叉樹在排序、查找、大規(guī)模數(shù)據(jù)索引方面有很多很多應(yīng)用。而且二叉樹排序是簡(jiǎn)單算法排序中速度最快的。　　在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的節(jié)點(diǎn)，或者對(duì)樹中全部節(jié)

6、點(diǎn)逐一進(jìn)行某種處理。這就提出了遍歷二叉樹。根據(jù)遍歷的方向的選擇，就有了前序遍歷，中序遍歷和后序遍歷以及層次遍歷二叉樹。因此掌握二叉樹的各種遍歷二叉樹算法非常重要，而且高效的遍歷算法能夠節(jié)省很多成本。　　3 概要設(shè)計(jì)　　3．1模塊劃分　　本

7、程序包括七個(gè)模塊：　?。?）主程序模塊　　void main()　　{　　初始化；　　以廣義表表示法輸出；</

8、p>　　建立二叉樹；　　非遞歸先序遍歷二叉樹并輸出；　　非遞歸中序遍歷二叉樹并輸出；　　非遞歸后序遍歷二叉樹并輸出；　　層次遍歷二叉樹并輸出；

9、}　?。?）以廣義表表示法輸出——實(shí)現(xiàn)對(duì)二叉樹的輸出　　（3）二叉樹建立模塊——建立一個(gè)二叉樹并　　對(duì)二叉樹進(jìn)行初始化　?。?）非遞歸先序遍歷模塊——實(shí)現(xiàn)對(duì)二叉樹的遞歸先序遍歷并輸出<

10、p>　?。?）非遞歸中序遍歷模塊——實(shí)現(xiàn)對(duì)二叉樹的遞歸中序遍歷并輸出　?。?）非遞歸后序遍歷模塊——實(shí)現(xiàn)對(duì)二叉樹的遞歸后序遍歷并輸出　　（7）層次遍歷模塊——實(shí)現(xiàn)對(duì)二叉樹的層次遍歷并輸出　　4 詳細(xì)設(shè)計(jì)　　4．1主要模塊流程圖&

11、lt;/p>　　主流程圖　　建立一棵二叉樹　　以廣義表表示法輸出一棵二叉樹　　非遞歸先序遍歷　　非遞歸中序遍歷&

12、lt;/b>　　非遞歸后序遍歷　　層次遍歷　　4．2數(shù)據(jù)類型的定義　?。?）二叉樹的二叉鏈表存儲(chǔ)類型　　typedef struct BiTNode

13、　　{　　char data;　　struct BiTNode *lchild,*rchild;　　} BiTNode,*BiTree;　?。?）棧類型的定義</b&g

14、t;　　typedef struct SqStack/*定義一個(gè)順序棧*/　　{　　BiTNode *base;　　BiTNode *top;　　int stacksize;

15、;　　} 　　SqStack;　　void InitStack(SqStack *S)/*棧的初始化*/　　{　　S->base=

16、(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));　　S->top=S->base;　　S->stacksize=STACK_INIT_SIZE;　　}　　void

17、Push(SqStack *S,BiTNode e)/*入棧算法*/　　{　　if(S->top-S->base>=S->stacksize)　　{　　S->base

18、=(BiTNode*)realloc(S->base,　　(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));　　S->top=S->base+S->stacksize;　　S->stacksize+=STACKINCREMENT;&l

19、t;/p>　　}　　*(S->top)=e;　　S->top++;　　}　　BiTNode Pop(SqStack *

20、S)/*出棧算法*/　　{　　S->top --;　　return *S->top;　　}　　int StackEmpty(SqStack *

21、S)/*判棧空*/　　{　　if(S->top == S->base )　　return 1;　　else

22、;　　return 0;　　}　　4．3主要模塊的算法描述　?。?）主函數(shù)　　void main()

23、;　　{　　BiTree Ta;int a=1;　　printf("請(qǐng)創(chuàng)建樹\n");　　Ta=CreateBiTree();　　printf("廣義表表示法輸出二叉樹\n");<p

24、>　　printfBTree(Ta);　　printf("\n");　　printf(" 請(qǐng)選擇：\n");　　printf(" （1）先序遍歷\n");　　printf(&q

25、uot; （2）中序遍歷\n");　　printf(" （3）后序遍歷\n");　　printf(" （4）層次遍歷\n");　　printf(" （0）結(jié)束程序\n");

26、;　　while(a)　　{　　scanf("%d",&a);　　if(a==1)　　{&

27、lt;/b>　?。?）建立二叉樹　　BiTree CreateBiTree()/*以二叉鏈表的存儲(chǔ)方式建立一棵二叉樹*/　　{　　char p;BiTree T;&l

28、t;p>　　scanf("%c",&p);　　if(p=='#')　　T=NULL;　　else　　{<

29、;/p>　　T=(BiTNode *)malloc(sizeof(BiTNode));　　T->data=p;　　T->lchild=CreateBiTree();　　T->rchild=CreateBiTree();<

30、b>　　}　　return (T);　　}　?。?）用廣義表表示法輸出二叉樹　　void printfbitree(t)/*用廣義表表示法輸出二叉樹*/<b&g

31、t;　　{　　if(t!=NULL)　　{　　printf("%c",t->data);　　if(t->lchild!=NULL||t->rchild!=NULL)</p

32、>　　{　　printf("(");　　printfbitree(t->lchild);　　if(t->rchild!=NULL)　　printf(","

33、);　　printfbirree(t->rchild);　　printf(")");　　}　　}　　}<

34、/b>　?。?）非遞歸先序遍歷二叉樹　　void PreOrder(BiTree T)/*非遞歸先序遍歷二叉樹*/　　{　　SqStack S;　　BiTree p=T;</p&g

35、t;　　InitStack(&S);　　if(p)　　Push(&S,*p);　　while(!StackEmpty(&S))　　{

36、;　　p=(BiTNode *)malloc(sizeof(BiTNode));　　*p=Pop(&S);　　printf("%c",p->data);　　if(p->rchild)　　Push(&S,

37、*p->rchild);　　if(p->lchild)　　Push(&S,*p->lchild);　　}　　}　?。?）非遞歸中

38、序遍歷二叉樹　　void InOrder(BiTree T)/* 非遞歸中序遍歷二叉樹*/　　{　　SqStack S;　　BiTree p=T;　　InitStack(&S);<

39、;/p>　　while(p||!StackEmpty(&S))　　{　　if(p)　　{　　Push(&S,*p)

40、;　　p=p->lchild;　　}　　else　　{　　p=(BiTNode *)malloc(sizeof

41、(BiTNode));　　*p=Pop(&S);　　printf("%c",p->data);　　p=p->rchild;　　}　　}

42、　　}　?。?）非遞歸后序遍歷二叉樹　　void PostOrder(BiTree T)/ *非遞歸后序遍歷二叉樹*/　　SqStack S;　　BiTNode p, *l

43、, *r;　　InitStack(&S);　　Push(&S, *T);　　while(!StackEmpty(&S))　　{　　p = Pop(&S);<

44、;/p>　　l = p.lchild;　　r = p.rchild;　　if (l == NULL && r == NULL)　　{　　printf("%c", p.da

45、ta);　　} 　　else 　　{　　p.lchild = NULL;　　p.rchild = NULL;<

46、/p>　　Push(&S, p);　　if (r != NULL) Push(&S, *r);　　if (l != NULL) Push(&S, *l);　　}

47、}　　}　　（7）層次遍歷　　void LevelOrderTraverse(BiTree T) /*層序遍歷*/　　{ </p&g

48、t;　　BiTree Q[STACK_INIT_SIZE]; 　　int front=0,rear=0; 　　BiTree p; 　　if(T)　　{ //根結(jié)點(diǎn)入隊(duì)

49、　Q[rear]=T; 　　rear=(rear+1)%STACK_INIT_SIZE; 　　} 　　while(front!=rear)　　{ 　　p=

50、Q[front]; //隊(duì)頭元素出隊(duì) 　　front=(front+1)%STACK_INIT_SIZE; 　　printf("%c",p->data); 　　if(p->lchild)　　{ //左孩子不為空，入隊(duì)

51、　　Q[rear]=p->lchild; 　　rear=(rear+1)%STACK_INIT_SIZE; 　　} 　　if(p->rchild){ //右孩子不為空，入隊(duì) 　　Q[rear]=p-&g

52、t;rchild; 　　rear=(rear+1)%STACK_INIT_SIZE; 　　} 　　} 　　} <

53、;b>　　5 測(cè)試分析　　6 課程設(shè)計(jì)總結(jié)　　通過這次課程設(shè)計(jì)使我充分的理解了從建立二叉樹到輸出二叉樹再遍歷二叉樹的基本原理與算法，尤其是深刻的學(xué)習(xí)了二叉樹遍歷的非遞歸實(shí)現(xiàn)的算法。之前由于二叉樹的非遞歸實(shí)現(xiàn)不是考試的要點(diǎn)，自己都沒怎么去學(xué)那方面的知識(shí)，對(duì)于算法更是沒明白。但通過這次課程設(shè)計(jì)后

54、，我對(duì)二叉樹的非遞歸實(shí)現(xiàn)的算法基本上了解了。雖然這次課程設(shè)計(jì)由于我們的程序問題耽誤了很多時(shí)間，但我們覺得非常值得，因?yàn)樵诤馁M(fèi)時(shí)間的同時(shí)，我們自己對(duì)程序的算法也理解的更加深刻了。這次的程序設(shè)計(jì)雖然并不是很完備，但是對(duì)于我來說，已經(jīng)覺得是很大的收獲了。我想以后再做課程設(shè)計(jì)的話，我的思路一定會(huì)更加清晰，也會(huì)做的更加順利了。　　在此我非常要感謝的是我的指導(dǎo)老師成婭輝老師，感謝老師對(duì)我們程序的細(xì)心認(rèn)真的輔

55、導(dǎo)，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程也越來越了解，越來越感興趣了。同時(shí)我還要感謝所有幫助過我的人以及我的隊(duì)友們，衷心的謝謝他們。　　參考文獻(xiàn)　　[1] 黃同成，黃俊民，董建寅．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國(guó)電力出版社，2008　　[2] 董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解[M]

56、．北京：中國(guó)電力出版社，2008　　[3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社，2002　　[4] 劉振鵬，張曉莉，郝杰．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國(guó)鐵道出版社，2003　　附錄（源程序清單）　　#in

57、clude <stdio.h>　　#include <stdlib.h>　　#include <malloc.h>　　#define STACK_INIT_SIZE 100　　#define STACKINCREMENT 10<

58、;/p>　　typedef struct BiTNode/*二叉樹的二叉鏈表存儲(chǔ)類型*/　　{　　char data;　　struct BiTNode *lchild,*rchild;　　} BiTNode

59、,*BiTree;　　typedef struct SqStack/*定義一個(gè)順序棧*/　　{　　BiTNode *base;　　BiTNode *top;　　int stacksize;&l

60、t;/p>　　} 　　SqStack;　　void InitStack(SqStack *S)/*棧的初始化*/　　{　　S-&g

61、t;base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));　　S->top=S->base;　　S->stacksize=STACK_INIT_SIZE;　　}

62、　　void printfBTree(BiTree bt)/*用廣義表表示法輸出二叉樹*/　　{　　if(bt!=NULL)　　{　　printf("%c",bt->da

63、ta);　　if(bt->lchild!=NULL||bt->rchild!=NULL)　　{　　printf("(");　　printfBTree(bt->lchild);

64、　　if(bt->rchild!=NULL)　　printf(",");　　printfBTree(bt->rchild);　　printf(")");　　}&l

65、t;/p>　　}　　}　　void Push(SqStack *S,BiTNode e)/*入棧算法*/　　{　　if(S->

66、;top-S->base>=S->stacksize)　　{　　S->base=(BiTNode*)realloc(S->base,　　(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));</

67、p>　　S->top=S->base+S->stacksize;　　S->stacksize+=STACKINCREMENT;　　}　　*(S->top)=e;

68、;　　S->top++;　　}　　BiTNode Pop(SqStack *S)/*出棧算法*/　　{　　S->top --;<p&g

69、t;　　return *S->top;　　}　　int StackEmpty(SqStack *S)/*判棧空*/　　{　　if(S->top == S->base )</

70、p>　　return 1;　　else　　return 0;　　}　　BiTree Crea

71、teBiTree()/*以二叉鏈表的存儲(chǔ)方式建立一棵二叉樹*/　　{　　char p;BiTree T;　　scanf("%c",&p);　　if(p=='#')&l

72、t;p>　　T=NULL;　　else　　{　　T=(BiTNode *)malloc(sizeof(BiTNode));　　T->data=p;

73、　　T->lchild=CreateBiTree();　　T->rchild=CreateBiTree();　　}　　return (T);　　}</b&g

74、t;　　void PreOrder(BiTree T)/*非遞歸先序遍歷二叉樹*/　　{　　SqStack S;　　BiTree p=T;　　InitStack(&S);</p&

75、gt;　　if(p)　　Push(&S,*p);　　while(!StackEmpty(&S))　　{　　p=(BiTNode *)malloc(sizeof

76、(BiTNode));　　*p=Pop(&S);　　printf("%c",p->data);　　if(p->rchild)　　Push(&S,*p->rchild);　　if

77、(p->lchild)　　Push(&S,*p->lchild);　　}　　}　　void InOrder(BiTree T)/* 非遞歸中序遍歷二叉樹*/

78、　　{　　SqStack S;　　BiTree p=T;　　InitStack(&S);　　while(p||!StackEmpty(&S))<b&

79、gt;　　{　　if(p)　　{　　Push(&S,*p);　　p=p->lchild;　　}<

80、/b>　　else　　{　　p=(BiTNode *)malloc(sizeof(BiTNode));　　*p=Pop(&S);　　prin

81、tf("%c",p->data);　　p=p->rchild;　　}　　}　　}

82、void PostOrder(BiTree T)/ *非遞歸后序遍歷二叉樹*/　　SqStack S;　　BiTNode p, *l, *r;　　InitStack(&S);　　Push(&S, *T);　　whi

83、le(!StackEmpty(&S))　　{　　p = Pop(&S);　　l = p.lchild;　　r = p.rchild;　　if (l == NULL &&

84、amp; r == NULL)　　{　　printf("%c", p.data);　　} 　　else <p

85、>　　{　　p.lchild = NULL;　　p.rchild = NULL;　　Push(&S, p);　　if (r != NULL) Push(&S, *r);

86、　if (l != NULL) Push(&S, *l);　　}　　}　　}　　void LevelOrderTraverse(BiTree T) /

87、*層序遍歷*/　　{ 　　BiTree Q[STACK_INIT_SIZE]; 　　int front=0,rear=0; 　　BiTree p; 　　if(T)</b

88、>　　{ //根結(jié)點(diǎn)入隊(duì) 　　Q[rear]=T; 　　rear=(rear+1)%STACK_INIT_SIZE; 　　} 　　while(front!=rear)

89、　　{ 　　p=Q[front]; //隊(duì)頭元素出隊(duì) 　　front= (front+1)%STACK_INIT_SIZE; 　　if(p->lchild)　　printf("%c",p

90、->data); 　　{ //左孩子不為空，入隊(duì) 　　Q[rear]=p->lchild; 　　rear=(rear+1)%STACK_INIT_SIZE; 　　}　　if(p-&

91、gt;rchild){ //右孩子不為空，入隊(duì) 　　Q[rear]=p->rchild; 　　rear=(rear+1)%STACK_INIT_SIZE; 　　} 　　}

92、;　　} 　　void main()　　{　　BiTree Ta;int a=1;　　printf("請(qǐng)創(chuàng)建樹\n");<p

93、>　　Ta=CreateBiTree();　　printf("廣義表表示法輸出二叉樹\n");　　printfBTree(Ta);　　printf("\n");　　printf(" 請(qǐng)選擇：\n&qu

94、ot;);　　printf(" （1）先序遍歷\n");　　printf(" （2）中序遍歷\n");　　printf(" （3）后序遍歷\n");　　printf(&q

95、uot; （4）層次遍歷\n");　　printf(" （0）結(jié)束程序\n");　　while(a)　　{　　scanf("%d

96、",&a);　　if(a==1)　　{　　printf("先序遍歷：\n");　　printf("\n");<

97、;p>　　PreOrder(Ta);　　printf("\n");　　}　　else if(a==2)　　{　　printf(&

98、quot;中序遍歷:\n");　　InOrder(Ta);　　printf("\n");　　}　　else if(a==3)　　{</b&

99、gt;　　printf("后序遍歷:\n");　　PostOrder(Ta);　　printf("\n");　　}　　else if(a==4)<

100、/p>　　{ 　　printf("層次遍歷:\n");　　LevelOrderTraverse(Ta);　　printf("\n");　　}&l

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

二叉樹課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

二叉樹課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載