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;

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/1600.html