前缀树（字典树）

一、什么是字典树？

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

字典树的基本功能是用来查询某个单词（前缀）在所有单词中出现次数的一种数据结构，它的插入和查询复杂度都为O(len),Len为单词（前缀）长度，但是它的空间复杂度却非常高，如果字符集是26个字母，那每个节点的度就有26个，典型的以空间换时间结构。

二、c++实现

1.字典树结点结构：

 typedef struct node
 {
     struct node *next[Max];  //表示对于每个节点最多有26个孩子节点
     int num;   //表示存储的孩子节点的个数
 }Node;

2.字典树代码实现：

【例题】

给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的……这样一个树的模型就渐渐清晰了……

#pragma once
#include <iostream>

using namespace std;

#define Max 26

//字典树的结点
/*
根结点是一个没有实际意义的结点，根结点的子节点才是单词开始的结点。
*/
typedef struct Node_trie
{
	struct Node_trie *next[Max];
	int num;//该结点出现的次数
}Node_trie;

//创建一个新节点
/*
创建一个结点时，把该结点的孩子结点都指向NULL，另外初始化该结点的次数为0；
*/
Node_trie *createNew()
{
	Node_trie *p = new Node_trie;
	for (int i = 0; i< Max; i++)
	{
		p->next[i] = NULL;
	}
	p->num = 0;
	return p;
}

//插入一个字符串
void Insert_str(char str[], Node_trie *head)
{
	int len = strlen(str);
	Node_trie *t, *p = head;//从根结点开始做插入单词操作
	for (int i = 0; i<len; i++)//遍历单词
	{
		int c = str[i] - 'a';//取字母的位置（在字母表中的位置）
		if (p->next[c] == NULL)//如果父节点没有孩子结点，就创建
		{

			t = createNew();//创建一个新节点
			p->next[c] = t;//将这个新节点作为p的第c个孩子结点
			p->next[c]->num++;
			p = p->next[c];
		}
		else
		{
			p = p->next[c];
			p->num++;
		}
	}
}

int Search_str(char str[], Node_trie *head)
{
	Node_trie *p = head;
	int len = strlen(str);
	int count = 0;
	for (int i = 0; i<len; i++)
	{
		int c = str[i] - 'a';
		if (p->next[c] == NULL)
		{

			cout << "不存在字符串" << endl;
			count = 0;
			return 0;
		}
		else
		{
			p = p->next[c];
			count = p->num;
		}

	}
	return count;
}

三、字典树的典型应用

1.统计一组字符串中某前缀出现的次数

//统计一组字符串中某前缀出现的次数
void test_Trie01()
{

	Node_trie *head = createNew();
	char s[10];

	while (cin >> s, strcmp(s, "quit"))
	{
		Insert_str(s, head);
	}

	while (cin >> s, strcmp(s, "exit"))
	{
		int c = Search_str(s, head);
		cout << c << endl;
	}

	system("pause");


}

2.判断一组字符串中是否有一个字符串是另一个字符串的前缀。

分析：需要对结点添加一个变量EndFlag，如果EndFlag == 0，表明该结点不是单词的结尾，如果EndFlag == 1，表明该结点是单词的结尾；插入的代码也需要修改，具体而言，

（1）针对已经有abcd的字典树中插入abc的时候，在插入到最后一个字符时，判断字典树中是否已经有最后一个字符，如果有，就说明存在前缀；

（2）针对已经有abc的字典树中插入abcd的时候，我们在插入c的时候，判断该结点是否是字典树中某个单词的结尾，如果是，就说明存在前缀；

#include<iostream>
using namespace std;
#define MAX 26
typedef struct node
{
    struct node *next[MAX];
    int num;//该结点出现的次数
    bool EndFlag;//如果EndFlag=0，表明该节点不是单词的结尾，如果EndFlag=1，表明该节点是单词的结尾
}Node;

Node *CreateNew()
{
    Node *p = new node;
    for (int i = 0; i<MAX; i++)
    {
        p->next[i] = NULL;
    }
    p->num = 0;
    p->EndFlag = 0;
    return p;
}
void insert_str(char str[], Node *head,bool &IsPrefix)//插入功能，并在插入的时候判断当前要插入的单词
//是否是已经插入的单词的前缀或者已经插入的单词是否是该单词的前缀
{
    IsPrefix = false;//初始化不存在
    int len = strlen(str);
    Node *t, *p = head;
    for (int i = 0; i<len; i++)
    {
        int c = str[i] - 'a';

        if (i == len - 1&&p->next[c]!=NULL)//插入最后一个字符串，且它是前面某个单词的后缀（已经有abcd，在插入abc时出现）
        {
            IsPrefix = true;
        }

        if (p->next[c] == NULL)
        {
            t = CreateNew();
            p->next[c] = t;
            p->next[c]->num++;
            p = p->next[c];
        }
        else
        {
            p = p->next[c];
            p->num++;
            if (p->EndFlag == 1)//某个已经插入的单词的结束标识符（已经有abc,插入abcd时出现）
                IsPrefix = true;
        }
    }
    p->EndFlag = 1;//单词插入完以后，就把当前的节点作为终结节点，EndFlag=1。
}
int main()
{
    cout << "Hello" << endl;
    Node *head = CreateNew();
    char s[10];
    bool IsPrefix = false;
    while (cin >> s, strcmp(s, "quit"))
    {
        insert_str(s, head, IsPrefix);
        if(IsPrefix)
            cout << "存在某个单词是另一个单词的前缀" << endl;
    }
    /*int c = search_str("ab", head);
    cout << c << endl;*/
    system("pause");
    return 0;
}

3.leetcode208 --- 实现前缀树

（1）版本一

class Trie
{
private:
	bool is_string = false;
	Trie* next[26] = { nullptr };
public:
	Trie() {}

	void insert(const string& word)//插入单词
	{
		Trie* root = this;
		for (const auto& w : word) {
			if (root->next[w - 'a'] == nullptr)root->next[w - 'a'] = new Trie();
			root = root->next[w - 'a'];
		}
		root->is_string = true;
	}

	bool search(const string& word)//查找单词
	{
		Trie* root = this;
		for (const auto& w : word) {
			if (root->next[w - 'a'] == nullptr)return false;
			root = root->next[w - 'a'];
		}
		return root->is_string;
	}

	bool startsWith(const string& prefix)//查找前缀
	{
		Trie* root = this;
		for (const auto& p : prefix) {
			if (root->next[p - 'a'] == nullptr)return false;
			root = root->next[p - 'a'];
		}
		return true;
	}
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

（2）版本2

防止出现内存泄漏的问题：

class Trie {
public:
    /** Initialize your data structure here. */
    Trie():root_(new TreeNode) { }

    ~Trie() { destroy(root_); }
    
    /** Inserts a word into the trie. */
   
    void insert(const std::string& word) {
        if(word.empty()) return;

        TreeNode* curr = root_;
        for(const char& ch : word) { 
            size_t index = ch -'a';
            if(curr->branchs[index] == nullptr) 
            {
                curr->branchs[index] = new TreeNode;
            }
            curr = curr->branchs[index];
        }
        curr->end = true; 
    }
    
    /** Returns if the word is in the trie. */
    bool search(const std::string& word) {
        if(word.empty()) return true;

        TreeNode* curr = root_;
        for(const char& ch : word) { 
            int index = ch - 'a';
            if(curr->branchs[index] == nullptr) 
            {
                return false;
            }

            curr = curr->branchs[index];
        }

        return curr->end;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const std::string& prefix) {
      if(prefix.empty()) return true;

      TreeNode* curr = root_;
      for(const char& ch : prefix) { 
        int index = ch - 'a';
        if(curr->branchs[index] == nullptr) 
        {
            return false;
        }

        curr = curr->branchs[index];
      }

      return true;
    }

private:
    struct TreeNode { 
        bool end; // 是否是某个字符串的结尾标志
        std::array<TreeNode*, 26> branchs;

        TreeNode(bool end=false)
        : end(end)
        { 
            branchs.fill(nullptr);
        }
    };

  void destroy(TreeNode* node) {
    if(node ==nullptr) return;

    for(TreeNode* entry : node->branchs)
    {
     destroy(entry); 
    } 

    if(node) 
    { 
      delete node;
      node = nullptr;
    }
  }
    

    TreeNode* root_;
};

4.leetcode14 --- 最长公共前缀

【题目描述】

class TrieNode{
public:
    TrieNode* children[26];
    int count = 0;
    bool isEnd = false;
    TrieNode() {
        for(int i = 0; i < 26; i++) {
            children[i] = NULL;
        }
        count = 0;
    }

    TrieNode* insert(char c) {
        if(children[c - 'a'] == NULL) {
            children[c - 'a'] = new TrieNode();
            count++;
        }
        return children[c - 'a'];
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        TrieNode* root = new TrieNode();
        for(int i = 0; i < n; i++) {
            string word = strs[i];
            //情况特判，如果有空字符串直接返回空
            if(word == "") {
                return "";
            }
            TrieNode* tmp = root;
            for(const char& c : word) {
                tmp = tmp -> insert(c);
            }
            //处理好一个字符串后设置结束标志，以便解决描述的情况2
            tmp -> isEnd = true;
        }
        string ans = "";
        //查找字典树中分支为1并且结束标识为false的字符
        while(root != NULL && root -> count == 1 && root -> isEnd == false) {
            for(int i = 0; i < 26; i++) {
                if(root -> children[i] != NULL) {
                    ans += ('a' + i);
                    root = root -> children[i];
                    break;
                }
            }
        }
        return ans;
    }
};