用于检查二叉树是否为BST的C ++程序
二进制搜索树是一种二进制树数据结构，其中我们具有3个属性-
节点的二分搜索树的左侧子树仅包含键小于节点键的节点。
二叉搜索树节点的右子树仅包含键大于该节点的键的节点。
子树的左侧和右侧也必须都是二叉搜索树。
算法
Begin
function BSTUtill() If node is equals to NULL then
Return 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 Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary 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 Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary Tree is not a BST"<<endl;
return 0;
}输出结果
The Given Binary Tree is not a BST The Given Binary Tree is a BST
热门推荐
10 祝孙辈生日祝福语简短
11 恋人跨年祝福语大全简短
12 考大学敬酒简短祝福语
13 开工投产大吉祝福语 简短
14 偶然结婚祝福语朋友简短
15 感谢学长学姐祝福语简短
16 戏精的祝福语简短
17 我要结婚祝福语简短
18 婚前女儿生日祝福语简短