课程设计—二叉树的先序中序后序遍历下载_Word模板_7

二叉树的各种遍历方法的实现一、设计目的 1．掌握二叉树的建立方法。 2．掌握二叉树的基本操作。 3．掌握二叉树的先序、中序、后序遍历算法。二、设计内容和要求建立一棵二叉树，完成： 1．对它进行先序、中序、后序遍历; 2．给出遍历过程中栈的变化情况；实习代码： #include #include using namespace std; #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef int Status; typedef char TElemType; TElemType Nil='^'; char pre[100]; char in[100]; char post[100]; typedef struct BiTNode { TElemType data; BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef BiTree SElemType; struct SqStack { SElemType *base; SElemType *top; int tag[100]; int count; int stacksize; }; Status InitStack(SqStack &S) { if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)))) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status GetTop(SqStack S,SElemType &e) { if(S.top>S.base) { e=*(S.top-1); return OK; } else return ERROR; } Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *(S.top)++=e; S.count++; return OK; } Status Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return ERROR; e=*--S.top; --S.count; return OK; } Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else return FALSE; } Status InitBiTree(BiTree &T) { T=NULL; return OK; } void CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if(ch==Nil) T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } Status PreOrderTraverse(BiTree T) { int i=0; SqStack S; BiTree p=T; InitStack(S); while(p||!StackEmpty(S)) { while(p) { Push(S,p); pre[i]=p->data; i++; cout<data<<"进栈"<lchild; } if(!StackEmpty(S)) //访问结点,向右一步 { Pop(S,p); if(p->data==NULL) return ERROR; cout<data<<"出栈"<rchild; } } return OK; } Status InOrderTraverse(BiTree T) { int i=0; SqStack S; BiTree p=T; InitStack(S); while(p||!StackEmpty(S)) { while(p) { Push(S,p); cout<data<<"进栈"<lchild; } if(!StackEmpty(S)) //访问结点,向右一步 { Pop(S,p); if(p->data==NULL) return ERROR; cout<data<<"出栈"<data; i++; p=p->rchild; } } return OK; } Status PostOrderTraverse(BiTree T) { int i=0; SqStack S; S.count=0; BiTree p=T; InitStack(S); while(p||!StackEmpty(S)) { while(p) { Push(S,p); cout<data<<"进栈"<lchild; } if(S.tag[S.count]==0) { GetTop(S,p); if(p->data==NULL) return ERROR; S.tag[S.count]=1; p=p->rchild; } else { while(S.tag[S.count]==1) { GetTop(S,p); if(p->data==NULL) return ERROR; Pop(S,p); cout<data<<"出栈"<data; i++; } p=NULL; } } return OK; } void main() { int i,flag=0; char ch; BiTree T; InitBiTree(T); printf("请先序输入二叉树：\n"); CreateBiTree(T); do { cout<<"请选择遍历方法："<>ch; switch(ch) { case '1': printf("\n先序非递归遍历二叉树栈的变化情况:\n"); PreOrderTraverse(T); cout<<"先序遍历二叉树结果："; for(i=0;i<20;i++) { cout<

                    本文档为【课程设计—二叉树的先序中序后序遍历】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

课程设计—二叉树的先序中序后序遍历

你可能还喜欢