树与二叉树的转换的实现_课程设计 (2)
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．设计题目
树与二叉树的转换实现 1.2设计要求
1、以及树的前序、后序的递归、非递归遍历算法，层次序的 非递归遍历算法的实现，应包含建树的实现。 2、遍历的内容应是千姿百态的。 二、设计小组成员 金亮
三．指导老师
武彬
四．设计课题
实现树与二叉树的转换的实现，以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（多种遍历可以只实现一个。）
五．基本思路及关键问题的解决方法 1. 二叉树创建
用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标 为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 2. 先序遍历二叉树的递归算法
若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（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. 层次序遍历算法
按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。 六、算法及流程图
七．调试过程中出现的问题及相应解决办法
在调试过程中出现了很多问题，定义表过长的，处理记录数量错误时程序的异常，记录冲突次数等等。
通过问同学，查资料，我知道路定义过长则减少某些属性的字符数。处理记
录数量错误时程序的异常则在被调用类（被主程序或其他类调用的类）中捕获异常记录到容器类中，然后抛出；在调用类（非主程序类）中继续捕获，然后同样是记录到错误容器继续向上抛出；依此方法直到最后在主程序中（入口程序类）捕获异常（记住这个捕获一定要捕获所有可能异常的情况）然后连同此次错误信息一并记录到错误容器，写入错误日志，给出
相应提示。
二叉树遍历中用到的最重要的一个思想就是递归调用，这次作业使我对递归有了深入的理解，尤其是对退回上一层后应执行的语句和结点位置的丝路更加清晰。程序调试比较顺利。
八、课程设计心得体会
以前用C 编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭意识和简单的语句来堆砌出一段段程序。现在变成感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么。然后再选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以自习斟酌出对挑选出最合适当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写程序的质量。 另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。 这次试验也让我看到了自己的不足，还是不太用模版类。还有许多关于C++的一些比较具体的东西还不太懂，比方说指针。这次实验还让我意识到只有不管在机子上调试程序，自己的水平才能得到提高。 我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。
九、源程序
#include #include #include #include #define edgetype int #define vextype int #define MAX 8
typedef struct node {
int vextex; struct node *next; }edgenode; typedef struct {
int vextex; int x,y;
edgenode *link;
}vexnode;
const int px[8]={1,2,2,1,-1,-2,-2,-1}; const int py[8]={2,1,-1,-2,-2,-1,1,2}; const int L=8,H=8; vexnode ga[L*H]; int visited[L*H]={0}; typedef struct {
int stack[L*H]; int top; }seqstack; seqstack s;
void setnull(seqstack *s) {s->top=-1;}
int empty(seqstack *s) {
if(s->top
int push(seqstack *s,int x) {
if(s->top>L*H-1) {
printf("stack overflow!\n"); return 0; }
else {
s->stack[++s->top] = x; return 1; }
}
int pop(seqstack *s) {
if(s->top
{
printf("stack empty!\n"); return NULL; } else
{
s->top--;
return(s->stack[s->top+1]); } } void init() {
int n;
for (int i=0;i
for (int j=0;j
n=L*i+j;
ga[n].vextex=n;
ga[n].x=j; ga[n].y=i;
ga[n].link=NULL; } }
for (i=0;i
edgenode *p;
for (int k=0;k
int tx=ga[i].x+px[k]; int ty=ga[i].y+py[k];
if(tx=L||ty>=H) continue; else
{
p=(edgenode*)malloc(sizeof(edgenode)); p->vextex=ty*L+tx; p->next=ga[i].link; ga[i].link=p; } } } }
void show() { int i;
printf("\n");
for (i=0;i
printf("%d->",ga[i].vextex); edgenode *p;
p=(edgenode*)malloc(sizeof(edgenode)); p=ga[i].link; while (p!=NULL) {
printf("%d ",p->vextex); p=p->next; }
printf("\n"); }
}
void showanswer() {
int rank[L*H];
int tag=s.top;
for (int i=L*H-1;i>=0;i--) {
rank[s.stack[tag--]]=i;
}
for (i=0;i
if (i%L==0&&i) {
printf("\n"); } printf("%d ",rank[i]);
}
}
int sum=1; int HFS(int n) {
edgenode *p; push(&s,ga[n].vextex); p=ga[n].link;
visited[n]=1;
while (p!=NULL) {
if (!visited[p->vextex]) {
HFS(p->vextex); }
p=p->next; }
if (s.top==L*H-1) {
printf("answer %d:\n",sum++); showanswer(); printf("\n"); }
visited[s.stack[s.top]]=0; pop(&s);
if (empty(&s)) {
return 0; }
return 0; }
int main()
{
int n;
for (n=0;n
memset(visited,0,sizeof(visited)); init(); show(); setnull(&s); HFS(n); getch(); } return 0; }
十、参考文献及资料：
[1]耿国华 数据结构——C 语言描述 高等教育出版社 [2]严蔚敏 数据结构——C 语言描述 清华大学出版社 [3]百度 .com