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 đó.
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
3Thử thách luyện tập
Phần tử nhỏ thứ kTổng trong phạm viTổ tiên chung thấp nhấtDuyệt theo thứ tự từng mứcPhần tử kế tiếp theo giá trịTự luyện tập: Trình biên dịch C online