数据结构课程设计----二叉树平衡的判定

《数据结构课程设计----二叉树平衡的判定》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法课程设计报告课程设计题目：二叉树平衡的判定专业班级：信息与计算科学1001班一、摘要：基于我们对C语言和数据结构的学习我们有能力编写处理一些比较基本而又简单的问题。在我们此题我们的目标就是任意给出一个二叉树我们判断是否为平衡的二叉树。我们在学习计算机语言类的知识时当然要注重理论知识的学习，但是我们要明确我们学习的是计算机语言，由于课程的性质就决定了我们必须将我们在课本中学到的知识在计算机上运行并且自己能编写一些比较简单的程序，这才是我们学习计算机语言的最终目的而不是满足于理解一个理论会算一个题。因而我们将

2、要抓住这样一个锻炼的机会所谓平衡二叉树，它或者是一颗空树或者是具有下列性质的二叉树：它的左右子树都是平衡二叉树，且左右子树的深度之差得绝对值不超过1。在我们这个判定任意给定的二叉树的题中。我们处理这道题的主要的思路是：首先按先序和中序或者按中序和后序的方式将我们所要判断的二叉树输入进入，目的是要得到一个明确的二叉树的结构准确的判断二叉树是否平衡。在我们判断二叉树的平衡中我们将分别考虑二叉树左右子树的是不是为平衡二叉树，依次得到左右子树的深度，判断左右子树的平衡性。在我们的设计思路中我们将用到不同的树的遍历方式。二、问题

3、重叙：平衡二叉树的判断，设计要求给定一个先序或者后序的遍历结果，判断其是否为二叉树。问题分析：在处理二叉树平衡的判断的问题中。我们需要将分别考虑二叉树的左右子树的平衡问题只要左右子树确定为平衡二叉树，而且左右子树的深度的绝对值之差不大于1，那么我们得到的就是一颗平衡的二叉树。我们将先通过前序和中序或者中序和后序将所要判断的二叉树输入。建立一个明确的二叉树在此基础上判断二叉树是否为平衡二叉树。我们先建立一个二叉树并用前序和中序或者中序和后序遍历的方式将我们输入的树的元素输入得到一个明确的树的结构。三、流程图如下：四、模块

4、分析：1、定义一个结构体存储各节点的信息，并且用递归的方法存储左右子树的信息typedefstructBINTREE{charchData;structBINTREE*pbLChild;structBINTREE*pbRChild;}BinTree,*pBinTree;2、分别得到树的深度以及左右子树的深度intBT_GetTreeDepth(pBinTreepbTree){//存储树总的深度intiDepthTotal=0;//存储左子树的深度intiDepthLeft=0;//存储右子树的深度intiDepthRi

5、ght=0;if(pbTree==NULL){iDepthTotal=0;}else{//左孩子的深度iDepthLeft=BT_GetTreeDepth(pbTree->pbLChild);//右孩子的深度iDepthRight=BT_GetTreeDepth(pbTree->pbRChild);//去左右孩子深度的最大值，1代表着根节点iDepthTotal=1+(iDepthLeft>iDepthRight?iDepthLeft:iDepthRight);}returniDepthTotal;}3、判断左右子树是

6、不是为平衡二叉树boolBT_IsBalanceTree(pBinTreepbTree){//如果树不是空的if(pbTree!=NULL){//存储左孩子的深度intiLeftDepth=0;//存储右孩子的深度intiRightDepth=0;//得到左孩子的深度iLeftDepth=BT_GetTreeDepth(pbTree->pbLChild);//得到右孩子的深度iRightDepth=BT_GetTreeDepth(pbTree->pbRChild);//判断树是不是平衡二叉树平衡二叉树的左右孩子的深度绝

7、对值只差不大于if((iLeftDepth-iRightDepth>=-1)&&(iLeftDepth-iRightDepth<=1)){//判断左子树是不是平衡的BT_IsBalanceTree(pbTree->pbLChild);//判断右子树是不是平衡的BT_IsBalanceTree(pbTree->pbRChild);}else{returnfalse;}}else{returnfalse;}returntrue;}4、输入各节点元素boolBT_PreInToTree(pBinTree&pbTree,cha

8、r*szInOrder,char*szPreOrder,intiInLeft,intiInRight,intiPreLeft,intiPreRight)BT_PreInToTree(pbTree->pbLChild,szInOrder,szPreOrder,iInLeft,iCurPos-1,iPreLeft+1,iPreLeft