尋找二叉搜索樹中節點的後繼節點：三種場景完整解析

編輯：關於C語言

定義

在 BST 中，節點 x 的後繼節點是中序遍歷中緊隨 x 之後的節點，即值大於 x 的最小節點。

三種情況

情況 1：節點有右子樹

後繼節點是右子樹中最左節點（右子樹的最小值）。


TreeNode* successor(TreeNode* x) {
    if (x->right) {
        TreeNode* p = x->right;
        while (p->left) p = p->left;
        return p;
    }
    // ... 處理情況 2、3
}

情況 2：節點無右子樹，且是某祖先的左子孫

向上追溯，第一個將當前節點作為左子孫的祖先即為後繼。


TreeNode* p = x->parent;
while (p && x == p->right) {  // 一直是右孩子，繼續向上
    x = p;
    p = p->parent;
}
return p;  // p 為 null 表示 x 是最大節點，無後繼

情況 3：節點無右子樹，且是右子孫（或根）

同上邏輯，循環會一直走到根的父節點（null），返回 NULL，表示無後繼（該節點是最大值）。

統一實現（含父指針版）


TreeNode* inorderSuccessor(TreeNode* x) {
    if (!x) return NULL;
    // 情況 1：有右子樹
    if (x->right) {
        x = x->right;
        while (x->left) x = x->left;
        return x;
    }
    // 情況 2/3：無右子樹，向上找第一個左拐的祖先
    while (x->parent && x == x->parent->right)
        x = x->parent;
    return x->parent;
}

無父指針版（從根查找）


TreeNode* inorderSuccessor(TreeNode* root, TreeNode* x) {
    TreeNode* succ = NULL;
    while (root) {
        if (x->val < root->val) {
            succ = root;       // root 是候選後繼
            root = root->left;
        } else if (x->val > root->val) {
            root = root->right;
        } else { // 找到 x
            if (root->right) { // 情況 1
                root = root->right;
                while (root->left) root = root->left;
                return root;
            }
            return succ;       // 情況 2/3，succ 已記錄
        }
    }
    return NULL;
}

利用 BST 性質：向左走時，當前節點比目標大，是潛在後繼；向右走時，當前節點比目標小，不可能是後繼。