数据结构课程设计：平衡二叉树目录1 课程设计的目的和内容..............................................1课程设计目的 ................................................ 1 1.11.2 主要内容 (1)2 课程设计分析 (2)2.1 程序的目的和要求 (2)2.2 程序的主要数据和功能模块 (2)3 详细设计 (5)3.1 程序主要功能模块的伪代码算法 (5)3.2 程序主要流程图 (8)4 测试数据与测试结果................................................ 9 5 程序的使用和改进. (14)5.1 用户使用说明 (14)5.2 程序的改进 (14)6 课程设计小结..................................................... 15 7 参考文献 (15)1 平衡二叉树1 课程设计的目的和内容1.1 课程设计目的复习二叉树的三叉链表存储结构和遍历方法。
掌握二叉排序树的特点和生成方法。
掌握平衡二叉树四种不平衡形态的判定和旋转为平衡的方法。
1.2 主要内容(1)输入结点数据，构造二叉树的结点，按二叉排序树的规则插入该结点到三叉链表中;(2)通过插入函数InsertAVL(BSTNode* &T,int key)插入新结点到二叉树中，并递归调用插入函数本身，直到正确插入到二叉树中，并返回上次递归，每返回上次递归一次同时判断其平衡度bf，找到最小不平衡树的根结点p。
(3)判断最小不平衡树的平衡因子(bf)的值，若bf>1, 则调用左平衡函数LeftBalance()，若bf<-1，则调用右平衡函RightBalance()，再判断根结点p的左(右)孩子的平衡因子(共有LL型、LR型、RR型、RL型四种)，然后判定得到的不平衡形态调用不同的旋转函数即可将其重新调整为平衡二叉树;(4)重复步骤(1)(2)(3)，直到所有结点都插入到该平衡二叉树中为止;(5)输出该二叉树的前序(或者后序)序列和中序序列，手工恢复出该二叉树，检验其是否为平衡二叉树;并验证其中序序列的有序性。
2 平衡二叉树2 课程设计分析2.1 程序的目的和要求(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,int key)要调用左平衡函数LeftBalance()和右平衡函数RightBalance()，左右平衡函数要调用左旋函数R_Rotate()和右旋函数L_Rotate()(4)平衡二叉树不平衡形态分析1) LL 型:新结点 1 插在结点 3 的左孩子的左子树里。
调整方法见图2.1。
图中以结点2为轴心，将结点结点3从结点2 的右上方转到结点2 的右下侧，使结点 3成为结点2 的右孩子。
3 平衡二叉树3 221 31LL型图2.12)RR 型:新结点3 插在结点 1 的右孩子的右子树里。
调整方法见图2.2.2。
图中以结点 2 为轴心，将结点1 从结点2的左上方转到结点2 的左下侧，使结点1 的左孩子。
成为结点21221 33 RR型图2.23)LR 型:新结点 2 插在结点 3的左孩子的右子树里。
调整方法见图2.3 。
分为两步进行:第一步以结点 2 为轴心，将结点 1 从结点2 的左上方转到结点2 的左下侧，使结点1 成为结点2 的左孩子，结点 2 成为结点3的左孩子。
第二步跟 LL 型一样处理 ( 应以结点2为轴心 ) 。
4 平衡二叉树3 321 21 32 1LR型图2.34)RL 型:2 插在 1的右孩子的左子树里。
调整方法见图2.4 。
分为两步进行: 新结点第一步以结点2为轴心，将结点 3 从结点 2 的右上方转到结点 2 的右下侧，使结点3 成为结点2 的右孩子，结点 2成为结点 1的右孩子。
第二步跟 RR 型一样处理 ( 应以结点2 为轴心 ) 。
1 123 21 32 3RL型图2.45 平衡二叉树3 详细设计3.1 程序主要功能模块的伪代码算法(1)对以*p为根的二叉排序树作右旋处理void R_Rotate(BSTree &p) {BSTNode* lc;lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;}对以*p为根的二叉排序树作左旋处理void L_Rotate(BSTree &p) {BSTNode* rc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}(2) 对以指针T所指结点为根的二叉排序树作左平衡旋转处理 void LeftBalance(BSTree &T) {int bf;BSTNode* lc;lc=T->lchild;bf = TreeDepth(lc->lchild) - TreeDepth(lc->rchild);switch(bf){case +1: //LLR_Rotate(T);break;case -1: //LRL_Rotate(T->lchild);6 平衡二叉树R_Rotate(T);}}对以指针T所指结点为根的二叉排序树作右平衡旋转处理 void RightBalance(BSTree &T){int bf;BSTNode* rc;rc=T->rchild;bf = TreeDepth(rc->lchild) - TreeDepth(rc->rchild);switch(bf){case -1: //RLL_Rotate(T);break;case +1: //RRR_Rotate(T->rchild);L_Rotate(T);}}(4)插入函数void InsertAVL(BSTNode* &T,int key){int bf;if(!T){T=(BSTNode*)malloc(sizeof(BSTNode));T->key=key;T->lchild=T->rchild=NULL;}else{if(key==T->key){printf("点已存在\n");7 平衡二叉树return;}else if(key<T->key) //*在*T的左子树中进行搜索{InsertAVL(T->lchild,key);bf = TreeDepth(T->lchild) - TreeDepth(T->rchild); if(bf>1)LeftBalance(T);}else //*在*T的右子树进行搜索{InsertAVL(T->rchild,key);bf = TreeDepth(T->lchild) - TreeDepth(T->rchild); if(bf<-1)RightBalance(T);}}}8 平衡二叉树3.2 程序主要流程图开始2 3switch(choice)1Preorder(T) Inorder(T)InsertAVL(T,key)输入keyNT==NULL 结束Y 0 InsertAVL(T,key)T->key=key switch(choice)key==T->keyNY Nkey<T->key 点已存在YInsertAVL(T->lchild,key) Bf>1>InsertAVL(T->rchild,key) LeftBalance(T)RightBalance(T) Bf<-1 >9 平衡二叉树4 测试数据与测试结果图4-1 程序主界面图4-2 退出程序10 平衡二叉树图4-3 LL型11 平衡二叉树图4-4 LR型12 平衡二叉树图4-5 RR型13 平衡二叉树图4-6 RL型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)的方式，通过左旋及右旋函数实现左平衡和右平衡，并验证了其中序序列有序性～这次课程设计主要的思想就是递归，首先是插入函数的递归，判断所要插入的数据跟原来树的根结点比较，比根结点数据小，则递归调用插入函数继续在其左子树中插入，比根结点的数据大，则递归调用插入函数继续在其右子树中插入，直到找到合适的位置，则插入成功。
插入成功后返回上一层次的递归，并且求出相当于插入结点的双亲结点的平衡因子，依次返回，找到第一个不平衡的结点，再做相应的调整，重复上述过程，直到整个二叉树都平衡。