数据结构课程设计平衡二叉树.docx

数据结构课程设计平衡二叉树.docx

《数据结构课程设计平衡二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计平衡二叉树.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构课程设计平衡二叉树

数据结构课程设计：

平衡二叉树

1课程设计的目的和内容

1

课程设计目的11.1

1.2主要内容1

2课程设计分析2

2.1程序的目的和要求2

2.2程序的主要数据和功能模块2

3详细设计5

3.1程序主要功能模块的伪代码算法5

3.2程序主要流程图8

4测试数据与测试结果95

程序的使用和改进14

5.1用户使用说明14

5.2程序的改进14

6课程设计小结157

参考文献15

1平衡二叉树

1课程设讣的LI的和内容

1.1课程设计目的

复习二义树的三义链表存储结构和遍历方法。

掌握二义排序树的特点和生成方法。

掌握平衡二义树四种不平衡形态的判定和旋转为平衡的方法。

1.2主要内容

（1）输入结点数据，构造二义树的结点，按二义排序树的规则插入该结点到三义链表中；

（2）通过插入函数InsertAVL（BSTNode*&T,intkey）插入新结点到二义树中，并递归调用插入函数本身，直到正确插入到二义树中，并返回上次递归，每返回上次递归一次同时判断其平衡度bf,找到最小不平衡树的根结点Po

（3）判断最小不平衡树的平衡因子（bf）的值，若bf>l,则调用左平衡函数LeftBalanceO,若bf<~l,则调用右平衡函RightBalance（）,再判断根结点p的左（右）孩子的平衡因子（共有LL型、LR型、RR型、RL型四种），然后判定得到的不平衡形态调用不同的旋转函数即可将其重新调整为平衡二义树；

（4）重复步骤

（1）

（2）（3）,直到所有结点都插入到该平衡二义树中为止；

（5）输出该二义树的前序（或者后序）序列和中序序列，手工恢复出该二义树，检验其是否为平衡二义树;并验证其中序序列的有序性。

2平衡二叉树

2课程设计分析

2.1程序的LI的和要求

（1）本程序演示平衡二义树的插入，以及AVL的前序遍历和中序遍历，并且验证其中序遍历有序性。

（2）对平衡二义树出现的的的LL,LR,RL,RR四种情况进行处理是其平衡。

（3）接着要实现平衡二义树的插入，其中根据平衡二义树插入的算法要不停的把插入的元素平衡地插入，需要判断平衡并调用左右旋转函数，更新平衡二义树

2.2程序的主要数据和功能模块

（1）程序主要数据

半衡二义树左右子树的深度:

ldep,rdep

半衡因子：

bf二TreeDepth（ldep）-TreeDepth（rdep）

（2）程序主要功能模块

求树深函数：

TreeDepth（）

左（右）旋函数：

L_Rotate（）,R_Rotate（）

左右平衡函数：

LeftBalance（）,RightBalance（）

插入函数：

InsertAVL（）

前（中）序遍历:

Preorder（）,Inorder（）

输出二义树函数Output（）

（3）程序主要功能模块之间的调用

插入函数InsertAVL（BSTNode*&T,intkey）要调用左平衡函数

LeftBalance（）和右平衡函数RightBalance（）,左右平衡函数要调用左旋函数R_Rotate（）和右旋函数L_Rotate（）

（4）平衡二义树不平衡形态分析

1）LL型：

新结点1插在结点3的左孩子的左子树里。

调整方法见图2.1。

图

中以结点2为轴心，将结点结点3从结点2的右上方转到结点2的右下侧，使结点3成为结点2的右孩子。

3平衡二叉树

32

2

13

1

LL型

图2.1

2）RR型：

新结点3插在结点1的右孩子的右子树里。

调整方法见图2.2.2。

图中以结点2为轴心，将结点1从结点2的左上方转到结点2的左下侧，使结点1

的左孩子。

成为结点2

1

2

2

13

3RR型

图2.2

3）LR型：

新结点2插在结点3的左孩子的右子树里。

调整方法见图2.3。

分为两步进行:

第一步以结点2为轴心，将结点1从结点2的左上方转到结点2的左下侧，使结点1成为结点2的左孩子，结点2成为结点3的左孩子。

第二步跟LL型一样处理（应以结点2为轴心）。

4平衡二叉树

33

2

12

13

21

LR型

图2.3

4）RL型：

2插在1的右孩子的左子树里。

调整方法见图2.4。

分为两步进行：

新结点

第一步以结点2为轴心，将结点3从结点2的右上方转到结点2的右下侧，使结点3成为结点2的右孩子，结点2成为结点1的右孩子。

第二步跟RR型一样处理（应以结点2为轴心）。

11

2

32

13

23

RL型

图2.4

5平衡二叉树

3详细设计

3.1程序主要功能模块的伪代码算法

（1）对以*P为根的二义排序树作右旋处理

voidR_Rotate（BSTree&p）{

BSTNode*lc;

lc=p->lchild;

p~>lchild=lc->rchiId;

lc~>rchild=p;

P二lc;

}

对以为根的二义排序树作左旋处理

voidL_Rotate（BSTree&p）{

BSTNode*rc;

rc=p->rchild;

p->rchild=rc->lchiId;

rc->lchild=p;

P=rc;

}

（2）对以指针T所指结点为根的二义排序树作左平衡旋转处理void

LeftBalance（BSTree&T）{

intbf;

BSTNode*lc;

lc=T->lchild;

bf=TreeDepth（lc->lchiId）-TreeDepth（lc->rchild）:

switch（bf）

{

case+1:

//LL

R_Rotate（T）;

break;

case-1:

//LR

L_Rotate（T~>lchiId）;

6平衡二义树

R_Rotate（T）;

}

}

对以指针T所指结点为根的二义排序树作右平衡旋转处理void

RightBalance（BSTree&T）

{

intbf;

BSTNode*rc;

rc=T->rchild;

bf=TreeDepth（rc->lchiId）-TreeDepth（rc->rchild）;switch（bf）

{

caseT:

//RL

L_Rotate（T）;

break;

case+1:

//RR

R_Rotate（T->rch订d）;

L_Rotate（T）;

}

}

（4）插入函数

voidInsertAVL（BSTNode*&T,intkey）

{

intbf;

辻（⑴

T=（BSTNode*）malloc（sizeof（BSTNode））;

T->key=key;

T->1chi1d二T-〉rchi1d二NULL;

}

else

{

if（key—T->key）

{

printf（，z点已存在\n"）;

7平衡二叉树

return;

}

else辻（keykey）//*在*丁的左子树中进行搜索

{

InsertAVL（T->lch订d,key）;

bf=TreeDepth（T->lchiId）-TreeDepth（T~>rchild）;

if（bf>l）

LeftBalance（T）;

}

else//*在*T的右子树进行搜索

{

InsertAVL（T->rchiId,key）;

bf=TreeDepth（T->lchiId）-TreeDepth（T~>rchiId）;

辻（bf<-l）

RightBalance（T）;

}

}

}

8平衡二叉树

3.2程序主要流程图

开始

23

switch（choice）

1

Preorder（T）Inorder（T）

InsertAVL（T,key）

输入key

N

T=NULL结束

Y0InsertAVL（T,key）

T->key=keyswitch（choice）

key~T->key

N

YN

keykey点已存在

Y

InsertAVL（T->lchild,key）Bf>l

>

InsertAVL（T->rchild,key）LeftBalance（T）

RightBalance（T）Bf〈-1

>

9平衡二义树

4测试数据与测试结果

图4-1程序主界面

3J£

平衝二叉忧

Press

B•心\

山小处删毎EW“J

IS1S

12-34-0人久/入、人

图4-2退出程序

10平衡二义树

JojxJ

it^AI插入元素的关前字《鑿数片3

二叉協树为：

根结占启上层为左干树讣层为右于删

3

NULL

NULL

蠡責锂亀左子树•下层为右子粉

3

2

NULL

NULL

NULL

赧缺略字*敲It?

&号树，下层为右刑

NULL

NULL

3

HULL

NULL

墮堑入你要遒行的操作：

2

翩臨離3

4

图4-3LL型

11平衡二义树

直鬻龍勇左子•灿下层为右子劭

3

NULL

NULL

籀建I瞬険理如硕舊鶴里皺左子悼下层为右子树,

3

1

NIJUI.

NULL

NULL

譎鹽龍另左子树丁层为右子树f

2

1

NULL

NULL

3

HULL

NUM.

-•1••2

營^

的••的••

行为行为

聲要斤

图4-4LR型

直鬻龍勇左子•灿下层为右子劭

3

NULL

NULL

籀建I瞬険理映硕舊鶴里皺左子悼下层为右子树,

3

2

NIJUI.

NULL

NULL

敷礬瞬翳字/5

譎鹽龍另左子树丁层为右子树f

2

1

NULL

NULL

3

HULL

NUM.

-•1••2

營^

的••的••

行为行为

聲要斤

图4-5RR型

*C*KU^ersKaei\8«skrt«p\B•baPXD1IIB6UM-A.¥L«x

就翼里鶴左子树•下层为右子粉

1

NULL

NULL

誡醤里欝左子怫下层为右子丽

1

NULL

3

NULL

NULL

諂蠶里欝左子树•下层为石子树?

HULL

HULL

NULLMULL

图4-6RL型

14平衡二叉树

5程序的使用和改进

5.1用户使用说明

（1）本程序调用时当按1时，进入插入操作，每输入一个元素就把它插入到二

义树中，然后进行左平衡，右平衡的判断，重新把二叉树变为平衡二义树。

平衡二义树的显示输出为输出根结点后根接着输出的上层为左子树，下层为右子树。

（2）当选择2时，进行平衡二叉树的前序遍历。

（3）当选择3时，进行平衡二叉树的中序遍历。

（4）若插入好二义树后，选择4清屏，原来插入的二义树结点数据仍然保留，继续插入需要注意不要插入已经存在的结点.

（5）选择0退出程序

5.2程序的改进

（1）可以加入平衡二义树的删除操作；

（2）可以加入平衡二义树的查找操作；

（3）这次课程设计没有找到很好的显示平衡二义树的方式，选用的显示方式不是很直观。

15平衡二叉树

6课程设计小结

这次数据结构课程设计是平衡二义树相关，通过课程设讣对二义排序树有了更进一步的深入了解以及平衡二义树的四种不平衡形态的分析，处理四种不平衡形态（LL,LR,RL,RR）的方式，通过左旋及右旋函数实现左平衡和右平衡，并验证了其中序序列有序性〜

这次课程设计主要的思想就是递归，首先是插入函数的递归，判断所要插入的数据跟原来树的根结点比较，比根结点数据小，则递归调用插入函数继续在其左子树中插入，比根结点的数据大，则递归调用插入函数继续在其右子树中插入，直到找到合适的位置，则插入成功。

插入成功后返回上一层次的递归，并且求出相当于插入结点的双亲结点的平衡因子，依次返回，找到第一个不平衡的结点，再做相应的调整，重复上述过程，直到整个二义树都平衡。

这次设讣没有在结构体中设置平衡因子，所以不需要判断和调整经过平衡处理后的结点的平衡因子。

此外，程序增加了二义树的显示功能，也是运用了递归的思想，虽然不是很直观，但是比没有显示略微好点。

笫一次做的时候，在结构体中定义了平衡因子，后面的程序就显得累赘了，在王老师的细心指导下，改进了程序，改用求树深的函数，就可以通过这个函数（左孩子的深度-右孩子的深度）来求结点的平衡因子了，参考了老师推荐的严蔚敬的数据结构，对我的帮助很大。

，虽然书上关于平衡二叉树的内容比较少，但是有疑难时可以先自己尝试解决，解决不了可以查询相关资料，咨询老师。

通过这次数据结构的课程设讣，我对平衡二义树的理解更深刻了，并且了解到了课程设计报告的要求，对撰写实验报告的格式，内容有了大致的了解，相信对以后的论文撰写什么的会有很大的帮助。

16平衡二义树

7参考文献

[1]陈元春，张亮，王勇编著.实用数据结构基础..2007年8月第2版.中国铁道出版社

[2]严蔚墩，吴伟民编著.数据结构•清华大学出版社