Trie树_字典树(字符串排序)简介及实现(4)
int count = 0;
trie->output(trie->root, str, count);
for(int i = 0; i < 12; i++)
cout<<str[i]<<endl;
return 0;
}
Node::Node()
{
count = 0;
for(int i = 0; i < NUM; i++)
char_arr[i] = NULL;
current_str = new char[100];
current_str[0] = '\0';
}
Trie::Trie()
{
root = new Node();
}
void Trie::insert(char* str)
{
int i = 0;
Node* parent = root;
//将str[i]插入到trie树中
while(str[i] != '\0')
{
//如果包含str[i]的分支存在,则新建此分支
if(parent->char_arr[str[i] - 'a'] == NULL)
{
parent->char_arr[str[i] - 'a'] = new Node();
//将父节点中的字符串添加到当前节点的字符串中
strcat(parent->char_arr[str[i] - 'a']->current_str, parent->current_str);
char str_tmp[2];
str_tmp[0] = str[i];
str_tmp[1] = '\0';
//将str[i]添加到当前节点的字符串中
strcat(parent->char_arr[str[i] - 'a']->current_str, str_tmp);
parent = parent->char_arr[str[i] - 'a'];
}
else
{
parent = parent->char_arr[str[i] - 'a'];
}
i++;
}
parent->count++;
}
//采用前序遍历
void Trie::output(Node* &node, char** str, int& count)
{
if(node != NULL)
{
if(node->count != 0)
{
for(int i = 0; i < node->count; i++)
str[count++] = node->current_str;
内容版权声明:除非注明,否则皆为本站原创文章。