二叉树平衡的判定.docx
《二叉树平衡的判定.docx》由会员分享，可在线阅读，更多相关《二叉树平衡的判定.docx（19页珍藏版）》请在冰点文库上搜索。
二叉树平衡的判定
数据结构与算法
课程设计报告
课程设计题目：
二叉树平衡的判定
专业班级：
信息与计算科学1001班
姓名：
郑伦学号：
100701214
设计室号：
理学院机房
设计时间：
2011-12-26批阅时间：
指导教师：
杜洪波成绩：
问题：
平衡二叉树的判断，设计要求给定一个先序或者后序的遍历结果，判断其是否为二叉树。
问题分析：
在处理二叉树平衡的判断的问题中。
我们需要将分别考虑二叉树的左右子树的平衡问题只要左右子树确定为平衡二叉树，而且左右子树的深度的绝对值之差不大于1，那么我们得到的就是一颗平衡的二叉树。
我们将先通过前序和中序或者中序和后序将所要判断的二叉树输入。
建立一个明确的二叉树在此基础上判断二叉树是否为平衡二叉树。
我们先建立一个二叉树并用前序和中序或者中序和后序遍历的方式将我们输入的树的元素
流程图如下：
模块分析：
1、定义一个结构体存储各节点的信息，并且用递归的方法存储左右子树的信息
typedefstructBINTREE
{
charchData;
structBINTREE*pbLChild;
structBINTREE*pbRChild;
}BinTree,*pBinTree;
2、分别得到树的深度以及左右子树的深度
intBT_GetTreeDepth（pBinTreepbTree）
{
//存储树总的深度
intiDepthTotal=0;
//存储左子树的深度
intiDepthLeft=0;
//存储右子树的深度
intiDepthRight=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、判断左右子树是不是为平衡二叉树
boolBT_IsBalanceTree（pBinTreepbTree）
{
//如果树不是空的
if（pbTree!
=NULL）
{
//存储左孩子的深度
intiLeftDepth=0;
//存储右孩子的深度
intiRightDepth=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
{
returnfalse;
}
}
else
{
returnfalse;
}
returntrue;
}
4、输入各节点元素
boolBT_PreInToTree（pBinTree&pbTree,char*szInOrder,char*szPreOrder,intiInLeft,intiInRight,intiPreLeft,intiPreRight）
BT_PreInToTree（pbTree->pbLChild,szInOrder,szPreOrder,iInLeft,iCurPos-1,iPreLeft+1,iPreLeft+iLegnthLeft）;
5、前序遍历二叉树
voidBT_PreOrder（pBinTreepbTree）
{
if（pbTree!
=NULL）
{
//Thepreordertraversalis,root,leftchild,rightchild
printf（"%c",pbTree->chData）;
BT_PreOrder（pbTree->pbLChild）;
BT_PreOrder（pbTree->pbRChild）;
}
}
6、后序遍历二叉树
voidBT_PostOrder（pBinTreepbTree）
{
if（pbTree!
=NULL）
{
//Thepostordertraversalis,leftchild,rightchild,root
BT_PostOrder（pbTree->pbLChild）;
BT_PostOrder（pbTree->pbRChild）;
printf（"%c",pbTree->chData）;
}
}
7、主函数
voidmain（）
{
charszPre[100]="";
charszMid[100]="";
charszPost[100]="";
pBinTreepbPreInTree;
pBinTreepbPostInTree;
（1）选用前序和后序的输出方式，并判断是不是平衡二叉树
printf（"请输入前序序列:
\n"）;
scanf（"%s",&szPre）;
printf（"请输入中序序列:
\n"）;
scanf（"%s",&szMid）;
boolbCorrect=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;
（2）选用中序和后序输入方式，并判断是不是平衡二叉树
{printf（"请输入中序序列:
\n"）;
scanf（"%s",&szMid）;
printf（"请输入后序序列:
\n"）;
scanf（"%s",&szPost）;
boolbCorrect=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（"不要乱选，不支持其他模式"）;
}
}
}
算法实现效果图：
1、选用输入方式：
2、中序
3、后序输入
4、得到结果
5、输入的中序和后序不匹配
6、得到正确的结果
总结：
在此次课程设计过程中我们成功的利用树的遍历以及二叉树成立的条件判断了随意的二叉树是为平衡二叉树。
其实在于计算机语言这类课程看重的就是上机的实际操作，不满足于基本理论的学习。
上机操作才能让我们更加好的掌握我们所要学习的计算机语言知识。
我们在解决我们问题的过程中通过前序和中序或者中序和后序的方式将树输入，再将其以后序或者前序的方式将其输出。
在判断是不是为平衡二叉树时我们分别检索左右子树的深度判断左右子树是不是平衡二叉树，并且比较左右子树的深度，看看它们之间的绝对值之差是不是小于1的。
最终得到我们所输入的二叉树是不是平衡二叉树。
在我们输入的过程中为了得到正确的结构，我们所输入的前序和中序必须是匹配的或者中序和后序是匹配的，只有这样才能得到一个明确的树的结构。
只顾学习理论是远远不够的。
实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。
此外，也让我更加明白编程是要解决现实问题的。
只有拥有把现实问题理论化的能力，才是编程真正需要达到的境界。
源程序如下：
#include
#include
#include
typedefstructBINTREE
{
charchData;
structBINTREE*pbLChild;
structBINTREE*pbRChild;
}BinTree,*pBinTree;
intBT_GetTreeDepth（pBinTreepbTree）
{
//存储树总的深度
intiDepthTotal=0;
//存储左子树的深度
intiDepthLeft=0;
//存储右子树的深度
intiDepthRight=0;
if（pbTree==NULL）
{
iDepthTotal=0;
}
else
{
//Depthofleftchild左孩子的深度
iDepthLeft=BT_GetTreeDepth（pbTree->pbLChild）;
//Depthofrightchild右孩子的深度
iDepthRight=BT_GetTreeDepth（pbTree->pbRChild）;
//Getthemaxdepthofleftandrightchild,1meansrootnode去左右孩子深度的最大值，1代表着根节点
iDepthTotal=1+（iDepthLeft>iDepthRight?
iDepthLeft:
iDepthRight）;
}
returniDepthTotal;
}
boolBT_IsBalanceTree（pBinTreepbTree）
{
//Iftreeisnotempty如果树不是空的
if（pbTree!
=NULL）
{
//Storetheleftchilddepth存储左孩子的深度
intiLeftDepth=0;
//Storetherightchilddepth存储右孩子的深度
intiRightDepth=0;
//Gettheleftchilddepth得到左孩子的深度
iLeftDepth=BT_GetTreeDepth（pbTree->pbLChild）;
//Gettherightchilddepth得到右孩子的深度
iRightDepth=BT_GetTreeDepth（pbTree->pbRChild）;
//Judgethetreeisbalancetreeornot判断树是不是平衡二叉树平衡二叉树的左右孩子的深度绝对值只差不大于1
//Thebalancetreeistheabstractofleftchilddepthreducerightchilddepthisequalorlessthan1
if（（iLeftDepth-iRightDepth>=-1）&&（iLeftDepth-iRightDepth<=1））
{
//Judgetheleftchildisbalancetoo判断左子树是不是平衡的
BT_IsBalanceTree（pbTree->pbLChild）;
//Judgetherightchildisbalancetoo判断右子树是不是平衡的
BT_IsBalanceTree（pbTree->pbRChild）;
}
else
{
returnfalse;
}
}
else
{
returnfalse;
}
returntrue;
}
boolBT_PreInToTree（pBinTree&pbTree,char*szInOrder,char*szPreOrder,intiInLeft,intiInRight,intiPreLeft,intiPreRight）
{
//Createnode创建一个节点
pbTree=newBinTree;
pbTree->chData=szPreOrder[iPreLeft];
pbTree->pbLChild=pbTree->pbRChild=NULL;
//Storecurrentposition
intiCurPos=iInLeft;
//Findthenodethesameaspreorder找到先前已经访问的节点
while（（iCurPos<=iInRight）&&（szInOrder[iCurPos]!
=szPreOrder[iPreLeft]））
{
iCurPos++;
}
//Ifthecurrentpositionisgreaterthantherightborder,returnfalse
if（iCurPos>iInRight）
{
returnfalse;
}
intiLegnthLeft=iCurPos-iInLeft;
//Ifcurrentpositionisgreaterthanleft,generateleftchild
if（iCurPos>iInLeft）
{
BT_PreInToTree（pbTree->pbLChild,szInOrder,szPreOrder,iInLeft,iCurPos-1,iPreLeft+1,iPreLeft+iLegnthLeft）;
}
//ifcurrentpositionislessthanright,generaterightchild
if（iCurPos{
BT_PreInToTree（pbTree->pbRChild,szInOrder,szPreOrder,iCurPos+1,iInRight,iPreLeft+iLegnthLeft+1,iPreRight）;
}
returntrue;
}
boolBT_InPostToTree（pBinTree&pbTree,char*szInOrder,char*szPostOrder,intiInLeft,intiInRight,intiPostLeft,intiPostRight）
{
//Createnode
pbTree=newBinTree;
pbTree->chData=szPostOrder[iPostRight];
pbTree->pbLChild=pbTree->pbRChild=NULL;
//Storecurrentposition
intiCurPos=iInLeft;
//Findthenodethesameaspostorder
while（iCurPos<=iInRight&&szInOrder[iCurPos]!
=szPostOrder[iPostRight]）
{
iCurPos++;
}
//Ifthecurrentpositionisgreaterthantherightborder,returnfalse
if（iCurPos>iInRight）
{
returnfalse;
}
intiLengthLeft=iCurPos-iInLeft;
//Ifthecurrentpositionisgreaterthantheleftborder,generatetheleftchild
if（iCurPos>iInLeft）
{
BT_InPostToTree（pbTree->pbLChild,szInOrder,szPostOrder,iInLeft,iCurPos-1,iPostLeft,iPostLeft+iLengthLeft-1）;
}
//Ifthecurrentpositionislessthantherightborder,generatetherightchild
if（iCurPos{
BT_InPostToTree（pbTree->pbRChild,szInOrder,szPostOrder,iCurPos+1,iInRight,iPostLeft+iLengthLeft,iPostRight-1）;
}
returntrue;
}
voidBT_PreOrder（pBinTreepbTree）
{
if（pbTree!
=NULL）
{
//Thepreordertraversalis,root,leftchild,rightchild
printf（"%c",pbTree->chData）;
BT_PreOrder（pbTree->pbLChild）;
BT_PreOrder（pbTree->pbRChild）;
}
}
voidBT_PostOrder（pBinTreepbTree）
{
if（pbTree!
=NULL）
{
//Thepostordertraversalis,leftchild,rightchild,root
BT_PostOrder（pbTree->pbLChild）;
BT_PostOrder（pbTree->pbRChild）;
printf（"%c",pbTree->chData）;
}
}
voidmain（）
{
charszPre[100]="";
charszMid[100]="";
charszPost[100]="";
pBinTreepbPreInTree;
pBinTreepbPostInTree;
intiMode=0;
printf（"请选择生成二叉树规则：
前序和中序（0），后序和中序
（1）\n"）;
scanf（"%d",&iMode）;
switch（iMode）
{
case0:
{
printf（"请输入前序序列:
\n"）;
scanf（"%s",&szPre）;
printf（"请输入中序序列:
\n"）;
scanf（"%s",&szMid）;
boolbCorrect=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;
case1:
{printf（"请输入中序序列:
\n"）;
scanf（"%s",&szMid）;
printf（"请输入后序序列:
\n"）;
scanf（"%s",&szPost）;
boolbCorrect=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（"不要乱选，不支持其他模式"）;
}
}
}
升级会员 