西北农林科技大学信息工程学院
《数据结构与C语言综合训练》实习
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
题 目:AVL Tree的实现及
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
学 号
************
姓 名
*************
专业班级
计算机科学与技术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((-2bf)&&(a->bf<2))//说明插入该顶点后仍然是平衡的
return true;
else
Rotate(&p,a);//判定是那种情况的旋转
if(fa==NULL)
*t=p;
else if(fa->elemelem)
fa->rchild=p;
else
fa->lchild=p;
return true;
}
void BSTInsert(AVLTree *t,int k)
{
p=*t;
while(p)
{
q=p;
if(p->elemrchild;
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->elemrchild=p;
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; klchild)
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后的形状
继续阅读