编程判断一棵二叉树是否为二叉排序树 ⑴ 二叉树采用二叉链表作为存储结构,且树中结点的关键字均不相同。 ⑵ 要输出最后的判断结果。
时间: 2023-10-19 11:14:56 浏览: 89
//该程序用于判断二叉树是否为二叉排序树
好的,我明白了。判断一棵二叉树是否为二叉排序树,需要满足以下条件:
1. 对于每个结点,它的左子树中的所有结点的关键字都比它小;
2. 对于每个结点,它的右子树中的所有结点的关键字都比它大;
3. 左子树和右子树都是二叉排序树。
根据这个条件,可以编写一段递归代码来判断二叉树是否为二叉排序树。
```python
def is_bst(root, min_val=None, max_val=None):
if root is None:
return True
if min_val is not None and root.val <= min_val:
return False
if max_val is not None and root.val >= max_val:
return False
return is_bst(root.left, min_val, root.val) and is_bst(root.right, root.val, max_val)
```
在这段代码中,min_val和max_val分别表示左子树和右子树的最小值和最大值。如果当前结点的值超出了这个范围,那么就不是二叉排序树。
如果root为None,说明子树为空,返回True。否则,判断当前结点的值是否超出了范围,并且递归判断左子树和右子树是否都是二叉排序树。
最后,调用is_bst函数来判断整棵二叉树是否为二叉排序树,并输出最后的结果。
希望我的回答能够帮助到你。如果你还有其他问题,请继续向我提问。
阅读全文