>>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)]) >>> is_bst(t2) False这个样例测试不通过
时间: 2024-03-03 07:47:05 浏览: 27
是的,这个样例测试确实不通过。这是因为在这个树中,3 的值比它的左子树中的最大值 2 大,但是它的右子树中的最小值 5 却比它小,因此这个树不是二叉搜索树。
为了解决这个问题,我们需要修改 `is_bst` 函数中的条件,以便它检查子树中的所有节点是否符合条件。具体来说,我们可以将左子树的最大值和右子树的最小值作为参数传递给 `is_bst` 函数,然后在对左右子树进行递归时将这些参数更新为当前节点的值。这样,我们可以确保左子树中的所有节点都小于等于当前节点,右子树中的所有节点都大于当前节点。
以下是修订版的代码:
```python
def is_bst(t, min_val=float('-inf'), max_val=float('inf')):
"""
判断树 t 是否为二叉搜索树
"""
if t.is_leaf():
return True
elif len(t.branches) == 1:
return is_bst(t.branches[0], min_val, max_val)
else:
left, right = t.branches
# 判断左子树是否为二叉搜索树
if min_val <= left.label <= t.label and is_bst(left, min_val, t.label):
# 判断右子树是否为二叉搜索树
if t.label <= right.label <= max_val and is_bst(right, t.label, max_val):
return True
return False
```
在这个修订版的函数中,我们将 `min_val` 和 `max_val` 参数添加到函数的参数列表中,并将它们的默认值分别设置为负无穷和正无穷。这两个参数用于记录当前子树中的最小值和最大值。在递归调用左右子树时,我们更新这些参数以反映当前节点的值。同时,我们还在检查左右子树是否为二叉搜索树时添加了额外的条件,以确保节点的值在 `min_val` 和 `max_val` 范围内。
下面是修订版函数的测试用例:
```python
t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
print(is_bst(t1)) # True
t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
print(is_bst(t2)) # False
t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
print(is_bst(t3)) # False
t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
print(is_bst(t4)) # True
t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
print(is_bst(t5)) # True
t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
print(is_bst(t6)) # True
t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
print(is_bst(t7)) # False
```
现在,这些测试用例都通过了。