资源描述：
《广工数据结构实验报告平衡二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构实验报告题目：平衡二叉树学院专业年级班别学号学生姓名指导教师2015年7月1日1.题目：采用字符类型为整型类型和链式存储结构，实现抽象数据类型BTree。ADTBTree{数据对象：D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、ai-1,ai∈D,i=2,...,n}基本操作：Adj_balance(T)操作结果：创建平衡二叉树。InsertAVL(T,search,taller)初始条件：二叉树T已存在。操作结果：增加新结点。SetAVL(T,search,taller)初始条件：二叉树T已存在
4、。操作结果：在平衡二叉树上增加新结点并调平衡。DeleteAVL(T,search,shorter)初始条件：二叉树T已存在。操作结果：删除结点。}ADTBTree2．存储结构定义公用头文件DS0.h:#include#include树的内部变量typedef struct BTNode{ intdata;int bf; //平衡因子struct BTNode *lchild,*rchild;//左、右孩子}BTNode,*BTree;/*需要的函数声明*/ void Right_Balance(BTr
5、ee &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); voidDelete(BTr
6、eeq,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);intmenu();3.算法设计/*对以*p为根的二叉排序树作右旋处理*/voidRight_Balance(BTree&p){BTreelc;lc=p->lchild;//lc指向的*p左
7、子树根结点p->lchild=lc->rchild;//rc的右子树挂接为*p的左子树lc->rchild=p;p=lc;//p指向新的结点}/*对以*p为根的二叉排序树作左旋处理*/voidLeft_Balance(BTree&p){BTreerc;rc=p->rchild;//指向的*p右子树根结点p->rchild=rc->lchild;//rc左子树挂接到*p的右子树rc->lchild=p;p=rc;//p指向新的结点}/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/voidLeft_Root_Balance(BTree&T){BTreelc,r
8、d;lc=T->lchild;//指向*T的左子树根结点switch(lc->bf)//检查*T的左子树的平衡度，并作相应平衡处理{case1://新结点插入在*T的左孩子的左子树上，要作单右旋处理T->bf=lc->bf=0;Right_Balance(T);break;case-1://新结点插入在*T的左孩子的右子树上，要作双旋处理rd=lc->rchild;//rd指向*T的左孩子的右子树根switch(rd->bf)//修改*T及其左孩子的平衡因子{case1:T->bf=-1;lc->bf=0;break;case0:T->bf=lc->bf=0;b
9、reak;case-1:T->bf=0;lc->bf=1;break;}rd->bf=0;Left_Balance(T->lchild);//对*T的左子树作左旋平衡处理Right_Balance(T);//对*T作右旋平衡处理}}/*对以指针T所指结点为根的二叉树作右平衡旋转处理*/voidRight_Root_Balance(BTree&T){BTreerc,ld;rc=T->rchild;//指向*T的左子树根结点switch(rc->bf)//检查*T的右子树的平衡度，并作相应平衡处理{case-1://新结点插入在*T的右孩子的右子树上，要作单左旋处理
10、T->bf=rc->bf
