二叉搜索树的前驱和后继

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


二叉搜索树

二叉搜索树(Binary Search Tree,简写BST),又称为二叉排序树,属于树的一种,通过二叉树将数据组织起来,树的每个节点都包含了健值 key、数据值 data、左子节点指针、右子节点指针。其中健值 key 是最核心的部分,它的值决定了树的组织形状;数据值 data 是该节点对应的数据,有些场景可以忽略,举个例子,key 为身份证号而 data 为人名,通过身份证号找人名;左子节点指针指向左子节点;右子节点指针指向右子节点。

二叉搜索树特点

  • 左右子树也分别是二叉搜索树。
  • 左子树的所有节点 key 值都小于它的根节点的 key 值。
  • 右子树的所有节点 key 值都大于他的根节点的 key 值。
  • 二叉搜索树可以为一棵空树。
  • 一般来说,树中的每个节点的 key 值都不相等,但根据需要也可以将相同的 key 值插入树中。

image

中序前驱节点

二叉树通过某种方式遍历后会得到一个序列结果,而某个节点的前驱节点就是该序列的前一个节点。由于中序遍历得到的序列的 key 值是按从小到大顺序排列的,所以在中序遍历下,某节点的前驱就是小于该节点的所有节点中最大的那个节点。

找中序前驱节点就是找小于某个节点的最大节点。主要有三种情况:

情况一

如果某个节点存在左子节点,那么左子节点(子树)下中的最大 key 值节点即是前驱。看下这种情况,找“C”节点的前驱,

image

存在左子节点“A”,找“A”下的最大值,

image

找到“B”为最大值,于是“B”即为“C”节点的前驱。

image

情况二

如果某个节点没有左子节点,而且如果该节点为其父节点的右子节点,那么该节点的父节点即为该节点的前驱。看下这种情况,找“D”节点的前驱,

image

“D”节点没有左子节点,且“D”为“C”节点的右子节点,所以“C”即是前驱,

image

情况三

如果某个节点没有左子节点,而且如果该节点为其父节点的左子节点,那么就往顶端寻找,直到找到一个节点是其父节点的右子节点,该父节点就是要找的前驱。看下这种情况,找“F”节点的前驱,

image

“F”节点没有左子节点,且“F”节点为其父节点的左子节点,于是往顶端寻找,

image

“G”节点是其父节点的右子节点,于是“G”节点的父节点即为要找的前驱,即是“E”节点。

image

中序后继节点

与前驱节点相应的,通过中序遍历后会得到一个序列结果,这时某个节点的后继节点就是该序列的后一个节点。由于中序遍历得到的序列的 key 值是按从小到大顺序排列的,所以某节点的后继就是大于该节点的所有节点中最小的那个节点。

找中序后继节点就是找大于某个节点的最小节点。同样有三种情况:

情况一

如果某个节点存在右子节点,那么右子节点(子树)下中的最小 key 值节点即是后继。看下这种情况,找“E”节点的后继,

image

“E”节点存在右子节点“G”,找到“G”下的最小值,

image

最小值即一直往左找,“F”即是最小值,找到后继。

image

情况二

如果某个节点没有右子节点,而且如果该节点为其父节点的左子节点,那么该节点的父节点即为该节点的后继。看下这种情况,找“F”节点的后继,

image

“F”节点没有右子节点,且“F”为“G”节点的左子节点,所以“G”即是后继,

image

情况三

如果某个节点没有右子节点,而且如果该节点为其父节点的右子节点,那么就往顶端寻找,直到找到一个节点是其父节点的左子节点,该父节点就是要找的后继。看下这种情况,找“B”节点的后继,

image

“B”节点没有右子节点,且“B”节点为其父节点的右子节点,于是往顶端寻找,

image

“A”节点是其父节点的左子节点,于是“A”节点的父节点即为要找的后继,即是“C”节点。

image

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 二叉搜索树的前驱和后继
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏