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

1、数据结构课程设计：平衡二叉树目录1课程设计的目的和内容1课程设计目的1 1.11.2主要内容12课程设计分析22.1程序的目的和要求22.2程序的主要数据和功能模块23详细设计53. 1程序主要功能模块的伪代码算法53. 2程序主要流程图84测试数据与测试结果95程序的使用和改进 145. 1用户使用说明145.2程序的改进146课程设计小结157参考文献151平衡二叉树1课程设讣的LI的和内容1.1课程设计目的复习二义树的三义链表存储结构和遍历方法。掌握二义排序树的特点和生成方法。掌握平衡二义树四种不平衡形态的判定和旋转为平衡的方法。1.2主要内容(1) 输入结点数据，构造二义树的结点，按二

2、义排序树的规则插入该结点到三 义链表中；(2) 通过插入函数InsertAVL(BSTNode* &T, int key)插入新结点到二义树中， 并递归调用插入函数本身，直到正确插入到二义树中，并返回上次递归，每返回上 次递归一次同时判断其平衡度bf,找到最小不平衡树的根结点Po(3) 判断最小不平衡树的平衡因子(bf)的值，若bfl,则调用左平衡函数 LeftBalanceO ,若bflchild;plchild=lc-rchiId;lcrchild=p;P 二 lc;对以为根的二义排序树作左旋处理void L_Rotate(BSTree &p) BSTNode* rc;rc=p-rchil

3、d;p-rchild=rc-lchiId;rc-lchild=p;P=rc;(2)对以指针T所指结点为根的二义排序树作左平衡旋转处理voidLeftBalance(BSTree &T) int bf;BSTNode* lc;lc=T-lchild;bf = TreeDepth (lc-lchiId) - TreeDepth(lc-rchild):switch(bf)case +1: /LLR_Rotate(T);break;case -1: /LRL_Rotate(TlchiId);6平衡二义树R_Rotate(T);对以指针T所指结点为根的二义排序树作右平衡旋转处理voidRightBala

4、nce (BSTree &T)int bf;BSTNode* rc;rc=T-rchild;bf = TreeDepth (rc-lchiId) - TreeDepth(rc-rchild); switch(bf)case T: /RLL_Rotate(T);break;case +1: /RRR_Rotate(T-rch订d);L_Rotate(T);(4) 插入函数void InsertAVL(BSTNode* &T, int key)int bf;辻(T=(BSTNode*)malloc(sizeof(BSTNode);T-key=key;T-1chi1d二T-rchi1d二NULL;e

5、lseif (keyT-key)printf (，z点已存在n);7平衡二叉树return;else辻(keykey) /*在*丁的左子树中进行搜索InsertAVL(T-lch订d, key);bf = TreeDepth(T-lchiId) - TreeDepth(Trchild);if(bfl)LeftBalance (T);else /*在*T的右子树进行搜索InsertAVL(T-rchiId, key);bf = TreeDepth(T-lchiId) - TreeDepth(TrchiId);辻(bfkey=key switch(choice)keyT-keyNY Nkeykey

6、点已存在YInsertAVL(T-lchild, key) BflInsertAVL(T-rchild,key) LeftBalance(T)RightBalance (T) Bf-19平衡二义树4测试数据与测试结果图4-1程序主界面3J平衝二叉忧Press an ke to cont inueB 心山小处删毎EW “JI S 1 S12-34-0 人久/入、人图4-2退出程序10平衡二义树JojxJitAI插入元素的关前字鑿数片3二叉協树为：根结占启上层为左干树讣层为右于删3NULLNULL蠡責锂亀左子树下层为右子粉32NULLNULLNULL赧缺略字* 敲It?&号树，下层为右刑NULLN

7、ULL3HULLNULL墮堑入你要遒行的操作：2翩臨離34图4-3 LL型11平衡二义树N ：aci4VL *麹字輕心3凶Z3直鬻龍勇左子灿下层为右子劭3NULLNULL籀建I瞬険理如 硕舊鶴里皺左子悼下层为右子树,31NIJUI.NULLNULL譎鹽龍另左子树丁层为右子树f21NULLNULL3HULLNUM.- 1 2營的的行为行为聲要斤图4-4 LR型N ：aci4VL *麹字輕心3凶Z3直鬻龍勇左子灿下层为右子劭3NULLNULL籀建I瞬険理映 硕舊鶴里皺左子悼下层为右子树,32NIJUI.NULLNULL敷礬瞬翳字/5譎鹽龍另左子树丁层为右子树f21NULLNULL3HULLNUM.

8、- 1 2營的的行为行为聲要斤图4-5 RR型*C * KUersK aei 8skrtp B baPXD1IIB6UM-A.L xa 1就翼里鶴左子树下层为右子粉1NULLNULL誡醤里欝左子怫下层为右子丽1NULL3NULLNULL諂蠶里欝左子树 下层为石子树?HULLHULLNULL MULL入你豊遒彳亍的操牡2帶雷葺論话作;3 遍历序列郑1 2(；m V -3图4-6 RL型14平衡二叉树5程序的使用和改进5. 1用户使用说明(1) 本程序调用时当按1时，进入插入操作，每输入一个元素就把它插入到二义树中，然后进行左平衡，右平衡的判断，重新把二叉树变为平衡二义树。平衡二 义树的显示输出为

9、输出根结点后根接着输出的上层为左子树，下层为右子树。(2) 当选择2时，进行平衡二叉树的前序遍历。(3) 当选择3时，进行平衡二叉树的中序遍历。(4) 若插入好二义树后，选择4清屏，原来插入的二义树结点数据仍然保留， 继续插入需要注意不要插入已经存在的结点.(5) 选择0退出程序5.2程序的改进(1) 可以加入平衡二义树的删除操作；(2) 可以加入平衡二义树的查找操作；(3) 这次课程设计没有找到很好的显示平衡二义树的方式，选用的显示方式不 是很直观。15平衡二叉树6课程设计小结这次数据结构课程设计是平衡二义树相关，通过课程设讣对二义排序树有了更 进一步的深入了解以及平衡二义树的四种不平衡形态

10、的分析，处理四种不平衡形态 (LL, LR, RL, RR)的方式，通过左旋及右旋函数实现左平衡和右平衡，并验证了其中 序序列有序性这次课程设计主要的思想就是递归，首先是插入函数的递归，判断所要插入的 数据跟原来树的根结点比较，比根结点数据小，则递归调用插入函数继续在其左子 树中插入，比根结点的数据大，则递归调用插入函数继续在其右子树中插入，直到 找到合适的位置，则插入成功。插入成功后返回上一层次的递归，并且求出相当于 插入结点的双亲结点的平衡因子，依次返回，找到第一个不平衡的结点，再做相应 的调整，重复上述过程，直到整个二义树都平衡。这次设讣没有在结构体中设置平 衡因子，所以不需要判断和调整经过平衡处理后的结点的平衡因子。此外，程序增加了二义树的显示功能，也是运用了递归的思想，虽然不是很直 观，但是比没有显示略微好点。笫一次做的时候，在结构体中定义了平衡因子，后面的程序就显得累赘了，在 王老师的细心指导下，改进了程序，改用求树深的函数，就可以通过这个函数（左 孩子的深度-右孩子的深度）来求结点的平衡因子了，参考了老师推荐的严蔚敬的数 据结构，对我的帮助很大。，虽然书上关于平衡二叉树的内容比较少，但是有疑难 时可以先自己尝试解决，解决不了可以查询相关资料，咨