二叉查找树是二叉树中比较常见且常用的类型，也叫二叉搜索树。二叉查找树要求二叉树中的任意一个节点满足以下要求
- 左子树中的每个节点的值都小于该节点
-
右子树中的每个节点的值都大于该节点
如图所示，就是一颗二叉查找树
二叉查找树
下面我们来看下二叉查找树的查找、插入、删除动作是怎么实现的
二叉查找树的查找
二叉树的查找是先从根节点开始，将待查找值和当前节点（最开始是根节点）进行比较，如果比当前节点的值小，则进入其左子树重复该步骤，如果比根节点的值大，则进入其右子树重复该步骤。图示，查找一个值为21的节点
查找值21
加上代码，方便理解
package tree;
/**
* @author TioSun
* 二叉查找树
*/
public class BinarySearchTree {
private TreeNode tree;
public TreeNode find(int data) {
TreeNode currentNode = tree;
while (currentNode != null) {
// 待查找值大于当前值，访问其右子树
if (data > currentNode.data) {
currentNode = currentNode.right;
// 待查找值小于当前值，访问其左子树
}else if (data < currentNode.data) {
currentNode = currentNode.left;
}else {
return currentNode;
}
}
return null;
}
public static class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data) {
this.data = data;
}
}
}
二叉查找树的查找很简单，就不多说了，下面来看看二叉查找树的插入
二叉查找树的插入
和二叉查找树的搜索类似，二叉查找树的插入是将待插入值和当前节点（最开始是根节点）进行比较，如果比当前节点小，则判断其左子节点是否为空，如果为空则插入，如果不为空，则进入其左子节点重复该步骤；如果比当前节点大，则判断其右子节点是否为空，如果为空则插入，如果不为空则进入其右子节点，重复该步骤。
package tree;
/**
* @author TioSun
* 二叉查找树
*/
public class BinarySearchTree {
private TreeNode tree;
public void insert(int data) {
if (tree == null) {
tree = new TreeNode(data);
return;
}
TreeNode currentNode = tree;
while (currentNode != null) {
if (data > currentNode.data) {
if (currentNode.right == null) {
currentNode.right = new TreeNode(data);
return;
}
currentNode = currentNode.right;
}else {
if (currentNode.left == null) {
currentNode.left = new TreeNode(data);
return;
}
currentNode = currentNode.left;
}
}
}
public static class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data) {
this.data = data;
}
}
}
二叉查找树的插入也很简单，下面来看下稍微复杂点的二叉查找树的删除
二叉查找树的删除
二叉查找树的删除比较复杂，根据删除的节点不同分为三种情况
- 删除的节点是叶子节点，则只需要将其父节点指向删除节点的指针指为null就好了，例如上图中的17。
- 删除的节点只有一个子节点，这种情况也比较简单，只需将删除节点的父节点指向删除节点的指针重新指向为删除节点的子节点就好，以上图为例，要删除节点8，只需将11指向8的指针指向10就可以了。
- 删除的节点有两个子节点，这种情况是比较复杂的，我们需要将待删除节点上的值赋值为其右子树上的最小节点的值，然后再删除掉这个最小的节点，由于是最小的节点，所以肯定没有左子节点，所以只需要再参照第一条或第二条的方式删除即可。
package tree;
/**
* @author TioSun
* 二叉查找树
*/
public class BinarySearchTree {
private TreeNode tree;
public void delete (int data) {
TreeNode needDelete = tree;
TreeNode needDeleteParent = null;
// 定位需要删除的节点。
while (needDelete != null && needDelete.data != data) {
needDeleteParent = needDelete;
if (data > needDelete.data) {
needDelete = needDelete.right;
}else {
needDelete = needDelete.left;
}
}
if (needDelete == null) {
return;
}
// 第三种情况，待删除节点的左右子节点都不为空
if (needDelete.left != null && needDelete.right != null) {
TreeNode minNode = needDelete.right;
TreeNode minNodeParent = needDelete;
while (minNode.left != null) {
minNodeParent = minNode;
minNode = minNode.left;
}
// 将待删除的节点用其右子树下的最小节点替换
needDelete.data = minNode.data;
// 将待删除的节点定位到最小节点上
needDelete = minNode;
needDeleteParent = minNodeParent;
}
// 删除只有一个或零个子节点的节点
// 获取要删除的节点的子节点
TreeNode child = null;
if (needDelete.left != null) {
child = needDelete.left;
}else if (needDelete.right != null) {
child = needDelete.right;
}
// parentNode为空，说明要删除的是根节点
if (needDeleteParent == null) {
tree = child;
}
// 如果要删除的是parent的左子节点，则将左子节点重新指向待删除节点的子节点
if (needDeleteParent.left == needDelete) {
needDeleteParent.left = child;
}else {
// 如果要删除的是parent的右子节点，则将右子节点重新指向待删除节点的子节点
needDeleteParent.right = child;
}
}
public static class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data) {
this.data = data;
}
}
}
除了上述的常规操作以外，二叉树还支持快速查找最大值（不停的right），最小值（不停的left）以及输出有序序列（中序遍历）等，就不一一用代码展示了。
如何处理重复数据
对于重复数据的处理，一般有两种做法
- 第一种做法比较简单好懂，以上文为例，就是将data变成一个数组或链表结构去存储相关数据。
- 第二种比较不好理解，但是形式上可能更加优雅。下面详细介绍第二种做法
重复数据的插入
重复数据的插入，我们可以将其插入已存在数据的右子树上，插入逻辑和普通的插入逻辑相同。
重复数据的查询
重复数据的查询，我们可以在查到相关数据后，不直接返回，而是继续往其右子树上查找，直到查到叶子节点为止，输出的也是一串符合查找条件的值。
重复数据的删除
重复数据的删除也和普通的删除类似，不过也是往右子树上遍历去删除所有满足条件的节点。
