二叉查找树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

在对二叉查找树进行中序遍历，会得到一个关键字的有序数列。

下图所示就是一个二叉查找树：

二叉查找树的查找算法
在二叉排序树b中查找x的过程为：

• 如果b是空树，则返回不包含
• 如果b的根结点的关键字等于x，则包含
• 如果b的根结点的关键字小于x，则在b的右子树中查找x
• 在b的左子树中查找x

private boolean find(Node node, T data) {
    if (node == null) {
        return false;
    }
    if (node.data.compareTo(data) == 0) {
        return true;
    } else if (node.data.compareTo(data) < 1) {
        return find(node.right, data);
    } else {
        return find(node.left, data);
    }
}

二叉查找树的插入算法
往二叉查找树b中插入一个结点s：

1. 如果b的根结点为null，则将s作为b的根结点
2. 如果树要求不能存在重复的关键字，在b的根结点的关键字与s的关键字相等时，返回false
3. 如果b的根结点的关键字小于(等于)s的关键字，则向b的右子树插入s结点
4. 向b的左子树插入s结点
   如果二叉树b不要求结点关键字不能重复的话，则没有第二步，等于的判断可以被加到第3步中，也可以默认放在第4步中

private boolean add(Node node, T data) {
    if (node == null) {
        node = new Node(data);
    } else if (node.data.compareTo(data) == 0) {
        return false;
    } else if (node.data.compareTo(data) < 0) {
        add(node.right, data);
    } else {
        add(node.left, data);
    }
    return true;
}

二叉查找树的删除算法
二叉查找树的删除算法需要分三种情况：

1. 删除结点是叶子结点；
2. 删除结点只有左子结点或者右子节点；
3. 删除结点既有左子节点也有右子节点；
   1. 删除结点是叶子结点
   直接删除该节点
   
   2. 删除结点只有左子节点或者右子结点
   将父节点中删除的结点用删除结点的唯一子节点替换
   
   删除有两个子节点的结点
   找到要删除结点的后继结点¹，将后继结点的值赋值给要删除的结点，删除后继结点
   
   如果要删除上图中的值为5的结点，先找到5的后继节点为7，将7赋值给5对应的结点，删除原来7对应的结点即可。

private boolean remove(Node node, T data) {
    if (node == null) {
        return false;
    } else if (node.data.compareTo(data) == 0) {
        if (node.left != null && node.right != null) {
            Node successorNode = successorNode(node.right);
            node.data = successorNode.data;
            node = successorNode;
        }
        Node child = null;
        if (node.left != null) {
            child = node.left;
        } else if (node.right != null) {
            child = node.right;
        }
        if (node.parent == null) {
            root = child;
        } else if (node.parent.right == node) {
            node.parent.right = child;
        } else {
            node.parent.left = child;
        }
    } else if (node.data.compareTo(data) < 0) {
        remove(node.right, data);
    } else {
        remove(node.left, data);
    }
    return true;
}

// 查找后继结点
private Node successorNode(Node node) {
    if (node.left == null) {
        return node;
    }
    return successorNode(node.left);
}

---

1. 后继结点：结点的右子树的最左结点 ↩︎