Un programme écrit en langage C pour vérifier si un arbre binaire est un arbre de recherche binaire (BST)

L'arbre binaire est une structure de données arborescente, chaque nœud a deux nœuds enfants. Ces deux nœuds enfants sont appelés nœud enfant gauche et nœud enfant droit.

L'arbre de recherche binaire (BST) est une structure arborescente dans laquelle le sous-arbre de gauche contient des nœuds avec une valeur inférieure au nœud racine et le sous-arbre de droite contient des nœuds avec une valeur supérieure au nœud racine.

Ici, nous allons vérifier si un arbre binaire est BST :

Pour vérifier cela, nous devons vérifier la condition BST sur l'arbre binaire. Pour le nœud racine, la valeur du nœud enfant gauche doit être inférieure à la valeur du nœud racine et la valeur du nœud enfant droit doit être supérieure à la valeur du nœud racine. Cette condition doit être remplie pour tous les nœuds. avec des nœuds enfants dans l’arborescence.

Programme pour vérifier si un arbre binaire est 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;
}

Output

The given tree is a BST

Explication du code

Le code ci-dessus vérifie un arbre de recherche binaire. La méthode main crée un arbre et appelle la méthode isBST(). Cette méthode vérifie si les nœuds enfants gauche et droit suivent les règles de l'arbre de recherche binaire et utilise la méthode isBSTuntil() pour vérifier si le sous-arbre formé est également un arbre de recherche binaire.

méthode.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!