给定二叉树是否为排序二叉树的算法,二叉树以二叉链表作为存储结构
时间: 2023-11-14 13:16:54 浏览: 150
判断一棵二叉树是否为排序二叉树,需要满足以下条件:
1. 对于任意节点,其左子树所有节点的值均小于该节点的值。
2. 对于任意节点,其右子树所有节点的值均大于该节点的值。
3. 对于任意节点,其左子树和右子树也必须是排序二叉树。
因此,我们可以使用递归的方式来判断一棵二叉树是否为排序二叉树。具体实现可以按照以下步骤:
1. 如果二叉树为空或者只有一个节点,那么它一定是排序二叉树,直接返回 true。
2. 如果二叉树不为空,那么判断其左子树是否为排序二叉树,如果不是,则直接返回 false。
3. 如果其左子树是排序二叉树,那么判断其右子树是否为排序二叉树,如果不是,则直接返回 false。
4. 如果左右子树都是排序二叉树,那么判断当前节点的值是否大于左子树中的最大值,且小于右子树中的最小值,如果满足条件,那么返回 true,否则返回 false。
下面是一个示例代码实现:
```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 helper(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
if node.val <= lower or node.val >= upper:
return False
if not helper(node.left, lower, node.val):
return False
if not helper(node.right, node.val, upper):
return False
return True
return helper(root)
```
其中,helper 函数用来递归判断二叉树是否为排序二叉树。lower 和 upper 分别表示当前节点值的下界和上界,初始化为负无穷和正无穷。如果当前节点不在 [lower, upper] 的范围内,那么直接返回 False。否则,递归判断其左子树和右子树是否为排序二叉树,如果都是,那么返回 True。
阅读全文