资源描述：
《平衡二叉排序树实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、华南农业大学信息学院综合性、设计性实验起止日期:2012冬学院信息学院专业班级软件工程2班学号5姓名许炯勃实验题目实现平衡二叉排序树的各种算法自我评价项目算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂插入新结点√√√√前序、中序、后序遍历二叉树（递归）√√√√前序、中序、后序遍历的非递归算法√√√√层次遍历二叉树√√√√在二叉树中查找给定关键字√√√√交换各结点的左右子树√√√√求二叉树的深度√√√√叶子结点数√√√√删除某结点√√√√lA---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符
2、合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。lB---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清晰完整。lC---------完成实验要求的大部分功能，实验报告良好。lD---------未按时完成实验，或者抄袭。成绩教师签名：杨秋妹一,实验所用的数据类型:(1)二叉树,其结构如下typedefstructBSTNode{ElemTypedata;/*树的值*/intbf;/*平衡因子*/structBSTNode*lchild,*rchild;}BSTNode,*BSTree;(2)非递归遍历和层次
3、遍历时用到的栈和队列为C++STL里的自带栈和队列,即stacks;queueq;其操作包括：s.push(SElemTypee)//入栈s.pop()//出栈s.empty()//判断栈是否为空，是空时返回TRUEs.top（）//返回栈顶元素q.push(SElemTypee)//入队列q.pop()//出队列q.empty()//判断队列是否为空，是空时返回TRUEq．front()//返回队头元素二,实验所用到的函数及其作用:(1)SearchBT(BSTreeT,ElemTypekey)/*
4、在二叉树中查找给定关键字(函数返回值为成功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)Pr
5、eOrderTraverse(BSTreeT,Status(*Visit)(ElemType))/*递归先序遍历平衡二叉排序树*/(8)PreOrder(BSTreeT,Status(*Visit)(ElemType))/*非递归先序遍历平衡二叉排序树*/(9)InOrderTraverse(BSTreeT,Status(*Visit)(ElemType))/*递归中序遍历平衡二叉排序树*/(10)InOrder(BSTreeT,Status(*Visit)(ElemType))/*非递归中序遍历平衡二叉排序树*/(11)PostOrder
6、Traverse(BSTreeT,Status(*Visit)(ElemType))/*递归后序遍历平衡二叉排序树*/(12)PostOrder(BSTreeT,Status(*Visit)(ElemType))/*非递归后序遍历平衡二叉排序树*/(13)LevelTraverse(BSTreeT,Status(*Visit)(ElemType))/*层次遍历平衡二叉排序树*/(14)ExchangeNode(BSTree&T)//交换各节点的左右子树(15)intTreeDepth(BSTreeT)//返回树的深度(16)intLeafC
7、ount(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_
8、Balance_del(BSTree&p,bool&shorter)//删除结点时向右平衡三，算法设计及其实现（1）结点的插入：在插入结点时，先判断树高度是否改变，再判断是否有结
