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

数据结构与算法课程设计报告 课程设计题目： 二叉树平衡的判定 专业班级： 信息与计算科学1001班 一、摘要：基于我们对C语言和数据结构的学习我们有能力编写处理一些比较基本而又简单的问题。在我们此题我们的目标就是任意给出一个二叉树我们判断是否为平衡的二叉树。我们在学习计算机语言类的知识时当然要注重理论知识的学习，但是我们要明确我们学习的是计算机语言，由于课程的性质就决定了我们必须将我们在课本中学到的知识在计算机上运行并且自己能编写一些比较简单的程序，这才是我们学习计算机语言的最终目的而不是满足于理解一个理论会算一个题。因而我们将要抓住这样一个锻炼的机会所谓平衡二叉树，它或者是一颗空树或者是具有下列性质的二叉树：它的左右子树都是平衡二叉树，且左右子树的深度之差得绝对值不超过1。在我们这个判定任意给定的二叉树的题中。我们处理这道题的主要的思路是：首先按先序和中序或者按中序和后序的方式将我们所要判断的二叉树输入进入，目的是要得到一个明确的二叉树的结构准确的判断二叉树是否平衡。在我们判断二叉树的平衡中我们将分别考虑二叉树左右子树的是不是为平衡二叉树，依次得到左右子树的深度，判断左右子树的平衡性。在我们的设计思路中我们将用到不同的树的遍历方式。二、问题重叙：平衡二叉树的判断，设计要求给定一个先序或者后序的遍历结果，判断其是否为二叉树。问题分析：在处理二叉树平衡的判断的问题中。我们需要将分别考虑二叉树的左右子树的平衡问题只要左右子树确定为平衡二叉树，而且左右子树的深度的绝对值之差不大于1，那么我们得到的就是一颗平衡的二叉树。我们将先通过前序和中序或者中序和后序将所要判断的二叉树输入。建立一个明确的二叉树在此基础上判断二叉树是否为平衡二叉树。我们先建立一个二叉树并用前序和中序或者中序和后序遍历的方式将我们输入的树的元素输入得到一个明确的树的结构。三、流程图如下：四、模块分析：1、定义一个结构体存储各节点的信息，并且用递归的方法存储左右子树的信息typedef struct BINTREE{ char chData; struct BINTREE * pbLChild; struct BINTREE * pbRChild;} BinTree, * pBinTree;2、分别得到树的深度以及左右子树的深度int BT_GetTreeDepth( pBinTree pbTree ){ //存储树总的深度 int iDepthTotal = 0; //存储左子树的深度 int iDepthLeft = 0; //存储右子树的深度 int iDepthRight = 0; if ( pbTree == NULL ) { iDepthTotal = 0; } else { // 左孩子的深度 iDepthLeft = BT_GetTreeDepth( pbTree-pbLChild ); // 右孩子的深度 iDepthRight = BT_GetTreeDepth( pbTree-pbRChild ); // 去左右孩子深度的最大值，1代表着根节点 iDepthTotal = 1 + ( iDepthLeft iDepthRight ? iDepthLeft : iDepthRight ); } return iDepthTotal;}3、判断左右子树是不是为平衡二叉树bool BT_IsBalanceTree( pBinTree pbTree ){ //如果树不是空的 if( pbTree != NULL ) { //存储左孩子的深度 int iLeftDepth = 0; //存储右孩子的深度 int iRightDepth = 0; //得到左孩子的深度 iLeftDepth = BT_GetTreeDepth( pbTree-pbLChild ); //得到右孩子的深度 iRightDepth = BT_GetTreeDepth( pbTree-pbRChild ); //判断树是不是平衡二叉树 平衡二叉树的左右孩子的深度绝对值只差不大于 if (( iLeftDepth - iRightDepth = -1 ) ( iLeftDepth - iRightDepth = 1 )) { // 判断左子树是不是平衡的 BT_IsBalanceTree( pbTree-pbLChild ); //判断右子树是不是平衡的 BT_IsBalanceTree( pbTree-pbRChild ); } else { return false; } } else { return false; } return true;}4、输入各节点元素bool BT_PreInToTree( pBinTree pbTree, char *