-
^.
实验报告
课程名称
数据结构实验
学
院
计算机学院
专业班级
计科
9
班
学
号
学生姓名
指导教师
苏庆
2015
年
7
月
6
日
^.
^.
1.
题目
:
平衡二叉树
ADT BBSTree{
数据对象
：
D
＝
{ ai | ai
∈
ElemSet, i=1,2,...,n, n≥0 }
数据关系
：
R1
＝
{
∈
D, i=2,...,n }
基本操作
：
BBSTree MakeBBSTree( )
操作结果：创建好一棵树
返回：将创建好的树返回
Status
InsertAVL(BBSTree
&T,
RcdType
e,
Status
&taller)
初始条件：树
T
已存在，
e
存在，
taller
为真
操作结果：将
e
插入到
T
中
返回：成功
TRUE
，失败
FALSE
Status
DeleteAVL(BBSTree
&t,
RcdType
e,
Status
&shorter)
初始条件：树
T
已存在，< br>e
存在，
shorter
为真
操作结果：将
e
从
T
中删除
返回：成功
TRUE
，失败
FALSE
BBSTree SearchAVL(BBSTree T, RcdType e)
初始条件：树
T
已存在，
e
存在
操作结果：从
T
中找到
e
返回：以
e
为根节点的树
void L_Rotate(BBSTree &p)
初始条件：树
p
存在
操作结果：对
p
左旋操作
void R_Rotate(BBSTree &p)
初始条件：树
p
存在
操作结果：对
p
右旋操作
void LeftBalance(BBSTree &T)
初始条件：树
T
存在
操作结果：对
T
左平衡操作
void RightBalance(BBSTree &T)
初始条件：树
T
存在
操作结果：对
T
右平衡操作
void ExchangeSubTree(BBSTree &T)
初始条件：树
T
存在
操作结果：对
T
所有左右孩子交换
int BBSTreeDepth(BBSTree T)
初始条件：树
T
已存在
操作结果：求树
T
的深度
返回：树的深度
BBSTree Combine2Tree(BBSTree T1, BBSTree T2)
初始条件：树
T1
和
T2
已存在
^.
操作结果：将
T1
和
T2
合并
返回：合并后的树
Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2,
BBSTree &Tt3, int x)
初始条件：树
Tt1
，
Tt2
，
Tt3
已存在，
x
存在
操作结果：将
Tt1
分裂成
Tt2
和
Tt3
返回：以
e
为根节点的树
Status PreOrder_RecTraverse(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
进行递归先序遍历输出
返回：成功
TRUE
失败
FALSE
Status InOrder_RecTraverse(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
进行递归中序遍历输出
返回：成功
TRUE
失败
FALSE
Status LastOrder_RecTraverse(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
进行递归后序遍历输出
返回：成功
TRUE
失败
FALSE
void PreOrderTravese_I(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
进行非递归先序遍历输出
void InOrderTraverse_I(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
进行非递归中序遍历输出
void LastOrderTravese_I(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
进行非递归后序遍历输出
void LevelOrederTraverse_Print(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
进行非递归层次遍历输出
void BraNotationPrint(BBSTree T)
初始条件：树
T
已存在
操作结果：对树
T
用括号表示法输出
}ADT BBSTree
2.
存储结构定义
#include
#include
#define OVERFLOW -1
#define OK 1
^.
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define LH +1
//
左高
#define EH 0
//
等高
#define RH -1
//
右高
typedef int RcdType;
typedef int Status;
/*
平衡二叉树结构体
*/
typedef struct BBSTNode{
RcdType data;
int bf;
BBSTNode *lchild, *rchild;
}BBSTNode,*BBSTree;
3.
算法设计
/*
求平衡二叉树的深度
*/
int BBSTreeDepth(BBSTree T){
int depthLeft, depthRight;
if(NULL==T) return 0;
else{
depthLeft = BBSTreeDepth(T->lchild);
depthRight = BBSTreeDepth(T->rchild);
return 1+(depthLeft > depthRight ? depthLeft : depthRight);
}
}
/*
交换二叉树所有结点的左右子树
*/
void ExchangeSubTree(BBSTree &T){
BBSTree temp;
if(NULL!=T){
ExchangeSubTree(T->lchild);
//
使用递归交换左子树
ExchangeSubTree(T->rchild);
//
使用递归交换右子树
if((T->lchild!=NULL)||(T->rchild!=NULL)){
//
如果
T
的子树有一个不
为空，则交换左右子树
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}
^.
}
}
/*
左旋调整
*/
void L_Rotate(BBSTree &p){
BBSTree rc = p->rchild;
p->rchild = rc->lchild;
rc->lchild = p;
p = rc;
}
/*
右旋调整
*/
void R_Rotate(BBSTree &p){
BBSTree lc = p->lchild;
p->lchild = lc->rchild;
lc->rchild = p;
p = lc;
}
/*
左平衡处理操作
*/
void LeftBalance(BBSTree &T){
BBSTree 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);
break;
}
}
/*
右平衡处理操作
*/
void RightBalance(BBSTree &T){
^.
BBSTree rd,lc;
rd=T->rchild;
switch(rd->bf)
{
case RH:
T->bf=rd->bf=EH; L_Rotate(T); break;
case LH:
lc=rd->lchild;
switch(lc->bf){
case RH:T->bf=LH;rd->bf=EH;break;
case EH:T->bf=rd->bf=EH;break;
case LH:T->bf=EH;rd->bf=RH;break;
}
lc->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}
}
/*
平衡二叉树的插入操作
*/
Status InsertAVL(BBSTree &T, RcdType e, Status &taller){
if(NULL==T){
T = (BBSTree)malloc(sizeof(BBSTNode));
T->data = e;
T->bf = EH;
T->lchild = NULL;
T->rchild = NULL;
}else if(e==T->data){ //
书中已存在和
e
相等的结点
taller = FALSE; return FALSE;
}else if(e
if(FALSE==InsertA
VL(T->lchild, e, taller)) return FALSE;
if(TRUE==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(FALSE==InsertA
VL(T->rchild, e, taller)) return FALSE;
if(TRUE==taller){
switch(T->bf){
^.
case LH: T->bf = EH; taller = FALSE; break;
case EH: T->bf = RH; taller = TRUE; break;
case RH: RightBalance(T); taller = FALSE; break;
}
}
}
return TRUE;
}
/*
平衡二叉树的删除操作
*/
Status DeleteA
VL(BBSTree &t, RcdType e, Status &shorter){
//
当被删结点是有两个孩子，且其前驱结点是左孩子时，
tag=1
static int tag = 0;
if(t == NULL){
return FALSE;
//
如果不存在元素，返回失败
}else if(e==t->data){
BBSTNode *q = NULL;
//
如果该结点只有一个孩子，则将自子树取代该结点
if(t->lchild == NULL){
q = t;
t = t->rchild;
free(q);
shorter = TRUE;
}
else if(t->rchild == NULL){
q = t;
t = t->lchild;
free(q);
shorter = TRUE;
}
//
如果被删结点有两个孩子，则找到结点的前驱结点，
//
并将前驱结点的值赋给该结点，然后删除前驱结点
else{
q = t->lchild;
while(q->rchild){
q = q->rchild;
}
t->data = q->data;
if(t->lchild->data==q->data){
tag = 1;
}
DeleteA
VL(t->lchild, q->data, shorter);
if(tag==1){
BBSTree r = t->rchild;
^.
if(NULL==r) t->bf = 0;
else{
switch(r->bf){
case EH: t->bf=-1;break;
default: RightBalance(t);break;
}
}
}
}
}else if(e
//
左子树中继续查找
if(!DeleteA
VL(t->lchild, e, shorter)){
return FALSE;
}
//
删除完结点之后，调整结点的平衡因子
if(shorter&&(tag==0))
{
switch(t->bf){
case LH:
t->bf = EH;
shorter = TRUE;
break;
case EH:
t->bf = RH;
shorter = FALSE;
break;
//
如果本来就是右子树较高，删除之后就不平衡，需要做右平
衡操作
case RH:
RightBalance(t);
//
右平衡处理
if(t->rchild->bf == EH)
shorter = FALSE;
else
shorter = TRUE;
break;
}
}
}else if(e>t->data){ //
右子树中继续查找
if(!DeleteA
VL(t->rchild, e, shorter)){
return FALSE;
}
//
删除完结点之后，调整结点的平衡因子
if(shorter&&(tag==0))
{
switch(t->bf){
case LH:
LeftBalance(t);
//
左平衡处理
^.
if(t->lchild->bf == EH)//
注意这里，画图思考一下
shorter = FALSE;
else
shorter = TRUE;
break;
case EH:
t->bf = LH;
shorter = FALSE;
break;
case RH:
t->bf = EH;
shorter = TRUE;
break;
}
}
if(tag==1){
int depthLeft = BBSTreeDepth(t->lchild);
int depthRight = BBSTreeDepth(t->rchild);
t->bf = depthLeft - depthRight;
}
}
return TRUE;
}
/*
平衡二叉树的查找操作
*/
BBSTree SearchA
VL(BBSTree T, RcdType e){
if(T==NULL) return NULL;
if(e==T->data){
return T;
}else if(e>T->data){
return SearchA
VL(T->rchild, e);
}else {
return SearchA
VL(T->lchild, e);
}
}
/*
获取输入存到数组
a*/
Array GetInputToArray(){
Array head, p, q;
char k;
head = p = q = NULL;
int m;
^.
if(k!='n'){
scanf(
p = (ArrayNode*)malloc(sizeof(ArrayNode));
head = p;
p->data = m;
k = getchar();
}
while(k!='n'){
scanf(
q = (ArrayNode*)malloc(sizeof(ArrayNode));
q->data = m;
p->next = q;
p = p->next;
k = getchar();
}
if(p!=NULL){
p->next = NULL;
}
return head;
//
返回存放数据的头指针
}
/*
根据输入的字符串建一棵平衡二叉树
*/
BBSTree MakeBBSTree( ){
int i=0;
Status taller = TRUE;
BBSTree T = NULL;
Array a;
a = GetInputToArray();
while(a!=NULL){
taller = TRUE;
InsertA
VL(T, a->data, taller);
a = a->next;
}
return T;
}
/*
递归先序遍历
*/
Status PreOrder_RecTraverse(BBSTree T){
if(NULL==T) return OK;
printf(
PreOrder_RecTraverse(T->lchild);
PreOrder_RecTraverse(T->rchild);
}
^.
/*
递归中序遍历
*/
Status InOrder_RecTraverse(BBSTree T){
if(T->lchild)
InOrder_RecTraverse(T->lchild);
printf(
if(T->rchild)
InOrder_RecTraverse(T->rchild);
}
/*
递归后序遍历
*/
Status LastOrder_RecTraverse(BBSTree T){
if(T->lchild)
LastOrder_RecTraverse(T->lchild);
if(T->rchild)
LastOrder_RecTraverse(T->rchild);
printf(
}
/*
找到最左结点
*/
BBSTree GoFarLeft(BBSTree T, LStack &S){
if(NULL==T) return NULL;
while(T->lchild!=NULL){
Push_LS(S, T);
T = T->lchild;
}
return T;
}
/*
非递归中序遍历
*/
void InOrderTraverse_I(BBSTree T){
LStack S;
InitStack_LS(S);
BBSTree p = NULL;
p = GoFarLeft(T, S);
while(p!=NULL){
printf(
if(p->rchild!=NULL){
p = GoFarLeft(p->rchild, S);
}
else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S, p);
else p = NULL;
}
}
^.
BBSTree VisitFarLeft(BBSTree T, LStack &S){
if(NULL==T) return NULL;
//
如果
T
为空，则返回空
printf(
//
先序，先读取结点数据
while(T->lchild!=NULL){
Push_LS(S, T);
//
入栈
T = T->lchild;
//
遍历下一个左子树
printf(
//
下一个结点的读取数据
}
return T;
}
/*
非递归先序遍历
*/
void PreOrderTravese_I(BBSTree T){
LStack S;
InitStack_LS(S);
BBSTree p;
p = VisitFarLeft(T, S);
//
先将左边的数据先序读取
while(p!=NULL){
if(p->rchild!=NULL)
//
如果最左下结点的右子树不为空
p = VisitFarLeft(p->rchild, S);
//
执行遍历该结点的左子树
else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S,p);
//
如果
S
不为空栈，
出栈
else p = NULL;
//
如果为空栈，
p
赋予空
}
}
/*
非递归后序遍历
*/
void LastOrderTravese_I(BBSTree root){
BBSTree p = root;
BBSTree stack[30];
int num=0;
BBSTree have_visited = NULL;
while(NULL!=p||num>0){
while(NULL!=p){
stack[num++]=p;
p=p->lchild;
}
p=stack[num-1];
if(NULL==p->rchild||have_visited==p->rchild){
printf(
num--;
have_visited=p;
p=NULL;
}
^.
else{
p=p->rchild;
}
}
printf(
}
/*
非递归层次遍历输出一棵二叉树
*/
void LevelOrederTraverse_Print(BBSTree T){
if(T==NULL){
printf(
}
if(T!=NULL){
LQueue Q;
InitQueue_LQ(Q);
BBSTree p = T;
printf(
EnQueue_LQ(Q,p);
while(DeQueue_LQ(Q,p)){
if(p->lchild!=NULL){
printf(
EnQueue_LQ(Q, p->lchild);
}
if(p->rchild!=NULL){
printf(
EnQueue_LQ(Q, p->rchild);
}
}
}
}
/*
括号表示法输出平衡二叉树
*/
void BraNotationPrint(BBSTree T){
if(NULL==T){
printf(
空
!
}else{
if(T!=NULL){
if(T!=NULL){
printf(
if(T->lchild||T->rchild){
printf(
}
}
}
^.
if(T->lchild||T->rchild){
if(T->lchild){
BraNotationPrint(T->lchild);
}else if(T->rchild){
printf(
}
printf(
if(T->rchild){
BraNotationPrint(T->rchild);
}else if(T->lchild){
printf(
}
printf(
}
}
}
/*
将一棵树转换为一个数组
*/
Array GetArrayFromTree(BBSTree T){
Status firstTime = TRUE;
Array head = NULL;
ArrayNode *b
= NULL;
ArrayNode *q = NULL;
if(T==NULL){
printf(
}
if(T!=NULL){
LQueue Q;
InitQueue_LQ(Q);
BBSTree p = T;
q = (Array)malloc(sizeof(ArrayNode));
q->data = p->data;
if(firstTime==TRUE){
head = q;
firstTime = FALSE;
b = q;
}else{
b->next = q;
b = b->next;
}
EnQueue_LQ(Q,p);
while(DeQueue_LQ(Q,p)){
if(p->lchild!=NULL){
^.
q = (Array)malloc(sizeof(ArrayNode));
q->data = p->lchild->data;
b->next = q;
b = b->next;
EnQueue_LQ(Q, p->lchild);
}
if(p->rchild!=NULL){
q = (Array)malloc(sizeof(ArrayNode));
q->data = p->rchild->data;
b->next = q;
b = b->next;
EnQueue_LQ(Q, p->rchild);
}
}
if(b!=NULL){
b->next = NULL;
}
}
return head;
}
/*
将两棵平衡二叉树合并成一颗平衡二叉树
*/
BBSTree Combine2Tree(BBSTree T1, BBSTree T2){
Status taller = TRUE;
Array a = NULL;
a = GetArrayFromTree(T2);
while(a!=NULL){
taller = TRUE;
InsertA
VL(T1, a->data, taller);
a = a->next;
}
return T1;
}
/*
将一棵平衡二叉树分裂成两棵平衡二叉树
*/
/*
参数
1
：要进行分裂的树
参数
2
：分裂出来的小于等于
x
的子树
参数
3
：分裂出来的
大于
x
的子树
参数
4
：关键字
x
*/
Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2, BBSTree &Tt3, int x){
Array a = NULL;
Status taller;
^.
a = GetArrayFromTree(Tt1);
if(Tt1==NULL) return FALSE;
else{
while(a!=NULL){
if(a->data<=x){
taller = TRUE;
InsertA
VL(Tt2, a->data, taller);
a = a->next;
}else {
taller = TRUE;
InsertA
VL(Tt3, a->data, taller);
a = a->next;
}
}
}
return TRUE;
}
4.
测试
(1)
建树操作
测试代码
:
测试数据：
1 2 3 4 5 6
测试结果：
^.
(2)
插入操作
测试代码：
测试数据：
1 2 3 4 5 6
插入
8
测试结果
：
测试数据：
1 2 3 4 5 6
插入
4
测试结果
：
^.
(3)
删除操作
测试代码：
测试数据：
1 2 3 4 5 6
删除
6
测试结果：
测试数据：
1 2 3 4 5 6
删除
2
测试结果：
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:24，由作者提供，不代表本网站立场，转载请注明出处：https://www.bjmy2z.cn/gaokao/565089.html