노드와 범위로 구성된 이진 검색 트리가 주어지며 주어진 범위에 있는 노드의 수를 계산하고 결과를 표시하는 작업이 작업입니다.
BST(Binary Search Tree)는 모든 노드가 아래에 언급된 속성을 따르는 트리입니다 -
-
노드의 왼쪽 하위 트리에는 상위 노드의 키보다 작거나 같은 키가 있습니다.
-
노드의 오른쪽 하위 트리에는 상위 노드의 키보다 큰 키가 있습니다.
따라서 BST는 모든 하위 트리를 두 개의 세그먼트로 나눕니다. 왼쪽 하위 트리와 오른쪽 하위 트리는 다음과 같이 정의할 수 있습니다. -
left_subtree(키) ≤ 노드(키) ≤ right_subtree(키)
예
입력 -
범위:[11, 40]
출력 - 개수:5
설명 − [11, 40] 범위 사이의 노드 값은 14, 19, 27, 31, 35이므로 주어진 이진 탐색 트리에 총 5개의 노드가 있습니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
데이터, 왼쪽 포인터, 오른쪽 포인터를 포함하는 노드의 구조를 만들고 범위를 만듭니다.
-
사용자가 입력할 새 노드를 삽입하는 함수를 만듭니다.
-
주어진 범위에 있는 노드를 계산하는 다른 함수를 만듭니다.
-
루트가 NULL인지 확인한 다음 반환
-
이제 IF root->data =Start AND root->data =End를 확인한 다음 1을 반환합니다.
-
이제 IF root->data <=high &&root->data>=low를 확인한 다음 1 + getCount(root->left, End, Start) + recursively_call_count_function(root->right, End, Start)
을 반환합니다. -
Else If, root->data
right, End, Start) -
그렇지 않으면 recursively_call_count_function(root->left, End, Start)
을 반환합니다.
예
#include<iostream>
using namespace std;
// A BST node
struct node{
int data;
struct node* left, *right;
};
// Utility function to create new node
node *newNode(int data){
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int findcount(node *root, int low, int high){
// Base case
if (!root){
return 0;
}
if (root->data == high && root->data == low){
return 1;
}
// If current node is in range, then include it in count and
// recur for left and right children of it
if (root->data <= high && root->data >= low){
return 1 + findcount(root->left, low, high) +
findcount(root->right, low, high);
}
else if (root->data < low){
return findcount(root->right, low, high);
}
// Else recur for left child
else{
return findcount(root->left, low, high);
}
}
// main function
int main(){
// Let us construct the BST shown in the above figure
node *root = newNode(27);
root->left = newNode(14);
root->right = newNode(35);
root->left->left = newNode(10);
root->left->right = newNode(19);
root->right->left = newNode(31);
root->right->right = newNode(42);
int low = 10;
int high = 50;
cout << "Count of nodes between [" << low << ", " << high
<< "] is " << findcount(root, low, high);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 -
Count of nodes between [10, 50] is 7