如何判断一个二叉树是不是搜索二叉树?
时间: 2024-09-07 22:03:05 浏览: 56
搜索二叉树(BST,Binary Search Tree)是一种特殊的二叉树结构,它满足以下性质:
1. 每个节点的左子树只包含小于当前节点的数。
2. 每个节点的右子树只包含大于当前节点的数。
3. 左右子树也必须分别是二叉搜索树。
要判断一个给定的二叉树是否是搜索二叉树,我们可以采用以下两种方法之一:
方法一:中序遍历
由于搜索二叉树的特性,中序遍历搜索二叉树的结果应该是一个递增的有序序列。因此,我们可以进行中序遍历,并检查遍历结果是否严格单调递增。如果不是,则说明给定的二叉树不是搜索二叉树。
方法二:递归检查
我们也可以通过递归的方式,遍历树中的每个节点,并检查其左子树中的所有节点值是否小于该节点值,右子树中的所有节点值是否大于该节点值。同时,对每个子树重复这个过程,递归地检查整棵树是否满足搜索二叉树的性质。
以下是使用递归方法的伪代码:
```pseudo
function isBST(node, min = null, max = null) {
if (node == null) {
return true;
}
if (min != null && node.value <= min) {
return false;
}
if (max != null && node.value > max) {
return false;
}
return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}
```
在这个函数中,我们传递当前节点以及它的上界和下界。对于根节点,上界和下界是`null`。对于左子节点,我们更新上界为父节点的值;对于右子节点,我们更新下界为父节点的值。如果在任何节点上违反了这些条件,就意味着树不是搜索二叉树。
阅读全文