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

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

Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢(xún)時(shí)間的開(kāi)銷(xiāo)以達(dá)到提高效率的目的。

?

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

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

?

Trie樹(shù)的更新操作(插入、查詢(xún)某字符串的數(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();//動(dòng)態(tài)建樹(shù)，也可以換成靜態(tài)
		p = p->next[del];
		i++;
	}
	if(p->id == -1)
		p->id = num++;
	return p->id;
}
  

?

POJ2513

題目大意：有n根筷子(n=250000)，每根筷子兩頭涂有顏色。現(xiàn)在問(wèn)能否將所有筷子連起來(lái)，并且每?jī)筛曜拥倪B接點(diǎn)顏色都相同。

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

?

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

1.判斷該圖是否連通；

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

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

?

POJ3630(1056)

題目大意：給出n個(gè)電話號(hào)碼(n=10000)，每個(gè)電話號(hào)碼長(zhǎng)度不超過(guò)10。要求是否滿(mǎn)足：每個(gè)電話號(hào)碼不能是其它號(hào)碼的前綴。

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

    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)在人們喜歡用縮寫(xiě)，比如 carbon 可以縮寫(xiě)為carb，但不能縮寫(xiě)為car。因?yàn)橛衏ar這個(gè)準(zhǔn)確的單詞。給你n個(gè)單詞(n=1000)，每個(gè)單詞長(zhǎng)度不超過(guò)20。求出每個(gè)單詞的最短縮寫(xiě)。

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

    #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樹(shù)