字典树(Trie)的基本实现(C++)

浏览数：38 / 时间：2015年06月08日

简要说明一下：

主要实现了两个操作，get，set

get用来查找字符串键值对应的value，set则用来向字典树添加key-value对。

这个实现参考自Algorithms 4th Edition, Robert Sedgewick

const int inf = -(1 << 30);

struct Node{
    int val;
    Node** next;
    Node(){
        val = -(1 << 30);
        next = new Node*[256];
        for (int i = 0; i < 256; i++)
            next[i] = NULL;
    }
};

class Tries{
private:
    Node* root;

    Node* get(Node* root, string key, int d)
    {
        if (root == NULL)
            return NULL;
        if (d == key.size())
            return root;

        return get(root->next[key[d]], key, d + 1);

    }

    Node* set(Node* root, string key, int val, int d)
    {
        if (root == NULL)
            root = new Node();
        if (d == key.length())
        {
            root->val = val;
            return root;
        }
            
        root->next[key[d]] = set(root->next[key[d]], key, val, d + 1);
        return root;
    }
public:
    Tries():root(NULL){  }
    int get(string& key)
    {
        Node* ans = get(root, key, 0);
        if (ans == NULL)
            return inf;
        return ans->val;
    }
    void set(string &key, int val)
    {
        root = set(root, key, val, 0);
    }


};

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

字典树(Trie)的基本实现(C++)