二叉排序树（BST, Binary Search Tree）

二叉排序树（BST，也称二叉搜索树）或者是一棵空树，或者是满足下列性质的二叉树：

• 若左子树非空，则左子树上所有结点的值都小于根结点的值；
• 若右子树非空，则右子树上所有结点的值都大于根结点的值；
• 左、右子树也分别是二叉排序树。

查找

从根开始，与目标值比较：相等则找到；小于当前结点则进入左子树；大于则进入右子树，直到空（失败）。

插入

沿查找路径下到“应插入位置的父结点”，作为叶子插入（BST 的新结点总是叶子）。

删除（三种情况）

1. 叶子结点：直接删除。
2. 只有一棵子树：用子树代替被删结点。
3. 有两棵子树：用直接前驱（左子树最右结点）或直接后继（右子树最左结点）替换被删结点，再删除那个前驱/后继。

// 查找（递归）
BiTNode *SearchBST(BiTree T, int key) {
    if (!T || key == T->data) return T;
    if (key < T->data) return SearchBST(T->lchild, key);
    else return SearchBST(T->rchild, key);
}

依次插入 50, 30, 70, 20, 40, 60, 80 得到如下 BST：

中序遍历得到 20, 30, 40, 50, 60, 70, 80，递增，符合 BST 性质。