字典树的C++实现 Implement of trie tree

Trie，字典树，又称单词查找树、前缀树，是一种哈希树的变种。应用于字符串的统计与排序，经常被搜索引擎系统用于文本词频统计。

性质：

1.根节点不包含字符，除根节点外的每一个节点都只包含一个字符。

2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3.每个节点的所有子节点包含的字符都不相同。

优点是查询快。对于长度为m的键值，最坏情况下只需花费O(m)的时间；而BST需要O(m log n)的时间。

本文用C++实现了字典树的

建立，插入，遍历，查找，删除节点，删除字典树，统计含有指定前缀的单词数等功能。

着重讲述下列功能的实现。

插入单词的实现：

1).设置当前节点为根节点，设置当前字符为插入字符串中的首个字符；

2).在当前节点的子节点上搜索当前字符，若存在，则将当前节点设为值为当前字符的子节点；否则新建一个值为当前字符的子节点，并将当前结点设置为新创建的节点。

3).将当前字符设置为串中的下个字符，若当前字符为0，则结束；否则转2.

4).结束时，把最后一个节点（即此时的当前节点）的isEnd设为true，对应下图中的黑色节点。表示该节点是一个单词的结尾。

查找单词的实现：

过程和插入单词非常类似，这里不再赘述。

删除单词的实现：

首先查找待删除字符串，将路径上的节点一个个入栈（本文用递归实现）。

1：若途中某个字符找不到，则不删除。

2：若到达了字符串的末尾的下一个位置，说明字符串中所有字符均找到，把包含字符串最后一个字符的那个节点设为（isEnd = false），表明到该位置不是一个单词的结尾了。

如果保存字符串中最后那个字符的节点是个叶子节点（即childCnt为0），则删除该点。

接下来便一层一层往上返回，判断当前节点是删除还是保留：

若当前节点孩子为0（childCnt为0）并且当前节点不为一个单词的结尾时（isEnd为false），则删除该节点，否则不删除。

容易造成的误解是，若当前节点的孩子为0了不就可以删除了吗？其实不然。

使用插入时用的图做说明：

当插入了字符串"abc","ad","ef","e"后，要删除字符串“ef“，遵循上述的步骤，指针会到达黑色的“ef”节点，此时把该节点的isEnd设为false，表示该节点已经不能表示一个单词的结尾了。而且该节点为叶子节点，所以要删除它。然后返回该节点的父节点，即“e”节点，由于它唯一的子节点已经被删除了，所以“e”节点此时已经退化成了叶子节点（childCnt==0），然而此时却不能删除它，因为它是黑色的（是单词“e”的结尾）。所以要判断当前节点是否可以删，必须满足它是叶子节点以及它不是一个单词的结尾这两个条件。

统计含有相同前缀的单词个数的实现（！！待改进版）：

以属性prefixCnt来统计，经过该节点的单词一共有多少个，这样，在给定一个前缀的时候，按照查询字符串的方法，一步步往下查找，途中出现为找到的字符串，则返回0。否则到达包含前缀的最后一个字符的节点，直接返回该节点的prefixCnt的值即可。然而该值是在进行插入单词时更新的，目前的处理只能针对没有重复插入同一个单词的情况。如果要对重复插入同一个单词的情况进行处理，需要使用栈的思维？如果各位有什么好的办法，评论里多多指教。

#include <queue>
#include <iostream>
using namespace std;

const int size = 26;

struct TrieTreeNode
{
	char val;
	bool isEnd;
	int childCnt;
	int prefixCnt;
	TrieTreeNode *child[size];
	TrieTreeNode(char _val)
		:val(_val),isEnd(false),childCnt(0),prefixCnt(0)
	{
		memset(child,NULL,sizeof(child));//not 26!!
	}
};

void Insert(TrieTreeNode *&root, const char *word)
{
	TrieTreeNode *p = root;
	for (int i = 0; i < strlen(word); i++)
	{
		if(p->child[word[i]-‘a‘] == NULL)
		{
			p->child[word[i]-‘a‘] = new TrieTreeNode(word[i]);
			p->childCnt++;
		}
		//notice!!this line need to be optimized to handle with duplicated insertion
		p->child[word[i]-‘a‘]->prefixCnt++;

		p = p->child[word[i]-‘a‘];
	}
	p->isEnd = true;
}

bool Find(TrieTreeNode *root, const char *word)
{
	TrieTreeNode *p = root;
	for (int i = 0; i < strlen(word); i++)
	{
		if (p->child[word[i]-‘a‘] == NULL)
			return false;
		p = p->child[word[i]-‘a‘];
	}
	return p->isEnd;
}

void LevelOrderTraverse(TrieTreeNode *root)
{
	if(root == NULL)
		return;
	queue<TrieTreeNode *> Q;
	Q.push(root);
	while (!Q.empty())
	{
		TrieTreeNode *p = Q.front();
		cout << p->val << "(" << p->childCnt << ") ";
		for (int i = 0; i < size; i++)
		{
			if(p->child[i] != NULL)
				Q.push(p->child[i]);
		}
		Q.pop();
	}
	cout << "\n";
}

void PreOrderTraverse(TrieTreeNode *treeNode)
{
	if (treeNode != NULL)
	{
		cout << treeNode->val << "(" << treeNode->childCnt << ") ";
		for (int i = 0; i < size; i++)
		{
			PreOrderTraverse(treeNode->child[i]);
		}
	}
}

void PostOrderTraverse(TrieTreeNode *treeNode)
{
	if (treeNode != NULL)
	{
		for (int i = 0; i < size; i++)
		{
			PostOrderTraverse(treeNode->child[i]);
		}
		cout << treeNode->val << "(" << treeNode->childCnt << ") ";
	}
}

void MakeEmpty(TrieTreeNode *&treeNode)
{
	if (treeNode != NULL)
	{
		for (int i = 0; i < size; i++)
		{
			MakeEmpty(treeNode->child[i]);
		}
		delete treeNode;
	}
	treeNode = NULL;
}

void BuildTrieTree(TrieTreeNode *&root,const char *words[], int n)
{
	for (int i = 0; i < n; i++)
	{
		Insert(root,words[i]);
	}
}

bool Remove(TrieTreeNode *&treeNode, const char *word,int pos, int n) 
{
	if (pos == n)
	{
		treeNode->isEnd = false;//set the node not to be an end
		//if the last node contains the last char is a leaf,return true to delete it
		return treeNode->childCnt == 0;
	}

	//not found, not delete this node
	if (treeNode->child[word[pos]-‘a‘] == NULL) 
		return false;

	//if true, the child is a leaf, delete the child
	if ( Remove( treeNode->child[word[pos]-‘a‘], word, pos+1, n))
	{ 
		delete treeNode->child[word[pos]-‘a‘];
		treeNode->child[word[pos]-‘a‘] = NULL;

		treeNode->prefixCnt--;
		//if the node becomes a leaf and is not an end,return true to delete it
		if (--treeNode->childCnt == 0 && treeNode->isEnd == false)
			return true;
	}

	//other not delete
	return false;
}

//Count the number of words which contain the specific prefix
int CountWordsWithPrefix(TrieTreeNode *root, const char *prefix)
{
	TrieTreeNode *p = root;
	for (int i = 0; i < strlen(prefix); i++)
	{
		if(p->child[prefix[i]-‘a‘] == NULL)
			return 0;
		
		p = p->child[prefix[i]-‘a‘];
	}
	return p->prefixCnt;
}

int main()
{
	TrieTreeNode *root = new TrieTreeNode(‘\0‘);
	//const char *words[] = {"b","abc","abd","bcd","abcd","efg","hii"}; //test insert
	//cout << sizeof(words) << "\n";//(4*7=28)
	//cout << sizeof(words[0]) << "\n";//4(is a pointer)

	const char *words[] = {"abc","ad","ef"};//test remove
	BuildTrieTree(root,words,sizeof(words)/sizeof(words[0]));
	LevelOrderTraverse(root);
	PreOrderTraverse(root);
	cout << ‘\n‘;
	PostOrderTraverse(root);
	cout << "\n";

	if (Find(root,"ef"))
		cout << "ef found" << endl;
	else cout << "ef not found" <<endl;

	Insert(root,"e");
	//after this insertion.the node ‘e‘ becomes a end but it‘s not a leaf,
	//so it can not be deleted unless its leaf(leaves) is deleted
	LevelOrderTraverse(root);

    Remove(root,"ef",0,strlen("ef"));
	LevelOrderTraverse(root);

	Remove(root,"e",0,strlen("e"));
	LevelOrderTraverse(root);

	cout << CountWordsWithPrefix(root,"a")<<endl;
	Remove(root,"ad",0,strlen("ad"));
	cout << CountWordsWithPrefix(root,"a")<<endl;

	MakeEmpty(root);
	
	return 0;
}

字典树的C++实现 Implement of trie tree,古老的榕树,5-wow.com