1万+  考点词条:  标题检索     全文检索
动态查找表
       二叉排序树
       二叉排序树又称为二叉查找树,它或者是一棵空树,或者是满足以下性质的二叉树。
       (1)若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
       (2)若它的右子树非空,则右子树上所有节点的值均大于根节点的值。
       (3)左、右子树本身就是两棵二叉排序树。
       二叉排序树的查找过程是:若二叉排序树非空,则将给定值与根节点的关键字值相比较,若相等,则查找成功;若不等,则当根节点的关键字值大于给定值时,到根的左子树中进行查找;否则到根的右子树中进行查找。若找到,则查找过程是走了一条从树根到所找到节点的路径;否则查找过程终止于一棵空树。
       二叉排序树中插入节点的操作:每读入一个元素,建立一个新节点,若二叉树非空,则将新节点的值与根节点的值相比较,如果小于根节点的值,则插入到左子树中,否则插入到右子树中;若二叉排序树为空,则新节点作为二叉排序树的根节点。
       二叉排序树中删除节点的操作:在二叉树中删除一个节点,不能把以该节点为根的子树都删除,只能删除这个节点并仍旧保持二叉排序树的特性,也就是说,删除二叉排序树上一个节点相当于删除有序数列中的一个元素。假设二叉排序树上的被删除节点为*pp指针指向被删除节点),*f为其双亲节点,则删除节点*p的过程可分为以下3种情况。
       ①若*p节点为叶子节点,即p→lchild及p→rchild均为空,则由于删去叶子节点后不破坏整棵树的结构,因此只需修改*p节点的双亲节点*f的相应指针即可,即f→lchild(或f→rchild)=NULL。
       ②若*p节点只有左子树或者只有右子树,此时只要将*p的左子树或右子树接成其双亲节点*f左子树或右子树,即令f→lchild(或f→rchild)=p→lchild,或f→lchild(或f→rchild)=p→rchild。
       ③若*p节点的左、右子树均不空,则不能像上面那样简单处理,删除*p节点时应将*p的左子树、右子树连接到适当的位置,并保持二叉排序树的特性。可采用以下两种方法进行处理:一是令*p的左子树为*f的左(或右)子树,而将*p的右子树下接到*p的中序遍历的直接前驱节点*s的右孩子指针上;二是用*p的中序直接前驱(或后继)节点*s代替*p节点,然后删除*s节点。
       平衡二叉树
       平衡二叉树又称为AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左、右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1;若将二叉树节点的平衡因子定义为该节点的左子树的深度减去其右子树的深度,则平衡树上所有节点的平衡因子只可能是-1、0和1;只要树上有一个节点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。
       平衡二叉树上的插入操作。失去平衡后进行调整的规律可归纳为4种情况:①单向右旋平衡处理;②单向左旋平衡处理;③双向旋转(从左到右)平衡处理;④双向旋转(从右到左)平衡处理。
       平衡二叉树上的删除操作:若删除节点的两个子树都不为空,就用该节点左子树上的中序遍历的最后一个节点(或其右子树上的第一个节点)替换该节点,将情况转化为待删除的节点只有一个子树后再进行处理。当一个节点被删除后,从被删节点到树根的路径上所有节点的平衡因子都需要更新,对于每一个位于该路径上的平衡因子为±2的节点来说,都要进行平衡处理。
       B-树
       B-树的定义:一棵m阶的B-树,或为空树,或为满足下列特性的m叉树。
未完............


 相关词条:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京ICP证140039号 | 京ICP备13027030号-1 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2019 All Rights Reserved 软考在线版权所有