数据结构
网络
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 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
更新于: 30-7-2019
271 次浏览
广告