资源描述：
《广工数据结构实验报告--平衡二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验报告课程名称数据结构实验学院计算机学院专业班级计科9班学号学生姓名指导教师苏庆2015年7月6日1.题目:平衡二叉树ADTBBSTree{数据对象：D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、ai-1,ai∈D,i=2,...,n}基本操作：BBSTreeMakeBBSTree()操作结果：创建好一棵树返回：将创建好的树返回StatusInsertAVL(BBSTree&T,RcdTypee,Status&taller)初始条件：树T已存在，e存在，ta
4、ller为真操作结果：将e插入到T中返回：成功TRUE，失败FALSEStatusDeleteAVL(BBSTree&t,RcdTypee,Status&shorter)初始条件：树T已存在，e存在，shorter为真操作结果：将e从T中删除返回：成功TRUE，失败FALSEBBSTreeSearchAVL(BBSTreeT,RcdTypee)初始条件：树T已存在，e存在操作结果：从T中找到e返回：以e为根节点的树voidL_Rotate(BBSTree&p)初始条件：树p存在操作结果：对p左旋操作voidR_Rot
5、ate(BBSTree&p)初始条件：树p存在操作结果：对p右旋操作voidLeftBalance(BBSTree&T)初始条件：树T存在操作结果：对T左平衡操作voidRightBalance(BBSTree&T)初始条件：树T存在操作结果：对T右平衡操作voidExchangeSubTree(BBSTree&T)初始条件：树T存在操作结果：对T所有左右孩子交换intBBSTreeDepth(BBSTreeT)初始条件：树T已存在操作结果：求树T的深度返回：树的深度BBSTreeCombine2Tree(BBSTr
6、eeT1,BBSTreeT2)初始条件：树T1和T2已存在操作结果：将T1和T2合并返回：合并后的树StatusSplitBBSTree(BBSTreeTt1,BBSTree&Tt2,BBSTree&Tt3,intx)初始条件：树Tt1，Tt2，Tt3已存在，x存在操作结果：将Tt1分裂成Tt2和Tt3返回：以e为根节点的树StatusPreOrder_RecTraverse(BBSTreeT)初始条件：树T已存在操作结果：对树T进行递归先序遍历输出返回：成功TRUE失败FALSEStatusInOrder_RecT
7、raverse(BBSTreeT)初始条件：树T已存在操作结果：对树T进行递归中序遍历输出返回：成功TRUE失败FALSEStatusLastOrder_RecTraverse(BBSTreeT)初始条件：树T已存在操作结果：对树T进行递归后序遍历输出返回：成功TRUE失败FALSEvoidPreOrderTravese_I(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归先序遍历输出voidInOrderTraverse_I(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归中序遍历输
8、出voidLastOrderTravese_I(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归后序遍历输出voidLevelOrederTraverse_Print(BBSTreeT)初始条件：树T已存在操作结果：对树T进行非递归层次遍历输出voidBraNotationPrint(BBSTreeT)初始条件：树T已存在操作结果：对树T用括号表示法输出}ADTBBSTree1.存储结构定义#include#include#defineOVERFLOW-1#def
9、ineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineLH+1//左高#defineEH0//等高#defineRH-1//右高typedefintRcdType;typedefintStatus;/*平衡二叉树结构体*/typedefstructBBSTNode{RcdTypedata;intbf;BBSTNode*lchild,*rchild;}BBSTNode,*BBSTree;1.算法设计/*求平衡二叉树的深度*/intBBSTreeDepth(BBSTreeT
10、){intdepthLeft,depthRight;if(NULL==T)return0;else{depthLeft=BBSTreeDepth(T->lchild);depthRight=BBSTreeDepth(T->rchild);return1+(depthLeft>depthRight?depthLeft:depthRight);}}
