입력으로 바이너리 트리가 제공됩니다. 목표는 내부에 하위 트리로 존재하는 이진 탐색 트리(BST)의 수를 찾는 것입니다. BST는 왼쪽 자식이 루트보다 작고 오른쪽 자식이 루트보다 큰 이진 트리입니다.
예를 들어
입력
값을 입력한 후 생성될 트리는 다음과 같습니다. -
출력
Count the Number of Binary Search Trees present in a Binary Tree are: 2
설명
우리는 이진 트리를 형성하는 데 사용되는 정수 값의 배열이 제공되며 그 안에 이진 검색 트리가 있는지 여부를 확인할 것입니다. 모든 루트 노드는 이진 탐색 트리를 나타내므로 주어진 이진 트리에서 다른 이진 탐색 트리가 존재하지 않음을 알 수 있으므로 개수는 이진 트리의 총 리프 노드 수인 2입니다.
입력
값을 입력한 후 생성될 트리는 다음과 같습니다. -
출력
Count the Number of Binary Search Trees present in a Binary Tree are: 6
설명
우리는 이진 트리를 형성하는 데 사용되는 정수 값의 배열이 제공되며 그 안에 이진 검색 트리가 있는지 여부를 확인할 것입니다. 모든 루트 노드는 이진 탐색 트리를 나타내므로 주어진 이진 트리에서 BST를 형성하는 4개의 리프 노드와 2개의 하위 트리가 있음을 알 수 있으므로 개수는 6입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -
이 접근 방식에서 우리는 노드 N의 왼쪽 서브트리에서 노드의 가장 큰 값을 찾아 N보다 작은지 확인합니다. 또한 노드 N의 오른쪽 서브트리에서 가장 작은 값을 찾아 보다 큰지 확인합니다. N. 참이면 BST입니다. 이진 트리를 상향식으로 순회하고 위의 조건을 확인하고 BST의 수를 증가시킵니다.
-
모든 node_data의 노드에는 존재하는 BST의 수, 해당 트리의 최대값, 최소값, 부울 하위 트리가 BST인 경우 참과 같은 정보가 포함됩니다.
-
BST_present(struct tree_node* parent) 함수는 부모에 뿌리를 둔 바이너리 트리 내부에 존재하는 BST의 개수를 찾습니다.
-
부모가 NULL이면 { 0, min, max, true }를 반환합니다. 여기서 min은 INT-MIN이고 max는 INT_MAX입니다.
-
왼쪽 및 오른쪽 자식이 null이면 { 1, parent->data, parent->data, true }
를 반환합니다. -
node_data 왼쪽 설정 =BST_present(parent->left); 및 node_data Right =BST_present(parent->right);
-
노드 n1을 선택하고 n1.lowest =min(parent->data, (min(Left.lowest,Right.lowest)))를 오른쪽 하위 트리에서 가장 낮은 값으로 설정합니다.
-
설정 n1.highest =max(parent->data, (max(Left.highest, Right.highest))); 왼쪽 하위 트리에서 가장 높습니다.
-
if(Left.check &&Right.check &&parent−>data> Left.highest &&parent−>data
-
bst 수를 n1.total_bst =1 + Left.total_bst + Right.total_bst로 늘리십시오.
-
그렇지 않으면 n1.check =false로 설정하고 n1.total_bst =Left.total_bst +Right.total_bst로 계산합니다.
-
끝에 n1을 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
struct tree_node{
struct tree_node* left;
struct tree_node* right;
int data;
tree_node(int data){
this−>data = data;
this−>left = NULL;
this−>right = NULL;
}
};
struct node_data{
int total_bst;
int highest, lowest;
bool check;
};
node_data BST_present(struct tree_node* parent){
if(parent == NULL){
int max = INT_MAX;
int min = INT_MIN;
return { 0, min, max, true };
}
if(parent−>left == NULL){
if(parent−>right == NULL){
return { 1, parent−>data, parent−>data, true };
}
}
node_data Left = BST_present(parent−>left);
node_data Right = BST_present(parent−>right);
node_data n1;
n1.lowest = min(parent−>data, (min(Left.lowest, Right.lowest)));
n1.highest = max(parent−>data, (max(Left.highest, Right.highest)));
if(Left.check && Right.check && parent−>data > Left.highest && parent−>data < Right.lowest){
n1.check = true;
n1.total_bst = 1 + Left.total_bst + Right.total_bst;
} else{
n1.check = false;
n1.total_bst = Left.total_bst + Right.total_bst;
}
return n1;
}
int main(){
struct tree_node* root = new tree_node(3);
root−>left = new tree_node(7);
root−>right = new tree_node(4);
root−>left−>left = new tree_node(5);
root−>right−>right = new tree_node(1);
root−>left−>left−>left = new tree_node(10);
cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst;
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count the Number of Binary Search Trees present in a Binary Tree are: 2