设计算法,判定给定的二叉树是否是二叉排序树,设此二叉树以二叉链表作为存储结构(c++)
时间: 2023-11-18 15:09:53 浏览: 155
写一算法,判断一棵二叉树是否是一棵二叉排序树。
可以使用递归方式来判断给定的二叉树是否是二叉排序树。对于二叉排序树来说,左子树的所有节点都小于根节点,右子树的所有节点都大于根节点。
具体实现如下:
```c++
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 判断二叉树是否是二叉排序树
bool isBST(TreeNode* root) {
if (!root) {
return true;
}
if (root->left && root->left->val > root->val) {
return false;
}
if (root->right && root->right->val < root->val) {
return false;
}
return isBST(root->left) && isBST(root->right);
}
```
该算法的时间复杂度为O(n),其中n为二叉树中节点的个数。
阅读全文