Lớp TrieNode

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

Mỗi nút trong trie là một đối tượng nhỏ chứa hai thông tin: các nút con bên dưới nó, tức là một bản đồ ánh xạ ký tự sang nút tiếp theo, và một cờ isEndOfWord cho biết đường đi từ nút gốc đến nút này có tạo thành một từ hoàn chỉnh đã được chèn hay không.

Đó là toàn bộ lớp. Không có giá trị, không có khóa: vị trí của một nút trong cây CHÍNH LÀ ý nghĩa của nó. Đường đi gồm các cạnh có nhãn c, a, t từ nút gốc sẽ đến nút mà ta đặt isEndOfWord = true khi chèn "cat".

Hãy bắt đầu bằng cách tạo lớp TrieNode này. Lớp Trie trong bài học tiếp theo sẽ dùng nó.

Thử thách

Dễ

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

Khởi tạo hai trường:

Đặt children thành một bản đồ rỗng (hoặc cấu trúc tương đương trong ngôn ngữ của bạn để ánh xạ ký tự sang nút).
Đặt isEndOfWord thành false.

Tự làm thử

#include <stdio.h>
#include "trienode.h"

int main() {
    TrieNode* n = TrieNode_new();
    printf("%s %s\n",
           TrieNode_childrenCount(n) == 0 ? "true" : "false",
           n->isEndOfWord ? "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 Trie Chè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