1、 数据结构与算法数据结构与算法 课程设计课程设计报告报告 课程设计课程设计题目：题目： 二叉树平衡的判定二叉树平衡的判定 专业班级：专业班级： 信息信息与计算科学与计算科学 10100101 班班 一、摘要：一、摘要： 基于我们对 C 语言和数据结构的学习我们有能力编写处理一些比 较基本而又简单的问题。 在我们此题我们的目标就是任意给出一个二 叉树我们判断是否为平衡的二叉树。 我们在学习计算机语言类的知识时当然要注重理论知识的学习， 但是我们要明确我们学习的是计算机语言， 由于课程的性质就决定了 我们必须将我们在课本中学到的知识在计算机上运行并且自己能编 写一些比较简单的程序， 这才是我们学习
2、计算机语言的最终目的而不 是满足于理解一个理论会算一个题。 因而我们将要抓住这样一个锻炼 的机会 所谓平衡二叉树，它或者是一颗空树或者是具有下列性质的二叉 树：它的左右子树都是平衡二叉树， 且左右子树的深度之差得绝对值 不超过 1。 在我们这个判定任意给定的二叉树的题中。我们处理这道题的主 要的思路是： 首先按先序和中序或者按中序和后序的方式将我们所要 判断的二叉树输入进入， 目的是要得到一个明确的二叉树的结构准确 的判断二叉树是否平衡。 在我们判断二叉树的平衡中我们将分别考虑 二叉树左右子树的是不是为平衡二叉树，依次得到左右子树的深度， 判断左右子树的平衡性。 在我们的设计思路中我们将用到不
3、同的树的遍历方式。 二、二、问题重叙问题重叙： 平衡二叉树的判断， 设计要求给定一个先序或者后序的遍历结果， 判断其是否为二叉树。 问题分析： 在处理二叉树平衡的判断的问题中。我们需要将分别考虑二叉树 的左右子树的平衡问题只要左右子树确定为平衡二叉树， 而且左右子 树的深度的绝对值之差不大于 1，那么我们得到的就是一颗平衡的二 叉树。 我们将先通过前序和中序或者中序和后序将所要判断的二叉树 输入。 建立一个明确的二叉树在此基础上判断二叉树是否为平衡二叉 树。 我们先建立一个二叉树并用前序和中序或者中序和后序遍历的方 式将我们输入的树的元素输入得到一个明确的树的结构。 三、流程图如下：三、流程图
4、如下： 四、模块分析：四、模块分析： 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
