二叉查找树图解
二叉查找树（Binary Search Tree），又叫二叉搜索对或二叉排序树，是一种数据结构，采用了图的树形结构。数据存储于二叉查找树的各个结点中，每个结点最多有两个子结点，如下图示。
结点中的数字是存储的数据，且前提是不存在相同的数字
二叉查找树性质
二叉查找树具有以下性质：
- 1、每个结点的值均大于其左子树上任意一个结点的值，例如结点 8 大于其左子树上任意一个结点的值；
- 2、每个结点的值均小于其右子树上任意一个结点的值，例如结点 10 大于其右子树上的 14 和 13；
- 3、任意结点的左、右子树也分别为二叉查找树；
根据上述性质，我们可以得出推论：二叉查找树的最小结点，要从顶端开始往其左侧的末端寻找，图示二叉查找树的最小值为 1；相反地，二叉查找树的最大结点，要从顶端开始往其右侧的末端寻找，图示二叉查找树的最大值为 14。
添加数据结点
我们尝试往图示二叉查找树添加数字 2，具体演变过程如下：
- 从二叉查找树的顶端结点开始寻找添加数字的位置，将要添加的 2 与结点中的值（假设为 x）进行比较，小于 x 则往左移，大于 x 则往右移；
- 与 8 比较，由于 2 小于 8，所以将其往左移；
- 左移后遇到结点 3，由于 2 小于 3，所以继续将其往左移；
- 左移后遇到结点 1，由于 2 大于 1，需要将其往右移，但结点 1 没有子结点了，所以把 2 作为新结点添加；
- 根据二叉查找树性质，需要交换结点 1 与 新结点 2 的位置，即结点 2 为结点 3 的左子树，为结点 1 的父结点。
下图为添加数字 2 后的最终二叉查找树：
我们尝试再往上图二叉查找树添加数字 15，按照上述演变过程，得到下图所示最终效果：
查找数据结点
在二叉查找树中查找目标结点，是从根结点出发，先将根结点和目标结点做比较：
- 与添加数据时一样，目标结点与二叉查找树其它结点中的值逐个比较，小于该结点的值则往左子树查找，大于则往右子树查找。
- 若目标值对应的结点不存在，则查找失败；若当前结点的值和目标结点值相等，则查找成功；
我们来尝试如何在二叉查找树（上图示）中查找结点 6。由于6 < 8，所以往左子树查找；遇到结点 3，因3 > 6，所以往右子树查找，最终找到结点 6。以下为查找过程图示：
删除数据结点
删除二叉查找树中已有的结点，必须确保整棵树还是二叉查找树，即删除的同时需要妥善处理它的左、右子树，可以归结为以下 3 种情况：
- 如果需要删除的结点是叶子结点（也就是说没有子结点），直接删除该结点即可，整棵树还是二叉查找树。我们尝试删除刚刚添加的结点 15，直接删除它并不会破坏二叉查找树的结构。得到如下图示效果：
- 如果需要删除的结点只有一个子结点，那么先删除目标结点，然后把子结点移到被删除结点的位置上即可。比如我们尝试删除上图结点 2，得到本文最初二叉查找树图示：
- 如果需要删除的结点有两个子结点，那么先删除目标结点，然后在被删除结点的左子树中寻找最大结点，并将最大结点移到被删除结点的位置上。比如我们尝试删除上图结点 8，得到如下图示效果：
这样，就能在满足二叉查找树性质的前提下删除结点了。如果需要移动的结点还有子结点，就递归执行前面的操作。
有很多数据结构是以二叉查找树为基础，比如“平衡二叉查找树”。这种数据结构可以修正形状不平衡的树，让其始终保持均衡形态，以提高查找效率。
关于二叉查找树新增、查找和删除数据结点的具体算法，限于篇幅原因，将在后续文章进行介绍。