Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 주어진 범위에 있는 BST 하위 트리 계산

<시간/>

입력으로 이진 검색 트리가 제공됩니다. 목표는 BST에서 시작과 끝 범위 사이에 노드 값이 있는 하위 트리의 수를 찾는 것입니다. 시작이 5이고 끝이 50이면 모든 노드의 가중치가>=5 및 <=50인 BST의 하위 트리를 셉니다.

입력 - 아래에 주어진 트리 - 범위 [ 3-6 ]

C++에서 주어진 범위에 있는 BST 하위 트리 계산

출력 − 범위에 있는 나무의 수 − 2

설명 − 노드 4 및 6에만 해당. 하위 트리( NULL )는 3-6 사이에 있습니다.

입력 - 아래에 주어진 트리:범위 [ 12-20 ]

C++에서 주어진 범위에 있는 BST 하위 트리 계산

출력 − 범위에 있는 나무의 수 − 3

설명 − 노드 16, 14 및 20의 경우. 하위 트리는 12-20 사이에 있습니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

  • Btreenode 구조는 정보 부분을 정수로 사용하고 하위 트리를 가리키는 왼쪽 및 오른쪽 포인터를 자체 참조하는 트리 노드를 만드는 데 사용됩니다.

  • 함수 Btreenode* insert(int data)는 데이터를 정보로, 왼쪽 및 오른쪽 포인터를 NULL로 하여 노드를 생성하는 데 사용됩니다.

  • 주어진 구조에 대해 호출하여 삽입 함수를 사용하여 BST를 만듭니다. 루트 노드의 오른쪽( root->right =insert(70); )과 루트의 왼쪽( root->left =insert(30); )에 노드를 추가하려면

  • 변수 l과 h는 범위의 최소값과 최대값을 저장하는 데 사용됩니다.

  • 변수 개수는 l과 h 사이의 범위에 있는 트리 내부의 BST 개수를 저장합니다. 처음에는 0.

  • 함수 getBtreeCount(Btreenode* root, int low, int high, int* count)는 BST의 루트, 범위의 왼쪽 및 오른쪽 경계 및 count 주소를 매개변수로 취하고 각 재귀 호출에 대한 count 값을 업데이트합니다.

  • 현재 루트의 경우 NULL인지 확인하고, 그렇다면 트리의 일부가 아니므로 1을 반환합니다.

  • 현재 노드의 경우 모든 왼쪽 및 오른쪽 하위 트리 노드가 지정된 범위에 있는지 확인합니다. 재귀 호출로 getBtreeCount(root->left, low, high, count); andgetBtreeCount(루트->오른쪽, 낮음, 높음, 개수);

  • 두 하위 트리가 범위 사이에 있고 현재 노드도 범위에 있으면 현재 노드에 뿌리를 둔 트리가 범위 내에 있습니다. 증분 카운트. if (left &&right &&root->info>=low &&root->info <=high) 및 ++*count; 1을 반환합니다.

  • 마지막 카운트는 모든 하위 트리의 카운트로 업데이트된 값을 갖습니다.

  • 결과를 count로 인쇄합니다.

예

#include <bits/stdc++.h>
using namespace std;
// A BST node
struct Btreenode {
   int info;
   Btreenode *left, *right;
};
int getBtreeCount(Btreenode* root, int low, int high, int* count){
   // Base case
   if (root == NULL)
      return 1;
      int left = getBtreeCount(root->left, low, high, count);
      int right = getBtreeCount(root->right, low, high, count);
      if (left && right && root->info >= low && root->info <= high) {
         ++*count;
      return 1;
   }
   return 0;
}
Btreenode* insert(int data){
   Btreenode* temp = new Btreenode;
   temp->info = data;
   temp->left = temp->right = NULL;
   return (temp);
}
int main(){
      /* BST for input
         50
        / \
       30 70
      / \ / \
20 40 60 80 */
   Btreenode* root = insert(50);
   root->left = insert(30);
   root->right = insert(70);
   root->left->left = insert(20);
   root->left->right= insert(40);
   root->right->left = insert(60);
   root->right->right = insert(80);
   int l = 10;
   int h = 50;
   int count=0;
   getBtreeCount(root, l, h, &count);
   cout << "Count of subtrees lying in range: " <<count;
   return 0;
}

출력

Count of subtrees lying in range: 3