之前面试经常被问到 MySQL 的索引相关问题，以及 HashMap 内部实现等，这些问题都跟树这种数据结构有关。比如：
- MySQL 索引使用的是 B+ 树；
- HashMap 底层实现是链式哈希表，当其中链表达到一定长度时则转换为红黑树；
这些树虽然经常听说，却不懂其中具体详情，更别提手写实现了。这会正值春季，阳光和煦，万物复苏，树木也开始抽新枝了，就好好来学习下这些令人又爱又恨的树吧！
数据结构的世界里都有哪些树？
- 普通树，Tree，没啥好说的！
- 二叉树，Binary Tree，长相匀称俊美，本身没啥牛逼之处，牛逼的是下面的它的变种；
- 最优二叉树，听这名字可能并不知道它是个什么鬼？我也不知道它的英文名字叫什么？它的定义：带权路径长度 WPL 最小的二叉树。看定义还是一脸懵逼，其实它还有个更加广为人知的名字：赫夫曼树（Huffman Tree），即跟赫夫曼编码相关。这里之所以提到它是为了不与后面那些杂七杂八的树的名字搞混了。
- 二叉排序树，Binary Sort Tree，世人又称之为二叉查找树。
二叉排序树
import java.util.ArrayList;
import java.util.List;
/**
* Created by clearbug on 2018/3/11.
*
* 二叉排序树
*/
public class BinarySortTree {
/**
* 节点
*/
static class TreeNode {
public int val;
public TreeNode leftChild;
public TreeNode rightChild;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 节点包装器
*/
static class TreeNodeWrapper {
public TreeNode node;
}
/**
* 二叉排序树-根节点
*/
public TreeNode root;
public BinarySortTree(TreeNode root) {
this.root = root;
}
/**
* 搜索某个给定值节点
*
* @param key 给定值
* @param wrapper 给定值节点包装器
* @return 若二叉排序树中存在给定值节点，则返回 true，相应的 wrapper.node 的值是该节点；否则返回 false，wrapper.node 的值为待插入节点的父节点
*/
public boolean search(int key, TreeNodeWrapper wrapper) {
return searchHelper(root, null, key, wrapper);
}
/**
* 插入
*
* @param key 给定值
* @return 若给定值已存在，则返回 false；否则，插入给定值节点并返回 true；
*/
public boolean insert(int key) {
TreeNodeWrapper wrapper = new TreeNodeWrapper();
if (!search(key, wrapper)) {
if (wrapper.node == null) {
throw new IllegalArgumentException("wrapper == null");
}
TreeNode node = new TreeNode(key);
if (key < wrapper.node.val) {
wrapper.node.leftChild = node;
} else {
wrapper.node.rightChild = node;
}
return true;
}
return false;
}
/**
* 删除
*
* @param key 给定值
* @return 若给定值存在，则删除之并返回 true；否则，返回 false；
*/
public boolean delete(int key) {
return deleteHelper(root, null, key);
}
/**
* 中序遍历，将节点值依序放入结果中
*
* @return 依序的节点值
*/
public List<Integer> inOrderTraverse() {
List<Integer> res = new ArrayList<>();
inOrderTraverseHelper(root, res);
return res;
}
private void inOrderTraverseHelper(TreeNode node, List<Integer> res) {
if (node.leftChild != null) {
inOrderTraverseHelper(node.leftChild, res);
}
res.add(node.val);
if (node.rightChild != null) {
inOrderTraverseHelper(node.rightChild, res);
}
}
private boolean deleteHelper(TreeNode node, TreeNode parentNode, int key) {
if (node == null) {
return false;
}
if (node.val == key) {
if (node.leftChild == null) {
if (parentNode == null) {
root = node.rightChild;
} else if (node == parentNode.leftChild) {
parentNode.leftChild = node.rightChild;
} else {
parentNode.rightChild = node.rightChild;
}
} else if (node.rightChild == null) {
if (parentNode == null) {
root = node.leftChild;
} else if (node == parentNode.leftChild) {
parentNode.leftChild = node.leftChild;
} else {
parentNode.rightChild = node.leftChild;
}
} else {
TreeNode q = node, s = node.leftChild;
while (s.rightChild != null) {
q = s;
s = s.rightChild;
}
node.val = s.val;
if (q != node) {
q.rightChild = s.leftChild;
} else {
q.leftChild = s.leftChild;
}
}
} else if (key < node.val) {
deleteHelper(node.leftChild, node, key);
} else {
deleteHelper(node.rightChild, node, key);
}
return false;
}
private boolean searchHelper(TreeNode node, TreeNode parentNode, int key, TreeNodeWrapper wrapper) {
if (node == null) {
wrapper.node = parentNode;
return false;
}
if (key == node.val) {
wrapper.node = node;
return true;
}
if (key < node.val) {
return searchHelper(node.leftChild, node, key, wrapper);
} else {
return searchHelper(node.rightChild, node, key, wrapper);
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(45);
BinarySortTree bsTree = new BinarySortTree(root);
bsTree.insert(24);
bsTree.insert(53);
bsTree.insert(12);
bsTree.insert(12);
bsTree.insert(37);
bsTree.insert(93);
bsTree.insert(38);
bsTree.insert(36);
bsTree.insert(35);
bsTree.insert(34);
bsTree.insert(33);
bsTree.insert(32);
bsTree.insert(31);
bsTree.insert(39);
bsTree.insert(40);
bsTree.insert(41);
bsTree.insert(42);
bsTree.insert(43);
bsTree.insert(44);
System.out.println(bsTree.inOrderTraverse());
bsTree.delete(12);
System.out.println(bsTree.inOrderTraverse());
bsTree.delete(37);
System.out.println(bsTree.inOrderTraverse());
bsTree.delete(53);
System.out.println(bsTree.inOrderTraverse());
bsTree.delete(45);
System.out.println(bsTree.inOrderTraverse());
bsTree.delete(24);
System.out.println(bsTree.inOrderTraverse());
bsTree.delete(93);
System.out.println(bsTree.inOrderTraverse());
bsTree.delete(37);
System.out.println(bsTree.inOrderTraverse());
}
}