1、前言
二叉树是非常重要的一种数据结构，二叉搜索树是其中的一种类型，其任意节点x，左子树中的关键字最大不超过x.key，右子树的关键字最小不低于x.key
一棵随机构造的二叉搜索树的期望高度为lgN，而二叉搜索树上基本操作所花费的时间均与树的高度成正比。
2、构建二叉搜索树
根据二叉搜索树的特性，对于任意节点x，均有
x.left.key <= x.key <= x.right.key
向二叉搜索树插入新节点时，分成两种情况
二叉搜索树为空，则新插入节点为根节点
-
根据新插入节点的关键字值，从根节点开始查找，小则向左，大则向右，最后确定新节点的位置
//插入算法相对较简单，就是根据值找位置，如果小，找左子树，如果大了，往右子树，直到某个节点为空 //但这种插入算法，有个问题，插入数值的顺序不同，得到的二叉搜索树就会不同。 public void insert(SearchTree tree, int v){ SearchNode node= new SearchNode(v); SearchNode x = tree.mRoot; SearchNode y = null; while (x != null) { y = x; if (v <= x.value) { x = x.left; }else { x = x.right; } } if (y == null) { mRoot = node; node.parent = null; return; } if (v <= y.value) { y.left = node; node.parent = y; }else { y.right = node; node.parent = y; } }
3、查找二叉搜索树
二叉搜索树查找特定值非常简单，与插入类似，根据关键字值大小比较可得出
public SearchNode search2(SearchNode node, int v){
SearchNode temp = node;
while (temp != null && temp.value != v) {
if (v < temp.value) {
temp = temp.left;
}else {
temp = temp.right;
}
}
return temp;
}
那寻找以节点x为根结点的树的最小值或最大值呢？根据二叉搜索树的特性，最小值肯定是x的左子树的左叶子节点，最大值是x的右子树的右叶子节点
public SearchNode treeMin(SearchNode node){
SearchNode x = node;
while (x != null && x.left != null) {
x = x.left;
}
return x;
}
public SearchNode treeMax(SearchNode node){
SearchNode x = node;
while (x != null && x.right != null) {
x = x.right;
}
return x;
}
如何寻找节点x的后继或前驱呢？
后继，遍历树时，位于节点x后的节点即为x的后继，反之则为前驱。根据不同的遍历方法，前序中序等等，会不同的后继，本文中仅讨论中序后继或中序前驱
如果使用中序遍历二叉搜索树，会发现一个奇特的现象，遍历得到的值一定是从小到大排列的，那么后继值，则刚好是大于x的最小节点。如此可分为两种情况
有右子树，那么查找x节点右子树上的最小值即可。
-
无右子树，示例图中9的后继是12，17的后继是18，节点x（5、17）的父节点均是目标节点的左节点
public SearchNode followUp(SearchNode x){ if (x.right != null) { return treeMin(x.right); } SearchNode y = x.parent; //当父节点是左子节点时，查找完成 while (y != null && y.right == x) { x = y; y = y.parent; } return y; }
前驱类似，不再详述
4、删除节点
删除节点是二叉搜索树中最复杂的。命名删除的节点为z，它需要分成三种情况讨论
z无左节点，把z的右节点顶替z的位置即可，如果z是15，那么把17顶替到15的位置上
z无右节点，把z的左节点顶替z的位置即可，如果z是17，则把16顶替17即可
z有左右节点，如果z是12，根据二叉搜索树的性质，则需要将15顶替12的位置，17顶替15的位置。根据二叉搜索树的性质，遍历后一定是按从小到大的顺序的，而15是12的后继，所以需要以15顶替12的位置。
二叉搜索树删除节点，左右节点存在的情况下，其通用作法就是使用后继替代它
public void delete(SearchNode z){
SearchNode y = null;
if (z == null) {
return;
}
if (z.left == null) {
swap(z, z.right);
}else if (z.right == null) {
swap(z, z.left);
}else {
//寻找Z的后继节点，此处改为 treeMin(z.right)
//为啥寻找z的后续节点就可以替换z的位置，二叉搜索树如果是中序遍历，那么一定是按从小到大排列的，
//如果删除某个数之后，这个特性段然存在，从这个角度来看，就得找它的后续节点来替代z
y = followUp(z);
if (y.parent != z) {
//本例中，将y的父节点和y的关系切断
swap(y, y.right);
//设置y的右节点为z的右节点
y.right = z.right;
//设置y右节点的父节点
y.right.parent = y;
}
swap(z, y);
//设置y左节点及其父节点
y.left = z.left;
y.left.parent = y;
}
}
5、线索化二叉树
前文提到前驱与后继，其实二叉树作为非线性结构，原来是不存在所谓前驱与后继概念的，但二叉树遍历后，彼此结点确实存在前后关系，加上二叉树是可以使用数组保存，所以才有前驱与后继一说。
二叉树的节点一般会有值、左子节点、右子节点等指针域。n个结点有2n个指针，其中非空指针为n-1个，空白指针有n+1个。
为了不浪费指针空间，将二叉树空白指针中存在着节点的前驱与后继信息，如果无左节点则左节点指针域存放前驱。无右节点，则右节点指针域存放后继，为了标志存放的是子节点还是前驱后继，还会添加两个额外标志位。
private TAG mLeftTag = TAG.LINK;
private TAG mRightTag = TAG.LINK;
线索化二叉树，在遍历二叉树的时候判断二叉树是否存在左节点，如果不存在，则将pre设置为它的前驱，然后再查看pre是否有右节点，如果没有，则将当前节点设置为pre的后继。
算法的精髓就在于设置一个全局变量pre。
ClueNode pre;
private void makeClueTree(ClueNode node){
if (node == null) {
return;
}
makeClueTree((ClueNode)node.getLeftChild());
if (!node.hasLeftChild()) {
node.setLeftTag(TAG.THREAD);
node.setLeftChild(pre);
}
if (pre != null && !pre.hasRightChild()) {
pre.setRightTag(TAG.THREAD);
pre.setRightChild(node);
}
pre = node;
makeClueTree((ClueNode)node.getRightChild());
}
已知一个线索化二叉树，那么在遍历此二叉树时，不再需要递归，也不需要借助栈，就能直接遍历了。
private void printClueTree(ClueNode node){
ClueNode p = node;
while (p != null) {
while(p.getLeftTag() == TAG.LINK && p.hasLeftChild()) {
p = (ClueNode) p.getLeftChild();
}
printNode(p);
while(p.getRightTag() == TAG.THREAD && p.hasRightChild()) {
p = (ClueNode) p.getRightChild();
printNode(p);
}
p = (ClueNode) p.getRightChild();
}
}
ps：所有代码均已上传至本人github
