数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C语言程序：检查二叉树是否为二叉搜索树 (BST)
二叉树是一种树形数据结构，其中每个节点有两个子节点。这两个子节点分别称为左子节点和右子节点。
BST（二叉搜索树）是一种树形结构，其中左子树包含小于根节点的值，右子树包含大于根节点的值。
在这里，我们将检查一个二叉树是否为BST。
要检查这一点，我们必须检查二叉树上的BST条件。对于根节点，检查左子节点是否小于根节点，右子节点是否大于根节点，这适用于树中所有存在子节点的节点。
检查二叉树是否为BST的程序
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int isBSTUtil(node* node, int min, int max);
int isBST(node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(node* node, int min, int max) {
if (node==NULL)
return 1;
if (node->data < min || node->data > max)
return 0;
return
isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max);
}
int main() {
node *root = new node(8);
root->left = new node(3);
root->right = new node(10);
root->left->left = new node(1);
root->left->right = new node(6);
if(isBST(root))
cout<<"The given tree is a BST";
else
cout<<"The given tree is Not a BST";
return 0;
}输出
The given tree is a BST
代码解释
上面的代码检查是否为BST。main方法创建一棵树并调用isBST()方法。此方法使用isBSTuntil()方法检查左子节点和右子节点是否遵循BST规则，以及是否也形成了BST的子树。
更新于：2019年8月7日
浏览量：271
广告