- 1、本文档共129页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[工学]5-第三章 查找与排序技术
* * * * * * * 第三章 查找与排序技术 向右兄弟结点借元素 结点联合调整:b中最大关键字(借过来的关键字)上移,a中刚刚大于被删关键字的关键字下移 55 60 70 10 40 58 65 75 80 a c b d f g h 55 60 70 10 40 58 65 75 80 a c b d f g h 第三章 查找与排序技术 60 55 70 10 40 58 65 75 80 a c b d f g h 第三章 查找与排序技术 60 55 70 10 58 65 75 80 a c b d f g h 用58取代 删除55 合并d, f,父结点相应关键字下移 60 58 70 10 65 75 80 a c b d g h f 第三章 查找与排序技术 合并b,c,父结点相应关键字下移,并删除根结点 60 70 10 58 65 75 80 c d g h 60 70 10 58 65 75 80 a c b d g h B-树删除的C语言实现,参照课本P215 上文回顾 二叉排序树 B-树 定义 创建和插入 查找 删除 定义 查找 创建和插入 删除 B-树的按值输出: 按值输出B-树中各关键字元素,类似于二叉树的中序遍历。由于B-树中的每个结点最多有2m个关键字和2m+1个指针,因此,按值大小遍历输出B-树中各关键字值的过程如下: 从B-树的根结点开始,对每一个非空结点中的关键字与,依次做如下操作: 1、沿关键字左指针指向的结点做同样的动作。 2、输出关键字值 最后沿该结点最后一个指针指向的结点做同样的操作 第三章 查找与排序技术 B-树的按值输出的C语言表述: 第三章 查找与排序技术 void Output_Balanced_Tree(struct BTNode *T) { int n; struct BTNode *p=T; if (p!=NULL) { for (n=0;nT-num;n++) { Output_Balanced_Tree(p-link[n]); printf(%d , p-key[n]); } Output_Balanced_Tree(p-link[n]); } } * * * * * * * * * * * * * * * * * * * * M就是Hash表的长度,一般取为素数 * * * * * 二叉排序树的删除算法 if((p-lchild==NULL)(p-rchild==NULL)) { if (p==T) T=NULL; else if (p==parent-lchild) parent-lchild=NULL; else parent-rchild=NULL; free(p);} else if ((p-lchild==NULL)||(p-rchild==NULL)) { if (p==T) { if(p-lchild==NULL) T=p-rchild; else T=p-lchild;} else { if ((p==parent-lchild)(p-lchild!=NULL)) parent-lchild=p-lchild; 第三章 查找与排序技术 //删除叶子结点 //叶子结点同时为根结点 //释放结点 //删除结点拥有单子树 //同时为根结点 //不为根结点 //共需要分四种情况 二叉排序树的删除算法 else if ((p==parent-lchild)(p-rchild!=NULL)) parent-lchild=p-rchild; else if ((p==parent-rchild)(p-lchild!=NULL)) parent-rchild=p-lchild; else parent-rchild=p-rchild; } free (p); } 第三章 查找与排序技术 //释放结点 二叉排序树的删除算法 else {temp=p; s=temp-lchild; while (s-rchild!=NULL) { temp=s;s=s-rchild;} p-
文档评论(0)