K. En Küçük Eleman

Coddy'nin AVL Tree - Veri Yapıları Serisi #10 kursunda ders 12 / 16.

Sıradaki zorluklar, az önce oluşturduğunuz ve size kilitli bir dosya olarak sunulan tamamlanmış AVLTree sınıfını kullanır. Her zorluk, ağacı KULLANAN bir fonksiyon yazdığınız yeni bir solution dosyasıyla birlikte gelir.

Herhangi bir ikili arama ağacının (rotasyonlar bunu değiştirmez) in-order dolaşımı, değerleri sıralı düzende ziyaret eder. Bu nedenle k. en küçük değer, basitçe bu dolaşımın k - 1 dizinindeki öğesidir.

Görev

Kolay

Ağaçtaki (1 tabanlı dizinlenmiş) en küçük k. değeri döndüren bir kthSmallest(tree, k) fonksiyonu yazın. k değerinin geçerli olduğunu varsayabilirsiniz.

Kendin dene

#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;
}