????? Trie樹，又稱單詞查找樹，典型用于統(tǒng)計和排序大量字符串，查詢效率比哈希表高。(空間復(fù)雜度高)

它有3個基本特性：
　　1）根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。
　　2）從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。
　　3）每個節(jié)點的所有子節(jié)點包含的字符都不相同。

Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

?

Trie樹的結(jié)構(gòu)體：

    struct Trie_Node
{
	int id;//數(shù)據(jù)域
	Trie_Node *next[26];//孩子結(jié)點
	Trie_Node()
	{
		id = -1;
		memset(next,0,sizeof(next));
	}
}*root;
  

?

Trie樹的更新操作(插入、查詢某字符串的數(shù)據(jù))

    int getNum(char *t)
{
	Trie_Node *p = root;
	int i = 0,del;
	while(t[i] != '\0')
	{
		del = t[i] - 'a';
		if(p->next[del] == NULL)
			p->next[del] = new Trie_Node();//動態(tài)建樹，也可以換成靜態(tài)
		p = p->next[del];
		i++;
	}
	if(p->id == -1)
		p->id = num++;
	return p->id;
}
  

?

POJ2513

題目大意：有n根筷子(n=250000)，每根筷子兩頭涂有顏色?，F(xiàn)在問能否將所有筷子連起來，并且每兩根筷子的連接點顏色都相同。

分析：題意不難理解，現(xiàn)在做一個轉(zhuǎn)換：將每種顏色作為一個結(jié)點，每根筷子兩頭的顏色之間連有一條邊。這樣，就形成了下面的圖：

?

???? 這樣問題就轉(zhuǎn)化為：要求全部走完且經(jīng)過每條邊一次且僅一次，即一筆畫問題。?這就成了歐拉路的判斷：

1.判斷該圖是否連通；

2.該圖的每個點的度要么全為偶數(shù)，要么有且僅有兩個度為奇數(shù)。

判斷圖是否是連通圖，可以用并查集。計算每個點的度，就是統(tǒng)計單詞出現(xiàn)的次數(shù)。因此聯(lián)想到用Trie樹統(tǒng)計單詞出現(xiàn)的次數(shù)，每次將單詞在Trie樹中查找，若該單詞在trie樹中第一次出現(xiàn)，則給它一個標(biāo)號(相當(dāng)于hash)。

?

POJ3630(1056)

題目大意：給出n個電話號碼(n=10000)，每個電話號碼長度不超過10。要求是否滿足：每個電話號碼不能是其它號碼的前綴。

分析：在Trie樹中放置一個標(biāo)志位，表示從根節(jié)點到該結(jié)點是否是已經(jīng)輸入的號碼。

    bool findAndInsert(char *t)
{
	Trie_Node *p = root;
	int i = 0,del;
	while(t[i] != '\0')
	{
		if(p->exist)
			return true;		//別的字符串是當(dāng)前字符串的前綴
		del = t[i] - '0';
		if(p->next[del] == NULL)
		{
			p->next[del] = &node[nodeNum];
			nodeNum++;
		}
		p = p->next[del];
		i++;
	}
	for(i = 0; i < 10; i++)		//當(dāng)前字符串是別的字符串的前綴
	{
		if(p->next[i] != NULL)
			return true;
	}
	p->exist = true;
	return false;
}
  

?

POJ2001

題目大意：現(xiàn)在人們喜歡用縮寫，比如 carbon 可以縮寫為carb，但不能縮寫為car。因為有car這個準(zhǔn)確的單詞。給你n個單詞(n=1000)，每個單詞長度不超過20。求出每個單詞的最短縮寫。

分析：在Trie樹中加入一個計數(shù)器num，表示以這個字符串為前綴的單詞有幾個。在查詢時，根據(jù)傳入的單詞一層層的往下找，找到num=1就說明這個是第一次被使用，停止輸出。

    #include <iostream>
const int MAX = 1001;
char str[MAX][21];
int nodeNum;

struct Trie_Node
{
	int num;	//to remember how many words can reach here
	Trie_Node *next[26];
	Trie_Node()
	{
		num = 0;
		memset(next,NULL,sizeof(next));
	}
};
Trie_Node node[MAX*10],head;

void insert(char *t)
{
	int i=0,del;
	Trie_Node *p = &head;
	while(t[i] != '\0')
	{
		del = t[i] - 'a';
		if(p->next[del] == NULL)
		{
			p->next[del] = &node[nodeNum];
			nodeNum++;
		}
		p->next[del]->num++;
		p = p->next[del];
		i++;
	}
}

void query(char *t)
{
	int i = 0;
	Trie_Node *p = &head;
	while(t[i] != '\0')
	{
		printf("%c",t[i]);
		p = p->next[t[i]-'a'];
		if(p->num == 1)
			break;
		i++;
	}
	printf("\n");
}

int main()
{
	int i = 0;
	nodeNum = 1;
	while(scanf("%s",str[i]) != EOF)
	{
		insert(str[i]);
		i++;
	}
	for(int j = 0; j < i; j++)
	{
		printf("%s ",str[j]);
		query(str[j]);
	}
	return 0;
}
  

?

?

?

數(shù)據(jù)結(jié)構(gòu)之——Trie樹