第一篇：数据结构课程设计二叉树平衡的判定
数据结构与算法 课程设计报告
课程设计题目： 二叉树平衡的判定
专业班级： 信息与计算科学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 <= 1))
{
// 判断左子树是不是平衡的
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 less than the right border, generate the right child if(iCurPos < iInRight){
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(”不要乱选，不支持其他模式");
} } }
第二篇：数据结构课程设计-_平衡二叉树操作 - 副本
课 程 设 计 报 告
一． 需求分析
1、建立平衡二叉树并进行创建、增加、删除、调平等操作。
2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。
3、测试数据：自选数据
二． 概要设计
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
三． 详细设计
树的内部变量
— 1 — typedef struct BTNode {
int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子
}BTNode,*BTree;调平二叉树(左右调平方式大体雷同，之具体写出其中一种调平方式)if(插入元素与当前根元素相等){ printf(“已存在相同关键字的结点n”);} if(插入元素小于当前根元素)){ if(插入新结点不成功)
return 0;if(插入成功)
switch(查看根的平衡因子)
{
case +1:
进行左平衡处理;
{
检查*T的左子树的平衡度，并作相应平衡处理
{
case +1:
令根及其左孩子的平衡因子为0;
做右平衡处理;
{
BTree lc;
lc指向的结点左子树根结点;
rc的右子树挂接为结点的左子树;
lc的右孩子为原结点;
原结点指向新的结点lc;
}
break;
case-1:
rd指向*T的左孩子的右子树根
switch(查看右孩子平衡因子)
{
case +1:
根的平衡因子为-1;
根左孩子的平衡因子为0;
break;
case 0:
令根和根左孩子的平衡因子为0;— 2 —
}
}
}
}
break;根平衡因子为0;根左孩子平衡因子为1;break;
case-1:
根右孩子的平衡因子为0;对*T的左子树作左旋平衡处理;对*T作右旋平衡处理;break;令根的平衡因子为+1;break;令根的平衡因子为-1;break;case 0:
case-1:
四．调试分析
在进行对插入新结点并调平时由于利用的是普通的插入方法进行LL、LR、RL、RR型的转换，使得在调试时经常没有更改内部变量的值，导致编译出错。
对于在空树情况下删除结点的考虑，是在后期的调试检验过程中发现的。在没有更改代码前，如果按此操作，程序就会崩溃。原因就是在删除函数中虽然考虑到了空树的情况，但是在输出树的函数中没有加入空树的考虑而只是在创建树函数中加入了if…else…的判断。经过反复的检查，发现可以直接在输出函数中加入判断而不必再其他位置判断，并且调试成功。
五．使用说明和测试结果
测试数据：
创建二叉树
增加二叉树
直接创建平衡二叉树
— 4 —平衡二叉树加入新节点并调平
删除结点
六．心得体会
了解了建立树的方法；
学会了利用二分法建立树结构。、； 学习到了二叉树的调平方法；
学会了向一个已知树插入或删除结点的方法。
— 6 —
第三篇：数据结构课程设计-平衡二叉树操作
课 程 设 计 报 告
课程名称 数据结构课程设计 题 目平衡二叉树操作 指导教师 设计起止日 2010-5-16 学 院 计算机学院 专 业
软件工程 学生姓名
班级/学号------------成 绩 _________________
一． 需求分析
1、建立平衡二叉树并进行创建、增加、删除、调平等操作。
2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。
3、测试数据：自选数据
二． 概要设计
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
三． 详细设计
树的内部变量
typedef struct BTNode { — 2 —
int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子
}BTNode,*BTree;调平二叉树(左右调平方式大体雷同，之具体写出其中一种调平方式)if(插入元素与当前根元素相等){ printf(“已存在相同关键字的结点n”);} if(插入元素小于当前根元素)){ if(插入新结点不成功)
return 0;if(插入成功)
switch(查看根的平衡因子)
{
case +1:
进行左平衡处理;
{
检查*T的左子树的平衡度，并作相应平衡处理
{
case +1:
令根及其左孩子的平衡因子为0;
做右平衡处理;
{
BTree lc;
lc指向的结点左子树根结点;
rc的右子树挂接为结点的左子树;
lc的右孩子为原结点;
原结点指向新的结点lc;
}
break;
case-1:
rd指向*T的左孩子的右子树根
switch(查看右孩子平衡因子)
{
case +1:
根的平衡因子为-1;
根左孩子的平衡因子为0;
break;
case 0:
令根和根左孩子的平衡因子为0;
break;
case-1:
}
}
}
}
根平衡因子为0;根左孩子平衡因子为1;break;
根右孩子的平衡因子为0;对*T的左子树作左旋平衡处理;对*T作右旋平衡处理;break;令根的平衡因子为+1;break;令根的平衡因子为-1;break;case 0:
case-1:
四．调试分析
在进行对插入新结点并调平时由于利用的是普通的插入方法进行LL、LR、RL、RR型的转换，使得在调试时经常没有更改内部变量的值，导致编译出错。
对于在空树情况下删除结点的考虑，是在后期的调试检验过程中发现的。在没有更改代码前，如果按此操作，程序就会崩溃。原因就是在删除函数中虽然考虑到了空树的情况，但是在输出树的函数中没有加入空树的考虑而只是在创建树函数中加入了if…else…的判断。经过反复的检查，发现可以直接在输出函数中加入判断而不必再其他位置判断，并且调试成功。
五．使用说明和测试结果
测试数据：
创建二叉树
— 4 —
增加二叉树
直接创建平衡二叉树
平衡二叉树加入新节点并调平
删除结点
— 6 —
六．心得体会
了解了建立树的方法；
学会了利用二分法建立树结构。、； 学习到了二叉树的调平方法；
学会了向一个已知树插入或删除结点的方法。七．附录 源代码
#include “stdafx.h” #include
}BTNode,*BTree;
/*需要的函数声明*/ void Right_Balance(BTree &p);void Left_Balance(BTree &p);void Left_Root_Balance(BTree &T);void Right_Root_Balance(BTree &T);bool InsertAVL(BTree &T,int i,bool &taller);void PrintBT(BTree T,int m);void CreatBT(BTree &T);void Left_Root_Balance_det(BTree &p,int &shorter);void Right_Root_Balance_det(BTree &p,int &shorter);void Delete(BTree q,BTree &r,int &shorter);int DeleteAVL(BTree &p,int x,int &shorter);void Adj_balance(BTree &T);bool SetAVL(BTree &T,int i,bool &taller);bool Insert_Balance_AVL(BTree &T,int i,bool &taller);/*主函数*/ void main(){
int input,search,m;bool taller=false;int shorter=0;BTree T;T=(BTree)malloc(sizeof(BTNode));T=NULL;while(1){
printf(“n请选择需要的二叉树操作n”);printf(“1.创建二叉树2.增加新结点3.直接创建平衡二叉树4.在平衡二叉树上增加新结点并调平衡5.scanf(”%d“,&input);getchar();switch(input){ case 1:
CreatBT(T);break;printf(”请输入你要增加的关键字“);scanf(”%d“,&search);getchar();InsertAVL(T,search,taller);m = 0;PrintBT(T,m);break;Adj_balance(T);删除0.退出n”);case 2: case 3: — 8 —
break;
case 4:
printf(“请输入你要增加的关键字”);
scanf(“%d”,&search);
getchar();
SetAVL(T,search,taller);
m = 0;
PrintBT(T,m);
break;
case 5:
printf(“请输入你要删除的关键字”);
scanf(“%d”,&search);
getchar();
DeleteAVL(T,search,shorter);
m=0;
PrintBT(T,m);
break;
case 0:
break;
default:
printf(“输入错误，请重新选择。”);
break;
}
if(input == 0)
break;
printf(“按任意键继续.”);
getchar();} } /*对以*p为根的二叉排序树作右旋处理*/ void Right_Balance(BTree &p){ BTree lc;lc = p->lchild;//lc指向的*p左子树根结点
p->lchild = lc->rchild;//rc的右子树挂接为*p的左子树 lc->rchild = p;p = lc;//p指向新的结点
} /*对以*p为根的二叉排序树作左旋处理*/ void Left_Balance(BTree &p){ BTree rc;rc = p->rchild;//指向的*p右子树根结点
p->rchild = rc->lchild;//rc左子树挂接到*p的右子树
rc->lchild = p;p = rc;//p指向新的结点
— 9 — } /*对以指针T所指结点为根的二叉树作左平衡旋转处理*/ void Left_Root_Balance(BTree &T){
} /*对以指针T所指结点为根的二叉树作右平衡旋转处理*/ void Right_Root_Balance(BTree &T){
BTree rc,ld;rc = T->rchild;//指向*T的左子树根结点
switch(rc->bf)//检查*T的右子树的平衡度，并作相应平衡处理 { case RH: //新结点插入在*T的右孩子的右子树上，要作单左旋处理
T->bf = rc->bf =EH;Left_Balance(T);break;ld = rc->lchild;//ld指向*T的右孩子的左子树根 switch(ld->bf)//修改*T及其右孩子的平衡因子 BTree lc,rd;lc = T->lchild;//指向*T的左子树根结点
switch(lc->bf)//检查*T的左子树的平衡度，并作相应平衡处理 { case LH: //新结点插入在*T的左孩子的左子树上，要作单右旋处理
} T->bf = lc->bf = EH;Right_Balance(T);break;rd = lc->rchild;//rd指向*T的左孩子的右子树根 switch(rd->bf)//修改*T及其左孩子的平衡因子 { case LH:
} rd->bf = EH;Left_Balance(T->lchild);//对*T的左子树作左旋平衡处理 Right_Balance(T);//对*T作右旋平衡处理 T->bf = RH;lc->bf = EH;break;T->bf = lc->bf = EH;break;T->bf = EH;lc->bf = LH;break;case RH: //新结点插入在*T的左孩子的右子树上，要作双旋处理
case EH: case RH: case LH: //新结点插入在*T的右孩子的左子树上，要作双旋处理
— 10 —
}
} { case LH:
} ld->bf = EH;Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理 Left_Balance(T);//对*T作左旋平衡处理 T->bf = EH;rc->bf = RH;break;T->bf = rc->bf =EH;break;T->bf = LH;rc->bf = EH;break;case EH: case RH: /*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/ bool InsertAVL(BTree &T,int i,bool &taller){
if(!T)//插入新结点，树“长高”，置taller为true {
} else {
if(EQ(i,T->data))//树中已存在和有相同关键字的结点 {
} if(LT(i,T->data))//应继续在*T的左子树中进行搜索 taller = false;printf(“已存在相同关键字的结点n”);return 0;T =(BTree)malloc(sizeof(BTNode));T->data = i;T->lchild = T->rchild =NULL;T->bf = EH;taller = true;{ if(!InsertAVL(T->lchild,i,taller))return 0;} else //应继续在*T的右子树中进行搜索 { if(!InsertAVL(T->rchild,i,taller))return 0;
— 11 — } } return 1;} /*按树状打印输出二叉树的元素,m表示结点所在层次*/ void PrintBT(BTree T,int m){
} /*创建二叉树，以输入-32767为建立的结束*/ void CreatBT(BTree &T){
} int m;int i;bool taller=false;T = NULL;printf(“n请输入关键字(以-32767结束建立二叉树):”);scanf(“%i”,&i);getchar();while(i!=-32767){
} m=0;printf(“您创建的二叉树为：n”);PrintBT(T,m);InsertAVL(T,i,taller);printf(“n请输入关键字(以-32767结束建立二叉树):”);scanf(“%i”,&i);getchar();taller=false;if(T){
} else {
} printf(“这是一棵空树！n”);getchar();int i;if(T->rchild)PrintBT(T->rchild,m+1);printf(“ ”);//打印i 个空格以表示出层次 for(i = 1;i<=m;i++)printf(“%dn”,T->data);//打印T 元素,换行 if(T->lchild)PrintBT(T->lchild,m+1);— 12 — /*删除结点时左平衡旋转处理*/ void Left_Root_Balance_det(BTree &p,int &shorter){
BTree p1,p2;if(p->bf==1)//p结点的左子树高，删除结点后p的bf减,树变矮 {
} else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 {
} else //p结点的右子树高 {
p1=p->rchild;//p1指向p的右子树
if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变 {
} else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮 {
} else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 {
p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0){
} else if(p2->bf==-1){ p->bf=1;p1->bf=0;p->bf=0;p1->bf=0;Left_Balance(p);p1->bf=p->bf=0;shorter=1;Left_Balance(p);p1->bf=1;p->bf=-1;shorter=0;p->bf=-1;shorter=0;p->bf=0;shorter=1;
}
}
} } else {
} p2->bf=0;p=p2;shorter=1;p->bf=0;p1->bf=-1;/*删除结点时右平衡旋转处理*/ void Right_Root_Balance_det(BTree &p,int &shorter){
BTree p1,p2;if(p->bf==-1){
} else if(p->bf==0){
} else {
p1=p->lchild;if(p1->bf==0){
} else if(p1->bf==1){
} else { p2=p1->rchild;Right_Balance(p);p1->bf=p->bf=0;shorter=1;Right_Balance(p);p1->bf=-1;p->bf=1;shorter=0;p->bf=1;shorter=0;p->bf=0;shorter=1;— 14 —
p1->rchild=p2->lchild;
p2->lchild=p1;
p->lchild=p2->rchild;
p2->rchild=p;
if(p2->bf==0)
{
p->bf=0;
p1->bf=0;
}
else if(p2->bf==1)
{
p->bf=-1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
} } } /*删除结点*/ void Delete(BTree q,BTree &r,int &shorter){ if(r->rchild==NULL){
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;} else {
Delete(q,r->rchild,shorter);
if(shorter==1)
Right_Root_Balance_det(r,shorter);} } /*二叉树的删除操作*/ int DeleteAVL(BTree &p,int x,int &shorter){
} int k;BTree q;if(p==NULL){
} else if(x
data)//在p的左子树中进行删除 {
} else if(x>p->data)//在p的右子树中进行删除 {
} else {
} q=p;if(p->rchild==NULL)//右子树空则只需重接它的左子树 {
} else if(p->lchild==NULL)//左子树空则只需重接它的右子树 {
} else//左右子树均不空 {
} return 1;Delete(q,q->lchild,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);p=q;p=p->rchild;free(q);shorter=1;p=p->lchild;free(q);shorter=1;k=DeleteAVL(p->rchild,x,shorter);if(shorter==1)Right_Root_Balance_det(p,shorter);return k;k=DeleteAVL(p->lchild,x,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);return k;printf(“不存在要删除的关键字！n”);return 0;— 16 — /*二叉树调平操作*/ void Adj_balance(BTree &T){ int m;int i;bool taller=false;T = NULL;printf(“n请输入关键字(以-32767结束建立平衡二叉树):”);scanf(“%d”,&i);getchar();while(i!=-32767){
SetAVL(T,i,taller);
printf(“n请输入关键字(以-32767结束建立平衡二叉树):”);
scanf(“%d”,&i);
getchar();
taller=false;} m=0;printf(“平衡二叉树创建结束.n”);if(T)
PrintBT(T,m);else
printf(“这是一棵空树.n”);} /*调平二叉树具体方法*/ bool SetAVL(BTree &T,int i,bool &taller){ if(!T)//插入新结点，树“长高”，置taller为true {
T =(BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = EH;
taller = true;} else {
if(EQ(i,T->data))//树中已存在和有相同关键字的结点
{
taller = false;
printf(“已存在相同关键字的结点n”);
return 0;
}
if(LT(i,T->data))//应继续在*T的左子树中进行搜索 {
}
}
} if(!SetAVL(T->lchild,i,taller))
{
} case LH: //原本左子树比右子树高，需要作左平衡处理
Left_Root_Balance(T);taller = false;break;T->bf = LH;taller = true;break;T->bf = EH;taller = false;break;return 0;switch(T->bf)//检查*T的平衡度 if(taller)//已插入到*T的左子树中且左子树“长高”
case EH: //原本左子树、右子等高，现因左子树增高而使树增高
case RH: //原本右子树比左子树高，现左、右子树等高
else //应继续在*T的右子树中进行搜索 {
} return 1;if(!SetAVL(T->rchild,i,taller))
{
} case LH: //原本左子树比右子树高，现左、右子树等高
T->bf = EH;taller = false;break;T->bf = RH;taller = true;break;Right_Root_Balance(T);taller = false;break;return 0;switch(T->bf)//检查*T的平衡度 if(taller)//已插入到*T的右子树中且右子树“长高”
case EH: //原本左子树、右子等高，现因右子树增高而使树增高
case RH: //原本右子树比左子树高，需要作右平衡处理
— 18 —
第四篇：数据结构平衡二叉树的操作演示
平衡二叉树操作的演示
1.需求分析
本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。具体功能：
（1）初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。
（2）平衡二叉树的显示采用凹入表现形式。（3）合并两棵平衡二叉树。
（4）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。
如下图：
2．概要设计
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤：
（1）每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点；
（2）若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
（3）判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；（4）如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
（5）计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。流程图
3.详细设计
二叉树类型定义： typedefint Status;typedefintElemType;typedefstructBSTNode{
ElemType data;
int bf;
structBSTNode *lchild ,*rchild;} BSTNode,* BSTree;
Status SearchBST(BSTreeT,ElemType e)//查找 void R_Rotate(BSTree&p)//右旋 void L_Rotate(BSTree&p)//左旋
void LeftBalance(BSTree&T)//插入平衡调整 void RightBalance(BSTree&T)//插入平衡调整
Status InsertAVL(BSTree&T,ElemTypee,int&taller)//插入 void DELeftBalance(BSTree&T)//删除平衡调整 void DERightBalance(BSTree&T)//删除平衡调整 Status Delete(BSTree&T,int&shorter)//删除操作
Status DeleteAVL(BSTree&T,ElemTypee,int&shorter)//删除操作 void merge(BSTree&T1,BSTree &T2)//合并操作
void splitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2)//分裂操作 void PrintBSTree(BSTree&T,intlev)//凹入表显示
附录
源代码：
#include
structBSTNode *lchild ,*rchild;//左、右孩子指针 } BSTNode,* BSTree;/* 查找算法 */ Status SearchBST(BSTreeT,ElemType e){ if(!T){ return 0;//查找失败 } else if(e == T->data){ return 1;//查找成功 } else if(e < T->data){ returnSearchBST(T->lchild,e);} else{ returnSearchBST(T->rchild,e);} }
//右旋
voidR_Rotate(BSTree&p){ BSTreelc;//处理之前的左子树根结点
lc = p->lchild;//lc指向的*p的左子树根结点
p->lchild = lc->rchild;//lc的右子树挂接为*P的左子树 lc->rchild = p;p = lc;//p指向新的根结点
} //左旋
voidL_Rotate(BSTree&p){ BSTreerc;rc = p->rchild;//rc指向的*p的右子树根结点
p->rchild = rc->lchild;//rc的左子树挂接为*p的右子树 rc->lchild = p;p = rc;//p指向新的根结点 } //对以指针T所指结点为根结点的二叉树作左平衡旋转处理，//本算法结束时指针T指向新的根结点 voidLeftBalance(BSTree&T){ BSTreelc,rd;lc=T->lchild;//lc指向*T的左子树根结点
switch(lc->bf){ //检查*T的左子树的平衡度，并做相应的平衡处理
case LH:
//新结点插入在*T的左孩子的左子树，要做单右旋处理 T->bf = lc->bf=EH;R_Rotate(T);break;case RH:
//新结点插入在*T的左孩子的右子树上，做双旋处理 rd=lc->rchild;//rd指向*T的左孩子的右子树根 switch(rd->bf){ //修改*T及其左孩子的平衡因子 case LH: T->bf=RH;lc->bf=EH;break;case EH: T->bf=lc->bf=EH;break;case RH: T->bf=EH;lc->bf=LH;break;} rd->bf=EH;L_Rotate(T->lchild);//对*T的左子树作左旋平衡处理 R_Rotate(T);//对*T作右旋平衡处理 } } //右平衡旋转处理
voidRightBalance(BSTree&T){ BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= rc->bf=EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} } //插入结点
Status InsertAVL(BSTree&T,ElemTypee,int&taller){//taller反应T长高与否 if(!T){//插入新结点，树长高，置taller为true T=(BSTree)malloc(sizeof(BSTNode));T->data = e;T->lchild = T->rchild = NULL;T->bf = EH;taller = 1;} else{ if(e == T->data){ taller = 0;return 0;} if(e < T->data){ if(!InsertAVL(T->lchild,e,taller))//未插入 return 0;if(taller)//已插入到*T的左子树中且左子树长高
switch(T->bf){//检查*T的平衡度，作相应的平衡处理 case LH: LeftBalance(T);taller = 0;break;case EH: T->bf = LH;taller = 1;break;case RH: T->bf = EH;taller = 0;break;} } else{ if(!InsertAVL(T->rchild,e,taller)){ return 0;} if(taller)//插入到*T的右子树且右子树增高 switch(T->bf){//检查*T的平衡度 case LH: T->bf = EH;taller = 0;break;case EH: T->bf = RH;taller = 1;break;case RH: RightBalance(T);taller = 0;break;} } } return 1;}
void DELeftBalance(BSTree&T){//删除平衡调整 BSTreelc,rd;lc=T->lchild;switch(lc->bf){ case LH: T->bf = EH;//lc->bf= EH;R_Rotate(T);break;case EH: T->bf = EH;lc->bf= EH;R_Rotate(T);break;case RH: rd=lc->rchild;switch(rd->bf){ case LH: T->bf=RH;lc->bf=EH;break;case EH: T->bf=lc->bf=EH;break;case RH: T->bf=EH;lc->bf=LH;break;} rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);} }
void DERightBalance(BSTree&T)//删除平衡调整 { BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case EH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} }
voidSDelete(BSTree&T,BSTree&q,BSTree&s,int&shorter){ if(s->rchild){ SDelete(T,s,s->rchild,shorter);if(shorter)switch(s->bf){ case EH: s->bf = LH;shorter = 0;break;case RH: s->bf = EH;shorter = 1;break;case LH: DELeftBalance(s);shorter = 0;break;} return;}
T->data = s->data;if(q!= T)q->rchild = s->lchild;else q->lchild = s->lchild;shorter = 1;} //删除结点
Status Delete(BSTree&T,int&shorter){ BSTree q;if(!T->rchild){ q = T;T = T->lchild;free(q);shorter = 1;} else if(!T->lchild){ q = T;T= T->rchild;free(q);shorter = 1;} else{ SDelete(T,T,T->lchild,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;} } return 1;}
Status DeleteAVL(BSTree&T,ElemTypee,int&shorter){ int sign = 0;if(!T){ return sign;} else{ if(e == T->data){ sign = Delete(T,shorter);return sign;}
else if(e < T->data){ sign = DeleteAVL(T->lchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;}
return sign;} else{ sign = DeleteAVL(T->rchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = LH;shorter = 0;break;case RH: T->bf = EH;break;case LH: DELeftBalance(T);shorter = 0;break;} return sign;}
} } //合并
void merge(BSTree&T1,BSTree &T2){ int taller = 0;if(!T2)return;merge(T1,T2->lchild);InsertAVL(T1,T2->data,taller);merge(T1,T2->rchild);} //分裂
void split(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ int taller = 0;if(!T)return;split(T->lchild,e,T1,T2);if(T->data > e)InsertAVL(T2,T->data,taller);else InsertAVL(T1,T->data,taller);split(T->rchild,e,T1,T2);} //分裂
voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ BSTree t1 = NULL,t2 = NULL;split(T,e,t1,t2);T1 = t1;T2 = t2;return;}
//构建
voidCreatBSTree(BSTree&T){ intnum,i,e,taller = 0;printf(“输入结点个数:”);scanf(“%d”,&num);printf(“请顺序输入结点值n”);for(i = 0;i voidPrintBSTree(BSTree&T,intlev){ int i;if(T->rchild)PrintBSTree(T->rchild,lev+1);for(i = 0;i intcho,taller,e,k;taller = 0;k = 0;while(1){ system(“cls”);printf(“平衡二叉树操作的演示 nn”);printf(“********************************n”);printf(“平衡二叉树显示区 n”);printf(“T1树n”);if(!T1)printf(“n 当前为空树n”);else{ PrintBSTree(T1,1);} printf(“T2树n”);if(!T2)printf(“n 当前为空树n”);else PrintBSTree(T2,1);printf(“n******************************************************************************n”);printf(“T1操作：1.创建 2.插入 3.查找 4.删除 10.分裂n”);printf(“T2操作：5.创建 6.插入 7.查找 8.删除 11.分裂n”);printf(“ 9.合并 T1,T2 0.退出n”);printf(“******************************************************************************n”);printf(“输入你要进行的操作：”);scanf(“%d”,&cho);switch(cho){ case 1: CreatBSTree(T1);break;case 2: printf(“请输入要插入关键字的值”);scanf(“%d”,&e);InsertAVL(T1,e,taller);break;case 3: printf(“请输入要查找关键字的值”);scanf(“%d”,&e); if(SearchBST(T1,e))printf(“查找成功！n”);else printf(“查找失败！n”);printf(“按任意键返回87”);getchar();getchar();break;case 4: printf(“请输入要删除关键字的值”);scanf(“%d”,&e);if(DeleteAVL(T1,e,k))printf(“删除成功！n”);else printf(“删除失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 5: CreatBSTree(T2);break;case 6: printf(“请输入要插入关键字的值”);scanf(“%d”,&e);InsertAVL(T2,e,taller);break;case 7: printf(“请输入要查找关键字的值”);scanf(“%d”,&e); if(SearchBST(T2,e))printf(“查找成功！n”);else printf(“查找失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 8: printf(“请输入要删除关键字的值”);scanf(“%d”,&e);if(DeleteAVL(T2,e,k))printf(“删除成功！n”);else printf(“删除失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 9: merge(T1,T2);T2 = NULL;printf(“合并成功，按任意键返回”);getchar();getchar();break;case 10: printf(“请输入要中间值字的值”);scanf(“%d”,&e);splitBSTree(T1,e,T1,T2);printf(“分裂成功，按任意键返回”);getchar();getchar();break;case 11: printf(“请输入要中间值字的值”);scanf(“%d”,&e);splitBSTree(T2,e,T1,T2);printf(“分裂成功，按任意键返回”);getchar();getchar();break;case 0: system(“cls”);exit(0);} } } main(){ BSTree T1 = NULL;BSTree T2 = NULL;Start(T1,T2);} 数据结构实验报告二 题目： 用先序递归过程监理二叉树（存储结构：二叉链表） 输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为： 并用如下实力测试： 算法思路： 显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。 利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。 初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下： template template root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。 为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。 先序遍历：采用递归的方法建立。template xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } 中序遍历：递归方法建立： template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } 后序遍历：递归方法建立： template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。 template Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。 int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< 程序结构： 主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验 源代码： #include template { T data; BiNode template { public: BiTree(); //构造函数，初始化一棵二叉树 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode //获得指向根结点的指针 void xianxu(BiNode //前序遍历二叉树 void zhongxu(BiNode //中序遍历二叉树 void houxu(BiNode //后序遍历二叉树 void cengxu(BiNode //层序遍历二叉树 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } } template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode BiNode else{ Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } template if(root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< cout<<“层序遍历序列为”< 通过对结果的分析，发现输出结果与建立二叉树时的输入完全符合，说明程序的运行结果是正确的。 心得体会： 1)函数递归的方法可以在相当程度上使程序简洁，避免代码的冗长复杂。2)构造函数如果带参数，在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用，初始的根节点的数据值由键盘输入，因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。 3)编程时，要不停得检验自己的输入与输出，必要的时候需要人工进行计算，以保证程序的运行按照预先的设想。第五篇：数据结构作业——二叉树
点击咨询 