二叉搜索树

1、前言

二叉树是非常重要的一种数据结构，二叉搜索树是其中的一种类型，其任意节点x，左子树中的关键字最大不超过x.key，右子树的关键字最小不低于x.key

Paste_Image.png

一棵随机构造的二叉搜索树的期望高度为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