所以,我试图阅读一个 Trie,对我来说是一种相对较新的数据结构。在我读到的任何地方,trie 中的每个节点都将包含一个整数变量,该变量将标记一个单词的结尾,并且还包含 26 个指针,每个指针指向较低级别的节点(假设单词只包含小字母字符)。
现在我面临的问题是,无论我在哪里看到/阅读实现,他们都会用一个字符标记节点。就像在这种情况下:
http://community.topcoder.com/i/education/alg_tries.png
但就我对 Trie 的理解而言,我相信每一条边都应该被标记为一个字符。虽然,我知道我们没有边缘的数据结构,只有节点。但是标记边缘不是更正确吗?
另外,这是我实现插入的算法。如果您发现它有问题,请告诉我。
struct trie
{
int val;
trie* aplha[26];
}
trie* insert (trie *root, char *inp)
{
if (*input == '\0')
return root;
if (root == NULL)
{
root = (trie *) malloc(sizeof(trie));
int i = 0;
for (i=0;i<26;i++)
root->alpha[i] = NULL;
}
temp = *input - 'a';
root->alpha[temp] = insert (root->alpha[temp],input+1);
if (*(input+1)=='\0')
root->val = 1;
return root;
}
我对如何实现删除感到困惑。如果可以的话,请帮助我删除算法。