Lớp Trie

Bài học 4 trên 14 trong khóa học Cây tiền tố, chuỗi cấu trúc dữ liệu số 8 của Coddy.

Bản thân lớp Trie rất gọn: lớp này chỉ có một trường là root, thuộc kiểu TrieNode. Mỗi lần thêm, tìm kiếm hoặc tra cứu đều bắt đầu từ nút gốc này rồi đi xuống cây, từng ký tự một.

Hàm khởi tạo tạo một TrieNode mới làm nút gốc. Nút gốc này chưa có nút con và chưa được đánh dấu là điểm kết thúc của từ nào, vì vậy trie bắt đầu ở trạng thái rỗng. Các phương thức chúng ta thêm vào trong những bài học tiếp theo sẽ tạo các nút con từ nút này.

Thử thách

Dễ

Viết một lớp Trie có hàm khởi tạo (constructor) không nhận đầu vào.

Khởi tạo một thuộc tính duy nhất root làm một TrieNode mới (dùng lớp bạn đã viết trong bài học trước).

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"

int main() {
    Trie t;
    Trie_init(&t);
    char line[1024];
    while (fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        char* cmd = strtok(line, " \t");
        if (!cmd) continue;
        if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
    }
    return 0;
}

Tất cả bài học trong Cây tiền tố, chuỗi cấu trúc dữ liệu số 8

1Giới thiệu

Giới thiệu Trie là gì?

2Dự án Trie

Lớp TrieNodeLớp TrieChèn Tìm kiếm Bắt đầu bằng Xóa Số lượng từ

3Thử thách luyện tập

Tiền tố chung dài nhất Đếm từ có tiền tố Tự động hoàn thành Từ dài nhất trong từ điển Tách từ

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