计算子树的深度

课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 计算机科学系题目:计算子树的深度初始条件：编写递归算法：对二叉树中以元素值为X的结点为根的子树的深度。（1）二叉树采用二叉链表作为存储结构。（2） 按题集p44面题6.69所指定的格式输出建立的二叉树。（3） 以二叉树中任意元素值为x的结点为根的子树，输出其深度。（4）测试用例自己设计要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、 第19周完成。2、 7月1日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名：系主任（或责任教师）签名：计算子树的深度问题描述问题重述根据任务书中给定的初始条件，经分析我们要完成以下内容：首先，我们需要以二叉链表作为存储结构，用以存储各结点相关信息，并建立各结点间的相关关系；其次，我们需要将所输入的二叉树序列（在这里我们以先序序列输入二叉树序列），按照二叉树各结点相对位置，输出树状二叉树；最后，对任意输出的X,求二叉树中以元素值为x的结点为根的子树的深度。问题分析经过对题目要求的分析,要实现打印树状二叉树的功能,我们可以将二叉树各结点的元素值按照其相对位置存储在数组中。故在存储结构中需添加行列标志位。首先要解决的就是确定元素所在的行列序数。我们发现,元素所在列序对应于该元素所在二叉树中的层数,树中结点总数与数组行数相同,这样就需要找出其间的对应关系,经分析,若按照“右子树—根节点—左子树”的逆中序遍历整个二叉树,其输出结果与行序一一对应。对于求二叉树中以元素值为X的结点为根的子树的深度,需先找出该节点的位置,然后再调用求树的深度的函数,即可进行求解,以此可实现本课程设计所要实现地功能。

设计思想实现过程的框图描述YY/NN修改各结点列标志位L修改各结点行标志位H创建二叉树存储结构的设计修改数组元素值前序遍历层次遍历求子树深度查找结点打印数组逆中序遍历YY/NN修改各结点列标志位L修改各结点行标志位H创建二叉树存储结构的设计修改数组元素值前序遍历层次遍历求子树深度查找结点打印数组逆中序遍历结束结束存储结构的设计由于本次功能实现需要记录各结点在逆中序遍历输出次序中的序数和层次，以确认各结点对应数组的行列值，故在二叉链表存储结构中添加标志量h和l,分别对应数组行和列。存储结构如下:typedefstructBiTNode{TElemTypedata;//结点元素值inth; //结点所在行序intl; //结点所在列序structBiTNode*lchild,*rchild; //左右孩子指针}*BiTree;主要算法设计层次遍历根据队列先进先出的特点，对于每次进入队列的元素修改对应的标志位1,设计思想是:算法设计为:StatusLevelOrderTraverse(BiTree&T){ //层次遍历二叉树SqQueueQ;BiTreeq,p;q=T;InitQueue(Q); //构建一个空队列Qif(T){EnQueue(Q,q); //根结点入队列q->l=1; //修改根结点标志位}while(Q.front!=Q.rear) //队列判空{DeQueue(Q,q); //队首元素出队列，并赋值给qif(q->lchild){EnQueue(Q,q->lchild);p=q->lchild;p->L=q->l+1;}//修改左孩子标志位if(q->rchild){EnQueue(Q,q->rchild);p=q->rchild;p->L=q->l+1;}//修改右孩子标志位}returnOK;}二叉树到数组的映射TElemTypech[20][20];StatusPreOrder(BiTreeT){//先序遍历二叉树，并将元素值赋值给数组对应位置值inta,b;if(T){a=T->h;b=T->l;ch[a-1][b-1]=T->data;//修改数组对应位置值if(PreOrder(T->lchild))if(PreOrder(T->rchild))returnOK;returnERROR;}elsereturnOK;}求子树深度BiTreepl二NULL; //返回元素值为输入值x的结点StatusSearch(BiTreeT,TElemTypedata){ //查找元素值为data的结点，并返回其位置if(!pl&&T){if(T->data==data)pl=T;if(Search(T->lchild,data))

if(Search(T->rchild,data))returnOK;returnERROR;}elsereturnOK;}intDepth(BiTreeT){//求二叉树的深度intdepthLeft,depthRight,depthval;if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}测试用例设计本次检验程序所用示例为:AB#D##CE#F###预期输出为:对应二叉树为:预期输出为:CFEADB调试报告调试过程程序编写完成后，经检测无误后，开始调试，但未能像预期中那样输出正确结果，究其原因是，虽然程序没有语法错误，但却存在较多逻辑错误。在逆中序遍历过程中修改各结点行标志位h时，引入了计数标志i，希望其没执行一次,i加1，以进行标志位的修改赋值。但由于将其放置在函数体内部，在进行递归调用时,i值始终从1开始计数，导致运行结果出错。经过对程序的调试，发现了计数标志i的值自增过程出错，经修改，将其定义为全局变量，此函数运行结果无误。层次遍历过程中，未修改结点列标志位L,在根结点入队列时，将其L值改为1,表示第一层；同一次循环中，处于同一层的结点进入队列，故L值相同，比上一层多1，设置了自增计数器，来修改列表值位。但忽略了每次出队列的结点仅为一个，故每次循环中同一层的结点不可能全部进入队列，由于思想与算法的不同导致了这个错误。发现后，将修改变量设置为双亲结点标志位加1，这样就能够解决这个问题了。在计算子树深度时，直接编写了求二叉树的深度的函数，这样就需要一个附加函数查找元素值为输入值x的结点，并记录其位置。开始时，在函数体内设置变量，在先序遍历过程中比较各结点元素值以查找满足要求的结点，但由于函数体采用的是递归调用的思想，循环执行次数比较多，在查找并确定结点位置之后，返回节点位置过程中，无法控制结束条件以正确退出函数，这就导致虽然找到了结点，但在退出过程中出现了错误。为解决此问题，在与同学交流中，建议我使用全局变量来记录所求结点位置，这样就很好地解决了问题。程序设计过程中，较多使用了递归的思想，虽然简化了程序设计，但控制条件却难以把握，使得我必须翻阅书本，理解书中程序递归调用中的控制思想，然后再结合本程序需要进行设置，当然这出现了许多错误，所以在设计时，先用简单数据进行分析以确定条件的设定。对设计和编码的讨论和分析根据本次课程设计所要实现的功能，在进行程序设计过程中较多使用了递归的思想，有效简化了程序设计的编码长度，但对控制条件的设置提高了要求，需要我们有较强的思维分析能力，这样才能合理的设置条件，实现函数功能。在进行题目分析时，实现二叉树的书状输出，首先想到的是利用数组存储各结点对应值，并将其他值赋值为空，然后输出打印数组，即可实现二叉树的树状输出。接下来就是确定各结点对应数组的行列值。经过对二叉树和数组的分析，我们发现，结点所在的层次数与其元素值在数组中的列序相同；对于任一结点与该结点元素值对应数组行序有如下关系：右子树的结点总数与其以上和双亲结点以下的行数相同，左子树的结点总数与其以下和双亲结点以上的行数相同。虽然我们发现了这一关系，但实现起来并不容易。以我们的思维，可以很直观的确定上下边界，以确定元素位置，但计算机很难按人的思维运行，不仅要记录直接双亲结点的位置，还要记录间接双亲结点的位置，加之左、右子树结点的个数，才能确定该结点位置，这无疑是增加了设计的难度，而却容易出错，不易修改，这种设计是不可行的，所以需要另求他途。以上的设计思路不可行了，我们需要需找新的方法解决这个问题。经过分析，我们发现二叉树的逆中序遍历的输出序列与数组按行序序列是一致的，而且不是偶然结果，发现这一规律，我们就能很好的解决问题了。解决了这一问题后，整个功能实现的思想方法就很清晰了：层次遍历确定结点的列标志位，逆中序遍历确定结点的行标志位，据此修改数组，即可实现二叉树的树状输出，实现功能一；为求子树的深度，可利用求树的深度的实现方法，再辅以查找函数确定元素值为X的结点位置，这样以它为根结点的子树深度就可直接用二叉树深度算法实现。至此，整个功能实现方法就完成了。接下来就是程序设计了，明白了整个设计思路，我们会发现，此次功能的实现可以利用基本的简单函数调用来实现。但其中的条件控制，数据修改都是需要注意的。还有的就是思维的转换方面，需要将我们的思维方式用计算机的可实现的方式，防止因两者之间的区别而造成逻辑上的错误。经验与体会经验总结在利用程序设计求解问题实现功能时，我们首先要对问题进行分析，将所要实现的功能分解成若干子功能来实现，这就需要对设计方法不断优化。队以同一问题，解决的方法很多，但寻求一个简单的方法，一个能够用简单的计算机语言语句实现的方法，才是问题的求解方法设计的关键。就像本次课程设计中实现二叉树树状输出时，有很多方法来确定二叉树结点与数组的对应关系，但适合计算机的简单方法才是最好最重要的。体会源程序清单和运行结果源程序清单#include<iostream>#include<malloc.h>usingnamespacestd;#definemax10typedefstructBiTNode{chardata; //结点元素值inth,l; //结点所在行序、列序structBiTNode*lchild,*rchild; //左右孩子指针}*BiTree;intCreateBiTree(BiTree&T){//按先序次序输入二叉树中结点的值(一个字符)，'#'字符表示空树，//构造二叉链表表示的二叉树Tcharc;cin>>c;if(c=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))return-1;T->data=c; //生成根结点CreateBiTree(T->lchild); //构造左子树CreateBiTree(T->rchild); //构造右子树}return1;}intDepth(BiTreeT){ //求二叉树的深度intdepthLeft,depthRight,depthval;if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}BiTreepl二NULL; //记录元素值为输入值x的结点intSearch(BiTreeT,chardata){ //查找元素值为data的结点，并返回其位置if(!pl&&T){if(T->data==data)pl=T;if(Search(T->lchild,data))if(Search(T->rchild,data))returnl;return0;elsereturn1;}#defineMAXQSize100 //最大队列长度structSqQueue{//队列的存储结构BiTree*base;//初始化的动态分配存储空间intfront;//头指针，若队列不空，指向队列头元素intrear;//尾指针，若队列不空，指向尾元素的下一位置};voidInitQueue(SqQueue&Q){ //构建空队列Q.base=newBiTree[MAXQSize];if(!Q.base)cout<<"Error!"; //存储分配失败Q.front=Q.rear=0;}voidEnQueue(SqQueue&Q,BiTreee){ //插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSize==Q.front)cout<<"ERROR";//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSize;}voidDeQueue(SqQueue&Q,BiTree&e){ //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；//否则返回ERRORif(Q.front==Q.rear)cout<<"ERROR";e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSize;}voidLevelOrderTraverse(BiTree&T)

{ //层次遍历二叉树SqQueueQ;{ //层次遍历二叉树SqQueueQ;BiTreeq,p;q=T;InitQueue(Q);if(T){EnQueue(Q,q);q->l=1;}while(Q.front!=Q.rear){DeQueue(Q,q);//构建一个空队列Q//根结点入队列//修改根结点标志位//队列判空//队首元素出队列，并赋值给qif(q->lchild) {EnQueue(Q,q->lchild);p=q->lchild;p->l=q->l+1;} //修改左孩子标志位if(q->rchild) {EnQueue(Q,q->rchild);p=q->rchild;p->l=q->l+1;} //修改右孩子标志位}}inti=1;intMidOrder(BiTree&T){ //递归算法实现逆中序遍历，并修改标志位hif(!T)return1;else{//逆中序遍历右子树//修改根结点标志位//逆中序遍历右子树//修改根结点标志位h//逆中序遍历左子树T->h=i++;MidOrder(T->lchild);return1;}charch[max][max];intPreOrder(BiTreeT){ //先序遍历二叉树，并将元素值赋值给数组对应位置值inta,b;if(T){a=T->h;b=T->l;ch[a-1][b-1]=T->data; //修改数组对应位置值if(PreOrder(T->lchild))if(PreOrder(T->rchild))return1;return0;}elsereturn1;}intm