Ein in der Sprache C geschriebenes Programm, um zu prüfen, ob ein Binärbaum ein Binary Search Tree (BST) ist.

Binärbaum ist eine Baumdatenstruktur, jeder Knoten hat zwei untergeordnete Knoten. Diese beiden untergeordneten Knoten werden als linker untergeordneter Knoten und rechter untergeordneter Knoten bezeichnet.

Binary Search Tree (BST) ist eine Baumstruktur, in der der linke Teilbaum Knoten mit einem Wert enthält, der kleiner als der Wurzelknoten ist, und der rechte Teilbaum Knoten mit einem Wert enthält, der größer als der Wurzelknoten ist.

Hier prüfen wir, ob ein Binärbaum BST ist:

Um dies zu überprüfen, müssen wir die BST-Bedingung im Binärbaum überprüfen. Für den Wurzelknoten sollte der Wert des linken untergeordneten Knotens kleiner sein als der Wert des Wurzelknotens und der Wert des rechten untergeordneten Knotens sollte größer als der Wert des Wurzelknotens sein. Diese Bedingung muss für alle Knoten erfüllt sein mit untergeordneten Knoten im Baum.

Programm zur Überprüfung, ob ein Binärbaum BST ist

#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;
}

Ausgabe

The given tree is a BST

Code-Erklärung

Der obige Code überprüft einen binären Suchbaum. Die Hauptmethode erstellt einen Baum und ruft die Methode isBST() auf. Diese Methode prüft, ob die linken und rechten untergeordneten Knoten den Regeln des binären Suchbaums folgen, und prüft mithilfe der Methode isBSTuntil(), ob der gebildete Teilbaum auch ein binärer Suchbaum ist.

Verfahren.

Das obige ist der detaillierte Inhalt vonEin in der Sprache C geschriebenes Programm, um zu prüfen, ob ein Binärbaum ein Binary Search Tree (BST) ist.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!