- 1、本文档共90页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
顺序查找的算法如下: int SeqSearch1(SeqList R,int n,KeyType k) {//在顺序表R[1..n]中查找关键字为k的记录,成功时 //返回找到的记录位置,失败时返回0 int i; R[0].key=k; //哨兵 for (i=n; R[i].key!=k; i--) ; //从表尾往前找 return i; } 例如 关键字序列为: {1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}。 创建一棵5阶B-树。 建立B-的过程如下图所示。 3. B-树的删除 B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的关键字个数≥?m/2?-1,将涉及到结点的“合并”问题。在B-树上删除关键字k的过程分两步完成: (1) 利用前述的B-树的查找算法找出该关键字所在的结点。 (2) 在结点上删除关键字k分两种情况:一种是在叶子结点上删除关键字;另一种是在非叶子结点上删除关键字。 2. 二叉排序树的插入和生成 在二叉排序树中插入一个新记录,要保证插入后仍满足BST性质。其插入过程是:若二叉排序树T为空,则创建一个key域为k的结点,将它作为根结点;否则将k和根结点的关键字比较,若二者相等,则说明树中已有此关键字k,无须插入,直接返回0;若kT-key,则将k插入根结点的左子树中,否则将它插入右子树中。对应的递归算法InsertBST()如下: int InsertBST(BSTNode *p,KeyType k) /*在以*p为根结点的BST中插入一个关键字为k的结点。插入成功返回1,否则返回0*/ { if (p==NULL) /*原树为空, 新插入的记录为根结点*/ { p=(BSTNode *)malloc(sizeof(BSTNode)); p-key=k;p-lchild=p-rchild=NULL; return 1; } else if (k==p-key) /*存在相同关键字的结点,返回0*/ return 0; else if (kp-key) return InsertBST(p-lchild,k);/*插入到左子树中*/ else return InsertBST(p-rchild,k); /*插入到右子树中*/ } 二叉排序树的生成,是从一个空树开始,每插入一个关键字,就调用一次插入算法将它插入到当前已生成的二叉排序树中。从关键字数组A[0..n-1]生成二叉排序树的算法CreatBST()如下: BSTNode *CreatBST(KeyType A[],int n) /*返回树根指针*/ { BSTNode *bt=NULL; /*初始时bt为空树*/ int i=0; while (in) { InsertBST(bt,A[i]); /*将A[i]插入二叉排序树T中*/ i++; } return bt; /*返回建立的二叉排序树的根指针*/ } 例10.2 已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。 解:生成的二叉排序树如右图所示。 3. 二叉排序树的删除 删除操作必须首先进行查找,假设在查找过程结束时,已经保存了待删除结点及其双亲结点的地址。指针变量p指向待删除的结点,指针变量q指向待删除结点p的双亲结点。删除过程如下: (1) 若待删除的结点是叶子结点,直接删去该结点。如图(a)所示,直接删除结点9。这是最简单的删除结点的情况。 (2) 若待删除的结点只有左子树而无右子树。根据二叉排序树的特点,可以直接将其左子树的根结点放在被删结点的位置。如图(b)所示,*p作为*q的右子树根结点,要删除*p结点,只需将*p的左子树(其根结点为3)作为*q结点的右子树。 (3) 若待删除的结点只有右子树而无左子树。与(2)情况类似,可以直接将其
您可能关注的文档
- (课件)乳腺癌诊治-公开课件.ppt
- (年东北大学秦皇岛分校数学与统计学院崔向南版)-公开课件.ppt
- (上)高三月学情调研-公开课件.ppt
- (苏教版)六年级语文上册课件青海高原一株柳-公开课件.ppt
- (用)高二历史《第课“罢黜百家,独尊儒术”-公开课件.ppt
- [管理]管理团队-公开课件.ppt
- [清新背景]蕾苞初绽的花萃,免费,非常怡人悦目的各种花-公开课件.ppt
- [清新背景]蕾苞初绽的花萃,免费,罕见的各种蕾苞初绽的-公开课件.ppt
- [小六上]两小儿辩日(人教版)-公开课件.ppt
- [医学微生物学][复习资料]-公开课件.ppt
- 10《那一年,面包飘香》教案.docx
- 13 花钟 教学设计-2023-2024学年三年级下册语文统编版.docx
- 2024-2025学年中职学校心理健康教育与霸凌预防的设计.docx
- 2024-2025学年中职生反思与行动的反霸凌教学设计.docx
- 2023-2024学年人教版小学数学一年级上册5.docx
- 4.1.1 线段、射线、直线 教学设计 2024-2025学年北师大版七年级数学上册.docx
- 川教版(2024)三年级上册 2.2在线导航选路线 教案.docx
- Unit 8 Dolls (教学设计)-2024-2025学年译林版(三起)英语四年级上册.docx
- 高一上学期体育与健康人教版 “贪吃蛇”耐久跑 教案.docx
- 第1课时 亿以内数的认识(教学设计)-2024-2025学年四年级上册数学人教版.docx
文档评论(0)