Trie树

Trie树

分类： 数据结构 2012-08-08 19:26 198人阅读 评论(0) 收藏 举报

nulldeleteinsertstruct搜索引擎存储

定义：Trie树是一种哈希树的变种，又称字典树，单词查找树或者前缀树，用于保存大量的字符串，是一种用于快速检索的多叉树结构(如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树)。
例如：假设词典由下面的单词构成：a、b、c、aa、ab、ac、ba、ca、aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba
其对应的Trie树如下图所示：


思想：利用字符串的公共前缀来节约存储空间。

典型应用：统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

优点：利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较，查询效率比哈希表高。

 缺点：如果存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存。

三个基本性质：

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

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

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

代码：

// Trie.cpp : 定义控制台应用程序的入口点。
//Trie 称为字典树，单词查找树或者前缀树
#include "stdafx.h"
#include <iostream>
#include <assert.h>
using namespace std;

const int MAX_NUM = 26;
//Trie 树的结点类型
struct Node
{
      bool COMPLETED ;//COMPLETED为 true时表示目前产生的一个字符串
      char ch ;
      struct Node * child[ MAX_NUM]; //26-tree->a, b ,c, .....z
};
//Trie 树类型
class Trie
{
public :
      Trie();
     ~ Trie();
      Node* CreateNewNode (char ch);// 创建一个新结点
      void InitTrie ();//初始化 Trie树
      int CharToindex (char ch);// 找到字母对应的数组下标
      int Find (const char chars [], int len);// 找到长度为 len的字符串
      void Insert (const char chars [], int len);// 插入长度为 len的字符串
      void Delete ();//删除整棵树

private :
      void DeleteTree (Node *& root);
      Node* root ; //根结点
};


Trie::Trie ()
{
    root = NULL ;
}

Trie::~Trie ()
{

}

Node* Trie ::CreateNewNode( char ch )//创建一个新的结点
{
      Node *new_node = new Node;
      new_node->ch = ch;
      new_node->COMPLETED = false;

      for(int i=0; i<MAX_NUM ; i++)
     {
        new_node->child [i] = NULL;
     }
      return new_node ;
}

void Trie ::InitTrie() //构建一棵空树
{
      root = CreateNewNode (' ');
}

int Trie ::CharToindex( char ch )
{
      return ch - 'a';
}

int Trie ::Find( const char chars[], int len )
{
      if (root == NULL)
     {
           cout<<" 树为空！"<< endl;
           return 0;
     }

      Node* ptr = root;
      int i = 0;
      while(i < len)
     {
           if(ptr ->child[ CharToindex(chars [i])] == NULL)
          {
               break;
          }
           ptr = ptr ->child[ CharToindex(chars [i])];
           i++;
     }
      return (i == len) && ( ptr->COMPLETED == true);
}

void Trie ::Insert( const char chars[], int len ) //向 Trie树中插入长度为len的字符串
{
      Node* ptr = root;

      for(int i = 0; i < len ; i++)
     {
           if(ptr ->child[ CharToindex(chars [i])] == NULL)
          {
               ptr->child [CharToindex( chars[i ])] = CreateNewNode (chars[ i]);
          }
           ptr = ptr ->child[ CharToindex(chars [i])];
     }
      ptr->COMPLETED = true;
}

void Trie ::Delete() //利用递归删除整棵树
{
   DeleteTree(root );
}

void Trie ::DeleteTree( Node *&Root )//利用递归删除整棵树 注意此处应该加上应用
{
      if (Root == NULL) //递归出口
     {
           return;
     }

      for (int i=0; i<MAX_NUM ; i++)
     {
           if (Root ->child[ i] != NULL )
          {
               DeleteTree(Root ->child[ i]);
          }
     }
//   if(Root->ch == ' ')
//   {
//        cout<<"zha'"<<endl;
//   }
      delete Root ;
      Root = NULL ;
}

int _tmain (int argc, _TCHAR * argv[])
{
      char *a = "ten";
      char *b = "tea";
      Trie trie ;
      trie.InitTrie ();
      trie.Insert (a, 3);
      trie.Insert (b, 3);
      cout<<trie .Find( a,3)<<endl ;
      trie.Delete ();
    cout<<trie .Find( b,3)<<endl ;

      system("pause" );
      return 0;
}