Tổ tiên chung thấp nhất
Bài học 14 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.
Tổ tiên chung thấp nhất của hai giá trị là nút sâu nhất có chứa cả hai giá trị trong cây con của nó. Trong cây tìm kiếm nhị phân, bạn có thể tìm nút này mà không cần so sánh trực tiếp các cây con: bắt đầu từ nút gốc, nếu cả hai giá trị đều nhỏ hơn nút hiện tại thì đáp án nằm đâu đó trong cây con bên trái; nếu cả hai đều lớn hơn thì đáp án nằm trong cây con bên phải.
Khi hai giá trị nằm ở hai phía khác nhau (hoặc một trong hai bằng nút hiện tại), bạn đã tìm thấy điểm phân chia: nút đó là tổ tiên chung thấp nhất.
Thử thách
DễViết một hàm (function) lca(tree, p, q) trả về giá trị của tổ tiên chung thấp nhất của p và q. Bạn có thể giả định rằng cả hai giá trị đều có trong câ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 p1 = atoi(strtok(NULL, " \n"));
int result = lca(tree, p0, p1);
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