k番目に小さい要素

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 12/16。

次のチャレンジでは、先ほど作成した完成済みの AVLTree クラスを使用します。これは編集不可のファイルとして提供されます。各チャレンジには新しい solution ファイルが含まれており、そこでツリーを使用する関数を記述します。

二分探索木の通りがけ順（in-order）の巡回（回転によってこれが変わることはありません）では、値はソートされた順序で訪問されます。したがって、k番目に小さい値は、その巡回のインデックス k - 1 にある要素にすぎません。

チャレンジ

簡単

ツリー内で k 番目に小さい値（1始まり）を返す関数 kthSmallest(tree, k) を作成してください。k は有効な値であると仮定して構いません。

自分で試してみよう

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int result = kthSmallest(tree, p0);
    printf("%d\n", result);
    return 0;
}