二分搜索树的前身和后继

电脑杂谈  发布时间:2020-07-03 10:19:15  来源:网络整理

树,森林与二叉树的转换_二叉树前驱后继_树和二叉树的转换

您必须全面了解二叉树,那么二叉搜索树是什么?首先给出每个节点的属性: 1)关键字关键字2)p父节点3)左左子代4)右右子代定义如下: 对于任何节点x,左子树的关键字不超过x .key ,右子树的键必须至少为x.key. 以下所有属性都是围绕此定义开发的. 方法: 1)遍历搜索二叉树: 与遍历普通二叉树相同,按照中间和背面的顺序,这取决于您的选择. 时间复杂度为O(n). n是节点数. 2)搜索二叉树: 由于二叉树的定义规则,搜索就像二分法,并且时间复杂度为O(h). h是树的高度3)搜索树的最大和最小关键字: 类似于搜索二叉树,根据定义的规则,时间复杂度为O(h)4)插入和删除的时间复杂度为也是O(h). 插入相对简单. 这与搜索二叉树直到该节点为空相同,然后该节点的位置就是插入位置. 删除要复杂一些,需要考虑三种情况. 我的重点是前任和后继.

树,森林与二叉树的转换_二叉树前驱后继_树和二叉树的转换

前辈和前辈

树,森林与二叉树的转换_树和二叉树的转换_二叉树前驱后继

什么是后继者和前任者,如果对数节点的键顺序为: key1 <= key2 <= ...... <= keyn3 <= keyn2 <= keyn1 <= keyn,则keyn3和keyn1为keyn2. 寻找节点的后继者的前任者和后继者分为两种情况,即: 1)节点的右子树不为空; 2)将节点的右子树更改为空. 下面说明这两种情况. 1)右子树R不为空. 在这种情况下,找到继任者相对简单. 知道了搜索二叉树的定义后,如果我们通过Zhong Xu遍历二叉树,则输出关键字将按从小到大的顺序排序. 也就是说二叉树前驱后继,在遍历该节点之后,应遍历该节点的右子树,并且右子树不为空,指示该节点的后继必须在右子树中,并且具有最小键的节点在右子树中. 子树具有最小的键可以通过方法3)计算. 2)右子树R为空. 问题在于访问节点a之后,我们接下来应该访问哪个节点?首先要确定的是,接下来要访问的节点是根节点. 为什么?因为我们必须承认,除了根节点之外,任何节点都是节点子树的一部分. 对于右子树为空的情况二叉树前驱后继,在访问节点a之后,访问以该节点为根节点的树Z. 接下来,可以在两种情况下进行分析. 树Z是上一个节点的左子树. 显然,在访问了左子树Z之后,是时候访问子树的根节点e了. 然后,根节点是节点a的后继节点. 如果该子树是前一个节点的右子树Z,则意味着在访问根节点e之后访问了右子树. 因此,它的后继节点应该仍然位于较高的节点上,直到遇到该节点所在的子树是某个节点q的左子树的一部分为止. 节点q是此节点的后继节点. 前体前体和后继体是对称的,在此不再赘述. 1)如果节点的左子树不为空,则该节点的前任节点为左子树的最右节点(最大节点)2)如果该节点的左子树为空,则该节点继续返回其子树父节点,知道某个节点是其父节点的正确节点,那么父节点就是后继节点


本文来自电脑杂谈,转载请注明本文网址:
http://www.pc-fly.com/a/jisuanjixue/article-266848-1.html

    相关阅读
    发表评论  请自觉遵守互联网相关的政策法规,严禁发布、暴力、反动的言论

    热点图片
    拼命载入中...