Основной вопрос реализации дерева префикса

Question

Я внедрил основное дерево префикса или «три». Три состоит из узлов, подобных этим:

// pseudo-code
struct node {
    char c;
    collection<node> childnodes;
};

Скажите, я добавляю следующие слова в свой Trie: «Apple», «Ark» и «Cat». Теперь, когда я просматриваю префиксы, такие как «AP» и «CA» My Trie's «Bool содержит Pprefix (String Prefix)», правильно вернет True.

Теперь я внедряю метод «Bool Canceswholeword (String Word)», который вернет True для «Cat» и «Ark», но False для «App» (в приведенном выше примере).

Обычно у узлов в Trie есть какой -то флаг «Endofword»? Это помогло бы определить, на самом деле было введено целое слово, введенное в Trie, а не просто префикс.

Ваше здоровье!

Answer 1

Если вам нужно хранить как «приложение», так и «Apple», но не «Appl», то да, вам нужно что -то вроде endOfWord флаг.

В качестве альтернативы, вы можете вписать его в свой дизайн (иногда), имея два узла с одним и тем же символом. Таким образом, «AP» есть для детей: листовой узел «P» и внутренний узел «P» с ребенком «L».

Answer 2

Конец ключа обычно обозначается через листовой узел. Либо:

• Дочерние узлы пусты; или же
• У вас есть ветка, с одним префиксом ключа и некоторыми детскими узлами.

Ваш дизайн не имеет листового/пустого узла. Попробуйте указать это, например, NULL.