华南农业大学信息学院综合性、设计性实验起止日期:2011秋学院软件学院专业班级10软件工程7班学号201031000704姓名黄定康实验题目实现平衡二叉排序树的各种算法自我评价项目算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂插入新结点√√√√前序、中序、后序遍历二叉树（递归）√√√√前序、中序、后序遍历的非递归算法√√√√层次遍历二叉树√√√√在二叉树中查找给定关键字√√√√交换各结点的左右子树√√√√求二叉树的深度√√√√叶子结点数√√√√删除某结点√√√√●A---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。
●B---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清晰完整。
●C---------完成实验要求的大部分功能，实验报告良好。
●D---------未按时完成实验，或者抄袭。
成绩教师签名：杨秋妹实验报告题目：实现平衡二叉排序树的各种算法班级：10软件工程7班姓名：黄定康学号：201031000704完成日期：2011/12/07（一）分析题目要求（1）函数说明void R_rotate(ptr& t) -右旋转函数，从T开始做右旋转int coutdeep(ptr t)-计算深度函数void L_rotate(ptr& t)-左旋转函数void leftbalance(ptr&t)-左平衡函数，从T开始做左平衡处理void rightbalance(ptr&t)-右平衡函数int insertA VL(ptr& t,int e,int & taller)-插入结点函数void preorder(ptr t)-（递归）先序遍历void preorder_2(ptr t)-（非递归）先序遍历void inorder(ptr t)-（递归）中序遍历void inorder_2(ptr t)-（非递归）中序遍历void posorder(ptr t)-（递归）后序遍历void posorder_2(ptr t)-（非递归）后序遍历void dfs(ptr t,int type)-（递归）深度优先遍历（包含中序先序后续）void dfs_2(ptr t,int type)-(递归) 深度优先遍历int bfs(ptr t)-层次便利int delete_node(ptr& t,int&shorter,int temp);-删除结点函数int Delete(ptr& t,int shorter)-删除结点函数int transfer(ptr&t)-左右子树交换函数int countleaf(ptr t)-计算叶节点int checkup(ptr t,int temp)- 从树t中查找temp是否存在，存在返回1否则返回0int main()-主函数void show_menu(ptr t)-简单的菜单函数（2）输入形式及输入值范围输入形式：当树没创建时，先在第一行输入树的节点数目n，第二行再输入n个大于0的不重复整数，以空格隔开。
删除结点时，直接输入要删除结点的值。
输入范围：所有int类型的大于零的值，注意不能重复输入。
（3）输出形式输出形式：各种遍历形式输出均用空格隔开，删除结点时，若成功，打印成功信息，若失败，则打印失败的信息。
（4）程序所能达到的功能程序里面的函数可以实现平衡二叉树的以下功能：（1）插入新结点（2）前序、中序、后序遍历二叉树（递归）（3）前序、中序、后序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字（6）交换各结点的左右子树（7）求二叉树的深度（8）叶子结点数（9）删除某结点（二）解题思路（1）插入的思路：插入基于一般二叉排序树的插入，但在插入的同时考虑是否破坏平衡。
在结构体中假如balance function（BF）,来记录当前结点的平衡情况。
（2）删除的思路：在删除结点的时候，删除之前先考虑删除之后是否影响该子树的平衡结构，再回溯考虑是否影响整棵A VL树的平衡。
调整后再删除。
（3）遍历的思路：非递归的遍历都用了栈作为辅助的结构，在树的结点中加入状态（statue）来记录当前结点的访问状态（是否访问了左右结点）。
然后再做对应操作。
（4）统计深度和叶节点数量的思路：都是用了递归的思想，统计深度是递归求左右子树的深度，取较大值。
统计叶节点则是递归求左右子树的叶节点，最后求和。
（三）调试分析（1）困难和解决：由于在课本上没有删除的相关算法，一开始要考虑删除后的平衡问题确实比较困难，不过通过上网查找相关资料。
最终还是得以解决。
同样，非递归遍历的算法也如此，一开始感觉无从下手，不过结合了堆栈的知识之后，就迎刃而解了。
（2）使用的测试数据：第一组：输入顺序是54321，树的三种遍历是42135，12345，13254.正确。
删除结点5后是2143，1234，1342.正确。
第二组：输入顺序是76543218，树的三种遍历是42136578，12345678，13258764.删除结点7后是4213568，1234658，1326854。
第三组：输入顺序是45 12 33 60 10.树的三种遍历是33 12 10 45 60，10 12 33 45 60，10 12 60 45 33.删除60后是33 12 10 45，10 12 33 45，10 12 45 33.（3）算法的效率分析和改进设想：删除和插入的算法均是用了二叉排序树的性质来进行，故算法的效率大概为O(lgn)。
而遍历的非递归算法均是以栈结构实现。
故应该以O(n)的效率进行。
由于算法设计的不完善，删除和插入函数的旋转操作都可以进一步提升效率，判断情况也可以尽量减少冗余。
这样可以让时间复杂度前面的系数变小，从而提高算法整体效率。
（4）经验和体会：这次的实验让我充分认识了A VL树的各种操作，及其优越的查找删除效率。
但由于一开始对删除操作的不熟悉，走了不少弯路，在上网查找了资料之后阔然开朗。
并实现了算法。
这次实验的最大体会是，要从小的例子开始，多动手来实际演算算法进行过程，从而发现错误所在。
（四）附录--带注释的源程序#include <stdio.h>#include <stdlib.h>#define LH 1#define EH 0#define RH -1#define WH //printf("this\n");struct node;int leaf;int deepth;typedef struct node* ptr;typedef struct node{int elem;int bf;int statue;ptr lchild;ptr rchild;}node;void R_rotate(ptr& t)//从t开始做右旋转{ptr lc=t->lchild;//首先另外存储t->lchild=lc->rchild;lc->rchild=t;t=lc;}int coutdeep(ptr t){if(t) return 1+ (coutdeep(t->lchild)>coutdeep(t->rchild)?coutdeep(t->lchild):coutdeep(t->rchild));else return 0;}void L_rotate(ptr& t)//和上面相反ptr rc=t->rchild;t->rchild=rc->lchild;rc->lchild=t;t=rc;}void leftbalance(ptr&t)//左子树要平衡{ptr lc=t->lchild;ptr rd;switch(lc->bf){case LH://LL型t->bf=lc->bf=EH;R_rotate(t);break;case RH://Lr型rd=lc->rchild;switch(rd->bf){case LH: t->bf=RH;lc->bf=EH;break;case EH: t->bf=lc->bf=EH;break;case RH: t->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_rotate(t->lchild);R_rotate(t);break;case EH:{t->bf=LH;lc->bf=RH;R_rotate(t);break;}}}void rightbalance(ptr&t){ptr rc=t->rchild;ptr ld;switch(rc->bf){case RH://rr型t->bf=rc->bf=EH;L_rotate(t);break;case LH://rl型ld=rc->lchild;switch(ld->bf){case LH:t->bf=EH;rc->bf=RH;break;case EH:t->bf=rc->bf=EH;break;case RH:t->bf=LH;rc->bf=EH;break;}ld->bf=EH;R_rotate(t->rchild);L_rotate(t);break;case EH://特殊情况，进行rr型旋转{t->bf=RH;rc->bf=LH;L_rotate(t);break;}}}int insertA VL(ptr& t,int e,int & taller){if(t==NULL){t=(node*)malloc(sizeof(node));t->elem=e;t->rchild=t->lchild=NULL;t->statue=0;t->bf=EH;taller=1;}else{if(t->elem==e){taller=0;return 0;}if(t->elem>e){if(!insertA VL(t->lchild,e,taller)) return 0;if(taller)switch(t->bf){case LH:leftbalance(t);taller=0;break;case EH:t->bf=LH;taller=1;break;case RH:t->bf=EH;taller=0;break;}}else{if(!insertA VL(t->rchild,e,taller)) return 0;if(taller)switch(t->bf)//本身{case LH://本身左高。