前言
推出一个新系列,《看图轻松理解数据结构和算法》, 主要使用图片来描述常见的数据结构和算法, 轻松阅读并理解掌握. 本系列包括各种堆, 各种队列, 各种列表, 各种树, 各种图, 各种排序等等几十篇的样子.
二叉搜索树
二叉搜索树 (Binary Search Tree, 简写 BST), 又称为二叉排序树, 属于树的一种, 通过二叉树将数据组织起来, 树的每个节点都包含了健值 key, 数据值 data, 左子节点指针, 右子节点指针. 其中健值 key 是最核心的部分, 它的值决定了树的组织形状; 数据值 data 是该节点对应的数据, 有些场景可以忽略, 举个例子, key 为身份证号而 data 为人名, 通过身份证号找人名; 左子节点指针指向左子节点; 右子节点指针指向右子节点.
二叉搜索树特点
左右子树也分别是二叉搜索树.
左子树的所有节点 key 值都小于它的根节点的 key 值.
右子树的所有节点 key 值都大于他的根节点的 key 值.
二叉搜索树可以为一棵空树.
一般来说, 树中的每个节点的 key 值都不相等, 但根据需要也可以将相同的 key 值插入树中.
中序遍历
我们知道对于二叉树来说, 遍历的方式一般有三种: 前序遍历, 中序遍历和后序遍历. 但对于二叉搜索树, 比较常用的是中序遍历, 因为通过该种方式遍历出来的元素属于一个递增序列.
开始中序遍历, 即是以 "左根右" 方式遍历, 先找到 "A",
接着找到 "B",
往下一个个获取,
树的最小 key 值
二叉搜索树的最小 key 值节点从根节点开始一直沿着左子节点搜索, 直到遇到节点的左子节点指针为空, 即找到最小值节点. 因为二叉搜索树中左边的节点总是小于右边的节点, 所以一直往左寻找.
从根节点开始,
往左查找,
再往左, 到达 "A" 节点, 没有左子节点了, 停止搜索, 找到最小值.
树的最大 key 值
二叉搜索树的最大 key 值节点从根节点开始一直沿着右子节点搜索, 直到遇到节点的右子节点指针为空, 即找到最大值节点. 因为二叉搜索树中右边的节点总是大于左边的节点, 所以一直往右寻找.
从根节点开始,
往右查找,
再往右, 到达 "H" 节点, 没有右子节点了, 停止搜索, 找到最大值.
来源: https://juejin.im/post/5c85a9dee51d450b662a060e