이진 트리가 BST(Binary Search Tree)인지 확인하기 위해 C 언어로 작성된 프로그램

이진 트리는 트리 데이터 구조이며 각 노드에는 두 개의 하위 노드가 있습니다. 이 두 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 합니다.

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

Output

The given tree is a BST

코드 설명

위 코드는 이진 검색 트리를 확인하는 코드입니다. 기본 메소드는 트리를 생성하고 isBST() 메소드를 호출합니다. 이 메서드는 왼쪽과 오른쪽 자식 노드가 이진 검색 트리 규칙을 따르는지 확인하고, isBSTuntil() 메서드를 사용하여 형성된 하위 트리도 이진 검색 트리인지 확인합니다.

방법.

위 내용은 이진 트리가 BST(Binary Search Tree)인지 확인하기 위해 C 언어로 작성된 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!