平衡二叉树的操作演示 Microsoft Office Word 文档

题目：平衡二叉树操作的演示

一、需求分析

1. 初始，平衡二叉树为空树，操作界面给出两棵平衡二叉树的显示、查找、插入、 删除、销毁、合并两棵树，几种种选择。其中查找、插入和删除操作均要提示用户输入关键字。每次插入或删除一个节点后都会更新平衡二叉树的显示。

2. 平衡二叉树的显示采用凹入表形式。

3. 每次操作完毕后都会给出相应的操作结果，并进入下一次操作，直到用户选择退出程序。

二、概要设计

1. 平衡二叉树的抽象数据类型定义：

ADT BalancedBinaryTree{

数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作P：

InitAVL(BSTree& T)

操作结果：构造一个空的平衡二叉树T

DestroyAVL(BSTree& T)

初始条件：平衡二叉树T存在

操作结果：销毁平衡二叉树T

SearchAVL(BSTree T,int key)

初始条件：平衡二叉树T存在，key为和关键字相同类型的给定值

操作结果：若T中存在关键字和key相等的数据元素，则返回指向该元素的指针，否则为空

InsertAVL(BSTree& T,int key,Status& taller)

初始条件：平衡二叉树T存在，key和关键字的类型相同

操作结果：若T中存在关键字等于key的数据元素则返回，若不存在则插入一个关键字为key的元素

DeleteAVL(BSTree& T,int &key,Status& lower)

初始条件：平衡二叉树T存在，key和关键字的类型相同

操作结果：若T中存在关键字和key相同的数据元素则删除它

}ADT BalancedBinaryTree

2. 本程序包含二个模块

1） 主程序模块：

在文件AVLTree.cpp中，主要实现与用户的交互，以及对平衡二叉树基本操作调用。

Void main（）

{

接收命令；

While(“命令”！＝“退出”)

{

处理命令；

清屏并得新打印提示信息；

接收下一条命令；

}

}

2） 平衡二叉树基本操作

在头文件AVLTree.h中，实现平衡二叉树的抽象数据类型的各函数原型。

各模块间的调用关系如下：

主程序模块

word/media/image1.gif

平衡二叉树模块

三、详细设计

1. 根据题目要求和平衡二叉树的操作特点，平衡二叉树采用整数链式存储结构，并实现在头文件AVL.h中。

――――――基本操作的函数原型――――――

#define LH 1 //左高

#define EH 0 //等高

#define RH -1 //右高

#define TRUE 1

#define FALSE 0

#define ERROR 0

#define OK 1

typedef int Status;

typedef int ElemType; //本程序处理数据对象为整型

typedef struct BSTNode{

ElemType data;

int bf;

struct BSTNode *lchild,*rchild;

}BSTNode,*BSTree;

――――――――内部操作――――――――

1）平衡二叉树基本操作实现

//构造平衡二叉树T

Status InitAVL(BSTree &T)

{

T=NULL;

return OK;

}

//对以*p为根的二叉树作左旋处理,处理之后p指向新的树根结点

//即旋转处理之前的右子树的根结点

void L_Rotate(BSTree &p)

{

BSTree rc;

rc=p->rchild;

p->rchild=rc->lchild;

rc->lchild=p; p=rc;

}

//对以*p为根的二叉树作右旋处理,处理之后p指向新的树根结点

//即旋转处理之前的左子树的根结点

void R_Rotate(BSTree &p)

{

BSTree lc;

lc=p->lchild;

p->lchild=lc->rchild;

lc->rchild=p; p=lc;

}

//对以指针T所指结点为根的二叉树作右平衡处理

//本算法结束时T指向新的根结点

void LeftBalance(BSTree &T)

{

BSTree lc,rd;

lc=T->lchild;

switch(lc->bf)

{

case LH:

T->bf=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);

}

}

//对以指针T所指结点为根的二叉树作右平衡处理

//本算法结束时T指向新的根结点

void RightBalance(BSTree& T)

{

BSTree rc,rd;

rc=T->rchild;

switch(rc->bf)

{

case RH: T->bf=rc->bf=EH;

L_Rotate(T);

break;

case LH: rd=rc->lchild;

switch(rd->bf){

case RH:

T->bf=LH; rc->bf=EH; break;

case EH:

T->bf=rc->bf=EH; break;

case LH:

T->bf=EH; rc->bf=RH; break;

}

rd->bf=EH;

R_Rotate(T->rchild);

L_Rotate(T);

}

}

//查找关键字为key的结点

//如有返回指向此结点的指针，如无返回空

Status SearchAVL(BSTree T,int e)

{

if(!T) return ERROR;

if(T->data==e){

printf("\t结果: %d[%d]\n\t",T->data,T->bf);

return OK;

}

else{

if(T->lchild)

if(SearchAVL(T->lchild,e))

return OK;

if(T->rchild)

if(SearchAVL(T->rchild,e))

return OK;

return ERROR;

}

}

//若在平衡的二叉排序树中不存在和e相同的关键字的结点，则插入一个数据元素为e的新结点并返回1，否则返回0。

//若因插入而使二叉排序树失去平衡，则做平衡旋转处理

//布尔变量taller反映T长高与否

Status InsertAVL(BSTree &T,ElemType e,Status &taller)

{

if(!T){

T=(BSTree)malloc(sizeof(BSTNode));

T->data=e;

T->lchild=T->rchild=NULL;

T->bf=EH;

taller=TRUE;

}

else{

if(e==T->data)

{taller=FALSE; return FALSE;}

if(edata){

if(!InsertAVL(T->lchild,e,taller)) return FALSE;

if(taller)

switch(T->bf)

{

case LH:

LeftBalance(T); taller=FALSE; break;

case EH:

T->bf=LH; taller=TRUE; break;

case RH:

T->bf=EH; taller=FALSE; break;

}

}

else

{

if(!InsertAVL(T->rchild,e,taller)) return FALSE;

if(taller)

switch(T->bf)

{

case RH:

RightBalance(T); taller=FALSE; break;

case EH:

T->bf=RH; taller=TRUE; break;

case LH:

T->bf=EH; taller=FALSE; break;

}

}

}

return TRUE;

}

//打印空格

void Printblank(int i){

while(i >=0){

printf(" ");

i--;

}

}

//以凹入表的形式显示平衡二叉树T

void ViewTree(BSTree T,int i)

{

if(T)

{ Printblank(i); printf("%d[%d]\n",T->data,T->bf);}

else

{ Printblank(i); printf("NULL\n"); return; }

ViewTree(T->lchild,i+5);

ViewTree(T->rchild,i+5);

}

//销毁平衡二叉树

void DestroyAVL(BSTree &T)

{

if(T)

{

if(T->lchild)

DestroyAVL(T->lchild);

if(T->rchild)

DestroyAVL(T->rchild);

free(T);

T=NULL;

}

}

//连接二叉树T2到T1中

Status CombineAVL(BSTree &T1,BSTree& T2)

{

Status taller;

if(!T2)return TRUE;

if(T2->lchild) CombineAVL(T1,T2->lchild);

if(T2->rchild) CombineAVL(T1,T2->rchild);

if(!InsertAVL(T1,T2->data,taller)) return FALSE;

return TRUE;

}

//从二叉排序树中删除结点p，并重接它的左或右子树

Status Delete(BSTree& p,int &e,int &flag){

BSTree q,s;

if(!p->rchild){

q=p;

if(p->lchild){

p->lchild->bf=p->bf;

e=p->lchild->data;

}

p=p->lchild;

free(q);

flag=1;

}

else if(!p->lchild){

q=p;

p->rchild->bf=p->bf;

e=p->rchild->data;

p=p->rchild;

free(q);

flag=1;

}

else{

q=p; s=p->lchild;

while(s->rchild){q=s; s=s->rchild;}

p->data=s->data;

if(q!=p)q->rchild=s->lchild;

else {

q->lchild=s->lchild;

p->bf=RH;

}

e=q->data;

free(s);

}

return TRUE;

}

//若二叉排序树T中存在关键字等于e的数据元素时，则删除该数据元素结点

//并返回TRUE，否则返回FALSE

Status DeleteBST(BSTree& T,int &e,int &flag){

if(!T)return FALSE;

else{

if(e==T->data)return Delete(T,e,flag);

else if(edata) {

if(!DeleteBST(T->lchild,e,flag)) return FALSE;

return TRUE;

}

else {

if(!DeleteBST(T->rchild,e,flag)) return FALSE;

return TRUE;

}

}

}

void DelBalance(BSTree& T,int e, Status &lower,int &flag)

{

if(!T){

lower=TRUE; return;

}

if(e==T->data){

if(flag==1)

switch(T->bf)

{

case RH:

case LH:

T->bf=EH; lower=TRUE; break;

}

else switch(T->bf)

{

case RH:

lower=FALSE; break;

case EH:

T->bf=LH; lower=FALSE; break;

case LH:

LeftBalance(T); lower=TRUE; break;

}

return ;

}

if(edata){

DelBalance(T->lchild,e,lower,flag);

if(lower)

switch(T->bf)

{

case LH:

T->bf=EH; lower=TRUE; break;

case EH:

T->bf=RH; lower=FALSE; break;

case RH:

RightBalance(T); lower=TRUE; break;

}

}

if(e>T->data){

DelBalance(T->rchild,e,lower,flag);

if(lower)

switch(T->bf)

{

case RH:

T->bf=EH; lower=TRUE; break;

case EH:

T->bf=LH; lower=FALSE; break;

case LH:

LeftBalance(T); lower=TRUE; break;

}

}

return ;

}

//删除平衡二叉树结点

Status DeleteAVL(BSTree &T,int &e,Status &lower){

int flag=0;

if(!DeleteBST(T,e,flag)) return FALSE;

else DelBalance(T,e,lower,flag);

return TRUE;

}

2）主函数Main及其它辅助函数的实现

/*主函数*/

#include "AVLTree.h"

void main()

{

system("color 3f");

void Print(); void About();

BSTree T,t,p; int e,s; Status taller,lower;

InitAVL(T); InitAVL(t); InitAVL(p);

Print();

scanf("%d",&s);

while(s!=8){

switch(s)

{

case 1: //显示

printf("按凹入表形式打印二叉树结构：\n");

printf("T:\n");

PrintTree(T,1);

printf("t:\n");

PrintTree(t,1);

break;

case 2: //查找

printf("\t选择树(1,2):");

scanf("%d",&s);

printf("\t关键字(整数):");

scanf("%d",&e);

if(s==1) s=SearchAVL(T,e);

if(s==2) s=SearchAVL(t,e);

if(!s) printf("\t查找失败\n\t");

break;

case 3: //插入

printf("\t选择树(1-T,2-t):");

scanf("%d",&s);

printf("\t关键字(整数):");

scanf("%d",&e);

if(s==1){

InsertAVL(T,e,taller);

printf("T:\n");

PrintTree(T,1);

}

if(s==2){

InsertAVL(t,e,taller);

printf("t:\n");

PrintTree(t,1);

}

break;

case 4: //删除

printf("\t选择树(1-T,2-t):");

scanf("%d",&s);

printf("\t关键字(整数):");

scanf("%d",&e);

if(s==1)

if(DeleteAVL(T,e,lower))

printf("\t删除成功\n\t");

else

printf("\t删除失败\n\t");

if(s==2)

if(DeleteAVL(t,e,lower))

printf("\t删除成功\n\t");

else

printf("\t删除失败\n\t");

break;

case 5: //合并

if(CombineAVL(T,t))

printf("\t合并成功\n");

else

printf("\t合并失败\n");

printf("合并后T:\n");

PrintTree(T,1);

break;

case 6: //销毁

printf("\t选择树(1,2):");

scanf("%d",&s);

if(s==1) DestroyAVL(T);

if(s==2) DestroyAVL(t);

printf("\t销毁成功\n\t");

break;

}

system("pause");

Print();

scanf("%d",&s);

}

}

void Print()

{

system("cls");

printf(" ※※※※平衡二叉树操作演示※※※※ \n");

printf("\n");

printf(" **************菜单**************** \n");

printf(" * 1. 显示 * \n");

printf(" * 2. 查找 * \n");

printf(" * 3. 插入 * \n");

printf(" * 4. 删除 * \n");

printf(" * 5. 合并 * \n");

printf(" * 6. 销毁 * \n");

printf(" * 7. 退出 * \n");

printf(" ********************************** \n");

printf("请选择：\n");

}

3）函数之间的调用关系图：

主程序

word/media/image2.gif

word/media/image3.gifword/media/image4.gifword/media/image4.gifword/media/image5.gifword/media/image6.gifword/media/image6.gif

PrintTree InitAVL SearchAVL InsertAVL CombineAV DeleteAVL

word/media/image7.gifword/media/image8.gifword/media/image9.gifword/media/image6.gifword/media/image6.gifword/media/image6.gif

PrintTree DelBalance DeleteBST

word/media/image10.gifword/media/image11.gifword/media/image10.gifword/media/image12.gif

RightBalance LeftBalance Delete

word/media/image8.gifword/media/image8.gifword/media/image8.gifword/media/image9.gif

word/media/image6.gifword/media/image6.gifword/media/image13.gifword/media/image14.gif

R_Rotate L_Rotate

四、调试分析

1. 本程序设计到二衡二叉树主要操作的几个函数大部分采用递归的形式实现。这种形式易于理解，而且代码简单，逻辑结构明了。唯一的缺点就是计算机执行效率比较慢。

2. 为了使程序代码结构清淅层次分明，并且易读性强。本程序中大量采用switch语句实现程序的分枝处理。比起用if语句来，不仅大大减少了代码量而且优化了程序的结构。

3. 在平衡二叉树的结构定义中，考虑到本程序的设计难度，只设置了关键字data和平衡因子bf两项。如要增强程序的功能，还可以加入其它数据域，如结点编号、注释信息等。

4. 本程序的数据对象为整型，但为了增强功能可以对处理的数据类型进行拓展，如支持字符、浮点型等。不过这样就要求对输入输出的处理比较烦锁一点。

5. 为了实现程序的可用性和及时反应操作期间平衡二叉树的变化，本程序采用了凹表输出平衡二叉树各结点的关键字的值及平衡因子的值。在每一次插入或都合并操作后都会重新显示平衡二叉树。这样就可以更容易地观察平衡二叉树的变化。

6. 为了实现二叉树的合并操作（选做内容），本程序里设置了两棵二叉树（T和t），每次查找、插入、删除及销毁操作都要先选择操作对象是哪棵树。合并二叉树时，并t中的元素逐个插入到T中去。从而T就是T和t合并以后的平衡二叉树。合并完毕将会以凹表显示合并以后的T。

7. 为了更接近于数据结构中的伪代码形式，程序采用Visual C++ 6.0编程坏境。用C++的环境写C语言的代码。由于C++兼容C，所以可以借用C++的引用功能而又保持C语言的本质不变，从而便代码更接近于数据结构中的代码形式。

8. 在考虑平和二叉树元素的删除时，平衡变换可以采用插入的平衡变幻的反变换方法，这样可以免去写删除时的左旋、右旋、左平衡、右平衡函数。但插入结点时是总是插入的叶子结点，这样可以从根开始执行递归，从插入点开始返回递归；可是删除却不一定是删除叶子结点。为了解决这个问题，本程序使用了排序树的删除函数，这样二叉树失去平衡就像是从叶子结点开始，并使关键字为失去平衡的结点或是被删除结点，还用了标志变量Flag区别这两种情况。然后再根据删除中的返回情况进行平衡处理，从而解决了这个问题。

五、用户手册
　　1. 程序的运行为Windows下的命令提示符，程序文件句为：AVLTree.exe。

2. 双击打开程序后出现如下界面：

这是本程序的主界面，列出了本程序所具用的所有功能，并接入用户的选择以进入不同的操作。

3. 选择1键以凹入表形式展示而叉平衡树。

4. 选择2键查找结点，按提示输入要查找的节点关键字。

5. 选择3键插入结点，按提示输入要插入的节点关键字。

6. 选择4键删除结点，按提示输入要删除的节点关键字。

7. 选择5键合并两棵树。

8. 选择6键销毁已存在的平衡二叉树。

9. 选择7键退出程序。

六、测试结果
　 1. 选择1时将会分别显示以凹表的形式显示程序中设置好的两棵平衡二叉树。程序启动了平衡二叉树T和t都是空的，这里分别赋值为：T:5,2,7 ，t：6,8. 按1显示后如下图：

2.选择2时为查找平衡二叉树的值，首先选择是对T操作还是对t操作。然后输入要查找的关键字。如果程序找个了这个关键字则输出其data值及bf值。如没找到则提示查找失败。如下图：

3. 选择3时为插入操作，首先选择是对T插入还是对t插入。然后输入插入的值，插入成功后凹表显示插入后的平衡二叉树，如下图：

4. 选择4时为删除操作，同上首先选择操作对象是T树还是t树，然后输入删除关键字。删除成功则提示删除成功，删除不成功则提示删除失败。如下图：

删除成功时，再按1显示二叉树会发现刚才删除的结点已经不在二叉树中。说明删除成功。

5. 按5时为合并平衡二叉树，程序将t树合到T中，合并成功后将以凹表显示合并后的内容：

6. 选6时为销毁平衡二叉树：

销毁成功后，平衡二叉树为空，其结点空间被释放。

七、附录
　 文件清单

AVLTree.h //平衡二叉树基本操作函数

AVLTree.cpp //程序主函数

2.选择2时为查找平衡二叉树的值，首先选择是对T操作还是对t操作。然后输入要查找的关键字。如果程序找个了这个关键字则输出其data值及bf值。如没找到则提示查找失败。如下图：

本文来源：https://www.2haoxitong.net/k/doc/2fc1a58302d276a200292ef0.html