详解前缀树(字典树)

前缀树又叫字典树，通常用来高效地查询字符串，比如查询库中是否有以某个子字符串为前缀的字符串，某个字符串出现的次数等。前缀树是 N 叉树的一种特殊形式，每一个节点会有多个子节点，通往不同子节点的 路径上 有着不同的字符，子节点中包含两种信息：pass(经过此字符的次数)，end(以此字符结尾的次数)。说多了没用，直接上图：

0-‘a’，1-’b’，2-‘c’，每个节点对应的下标即代表相应字母，除 root 外的其他节点中包含着该字母的信息。
细心的同学应该发现，root 的 end 域只可能为 0，因为这代表着插入了一个空字符串，这是不被允许的。所以我们似乎可以利用这个 end 域做些坏事。容易知道，root 的 pass 域代表着此前缀树中一共有多少个字符串（相同字符串会被重复计数），那么，我如果想知道一共有多少种字符串呢？此时，就要利用 root 的 end 域来记录了。详细注释已在代码给出，不在赘述。代码如下(仅支持小写字母)：

#include<unordered_map>
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<list>
using namespace std;

struct preNode
{
	int pass;
	int end;
	preNode* arr[26];
	preNode() :pass(0), end(0) { 
		for (int i = 0; i < 26; i++)
			arr[i] = NULL;
	}
};

class trieTree
{
private:
	preNode  root;
public:
	trieTree(){}
	void insert(string str);//插入字符串
	int search(string str);//返回某个字符串出现的个数
	bool delOnce(string str);//只删一次，如果删除失败，返回false
	bool delAll(string str);//删除所有str，如果删除失败，返回false
	int prefixSearch(string str);//返回以str为前缀的字符串的个数
	int counts() { return root.pass; }//所有单词总个数
	int nonRepeatCounts() { return root.end; }//不重复单词的个数
};


int main()
{
	trieTree root;
	root.insert("ahc");
	root.insert("ahc");
	root.insert("ahc");
	root.insert("ahcdx");
	root.insert("ahcdx");
	root.insert("ahcdc");
	root.insert("ahcdx");
	root.delAll("ahc");
	int r = root.counts();
	int n = root.nonRepeatCounts();
	cout << "不重复单词个数：" << n << endl;
	cout << "总单词个数：" << r;
}

void trieTree::insert(string str)
{
	if (str.size() == 0)
		return;
	preNode *tmp = &root;
	for (int i = 0; i < str.size(); i++)
	{
		tmp->pass++;
		int p = str[i] - 'a';
		if(tmp->arr[p]==NULL)
			tmp->arr[p] = new preNode;
		tmp = tmp->arr[p];
	}
	if (tmp->end == 0)//插入重复字符串，root->end不计数
		root.end++;
	tmp->end++;
	tmp->pass++;
}

int trieTree::search(string str)
{
	if (str.size() == 0)
		return 0;
	preNode* tmp = &root;
	for (int i = 0; i < str.size(); i++)
	{
		int p = str[i] - 'a';
		if (tmp->arr[p] == NULL)
			return 0;
		tmp = tmp->arr[p];
	}
	return tmp->end;
}

bool trieTree::delOnce(string str)
{
	if (str.size() == 0)
		return false;
	preNode* tmp = &root;
	tmp->pass--;
	for (int i = 0; i < str.size()-1; i++)//遍历到str的倒数第二个字符
	{                                     //因为如果最后一个字符的end=0
		int p = str[i] - 'a';             //就必须delete该节点，然后将指向
		if (tmp->arr[p] == NULL)          //该节点的指针赋值为NULL
			return false;
		tmp->pass--;
		tmp = tmp->arr[p];
	}
	tmp->arr[str.size() - 1]->end--;
	tmp->arr[str.size() - 1]->pass--;
	if (tmp->arr[str.size() - 1]->pass == 0)
	{
		delete tmp->arr[str.size() - 1];
		tmp->arr[str.size() - 1] = NULL;
	}
	return true;
}

bool trieTree::delAll(string str)
{
	if (str.size() == 0)
		return false;
	preNode* tmp = &root;
	for (int i = 0; i < str.size(); i++)
	{
		int p = str[i] - 'a';
		if (tmp->arr[p] == NULL)
			return false;
		tmp = tmp->arr[p];
	}
	root.end--;
	int cnt = tmp->end;
	tmp = &root;
	for (int i = 0; i < str.size()-1; i++)
	{
		tmp->pass -= cnt;
		int p = str[i] - 'a';
		tmp = tmp->arr[p];
	}
	if (tmp->arr[str.size() - 1]->pass == cnt)
	{
		delete tmp->arr[str.size() - 1];
		tmp->arr[str.size() - 1] = NULL;
	}
	tmp->arr[str.size() - 1]->pass -= cnt;
	tmp->arr[str.size() - 1]->end -= cnt;
}

int trieTree::prefixSearch(string str)
{
	if (str.size() == 0)
		return false;
	preNode* tmp = &root;
	for (int i = 0; i < str.size(); i++)
	{
		int p = str[i] - 'a';
		if (tmp->arr[p] == NULL)
			return 0;
		tmp = tmp->arr[p];
	}
	return tmp->pass;
}

以上是链式实现，当字符种类很多时，一般就采用哈希实现，此方式后面有时间再给出。