平衡二叉树操作的演示
1．需求分析
1.输入的形式和输入值的范围：
输入的形式是用户自主输入，输入值得范围是整数。
2.输出的形式：
凹入表形式
3.程序所能达到的功能：
(1)初始，平衡二叉树为空树，操作界面给种出查找、插入和删除三操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新平衡二叉树的显示。
(2)平衡二叉树的显示采用如6.3题要求的凹入表形式。
(3)合并两棵平衡二叉树。
4.把一棵平衡二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。
5.测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。
如下图:
2.概要设计
平衡二叉树的所有数据类型的定义：
#define LH +1 //左子树比右子树高
#define EH 0 //左子树与右子树等高
#define RH -1 //左子树与右子树矮
typedef int ElemType;
typedef struct BBSTNode{
ElemType data;
int bf;
struct BBSTNode *lchild, *rchild;
} BBSTNode, *BBSTree;
int SearchBST(BBSTree T, ElemType e);//查找
void R_Rotate(BBSTree &p);//右旋
void L_Rotate(BBSTree &p);//左旋
void LeftBalance(BBSTree &T);//左平衡处理操作
void RightBalance(BBSTree &T);//右平衡处理操作
void CreatBBSTree(BBSTree &T);//创建平衡二叉树操作
int InsertAVL(BBSTree &T, ElemType e, int &taller);//插入节点操作
int DeleteAVL(BBSTree &t, ElemType key, int &shorter);//删除节点操作
void SplitBBSTree(BBSTree T, ElemType e, BBSTree &T1, BBSTree &T2);//分裂平衡二叉树操作
void Merge(BBSTree &T1, BBSTree &T2);//合并两棵平衡二叉树操作
void BBSTPageWindow(BBSTree &T1, BBSTree &T2);//程序主页面窗口
void PrintBBSTree(BBSTree &T, int lev);//凹入表形式显示方法
平衡二叉树的主程序的流程以及各程序模块之间的调用关系如下图：
3.详细设计
平衡二叉树的所有数据类型的定义：
#define LH +1 //左子树比右子树高
#define EH 0 //左子树与右子树等高
#define RH -1 //左子树与右子树矮
typedef int ElemType;
typedef struct BBSTNode{
ElemType data;
int bf;
struct BBSTNode *lchild, *rchild;
} BBSTNode, *BBSTree;
函数之间的调用关系如下图：
各模块的伪代码：
int SearchBST(BBSTree T, ElemType e);//查找
{
//若树为空，则查找失败
//若树不为空，则类似树先序递归遍历查找
}
void R_Rotate(BBSTree &p);//右旋{
//lc指向p节点的左孩子
//lc节点的右子树置为p节点的左子树
//置p节点为lc节点的右孩子
//p指向新的根节点
}
void L_Rotate(BBSTree &p);//左旋 {
//rc指向p节点的右孩子
//rc节点的左子树置为p节点的右子树
//置p节点为ec节点的左孩子
//p指向新的根节点
}
void RightBalance(BBSTree &T) { //实现对树T的右平衡处理
//检查T的右子树的平衡度，并做相应的平衡处理
//RR型，左旋调整
//RL型，左旋调整
//修改T及其右孩子的平衡因子
//对T的右子树作右旋平衡处理
//对T作左旋平衡处理
}
}
void LeftBalance(BBSTree &T){ //实现对树T的左平衡处理
//检查T的左子树的平衡度，并做相应的平衡处理
//LL型，右旋处理
//LR型，做双旋处理
//修改T及其左孩子的平衡因子
//对T的左子树作左旋调整
//对T作右旋调整
}
}
void CreatBBSTree(BBSTree &T);//创建平衡二叉树操作 {
输入值并不断的调用插入函数
}
int InsertAVL(BBSTree &T, ElemType e, Status &taller){ //插入结点,taller反应T长高与否
//创建节点
//若二叉树为空,直接插入节点
//若查找到相同的值，则插入失败
//插入到左子树
//先判断是否插入
//检查T的平衡因子
//原本左高，左平衡处理
//原本等高，左变高
//原本右高，变等高
//插入到右子树
//检查T的平衡因子
//原本左高，变等高
//原本等高，右变高
//原本右高，右平衡处理
}
int DeleteAVL(BBSTree &t, ElemType key, int &shorter){//删除节点操作 //若树空,则不存在该元素,删除失败
//查找该元素结点若左子树为空，则直接让右孩子节点覆盖该节点
//查找该元素结点若右子树为空，则直接让左孩子节点覆盖该节点
//查找该元素结点若左右子树都存在,则找到该节点的前驱节点
//在左子树中递归删除前驱结点
//递归在左右子树中继续查找并删除该节点，并检查平衡因子，做出相应的左右平衡调整
}
void SplitBBSTree(BBSTree T, ElemType e, BBSTree &T1, BBSTree &T2){ //分裂平衡二叉树
//若树为空，则失败
//不断递归T的左右子树
//当e大于T->data,则将T->data插入T2
//当e小于或等于于T->data,则将T->data插入T1
}
void Merge(BBSTree &T1, BBSTree &T2);//合并两棵平衡二叉树操作{
//若树为空，则失败
//不断递归T2的左右子树
//将T2->data插入T1
}
void BBSTPageWindow(BBSTree &T1, BBSTree &T2);{ //程序主页面窗口
//平衡二叉树1操作：1.创建 2.插入 3.查找 4.删除 5.分裂
// 平衡二叉树2操作：6.创建 7.插入 8.查找 9.删除 10.分裂
//平衡二叉树操作：11.合并两棵二叉树 0.退出
//用switch-case语句创建出相应功能对应的操作序号并调用相关的函数
}
void PrintBBSTree(BBSTree &T, int lev);{ //凹入表形式显示方法
//利用打印空格间隔和行递归打印出二叉树
}
4.调试分析
在运行过程中由于使用递归算法，经常出现因空间不够而导致程序中断结束，因此只能使用断点来对各个函数模块测试，需要耐性和细致，经过不断的调试，最终才完成了整个程序的编写。
5.用户使用说明
根据主页面，按照序号提示选择你需要实现的功能即可。
6.测试结果
所有的测试数据步骤如下图:
输入：2,4,6,1,3,5,9，创建二叉树T1:
创建成功凹入表显示：
成功查找二叉树T1中值为3的结点：
成功插入二叉树T1中值为7的结点：
成功删除二叉树T1中值为6的结点：
成功分裂二叉树T1中值为4的结点：
成功合并分裂后T1,T2为T1:
输入：2,5,3,7,1,6,8,9，创建二叉树T2:
成功凹入表显示：
成功查找二叉树T2中值为3的结点：
成功插入二叉树T2中值为4的结点：
成功删除二叉树T2中值为6的结点：
成功分裂二叉树T2中值为5的结点：
分裂后成功显示:
成功合并上面分裂的二叉树：
7.附录
平衡二叉树源代码文件：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LH +1 //左子树比右子树高
#define EH 0 //左子树与右子树等高
#define RH -1 //左子树与右子树矮
typedef int ElemType;
typedef struct BBSTNode{
ElemType data;
int bf;
struct BBSTNode *lchild, *rchild;
} BBSTNode, *BBSTree;
int SearchBST(BBSTree T, ElemType e);//查找
void R_Rotate(BBSTree &p);//右旋
void L_Rotate(BBSTree &p);//左旋
void LeftBalance(BBSTree &T);//左平衡处理操作
void RightBalance(BBSTree &T);//右平衡处理操作
void CreatBBSTree(BBSTree &T);//创建平衡二叉树操作
int InsertAVL(BBSTree &T, ElemType e, int &taller);//插入节点操作
int DeleteAVL(BBSTree &t, ElemType key, int &shorter);//删除节点操作
void SplitBBSTree(BBSTree T, ElemType e, BBSTree &T1, BBSTree &T2);//分裂平衡二叉树操作
void Merge(BBSTree &T1, BBSTree &T2);//合并两棵平衡二叉树操作
void BBSTPageWindow(BBSTree &T1, BBSTree &T2);//程序主页面窗口
void PrintBBSTree(BBSTree &T, int lev);//凹入表形式显示方法
//测试代码
int main()
{
BBSTree T1 = NULL;
BBSTree T2 = NULL;
BBSTPageWindow(T1, T2);
return 0;
}
//插入结点
int InsertAVL(BBSTree &T, ElemType e, int &taller){ //taller反应T长高与否
if (!T){//插入新结点，树长高，置taller为true
T = (BBSTree)malloc(sizeof(BBSTNode));
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;
}
//查找
int SearchBST(BBSTree T, ElemType e){
if (!T){
return 0; //查找失败
}
else if (e == T->data)
{
return 1; //查找成功
}
else if (e < T->data){
return SearchBST(T->lchild, e);
}
else{
return SearchBST(T->rchild, e);
}
}
//右旋
void R_Rotate(BBSTree &p){
BBSTree lc;
lc = p->lchild;
p->lchild = lc->rchild;
lc->rchild = p;
p = lc;
}
//左旋
void L_Rotate(BBSTree &p){
BBSTree rc;
rc = p->rchild;
p->rchild = rc->lchild;
rc->lchild = p;
p = rc;
}
//右平衡旋转处理
void RightBalance(BBSTree &T) { //实现对树T的右平衡处理
BBSTree rc, ld;
rc = T->rchild;
switch (rc->bf){//检查T的右子树的平衡度，并做相应的平衡处理
case RH://RR型，左旋调整
T->bf = rc->bf = EH;
L_Rotate(T);
break;
case LH://RL型，左旋调整
ld = rc->lchild;
switch (ld->bf){//修改T及其右孩子的平衡因子
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);// 对T的右子树作右旋平衡处理
L_Rotate(T);//对T作左旋平衡处理
break;
}
}
//左平衡旋转处理
void LeftBalance(BBSTree &T){ //实现对树T的左平衡处理
BBSTree lc, rd;
lc = T->lchild;
switch (lc->bf){ //检查T的左子树的平衡度，并做相应的平衡处理
case LH: //LL型，右旋处理
T->bf = lc->bf = EH;
R_Rotate(T);
break;
case RH:
//LR型，做双旋处理
rd = lc->rchild;
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作右旋调整
break;
}
}
int DeleteAVL(BBSTree &t, ElemType key, int &shorter)
{
if(t == NULL) //不存在该元素
{
return 0; //删除失败
}
else if (t->data == key) //找到元素结点
{
BBSTree q = NULL;
if (t->lchild == NULL) //左子树为空
{
q = t;
t = t->rchild;
delete q;
shorter = 1;
}
else if (t->rchild == NULL) //右子树为空
{
q = t;
t = t->lchild;
delete q;
shorter = 1;
}
else //左右子树都存在,
{
q = t->lchild;
while (q->rchild)
{
q = q->rchild;
}
t->data = q->data;
DeleteAVL(t->lchild, q->data, shorter); //在左子树中递归删除前驱结点
}
}
else if (t->data > key) //左子树中继续查找
{
if (!DeleteAVL(t->lchild, key, shorter))
{
return 0;
}
if (shorter)
{
switch (t->bf)
{
case LH:
t->bf = EH;
shorter = 1;
break;
case EH:
t->bf = RH;
shorter = 0;
break;
case RH:
RightBalance(t); //右平衡处理
if (t->rchild->bf == EH)
shorter = 0;
else
shorter = 1;
break;
}
}
}
else //右子树中继续查找
{
if (!DeleteAVL(t->rchild, key, shorter))
{
return 0;
}
if (shorter)
{
switch (t->bf)
{
case LH:
LeftBalance(t); //左平衡处理
if (t->lchild->bf == EH)
shorter = 0;
else
shorter = 1;
break;
case EH:
t->bf = LH;
shorter = 0;
break;
case RH:
t->bf = EH;
shorter = 1;
break;
}
}
}
return true;
}
//合并
void Merge(BBSTree &T1, BBSTree &T2){
int taller = 0;
if (!T2)
return;
Merge(T1, T2->lchild);
InsertAVL(T1, T2->data, taller);
Merge(T1, T2->rchild);
}
//分裂
void Split(BBSTree T, ElemType e, BBSTree &T1, BBSTree &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);
return;
}
//分裂
void SplitBBSTree(BBSTree T, ElemType e, BBSTree &T1, BBSTree &T2){
BBSTree t1 = NULL, t2 = NULL;
Split(T, e, t1, t2);
T1 = t1;
T2 = t2;
return;
}
//构建
void CreatBBSTree(BBSTree &T){
int num, i, e, taller = 0;
printf("请输入结点个数:");
scanf("%d", &num);
for (i = 0; i < num; i++)
{
printf("请输入第%d个结点的值:", i + 1);
scanf("%d", &e);
InsertAVL(T, e, taller);
}
printf("构建成功，输入任意字符返回\n");
getchar();
getchar();
}
//凹入表形式显示方法
void PrintBBSTree(BBSTree &T, int lev){
int i;
if (T->rchild)
PrintBBSTree(T->rchild, lev + 1);
for (i = 0; i <lev; i++)
printf(" ");
printf("%d\n", T->data);
if (T->lchild)
PrintBBSTree(T->lchild, lev + 1);
}
//程序主页面窗口
void BBSTPageWindow(BBSTree &T1, BBSTree &T2){
int cho, taller, e, k;
taller = 0;
k = 0;
while (1){
system("cls");
printf("\n*******************************************************************************************\n");
printf(" 平衡二叉树操作的演示 \n\n");
printf("\n------------------------------------------------------------------------------\n");
printf(" 平衡二叉树1操作：1.创建 2.插入 3.查找 4.删除 5.分裂\n");
printf(" 平衡二叉树2操作：6.创建 7.插入 8.查找 9.删除 10.分裂\n");
printf(" 平衡二叉树操作：11.合并两棵二叉树 0.退出\n");
printf("\n------------------------------------------------------------------------------\n");
printf("平衡二叉树显示区: \n");
printf("T1树\n");
if (!T1)
printf("\n 当前为空树\n");
else{
PrintBBSTree(T1, 1);
}
printf("T2树\n");
if (!T2)
printf("\n 当前为空树\n");
else
PrintBBSTree(T2, 1);
printf("******************************************************************************\n");
printf("输入你要进行的操作：");
scanf("%d", &cho);
switch (cho){
case 1:
CreatBBSTree(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("按任意键返回");
getchar();
getchar();
break;
case 4:
printf("请输入要删除关键字的值:");
scanf("%d", &e);
if (DeleteAVL(T1, e, k))
printf("删除成功！\n");
else
printf("删除失败！\n");
printf("按任意键返回");
getchar();
getchar();
break;
case 6:
CreatBBSTree(T2);
break;
case 7:
printf("请输入要插入关键字的值:");
scanf("%d", &e);
InsertAVL(T2, e, taller);
break;
case 8:
printf("请输入要查找关键字的值:");
scanf("%d", &e);
if (SearchBST(T2, e))
printf("查找成功！\n");
else
printf("查找失败！\n");
printf("按任意键返回");
getchar();
getchar();
break;
case 9:
printf("请输入要删除关键字的值:");
scanf("%d", &e);
if (DeleteAVL(T2, e, k))
printf("删除成功！\n");
else
printf("删除失败！\n");
printf("按任意键返回");
getchar();
getchar();
break;
case 11:
Merge(T1, T2);
T2 = NULL;
printf("合并成功，按任意键返回");
getchar();
getchar();
break;
case 5:
printf("请输入要分裂的值:");
scanf("%d", &e);
SplitBBSTree(T1, e, T1, T2);
printf("分裂成功，按任意键返回");
getchar();
getchar();
break;
case 10:
printf("请输入要分裂的值:");
scanf("%d", &e);
SplitBBSTree(T2, e, T1, T2);
printf("分裂成功，按任意键返回");
getchar();
getchar();
break;
case 0:
system("cls");
exit(0);
}
}
}