Menu
CoddyTech

Phần tử nhỏ thứ k

Bài học 12 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.

Các thử thách tiếp theo dùng lớp AVLTree đã hoàn thiện mà bạn vừa xây dựng, được cung cấp dưới dạng tệp chỉ đọc. Mỗi thử thách có một tệp solution mới, nơi bạn viết một hàm sử dụng cây.

Phép duyệt theo thứ tự giữa của mọi cây tìm kiếm nhị phân (các phép xoay không làm thay đổi điều này) sẽ thăm các giá trị theo thứ tự đã sắp xếp. Vì vậy, giá trị nhỏ thứ k chính là phần tử ở chỉ số k - 1 trong lần duyệt đó.

challenge icon

Thử thách

Dễ

Viết một hàm kthSmallest(tree, k) trả về giá trị nhỏ thứ k trong cây (đánh chỉ số từ 1). Bạn có thể giả định rằng k hợp lệ.

Tự làm thử

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

Tất cả bài học trong Cây AVL, chuỗi cấu trúc dữ liệu #10

Tự luyện tập: Trình biên dịch C online