《数据结构课程设计先中后序遍历.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计先中后序遍历.doc（25页珍藏版）》请在金锄头文库上搜索。
1、安徽工程大学数 据 结 构课 程 设 计 说 明 书学生姓名:刘超学 号：学 院:计算机与信息学院专 业:信息与计算科学题 目:二叉树的创建和遍历指导教师潘海玉2023年8月25日目录1. 需求分析-12. 概要设计-13. 具体设计-34. 调试分析-95. 课程总结-106. 附录 -121. 需求分析问题描述：根据运营时输入的先序序列，创建一棵二叉树，分别对其 进行先序、中序、后序、层序遍历，并显示遍历结果。void CreateBTree(BTree &T) /按先序顺序输入，构造二叉树void PreOrder(BTree T) /递归先序遍历void InOrder(BTree T
2、) /递归中序遍历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本设计所
3、使用的存储结构：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=
4、(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-rchi
5、ld);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) /左孩子不为空，
6、入队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-rchi
7、ld;/*左子树为空，进右子树*/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
8、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.课程总结这个程序的代码较为
9、简朴，可以实现了二叉树的三种递归遍历算法和三种非递归遍历算法尚有层序遍历算法，想要改善的话可以在选择功能上下手，建立的时候提醒更人性化，对输入的数据进行有效性验证，也可以改善为对遍历算法进行选择等等。二叉树这个数据结构几乎在每一本的数据结构的书都作为重点内容讲述，足见其在算法和程序设计界的重要地位。但是，到目前为止，自己还没有真正体验到它的威力，也许是学习的还不够深刻。像二叉树遍历的算法，用递归的算法只是简朴的几行代码，然后就可以实现输出遍历顺序。对于非递归的思想，要用到栈这个数据结构，但是对于二叉树遍历问题来说非递归要较递归复杂。程序一开始总是出现语法错误，改了很多次也上网查了相关资料，才最
10、后改为现在可以成功运营的程序。在这个过程中，我体会到开发工程师的感觉了，就是要用挑剔的眼光想问题并且不断地改善自己的程序。通过这次课程设计逐渐提高了自己的程序设计和调试能力，通过上机实习，严整自己设计算法的对的性，学会了有效运用基本调试方法，查找出代码中的错误并且修改。我会继续我的爱好编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。6.附录#include #include #include#define MAX 10 /结点个数不超过10个typedef char ElemType;/定义二叉树结点值的类型为字符型typedef struct bnode/二叉链表结构定义Elem
11、Type 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)
