数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
时尚研究
法律研究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
更新于： 30-Jul-2019
815 次浏览
广告