定义

二叉查找树(Binary Search Tree)，又叫二叉排序树或二叉搜索树，它或者是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
它的左右子树也分别为二叉排序树。

二叉排序树

操作

BST的节点结构和普通二叉树没有区别

class Node {
    int data; // 数据域
    Node left; // 左孩子
    Node right; // 右孩子
}

插入

向一颗BST中插入节点p，如果是一颗空树，则p就是树的根节点，否则判断根节点的数据域与p的数据域，如果p的数据域大，则在根节点的右子树中插入节点p，否则在根节点的左子树中插入节点p，递归执行上述流程，直至p插入完成。

伪代码
function insertNode(root, p) {
    if root is null:
        root = p;
        return;
    if root.data > p.data:
        root = root.left;
    else:
        root = root.right;
    
    insertNode(root, p);
}

查找

查找操作类似二分查找，先判断根节点，若根节点为空，则返回false，如果根节点的数据域等于p的数据域，则返回true，如果根节点的数据域大于p的数据域，则在根的左子树中查找，否则在根的右子树中查找。

伪代码
function searchNode(root, key){
    if root is null:
        return null;
    if root.data = key:
        return root;
    else if root.data > key:
        searchNode(root->left, key);
    else :
        searchNode(root->right, key);
}

前驱、后继节点

前驱节点指小于给定节点p的节点中最大的节点，一般情况下，前驱节点是节点p的左子树的最右节点，若左子树为空，则是p的右孩子。
后继节点指大于给定节点p的节点中最小的节点，一般情况下，后继节点是节点p的右子树的最左节点，若右子树为空，则是p的左孩子。

后继节点伪代码
function nextNode(root, key) {
    if root->right is null:
        return root->left;
    
    root = root->right;
    while(root->left is not null):
        root = root->left;
    return root;
}

删除

删除节点操作相对于插入和查找操作来说要复杂很多，要分不同的情况进行讨论：

删除节点是叶子节点
删除节点非叶子节点，且仅有左孩子
删除节点非叶子节点，且仅有右孩子
删除节点非叶子节点，且既有左孩子又有右孩子

对于情况1，则直接删除节点即可。
对于情况2，将p的左孩子代替p即可。
对于情况3，将p的右孩子代替p即可。
对于情况4，需要先找到p的后继节点n，使用n代替p即可。

function deleteNode(root, p){
    if p->left is null and p->right is null:
        delete p from parent(p)
    else if p->left is not null and p->right is null:
        parent(p) link to p->left
        delete p
    else if p->left is null and p->right is not null:
        parent(p) link to p->right
        delete p
    else:
        n = nextNode(root, p)
        parent(n) link to n->right
        parent(p) link to n
        delete p
}