一起学习交流~

字典树

算法 laomuji 9个月前 (01-10) 536次浏览 已收录 0个评论

一、什么是字典树

又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

二、原理

大概长这个样子

一层层的进行匹配
原理比较简单 一看就看出来了
我就不多废话了

三、代码

核心代码

#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//字典树一般用于统计词频
class KeyWordTree
{
private:
    struct Node
    {
        char ch = -1;//保存字符
        int isComplete = 0;//是否是某个字符串的结尾
        vector<struct Node* >childen;//存放所有的孩子节点
    };
    Node root;//根节点,不存放字符,方便操作
public:
    void insert(string str) {
        Node* node = &root;
        int i, j;
        //将str分割为字符
        for (i = 0; i < str.size(); i++)
        {
            int isFind = 0;
            for (j = 0; j < node->childen.size(); j++)
            {
                if (node->childen[j]->ch == str[i]) 
                {
                    node = node->childen[j];//移动节点
                    isFind = 1;//找到了字符
                    break;
                }
            }
            if (isFind == 0) 
            {
                Node* nNode = new Node{ str[i] };
                node->childen.push_back(nNode);//新建一个字符进去
                node = nNode;
            }
            //如果是最后一个字符了,就设定为字符串结束
            if (i + 1 == str.size() && str[i] == node->ch) {
                node->isComplete = 1;
            }

        }
    }
    //字典树中是否存在该字符串,完全匹配
    bool has(string str) 
    {
        Node* node = &root;
        for (int i = 0; i < str.size(); i++) 
        {
            int isFind = 0;
            for (int j = 0; j < node->childen.size(); j++)
            {
                if (node->childen[j]->ch == str[i]) {
                    isFind = 1;
                    node = node->childen[j];
                    break;
                }
            }
            if (isFind==0) {
                return false;
            }
        }
        return true;
    }
    vector<string> search(string str) 
    {
        Node* node = &root;
        vector<string>result;//返回结果数组
        //将str分割为字符
        for (int i = 0; i < str.size(); i++)
        {
            int isFind = 0;
            for (int j = 0; j < node->childen.size(); j++)
            {
                if (node->childen[j]->ch == str[i]) 
                {
                    node = node->childen[j];//移动节点
                    isFind = 1;
                    break;
                }
            }
            if (isFind == 1 && i + 1 == str.size()) {
                //如果当前字符串也是完整的,那么也加入到结果里
                if (node->isComplete == 1) {
                    result.push_back(str);
                }
                //dfs把结果添加进数组
                dfs(node, result, str);
                break;
            }
        }
        return result;
    }

    //打印所有节点
    void prt() {
        vector<string> result;
        dfs(&root,result);
        for (size_t i = 0; i < result.size(); i++)
        {
            cout << result[i] << endl;
        }
    }
    void dfs(Node* node,vector<string>&result, string prefix = "") {
        if (node->childen.size() == 0)return;
        for (int i = 0; i < node->childen.size(); i++) {
            if (node->childen[i]->isComplete) {
                result.push_back(prefix + node->childen[i]->ch);
            }
            dfs(node->childen[i],result, prefix + node->childen[i]->ch);
        }
    }
};

测试代码

#include<iostream>
#include"KeyWordTree.h"

int main1() {
    KeyWordTree tree;
    tree.insert("a");
    tree.insert("aa");
    tree.insert("abc");
    tree.insert("aac");
    tree.insert("ba");
    tree.insert("baa");
    tree.insert("babbc");
    tree.insert("cbaac");
    tree.prt();
    cout << tree.has("baaa") << endl;
    cout << tree.has("babbc") << endl;
    auto res = tree.search("a");
    for (size_t i = 0; i < res.size(); i++)
    {
        cout << res[i] << endl;
    }
    return 0;
}

int main() {
    KeyWordTree tree;
    tree.insert("java");
    tree.insert("c++");
    tree.insert("cpp");
    tree.insert("python");
    tree.insert("c#");
    tree.insert("go");
    tree.insert("c");
    tree.insert("cplusplus");
    tree.prt();
    cout << "---search:\"c\"---" << endl;
    auto resc = tree.search("c");
    for (size_t i = 0; i < resc.size(); i++)
    {
        cout << resc[i] << endl;
    }
    cout << "---search:\"cp\"---" << endl;
    auto rescp = tree.search("cp");
    for (size_t i = 0; i < rescp.size(); i++)
    {
        cout << rescp[i] << endl;
    }
    return 0;
}
喜欢 (2)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论