GC01-判断二叉树是否为二叉搜索树¶

问题分析¶

二叉搜索树（BST）的性质： - 对于任意结点，其左子树中所有结点值都小于该结点值 - 对于任意结点，其右子树中所有结点值都大于该结点值 - 中序遍历结果为严格递增序列

[[#1. 方法一优化：边遍历边验证]]

方法一：中序遍历 + 数组验证¶

代码实现¶

C
/**
 * 中序遍历函数：将二叉树按中序遍历顺序存储到数组中
 * 参数说明：
 * T - 当前遍历的二叉树结点
 * res[] - 存储遍历结果的数组
 * index - 数组下标指针（引用传递）
 */
void inprint(BiTree T, int res[], int *index) {
    // 递归终止条件：当前结点为空
    if (T != NULL) {
        // 左子树遍历
        inprint(T->lchild, res, index);

        // 访问当前结点（中序遍历核心）
        res[(*index)++] = T->data;

        // 右子树遍历
        inprint(T->rchild, res, index);
    }
}

/**
 * 验证数组是否为严格递增序列
 * 参数说明：
 * res[] - 待验证的数组
 * index - 数组有效元素个数
 * 返回值：true表示严格递增，false表示不是
 */
bool isture(int res[], int index) {
    // 遍历数组，检查相邻元素是否严格递增
    for (int i = 0; i < index - 1; i++) {
        if (res[i] >= res[i + 1]) {  // 注意：BST要求严格递增
            return false;
        }
    }
    return true;
}

/**
 * 方法一主函数：判断二叉树是否为BST
 */
bool isBST_Method1(BiTree T) {
    int res[MAXSIZE];  // 存储中序遍历结果
    int index = 0;     // 数组下标

    // 中序遍历获取序列
    inprint(T, res, &index);

    // 验证序列是否严格递增
    return isture(res, index);
}

执行过程图解¶

C
// 二叉树示例：
//       5
//      / \
//     3   8
//    / \ / \
//   2  4 7  9

// 中序遍历过程：
// 访问顺序：2 → 3 → 4 → 5 → 7 → 8 → 9
// 数组res：[2, 3, 4, 5, 7, 8, 9]
// 验证：2<3<4<5<7<8<9 → 严格递增 → 是BST

方法二：递归范围约束法¶

代码实现¶

C
/**
 * 方法二：递归判断BST，通过维护值的范围约束
 * 参数说明：
 * T - 当前检查的二叉树结点
 * low - 当前结点值的下界（不包含）
 * high - 当前结点值的上界（不包含）
 * 返回值：true表示满足BST性质，false表示不满足
 */
bool func(BiTree T, int low, int high) {
    // 递归终止条件：空结点满足BST性质
    if (T == NULL) {
        return true;
    }

    // 检查当前结点值是否在有效范围内
    if (T->data <= low || T->data >= high) {
        return false;  // 违反BST性质
    }

    // 递归检查左右子树
    // 左子树：值范围 (low, T->data)
    bool left = func(T->lchild, low, T->data);

    // 右子树：值范围 (T->data, high)
    bool right = func(T->rchild, T->data, high);

    // 返回左右子树的检查结果
    return left && right;
}

/**
 * 方法二主函数：判断二叉树是否为BST
 */
bool isBST_Method2(BiTree T) {
    // 初始调用：根结点值范围 (-∞, +∞)
    return func(T, INT_MIN, INT_MAX);
}

执行过程图解¶

C
// 二叉树示例：
//       5
//      / \
//     3   8
//    / \ / \
//   2  4 7  9

// 递归调用过程：
// func(5, INT_MIN, INT_MAX)  // 5 ∈ (-∞, +∞) ✓
// ├── func(3, INT_MIN, 5)    // 3 ∈ (-∞, 5) ✓
// │   ├── func(2, INT_MIN, 3) // 2 ∈ (-∞, 3) ✓
// │   └── func(4, 3, 5)      // 4 ∈ (3, 5) ✓
// └── func(8, 5, INT_MAX)    // 8 ∈ (5, +∞) ✓
//     ├── func(7, 5, 8)      // 7 ∈ (5, 8) ✓
//     └── func(9, 8, INT_MAX) // 9 ∈ (8, +∞) ✓

// 结果：所有检查都通过 → 是BST

复杂度分析¶

方法一：中序遍历 + 数组验证¶

时间复杂度¶

中序遍历：O(N) - 访问每个结点一次
数组验证：O(N) - 检查N-1对相邻元素
总体时间复杂度：O(N)

空间复杂度¶

数组存储：O(N) - 存储N个结点值
递归栈：O(h) - h为树的高度，最坏O(N)
总体空间复杂度：O(N)

方法二：递归范围约束法¶

时间复杂度¶

递归检查：O(N) - 每个结点最多被访问一次
总体时间复杂度：O(N)

空间复杂度¶

递归栈：O(h) - h为树的高度，最坏O(N)
额外变量：O(1) - 只使用常数个局部变量
总体空间复杂度：O(N)（最坏情况）

两种方法对比¶

特性	方法一	方法二
核心思想	中序遍历 + 验证	范围约束递归
时间复杂度	O(N)	O(N)
空间复杂度	O(N)	O(N)
实现难度	简单直观	稍复杂
执行效率	需要两次遍历	一次遍历
提前终止	不能	能

算法正确性证明¶

方法一正确性¶

BST性质 ⇔ 中序遍历结果严格递增
通过中序遍历获得序列，验证序列严格递增即可

方法二正确性¶

BST性质：任意结点值必须在指定范围内
递归维护：通过传递范围约束保证全局性质
数学归纳法：可以证明正确性

优化版本¶

1. 方法一优化：边遍历边验证¶

C
/**
 * 函数：isBST_Optimized1
 * ----------------------
 * 判断给定的二叉树是否为合法的二叉搜索树（BST）。
 * 
 * 算法思路：
 *   利用 BST 的中序遍历具有「严格递增」特性的性质，
 *   在中序遍历时动态记录前一个访问的节点值，检查当前值是否大于前驱值。
 *   若全程满足，则为 BST。
 * 
 * 优势：
 *   - 时间复杂度：O(n)，每个节点访问一次
 *   - 空间复杂度：O(h)，h 为树高（递归栈深度），无需额外数组存储遍历结果
 * 
 * 参数：
 *   root: 指向二叉树根节点的指针
 * 
 * 返回值：
 *   true  -> 是 BST
 *   false -> 不是 BST
 */
bool isBST_Optimized1(BiTree root) {
    int prevValue = INT_MIN;  // 记录中序遍历中上一个访问的节点值，初始化为最小整数
    return inorderCheckBST(root, &prevValue);
}

/**
 * 函数：inorderCheckBST
 * ---------------------
 * 辅助函数：通过中序遍历验证 BST 性质。
 * 
 * 执行顺序：左 → 根 → 右
 * 验证规则：当前节点值必须 > 前一个访问的节点值（严格递增）
 * 
 * 参数：
 *   node: 当前遍历到的节点
 *   prevValue: 指向前一个访问节点值的指针（用于跨递归调用传递状态）
 * 
 * 返回值：
 *   true  -> 当前子树满足 BST 性质
 *   false -> 发现违反 BST 性质的情况
 */
bool inorderCheckBST(BiTree node, int* prevValue) {
    // 基础情况：空节点不破坏 BST 性质
    if (node == NULL) {
        return true;
    }

    // 1. 递归检查左子树
    if (!inorderCheckBST(node->lchild, prevValue)) {
        return false;  // 左子树已不满足，提前返回
    }

    // 2. 检查当前节点：必须严格大于前一个中序访问的值
    if (node->data <= *prevValue) {
        return false;  // 出现非递增，违反 BST 规则
    }
    *prevValue = node->data;  // 更新前驱值为当前节点值

    // 3. 递归检查右子树
    return inorderCheckBST(node->rchild, prevValue);
}

复杂度类型	表达式	说明
时间复杂度	O(n)	每个节点访问一次
空间复杂度	O(h)	h 为树高，递归栈开销
### 2. 方法二优化：使用长整型避免溢出

C
/**
 * 优化版本：使用long long避免整数溢出
 */
bool isBST_Optimized2(BiTree T) {
    return func_safe(T, LLONG_MIN, LLONG_MAX);
}

bool func_safe(BiTree T, long long low, long long high) {
    if (T == NULL) return true;

    if (T->data <= low || T->data >= high) {
        return false;
    }

    return func_safe(T->lchild, low, T->data) &&
           func_safe(T->rchild, T->data, high);
}

实际应用场景¶

1. 数据库索引验证¶

C
// 验证B+树索引结构是否正确
bool validate_btree_index(BiTree index_root) {
    return isBST_Method2(index_root);
}

2. 编译器语法树检查¶

C
// 验证表达式树是否满足BST性质
bool validate_expr_tree(BiTree expr_root) {
    return isBST_Method2(expr_root);
}

3. 文件系统目录验证¶

C
// 验证目录树结构是否正确
bool validate_directory_tree(BiTree dir_root) {
    return isBST_Method2(dir_root);
}

错误示例分析¶

常见错误实现¶

C
// 错误方法：只检查直接孩子
bool wrong_isBST(BiTree T) {
    if (T == NULL) return true;

    // 错误：只检查直接孩子，忽略了孙子结点
    if (T->lchild && T->lchild->data >= T->data) return false;
    if (T->rchild && T->rchild->data <= T->data) return false;

    return wrong_isBST(T->lchild) && wrong_isBST(T->rchild);
}

// 反例：
//     3
//    / \
//   2   5
//  /
// 1
// 虽然直接孩子满足条件，但结点1 < 结点3，违反BST性质

理论扩展¶

1. 与其他树结构的关系¶

C
// AVL树判定
bool isAVL(BiTree T) {
    return isBST_Method2(T) && isBalanced(T);
}

// 红黑树判定
bool isRedBlack(BiTree T) {
    // 更复杂的判定逻辑...
    return isBST_Method2(T) && satisfiesRedBlackProperties(T);
}

2. 在不同存储结构中的应用¶

C
// 数组存储的完全二叉树判定
bool isBST_Array(int arr[], int n, int i, int low, int high) {
    if (i >= n) return true;
    if (arr[i] <= low || arr[i] >= high) return false;

    return isBST_Array(arr, n, 2*i+1, low, arr[i]) &&
           isBST_Array(arr, n, 2*i+2, arr[i], high);
}

3. 并行化处理¶

C
// 对于大规模树结构，可以考虑并行处理
bool isBST_Parallel(BiTree T) {
    // 左右子树可以并行验证
    // 但需要同步机制保证正确性
    // 实际应用中需要考虑线程安全
}

总结¶

两种方法各有优势：

方法一特点¶

直观易懂：符合人类思维习惯
易于调试：可以查看完整的中序遍历序列
适合教学：便于理解BST性质

方法二特点¶

高效实用：一次遍历完成判定
提前终止：发现违反性质时立即返回
空间优化：不需要额外数组存储

选择建议¶

学习理解：推荐方法一
实际应用：推荐方法二
性能要求高：推荐方法二的优化版本

这两种方法都体现了分治思想和约束传播的算法设计技巧，是树算法中的经典范例。通过对比学习，可以更好地理解不同算法设计思路的优劣。