1
二叉树：每个节点最多两个子节点
2
BST：对「每个」节点，其左子树所有值更小、右子树所有值更大
3
     若允许重复值，左子树可为「小于或等于」
4
左子树、右子树「自身也必须是 BST」—— 不仅仅是根节点

1
B：根值 10，但左子树中有 11（比 10 大）→ 违反「左子树全部更小」
2
D：根值 5，左子树有 1、右子树有 8、9、12 → 对根节点来说没问题；
3
   但值为 8 的节点，其左边有个 9 → 不是 BST

1
isSubtreeLesser(root, value)   → 子树中所有元素都 ≤ value 则返回真
2
isSubtreeGreater(root, value)  → 子树中所有元素都 > value 则返回真

1
① isSubtreeLesser(root->left,  root->data)
2
② isSubtreeGreater(root->right, root->data)
3
③ isBinarySearchTree(root->left)
4
④ isBinarySearchTree(root->right)

1
根节点范围 (−∞, +∞)
2
向左走 → 收紧上限（新上限 = 当前节点数据）
3
向右走 → 收紧下限（新下限 = 当前节点数据）

1
int isBSTUtil(struct node *root, int min, int max) {
2
    if (root == NULL) return 1;
3
    if (root->data > min && root->data < max
4
        && isBSTUtil(root->left,  min, root->data)
5
        && isBSTUtil(root->right, root->data, max))
6
        return 1;
7
    else return 0;
8
}
9

10
int isBinarySearchTree(struct node *root) {
11
    return isBSTUtil(root, INT_MIN, INT_MAX);
12
}

1
对二叉树做中序遍历，若是 BST，读到的数据必然有序
2
技巧：遍历时记录前一个读过的节点
3
      任何时刻「当前节点数据必须大于前一个节点数据」

1
① 在「右子树中找最小值」
2
② 把该最小值「复制/填入」被删节点
3
③ 再从右子树中删除那个「最小值节点」
4
   （它必无左孩子，于是情形三降级为情形一或情形二）

1
它来自右子树 → 一定大于被删节点
2
又是右子树最小值 → 右侧其余元素都 ≥ 它
3
左侧元素本就都更小
4
→ BST 性质保持

1
树/子树中具有最小值的节点一定没有左孩子（有左孩子就会有更小的值），但可能有右孩子
2
  → 若有右孩子 → 降级为情形二
3
  → 若无右孩子 → 降级为情形一

1
左子树最大值 ≥ 左子树所有值，且因为来自左子树所以 < 被删值
2
该节点一定没有右孩子（有右孩子就有更大值），可能有左孩子

1
struct node *Delete(struct node *root, int data) {
2
    if (root == NULL) return root;                    /* 空树直接返回 */
3
    else if (data < root->data)
4
        root->left  = Delete(root->left,  data);      /* 去左子树删 */
5
    else if (data > root->data)
6
        root->right = Delete(root->right, data);      /* 去右子树删 */
7
    else {                                            /* 找到了 */
8
        /* 情形一：无子节点 */
9
        if (root->left == NULL && root->right == NULL) {
10
            delete root;                              /* C 用 free(root) */
11
            root = NULL;
12
        }
13
        /* 情形二：只有一个子节点 */
14
        else if (root->left == NULL) {                /* 只有右孩子 */
15
            struct node *temp = root;
16
            root = root->right;
17
            delete temp;
18
        }
19
        else if (root->right == NULL) {               /* 只有左孩子 */
20
            struct node *temp = root;
21
            root = root->left;
22
            delete temp;
23
        }
24
        /* 情形三：两个子节点 */
25
        else {
26
            struct node *temp = FindMin(root->right); /* 右子树最小值 */
27
            root->data = temp->data;                  /* 复制值 */
28
            root->right = Delete(root->right, temp->data);  /* 删掉那个副本 */
29
        }
30
    }
31
    return root;                                      /* 统一在所有分支之后返回 */
32
}

1
示例树：根 5；左 3（左孩子 1）；右 12；12 的左孩子 7（7 的右孩子 9）
2
        另有 15（左 13、右 17）、19 等
3

4
叶子节点（4 个）：      1、9、13、19
5
只有一个子节点（2 个）：3（只有左孩子 1）、7（只有右孩子 9）

1
删 19           → 父节点 17 的子节点置空
2
删 7            → 把 9 设为 5 的右孩子（9 及其以下整棵子树接到 5 右侧）
3
删 3            → 把 1 设为 5 的左孩子
4
删 15（两个子节点）→ 右子树最小值 = 17 → 用 17 覆盖 15 的位置，
5
                   再删掉原 17 节点（17 只有一个子节点 19 → 情形二），最终树仍合法

1
6, 8, 10, 11, 12, 15, 16, 17, 20, 25, 27

1
从某节点的左孩子返回该节点时，该节点尚未被访问
2
从右孩子返回父节点时，父节点已被访问过

1
中序后继 = 右子树中的最左侧节点
2
         = 右子树中具有最小值的节点
3
做法：只要能向左就一直向左走

1
需要「从根节点走到该节点」
2
找「最近的祖先节点，使得给定节点处于其左子树中」

1
若从左边回到某祖先，该祖先尚未被访问 → 它就是后继
2
若从右边回到某祖先，该祖先已访问过   → 继续往上回退

1
10 → 11     10 有右子树，右子树最小是 11
2
8  → 10     8 无右子树，从左边回到 10
3
12 → 15     12 无右子树；先到 10，但 12 在 10 的右边，排除；
4
            再到 15，12 在 15 的左边 → 15 是后继
5
6  → 8      从根走到 6 的路径上，6 在其左子树中的最深的那个祖先是 8
6
15 → 16、16 → 17、17 → 20、20 → 25、25 → 27
7
27（最大值）→ 没有后继，返回 NULL

1
中序遍历 O(n) 代价太高
2
BST 的插入/删除/搜索都是 O(h)，所以希望在 O(h) 内找到后继
3
平衡二叉树高度 = log₂N，O(log n) 几乎是最佳运行时间

1
struct node *Getsuccessor(struct node *root, int data) {
2
    struct node *current = Find(root, data);      /* 先找到该节点 */
3
    if (current == NULL) return NULL;             /* 树中不存在 */
4

5
    if (current->right != NULL) {                 /* 情形一：有右子树 */
6
        return FindMin(current->right);           /* 右子树最小值（最左节点） */
7
    }
8
    else {                                        /* 情形二：无右子树 */
9
        struct node *successor = NULL;
10
        struct node *ancestor  = root;
11
        while (ancestor != current) {
12
            if (current->data < ancestor->data) { /* current 在祖先左侧 */
13
                successor = ancestor;             /* 这个祖先「可能是」后继 */
14
                ancestor  = ancestor->left;       /* 继续向左，找更深的 */
15
            }
16
            else {                                /* current 在祖先右侧 */
17
                ancestor = ancestor->right;       /* 只向右走，不更新 successor */
18
            }
19
        }
20
        return successor;                         /* 可能为 NULL */
21
    }
22
}

1
Find 找节点：O(h)
2
FindMin：O(h)
3
从根走到某节点：O(h)
4

5
→ 整个 Getsuccessor 的总时间复杂度 = O(h)