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를 확인합니다. 메인 메소드는 트리를 생성하고 isBST() 메소드를 호출합니다. 이 메서드는 isBSTuntil() 메서드를 사용하여 왼쪽 및 오른쪽 자식이 BST 규칙을 따르는지, 형성된 하위 트리도 BST인지 확인합니다.