试编写一个算法,判别给定的二叉树是否是二叉搜索树
时间: 2023-04-16 18:05:16 浏览: 337
写一算法,判断一棵二叉树是否是一棵二叉排序树。
判断二叉树是否为二叉搜索树的算法如下:
1. 对于空树,返回 true。
2. 对于非空树,判断其左子树是否为二叉搜索树,右子树是否为二叉搜索树。
3. 对于左子树,判断其最大值是否小于当前节点的值,对于右子树,判断其最小值是否大于当前节点的值。
4. 如果左子树和右子树都是二叉搜索树,并且满足上述条件,则当前树为二叉搜索树,返回 true。
5. 如果左子树或右子树不是二叉搜索树,或者不满足上述条件,则当前树不是二叉搜索树,返回 false。
算法的时间复杂度为 O(n),其中 n 为二叉树的节点数。
阅读全文