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

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

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

?

Trie樹的結構體：

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

?

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

    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();//動態建樹，也可以換成靜態
		p = p->next[del];
		i++;
	}
	if(p->id == -1)
		p->id = num++;
	return p->id;
}
  

?

POJ2513

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

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

?

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

1.判斷該圖是否連通；

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

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

?

POJ3630(1056)

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

分析：在Trie樹中放置一個標志位，表示從根節點到該結點是否是已經輸入的號碼。

    bool findAndInsert(char *t)
{
	Trie_Node *p = root;
	int i = 0,del;
	while(t[i] != '\0')
	{
		if(p->exist)
			return true;		//別的字符串是當前字符串的前綴
		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++)		//當前字符串是別的字符串的前綴
	{
		if(p->next[i] != NULL)
			return true;
	}
	p->exist = true;
	return false;
}
  

?

POJ2001

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

分析：在Trie樹中加入一個計數器num，表示以這個字符串為前綴的單詞有幾個。在查詢時，根據傳入的單詞一層層的往下找，找到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;
}
  

?

?

?

數據結構之——Trie樹