字典树

你的名字 2022-08-02 14:59 177阅读 0赞

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

![Center][]

它有3个基本性质：  
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符；

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

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

// Trie.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    
    using namespace std;
    
    #define MAXSIZE 26
    
    
    
    struct TrieNode
    {
    	TrieNode* next[MAXSIZE];
    	char p;
    	int Num;
    	bool isword;
    };
    
    TrieNode*initiate_Trie()
    {
    	TrieNode*root = new TrieNode;
    	for (int i = 0; i < MAXSIZE; i++)
    		root->next[i] = NULL;
    	root->Num = 0;
    	root->isword = false;
    	return root;
    
    
    }
    
    bool search(TrieNode*root, char*str)
    {
    	TrieNode*tn;
    	tn = root;
    	int k;
    	while (*str != '\0')
    	{
    		k = *str - 'a';
    		if (tn->next[k] == NULL)
    			return false;
    		tn = tn->next[k];
    		str++;
    	}
    	if (tn->isword == false)
    		return false;
    	return true;
    }
    
    TrieNode*build_Trie_singleword(TrieNode*root, char*str)
    {
    	if (search(root, str))
    		return root;
    	root->Num = root->Num + 1;
    	TrieNode*tn;
    	tn = root;
    	while (*str != '\0')
    	{
    		int k = *str - 'a';
    		if (tn->next[k] == NULL)
    		{
    			tn->next[k] = new TrieNode;
    			for (int i = 0; i < MAXSIZE; i++)
    				tn->next[k]->next[i] = NULL;
    			tn->next[k]->p = *str;
    			tn->next[k]->Num = 1;
    			tn->next[k]->isword = false;
    		}
    
    		else
    		{
    			tn->next[k]->Num = tn->next[k]->Num + 1;
    
    		}
    		tn = tn->next[k];
    		str++;
    	}
    	tn->isword = true;
    	return root;
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	TrieNode*root = initiate_Trie();
    	root = build_Trie_singleword(root, "abc");
    	root = build_Trie_singleword(root, "abcd");
    	root = build_Trie_singleword(root, "abc");
    	
    	system("pause");
    	return 0;
    }

[Center]: /images/20220731/7a3d1134ff09486cbf718d180a91c847.png