经典算法之二叉搜索树
二叉树（Binary Tree）
二叉树（Binary Tree）是一种特殊的树类型，其每个节点最多只能有两个子节点。这两个子节点分别称为当前节点的左孩子（left child）和右孩子（right child）。
上图中，二叉树（a）包含 8 个节点，其中节点 1 是它的根节点。节点 1 的左孩子为节点 2，右孩子为节点 3。注意，并没有要求一个节点同时具有左孩子和右孩子。例如，二叉树（a）中，节点 4 就只有一个右孩子 6。此外，节点也可以没有孩子节点。例如，二叉树（b）中，节点 4、5、6、7 都没有孩子节点。
没有孩子的节点称为叶节点（Leaf Node），有孩子的节点则称为内节点（Internal Node）。如上图中，二叉树 （a） 中节点 6、8 为叶节点，节点 1、2、3、4、5、7 为内节点。
完全二叉树和满二叉树
完全二叉树（Complete Binary Tree）：深度为 h，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 h 的满二叉树中，序号为 1 至 n 的节点对应时，称之为完全二叉树。
满二叉树（Full Binary Tree）：一棵深度为 h，且有 2h - 1 个节点称之为满二叉树。
完全二叉树 | 满二叉树 | |
|---|---|---|
总节点数 k | 2h-1 <= k < 2h - 1 | k = 2h - 1 |
树高 h | h = log2k + 1 | h = log2(k + 1) |
二叉搜索树
二叉搜索树，是指一棵空树或者具有下列性质的二叉树：
1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2.若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左，右子树也分别为二叉搜索树；没有键值相等的节点。
如下图：
Java来表示二叉树
public class BinarySearchTree
{ // 二叉搜索树类
private class Node
{ // 节点类
int data; // 数据域
Node right; // 右子树
Node left; // 左子树
}
private Node root; // 树根节点
}首先，需要一个节点对象的类。这个对象包含数据域和指向节点的两个子节点的引用。其次，需要一个树对象的类。这个对象包含一个根节点root。
创建树（insert）
创建树的时候，主要用到了parent，current来记录要插入节点的位置。哪么怎么检验自己是否正确地创建了一颗二叉搜索树呢，我们通过遍历来输出各个节点的值
public void insert(int key)
{
Node p=new Node(); //待插入的节点
p.data=key;
if(root==null)
{
root=p;
}
else
{
Node parent=new Node();
Node current=root;
while(true)
{
parent=current;
if(key>current.data)
{
current=current.right; // 右子树
if(current==null)
{
parent.right=p;
return;
}
}
else //本程序没有做key出现相等情况的处理，暂且假设用户插入的节点值都不同
{
current=current.left; // 左子树
if(current==null)
{
parent.left=p;
return;
}
}
}
}
}遍历树（travel）
遍历指的是按照某种特定的次序来访问二叉搜索树中的每个节点，主要有三种遍历的方法：
前序遍历，“中左右” 中序遍历，“左中右” 后序遍历，“左右中” 上面的口诀“中左右”表示的含义是，先访问根节点，再访问左子，最后访问右子。
举个例子：
前序遍历：39 24 23 30 64 53 60 中序遍历：23 24 30 39 53 60 64 后序遍历：23 30 24 60 53 64 39
你会发现，按照中序遍历的规则将一个二叉搜索树输入，结果为按照正序排列。
public void preOrder(Node root)
{ // 前序遍历,"中左右"
if (root != null)
{
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
}
public void inOrder(Node root)
{ // 中序遍历,"左中右"
if (root != null)
{
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
}
public void postOrder(Node root)
{ // 后序遍历,"左右中"
if (root != null)
{
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + " ");
}
}
public void traverse(int traverseType)
{ // 选择以何种方式遍历
switch (traverseType)
{
case 1:
System.out.print("preOrder traversal ");
preOrder(root);
System.out.println();
break;
case 2:
System.out.print("inOrder traversal ");
inOrder(root);
System.out.println();
break;
case 3:
System.out.print("postOrder traversal ");
postOrder(root);
System.out.println();
break;
}
}以上的代码采用递归的方式实现三种遍历，为了方便我们使用，又写了一个traverse函数来实现选择哪种方式进行树的遍历。
这会儿就可以写单元测试了，我们首先创建一个二叉搜索树，然后分别使用“前序”，“中序”，“后序”来遍历输出树的所有节点。
public static void main(String[] args) //unit test
{
BinarySearchTree tree=new BinarySearchTree();
tree.insert(39);
tree.insert(24);
tree.insert(64);
tree.insert(23);
tree.insert(30);
tree.insert(53);
tree.insert(60);
tree.traverse(1);
tree.traverse(2);
tree.traverse(3);
}运行该单元测试，可以看到如下的结果：
查找节点（find）
查找节点比较简单，如果找到节点则返回该节点，否则返回null。为了方便在控制台输出，我们有添加了一个show函数，用来输出节点的数据域。
public Node find(int key)
{ // 从树中按照关键值查找元素
Node current = root;
while (current.data != key)
{
if (key > current.data)
current = current.right;
else
current = current.left;
if (current == null) return null;
}
return current;
}
public void show(Node node)
{ //输出节点的数据域
if(node!=null)
System.out.println(node.data);
else
System.out.println("null");
}删除节点（delete）
删除节点是二叉搜索树中，最复杂的一种操作，但是也不是特别难，我们分类讨论： 1、要删除节点有零个孩子，即叶子节点
如图所示，只需要将parent.left(或者是parent.right)设置为null，然后Java垃圾自动回收机制会自动删除current节点。
2.要删除节点有一个孩子
如图所示，只需要将parent.left(或者是parent.right)设置为curren.right(或者是current.left)即可。
3、要删除节点有两个孩子
这种情况比较复杂，首先我们引入后继节点的概念，如果将一棵二叉树按照中序周游的方式输出，则任一节点的下一个节点就是该节点的后继节点。例如：上图中24的后继节点为25，64的后继节点为70.找到后继节点以后，问题就变得简单了，分为两种情况：
3.1.后继节点为待删除节点的右子，只需要将curren用successor替换即可，注意处理好current.left和successor.right.
注意：这种情况下，successor一定没有左孩子，一但它有左孩子，哪它必然不是current的后继节点。
3.2.后继节点为待删除结点的右孩子的左子树，这种情况稍微复杂点，请看动态图片演示。
算法的步骤是：
successorParent.left=successor.right successor.left=current.left parent.left=seccessor 弄懂原理后，我们来看具体的代码实现：
private Node getSuccessor(Node delNode) //寻找要删除节点的中序后继结点
{
Node successorParent=delNode;
Node successor=delNode;
Node current=delNode.right;
//用来寻找后继结点
while(current!=null)
{
successorParent=successor;
successor=current;
current=current.left;
}
//如果后继结点为要删除结点的右子树的左子，需要预先调整一下要删除结点的右子树
if(successor!=delNode.right)
{
successorParent.left=successor.right;
successor.right=delNode.right;
}
return successor;
}
public boolean delete(int key) // 删除结点
{
Node current = root;
Node parent = new Node();
boolean isRightChild = true;
while (current.data != key)
{
parent = current;
if (key > current.data)
{
current = current.right;
isRightChild = true;
}
else
{
current = current.left;
isRightChild = false;
}
if (current == null) return false; // 没有找到要删除的结点
}
// 此时current就是要删除的结点,parent为其父结点
// 要删除结点为叶子结点
if (current.right == null && current.left == null)
{
if (current == root)
{
root = null; // 整棵树清空
}
else
{
if (isRightChild)
parent.right = null;
else
parent.left = null;
}
return true;
}
//要删除结点有一个子结点
else if(current.left==null)
{
if(current==root)
root=current.right;
else if(isRightChild)
parent.right=current.right;
else
parent.left=current.right;
return true;
}
else if(current.right==null)
{
if(current==root)
root=current.left;
else if(isRightChild)
parent.right=current.left;
else
parent.left=current.left;
return true;
}
//要删除结点有两个子结点
else
{
Node successor=getSuccessor(current); //找到要删除结点的后继结点
if(current==root)
root=successor;
else if(isRightChild)
parent.right=successor;
else
parent.left=successor;
successor.left=current.left;
return true;
}
}总结
BST 算法查找时间依赖于树的拓扑结构。最佳情况是 O(log2n)，而最坏情况是 O(n)。
参考文档： https://www.cnblogs.com/yahuian/p/10813614.html#2034425196
https://www.cnblogs.com/gaochundong/p/binary_search_tree.html
https://www.cnblogs.com/vamei/archive/2013/03/17/2962290.html