判断是否为二叉排序树
时间: 2023-08-21 14:13:19 浏览: 49
判断二叉树是否为二叉排序树(BST),需要满足以下条件:
1. 对于任意节点,其左子树中所有节点的值均小于该节点的值;
2. 对于任意节点,其右子树中所有节点的值均大于该节点的值;
3. 左右子树都必须是二叉排序树。
因此,可以采用递归的方式进行判断。对于每个节点,判断其值是否在合法的范围内,并递归判断左右子树是否也是二叉排序树。
以下是一个示例的 Python 代码:
```python
def is_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
val = root.val
if val <= low or val >= high:
return False
return is_bst(root.left, low, val) and is_bst(root.right, val, high)
```
其中 `low` 和 `high` 分别表示当前节点的值的下界和上界,最开始为负无穷和正无穷。如果当前节点的值超出了范围,则说明不是二叉排序树。否则,递归判断左右子树即可。
相关问题
如何判断是否为二叉排序树
要判断一个二叉树是否为二叉排序树,可以使用中序遍历的方法。中序遍历按照从小到大的顺序输出二叉树的节点。如果遍历的结果是一个递增的序列,则该二叉树是二叉排序树。现在我将给出一个判断二叉树是否为二叉排序树的算法:
1. 定义一个函数IsBST,参数为二叉树T,返回值为1表示是二叉排序树,返回值为0表示不是。
2. 在IsBST函数中,首先定义两个标记flag1和flag2,用于标记左子树和右子树是否存在。如果T的左子树存在,则将flag1设置为1。如果T的右子树存在,则将flag2设置为1。
3. 如果T的左子树存在,判断左子树是否满足二叉排序树的条件,即左子树中的最大节点的值小于T的值。如果不满足,则返回0,表示不是二叉排序树。
4. 如果T的右子树存在,判断右子树是否满足二叉排序树的条件,即右子树中的最小节点的值大于T的值。如果不满足,则返回0,表示不是二叉排序树。
5. 如果flag1为1且左子树不是二叉排序树,返回0,表示不是二叉排序树。如果flag2为1且右子树不是二叉排序树,返回0,表示不是二叉排序树。
6. 如果经过上述判断,左子树和右子树都是二叉排序树,则返回1,表示是二叉排序树。
这样,我们就可以使用IsBST函数来判断一个二叉树是否为二叉排序树了。
给定二叉树判断是否为二叉排序树代码
以下是判断二叉树是否为二叉排序树(BST)的代码,其中假设二叉树中不包含重复的节点值:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_bst(root):
def dfs(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
if node.val <= lower or node.val >= upper:
return False
return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper)
return dfs(root)
```
该算法使用深度优先搜索(DFS)遍历二叉树,同时维护每个节点的上下界,判断每个节点是否在其对应的上下界范围内。如果二叉树中的所有节点都满足该条件,则该二叉树为二叉排序树。
注意,该算法的时间复杂度为O(n),其中n为二叉树中的节点数。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)