对给定的二叉树,假设其中各结点的值均不相同,设计算法以判断该二叉树是否是二叉排序树。用C++语言写出算法。其中二叉树的结构为typedef struct lBNode { int data; struct lBNode *lChild, *rChild; }BiNode,*BiTree;
时间: 2024-03-16 14:47:42 浏览: 70
C++的二叉排序树算法
判断一个二叉树是否为二叉排序树,需要满足以下条件:
1. 左子树中所有结点的值均小于根节点的值;
2. 右子树中所有结点的值均大于根节点的值;
3. 左子树和右子树都必须是二叉排序树。
根据上述条件,可以设计如下的算法:
```c++
bool isBST(BiTree root, int min, int max) {
if (root == NULL) {
return true;
}
if (root->data < min || root->data > max) {
return false;
}
return isBST(root->lChild, min, root->data - 1) &&
isBST(root->rChild, root->data + 1, max);
}
bool isBinarySearchTree(BiTree root) {
return isBST(root, INT_MIN, INT_MAX);
}
```
上述算法中,isBST函数用于判断当前节点是否满足二叉排序树的条件,并递归判断左右子树是否也满足二叉排序树的条件。isBinarySearchTree函数则是用于判断整棵二叉树是否为二叉排序树。
其中,INT_MIN和INT_MAX分别为整型变量的最小值和最大值,用于限制根节点的值的范围。
阅读全文