二叉樹課程設計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：22 大?。?55.50KB 人氣指數(shù)：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、　　目錄　　1 問題描述1　　2 需求分析1　　3 概要設計1　　3．1模塊劃分………………

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

3、/p>　　5 測試分析14　　6 課程設計總結17　　參考文獻18　　附錄（源程序清單）19　　1 問題描述</p&

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

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

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

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

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

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

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

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

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

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

14、t;　　typedef struct SqStack/*定義一個順序棧*/　　{　　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主要模塊的算法描述　　（1）主函數(shù)　　void main()

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

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

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

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

27、lt;/b>　?。?）建立二叉樹　　BiTree CreateBiTree()/*以二叉鏈表的存儲方式建立一棵二叉樹*/　　{　　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);　　}　　}　　（5）非遞歸中

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、}　　}　?。?）層次遍歷　　void LevelOrderTraverse(BiTree T) /*層序遍歷*/　　{ </p&g

48、t;　　BiTree Q[STACK_INIT_SIZE]; 　　int front=0,rear=0; 　　BiTree p; 　　if(T)　　{ //根結點入隊

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

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

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

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

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

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

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

56、．北京：中國電力出版社，2008　　[3] 嚴蔚敏，吳偉民. 數(shù)據(jù)結構（C語言版）[M]. 北京：清華大學出版社，2002　　[4] 劉振鵬，張曉莉，郝杰．數(shù)據(jù)結構[M]．北京：中國鐵道出版社，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/*二叉樹的二叉鏈表存儲類型*/　　{　　char data;　　struct BiTNode *lchild,*rchild;　　} BiTNode

59、,*BiTree;　　typedef struct SqStack/*定義一個順序棧*/　　{　　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()/*以二叉鏈表的存儲方式建立一棵二叉樹*/　　{　　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、>　　{ //根結點入隊 　　Q[rear]=T; 　　rear=(rear+1)%STACK_INIT_SIZE; 　　} 　　while(front!=rear)

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

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

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

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

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

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

95、uot; （4）層次遍歷\n");　　printf(" （0）結束程序\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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

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

二叉樹課程設計

文檔簡介

溫馨提示

最新文檔

評論

二叉樹課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載