《数据结构与C语言综合训练》实习报告
题 目：AVL Tree的实现及分析
| 学 号 | ************ |
| 姓 名 | ************* |
| 专业班级 | 计算机科学与技术103 |
| 指导教师 | ******* |
| 实践日期 | 2011年7月8日-2011年7月18日 |
一、综合训练目的与要求 1
二、综合训练任务描述 1
三、算法设计 1
四、详细设计及说明 11
五、调试与测试 11
六、实习日志 13
七、实习总结 14
八、附录：核心代码清单 14
一、综合训练目的与要求
本综合训练是计算机科学与技术专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务：
1. 巩固和加深学生对算法分析课程基本知识的理解和掌握；
2. 培养利用算法知识解决实际问题的能力；
3. 掌握利用程序设计语言进行算法程序的开发、调试、测试的能力；
4. 掌握书写算法设计说明文档的能力；
5. 提高综合运用算法、程序设计语言、数据结构知识的能力。
二、综合训练任务描述
1、创建一棵一般二元查找树。
2、判断一般二元查找数是否为AVL树。
3、一般二元查找树转化为AVL。
4、AVL树的插入与删除元素操作。
三、算法设计
(1) 文字描述
首先利用二元查找树的性质创建一棵一般的二元查找树，然后计算每个节点的bf值（平衡因子），通过bf值来判断所建立的二元查找树是否为平衡二叉树，不是的话就把它转换为平衡二叉树。首先把原二元查找树的每个节点的地址存放到一个循环队列中，然后把它们一一插入到建立的平衡二叉树里面，在建立的过程中一是要保证不能插入相同的节点，二是保证插入元素后平衡二叉树还是平衡的，这就要做到边插入边旋转，旋转有四种方式，分别是RR,RL,LR,LL。平衡二叉树的删除操作，首先要找到要删除的节点，要是没有找到的话应该报错，有的话就删除，删除要注意那三种情况，一是所删除节点只有左子树，一是所删除节点只有右子树，然后是所删除节点左右子树都有。
(2) 框图
核心代码流程图
①创建二元查找树
②一般二元查找树转化为平衡二叉树
③AVL插入元素操作
④AVL删除元素操作
(3) 伪代码
#include #include #define MAXSIZE 1000 #define true 1 #define false 0 typedef struct anode { int elem; int bf; struct anode *lchild; struct anode *rchild; } AVLNode,*AVLTree; typedef struct { AVLTree data[MAXSIZE]; int front,rear; } Queue,*PQueue; int AVLInsert(AVLTree *t,AVLTree s) { fa=NULL; if((*t)==NULL) { *t=s; return true; }//判断是否为空树,是插入后就结束 if(!locateAVLNode(t,s,&fa,&a)) return false;//查找并且插入新的节点 adjustAVLbf(&a,s); if((-2 return true; else Rotate(&p,a);//判定是那种情况的旋转 if(fa==NULL) *t=p; else if(fa->elem fa->rchild=p; else fa->lchild=p; return true; } void BSTInsert(AVLTree *t,int k) { p=*t; while(p) { q=p; if(p->elem else p=p->lchild; } p=(AVLTree)malloc(sizeof(AVLNode));//构造节点 p->elem=k; p->lchild=p->rchild=NULL; if(*t==NULL) { *t=p; return; } if(q->elem else q->lchild=p; } /**********向二叉排序树中删除一个数据*********/ int BSTDelete(AVLTree *t,int x) { if(!*t||BSTsearch(*t,x)==0) return 0; else { if(x==(*t)->elem) DeleteNode(t); else if((*t)->elem>x) BSTDelete(&(*t)->lchild,x); else BSTDelete(&(*t)->rchild,x); return 1; } } void DeleteNode(AVLTree *s) { if(!(*s)->rchild) { q=*s; *s= (*s)->lchild; free(q); } else if(!(*s)->lchild) { q=*s; *s=(*s)->rchild; free(q); } else { x=*s; y=(*s)->lchild; while(y->rchild) { x=y; y=y->rchild; } (*s)->elem=y->elem; if(x!=*s) x->rchild=y->lchild; else x->lchild=y->lchild; free(y); } } void Rotate(AVLTree *t,AVLTree a) { if(a->bf==2)//左边不平衡的时候 { b=a->lchild; if(b->bf==0) { } if(b->bf==1) *t=LL(a); else *t=LR(a); } else//右边不平衡的时候 { b=a->rchild; if(b->bf==1) *t=RL(a); else *t=RR(a); } } AVLTree createBST(int size) { printf("\\n请输入各不相同的%d个关键字:\\n",size); for(k=0; k scanf(data); if(!BSTsearch(t,data))//先查找,看该关键字是否唯一,唯一则插入 BSTInsert(&t,data); else k--; } return t; } void convertBSTAVL(AVLTree *t) { AVLTree p,temp,q; PQueue Q; Q=InitQueue(); temp=NULL; if(*t) { pushQueue(Q,*t); while(!emptyQueue(Q)) { poPQueue(Q,&p); if(p->lchild) pushQueue(Q,p->lchild); if(p->rchild) pushQueue(Q,p->rchild); q=(AVLTree)malloc(sizeof(AVLNode)); q->bf=0; q->lchild=q->rchild=NULL; q->elem=p->elem; AVLInsert(&temp,q); free(p); } *t=temp; } else printf("\\n此树为空树!\\n"); destoryQueue(&Q); } 四、详细设计及说明 ①首先创建一棵普通的二元查找树，构建该树时要遵守双亲节点大于其左孩子，双亲节点小于其右孩子的原则。当插入每一个节点的时候要判断节点是否已经在二元查找树中存在，要存的话要报错，让用户重新输入数据，若不存在的话就正常插入元素。当前插入的元素肯定是当前二元查找树的叶子节点。 ②创建完树判断该树是否为平衡二叉树，从根节点开始判断每个节点的左子树深度和右子树深度，然后求他们的差，若差的绝对值小于2然后递归该判断，若差的绝对值大于2则停止判断，返回该树不是平衡二叉树，用递归算法判断一棵树是否为平衡二叉树。 ③要将一棵二元查找树转化为平衡二叉树，首先定义一个顺序队，然后将二元查找树的每一个节点的地址存放到该队中，然后让每一个节点出队，把他们插入到平衡二叉树中，在插入每一个节点之后，调整根节点到插入节点之间所有节点的bf值，如果有bf的绝对值大于2，则对不平衡的节点进行旋转，旋转的方式有四种，分别是RR,RL,LR,LL。 ④从平衡二叉树中删除一个节点，有三种情况，分别是一是所删除节点只有左子树，一是所删除节点只有右子树，然后是所删除节点左右子树都有。如果所删除节点只有左子树或只有右子树，在删除了节点后只需将节点的右子树或左子树作为其双亲节点的左子树，若所删除节点的左右子树都存在，则使其直接前驱节点的左子树成为其双亲节点的右子树节点。 ⑤从平衡二叉树中增加一个节点，先把平衡二叉树当成一般的二元查找树对待，根据双亲节点大于其左孩子，双亲节点小于其右孩子的原则将节点插入，然后将此二元查找树转化为平衡二叉树。 五、调试与测试 1 创建二元查找树 2 判断所创建的二元查找树是否为平衡二叉树 3 所创建的二叉树的树形图（注：此树的根节点在最左边，树为一棵横着的二元查找树） 很明显，此树不是平衡二叉树，然后将其转化为平衡二叉树 4 从此图可以看到现在这棵树是平衡二叉树，根节点是4 5 当平衡二叉树插入数据9后的形状 6 当平衡二叉树删除数据4后的形状，根节点为3 7 先序遍历的结果 8 中序遍历的结果 六、实习日志 2011年7月8日星期五 今天就一个事——选题，要是能选个好题的话能省好多时间，太简单的不行，选得人太多，太难也不行，不会做，所以选了个一般的，不过悲剧的是还是有人和我选重了，我很大方，把那个题让给了他，然后重新选了个题。当时那个看着挺难，是平衡二叉树的操作，仔细看后感觉这个题还可以，在我能力范围之内，然后就开使了我的编代码工作。 2011年7月9日星期六 今天的主要工作就是查找资料，主要方面是当平衡二叉树插入元素时的四种旋转和将一般二元查找树转化为平衡二叉树的代码。找了很久，还好找到了，这为我写代码提供了很大的帮助。 2011年7月10日星期日 今天开始写代码，主要是写main函数和菜单函数，感觉不太顺利，最主要的难处是协调各个函数之间的关系，不过还好，最好都搞通了。 2011年7月11日星期一 今天写了个创建一般二元查找树的函数和判断其是否为平衡二叉树的函数。因为在网上和书上都有相关的代码，而且都比较符合我的要求因此这两个函数写的很顺利。 2011年7月12日星期二 今天写了两个函数，平衡二叉树的删除操作和平衡二叉树的插入操作，删除操作感觉挺简单，再加上书上有代码，所以很快编完了，但是平衡二叉树的插入操作感觉很难，今天没有写完，插入操作里面要有很多的子函数，其中最主要的还是那四种旋转的函数和求每个节点平衡因子的函数。唉，只能明天继续了。 2011年7月14日星期四 昨天放了一天假，没有学习，今天要补上，还是要继续编那讨厌的插入操作，这段代码很重要，因为以后要是把一般二元查找树转化为平衡二叉树要用到这个函数，所以今天的重点就是变这个函数，在网上又查了些资料，这个函数涉及到很多的知识，并且需要好几个子函数，不过最终我还是把它给搞定了。 2011年7月15日星期五 今天主要编写的函数是把一般的二元查找树转化为平衡二叉树，要实现这个过程，首先要定义一个队，然后根据昨天编的那个平衡二叉树插入操作函数完成。队的ADT写过好几次，所以定义一个队比较简单，因为昨天的插入操作已经完成，所以这个函数在当天就完成了。 2011年7月16日星期六 现在已经把所有的代码都写完了，剩下的工作就是代码的调试与完善，把所能发现的BUG都统统解决掉，使程序更加的健壮，能处理更多的错误。今天已经调试的差不多了。已经开始写实习报告了。 7、实习总结 这个实习所写的代码是我上大一以来所写代码长度最长的一次，这是我有写长代码的经历，使我比较有成就感。这是我对函数的统筹兼顾与参数传递有更加深刻的了解。写程序最需要注意的就是当你的代码这里的时候参数值已经发生里什么样的变化，心里面一定要对此有很清楚，还有就是，当调用函数的时候是传递参数还是要传递参数的地址，深刻明白这一点很重要，因为有的时候只需要引用一下参数里面的内容，而有的是要改变主函数里面的内容，这进一步加深了我对指针的了解，尤其是二重指针的应用。经过这次实习，也是我熟悉了结构体的应用。经过这次实习感觉掌握了很多的知识同时也巩固了以前所学的c语言的知识和数据结构的知识，同时也使我更加熟悉编译软件的功能和操作了解了c语言原来能做如此之多的事情，感觉从中受益匪浅，希望这样的实习以后能多开一些。 8、附录：核心代码清单 /***********向二叉排序树中插入一个数据***********/ int AVLInsert(AVLTree *t,AVLTree s) { AVLTree fa,a,p; p=a=*t; fa=NULL; if((*t)==NULL) { *t=s; return true; }//判断是否为空树,是插入后就结束 if(!locateAVLNode(t,s,&fa,&a)) return false;//查找并且插入新的节点 adjustAVLbf(&a,s); if((-2 return true; else Rotate(&p,a);//判定是那种情况的旋转 if(fa==NULL) *t=p; else if(fa->elem fa->rchild=p; else fa->lchild=p; return true; } void BSTInsert(AVLTree *t,int k) { AVLTree p,q; p=*t; while(p) { q=p;//q指向p的双亲节点 if(p->elem else p=p->lchild; } p=(AVLTree)malloc(sizeof(AVLNode));//构造节点 p->elem=k; p->lchild=p->rchild=NULL; if(*t==NULL) { *t=p; return; } if(q->elem else q->lchild=p; } /**********向二叉排序树中删除一个数据*********/ int BSTDelete(AVLTree *t,int x) { if(!*t||BSTsearch(*t,x)==0) return 0; else { if(x==(*t)->elem) DeleteNode(t); else if((*t)->elem>x) BSTDelete(&(*t)->lchild,x); else BSTDelete(&(*t)->rchild,x); return 1; } } void DeleteNode(AVLTree *s) { AVLTree q,x,y; if(!(*s)->rchild) { q=*s; *s= (*s)->lchild; free(q); } else if(!(*s)->lchild) { q=*s; *s=(*s)->rchild; free(q); } else { x=*s; y=(*s)->lchild; while(y->rchild) { x=y; y=y->rchild; } (*s)->elem=y->elem; if(x!=*s) x->rchild=y->lchild; else x->lchild=y->lchild; free(y); } } /***********调整平衡因子*************/ AVLTree LL(AVLTree p) { AVLTree b; b=p->lchild; p->lchild=b->rchild; b->rchild=p; p->bf=b->bf=0; return b; } AVLTree LR(AVLTree p) { AVLTree b,c; b=p->lchild; c=b->rchild; b->rchild=c->lchild; p->lchild=c->rchild; c->lchild=b; c->rchild=p; p->bf=-1; b->bf=0; c->bf=0; return c; } AVLTree RL(AVLTree p) { AVLTree b,c; b=p->rchild; c=b->lchild; b->lchild=c->rchild; p->rchild=c->lchild; c->lchild=p; c->rchild=b; p->bf=1; b->bf=0; c->bf=0; return c; } AVLTree RR(AVLTree p) { AVLTree b; b=p->rchild; p->rchild=b->lchild; b->lchild=p; p->bf=b->bf=0; return b; } void Rotate(AVLTree *t,AVLTree a) { AVLTree b; if(a->bf==2)//左边不平衡的时候 { b=a->lchild; if(b->bf==0) { } if(b->bf==1) *t=LL(a); else *t=LR(a); } else//右边不平衡的时候 { b=a->rchild; if(b->bf==1) { *t=RL(a); } else *t=RR(a); } } AVLTree createBST(int size) { AVLTree t=NULL; int data; int k; printf("\\n请输入各不相同的%d个关键字:\\n",size); for(k=0; k scanf("%d",&data); if(!BSTsearch(t,data))//先查找,看该关键字是否唯一,唯一则插入 BSTInsert(&t,data); else { printf("你已经输入相同的数字，请再次输入\\n"); k--; } } return t; } void convertBSTAVL(AVLTree *t) { AVLTree p,temp,q; PQueue Q;//Q指向队，将树中节点的信息存入到顺序队中 Q=InitQueue(); temp=NULL; if(*t) { pushQueue(Q,*t); while(!emptyQueue(Q)) { poPQueue(Q,&p); if(p->lchild) pushQueue(Q,p->lchild); if(p->rchild) pushQueue(Q,p->rchild); q=(AVLTree)malloc(sizeof(AVLNode)); q->bf=0; q->lchild=q->rchild=NULL; q->elem=p->elem; AVLInsert(&temp,q); free(p); } *t=temp; } else printf("\\n此树为空树!\\n"); destoryQueue(&Q); }
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
