Lớp nút
Bài học 3 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.
Mỗi nút trong cây lưu bốn thông tin: value của nó, các con trỏ đến nút con left và right, cùng với height của chính nó. Một nút mới hoàn toàn là nút lá, nên chiều cao ban đầu là 1 và nó chưa có nút con.
Lưu chiều cao trực tiếp trên nút, thay vì tính lại bằng cách duyệt qua cây mỗi lần, giúp mọi thao tác sau này kiểm tra độ cân bằng trong thời gian hằng số.
Thử thách
Người mớiViết một lớp Node có hàm khởi tạo nhận một value và lưu giá trị đó, đặt left và right thành null, rồi đặt height thành 1.
Tự làm thử
#include <stdio.h>
#include "node.h"
int main(void) {
char line[256];
while (fgets(line, sizeof(line), stdin) != NULL) {
int v;
if (sscanf(line, "%d", &v) != 1) {
continue;
}
Node* n = Node_create(v);
if (n->left == NULL && n->right == NULL) {
printf("%d %d null null\n", n->value, n->height);
} else if (n->left == NULL) {
printf("%d %d null %d\n", n->value, n->height, n->right->value);
} else if (n->right == NULL) {
printf("%d %d %d null\n", n->value, n->height, n->left->value);
} else {
printf("%d %d %d %d\n", n->value, n->height, n->left->value, n->right->value);
}
}
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