试写一个判别给定工叉树是否为二叉排序树的算法,设此二叉树以二叉链 表作存储结构。且树中结点的关键字均不同。
时间: 2024-03-26 07:41:43 浏览: 16
判别一棵二叉树是否为二叉排序树的算法如下:
1. 对于一棵二叉树来说,如果它为空,则它是一棵二叉排序树,否则进行第2步。
2. 检查左子树是否为二叉排序树,如果是,则进行第3步,否则返回false。
3. 检查右子树是否为二叉排序树,如果是,则进行第4步,否则返回false。
4. 检查根节点的值是否大于左子树中最大的值,并且小于右子树中最小的值,如果是,则返回true,否则返回false。
下面是该算法的 C++ 代码实现:
```c++
bool isBST(TreeNode* root, int minValue, int maxValue) {
if (root == nullptr) {
return true;
}
if (root->val <= minValue || root->val >= maxValue) {
return false;
}
return isBST(root->left, minValue, root->val) && isBST(root->right, root->val, maxValue);
}
bool isBST(TreeNode* root) {
return isBST(root, INT_MIN, INT_MAX);
}
```
其中,isBST 函数是递归实现的,用于判断给定二叉树是否为二叉排序树。isBST 函数的第一个参数是当前待判断的二叉树的根节点,第二个参数是当前节点所能取到的最小值,第三个参数是当前节点所能取到的最大值。函数的返回值为true表示当前二叉树是二叉排序树,返回false表示当前二叉树不是二叉排序树。
isBST 函数的实现过程如下:
1. 如果当前节点为空,则返回true。
2. 如果当前节点的值不在[minValue, maxValue]范围内,则返回false。
3. 递归检查左子树是否为二叉排序树,传入的最大值为当前节点的值。
4. 递归检查右子树是否为二叉排序树,传入的最小值为当前节点的值。
最终,isBST 函数的返回值即为当前二叉树是否为二叉排序树的判断结果。