GC02-判断顺序存储的二叉树是否为二叉搜索树

代码实现

// 函数 func：判断顺序存储的二叉树是否为二叉搜索树
// 参数说明：
// T - 顺序存储的二叉树结构
// i - 当前检查结点的数组下标
// low - 当前结点值的下界（不包含）
// high - 当前结点值的上界（不包含）
bool func(SqBiTree T, int i, ElemType low, ElemType high) {
    // 递归终止条件1：下标超出范围或结点为空
    if (i >= T.ElemNum || T.Node[i] == -1) {
        return true;  // 空子树满足二叉搜索树性质
    }

    // 递归终止条件2：当前结点值不满足BST性质
    if (T.Node[i] <= low || T.Node[i] >= high) {
        return false;  // 违反二叉搜索树的范围约束
    }

    // 递归检查左右子树
    // 左子树：值的范围应在 (low, T.Node[i]) 之间
    bool left = func(T, 2 * i + 1, low, T.Node[i]);

    // 右子树：值的范围应在 (T.Node[i], high) 之间
    bool right = func(T, 2 * i + 2, T.Node[i], high);

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

---

代码逻辑解析

1. 顺序存储的二叉树结构

// 顺序存储的二叉树结构定义
typedef struct {
    ElemType Node[MAXSIZE];  // 数组存储结点值
    int ElemNum;             // 实际结点个数
} SqBiTree;

// 存储规律：
// 下标为 i 的结点：
// - 父结点下标：(i-1)/2 (i > 0)
// - 左孩子下标：2*i + 1
// - 右孩子下标：2*i + 2

2. 二叉搜索树的判定原理

// BST性质：对于任意结点，其值必须在特定范围内
// 根结点：范围 (-∞, +∞)
// 左子树：范围 (父结点下界, 父结点值)
// 右子树：范围 (父结点值, 父结点上界)

3. 执行流程图解

顺序存储的二叉树示例（数组下标从0开始）：
数组：[5, 3, 8, 2, 4, 7, 9]
树形结构：
       5(0)
      /    \
    3(1)   8(2)
   /  \    /  \
 2(3) 4(4) 7(5) 9(6)

验证过程：
根结点5：范围(-∞, +∞) → 5 ∈ (-∞, +∞) ✓
├─ 左子树3：范围(-∞, 5) → 3 ∈ (-∞, 5) ✓
│  ├─ 左子树2：范围(-∞, 3) → 2 ∈ (-∞, 3) ✓
│  └─ 右子树4：范围(3, 5) → 4 ∈ (3, 5) ✓
└─ 右子树8：范围(5, +∞) → 8 ∈ (5, +∞) ✓
   ├─ 左子树7：范围(5, 8) → 7 ∈ (5, 8) ✓
   └─ 右子树9：范围(8, +∞) → 9 ∈ (8, +∞) ✓

结果：是二叉搜索树

4. 递归执行过程

// 调用过程示例：func(T, 0, INT_MIN, INT_MAX)
// 递归调用栈示意：
// func(0, INT_MIN, INT_MAX)  // 检查根结点5
// ├── func(1, INT_MIN, 5)    // 检查左子树3
// │   ├── func(3, INT_MIN, 3) // 检查左子树2
// │   └── func(4, 3, 5)      // 检查右子树4
// └── func(2, 5, INT_MAX)    // 检查右子树8
//     ├── func(5, 5, 8)      // 检查左子树7
//     └── func(6, 8, INT_MAX) // 检查右子树9

---

时间复杂度分析

1. 访问结点次数

• 每个有效结点最多被访问一次
• 空结点（值为-1）也会被检查一次
• 时间复杂度：O(N)，其中 N 是数组长度

2. 每步操作

• 基本比较操作：O(1)
• 递归调用：O(1)
• 每步时间：O(1)

3. 总体时间复杂度

O(N)，其中 N 是顺序存储数组的长度

---

空间复杂度分析

1. 递归调用栈

• 递归深度等于树的高度
• 完全二叉树：O(log N)
• 退化为链表：O(N)

2. 额外空间

• 参数传递：O(1) 每次调用
• 局部变量：O(1)

3. 总体空间复杂度

O(N)（最坏情况下的递归栈空间）

---

较难理解部分的说明

1. 范围约束的理解

// 为什么需要维护上下界？
// BST性质：左子树所有结点 < 根结点 < 右子树所有结点

// 错误的检查方法：
bool wrong_check(SqBiTree T, int i) {
    if (i >= T.ElemNum || T.Node[i] == -1) return true;

    // 只检查直接孩子，忽略了孙子结点
    if (T.Node[2*i+1] >= T.Node[i]) return false;  // 左孩子
    if (T.Node[2*i+2] <= T.Node[i]) return false;  // 右孩子

    return wrong_check(T, 2*i+1) && wrong_check(T, 2*i+2);
}

// 正确的检查方法：
// 维护每个结点值的有效范围
// 左子树：(父结点下界, 父结点值)
// 右子树：(父结点值, 父结点上界)

2. 边界条件处理

// 空结点的处理
if (i >= T.ElemNum || T.Node[i] == -1) {
    return true;  // 空树也是BST
}

// 范围边界处理
if (T.Node[i] <= low || T.Node[i] >= high) {
    return false;  // 等号表示违反BST性质
}

// 示例说明：
// 结点值为5，范围要求(3, 5)
// 5 >= 5，违反要求，返回false

3. 数组下标计算

// 顺序存储的下标规律（从0开始）：
// 结点i的：
// - 左孩子：2*i + 1
// - 右孩子：2*i + 2
// - 父结点：(i-1)/2

// 示例验证：
// 结点0：左孩子1，右孩子2
// 结点1：左孩子3，右孩子4
// 结点2：左孩子5，右孩子6

---

延伸知识点

1. 非递归实现版本

// 使用栈的非递归实现
bool func_iterative(SqBiTree T) {
    typedef struct {
        int index;
        ElemType low;
        ElemType high;
    } StackNode;

    StackNode stack[MAXSIZE];
    int top = -1;

    // 初始状态：根结点，范围(-∞, +∞)
    stack[++top] = (StackNode){0, INT_MIN, INT_MAX};

    while (top >= 0) {
        StackNode current = stack[top--];
        int i = current.index;
        ElemType low = current.low;
        ElemType high = current.high;

        // 空结点检查
        if (i >= T.ElemNum || T.Node[i] == -1) {
            continue;
        }

        // 范围检查
        if (T.Node[i] <= low || T.Node[i] >= high) {
            return false;
        }

        // 将左右子树入栈
        stack[++top] = (StackNode){2*i+1, low, T.Node[i]};      // 左子树
        stack[++top] = (StackNode){2*i+2, T.Node[i], high};     // 右子树
    }

    return true;
}

2. 中序遍历验证版本

// 通过中序遍历验证BST性质
bool func_inorder(SqBiTree T) {
    ElemType prev = INT_MIN;
    return inorder_check(T, 0, &prev);
}

bool inorder_check(SqBiTree T, int i, ElemType* prev) {
    if (i >= T.ElemNum || T.Node[i] == -1) {
        return true;
    }

    // 左子树
    if (!inorder_check(T, 2*i+1, prev)) {
        return false;
    }

    // 当前结点
    if (T.Node[i] <= *prev) {
        return false;  // 应该严格递增
    }
    *prev = T.Node[i];

    // 右子树
    return inorder_check(T, 2*i+2, prev);
}

3. 增强版数据结构

// 带范围信息的顺序存储结构
typedef struct {
    ElemType Node[MAXSIZE];
    int ElemNum;
    // 可以预计算每个位置的范围，避免重复计算
} EnhancedSqBiTree;

// 预处理版本
bool func_preprocessed(SqBiTree T) {
    // 可以预先计算每个位置的min/max值
    // 但这会增加空间复杂度
    return func(T, 0, INT_MIN, INT_MAX);
}

4. 错误检测与调试

// 带调试信息的版本
bool func_debug(SqBiTree T, int i, ElemType low, ElemType high, int depth) {
    if (i >= T.ElemNum || T.Node[i] == -1) {
        printf("%*s空结点 %d\n", depth*2, "", i);
        return true;
    }

    printf("%*s检查结点 %d (值=%d), 范围(%.0f, %.0f)\n", 
           depth*2, "", i, T.Node[i], (double)low, (double)high);

    if (T.Node[i] <= low || T.Node[i] >= high) {
        printf("%*s违反BST性质: %d 不在 (%.0f, %.0f) 范围内\n",
               depth*2, "", T.Node[i], (double)low, (double)high);
        return false;
    }

    bool left = func_debug(T, 2*i+1, low, T.Node[i], depth+1);
    bool right = func_debug(T, 2*i+2, T.Node[i], high, depth+1);

    return left && right;
}

5. 实际应用场景

// 数据库索引验证
bool validate_bst_index(SqBiTree index) {
    return func(index, 0, INT_MIN, INT_MAX);
}

// 文件系统目录结构验证
bool validate_directory_tree(SqBiTree dirs) {
    return func(dirs, 0, INT_MIN, INT_MAX);
}

// 表达式树验证
bool validate_expression_tree(SqBiTree expr_tree) {
    // 可以扩展为验证特定类型的BST
    return func(expr_tree, 0, INT_MIN, INT_MAX);
}

6. 理论扩展

数学性质分析：

BST判定的充要条件：
1. 空树是BST
2. 对于任意结点，其值必须在指定范围内
3. 其左右子树都必须是BST

时间复杂度理论下界：
- 必须检查每个结点至少一次
- Ω(N) 是理论下界
- 该算法达到 O(N)，是最优的

与其它BST判定方法的比较：

// 方法1：范围约束法（当前方法）
// 时间：O(N)，空间：O(h)
// 优点：一次遍历，提前终止
// 缺点：需要维护范围

// 方法2：中序遍历法
// 时间：O(N)，空间：O(h)  
// 优点：直观易懂
// 缺点：必须完成遍历

// 方法3：递归定义法（错误方法）
// 时间：O(N)，空间：O(h)
// 优点：代码简洁
// 缺点：无法正确处理孙子结点

在不同存储结构中的应用：

// 链式存储的BST判定
bool isBST_Linked(TreeNode* root, int min, int max) {
    if (!root) return true;
    if (root->val <= min || root->val >= max) return false;
    return isBST_Linked(root->left, min, root->val) &&
           isBST_Linked(root->right, root->val, max);
}

// 数组存储的BST判定（当前方法）
bool isBST_Array(SqBiTree T, int i, int min, int max) {
    // 基本相同，只是访问方式不同
}

这种方法体现了递归思想、约束传播和数据结构特性利用的完美结合。通过为每个结点维护有效的值范围，将全局的BST性质判定转化为局部的范围检查，是树算法中的经典设计模式。同时展示了顺序存储结构的特点和处理方法。