一个检查二进制树是否在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()方法。此方法使用该方法检查左孩子和右孩子是否都遵循BST规则，并且所形成的子树也是BST的子树isBSTuntil()。