数据结构课程设计二叉树平衡的判定由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“课程设计平衡二叉树”。
数据结构与算法 课程设计报告
课程设计题目： 二叉树平衡的判定
专业班级： 信息与计算科学1001班 姓 名： 谢炜 学 号：100701114 设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 杜洪波 成 绩：
一、摘要：
基于我们对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((iLeftDepthiRightDepth
{
// 判断左子树是不是平衡的 BT_IsBalanceTree(pbTree->pbLChild);
//判断右子树是不是平衡的 BT_IsBalanceTree(pbTree->pbRChild);
}
else
{
return false;
} } else {
return false;}
return true;}
4、输入各节点元素
bool BT_PreInToTree(pBinTree & pbTree, char * szInOrder, char * szPreOrder, int iInLeft, int iInRight, int iPreLeft, int iPreRight)
BT_PreInToTree(pbTree->pbLChild, szInOrder, szPreOrder, iInLeft, iCurPosiRightDepth >=-1)&&(iLeftDepthiInLeft;// If current position is greater than left, generate left child if(iCurPos > iInLeft){ BT_PreInToTree(pbTree->pbLChild, szInOrder, szPreOrder, iInLeft, iCurPosiInLeft;// If the current position is greater than the left border, generate the left child if(iCurPos > iInLeft){
BT_InPostToTree(pbTree->pbLChild, szInOrder, szPostOrder, iInLeft, iCurPos1);}
// If the current position is le than the right border, generate the right child if(iCurPos
BT_InPostToTree(pbTree->pbRChild, szInOrder, szPostOrder, iCurPos + 1, iInRight, iPostLeft + iLengthLeft, iPostRight-1);} return true;} void BT_PreOrder(pBinTree pbTree){ if(pbTree!= NULL){
// The preorder traversal is, root, left child, right child
printf(“%c ”, pbTree->chData);
BT_PreOrder(pbTree->pbLChild);
BT_PreOrder(pbTree->pbRChild);} } void BT_PostOrder(pBinTree pbTree){
if(pbTree!= NULL){
// The postorder traversal is, left child, right child, root
BT_PostOrder(pbTree->pbLChild);
BT_PostOrder(pbTree->pbRChild);
printf(“%c ”, pbTree->chData);} } void main(){ char szPre [100] = “”;char szMid [100] = “”;char szPost [100] = “”;pBinTree pbPreInTree;pBinTree pbPostInTree;int
iMode = 0;printf(“请选择生成二叉树规则：前序和中序(0)，后序和中序(1)n”);scanf(“%d”,&iMode);switch(iMode){ case 0:
{
printf(“请输入前序序列:n”);
scanf(“%s”,&szPre);printf(“请输入中序序列:n”);
scanf(“%s”,&szMid);bool bCorrect = BT_PreInToTree(pbPreInTree, szMid, szPre, 0, strlen(szMid)-1, 0, strlen(szPre)-1);
if(bCorrect)
{printf(“该树的后序序列为：n”);
BT_PostOrder(pbPreInTree);
if(BT_IsBalanceTree(pbPreInTree))
{printf(“该树是平衡二叉树”);
}
else
{printf(“这个不是平衡二叉树”);
}
}
else
{printf(“不要乱输，前序与中序不匹配”);} }
break;case 1:
{printf(“请输入中序序列:n”);scanf(“%s”,&szMid);printf(“请输入后序序列:n”);scanf(“%s”,&szPost);bool bCorrect = BT_InPostToTree(pbPostInTree, szMid, szPost, 0, strlen(szMid)-1, 0, strlen(szPost)-1);
if(bCorrect)
{printf(“该树的前序序列为：n”);BT_PreOrder(pbPostInTree);
if(BT_IsBalanceTree(pbPostInTree))
{printf(“该树是平衡二叉树”);
}
else
{printf(“这个不是平衡二叉树”);
}
}
else
{printf(“不要乱输，中序与后序不匹配”);
} }
break;default:
{printf(“不要乱选，不支持其他模式”);
} } }
课 程 设 计 报 告课程名称 数据结构课程设计 题 目平衡二叉树操作 指导教师 设计起止日 2010-5-16 学 院 计算机学院 专 业软件工程 学生姓名 班级/学号------------......
课 程 设 计 报 告一． 需求分析1、建立平衡二叉树并进行创建、增加、删除、调平等操作。2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入......
平衡二叉树操作的演示1.需求分析本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。 具体功能：（1） 初始，平衡二叉树为空树，操作界面给出创建、查找、插入......
数据结构实验报告二题目：用先序递归过程监理二叉树（存储结构：二叉链表）输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为：并......
数据结构课程设计报告 题目名称： 二叉树的应用问题 专业班级： 计算机科学与技术学生姓名：学生学号：指导教师：目录一、题目要求 ....................................................
