大家好，欢迎来到IT知识分享网。
前言
推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。
二叉搜索树
二叉搜索树(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”节点。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/60124.html
