何為前綴樹(shù)：又叫字典樹(shù)、單詞查找樹(shù)或鍵樹(shù)，是一種多叉樹(shù)結(jié)構(gòu)。如下圖

上圖是一棵Trie樹(shù)，表示了關(guān)鍵字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。從上圖可以歸納出Trie樹(shù)的基本性質(zhì)：

①根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符。?
②從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。?
③每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符互不相同。?

④從第一字符開(kāi)始有連續(xù)重復(fù)的字符只占用一個(gè)節(jié)點(diǎn)，比如上面的to，和ten，中重復(fù)的單詞t只占用了一個(gè)節(jié)點(diǎn)。

前綴樹(shù)的結(jié)構(gòu)定義：path，end，next

前綴樹(shù)的插入操作：插入操作解析：首先呢？先判斷word是否為空，空的話就直接放回空了；

如果不為空的話，先將word字符串轉(zhuǎn)換為字符數(shù)組，定義一個(gè)類型為T(mén)rieTree的node。

然后呢，用index來(lái)代表要去檢查的路徑（注意index 的由來(lái)），如果index這條路徑為空的話，那么就給他新建一個(gè)節(jié)點(diǎn)；

并且node節(jié)點(diǎn)繼續(xù)往下級(jí)走，path++，最后遍歷完整個(gè)數(shù)組之后再end++（表示有多少個(gè)以他結(jié)尾的字符串）。

前綴樹(shù)的查找操作：

前綴樹(shù)的刪除操作：

前綴樹(shù)的前綴字符匹配操作：

歡迎來(lái)討論~

總結(jié)

以上是生活随笔為你收集整理的树结构-------前缀树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。