数据结构（一）数组实现一个简单的ArrayList
数据结构（二）链表实现LinkedList
数据结构（三）用两种方式简单实现栈
数据结构（四）栈和队列的简单应用
数据结构（五）用两种方式简单实现队列
数据结构（六）二分搜索树(Binary Search Tree)（上）
数据结构（六）二分搜索树(Binary Search Tree)（下）
数据结构（七）两种方式实现set
数据结构（八）两种方式实现map
数据结构（九）set解决LeetCode349号问题
今天这篇文章是接上次的文章，二分搜索树还有几个方法没有分析完。简单回顾一下，昨天我们分析了添加操作，是否包含操作，最小值，最大值，以及删除最大值最小值操作。今天我们分析一下删除操作，以及他的几个遍历方法：前序遍历，中序遍历以及后续遍历。
- preOrder
// 二分搜索树的前序遍历
public void preOrder(){
preOrder(root);
}
// 前序遍历以node为根的二分搜索树, 递归算法
private void preOrder(Node node){
if(node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
这里我们同样用递归实现前序遍历。先找到结束的条件就是当前节点为空就结束了。前序遍历就是先打印当前节点，然后再打印左子树然后是右子树。这样前序遍历就完成。
大家可以看一下上边这个图。这里就是前序遍历的顺序图。下边这个图是她的打印结果。
- inOrder 好了看完了前序遍历我们来看一下中序遍历其实和前序遍历一样
// 二分搜索树的中序遍历
public void inOrder(){
inOrder(root);
}
// 中序遍历以node为根的二分搜索树, 递归算法
private void inOrder(Node node){
if(node == null)
return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
这里唯一一点不同的是 先打印左子树，然后是根节点，然后是右子树。下边是她的打印结果。
大家有没有发现一个好玩的地方，对没错他是按从小到大的顺序排序好的。所以二分搜索树的一个特性就是中序遍历是从小到大的排序好的。
- postOrder
后续遍历跟之前的前序、中序遍历一样我想大家都可以自己写出代码,这里我们就不过多的解释。
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
- remove
//删除以node为根的二分搜索树中元素为e的节点，递归算法
//返回删除节点后二分搜索树的根
private Node remove(Node node, E e) {
if (node == null)
return null;
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {// e == node.e
if (node.left == null) {
Node right = node.right;
node.right = null;
size--;
return right;
}
if (node.right == null) {
Node left = node.left;
node.left = null;
size--;
return left;
}
Node successor = mininum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
删除方法这个比较复杂了，这里也是递归的方式实现。写一个以node为根的节点的方法。如果这个节点为空就返回空，如果传入的元素比当前节点的的元素小，那么就去他的左子树去找；如果传入的元素比当前节点的元素大那么就去他的右子树去找。如果传入的元素等于当前节点那么又有三种情况：如果左子树是空的，那么直接删除这个节点，然后把他的右子树返回就可以了；如果这个节点的右子树为空那么就删除这个节点，然后把它的左子树返回就可以了；如果删除的这个节点左右子树都不为空，那么就吧右子树的最小值放到这个节点上就可以了，当然也可以把左子树的最大值放到这个节点上，这样还满足这是一棵二分搜索树。具体的替换绿色的小球表示要替换旁边红色的小球，红色小球是要被替换的小球。
到这里二分搜索书的基本方法都介绍完了。希望大家可以明白，有什么不明白的可以评论里说。
