详解二叉搜索树(BST)的Java实现和五种遍历方式
树是一种典型的数据结构。今天我们来了解一下，一种特殊的树，二叉搜索树(BST)，二叉搜索树在我们的实际开发过程中应用还是很广泛的，
在我们的HashMap中，红黑树(一种特殊的二叉搜索树)，是我们解决Hash冲突的一种方式。
今天我们来好好了解一下我们的二叉搜索树。
1.二叉搜索树的特征：
对于树中的每一个节点，它的左子树中的节点值都小于该节点的值，而它的右子树中的节点值都大于该节点值。如下图所示：
2.二叉搜索树的表示：
在我们的开发过程中,我们可以使用一个链式节点的集合来表示我们的二叉搜索树。在我们定义的节点中包含一个节点当前节点的指向，一个left指向，一个right指向，表示当前节点，当前节点的左节点，当前节点的右节点。如下代码所示：
public class TreeNode<E> {
//当前节点
protected E element;
//当前节点的左节点
protected TreeNode<E> left;
//当前节点的右节点
protected TreeNode<E> right;
public TreeNode(E element) {
this.element = element;
}
}
3.插入一个树
当我们需要在BST插入一个节点时，我们首先要确定其父节点的位置。那么父节点的位置，我们怎么来确定呢？首先我们现在已经知道二叉搜索树的排列是有一定规律可循的。左边的节点值都小于根节点，右边节点的值都大于根节点，其实这个就类似与我们的二分法。‘
当我们插入一个节点时，如果当前二叉树是空的，那我们就把当前要插入的节点，作为二叉树的根节点。如果当前BST不为空，我们从根节点开始，遍历，如果我们要插入的值小于当前节点的值，我们就去遍历它的左子树，如果我们要插入的值大于当前节点的值，我们就去遍历它的右子树，直到，我们找到要插入节点的父节点(直到我们找到一个空子树)。下面我们来看看Java代码的实现：
//插入成功返回true,否则返回false
public boolean insert(E o) {
//如果根节点为空，新建一个节点作为当前二叉树的根节点
if (root == null) {
TreeNode<E> treeNode = new TreeNode<>(o);
root = treeNode;
} else {
//用来记录我们插入的节点的父节点
TreeNode<E> parent = null;
//记作当前节点
TreeNode<E> current = root;
//current为null，跳出循环，parent节点代表我们要插入元素的父节点
while (current != null) {
//如果我们要插入的节点小于当前节点，就去遍历其左子树
//否则遍历右子树
if (o.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (o.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
//树中存在当前要插入的元素，则插入失败
return false;
}
}
//比较当前元素和父节元素的大小
if (o.compareTo(parent.element) < 0) {
//小于父节点的元素，则新建元素节点作为父节点的左节点
parent.left = new TreeNode<>(o);
} else {
//大于父节点的元素，则新建元素节点作为父节点的右节点
parent.right = new TreeNode<>(o);
}
}
//当前树种存储的元素+1
size++;
return true;
}
4.查找一个元素
当我们需要在BST中查找一个节点时，我们从根节点从下扫描，直到我们找到匹配的元素或者达到一个空子树(树中不存在当前要查找的元素)，下面我们来看下它的Java实现：
//返回true表示查询成功，false表示没右查询到
public boolean search(E o) {
//记录遍历时的当前节点
TreeNode<E> current = root;
while (current != null) {
//小于当前节点元素遍历其左子树
if (o.compareTo(current.element) < 0) {
current = current.left;
/大于当前节点元素遍历其右子树
} else if (o.compareTo(current.element) > 0) {
current = current.right;
} else {
//查到
return true;
}
}
return false;
}
5.删除一个元素
当我们要在BST中删除一个元素，首先我们需要定位该元素的位置。然后在删除它时，比插入的时候要复杂一点，因为我们需要考虑两种情况：
1.当前元素节点没有左子节点。
2.当前元素节点右左子节点。
下面我们直接从代码角度来看看如何来删除一个节点：
//删除成功返回true,否则返回false
public boolean delete(E o) {
//指向当前节点的父节点
TreeNode<E> parent = null;
//指向当前节点
TreeNode<E> current = root;
//遍历二叉树
while (current != null) {
if (o.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (o.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
//找到跳出循环 current就是要删除的节点
break;
}
}
//如果为null返回false
if (current == null) {
return false;
}
//如果要删除的节点没有左节点
if (current.left == null) {
//如果当前要删除节点是根节点，当前节点的右子节点作为根节点。
if (parent == null) {
root = current.right;
} else {
//比较当前要删除的元素和父节点元素的大小
//如果当前要删除的元素是父节点的左子节点
//当前节点的右子节点作为父节点的左子节点
if (o.compareTo(parent.element) < 0) {
parent.left = current.right;
} else {
//如果当前要删除的元素是父节点的右子节点
//当前节点的右子节点作为父节点的右子节点
parent.right = current.right;
}
}
} else {
//如果存在要删除的节点存在左子节点,找到current的左子树的最大元素节点
//parentOfRightMost 指向 最大元素节点的父节点
//最大元素节点不会存在右节点只会存在左节点(如果存在，就不是最大了)
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
//最大元素节点替换要删除的节点
current.element = rightMost.element;
//如果最大元素节点是其父节点的右节点，左子节点作为父元素的右子节点
if (parentOfRightMost.right == rightMost) {
parentOfRightMost.right = rightMost.left;
} else {
//如果最大元素节点是其父节点的左节点 左子节点作为父元素的左子节点
parentOfRightMost.left = rightMost.left;
}
}
size--;
return true;
}
6.二叉搜索树的遍历
所谓树的遍历，就是访问树中的每个节点一次。遍历树的方式主要有以下几种：
1.中序遍历，先递归访问左子树，然后访问当前节点，在递归访问右子树。
2.前序遍历，先访问当前节点，在递归访问左子树，在递归访问右子树。
3.后序遍历，先递归访问左子树，在递归访问右子树，然后访问当前节点。
4.深度优先遍历 和前序遍历法相同。
5.广度优先遍历 逐层访问树中的节点。
中前后，代表访问当前节点的顺序。
拿我们这张图上的BST举例，我们来写下它的五种遍历方式的结果：
中序：1，2，3，4，5，6，7，8，9，10
前序：7，4，2，1，3，6，5，9，8，10
后序：1，3，2，5，6，4，8，10，9，7
广度优先：7，4，9，2，6，8，10，1，3，5
深度优先：7，4，2，1，3，6，5，9，8，10
我们来用中序遍历，讲解一下我们的遍历规则：
首先我们递归遍历左子树，我们遍历以2为节点的树，我们先访问它的左子节点1，然后我们访问当前节点2，继而让问右子节点3，然后我们访问2的父节点4，在遍历4的右子树，同上我们遍历以6为节点的树，先访问它的左子节点5，在访问当前节点6，然后我们访问节点4的父节点。在去遍历7的右子树，同上先遍历以9为节点的树，先访问它的左子节点8，在访问它本身，在访问它的右节点10。
最后得出结果1，2，3，4，5，6，7，8，9，10。