树与二叉树的转换的实现_课程设计 .doc

《树与二叉树的转换的实现_课程设计 .doc》由会员分享，可在线阅读，更多相关《树与二叉树的转换的实现_课程设计 .doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、XXXXX学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称树与二叉树的转换的实现_课程设计 专业 计算机软件工程 班级 XXXXXXXXXXXXXXX 学号 XXXXXXX 姓名 XXXX 联系方式 XXXXXXXXXXXX 指导教师XXXX 20 14 年 6 月 17 日目 录一、数据结构课程设计任务书1 1.1设计题目1 1.2设计要求1二、设计小组成员1三、指导老师1四、设计课题1五、基本思路及关键问题的解决方法1六、算法及流程图2七调试过程中出现的问题及相应解决办法3八、课程设计心得体会3九、源程序4十、参考文献及资料一、数据结构课程设计任务书1.1设计题目 树与二叉

2、树的转换实现1.2设计要求1、以及树的前序、后序的递归、非递归遍历算法，层次序的 非递归遍历算法的实现，应包含建树的实现。2、遍历的内容应是千姿百态的。二、设计小组成员 金亮三指导老师武彬四设计课题 实现树与二叉树的转换的实现，以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（多种遍历可以只实现一个。）五基本思路及关键问题的解决方法1.二叉树创建用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 2.先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍

3、历左子树；（3）先序遍历右子树。void PreOrder(BiNode root)。3.后序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)。4.先序非递归算法BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。5.后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)6.层次序遍历算法按照树的层次从

4、左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。六、算法及流程图退出程序层次遍历开始双亲法建树按照格式输入各个结点输出树的结点情况1主菜单前序遍历（递归）后序遍历（递归）前序遍历（非递归）后序遍历（非递归）输出遍历结果副菜单退出程序23540069七调试过程中出现的问题及相应解决办法在调试过程中出现了很多问题，定义表过长的，处理记录数量错误时程序的异常，记录冲突次数等等。通过问同学，查资料，我知道路定义过长则减少某些属性的字符数。处理记录数量错误时程序的异常则在被调用类（被主程序或其他类调用的类）中捕获异常记录到容器类中，然后抛出

5、；在调用类（非主程序类）中继续捕获，然后同样是记录到错误容器继续向上抛出；依此方法直到最后在主程序中（入口程序类）捕获异常（记住这个捕获一定要捕获所有可能异常的情况）然后连同此次错误信息一并记录到错误容器，写入错误日志，给出相应提示。二叉树遍历中用到的最重要的一个思想就是递归调用，这次作业使我对递归有了深入的理解，尤其是对退回上一层后应执行的语句和结点位置的丝路更加清晰。程序调试比较顺利。 八、课程设计心得体会以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭意识和简单的语句来堆砌出一段段程序。现在变成感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素

6、，首先选取自己需要的数据结构，是树还是图或是别的什么。然后再选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以自习斟酌出对挑选出最合适当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写程序的质量。 另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。 这次试验也让我看到了自己的不足，还是不太用模版类。还有许多关于C+的一些比较具体的东西还不太懂，比方说指针。这次实验还让我意识到只有不管在

7、机子上调试程序，自己的水平才能得到提高。 我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。九、源程序#include#include#include#include#define edgetype int#define vextype int#define MAX 8typedef struct node int vextex; struct node *next;edgenode;typedef struct int vextex; int x,y; edgenode *link;vexnode;const int px8=1,2,2,1,-1,-2,-2,-1;

8、const int py8=2,1,-1,-2,-2,-1,1,2;const int L=8,H=8;vexnode gaL*H; int visitedL*H=0; typedef struct int stackL*H; int top; seqstack; seqstack s; void setnull(seqstack *s) s-top=-1; int empty(seqstack *s) if(s-toptopL*H-1) printf(stack overflow!n); return 0; else s-stack+s-top = x; return 1; int pop(

9、seqstack *s) if(s-toptop-; return(s-stacks-top+1); void init() int n; for (int i=0;iH;i+) for (int j=0;jL;j+) n=L*i+j; gan.vextex=n; gan.x=j; gan.y=i; gan.link=NULL; for (i=0;iL*H;i+) edgenode *p; for (int k=0;kMAX;k+) int tx=gai.x+pxk; int ty=gai.y+pyk; if(tx0|ty=L|ty=H) continue; else p=(edgenode*

10、)malloc(sizeof(edgenode); p-vextex=ty*L+tx; p-next=gai.link; gai.link=p; void show() int i; printf(n); for (i=0;i,gai.vextex); edgenode *p; p=(edgenode*)malloc(sizeof(edgenode); p=gai.link; while (p!=NULL) printf(%d ,p-vextex); p=p-next; printf(n); void showanswer() int rankL*H; int tag=s.top; for (

11、int i=L*H-1;i=0;i-) ranks.stacktag-=i; for (i=0;ivextex) HFS(p-vextex); p=p-next; if (s.top=L*H-1) printf(answer %d:n,sum+); showanswer(); printf(n); visiteds.stacks.top=0; pop(&s); if (empty(&s) return 0; return 0; int main() int n; for (n=0;nH*L;n+) memset(visited,0,sizeof(visited); init(); show(); setnull(&s); HFS(n); getch(); return 0;十、参考文献及资料：1耿国华 数据结构C语言描述 高等教育出版社2严蔚敏 数据结构C语言描述 清华大学出版社3百度 www.baidu .com