一 : 树

　　一棵葱茏的大树，

　　一片茂盛的树阴，

　　种种迹象，

　　谁会知道它是怎样诞生？

　　不知经历了多少年，

　　才会如此成功，

　　为一片绿阴，

　　钻透过各种硬土，

　　吮吸过任何雨露，

　　为了梦后的奉献，

　　它生长着，

　　拼搏着，

　　永不停息。

 

    初一:栀香

二 : Trie树

                                                        Trie树

      Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。［www.61k.com]

一.Trie树的原理

   利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。

   下面以英文单词构建的字典树为例，这棵Trie树中每个结点包括26个孩子结点，因为总共有26个英文字母(假设单词都是小写字母组成)。

   则可声明包含Trie树的结点信息的结构体:

#define MAX 26

typedef struct TrieNode //Trie结点声明
{
bool isStr; //标记该结点处是否构成单词
struct TrieNode *next[MAX]; //儿子分支
}Trie;

   其中next是一个指针数组，存放着指向各个孩子结点的指针。

   如给出字符串"abc","ab","bd","dda"，根据该字符串序列构建一棵Trie树。则构建的树如下:

 Trie树的根结点不包含任何信息，第一个字符串为"abc"，第一个字母为'a'，因此根结点中数组next下标为'a'-97的值不为NULL，其他同理，构建的Trie树如图所示，红色结点表示在该处可以构成一个单词。很显然，如果要查找单词"abc"是否存在，查找长度则为O(len)，len为要查找的字符串的长度。而若采用一般的逐个匹配查找，则查找长度为O(len*n)，n为字符串的个数。显然基于Trie树的查找效率要高很多。

但是却是以空间为代价的，比如图中每个结点所占的空间都为(26*4+1)Byte=105Byte，那么这棵Trie树所占的空间则为105*8Byte=840Byte，而普通的逐个查找所占空间只需(3+2+2+3)Byte=10Byte。

二.Trie树的操作

   在Trie树中主要有3个操作，插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况，因此只考虑删除整棵树。

1.插入

 假设存在字符串str，Trie树的根结点为root。i=0，p=root。

 1)取str[i]，判断p->next[str[i]-97]是否为空，若为空，则建立结点temp，并将p->next[str[i]-97]指向temp，然后p指向temp；

  若不为空，则p=p->next[str[i]-97]；

 2)i++，继续取str[i]，循环1)中的操作，直到遇到结束符'\0'，此时将当前结点p中的isStr置为true。

2.查找

 假设要查找的字符串为str，Trie树的根结点为root，i=0，p=root

 1)取str[i]，判断判断p->next[str[i]-97]是否为空，若为空，则返回false；若不为空，则p=p->next[str[i]-97]，继续取字符。

 2)重复1)中的操作直到遇到结束符'\0',若当前结点p不为空并且isStr为true，则返回true，否则返回false。

3.删除

 删除可以以递归的形式进行删除。

测试程序:

/*Trie树(字典树) 2011.10.10*/ #include <iostream> #include<cstdlib> #define MAX 26 using namespace std; typedef struct TrieNode //Trie结点声明 { 	bool isStr; //标记该结点处是否构成单词 struct TrieNode *next[MAX]; //儿子分支 }Trie; void insert(Trie *root,const char *s) //将单词s插入到字典树中 { 	if(root==NULL||*s=='\0')  return; 	int i;  Trie *p=root; 	while(*s!='\0') 	{  if(p->next[*s-'a']==NULL) //如果不存在，则建立结点 {  Trie *temp=(Trie *)malloc(sizeof(Trie));  for(i=0;i<MAX;i++)  {  temp->next[i]=NULL;  }  temp->isStr=false;  p->next[*s-'a']=temp;  p=p->next[*s-'a']; } else  {  p=p->next[*s-'a'];  }  s++; 	} 	p->isStr=true; //单词结束的地方标记此处可以构成一个单词 } int search(Trie *root,const char *s) //查找某个单词是否已经存在 { 	Trie *p=root; 	while(p!=NULL&&*s!='\0') 	{  p=p->next[*s-'a'];  s++; 	} 	return (p!=NULL&&p->isStr==true); //在单词结束处的标记为true时，单词才存在 } void del(Trie *root) //释放整个字典树占的堆区空间 { 	int i; 	for(i=0;i<MAX;i++) 	{  if(root->next[i]!=NULL)  {  del(root->next[i]);  } 	} 	free(root); } int main(int argc, char *argv[]) { 	int i; 	int n,m; //n为建立Trie树输入的单词数，m为要查找的单词数 char s[100]; 	Trie *root= (Trie *)malloc(sizeof(Trie)); 	for(i=0;i<MAX;i++) 	{  root->next[i]=NULL; 	} 	root->isStr=false;  scanf("%d",&n);  getchar(); 	for(i=0;i<n;i++) //先建立字典树 {  scanf("%s",s);  insert(root,s); 	} 	while(scanf("%d",&m)!=EOF) 	{  for(i=0;i<m;i++) //查找 {  scanf("%s",s);  if(search(root,s)==1)  printf("YES\n");  else  printf("NO\n");  }  printf("\n"); } 	del(root); //释放空间很重要 return 0; }

训练题目:

http://acm.hdu.edu.cn/showproblem.php?pid=1671

http://acm.hdu.edu.cn/showproblem.php?pid=1075

http://acm.hdu.edu.cn/showproblem.php?pid=1251

扩展：trie / trie树 java / 双数组trie树

扩展：trie / trie树 java / 双数组trie树

三 : 树

当我

第一次

遇见那棵树

的时候，我便知道

这是我寻觅多年的感受。

虽叫不出她的名字，却感应了( 文章阅读网：www.61k.com )

前生所遗留的自愿和哀怨。

说她高，她不高；说她矮，她又高于我。

作为一棵树，在这样的山巅，她寂寞吗？

她是否后悔过生在了悬崖，没有低语的伙伴？

我忘记了树是不能言语的。她的气质，铸就了她的孤独。

渐渐地少了抱怨，默默地扎根，缓缓地生长。

一棵树到底能够存在多久？她也应该存在多时了罢。

没有翠绿，也没有饱经沧桑，就伫立在哪儿。

少了柔美，却也不老气横秋，给人以平静的感受。

平实的外表下又隐了多少伤痕？依稀可以见得。

枝叶遒劲，像是松柏；散出异香，又似香樟。

引起我对她身世的猜疑，没有结果。

在三千海拔的高山上，我遇见了这棵树

一种相见恨晚的感受，莫名袭来。

胸膛迸射出热量，我变成一棵树

从那以后，那棵树的旁边多了一棵小树

我在想，小树也许能和大树对话，聆听

她的前生今世

我对她的情感，

不好用任何形容

我只好用笨拙

的诗行，描绘

她依稀的轮廓

也许，这树

只是我的臆想

大梦初醒

霍然发觉

荒唐了

这一生。

本文标题：树-树
本文地址： http://www.61k.com/1077991.html