一 、前綴樹是什么

• 前綴樹是一種查找結(jié)構(gòu)，常用于指定字符串或是數(shù)組、線性表等連續(xù)信息的存儲和查找。
• 他的作用類似于哈希表，但是它相對于哈希表來說，限制更多，通用性較差，但是它的功能更加強(qiáng)大，可定制性也更強(qiáng)。
  leetcode指路：實(shí)現(xiàn)Trie(前綴樹)

二、簡單前綴樹的結(jié)構(gòu)分析

如需理解以下內(nèi)容，首先你需要了解樹的結(jié)構(gòu)；

我們提供的服務(wù)有：成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、站前ssl等。為數(shù)千家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的站前網(wǎng)站制作公司

1. 比如二叉樹，父節(jié)點(diǎn)之下包含兩個(gè)節(jié)點(diǎn)，分別為左右子節(jié)點(diǎn)，分別開辟空間，進(jìn)行數(shù)據(jù)存儲。
2. 前綴樹的結(jié)構(gòu)也是類似的，它的每個(gè)節(jié)點(diǎn)包含兩個(gè)部分: 值部分和指針部分。
3. 它的存儲方式為：在一棵樹上，從根到子節(jié)點(diǎn)，分別存儲所有目標(biāo)數(shù)據(jù)的每一個(gè)下標(biāo)位置上的數(shù)據(jù)
4. 值部分主要又包含兩個(gè)數(shù)據(jù): 路過該節(jié)點(diǎn)的數(shù)量為pass， 以該節(jié)點(diǎn)為結(jié)尾的數(shù)量為end。
5. 指針部分主要包含它的所有子節(jié)點(diǎn)，記為next

• 以存儲26個(gè)小寫英文字母為例，現(xiàn)在需要存儲英文單詞"ass"，則存儲路徑如下：
  
• 上圖中，每經(jīng)過一個(gè)節(jié)點(diǎn)，將該節(jié)點(diǎn)的pass值加一，將末尾節(jié)點(diǎn)的end值加一。通過這種操作記錄所有經(jīng)過的數(shù)據(jù)記錄。
• 同時(shí)在樹中，需要一個(gè)根節(jié)點(diǎn)來管理所有子節(jié)點(diǎn)，根節(jié)點(diǎn)中不存數(shù)據(jù)（除非是空字符串）
• 接下來就只需要用代碼將所有方法實(shí)現(xiàn)即可

下面給出實(shí)現(xiàn)，一共四個(gè)接口：

1. insert插入字符串，給前綴樹添加一組數(shù)據(jù)
2. find查找已存入的字符串個(gè)數(shù)
3. findContain輸入前綴查找已存在的前綴相同的字符串個(gè)數(shù)
4. erase從前綴樹中擦除一個(gè)字符串及其所存在數(shù)據(jù)

• 其中insert方法需要注意pass的數(shù)據(jù)增加
• erase方法需要注意的是：
  需要先檢查字符串是否存在；
  當(dāng)一個(gè)節(jié)點(diǎn)的經(jīng)過數(shù)量等于0時(shí)，即pass == 0時(shí)，代表其下沒有任何可能存在的字符串，所以直接將整棵樹刪除即可；
  移除節(jié)點(diǎn)時(shí)，需要提前寫好析構(gòu)函數(shù)，將其所有子節(jié)點(diǎn)的內(nèi)存全部釋放，以免出現(xiàn)內(nèi)存泄漏

代碼：

#includeusing namespace std;
//26 個(gè)小寫英文字母
#define NUMBER 26

// 節(jié)點(diǎn)的結(jié)構(gòu)
class TrieNode
{public:
	int pass;
	int end;
	TrieNode* nexts[NUMBER];
	TrieNode()
	{pass = 0;
		end = 0;
		for (int i = 0; i< NUMBER; i++)
		{	nexts[i] = nullptr;
		}
	}
	~TrieNode()
	{for (int i = 0; i< NUMBER; i++)
		{	if (nexts[i]) delete nexts[i];
		}
	}
};

// 所調(diào)用的樹結(jié)構(gòu)
class TrieTree
{TrieNode* root = nullptr;
public:
	TrieTree()
	{root = new TrieNode();
	}
	// 插入
	void insert(string word)
	{TrieNode* cur = root;
		cur->pass++;
		for (int i = 0; i< word.size(); i++)
		{	
			int num = word[i] - 'a';
			if (cur->nexts[num] == nullptr)
			{		cur->nexts[num] = new TrieNode();
			}
			cur = cur->nexts[num];
			cur->pass++;
		}
		cur->end++;
	}
	//查找字符串?dāng)?shù)量
	int find(string word)
	{TrieNode* cur = root;
		for (int i = 0; i< word.size(); i++)
		{	int num = word[i] - 'a';
			if (cur->nexts[num] == nullptr) return 0;

			cur = cur->nexts[num];
		}
		return cur->end;
	}
	//查找前綴數(shù)量
	int findContain(string word)
	{TrieNode* cur = root;
		for (int i = 0; i< word.size(); i++)
		{	int num = word[i] - 'a';
			if (cur->nexts[num] == nullptr) return 0;

			cur = cur->nexts[num];
		}
		return cur->pass;
	}
	//刪除
	bool erase(string word)
	{if (find(word) == 0) return false;
		TrieNode* cur = root;
		for (int i = 0; i< word.size(); i++)
		{	int num = word[i] - 'a';

			if (cur->nexts[num]->pass<= 1)
			{		delete cur->nexts[num];
				cur->nexts[num] = nullptr;
				return true;
			}
			cur = cur->nexts[num];
			cur->pass--;
		}
		cur->end--;
		return true;
	}
};

• 最后想說的是：這個(gè)樹結(jié)構(gòu)可以根據(jù)需求來進(jìn)行多樣式的處理；
• 上述方法是使用下標(biāo)作為數(shù)據(jù)進(jìn)行處理，如果需要實(shí)現(xiàn)大量不同的數(shù)據(jù)處理的話，可以考慮使用哈希表或其他結(jié)構(gòu)，如set容器，map容器等。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：C++實(shí)現(xiàn)前綴樹-創(chuàng)新互聯(lián)
文章鏈接：http://weahome.cn/article/disejd.html