平衡二叉排序树实验报告

华南农业大学信息学院综合性、设计性实验起止日期:2012冬学院信息学院专业班级软件工程2班学号201130690225姓名许炯勃实验题目实现平衡二叉排序树的各种算法自我评价项目算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂插入新结点√√√√前序、中序、后序遍历二叉树（递归）√√√√前序、中序、后序遍历的非递归算法√√√√层次遍历二叉树√√√√在二叉树中查找给定关键字√√√√交换各结点的左右子树√√√√求二叉树的深度√√√√叶子结点数√√√√删除某结点√√√√A---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。B---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清晰完整。C---------完成实验要求的大部分功能，实验报告良好。D---------未按时完成实验，或者抄袭。成绩教师签名：杨秋妹一,实验所用的数据类型:(1)二叉树,其结构如下typedefstructBSTNode{ElemTypedata;/*树的值*/intbf;/*平衡因子*/structBSTNode*lchild,*rchild;}BSTNode,*BSTree;(2)非递归遍历和层次遍历时用到的栈和队列为C++STL里的自带栈和队列,即stackBSTNode*s;queueBSTNode*q;其操作包括：s.push(SElemTypee)//入栈s.pop()//出栈s.empty()//判断栈是否为空，是空时返回TRUEs.top（）//返回栈顶元素q.push(SElemTypee)//入队列q.pop()//出队列q.empty()//判断队列是否为空，是空时返回TRUEq．front()//返回队头元素二,实验所用到的函数及其作用:(1)SearchBT(BSTreeT,ElemTypekey)/*在二叉树中查找给定关键字(函数返回值为成功TRUE,失败FALSE)*/(2)InsertAVL(BSTree&T,ElemTypee,bool&taller)/*插入结点，并使所成树为平衡二叉排序树,e为插入结点的值，taller为判断插入结点后树是否长高的布尔型变量*/(3)R_Rotate(BSTree&p)//将树向右旋转(4)L_Rotate(BSTree&p)//将树向左旋转(5)Left_Balance(BSTree&T)//插入结点时向左平衡(6)Right_Balance(BSTree&T)//插入结点时向右平衡(7)PreOrderTraverse(BSTreeT,Status(*Visit)(ElemType))/*递归先序遍历平衡二叉排序树*/(8)PreOrder(BSTreeT,Status(*Visit)(ElemType))/*非递归先序遍历平衡二叉排序树*/(9)InOrderTraverse(BSTreeT,Status(*Visit)(ElemType))/*递归中序遍历平衡二叉排序树*/(10)InOrder(BSTreeT,Status(*Visit)(ElemType))/*非递归中序遍历平衡二叉排序树*/(11)PostOrderTraverse(BSTreeT,Status(*Visit)(ElemType))/*递归后序遍历平衡二叉排序树*/(12)PostOrder(BSTreeT,Status(*Visit)(ElemType))/*非递归后序遍历平衡二叉排序树*/(13)LevelTraverse(BSTreeT,Status(*Visit)(ElemType))/*层次遍历平衡二叉排序树*/(14)ExchangeNode(BSTree&T)//交换各节点的左右子树(15)intTreeDepth(BSTreeT)//返回树的深度(16)intLeafCount(BSTreeT)//计算树的叶子节点数并返回(17)CreateBT(BSTree&T)//创建一颗平衡二叉排序树(18)DeleteAVL(BSTree&p,ElemTypee,bool&shorter)/*平衡二叉排序树的删除,e为删除的结点的值，shorter为判断删除结点后树高度是否减小的布尔型变量*/(19)Delete(BSTreeq,BSTree&r,bool&shorter)//结点的删除(20)Left_Balance_del(BSTree&p,bool&shorter)//删除结点是向左平衡(21)Right_Balance_del(BSTree&p,bool&shorter)//删除结点时向右平衡三，算法设计及其实现（1）结点的插入：在插入结点时，先判断树高度是否改变，再判断是否有结点的平衡因子的绝对值大于1，如果有，则根据情况（分为四种情况：LL型，LR型，RR型，RL型）进行左旋或右旋，使新生成的树也是一颗平衡二叉排序树，代码如下：StatusInsertAVL(BSTree&T,ElemTypee,bool&taller){/*插入结点，并使所成树为平衡二叉排序树*/if(SearchBT(T,e)){cout该值在树中已存在！endl;return0;}if(!T){T=(BSTree)malloc(sizeof(BSTNode));T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;}else{if(e==T-data){taller=false;return0;}if(eT-data){if(!InsertAVL(T-lchild,e,taller))return0;if(taller)switch(T-bf){caseLH:Left_Balance(T);taller=false;break;caseEH:T-bf=LH;taller=true;break;caseRH:T-bf=EH;taller=false;break;}}else{if(!InsertAVL(T-rchild,e,taller))return0;if(taller)switch(T-bf){caseLH:T-bf=EH;taller=false;break;caseEH:T-bf=RH;taller=true;break;caseRH:Right_Balance(T);taller=false;break;}}}returnOK;}voidR_Rotate(BSTree&p){//将树向右旋转BSTreelc;lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;}voidL_Rotate(BSTree&p){//将树向左旋转BSTreerc;rc=p-rchild;p-rchild=rc-lchild;rc-lchild=p;p=rc;}voidLeft_Balance(BSTree&T){//插入结点时向左平衡BSTreelc,rd;lc=T-lchild;switch(lc-bf){caseLH:T-bf=lc-bf=EH;R_Rotate(T);break;caseRH:rd=lc-rchild;switch(rd-bf){caseLH:T-bf=RH;lc-bf=EH;break;caseEH:T-bf=lc-bf=EH;break;caseRH:T-bf=EH;lc-bf=LH;break;}rd-bf=EH;L_Rotate(T-lchild);R_Rotate(T);}}voidRight_Balance(BSTree&T){//插入结点时向右平衡BSTreerc,ld;rc=T-rchild;switch(rc-bf){caseRH:T-bf=rc-bf=EH;L_Rotate(T);break;caseLH:ld=rc-lchild;switch(ld-bf){caseRH:T-bf=LH;rc-bf=EH;break;caseEH:T-bf=rc-bf=EH;break;caseLH:T-bf=EH;rc-bf=RH;break;}//switch(ld-bf)ld-bf=EH;R_Rotate(T-rchild);L_Rotate(T);}}(2)前序、中序、后序遍历二叉树（递归）:根据各种顺序遍历的特点掌握一种递归遍历方法很容易可以推出另外两种，代码如下：StatusPreOrderTraverse(BSTreeT,Status(*Visit)(ElemType)){//递归先序遍历平衡二叉排序树if(T){if(Visit(T-data))if(PreOrderTraverse(T-lchild,Visit))if(PreOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusInOrderTraverse(BSTreeT,Status(*Visit)(ElemType)){//递归中序遍历平衡二叉排序树if(T){if(InOrderTraverse(T-lchild,Visit))if(Visit(T-data))if(InOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BSTreeT,Status(*Visit)(ElemType)){//递归后序遍历平衡二叉排序树if(T){if(PostOrderTraverse(T-lchild,Visit))if(PostOrderTraverse(T-rchild,Visit))if(Visit(T-data))returnOK;returnERROR;}elsereturnOK;}(3)前序、中序、后序遍历的非递归算法:主要运用栈对暂未访问结点进行暂时储存，形成遍历，其中前序，中序遍历较简单，后序遍历则比较复杂，应特别注意，代码如下：StatusPreOrder(BSTreeT,Status(*Visit)(ElemType)){//非递归先序遍历平衡二叉排序树BSTNode*p=T;stackBSTNode*s;cout先序遍历（非递归）：;while(p||!s.empty()){if(p){if(!Visit(p-data))returnERROR;s.push(p);p=p-lchild;}else{p=s.top();s.pop();p=p-rchild;}}returnOK;}StatusInOrder(BSTreeT,Status(*Visit)(ElemType)){//非递归中序遍历平衡二叉排序树BSTNode*p=T;stackBSTNode*s;cout遍历（非递归）：;while(p||!s.empty()){if(p){s.push(p);p=p-lchild;}else{p=s.top();s.pop();if(!Visit(p-data))returnERROR;p=p-rchild;}}returnOK;}StatusPostOrder(BSTreeT,Status(*Visit)(ElemType)){//非递归后序遍历平衡二叉排序树BSTNode*p=T,*node=T;stackBSTNode*s;cout后序遍历（非递归）：;while(p||!s.empty()){if(p){s.push(p);p=p-lchild;}else{p=s.top();if(p-lchild==NULL||p-rchild==node){if(!Visit(p-data))ret