数据结构程序报告(平衡二叉树的操作).docVIP

. . 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学 号： 班 级： 指导老师： 报告日期： 需求分析 1．建立平衡二叉树并进行创建、查找、插入、删除等功能。 2．设计一个实现平衡二叉树的程序，可进行创建、查找、插入、删除等操作，实现动态的输入数据，实时的输出该树结构。 3．测试数据：自选数据 2.概要设计 1.抽象数据类型定义： typedef struct BSTNode { int data; int bf; //节点的平衡因子 struct BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; void CreatBST(BSTree T); //创建平衡二叉树 void R_Rotate(BSTree p); //对以*p为根的二叉排序树作左旋处理 void L_Rotate(BSTree p); //对以*p为根的二叉排序树作左旋处理 void LeftBalance(BSTree T); //对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理 void RightBalance(BSTree T); //对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理 bool InsertAVL(BSTree T,int e,bool taller); //插入结点e bool SearchBST(BSTree T,int key); //查找元素key是否在树T中 void LeftBalance_div(BSTree p,int shorter); //删除结点时左平衡旋转处理 void RightBalance_div(BSTree p,int shorter); //删除结点时右平衡旋转处理 void Delete(BSTree q,BSTree r,int shorter); //删除结点 int DeleteAVL(BSTree p,int x,int shorter); //平衡二叉树的删除操作 void PrintBST(BSTree T,int m); //按树状打印输出二叉树的元素 主程序的流程 请输入操作的选项编号（1-5） 1---创建平衡二叉树 2---查找 3---插入 4---删除 5---结束 3.各模块之间的层次调用 退出输出删除插入查找平衡化输入数据元素显示主菜单主模块 退出 输出 删除 插入 查找 平衡化 输入数据元素 显示主菜单 主模块 详细设计 1.以平衡二叉树的插入和平衡化为例： bool InsertAVL(BSTree T,int e,bool taller) { //若存在平衡的二叉排序树T中不存在和e有相同关键字的节点，则插入一个数据元素为e //的新结点，并返回1，否者返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转理， //布尔变量taller反映T长高与否。 if(!T)//插入新结点，树“长高”，置taller为true { T = (BSTree)malloc(sizeof(BSTNode)); T-data = e; T-lchild = T-rchild =NULL; T-bf = EH; taller = true; } else { if(EQ(e,T-data)) //树中已存在和有相同关键字的结点 { taller = false;printf(已存在相同关键字的结点\n); return 0; }//则不再插入 if(LT(e,T-data)) //应继续在*T的左子树中进行有哪些信誉好的足球投注网站 { if(!InsertAVL(T-lchild,e,taller)) return 0;//未插入 if(taller) //已插入到*T的左子树中且左子树“长高” switch(T-bf) //检查*T的平衡度 { case LH: