完全二叉树操作演示

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称完全二叉树操作演示专业班级计算机科学与技术专升本1班学号14011016、14011040、14011019姓名李鹏王帅李泳波联系方式指导教师严小燕完成日期:2014年12月27日目录1数据结构课程设计任务书.................................11.1题目................................................11.2目的................................................11.3要求................................................12总体设计...............................................12.1功能模块设计........................................12.2所有功能模块流程图..................................13详细设计...............................................23.1程序中所采用的数据结构及存储结构的说明..............23.2算法设计思想........................................33.3主要的功能函数......................................34调试与测试.............................................34.1调试方法与步骤......................................44.2测试结果分析与讨论..................................44.3测试过程中遇到的主要问题及采取的解决措施............55时间复杂度分析.........................................66程序清单...............................................67总结..................................................12参考文献................................................1311数据结构课程设计任务书1.1题目完全二叉树操作演示1.2目的（1）掌握二叉树的概念和性质。（2）掌握完全二叉树存储结构。（3）掌握完全二叉树的基本操作。1.3要求（1）创建完全二叉树（用字母表示节点）(用顺序方式存储)。（2）求二叉树的深度和叶子结点数。（3）实现二叉树的前序、中序、后序和层次遍历。（4）查找给定结点的双亲、祖先和左右孩子节点。2总体设计2.1功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如图1：图1功能组成框图2.2所有功能模块流程图设计好功能模块后，各个模块的关系如下图2：完全二叉树操作演示创建完全二叉树显示完全二叉树深度层次遍历前中后序遍历查找双亲左右孩子叶子节点数退出程序2图2流程图3详细设计3.1程序中所采用的数据结构及存储结构的说明（1）整个程序采用结构体与顺序表相结合的编程方法一共完成了7个功能。在你输入错误时有报错消息，这样使整个程序运行起来更加完整。程序中有若干个子函数被主函数调用执行。结构体定义如下：#defineMAX100//定义100个节点typedefstruct{chardat;//节点信息}node;typedefstructTree//节点组成树{intlength;node*r;//指向根节点开始创建完全二叉树选择操作显示完全二叉树深度查找双亲左右孩子叶子节点数层次遍历前中后序遍历退出系统3}Tree;3.2算法设计思想完全二叉树具有以下几个性质，由此可设计出相应算法。性质1完全二叉树约定编号从根节点起，自上而下，自左自由。由此设计出顺序存储结构且进行层次遍历时，只需输出顺序表中存储的元素即可。性质2具有n个结点的完全二叉树的深度为。由此设计出深度计算函数。性质3完全二叉树第i层上的结点数目最多为2i-1(i≥1)。由此设计出每层节点个数函数，在显示完全二叉树时可以找到其最左边的孩子节点。性质4在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点且叶子节点个数为（n+1）/2。由此设计出叶子节点函数。性质5在完全二叉树中，若根节点为i，则左孩子节点为2i,右孩子节点为2i+1。由此采用递归思想，可以对完全二叉树进行前序、中序、后序遍历和给定节点找其双亲及孩子。3.3主要的功能函数CreatTree(Tree&t)//创建完全二叉树LevCount(intn)//统计每层最多节点个数OutputTree(Tree&t)//显示完全二叉树Depth(Tree&t)//求树深Leaf(Tree&t)//叶子节点PreOrder(Tree&t,intr)//先序遍历InOrder(Tree&t,intr)//中序遍历PostOrder(Tree&t,intr)//后序遍历LeOrder(Tree&t)//层次遍历Search(Tree&t,charq)//查找给定结点的双亲、左右孩子完善以上函数，就可以设计出完全二叉树的操作了。4调试与测试1log2n44.1调试方法与步骤第一步：建立完全二叉树，输入节点个数和节点。第二步：选择要操作的对象，比如显示完全二叉树，按下电脑键盘1。查找双亲及孩子功能函数在操作时需要输入信息，按照相应提示输入相应信息即可运行，输入不对时，程序会有报错提示信息。4.2测试结果分析与讨论假定完全二叉树节点数为9个，节点信息为a、b、c、d、e、f、g、h、i。操作结果如下图所示：（1）操作界面图3操作界面（2）创建完全二叉树图4创建完全二叉树（3）显示完全二叉树5图5显示完全二叉树（4）完全二叉树深度图6完全二叉树深度（5）完全二叉树层次遍历图7完全二叉树层次遍历（6）完全二叉树前序、中序、后序图8前序、中序、后序遍历（7）查找给定节点双亲及孩子图9查找给定节点双亲及孩子（8）完全二叉树叶子节点数图10节点数4.3测试过程中遇到的主要问题及采取的解决措施6在建立完全二叉树时操作不当会出现程序错误。如下图：图11错误界面导致以上错误的原因是，再输入第一个字母元素时，不能空格，程序中的getchar()函数只能接收上一个空格字符，即输入节点产生的空格，解决方法是重新编译运行程序按要求输入即可。5时间复杂度分析这里主要分析查找节点时的时间复杂度，当给定节点时，需要在顺序表中进行一一比对查找，即顺序查找，那么最坏的情况就是找最后一个叶子节点了，这就跟表长有关系了，所以时间复杂度为n=length。6程序清单#includestdio.h#includestdlib.h#includestring.h#defineMAX100//定义100个节点typedefstruct{chardat;//节点信息}node;typedefstructTree//节点组成树{intlength;node*r;//指向根节点}Tree;intCreatTree(Tree&t){inti;7t.r=(node*)malloc(MAX*sizeof(node));//r[MAX]printf(请输入完全二叉树节点个数,输入后继续:);scanf(%d,&t.length);printf(请输入完全二叉树节点，以字母空格隔开且不要以空格开头:);for(i=0;it.length;i++){getchar();scanf(%c,&t.r[i+1].dat);}return1;}intLevCount(intn)//统计每层最多节点个数{intp=1;for(inti=1;i=n;i++)p=p*2;returnp;}voidOutputTree(Tree&t)//显示完全二叉树{intk=0,n=t.length;//求树的层数Kwhile(n){k++;n=n/2;}//层数控制行每层节点个数控制列for(inti=1;i=k;i++)//jLevCount(i)-LevCount(i-1)&&LevCount(i-1)+j=t.length{//判断条件是每层节点个数且以最左边孩子节点开始不小于表长for(intj=0;jLevCount(i)-LevCount(i-1)&&LevCount(i-1)+j=t.length;j++)8printf(%2c,t.r[LevCount(i-1)+j].dat);//输出每层各个节点printf(\n);}}voidDepth(Tree&t)//求树深{intk=0,n=t.length;while(n){k++;n=n/2;}printf(二叉树深度：%2d\n,k);}voidLeaf(Tree&t)//叶子节点{intlef;lef=(t.length+1)/2;printf(叶子节点个数：%2d\n,lef);}voidPreOrder(Tree&t,intr)//先序遍历DLR{if(t.lengthr)return;printf(%c,t.r[r].dat);PreOrder(t,2*r);PreOrder(t,2*r+1);}voidInOrder(Tree&t,intr)//中序遍历LDR{if(t.lengthr)return;InOrder(t,2*r);9printf(%c,t.r[r].dat);InOrder(t,2*r+1);}voidPostOrder(Tree&t,intr)//后序遍历LRD{if(t.lengthr)return;PostOrder(t,2*r);PostOrder(t,2*r+1);printf(%c,t.r[r].dat);}voidLeOrder(Tree&t)//层次遍历{inti;for(i=0;it.length;i++)printf(%c,t.r[i+1].dat);printf(\n);}voidSearch(Tree&t,charq)//查找给定结点的双亲、左右孩子{boolflag=false;inti;printf(请输入查找节点:);getchar();scanf(%c,&q);for(i=1;i=t.length;i++){if(t.r[i].dat==q)//找到给定节点下标且默认节点0号单元无节点{if(i/2==0)//根节点无双亲printf(此节点无双亲);else10printf(此节点的双亲:%c,t.r[i/2].dat);if(2*it.length)//左孩子下标值大于表长，肯定无孩子printf(此节点无左右孩子);else{printf(此节点左孩子:%c,t.r[2*i].dat);if(2*i+1t.length)//右孩子下标值大于表长，只是无右孩子printf(此节点无右孩子);else{printf(此节点右孩子:%c,t.r[2*i+1].dat);}}flag=true;break;}}if(flag==false)printf(二叉树中没有此节点\n);printf(\n);}voidmenu(){printf(*****************************菜单************************************\n);printf(\n);printf(\n);printf(1.创建完全二叉树2.显示完全二叉树\n);printf(\n);printf(3.完全二叉树深度4.完全二叉树层次遍历\n);printf(\n);printf(5.完全二叉树的前序、中序、后序6.查找给定结点双亲、左