广工数据结构实验报告平衡二叉树解剖.doc

数据结构实验报告 题目：平衡二叉树 学 院 专 业 年级班别 学 号 学生姓名 指导教师 2015年7月1日 题目：采用字符类型为整型类型和链式存储结构，实现抽象数据类型BTree。 ADT BTree{ 数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ ai-1, ai|ai-1, ai∈D, i=2,...,n } 基本操作： Adj_balance(T) 操作结果：创建平衡二叉树。 InsertAVL(T,search,taller) 初始条件：二叉树T已存在。 操作结果：增加新结点。 SetAVL(T,search,taller) 初始条件：二叉树T已存在。 操作结果：在平衡二叉树上增加新结点并调平衡。 DeleteAVL(T,search,shorter) 初始条件：二叉树T已存在。 操作结果：删除结点。 } ADT BTree 存储结构定义 公用头文件DS0.h: #includestdio.h #include malloc.h 树的内部变量 typedef?struct?BTNode {? int data; int?bf;????????????//平衡因子 struct?BTNode?*lchild,*rchild;//左、右孩子 }BTNode,*BTree; /*需要的函数声明*/? void?Right_Balance(BTree?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);? void Delete(BTree q,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); int menu( ); 算法设计 /*对以*p为根的二叉排序树作右旋处理*/ void Right_Balance(BTree p) { BTree lc; lc =p-lchild; //lc指向的*p左子树根结点 p-lchild = lc-rchild; //rc的右子树挂接为*p的左子树 lc-rchild = p; p = lc; //p指向新的结点 } /*对以*p为根的二叉排序树作左旋处理*/ void Left_Balance(BTree p) { BTree rc; rc = p-rchild; //指向的*p右子树根结点 p-rchild = rc-lchild; //rc左子树挂接到*p的右子树 rc-lchild = p; p = rc; //p指向新的结点 } /*对以指针T所指结点为根的二叉树作左平衡旋转处理*/ void Left_Root_Balance(BTree T) { BTree lc