前缀树C++

前缀树

1. 特点就是利用空间换时间，通过利用前缀存储的方法达到高效的查找效率。
   3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同

1. 假设有abc，abd，bcd，efg，hii，那么我们构建如下一个树结构用于表示这些单词
   
   这样带来的问题就是如果匹配b，这个单词是否出现过呢，bc出现过吗？ 针对上述问题，为每个节点添加字符串的统计信息，表示以这个节点对应的字符结尾的string数量。
   
   如果现在有另外一个问题，我想知道所有字符串中有多少个以该字符串作为前缀，那是不是得遍历该条路径后面的节点，将所有的end加起来。为了简单，我们仍然可以在节点中多存入一个信息，每个节点被划过了多少次，也就是在建立多叉树的时候就记录了以所有字符串中有多少个以某字符串作为前缀，划过的次数就是这个值。
   

代码

class TrieNode{
  
public:
	const static int MAXBRANCH = 26；
	int end;
	int pass;
	string word;
	TrieNode *next[MAXBRANCH];
	TrieNode(){
  
		end = 0;
		pass = 0;
		word="";
		memset(next, NULL, sizeof(TrieNode*)*MAXBRANCH);
	}
	
};
class TrieTree{
  
private:
	TrieNode*root;
public:
	TrieTree();
	~TrieTree();
	void insert_str(string str);
	void delete_str(string str);
	int search_str(string str);

};
TrieTree::TrieTree(){
  
	root = new TrieNOde();
}
TrieTree::~TrieTree(){
  
	destroy(root);
}
void TrieTree::insert_str(string str){
  
	if(str=="") return;
	int len = str.size();
	TrieNode* node = root;
	for(int i = 0; i <len; i++){
  
		int index = str[i] - 'a';
		if(node->next[index]==NULL){
  
			node->next[index]=new TrieNode();
		}
		node = node->next[index];
		node->pass++;
	}
	node->end++;
	node->word=str;
}
void TrieTree::delete_str(string str){
  
	if(str == "") return;
	int len = str.size();
	TrirNode *tmp, *node=root;
	for(int i = 0; i < len; i++){
  
		int index = str[i] - 'a';
		tmp = node->next[index];
		if(tmp->pass == 1){
  
			delete node->next[index];
		}
		tmp->pass--;
		node = tmp;
	}
	tmp->end--;
}
int TrieTree::search_str(string str){
  
	if(str == "") return;
	int len = str.size();
	TrieNode *node = root;
	for(int i = 0; i < len; i++){
  
		int index = str[i]-'a';
		if(node->next[index] == NULL) return 0;
		node = node->next[index];
	}
	return node->end;
}