文章

63

粉丝

0

获赞

0

访问

13.4k

头像
2022年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年10月10日 09:40
阅读数 132

(1) 该算法的核心思想是,不能只通过比较一个节点和其直接子节点来判断,而必须确保每个节点都满足其所有祖先节点所施加的约束。为此,我们采用递归遍历全树,并为每个节点都设定一个有效的取值范围 (min, max)。当向左子树递归时,当前节点的值就成为左子树新的上界(max);当向右子树递归时,当前节点的值则成为右子树新的下界(min)。通过检查每个节点的值是否都严格落在这个从上层层层传递并不断收紧的范围之内,就能保证整棵树的全局有序性。

(2)

// 递归辅助函数,真正执行判断逻辑
// 使用 long long 类型的 min_val 和 max_val 是为了处理边界情况,
// 即当树中节点的值本身就是 INT_MIN 或 INT_MAX 时,我们的范围判断依然有效。
bool isBST_helper(SqBiTree* tree, int node_idx, long long min_val, long long max_val) {
    // 基线条件1 (Base Case): 如果节点索引超出了元素数量,或者节点为空(-1),
    // 说明这是一棵空树或者到达了叶子节点的子节点,是合法的BST。
    if (node_idx >= tree->ElemNum || tree->SqBiTNode[node_idx] == -1) {
        return true;
    }

    // 获取当前节点的值
    int current_val = tree->SqBiTNode[node_idx];

    // 核心判断逻辑:
    // 检查当前节点的值是否在从父节点继承下来的有效范围内。
    // 注意:这里用 <= 和 >= 来进行判断,确保节点值严格小于max且严格大于min。
    // 如果等于边界值,则不满足BST的严格定义。
    if (current_val <= min_val || current_val >= max_val) {
        return false;
    }

    // 递归地检查左右子树
    // 1. 检查左子树:左子树...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发