C++에서 BST(BST의 순서 통계)에서 k번째 가장 작은 요소 찾기

이진 검색 트리와 값 K가 입력으로 있다고 가정하면 트리에서 K 번째로 작은 요소를 찾아야 합니다.

따라서 입력이 다음과 같으면

k =3이면 출력은 15가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• find_kth_smallest() 함수를 정의합니다. 이것은 root, count, k,

  를 취합니다.

• 루트가 NULL이면 -

  • NULL 반환

• left =find_kth_smallest(루트의 왼쪽, 개수, k)

• 왼쪽이 NULL이 아니면 -

  • 왼쪽으로 돌아가기

• (1씩 증가)

• count가 k와 같으면 -

  • 루트 반환

• return find_kth_smallest(루트의 오른쪽, 개수, k)

• 기본 방법에서 다음을 수행하십시오 -

• 개수 :=0

• res =find_kth_smallest(루트, 개수, k)

• res가 NULL이면 -

  • 디스플레이를 찾을 수 없음

• 그렇지 않으면

  • res의 표시 값

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <iostream>
using namespace std;
struct TreeNode {
   int val;
   TreeNode *left, *right;
   TreeNode(int x) {
      val = x;
      left = right = NULL;
   }
};
TreeNode* find_kth_smallest(TreeNode* root, int &count, int k) {
   if (root == NULL)
      return NULL;
   TreeNode* left = find_kth_smallest(root->left, count, k);
   if (left != NULL)
      return left;
   count++;
   if (count == k)
      return root;
   return find_kth_smallest(root->right, count, k);
}
void kth_smallest(TreeNode* root, int k) {
   int count = 0;
   TreeNode* res = find_kth_smallest(root, count, k);
   if (res == NULL)
      cout << "Not found";
   else
      cout << res->val;
}
int main() {
   TreeNode* root = new TreeNode(25);
   root->left = new TreeNode(13);
   root->right = new TreeNode(27);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(17);
   root->left->right->left = new TreeNode(15);
   root->left->right->right = new TreeNode(19);
   int k = 3;
   kth_smallest(root, k);
}

입력

TreeNode* root = new TreeNode(25); root->left = new TreeNode(13);
root->right = new TreeNode(27); root->left->left = new
TreeNode(9); root->left->right = new TreeNode(17); root- >left->right->left = new TreeNode(15); root->left->right->right = new TreeNode(19); k = 3

출력

15