数据结构实验报告题目：平衡二叉树学院专业年级班别学号学生姓名指导教师2015 年 7 月 1 日1.题目： 采用字符类型为整型类型和链式存储结构，实现抽象数据类型BTree。 ADT BTree 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 |ai-1, aiD, i=2,.,n 基本操作： Adj_balance(T) 操作结果：创建平衡二叉树。 InsertAVL(T,search,taller) 初始条件：二叉树T 已存在。 操作结果：增加新结点。 SetA VL(T,search,taller) 初始条件：二叉树T 已存在。 操作结果：在平衡二叉树上增加新结点并调平衡。 DeleteAVL(T,search,shorter) 初始条件：二叉树T 已存在。 操作结果：删除结点。 ADT BTree 2存储结构定义 公用头文件 DS0.h: #include #include 树的内部变量 typedef struct BTNode int data; int bf; /平衡因子 struct BTNode *lchild,*rchild;/ 左、右孩子 BTNode,*BTree; /*需要的函数声明 */ void Right_Balance(BTree void Left_Balance(BTree void Left_Root_Balance(BTree void Right_Root_Balance(BTree bool InsertAVL(BTree void PrintBT(BTree T); void Left_Root_Balance_det(BTree void Right_Root_Balance_det(BTree void Delete(BTree q,BTree int DeleteAVL(BTree void Adj_balance(BTree bool SetAVL(BTree bool Insert_Balance_A VL(BTree int menu( ); 3. 算法设计/*对以*p 为根的二叉排序树作右旋处理*/ void Right_Balance(BTree lc =p-lchild; /lc 指向的 *p 左子树根结点 p-lchild = lc-rchild; /rc 的右子树挂接为 *p 的左子树 lc-rchild = p; p = lc; /p 指向新的结点 /*对以*p 为根的二叉排序树作左旋处理*/ void Left_Balance(BTree rc = p-rchild; /指向的 *p 右子树根结点 p-rchild = rc-lchild; /rc 左子树挂接到 *p 的右子树 rc-lchild = p; p = rc; /p 指向新的结点 /*对以指针 T 所指结点为根的二叉树作左平衡旋转处理*/ void Left_Root_Balance(BTree lc = T-lchild; /指向*T 的左子树根结点 switch(lc-bf) /检查*T 的左子树的平衡度，并作相应平衡处理 case 1: /新结点插入在 *T 的左孩子的左子树上，要作单 右旋处理 T-bf = lc-bf = 0; Right_Balance(T); break; case -1: /新结点插入在 *T 的左孩子的右子树上，要作双 旋处理 rd = lc-rchild; /rd 指向*T 的左孩子的右子树根 switch(rd-bf) /修改*T 及其左孩子的平衡因子 case 1: T-bf = -1; lc-bf = 0; break; case 0: T-bf = lc-bf = 0; break; case -1: T-bf = 0; lc-bf = 1; break; rd-bf = 0; Left_Balance(T-lchild); /对*T 的左子树作左旋平衡处理 Right_Balance(T); /对*T 作右旋平衡处理 /*对以指针 T 所指结点为根的二叉树作右平衡旋转处理*/ void Right_Root_Balance(BTree rc = T-rchild; /指向*T 的左子树根结点 switch(rc-bf) /检查*T 的右子树的平衡度，并作相应平衡处理 case -1: /新结点插入在 *T 的右孩子的右子树上， 要作单左 旋处理 T-bf = rc-bf =0; Left_Balance(T); break; case 1: /新结点插入在 *T 的右孩子的左子树上，要作双旋 处理 ld = rc-lchild; /ld 指向*T 的右孩子的左子树根 switch(ld-bf) /修改*T 及其右孩子的平衡因子 case 1: T-bf = 0; rc-bf = -1; break; case 0: T-bf = rc-bf =0; break; case -1: T-bf = 1; rc-bf = 0; break; ld-bf = 0; Right_Balance(T-rchild);/对*T 的右子树作左旋平衡处理 Left_Balance(T); /对*T 作左旋平衡处理 /*插入结点 i,若 T 中存在和 i 相同关键字的结点，则插入一个数据元素为i 的新 结点，并返回，否则返回*/ bool InsertAVL(BTree T-data = i; T-lchild = T-rchild =NULL; T-bf = 0; taller = true; else if(i=T-data) /树中已存在和有相同关键字的结点 taller = 0; printf(“ 已存在相同关键字的结点 n“); return 0; if(idata) /应继续在 *T 的左子树中进行搜索 if(!InsertAVL(T-lchild,i,taller) return 0; else /应继续在 *T 的右子树中进行搜 索 if(!InsertAVL(T-rchild,i,taller) return 0; return 1; /*输出二叉树 */ void PrintBT(BTree T) if(T) printf(“%d“,T-data); if(T-lchild|T-rchild) printf(“(“); PrintBT(T-lchild); printf(“,“); PrintBT(T-rchild); printf(“)“); /*删除结点时左平衡旋转处理*/ void Left_Root_Balance_det(BTree if(p-bf=1) /p 结点的左子树高，删除结点后p 的 bf 减,树变矮 p-bf=0; shorter=1; else if(p-bf=0)/p 结点左、右子树等高，删除结点后p 的 bf 减,树高不变 p-bf=-1; shorter=0; else /p 结点的右子树高 p1=p-rchild;/p1 指向 p 的右子树 if(p1-bf=0)/p1 结点左、 右子树等高 ,删除结点后 p 的 bf 为-2,进行左旋 处理，树高不变 Left_Balance(p); p1-bf=1; p-bf=-1; shorter=0; else if(p1-bf=-1)/p1 的右子树高，左旋处理后，树变矮 Left_Balance(p); p1-bf=p-bf=0; shorter=1; else /p1的左子树高 ,进行双旋处理 (先右旋后左旋 )，树变矮 p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=-1) p-bf=1; p1-bf=0; else p-bf=0; p1-bf=-1; p2-bf=0; p=p2; shorter=1; /*删除结点时右平衡旋转处理*/ void Right_Root_Balance_det(BTree if(p-bf=-1) p-bf=0; shorter=1; else if(p-bf=0) p-bf=1; shorter=0; else p1=p-lchild; if(p1-bf=0) Right_Balance(p); p1-bf=-1; p-bf=1; shorter=0; else if(p1-bf=1) Right_Balance(p); p1-bf=p-bf=0; shorter=1; else p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=1) p-bf=-1; p1-bf=0; else p-bf=0; p1-bf=1; p2-bf=0; p=p2; shorter=1; /*删除结点 */ void Delete(BTree q,BTree q=r; r=r-lchild; free(q); shorter=1; else Delete(q,r-rchild,shorter); if(shorter=1) Right_Root_Balance_det(r,shorter); /*二叉树的删除操作 */ int DeleteAVL(BTree BTree q; if(p=NULL) printf(“ 不存在要删除的关键字 !n“); return 0; else if(xdata)/在 p 的左子树中进行删除 k=DeleteAVL(p-lchild,x,shorter); if(shorter=1) Left_Root_Balance_det(p,shorter); return k; else if(xp-data)/在 p 的右子树中进行删除 k=DeleteAVL(p-rchild,x,shorter); if(shorter=1) Right_Root_Balance_det(p,shorter); return k; else q=p; if(p-rchild=NULL) / 右子树空则只需重接它的左子树 p=p