二叉搜索树之前驱后继

什么是二叉搜索树

想必对二叉树都有了解，那么什么是二叉搜索树呢？ 首先给出每个节点的属性： 1)key$key$ 关键字 2)p$p$ 父亲节点 3)left$left$ 左孩子 4)right$right$ 右孩子 其定义如下： 对于任何的节点x$x$，其左子树的关键字最大不超过x.key$x.key$，其右子树的关键字最小不小于x.key$x.key$。 下面的所有性质都是围绕该定义展开的。 方法： 1)遍历搜索二叉树：同遍历普通二叉树一般，前中后序，随你怎么来。时间复杂度为O(n)$O(n)$。n$n$为节点数 2)搜索二叉树：由于二叉树的定义规则，所以搜索的时候如同二分法，时间复杂度为O(h)$O(h)$。h$h$为树的高度 3)搜索树的最大最小关键字：同搜索二叉树类似，依据定义的规则，时间复杂度为O(h)$O(h)$ 4)插入删除的时间复杂度同样也为O(h)$O(h)$。插入比较简单，同搜索二叉树，直到出现节点为空，则该节点的位置即为插入位置；删除稍微复杂一些，需要考虑三种情况，不再细说，因为这些不是我想介绍的重点。我重点希望讲的是前驱和后继。

后继和前驱

什么是后继和前驱，如果对数的节点的关键字排序： key1<=key2<=......<=keyn−3<=keyn−2<=keyn−1<=keyn$key_1<=key_2<=......<=key_{n-3}<=key_{n-2}<=key_{n-1}<=key_{n}$，那么keyn−3$key_{n-3}$和keyn−1$key_{n-1}$就是keyn−2$key_{n-2}$的前驱和后继 后继 寻找节点的后继被分为两种情况，分别是1)该节点的右子树非空；2)改节点的右子树为空。下面分别解释这两种情况 1)右子树R$R$非空。这种情况下的寻找后继相对简单。对搜索二叉树的定义的了解可知，如果通过钟旭遍历二叉树，那么输出的关键字正好是从小到大排序。即遍历该节点之后应该要遍历该节点的右子树，而右子树非空，说明该节点的后继必定在该右子树中，且是右子树的关键字最小的节点，关键字最小的节点可以通过方法3)计算得到。 2)右子树R$R$为空。该问题也就是访问完该节点a$a$，接下来该访问哪一个节点了呢？首先可以肯定的是，接下来要访问的节点是一个根节点。为什么呢？因为我们必须承认，除了根节点以外，任何节点都是某个节点的子树中的一部分。而对于右子树为空的情况，当访问完该节点a$a$后，以该节点作为根节点的树Z$Z$访问结束了。接下来可以分两种情况分析，该树Z$Z$为上一级节点的左子树，显而易见，访问完左子树Z$Z$就该访问该子树的根节点e$e$了。那么该根节点就是该节点a$a$的后继。若该子树为上一级节点的右子树Z$Z$，那么说明是访问完该根节点e$e$后再访问右子树的。所以其后继应该还在更上层的节点，直到遇到该节点所在的子树是某个节点q$q$的左子树的一部分为止。节点q$q$就是该节点的后继。 前驱 前驱和后继对称，不在赘述。 1）如果节点的左子树非空，那么该节点的前驱就是左子树的最右边的节点（最大节点） 2）如果节点的左子树为空，那么就以该节点不断回到其双亲节点，知道找到某个节点为其双亲节点的右节点 则该双亲节点即为后继