Phần tử kế tiếp theo giá trị
Bài học 16 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.
Nút kế tiếp theo thứ tự trung thứ tự của một giá trị là giá trị nhỏ nhất trong cây lớn hơn giá trị đó, tức là giá trị đứng ngay sau nó trong danh sách đã sắp xếp. Nếu giá trị đó là giá trị lớn nhất trong cây, nó không có nút kế tiếp.
Bạn có thể tìm nút này chỉ qua một lượt mà không cần sắp xếp: đi xuống từ nút gốc, mỗi khi đi sang phải qua một giá trị quá nhỏ, hãy nhớ nút gần nhất mà bạn đã đi sang trái từ đó làm ứng viên tốt nhất cho đến lúc này.
Thử thách
DễViết một hàm (function) successor(tree, value) trả về giá trị nhỏ nhất trong cây lớn hơn value, hoặc -1 nếu không có giá trị nào như vậy.
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 = successor(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