Trie tree 有时被称为 (digital tree) 或(radix tree https://en.wikipedia.org/wiki/Radix_tree or prefix tree).
可能是编译器问题, 我的实现方法用 gcc 编译器, debug 没问题, 但一 run 就有问题...
Debug output:
Starting debugger: C:\TDM-GCC-64\bin\gdb.exe -nx -fullname -quiet -args E:/CodeBlocks_C++Projects/NYOJ/bin/Debug/NYOJ.exe
- done
- Setting breakpoints
- Debugger name and version: GNU gdb (GDB) 7.9.1
Child process PID: 208
- [Inferior 1 (process 208) exited normally]
- Debugger finished with status 0
弄了很久, 还以为是我哪里指针处理没做好, 但最后不管怎么想都觉得逻辑都没问题, 于是换 VS,run 成功了, 而且结果是正确的.
原理很简单, 没什么好说的, 看 wiki 上的图就能够明白什么是前缀树, 以及如何设计这样的数据结构了. 遍历的思路用的是二叉树的后序遍历思想, 这里用循环建立了 26 个子递归, 实际上原理是一样的. ps: 其实成员 letter 没有必要有...
- code:
- #include "stdafx.h"
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define SIZE 26
- #define INDEX(c) ((c) - 'a')
- #define ARR_SIZE(strs) (sizeof((strs))/sizeof(strs[0]))
- #define FOR(i, range, node) for (i = 0; i <range; i++) node->children[i] = NULL
- typedef struct BaseNode {
- struct BaseNode* children[SIZE];
- char letter;
- char*s;
- }trie;
- trie*init()
- {
- int i;
- trie*root = (trie*)malloc(sizeof(trie));
- root->letter = 0;
- FOR(i, SIZE, root);
- root->s = NULL;
- return root;
- }
- trie*insert(trie*root, char str[])
- {
- trie*node = root;
- int i, j;
- for (i = 0; node->children[INDEX(str[i])] != NULL; i++)
- {
- node = node->children[INDEX(str[i])];
- }
- while (i <(int)strlen(str))
- {
- trie*temp = (trie*)malloc(sizeof(trie));
- temp->letter = str[i];
- FOR(j, SIZE, temp);
- temp->s = NULL;
- if (i + 1 == (int)strlen(str))
- temp->s = str;
- node->children[INDEX(str[i])] = temp;
- node = temp;
- i++;
- }
- FOR(j, SIZE, node);
- return root;
- }
- trie*search(trie*root, char str[])
- {
- trie*node = root;
- for (int i = 0; i <(int)strlen(str); i++)
- {
- if (node != NULL)
- {
- node = node->children[INDEX(str[i])];
- // printf("%c ->", node->letter);
- }
- else
- break;
- }
- return node;
- }
- bool remove_helper(trie*node)
- {
- for (int i = 0; i <SIZE; i++)
- {
- if (node->children[i] != NULL)
- return true;
- }
- return false;
- }
- void remove(trie**node, char*str)
- {
- if (*node != NULL)
- {
- char c = *str;
- ++str;
- remove(&(*node)->children[INDEX(c)], str);
- if (!remove_helper(*node))
- {
- free(*node);
- *node = NULL;
- }
- }
- }
- void show(trie*node)
- {
- if (node != NULL)
- {
- for (int i = 0; i <SIZE; i++)
- {
- show(node->children[i]);
- }
- printf("%s\n", node->s);
- }
- }
- void destory(trie*node)
- {
- if (node != NULL)
- {
- for (int i = 0; i <SIZE; i++)
- {
- destory(node->children[i]);
- }
- free(node);
- node = NULL;
- }
- }
- int main()
- {
- char strs[][12] = { "tea","eat","engineer","table","profile" };
- trie*root;
- root = init();
- for (int i = 0; i < (int)ARR_SIZE(strs); i++)
- {
- root = insert(root, strs[i]);
- }
- show(root);
- remove(&root, strs[0]);
- // trie*node = search(root, strs[0]);
- show(root);
- destory(root);
- getchar();
- return 0;
- }
- Output:
- eat
- engineer
- profile
- table
- tea
- (null)
- (null)
- (null)
- eat
- engineer
- profile
- table
参考:
- https://github.com/darkchii/cosmos/blob/master/code/data_structures/src/tree/tree/trie/trie.c
- https://en.wikipedia.org/wiki/Trie
- Trie tree(字典树)
来源: http://www.bubuko.com/infodetail-2620507.html