概念
二叉搜索树是二叉数的一种特例，二叉树又是树的其中一种，树又是图的一种特例。二叉搜索树作为特例中的特例，结构最为简单，编码也最容易理解，作为学习树和图的起点最为合适。
首先树是由节点和边组成的，节点一般用来储存数据，边用来表示节点之间的联系，Java中常常用引用来表示边。
树有一些概念，如：根、父节点、子节点、叶结点、子树、路径等，这些概念通过画图来理解比较容易。
二叉搜索树.png
此图中的父节点、子节点以及子树的概念都是相对于标记节点40的
二叉树是指树中每个节点最多只能有两个子节点，如上图所示
而二叉搜索树是指：一个节点的左子节点的关键值小于这个节点的关键值，右子节点的关键值大于或等于这个节点的关键值的二叉树，如上图所示。
二叉搜索树的方法与实现
搞清楚二叉搜索树的概念之后，我们来考虑它的方法和实现。
一颗二叉搜索树的组成包括：节点和引用
首先来实现节点，节点应该封装了需要储存的数据，数据类型可以是数字，字符串等，也可以是一个对象的引用，方便起见，我们这里就存储一个整型数字iData。
一个节点还需要持有其子节点的引用，在二叉搜索树中就分为：左子节点（leftChild）和右子节点（rightChild），叶子节点的子节点引用指向null。
以下代码实现了一个简单的节点类Node
public class Node {
private int data;
public Node leftChild;
public Node rightChild;
//constructor
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void displayNode() {
System.out.print("{" + data + "}");
}
}
一颗二叉搜索树的方法应该有：查找、插入、遍历、删除
二叉搜索树的基点是根节点，从根节点来展开以上方法，所以一个二叉搜索树的对象需要持有根节点的引用root，在还没有节点插入之前，root的初始值为null，如下代码所示：
public class BinaryTree {
//reference to root
private Node root;
//constructor
public BinaryTree() {
root = null;
}
}
由于二叉搜索树的特性（即当前节点的值大于其左子节点的值，小于其右子节点的值），使得其在查找、插入和遍历的实现上较为容易，而删除则比较麻烦，因为删除一个节点之后需要重新构建二叉搜索树使其满足特性，我们逐个来分析。
查找
传入一个整型类型的值，从根节点开始比较，根据比较结果去搜索其左子树或是右子树，逻辑较为简单，实现代码：
public Node find(int key) {
Node current = root;
while(current.getData() != key) {
if (key < current.getData()) {
current = current.leftChild;
} else {
current = current.rightChild;
}
if (current == null) {
return null;
}
}
return current;
}
需要注意的是退出循环的条件，当current指向null的时候表明已比较过叶子节点，即没有找到key。
插入
插入和查找的逻辑几乎一样，需要注意的是插入的节点如何算作树的一部分：是其父节点的子节点引用指向该插入的节点，所以除current外，还需要一个parent引用
下面来看insert的实现：
public void insert(int key) {
Node newNode = new Node(key);
if (root == null) {
root = newNode;
} else {
Node current = root;
Node parent;
while(true) {
parent = current;
if (key < current.getData()) {
current = current.leftChild;
if (current == null) {
parent.leftChild = newNode;
return;
}
} else {
current = current.rightChild;
if (current == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
在做插入判断的时候，需要对左右两个子节点的分支做独立判断，为简化代码，可以设置一个标志变量isLeftChild(boolean)来合并两个分支的插入判断，在删除方法中，逻辑较为复杂，我们就可以使用这种方法。
遍历
遍历树有三种简单的方法：前序遍历(preOrder)、中序遍历(inOrder)和后序遍历(postOrder)
二叉搜索树因其结构特性，可以使用递归的方法来实现遍历，一般来说二叉搜索树的中序遍历比较有现实意义，因为可以得到有序的数据序列。
中序遍历的实现方法为：
1.对当前节点递归的调用自身来遍历其左节点
2.访问这个节点
3.调用自身来遍历其右节点
以下是实现代码：
private void inOrder(Node localRoot) {
while(localRoot != null) {
inOrder(localRoot.leftChild);
System.out.print(localRoot.getData() + " ");
inOrder(localRoot.rightChild);
}
}
前序遍历和后序遍历相比于中序遍历，其实现上的差异就在于调用的顺序不同：前序遍历是先访问当前节点再遍历左节点最后遍历右节点，后序遍历则是先遍历左节点再遍历右节点最后访问当前节点，以下是其实现代码：
private void preOrder(Node localRoot) {
if (localRoot != null) {
System.out.print(localRoot.getData() + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
private void postOrder(Node localRoot) {
if (localRoot != null) {
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.getData() + " ");
}
}
删除
删除方法是二叉搜索树中最难实现的方法，其逻辑复杂在于：删除一个节点之后，为了填补空洞，需要重新构建一个二叉搜索树，且删除节点又分几种情况：删除节点无子节点、删除节点只有一个子节点、删除节点有两个子节点等，接下来结合代码逐一分析
首先删除方法中同样需要持有两个引用current和parent，一个指向当前节点，一个指向当前节点的父节点，为了减少代码量，设置了一个布尔值isLeftChild，来标注current的是否为parent的左子节点。
Node current = root;
Node parent = root;
boolean isLeftChild = true;
接下来根据传入的key，找到需要删除的节点，这一步的实现代码类似于查找的代码：
while(key != current.getData()) {
parent = current;
if (key < current.getData()) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
此时的current已经指向要删除的节点了，那么就要把待删除的节点分几种情况来讨论：
1.无子节点
2.有一个子节点
3.有两个子节点
当无子节点时，即待删除的节点为叶子节点，那么可以直接删除，对树的结构没有什么影响
if (current.leftChild == null && current.rightChild == null) {
if (current == root) { //需要考虑的特例
root = null;
} else {
if (isLeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
}
}
当仅有一个子节点时，需要进行左右子节点的分别判断处理
else if (current.leftChild == null) {
if (current == root) {
root = root.rightChild;
} else {
if (isLeftChild) {
parent.leftChild = current.rightChild;
} else {
parent.rightChild = current.rightChild;
}
}
}
else if (current.rightChild == null) {
if (current == root) {
root = root.leftChild;
} else {
if (isLeftChild) {
parent.leftChild = current.leftChild;
} else {
parent.rightChild = current.leftChild;
}
}
}
代码中比较不容易理解的地方就是四个比较长的赋值语句，其实就是删除的过程本身：将父节点的子节点引用指向待删除节点的子节点，自己动手画图会比较容易理解。
下面讨论最复杂的情况，待删除的节点有两个子节点，且可能有子树。
这种情况，待删除的节点处于树比较中间的位置，故需要找到一个替代节点来填补这个空洞，重构二叉搜索树的结构，这个替代节点也叫删除节点的后继，下面画图说明如何寻找后继节点
寻找后继结点.png
看以看出寻找后继节点的窍门在于：后继节点为删除节点右子树的最左子节点
转化为算法描述即为：程序首先找到删除节点的右子节点，如果其存在左子树则寻找其左子节点的左子节点的左子节点......直到找到最后一个左子节点（它可以有右子节点，但不可以有左子节点，否则它就不是最后一个左子节点），如果这个右子节点不存在左子节点，那么后继节点就是这个右子节点。
这个描述比较拗口，结合下图理解会比较容易
寻找后继节点过程示意图.png
下面给出寻找后继节点的代码：
private Node getReplace(Node delNode) {
Node replace = delNode;
Node replaceParent = delNode;
Node current = delNode.rightChild;
while(current != null) { //三个指针都向最左子节点移动
replaceParent = replace;
replace = current;
current = current.leftChild;
}
//找到后继节点后，可能是删除节点的右子节点，则右子节点为根的子树直接上移替代删除节点即可
//如果后继节点为最左子节点，则需要处理后继节点的右子树，并用后继节点替代删除节点
if (replace != delNode.rightChild) {
replaceParent.leftChild = replace.rightChild;
replace.rightChild = delNode.rightChild;
}
return replace;
}
找到后继节点后，继续刚才的逻辑，接下来需要将删除节点的父节点引用指向后继节点，且把删除节点的左子树给后继节点拼接上，代码如下：
else {
Node replace = getReplace(current);
if (current == root) { //需要考虑的特殊情况
root = replace;
} else { //切换parent引用
if (isLeftChild) {
parent.leftChild = replace;
} else {
parent.rightChild = replace;
}
}
//拼接左子树
replace.leftChild = current.leftChild;
}
至此，删除方法的所有情况均已考虑在内，还是挺难理解的，最好可以自己画图分析一下，以下给出完整的删除方法的完整代码
public boolean delete(int key) {
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(key != current.getData()) {
parent = current;
if (key < current.getData()) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
if (current.leftChild == null && current.rightChild == null) {
if (current == root) { //需要考虑的特例
root = null;
} else {
if (isLeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
}
}
else if (current.leftChild == null) {
if (current == root) {
root = root.rightChild;
} else {
if (isLeftChild) {
parent.leftChild = current.rightChild;
} else {
parent.rightChild = current.rightChild;
}
}
}
else if (current.rightChild == null) {
if (current == root) {
root = root.leftChild;
} else {
if (isLeftChild) {
parent.leftChild = current.leftChild;
} else {
parent.rightChild = current.leftChild;
}
}
}
else {
Node replace = getReplace(current);
if (current == root) { //需要考虑的特殊情况
root = replace;
} else { //切换parent引用
if (isLeftChild) {
parent.leftChild = replace;
} else {
parent.rightChild = replace;
}
}
//拼接左子树
replace.leftChild = current.leftChild;
}
return true;
}
private Node getReplace(Node delNode) {
Node replace = delNode;
Node replaceParent = delNode;
Node current = delNode.rightChild;
while(current != null) { //三个指针都向最左子节点移动
replaceParent = replace;
replace = current;
current = current.leftChild;
}
//找到后继节点后，可能是删除节点的右子节点，则右子节点为根的子树直接上移替代删除节点即可
//如果后继节点为最左子节点，则需要处理后继节点的右子树，并用后继节点替代删除节点
if (replace != delNode.rightChild) {
replaceParent.leftChild = replace.rightChild;
replace.rightChild = delNode.rightChild;
}
return replace;
}
二叉搜索树的效率
二叉搜索树的时间复杂度与其树高有关，在查找、插入和删除代码中可以观察到，比较的次数和树的层数正相关，假设树的层数为L，节点数位N，对于一颗满二叉搜索树，存在关系：2^(L -1) = N，那么L=log2N+1(2为底数),
所以一般来说时间复杂度为O(logN)，不满的树的平均查找时间比满树要短，因其在层数较低的比较次数少于满树。
考虑特殊情况，如果一颗二叉搜索树极不平衡，例如插入的是一串升序序列，那么新插入的节点都是上个节点的右子节点，将会导致二叉搜索树变成一个链表，时间复杂度退化为O(N)，所以对于一颗二叉树结构来说，平衡是一个重要的特性，红黑树的诞生就是为了解决树的不平衡而导致的效率下降问题。
参考文章
《Data Structures & Algorithms in Java》 Robert Lafore著
网友评论