C ++のBST（BSTの順序統計量）でk番目に小さい要素を検索します

二分探索木があり、入力として値Kがあるとすると、ツリー内でK番目に小さい要素を見つける必要があります。

したがって、入力が次のような場合

k =3の場合、出力は15になります。

これを解決するには、次の手順に従います-

• 関数find_kth_smallest（）を定義します。これは、root、count、k、

  を取ります。

• ルートがNULLの場合、-

  • NULLを返す

• left =find_kth_smallest（rootの左側、カウント、k）

• leftがNULLでない場合、-

  • 左に戻る

• （カウントを1つ増やします）

• countがkと同じ場合、-

  • ルートを返す

• find_kth_smallest（ルートの右、カウント、k）を返す

• メインの方法から、次のようにします-

• カウント：=0

• res =find_kth_smallest（root、count、k）

• resがNULLの場合、-

  • 表示が見つかりません

• それ以外の場合

  • 解像度の値を表示

例（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