二叉树基本操作演示程序的设计与实现.doc

数据结构课程设计报告XXX大学电子与信息工程学院数据结构课程设计报告 ( 20122013年度第一学期)课程名称： 数据结构课程设计 题 目 ：6.2二叉树的基本操作演示程序 院 系： 计算机科学系 班 级： 10软件本二班 姓 名： X X 学 号： 100913005 指导教师： 孙凌宇老师 成 绩： 2012 年 月 日成 绩 评 定一、 指导教师评语二、 成绩成绩备注 指导教师： 日 期： 年 月 日设计题目：6.2二叉树基本操作演示程序的设计与实现一、设计要求1问题描述设计一个与二叉树基本操作相关的演示程序。2需求分析（1）创建二叉树。按照用户需要的二叉树，构建二叉树。（2）将创建的二叉树，以树状形式输出。（3）分别以先序、中序、后序三种遍历访问二叉树。（4）输出二叉树的叶子结点及叶子结点的个数。（5）输出二叉树的高度。二、概要设计为了实现以上功能，可以从3个方面着手设计。1 主界面设计为了实现二叉树的相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。本程序主控菜单运行界面如图1所示。图1“二叉树基本操作程序”主菜单2存储结构设计本程序采用二叉链式存储类型（BiTNode）存储二叉树的结点信息。二叉树的链表中的结点至少包含3个域：数据域（data）、左孩子指针域（Lchild）、和右孩子指针域（Rchild）。3系统功能设计本程序除了完成二叉树的创建功能外还设置了8个子功能菜单。由于这8个子功能都是建立在二叉树的构造上的，所以二叉树的创建由主函数main（）实现。8个子功能的设计描述如下：(1) 树状输出二叉树。树状输出二叉树有函数TranslevePrint（）实现。当用户选择该功能时，系统即以树状的形式输出用户所创建的二叉树。(2)先序遍历二叉树。由函数PreOrder（）实现。该功能按照先序遍历访问二叉树的方法输出先序遍历序列。(3)中序遍历二叉树。由函数InOrder（）实现。该功能按照中序遍历访问二叉树的方法输出中序遍历序列。(4)后序遍历二叉树。由函数PostOrder（）实现。该功能按照后序遍历访问二叉树的方法输出后序遍历序列。(5)输出叶子结点。该功能采用先序遍历二叉树的方法，依次输出叶子结点。由函数PreOrderLeaf（）实现。(6)输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount（）函数实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有一个结点时，叶子结点个数为1；否则，叶子结点个数等于左、右子树叶子结点数之和。(7)输出二叉树的深度。该功能即输出二叉树结点所在层次的最大值。由函数PostTreeDepth（）实现，采用后序遍历的递归算法求二叉树的深度。(8)退出。由exit（0）函数实现。三、模块设计1模块设计本程序包含三个模块：主程序模块、建立二叉树模块和工作区模块。其调用关系如图2所示。主程序模块建立二叉树模块工作区选择模块图2 模块调用示意图2系统子程序及功能设计本系统共设置11个子程序，各子程序的函数名及功能说明如下：(1) void CreateBiTree(BiTree *bt) /建立二叉树(2) void TranslevelPrint(BiTree bt) /树状打印二叉树(3) void Visit(char ch) /输出结点(4) void PreOrder(BiTree root) /先序遍历二叉树(5) void InOrder(BiTree root) /中序遍历二叉树(6) void PostOrder(BiTree root) /后序遍历二叉树(7) void PrePrderLeaf(BiTree root) /输出叶子结点(8) int LeafCount(BiTree root) /输出叶子结点的个数(9) int PostTreeDepth(BiTree root) /输出二叉树的深度(10) void mainwork( ) /主要工作函数。操作区用户界面(11) void main( ) /主函数。创建二叉树。调用工作区模块函数 3函数主要调用关系图本系统11个子程序之间的主要调用关系如图3所示。图中数字是各函数的编号。10 mainwork()98765423111 main()图3 系统函数调用关系图四、详细设计1数据类型定义Typedef struct BiTNode/定义二叉树结点结构char data; /数据域struct BiTNode *LChild, *RChild; /左右孩子指针域2系统主要子程序详细设计(1) 主函数模块设计主函数，创建二叉树，调用工作区模块函数void main() printf(首先请输入二叉树的结点序列：);printf(【提示：用隔离】n);CreateBiTree(&T);printf(【零式提醒】看下面的菜单哦：n);mainwork ();(2) 建立二叉树模块该模块是实现工作区模块的基础，工作区模块实现的8个子功能菜单都建立在此模块之上.void CreateBiTree(BiTree *bt) /按照先序序列建立二叉树的二叉链表char ch;scanf(%c,&ch);if(ch=) *bt=NULL;else*bt=(BiTree)malloc(sizeof(BiTNode); /生成一个新结点(*bt)-data=ch;CreateBiTree(&(*bt)-LChild); /生成左子树CreateBiTree(&(*bt)-RChild); /生成右子树(3) 用户工作区模块设计主要工作函数，操作区用户界面设计。void mainwork()int yourchoice;printf( _ n);printf(| |n);printf(|-欢迎使用二叉树基本操作程序-|n);printf(|- _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -|n);printf(|- -菜单选项- -|n);printf(|- 1.树状输出二叉树 2.先序遍历二叉树 -|n);printf(|- 3.中序遍历二叉树 4.后序遍历二叉树 -|n);printf(|- 5.输出叶子结点 6.输出叶子结点个数 -|n);printf(|- 7.输出二叉树的深度 8.退出 -|n);printf(|-|n);printf(|-【零 式】制 作QQ:461595940-|n);printf(|_|n);printf(【零式提醒】您的输入只能在1至8之间哦！n);printf(看数输数:);scanf(%d,&yourchoice);while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|yourchoice=5|yourchoice=6|yourchoice=7|yourchoice=8)printf(【键入警告ERROR!】n);printf(请重新输入：);scanf(%d,&yourchoice);while(1)switch(yourchoice)case 1:printf(树的形状为:n); TranslevelPrint(T); getch(); break;case 2:printf(先序遍历序列为:); PreOrder(T); break;case 3:printf(n中序遍历序列为:); InOrder(T); break;case 4:printf(n后序遍历序列为:); PostOrder(T); break;case 5:printf(叶子结点为:); PreOrderLeaf(T); break;case 6:printf(叶子结点为:%d,LeafCount(T); break;case 7:printf(二叉树的深度为:%dn,PostTreeDepth(T); break;case 8: system(cls); exit(0); break;default: break;printf( n_ n);printf(| |n);printf(|-欢迎使用二叉树基本操作程序-|n);printf(|- _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -|n);printf(|- -菜单选项- -|n);printf(|- 1.树状输出二叉树 2.先序遍历二叉树 -|n);printf(|- 3.中序遍历二叉树 4.后序遍历二叉树 -|n);printf(|- 5.输出叶子结点 6.输出叶子结点个数 -|n);printf(|- 7.输出二叉树的深度 8.退出 -|n);printf(|-|n);printf(|-【零 式】制 作QQ:461595940-|n);printf(|_|n);printf(【零式提醒】您的输入只能在1至8之间哦！n);printf(看数输数:);scanf(%d,&yourchoice);/endwhile(1)/endmainwork(4) 树状输出二叉树void TranslevelPrint(BiTree bt) /本算法实现二叉树的按层打印struct nodeBiTree vecMAXLEN; /存放树结点int layerMAXLEN; /结点所在的层int locateMAXLEN;/打印结点的位置int front,rear;q; /定义队列qint i, j=1, k=0, nLocate;q.front = 0; q.rear = 0; /初始化队列q队头，队尾printf( );q.vecq.rear=bt; /将二叉树根结点如队列q.layerq.rear=1;q.locateq.rear=20;q.rear = q.rear+1;while(q.front q.rear)bt = q.vecq.front;i = q.layerq.front;nLocate = q.locateq.front;if(j i) /进层打印时换行printf(n); printf(n);j=j+1; k=0;while(knLocate)printf( ); k+;while (kdata);q.front=q.front+1;if(bt-LChild !=NULL) /存放在左子树，将左子树根结点如队列q.vecq.rear=bt-LChild;q.layerq.rear=i+1;q.locateq.rear=(int)(nLocate - pow(2, NLAYER-i-1);q.rear = q.rear +1;if(bt-RChild !=NULL) /存放右子树，将右子树根结点入队列q.vecq.rear=bt-RChild;q.layerq.rear=i+1;q.locateq.rear=(int)(nLocate+pow(2,NLAYER-i-1);q.rear=q.rear+1;五、测试分析请根据先根结点，按照从上到下、左至有的次序依次先根遍历根的每棵子树的方法，分别输入二叉树的结点序列（号表示该结点为空）。例如“ABDECH”程序运行得到如图1所示的开始界面。各子功能测试运行结果如下。1. 树状输出二叉树在主菜单下，用户输入1并回车，运行结果如图4所示。图4 按树形输出创建二叉树2. 先序遍历二叉树在主菜单下，用户输入2并回车，运行结果如图5所示。图5 输出二叉树先序遍历序列3. 中序遍历二叉树在主菜单下，用户输入3并回车，运行结果如图6所示。图6输出二叉树中序遍历序列4. 后序遍历二叉树在主菜单下，用户输入3并回车，运行结果如图7所示。图7 输出二叉树后序遍历序列5. 输出叶子结点在主菜单下，用户输入5并回车，运行结果如图8所示。图8 输出二叉树的叶子结点6. 输出叶子结点个数在主菜单下，用户输入6并回车，运行结果如图9所示。图9输出二叉树的叶子结点个数7. 输出二叉树的深度在主菜单下，用户输入7并回车，运行结果如图10所示。图10 输出二叉树的深度8. 退出在主菜单下，用户输入8并回车，即退出“二叉树基本操作程序”。六、用户手册 (1) 本程序执行文件为“二叉树的基本操作演示.exe”。(2) 进入本程序之后，首先按照提示输入二叉树的结点，如按下列次序顺序读入字符ABDECH。(3) 随即显示系统主菜单界面，用户可在该界面下输入各子菜单前对应的数字并回车，执行相应子菜单命令。七、调试报告(1) 调试过程中最常见的便是代码输入错误，如字母大小写、顺序颠倒、符号的半/全角使用等一些问题，都是在调试过程中逐一改正的。(2)本程序是二叉树最基本的操作，没有深入。难免在执行程序时对输入的其他指令发生错误。所以只要根据本程序的说明操作即可。(3)我想以后还可以给此程序添加其他一些功能，例如创建的二叉树是空树还是满二叉树；对创建的二叉树进行查找，删除，插入，匹配；如何解决程序顺利执行而不会陷入死循环一些问题等等。(4)感想：程序员真的是太乏味了，不停的码代码，测代码，调代码，分析算法，考虑结构，然后不停的测试，不停的修改错误，直到没有问题为止。对我们年轻人的程序员，尤其是刚入门的学生来说，没有多大的兴趣和耐性去搞，所以当认真的去完成这个作业的时候，才发现八窍通了七窍其结果是一窍不通。然而，当我就这一个小小的简单程序独立完成时，心中的喜悦和成就感却又充满心中，让我小乐了一下。我想IT业界的程序员们，埋头苦日，等的就是完成的那一刻的喜悦与成就吧。所以坚信自己是一大奇迹，我就能乘风万里。八、程序清单#include #include #include #include #define MAXLEN 100#define NLAYER 4typedef struct BiTNode /定义二叉树结点结构char data; /数据域struct BiTNode *LChild,*RChild; /左右孩子指针域BiTNode,*BiTree;BiTree T;/1.建立二叉树/该模块是实现工作区模块的基础，工作区模块实现的8个子功能菜单都建立在此模块之上void CreateBiTree(BiTree *bt)/源代码参见:6.2.4详细设计2.(2) /按照先序序列建立二叉树的二叉链表char ch;scanf(%c,&ch);if(ch=) *bt=NULL;else*bt=(BiTree)malloc(sizeof(BiTNode); /生成一个新结点(*bt)-data=ch;CreateBiTree(&(*bt)-LChild); /生成左子树CreateBiTree(&(*bt)-RChild); /生成右子树/2.属性打印二叉树void TranslevelPrint(BiTree bt)/源代码参见:6.2.4详细设计2.(4) /本算法实现二叉树的按层打印struct nodeBiTree vecMAXLEN;/存放树结点int layerMAXLEN;/结点所在的层int locateMAXLEN;/打印结点的位置int front,rear;q;/定义队列qint i, j=1, k=0, nLocate;q.front = 0; q.rear = 0;/初始化队列q队头，队尾printf( );q.vecq.rear=bt;/将二叉树根结点如队列q.layerq.rear=1;q.locateq.rear=20;q.rear = q.rear+1;while(q.front q.rear)bt = q.vecq.front;i = q.layerq.front;nLocate = q.locateq.front;if(j i)/进层打印时换行printf(n); printf(n);j=j+1; k=0;while(knLocate)printf( ); k+;while (kdata);q.front=q.front+1;if(bt-LChild !=NULL) /存放在左子树，将左子树根结点如队列q.vecq.rear=bt-LChild;q.layerq.rear=i+1;q.locateq.rear=(int)(nLocate - pow(2, NLAYER-i-1);q.rear = q.rear +1;if(bt-RChild !=NULL) /存放右子树，将右子树根结点入队列q.vecq.rear=bt-RChild;q.layerq.rear=i+1;q.locateq.rear=(int)(nLocate+pow(2,NLAYER-i-1);q.rear=q.rear+1;/3.输出结点void Visit(char ch)printf(%c ,ch);/4.先序遍历二叉树void PreOrder(BiTree root) /先序遍历二叉树，root为指向二叉树（或莫一子树）根结点的指针if (root!=NULL)Visit(root -data); /访问根结点PreOrder(root -LChild); /先序遍历左子树PreOrder(root -RChild); /先序遍历右子树/5.中序遍历二叉树void InOrder( BiTree root) /中序遍历二叉树，root为指向二叉树（或莫一子树）根结点的指针if (root!=NULL)InOrder(root -LChild);/中序遍历左子树Visit(root -data);/访问根结点InOrder(root -RChild);/中序遍历右子树/6.后序遍历二叉树void PostOrder(BiTree root)/后序遍历二叉树，root为指向二叉树（或莫一子树）根结点的指针if(root!=NULL)PostOrder(root -LChild);/后序遍历左子树PostOrder(root -RChild);/后序遍历右子树Visit(root -data);/访问根结点/7.输出叶子结点void PreOrderLeaf(BiTree root) /先序遍历二叉树并输出叶子结点，root为指向二叉树根结点的指针if (root!=NULL)if (root -LChild=NULL & root -RChild=NULL)printf(%c , root -data);/输出叶子结点PreOrderLeaf(root -LChild);/先序遍历左子树PreOrderLeaf(root -RChild);/先序遍历右子树/8.输出叶子结点的个数int LeafCount(BiTree root)int LeafNum;if(root=NULL) LeafNum=0;else if(root-LChild=NULL)&(root-RChild=NULL) LeafNum=1;else LeafNum=LeafCount(root-LChild)+LeafCount(root-RChild); /叶子树为左右孩子树叶子数目之和return LeafNum;/9.输出二叉树的深度int PostTreeDepth(BiTree root)/后序遍历求二叉树的深度递归算法int h1, hr, max;if(root!=NULL)h1=PostTreeDepth(root-LChild);/求左子树的深度hr=PostTreeDepth(root-RChild);/求右子树的深度max=h1hr?h1:hr;/得到左右子树深度较大者return(max+1);/返回树的深度else return(0);/如果是空树，则返回0/10.主要工作函数，操作区用户界面void mainwork()/源代码参见:6.2.4详细设计2.(3)int yourchoice;printf( _ n);printf(| |n);printf(|-欢迎使用二叉树基本操作程序-|n);printf(|- _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -|n);printf(|- -菜单选项- -|n);printf(|- 1.树状输出二叉树 2.先序遍历二叉树 -|n);printf(|- 3.中序遍历二叉树 4.后序遍历二叉树 -|n);printf(|- 5.输出叶子结点 6.输出叶子结点个数 -|n);printf(|- 7.输出二叉树的深度 8.退出 -|n);printf(|-|n);printf(|-【零 式】制 作QQ:461595940-|n);printf(|_|n);printf(【零式提醒】您的输入只能在1至8之间哦！n);printf(看数输数:);scanf(%d,&yourchoice);while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|yourchoice=5|yourchoice=6|yourchoice=7|yourchoice=8)printf(【键入警告ERROR!】n);printf(请重新输入：);scanf(%d,&yourchoi