主函数和层次建立二叉树 数据结构课程设计.docVIP

黑龙江八一农垦大学 《数据结构课程设计》报告 设计名称 主函数和层次建立二叉树 专 业 信息与计算科学 年 级 11级 组 长 俎向朋 学 号 20114091024 组 员 徐丰 黄复闯 学 号 20114091017（徐丰） 20114091023（黄复闯） 黑龙江八一农垦大学文理学院数学实验室 目 录 一、设计题目 1 二、运行环境 1 三、设计思想 1 四、流程图 1 五、算法设计分析 1 六、运行结果分析 3 七、学习总结 6 八、源代码 6 主函数代码 6 层次建立二叉树代码 8 一、设计题目 主函数设计和层次建立二叉树 二、运行环境 VC++6.0 三、设计思想 主函数设计 由于程序的功能进行的了模块化设计，分别由各小组完成，所以主函数的设计是对所有模块的调用以实现函数的各种功能，进而完成程序的功能实现。 各个功能模块是并列关系，就用switch分支结构实现对功能函数的平行调用。 为了使操作者清楚自己的指令所实现的功能，所以设计了一个主界面来介绍模块功能和对应的操作指令。 四、流程图 略（本小组负责设计主函数故流程图省略）。 五、算法设计分析 我们小组选用层次建立法建立二叉树，操作时按层次直接输入即可，不需要将元素进行先序或中序或后序处理。为了实现二叉树的层次输入建立而采用队列作为二叉树的存储结构。另外，还选用了结构体等数据结构。 具体数据结构介绍如下： 二叉树结点结构体： typedef struct Binnode{ char data; struct Binnode *lchild; struct Binnode *rchild; }; 该结构体包含数据域（储存结点信息）和指针域（储存结点的左右孩子结点的指针）。 二叉树结点队列： typedef struct queue{ Bintree data[30]; int front; int rear; }; 该结构体包含一个Bintree类型的数组，其内储存结点信息。 层次建立二叉树的算法设计如下： Bintree Level_Creat() { Bintree root,p,s; queue node; node.front=node.rear=0; char ch; ch=getchar(); if(ch==) { return NULL; } root=(Binnode*)malloc(sizeof(Binnode)); //生成根结点 root-data=ch; node.data[node.rear++]=root; //用队列实现层次遍历 while(node.frontnode.rear) { p=node.data[node.front++]; ch=getchar(); //为了简化操作，分别对左右子结点进行赋值。 if(ch!=)//子树不空则进队列进行扩充。下同 { s=(Binnode*)malloc(sizeof(Binnode)); s-data=ch; p-lchild=s; node.data[node.rear++]=s; } else { p-lchild=NULL; } ch=getchar(); if(ch!=) { s=(Binnode*)malloc(sizeof(Binnode)); s-data=ch; p-rchild=s; node.data[node.rear++]=s; } else { p-rchild=NULL; } } return root; } 六、运行结果分析 主界面运行结果分析 输入任意键进入选项操作界面 输入1—12 实现所选操作 层次建立二叉树运行结果分析： 进行输入操作时要注意程序终止条件，由于我们小组采用的是层次建立，所以结束条件为当二叉树的地所有叶子结点的左右孩子指针域为空时程序结束： 简单举例： 输入ABCDEFGHLI 输出结果如下; 七、学习总结 我们学习小组在做这次课程设计的时候我