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

数据结构实验报告

题目：平衡二叉树

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

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;