- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
实用标准文案
精彩文档
实验五
查找算法实现
1、实验目的
熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法,比较它们的平均查找长度。
2、问题描述
查找表是数据处理的重要操作, 试建立有100个结点的二叉排序树进行查找,然后用原数据建立AVL树, 并比较两者的平均查找长度。
3、基本要求
以链表作为存储结构,实现二叉排序树的建立、查找和删除。
根据给定的数据建立平衡二叉树。
4、测试数据
随即生成
5、源程序
#includeiostream.h
#includestdlib.h
#includestring.h
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)(b))
#define LQ(a,b) ((a)(b))
typedef int Keytype;
typedef struct
{ Keytype key; //关键字域
}ElemType;
typedef struct BSTnode
{ ElemType data;
int bf;
struct BSTnode *lchild,*rchild;
}BSTnode,*BSTree;
void InitBSTree(BSTree T)
{T=NULL;
}
void R_Rotate(BSTree p)
{BSTnode *lc;
lc=p-lchild;
p-lchild=lc-rchild;
lc-rchild=p;
p=lc;
}
void L_Rotate(BSTree p)
{BSTnode *rc;
rc=p-rchild;
p-rchild=rc-lchild;
rc-lchild=p;
p=rc;
}
void Leftbalance(BSTree T)
{BSTnode *lc,*rd;
lc=T-lchild;
switch(lc-bf)
{
case +1:
T-bf=lc-bf=0;
R_Rotate(T);
break;
case -1:
rd=lc-rchild;
switch(rd-bf)
{ case 1:
T-bf=-1;
lc-bf=0;
break;
case 0:
T-bf=lc-bf=0;
break;
case -1:
T-bf=0;
lc-bf=1;
break;
}
rd-bf=0;
L_Rotate(T-lchild);
R_Rotate(T);
}
}
void Rbalance(BSTree T)
{BSTnode *lc,*ld;
lc=T-rchild;
switch(lc-bf)
{ case 1:
ld=lc-lchild;
switch(ld-bf)
{ case 1:
T-bf=0;
lc-bf=-1;
break;
case 0:
T-bf=lc-bf=0;
break;
case -1:
T-bf=1;
lc-bf=0;
break;
}
ld-bf=0;
R_Rotate(T-rchild);
L_Rotate(T);
case -1:
T-bf=lc-bf=0;
L_Rotate(T);
break;
}
}
int InsertAVL(BSTree T,ElemType e,bool taller)
{ if(!T)
{ T=(BSTree)malloc(sizeof(BSTnode));
T-data=e;
T-lchild=T-rchild=NULL;
T-bf=0;
taller=true;
}
else
{ if(EQ(e.key,T-data.key))
{ taller=false;
cout结点 e.key 不存在。endl;
return 0;
}
if(LT(e.key,T-data.key))
{ if(!InsertAVL(T-lchild,e,
文档评论(0)