文章
316
粉丝
0
获赞
0
访问
46.4k
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;
}
/...
登录后发布评论
暂无评论,来抢沙发