广工数据结构实验报告平衡二叉树

更新时间：2023-10-06 10:45:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构实验报告

题目：平衡二叉树

学院专业年级班别学号学生姓名指导教师

2015年7月1日

1.题目：采用字符类型为整型类型和链式存储结构，实现抽象数据类型BTree。 ADT BTree{

数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ |ai-1, ai∈D, i=2,...,n } 基本操作： Adj_balance(T)

操作结果：创建平衡二叉树。 InsertAVL(T,search,taller)

初始条件：二叉树T已存在。操作结果：增加新结点。 SetAVL(T,search,taller)

初始条件：二叉树T已存在。

操作结果：在平衡二叉树上增加新结点并调平衡。 DeleteAVL(T,search,shorter)

初始条件：二叉树T已存在。操作结果：删除结点。 } ADT BTree 2．存储结构定义

公用头文件DS0.h: #include #include 树的内部变量

typedef struct BTNode {

int data;

int bf; //平衡因子

struct BTNode *lchild,*rchild;//左、右孩子 }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);

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); int menu( ); 3. 算法设计

/*对以*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指向新的结点 }

/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/ void Left_Root_Balance(BTree &T) {

BTree lc,rd;

lc = T->lchild; //指向*T的左子树根结点

switch(lc->bf) //检查*T的左子树的平衡度，并作相应平衡处理 {

case 1: //新结点插入在*T的左孩子的左子树上，要作单右旋处理

T->bf = lc->bf = 0; Right_Balance(T); break;

case -1: //新结点插入在*T的左孩子的右子树上，要作双旋处理

rd = lc->rchild; //rd指向*T的左孩子的右子树根 switch(rd->bf) //修改*T及其左孩子的平衡因子 {

case 1:

T->bf = -1; lc->bf = 0; break; case 0:

T->bf = lc->bf = 0; break; case -1:

T->bf = 0;

lc->bf = 1; break; }

rd->bf = 0;

Left_Balance(T->lchild); //对*T的左子树作左旋平衡处理 Right_Balance(T); //对*T作右旋平衡处理 } }

/*对以指针T所指结点为根的二叉树作右平衡旋转处理*/ void Right_Root_Balance(BTree &T) {

BTree rc,ld;

rc = T->rchild; //指向*T的左子树根结点

switch(rc->bf) //检查*T的右子树的平衡度，并作相应平衡处理 {

case -1: //新结点插入在*T的右孩子的右子树上，要作单左旋处理

T->bf = rc->bf =0;

Left_Balance(T); break;

case 1: //新结点插入在*T的右孩子的左子树上，要作双旋处理

ld = rc->lchild; //ld指向*T的右孩子的左子树根 switch(ld->bf) //修改*T及其右孩子的平衡因子 {

case 1:

T->bf = 0; rc->bf = -1; break; case 0:

T->bf = rc->bf =0; break; case -1:

T->bf = 1; rc->bf = 0; break; }

ld->bf = 0;

Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理 Left_Balance(T); //对*T作左旋平衡处理 } }

/*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/

bool InsertAVL(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 = 0; taller = true; } else {

if(i==T->data) //树中已存在和有相同关键字的结点 {

taller = 0;

printf(\已存在相同关键字的结点\\n\ return 0; }

if(idata) //应继续在*T的左子树中进行搜索 {

if(!InsertAVL(T->lchild,i,taller)) return 0; }

else //应继续在*T的右子树中进行搜索

{

if(!InsertAVL(T->rchild,i,taller)) return 0; } }

return 1; }

/*输出二叉树*/

void PrintBT(BTree T) {

if(T) {

printf(\ if(T->lchild||T->rchild) {

printf(\

PrintBT(T->lchild); printf(\

PrintBT(T->rchild); printf(\

} } }

/*删除结点时左平衡旋转处理*/

void Left_Root_Balance_det(BTree &p,int &shorter) {

BTree p1,p2;

if(p->bf==1) //p结点的左子树高，删除结点后p的bf减,树变矮 {

p->bf=0; shorter=1; }

else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 {

p->bf=-1; shorter=0; }

else //p结点的右子树高 {

p1=p->rchild;//p1指向p的右子树 if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变 {

Left_Balance(p); p1->bf=1; p->bf=-1; shorter=0; }

else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮 {

Left_Balance(p); p1->bf=p->bf=0; shorter=1; }

else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 {

p2=p1->lchild;

p1->lchild=p2->rchild; p2->rchild=p1;

p->rchild=p2->lchild; p2->lchild=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 Right_Root_Balance_det(BTree &p,int &shorter) {

BTree p1,p2; if(p->bf==-1) {

p->bf=0; shorter=1; }

else if(p->bf==0) {

p->bf=1; shorter=0; } else {

p1=p->lchild; if(p1->bf==0) {

Right_Balance(p); p1->bf=-1; p->bf=1; shorter=0; }

else if(p1->bf==1)

{

Right_Balance(p); p1->bf=p->bf=0; shorter=1; } else {

p2=p1->rchild;

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) {

printf(\不存在要删除的关键字!!\\n\ return 0; }

else if(xdata)//在p的左子树中进行删除 {

k=DeleteAVL(p->lchild,x,shorter); if(shorter==1)

Left_Root_Balance_det(p,shorter); return k; }

else if(x>p->data)//在p的右子树中进行删除 {

k=DeleteAVL(p->rchild,x,shorter); if(shorter==1)

Right_Root_Balance_det(p,shorter); return k; } else {

q=p;

if(p->rchild==NULL) //右子树空则只需重接它的左子树 {

p=p->lchild; free(q); shorter=1; }

else if(p->lchild==NULL)//左子树空则只需重接它的右子树 {

p=p->rchild; free(q);

shorter=1; }

else//左右子树均不空 {

Delete(q,q->lchild,shorter); if(shorter==1)

Left_Root_Balance_det(p,shorter); p=q; }

return 1; } }

/*调平二叉树具体方法*/

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 = 0; taller = true; } else {

if(i==T->data) //树中已存在和有相同关键字的结点 {

taller = false;

printf(\已存在相同关键字的结点\\n\ return 0; }

if(idata) //应继续在*T的左子树中进行搜索 {

if(!SetAVL(T->lchild,i,taller)) return 0;

if(taller) //已插入到*T的左子树中且左子树“长高”

switch(T->bf) //检查*T的平衡度 {

case 1: //原本左子树比右子树高，需要作左平衡处理

Left_Root_Balance(T); taller = false; break;

case 0: //原本左子树、右子等高，现因左子树增高而使树增高

T->bf = 1; taller = true; break;

case -1: //原本右子树比左子树高，现左、右子树等高

T->bf = 0; taller = false; break; } }

else //应继续在*T的右子树中进行搜索

{

if(!SetAVL(T->rchild,i,taller)) return 0;

if(taller) //已插入到*T的右子树中且右子树“长高”

switch(T->bf) //检查*T的平衡度 {

case 1: //原本左子树比右子树高，现左、右子树等高

T->bf = 0; taller = false; break;

case 0: //原本左子树、右子等高，现因右子树增高而使树增高

T->bf = -1; taller = true; break;

case -1: //原本右子树比左子树高，需要作右平衡处理

Right_Root_Balance(T); taller = false; break; } }

return 1; } }

/*二叉树调平操作*/

void Adj_balance(BTree &T) {

int i;

bool taller=false; T = NULL;

printf(\请输入关键字(以-1结束建立平衡二叉树):\ scanf(\ getchar(); while(i != -1) {

SetAVL(T,i,taller);

printf(\请输入关键字(以-1结束建立平衡二叉树):\ scanf(\ getchar(); taller=false; }

printf(\平衡二叉树创建结束.\\n\ if(T)

PrintBT(T); else

printf(\这是一棵空树.\\n\}

/*菜单函数*/ int menu( ) {

int m;

printf(\年7月1日......................\\n\\n\ printf(\ 平衡二叉树\\n\

printf(\ ________________________________\\n\\n\ printf(\ 1 创建平衡二叉树\\n\

printf(\ 2 在平衡二叉树上增加新结点并调衡\\n\ printf(\ 3 在平衡二叉树上删除一个结点并调衡\\n\ printf(\ 0 退出\\n\

printf(\ ________________________________\\n\\n\ printf(\ 请输入所选功能0-3\\n\ scanf(\ return m; }

4．测试 /*主函数*/ void main() {

int input,search; bool taller=0; int shorter=0; BTree T;

T=(BTree)malloc(sizeof(BTNode)); T=NULL; while(1) {

printf(\请选择需要的二叉树操作\\n\ input=menu( ); switch(input) {

case 1:

Adj_balance(T); break; case 2:

printf(\请输入你要增加的关键字\ scanf(\ getchar();

SetAVL(T,search,taller); PrintBT(T); break; case 3:

printf(\请输入你要删除的关键字\ scanf(\ getchar();

DeleteAVL(T,search,shorter); PrintBT(T); break; case 0: break; default:

printf(\输入错误，请重新选择。\ break; }

if(input == 0) break;

printf(\按任意键继续.\ getchar(); } }

测试截图:

1.界面：

2.创建平衡二叉树：

3.增加节点并调衡：

4.删除节点并调衡：

5. 思考与小结

在平衡二叉树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

scanf(\ return m; }

/*主函数*/ void main() {

int input,search; bool taller=0; int shorter=0; BTree T;

T=(BTree)malloc(sizeof(BTNode)); T=NULL; while(1) {

printf(\请选择需要的二叉树操作\\n\ input=menu( ); switch(input) {

case 1:

Adj_balance(T); break; case 2:

printf(\请输入你要增加的关键字\ scanf(\ getchar();

SetAVL(T,search,taller); PrintBT(T); break; case 3:

printf(\请输入你要删除的关键字\ scanf(\ getchar();

DeleteAVL(T,search,shorter); PrintBT(T); break; case 0: break; default:

printf(\输入错误，请重新选择。\ break; }

if(input == 0) break;

printf(\按任意键继续.\ getchar(); } }

本文来源：https://www.bwwdw.com/article/togd.html

相关文章：

正在阅读：

5营销环境分析01-15

三年级上册品德一课一练第一单元第一课天生我材必有用浙教版12-14

我能小学作文06-15

一年级下册《求比一个数多几或少几的数》的教学反思07-28

粤教版小学四年级品德与社会期末复习总结03-18

中药鉴定学复习资料01-29

上一篇：军用电子元器件的质量等级下一篇：基于单片机控制直流电机调速系统毕业设计论文