Program yang ditulis dalam bahasa C untuk menyemak sama ada pokok binari ialah Pokok Carian Binari (BST)

Pokok binari ialah struktur data pokok, setiap nod mempunyai dua nod anak. Kedua-dua nod anak ini dipanggil nod anak kiri dan nod anak kanan.

Binary Search Tree (BST) ialah struktur pokok di mana subpokok kiri mengandungi nod dengan nilai kurang daripada nod akar dan subpokok kanan mengandungi nod dengan nilai lebih besar daripada nod akar.

Di sini, kami akan menyemak sama ada pokok binari adalah BST:

Untuk menyemak ini, kita perlu menyemak keadaan BST pada pokok binari. Untuk nod akar, nilai nod anak kiri hendaklah kurang daripada nilai nod akar, dan nilai nod anak kanan hendaklah lebih besar daripada nilai nod akar dengan nod anak dalam pokok.

Program untuk menyemak sama ada pokok binari adalah 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

Penjelasan kod

Kod di atas menyemak pepohon carian binari. Kaedah utama mencipta pokok dan memanggil kaedah isBST(). Kaedah ini menyemak sama ada nod anak kiri dan kanan mengikut peraturan pepohon carian binari, dan menggunakan kaedah isBSTuntil() untuk menyemak sama ada subpokok yang terbentuk juga merupakan pepohon carian binari.

kaedah.

Atas ialah kandungan terperinci Program yang ditulis dalam bahasa C untuk menyemak sama ada pokok binari ialah Pokok Carian Binari (BST). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!