数据结构课程设计(先中后序遍历).doc

安徽工程大学数 据 结 构课 程 设 计 说 明 书学生姓名:刘超学 号：3120702109学 院:计算机与信息学院专 业:信息与计算科学题 目:二叉树的创建和遍历指导教师潘海玉2014年8月25日目录1. 需求分析-12. 概要设计-13. 详细设计-34. 调试分析-95. 课程总结-106. 附录 -121. 需求分析问题描述：根据运行时输入的先序序列，创建一棵二叉树，分别对其 进行先序、中序、后序、层序遍历，并显示遍历结果。void CreateBTree(BTree &T) /按先序次序输入，构造二叉树void PreOrder(BTree T) /递归先序遍历void InOrder(BTree T) /递归中序遍历void PostOrder(BTree T) /递归后序遍历void LevelOrder(BTree T) /层序遍历void NRPreOrder(BTree bt) /非递归先序遍历void NRInOrder(BTree bt) /非递归中序遍历void NRPostOrder(BTree bt) /非递归后序遍历void main() /二叉树的建立与遍历实现2.概要设计此次课程设计遍历算法的框架图层序遍历遍历算法递归遍历非递归遍历先序遍历中序遍历后序遍历先序遍历中序遍历后序遍历 此次课程设计所用的三组二叉树 AACBCB DFEEFDGHABFGCDEH本设计所使用的存储结构：typedef char ElemType;/定义二叉树结点值的类型为字符型typedef struct bnode/二叉链表结构定义ElemType data;struct bnode *lchild,*rchild;Bnode,* BTree;typedef struct BTree ptr; int tag;stacknode;3.详细设计void CreateBTree(BTree &T)/按先序次序输入，构造二叉链表表示的二叉树T，#表示空树char ch;ch=getchar(); if(ch=#) T=NULL;/读入#时，将相应节点指针置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf(创建失败!);/生成结点空间T-data=ch;CreateBTree(T-lchild);/构造二叉树的左子树CreateBTree(T-rchild);/构造二叉树的右子树void PreOrder(BTree T)/递归先序遍历if(T)printf(%c ,T-data);PreOrder(T-lchild);PreOrder(T-rchild);void InOrder(BTree T)/递归中序遍历if(T)InOrder(T-lchild);printf(%c ,T-data);InOrder(T-rchild);void PostOrder(BTree T)/递归后序遍历if(T)PostOrder(T-lchild);PostOrder(T-rchild);printf(%c ,T-data);void LevelOrder(BTree T)/层序遍历BTree QMAX;int front=0,rear=0;BTree p;if(T) /根结点入队Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /队头元素出队front=(front+1)%MAX; printf(%c ,p-data);if(p-lchild) /左孩子不为空，入队Qrear=p-lchild;rear=(rear+1)%MAX;if(p-rchild) /右孩子不为空，入队Qrear=p-rchild;rear=(rear+1)%MAX;void NRPreOrder(BTree bt)/非递归先序遍历BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top0) while(p!=NULL) printf(%c,p-data);stacktop=p;/预留p指针在数组中top+;p=p-lchild; if (top0) top-; p=stacktop; p=p-rchild;/*左子树为空，进右子树*/void NRInOrder(BTree bt)/非递归中序遍历BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top0)while(p!=NULL) stacktop=p; /预留p指针在数组中top+;p=p-lchild; if (top0)top-; p=stacktop;printf(%c,p-data); p=p-rchild;/*左子树为空，进右子树*/void NRPostOrder(BTree bt)/非递归后序遍历 stacknode sMAX,x; BTree p=bt;int top;if(bt!=NULL) top=0;p=bt;dowhile (p!=NULL) /遍历左子树stop.ptr = p; stop.tag = 1; /标记为左子树top+;p=p-lchild;while (top0 & stop-1.tag=2)x = s-top;p = x.ptr;printf(%c,p-data); /tag为R，表示右子树访问完毕，故访问根结点 if (top0)stop-1.tag =2; /遍历右子树p=stop-1.ptr-rchild; while (top0);4.调试分析 一组测试树 运行时界面 5.课程总结这个程序的代码较为简单，可以实现了二叉树的三种递归遍历算法和三种非递归遍历算法还有层序遍历算法，想要改进的话可以在选择功能上下手，建立的时候提示更人性化，对输入的数据进行有效性验证，也可以改进为对遍历算法进行选择等等。二叉树这个数据结构几乎在每一本的数据结构的书都作为重点内容讲述，足见其在算法和程序设计界的重要地位。但是，到目前为止，自己还没有真正体验到它的威力，可能是学习的还不够深刻。像二叉树遍历的算法，用递归的算法只是简单的几行代码，然后就可以实现输出遍历次序。对于非递归的思想，要用到栈这个数据结构，但是对于二叉树遍历问题来说非递归要较递归复杂。程序一开始总是出现语法错误，改了很多次也上网查了相关资料，才最后改为现在可以成功运行的程序。在这个过程中，我体会到开发工程师的感觉了，就是要用挑剔的眼光想问题并且不断地改进自己的程序。通过这次课程设计逐渐提高了自己的程序设计和调试能力，通过上机实习，严整自己设计算法的正确性，学会了有效利用基本调试方法，查找出代码中的错误并且修改。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。6.附录#include #include #include#define MAX 10 /结点个数不超过10个typedef char ElemType;/定义二叉树结点值的类型为字符型typedef struct bnode/二叉链表结构定义ElemType data;struct bnode *lchild,*rchild;Bnode,* BTree;void CreateBTree(BTree &T)/按先序次序输入，构造二叉链表表示的二叉树T，#表示空树char ch;ch=getchar(); if(ch=#) T=NULL;/读入#时，将相应节点指针置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf(创建失败!);/生成结点空间T-data=ch;CreateBTree(T-lchild);/构造二叉树的左子树CreateBTree(T-rchild);/构造二叉树的右子树void PreOrder(BTree T)/递归先序遍历if(T)printf(%c ,T-data);PreOrder(T-lchild);PreOrder(T-rchild);void InOrder(BTree T)/递归中序遍历if(T)InOrder(T-lchild);printf(%c ,T-data);InOrder(T-rchild);void PostOrder(BTree T)/递归后序遍历if(T)PostOrder(T-lchild);PostOrder(T-rchild);printf(%c ,T-data);void LevelOrder(BTree T)/层序遍历BTree QMAX;int front=0,rear=0;BTree p;if(T) /根结点入队Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /队头元素出队front=(front+1)%MAX; printf(%c ,p-data);if(p-lchild) /左孩子不为空，入队Qrear=p-lchild;rear=(rear+1)%MAX;if(p-rchild) /右孩子不为空，入队Qrear=p-rchild;rear=(rear+1)%MAX;void NRPreOrder(BTree bt)/非递归先序遍历BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top0) while(p!=NULL) printf(%c,p-data);stacktop=p;/预留p指针在数组中top+;p=p-lchild; if (top0) top-; p=stacktop; p=p-rchild;/*左子树为空，进右子树*/void NRInOrder(BTree bt)/非递归中序遍历BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top0)while(p!=NULL) stacktop=p; /预留p指针在数组中top+;p=p-lchild; if (top0)top-; p=stacktop;printf(%c,p-data); p=p-rchild;/*左子树为空，进右子树*/typedef struct BTree ptr; int tag;stacknode;void NRPostOrder(BTree bt)/非递归后序遍历 stacknode sMAX,x; BTree p=bt;int top;if(bt!=NULL) top=0;p=bt;dowhile (p!=NULL) /遍历左子树stop.ptr = p; stop.tag = 1; /标记为左子树top+;p=p-lchild;while (top0 & stop-1.tag=2)x = s-top;p = x.ptr;printf(%c,p-data); /tag为R，表示右子树访问完毕，故访问根结点 if (top0)stop-1.tag =2; /遍历右子树p=stop-1.ptr-rchild; while (top0);void main()/主函数BTree T;T=NULL;int select;while(1)printf(nnn请选择要执行的操作:n);printf(1.创建二叉树n);printf(2.二叉树的递归遍历算法（前、中、后）n);printf(3.二叉树的层次遍历算法n);printf(4.二叉树的非递归遍历算法（前、中、后）n); printf(0.退出n);printf(输入：); cinselect;switch(select)case 0:return;case 1:printf(n请按先序次序输入各结点的值，以#表示空树(输入时可连续输入):n);CreateBTree(T);break;case 2:if(!T) printf(n未建立树，请先建树！);elseprintf(nn递归先序遍历:n);PreOrder(T);printf(n递归中序遍历:n);InOrder(T);printf(n递归后序遍历:n);Po