检查给定树是否为二叉搜索树的C ++程序
二进制搜索树是一种二进制树数据结构，其中我们具有3个属性
节点的二分搜索树的左侧子树仅包含键小于节点键的节点。
二叉搜索树节点的右子树仅包含键大于该节点的键的节点。
子树的左右树也必须都是二叉搜索树。
算法
Begin
function BSTUtill() If node is equals to NULL then
Returns 1.
If data of node is less than minimum or greater than
maximum data then
Return 0.
Traverse left and right sub-trees recursively.
End.范例程式码
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
struct n {
int d;
n* l;
n* r;
};
int BSTUtil(n* node, int min, int max);
int isBST(n* node) {
return(BSTUtil(node, INT_MIN, INT_MAX));
}
int BSTUtil(struct n* node, int min, int max) {
if (node==NULL)
return 1;
if (node->d < min || node->d > max)
return 0;
return BSTUtil(node->l, min, node->d - 1) && BSTUtil(node->r, node->d + 1, max);
}
n* newN(int d) {
n* nod = new n;
nod->d = d;
nod->l = NULL;
nod->r = NULL;
return nod;
}
int main() {
n *root = newN(7);
root->l = newN(6);
root->r = newN(10);
root->l->l = newN(2);
root->l->r = newN(4);
if (isBST(root))
cout<<"The Given Tree is a BST"<<endl;
else
cout<<"The Given Tree is not a BST"<<endl;
n *root1 = newN(10);
root1->l = newN(6);
root1->r = newN(11);
root1->l->l = newN(2);
root1->l->r = newN(7);
if (isBST(root1))
cout<<"The Given Tree is a BST"<<endl;
else
cout<<"The Given Tree is not a BST"<<endl;
return 0;
}输出结果
The Given Tree is not a BST The Given Tree is a BST
热门推荐
1 如何训练狗狗不叫
2 训练狗狗不叫
3 训练狗狗随行
4 怎么训练狗狗不叫
7 训练比熊狗狗教程
10 上海狗狗训练
11 怎么训练狗狗上厕所
12 训练狗狗趴下
13 狗狗服从训练
14 训练狗狗拒食
15 训练狗狗笑
16 训练狗狗大便
17 训练狗狗立
18 训练狗狗捡东西