文章

316

粉丝

0

获赞

0

访问

46.4k

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

1):
核心依据:二叉搜索树的本质特征是 “对任意节点,其左子树中所有节点的值均小于该节点值,右子树中所有节点的值均大于该节点值”,而非仅约束直接左右孩子。
范围约束法:通过递归为每个节点设定合法取值范围,确保整个子树满足 BST 规则:
对当前节点,其值必须严格大于左边界(lower)且严格小于右边界(upper);
左子树的节点值需在 “父节点的左边界” 与 “当前节点值” 之间(即(lower, val));
右子树的节点值需在 “当前节点值” 与 “父节点的右边界” 之间(即(val, upper))。
空节点处理:顺序存储中以值为-1表示空节点,空节点默认满足 BST 条件。
递归逻辑:从根节点(索引 0)开始,初始范围设为(-∞, +∞)(用INT_MIN和INT_MAX表示),逐层递归检查左、右子树(索引分别为2*i+1和2*i+2),最终通过左右子树的合法性共同判定当前树是否为 BST。
该设计通过传递动态范围,严格约束了所有子节点的取值,避免了仅判断直接孩子而忽略深层节点的逻辑漏洞。

 

2):

bool is_SearchTree(SqBiTree& root, int i, int lower, int upper) {
    // 空节点(值为-1)视为满足条件
    if (root->SqBiTNode[i] == -1) {
        return true;
    }
    int val = root->SqBiTNode[i];
    // 当前节点值需严格在(lower, upper)范围内
    if (val <= lower || val >= upper) {
        return false;
    }
    /...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发