Chèn

Bài học 5 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.

Để chèn một từ vào trie, hãy đi từ nút gốc xuống, mỗi lần một ký tự. Với mỗi ký tự trong từ: nếu nút hiện tại không có nút con tương ứng với ký tự đó, hãy tạo một TrieNode mới và gắn nó vào. Dù thế nào, hãy chuyển sang nút con đó rồi tiếp tục với ký tự tiếp theo.

Khi đến cuối từ, hãy đánh dấu nút bạn dừng lại bằng isEndOfWord = true. Cờ này giúp phân biệt một từ thực sự được lưu với một đường đi chỉ tồn tại vì nó là tiền tố của một từ khác.

Chèn "cat" rồi đến "car" sẽ dùng chung đường đi c -> a và chỉ rẽ nhánh ở ký tự thứ ba. Việc dùng chung đường đi giúp trie tiết kiệm không gian khi lưu từ điển.

Thử thách

Dễ

Thêm phương thức insert vào lớp Trie.

Phương thức nhận một chuỗi word và lưu chuỗi đó vào trie:

Bắt đầu từ root. Với mỗi ký tự c trong word, nếu nút hiện tại chưa có nút con tương ứng với c, hãy thêm một TrieNode mới tại đó.
Chuyển sang nút con đó rồi tiếp tục.
Sau ký tự cuối cùng, đánh dấu isEndOfWord của nút cuối cùng là true.

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"); }
        if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
        if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
    }
    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 TrieNode Lớp TrieChènTì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