Elemen Terkecil ke-K
Pelajaran 12 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
Tantangan berikutnya menggunakan class AVLTree yang sudah selesai kamu buat, tersedia sebagai file terkunci. Setiap tantangan menyediakan file solution baru untuk menulis fungsi yang menggunakan tree tersebut.
Penelusuran inorder pada binary search tree mana pun (rotasi tidak mengubahnya) mengunjungi nilai dalam urutan terurut. Jadi, nilai terkecil ke-k cukup diambil dari elemen pada indeks k - 1 dalam penelusuran tersebut.
Tantangan
MudahTulis fungsi kthSmallest(tree, k) yang mengembalikan nilai terkecil ke-k dalam tree (indeks dimulai dari 1). Kamu boleh mengasumsikan bahwa k valid.
Coba sendiri
#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;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
3Tantangan Latihan
Elemen Terkecil ke-KJumlah RentangLeluhur Bersama TerendahPenelusuran Berdasarkan Urutan LevelPenerus Suatu NilaiLatihan sendiri: Compiler C online