二叉樹的中序的遞歸、非遞歸遍歷算法

1、信息工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目 二叉樹的中序的遞歸、非遞歸遍歷算法 專 業(yè) 班 級 小 組 成 員 一 題目：二叉樹的中序的遞歸、非遞歸遍歷算法二 小組任務(wù)分工 馬凱：編寫二叉樹中序遞歸遍歷、非遞歸遍歷 崔妍：編寫二叉樹層序遍歷、打印二叉樹三 設(shè)計目標(biāo)幫助學(xué)生熟練掌握二叉樹的遍歷；四 問題描述二叉樹的中序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應(yīng)包含建樹為了的實現(xiàn)。五 概要設(shè)計實現(xiàn)上述程序功能，需要定義一個結(jié)構(gòu)體typedef struct tree /定義數(shù)據(jù)結(jié)構(gòu)體ElemType data;/數(shù)據(jù)信息struct tree *lchild;/左孩子struct tr

2、ee *rchild;/右孩子TreeNode,*Tree;typedef struct /層序遍歷的隊列結(jié)構(gòu)體定義QElemType baseMAXQSIZEZ;int front;/定義隊頭int rear;/定義隊尾Sqstack1;typedef struct stack /非遞歸遍歷棧Tree *base;/定義棧底Tree *top;/定義棧頂int stackszie; /指示棧內(nèi)剩余空間Sqstack; 六 詳細設(shè)計（程序代碼及核心代碼流程圖）總體操作步驟：(1)以前序遍歷的方式輸入二叉樹；(2)打印出二叉樹的中序遞歸、非遞歸遍歷、層序遍歷；(3)完成操作 。#include&

3、lt;stdio.h>#include<stdlib.h>#define STACKINITSIZE 100#define STACKINCREASESIZE 20/層序遍歷部分#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;/*8typedef char ElemType;typedef struct tree /定義數(shù)據(jù)結(jié)構(gòu)體ElemType data;/數(shù)據(jù)信息struct tree *lchild;/左孩子struct tree

4、*rchild;/右孩子TreeNode,*Tree; /層序遍歷#define MAXQSIZEZ 100/宏定義最大長度typedef Tree QElemType;typedef struct /層序遍歷的隊列結(jié)構(gòu)體定義QElemType baseMAXQSIZEZ;int front;/定義隊頭int rear;/定義隊尾Sqstack1;typedef struct stack /利用結(jié)構(gòu)體定義棧Tree *base;/定義棧底Tree *top;/定義棧頂int stackszie; /指示棧內(nèi)剩余空間Sqstack; void CreateTree(Tree *root)/創(chuàng)建一

5、棵樹char s;/定義樹的根節(jié)點s=getchar();/描述樹中表示空樹時的情況if(s = '#')*root= NULL;else*root=(Tree)malloc(sizeof(TreeNode);/申請空間，用malloc函數(shù)動態(tài)分配空間if(!root)/判斷根節(jié)點是否為空，即，該樹是否為空printf("分配內(nèi)存失??！");(*root)->data=s; /將getcher得到的數(shù)據(jù)分配到樹中CreateTree(&(*root)->lchild); CreateTree(&(*root)->rchild

6、); /返回值/層序遍歷隊列定義void InitQueue(Sqstack1 *Q) /初始化前尾指針Q->front=Q->rear=0;/隊頭等于隊尾Status ErQueue(Sqstack1 *Q, QElemType e) /入隊if(Q->rear+1)%MAXQSIZEZ=Q->front)/判斷對是否滿return ERROR;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZEZ; return OK;Status DeQueue(Sqstack1 *Q,QElemType *e) /刪

7、除元素if(Q->front=Q->rear)/隊為空，不能刪除return ERROR;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZEZ; return OK;Status QueueEmpty(Sqstack1 Q) /判斷隊列是否為空if(Q.rear=Q.front)return TRUE;elsereturn FALSE;void Traverse(Tree T)/層序遍歷Sqstack1 Q;Tree p;p=T;InitQueue(&Q);/初始化if(p)ErQueue(&Q

8、,p);while (!QueueEmpty(Q)DeQueue(&Q,&p);/出隊printf("%c",p->data);if(p->lchild)ErQueue(&Q,p->lchild);if(p->rchild)ErQueue(&Q,p->rchild);printf("n");/*/使用遞歸完成中序遍歷void InOrder(Tree root )if(root)/如果根節(jié)點不為空，一句左根右的順序遍歷InOrder(root->lchild);printf("

9、%c",root->data);InOrder(root->rchild);/初始化棧void InStack(Sqstack *s)s->base=(Tree*)malloc(STACKINITSIZE*sizeof(TreeNode);/動態(tài)分配空間if(!s->base)printf("棧創(chuàng)建失敗！");s->top=s->base;s->stackszie=STACKINITSIZE;/棧中的剩余內(nèi)存/壓棧void Push(Sqstack *s,Tree root)if(*s).top-(*s).base)>

10、;=(*s).stackszie)/判斷棧是否滿？如果滿(*s).base =(Tree*)realloc(*s).base,(*s).stackszie+STACKINCREASESIZE)*sizeof(Tree);/擴容if(!(*s).base)printf("內(nèi)存分配失敗！");(*s).top=(*s).base+(*s).stackszie;(*s).stackszie+=STACKINCREASESIZE;*(s->top)= root; s->top+;/進行依次入棧操作/獲得棧頂元素void GetTop(Sqstack *s, Tree *

11、root)*root =*(*s).top-1);/彈出棧頂元素void Pop(Sqstack *s,Tree *root)if(*s).top = (*s).base) /=與=printf("棧已經(jīng)空了！");*root = *(-(*s).top);/判斷棧是否為空int StackEmpty(Sqstack *s)if(s->top= s->base) return 1;else return 0;/非遞歸中序遍歷void InOrderS(Tree root)Tree p=root;Sqstack s;InStack(&s);while (p

12、 |!StackEmpty(&s)if(p) Push(&s,p);p=p->lchild;else Pop(&s,&p); printf("%c",p->data);p=p->rchild;void PrintTree(Tree root,int nLayer)/樹狀打印二叉樹 int i;if(root = NULL)return;PrintTree(root->rchild ,nLayer+1);for(i=0;i<nLayer;i+)printf(" ");printf("%

13、cn",root->data);PrintTree(root->lchild ,nLayer+1);void main() int layer=0;Tree root=NULL;printf("先序遍歷輸入二叉樹,#代表空子樹:n");CreateTree( &root);/參數(shù)不懂printf("遞歸中序遍歷輸出:n"); InOrder(root);printf("n");printf("非遞歸中序遍歷輸出:n");InOrderS(root);printf("n&quo

14、t;);printf("層序遍歷二叉樹：n");Traverse(root);printf("打印二叉樹：n");PrintTree(root, layer);printf("n");七 測試分析測試內(nèi)容測試結(jié)果輸入二叉樹正確遞歸中序遍歷正確非遞歸中序遍歷正確層序遍歷正確打印二叉樹正確八課程設(shè)計總結(jié)此次課程設(shè)計中，題目為二叉樹的中序遍歷、層序遍歷，在完成這次設(shè)計過程中，遇到了好多問題，例如：不知道如何循環(huán)完成二叉樹的非遞歸遍歷，如何利用棧和隊列的特性，怎么將它們合理的進棧和出棧。 通過這次課程設(shè)計的設(shè)計，使我明白了自己在學(xué)習(xí)過程中的一

15、些漏洞，比如，棧和隊列中出入的一些細節(jié)的處理、結(jié)構(gòu)體指針的應(yīng)用、運行過程中內(nèi)存的分配等。#include<stdio.h>#include<stdlib.h>#define STACKINITSIZE 100#define STACKINCREASESIZE 20/層序遍歷部分#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;/*8typedef char ElemType;typedef struct tree /定義數(shù)據(jù)結(jié)構(gòu)體El

16、emType data;/數(shù)據(jù)信息struct tree *lchild;/左孩子struct tree *rchild;/右孩子TreeNode,*Tree;/重命名/層序遍歷#define MAXQSIZEZ 100/宏定義最大長度typedef Tree QElemType;typedef struct /層序遍歷的隊列結(jié)構(gòu)體定義QElemType baseMAXQSIZEZ;int front;/定義隊頭int rear;/定義隊尾Sqstack1;typedef struct stack /利用結(jié)構(gòu)體定義棧Tree *base;/定義棧底Tree *top;/定義棧頂int stac

17、kszie; /指示棧內(nèi)剩余空間Sqstack;/借助結(jié)構(gòu)體對棧進行重命名void CreateTree(Tree *root)/創(chuàng)建一棵樹char s;/定義樹的根節(jié)點s=getchar();/getchar和scanf的區(qū)別是什么 手動從鍵盤輸入字符/描述樹中表示空樹時的情況if(s = '#')*root= NULL;else*root=(Tree)malloc(sizeof(TreeNode);/申請空間，用malloc函數(shù)動態(tài)分配空間if(!root)/判斷根節(jié)點是否為空，即，該樹是否為空printf("分配內(nèi)存失??！");(*root)->

18、data=s; /將getcher得到的數(shù)據(jù)分配到樹中/？CreateTree(&(*root)->lchild);/？CreateTree(&(*root)->rchild);/？/返回值/層序遍歷隊列定義void InitQueue(Sqstack1 *Q) /初始化前尾指針Q->front=Q->rear=0;/隊頭等于隊尾Status ErQueue(Sqstack1 *Q, QElemType e) /入隊if(Q->rear+1)%MAXQSIZEZ=Q->front)/判斷對是否滿?return ERROR;Q->base

19、Q->rear=e;Q->rear=(Q->rear+1)%MAXQSIZEZ;/？return OK;Status DeQueue(Sqstack1 *Q,QElemType *e) /刪除元素if(Q->front=Q->rear)/隊為空，不能刪除return ERROR;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZEZ;/？return OK;Status QueueEmpty(Sqstack1 Q) /判斷隊列是否為空if(Q.rear=Q.front)return TRUE;e

20、lsereturn FALSE;void Traverse(Tree T)/層序遍歷Sqstack1 Q;Tree p;p=T;InitQueue(&Q);/初始化if(p)ErQueue(&Q,p);while (!QueueEmpty(Q)DeQueue(&Q,&p);/出隊printf("%c",p->data);if(p->lchild)ErQueue(&Q,p->lchild);if(p->rchild)ErQueue(&Q,p->rchild);printf("n"

21、);/*/使用遞歸完成中序遍歷void InOrder(Tree root )if(root)/如果根節(jié)點不為空，一句左根右的順序遍歷InOrder(root->lchild);printf("%c",root->data);InOrder(root->rchild);/初始化棧void InStack(Sqstack *s)s->base=(Tree*)malloc(STACKINITSIZE*sizeof(TreeNode);/動態(tài)分配空間if(!s->base)printf("棧創(chuàng)建失敗！");s->top=s-

22、>base;s->stackszie=STACKINITSIZE;/棧中的剩余內(nèi)存/壓棧void Push(Sqstack *s,Tree root)if(*s).top-(*s).base)>=(*s).stackszie)/判斷棧是否滿？如果滿(*s).base =(Tree*)realloc(*s).base,(*s).stackszie+STACKINCREASESIZE)*sizeof(Tree);/擴容if(!(*s).base)printf("內(nèi)存分配失??！");(*s).top=(*s).base+(*s).stackszie;(*s).s

23、tackszie+=STACKINCREASESIZE;*(s->top)= root; s->top+;/進行依次入棧操作/獲得棧頂元素void GetTop(Sqstack *s, Tree *root)/?*root =*(*s).top-1);/彈出棧頂元素void Pop(Sqstack *s,Tree *root)if(*s).top = (*s).base) /=與=printf("棧已經(jīng)空了！");*root = *(-(*s).top);/判斷棧是否為空int StackEmpty(Sqstack *s)if(s->top= s->base) /=寫為=return 1;else return 0;/非遞歸中序遍歷void InOrderS(Tree roo