前注：本文的實(shí)現(xiàn)參考了此 Github 倉庫: https://github.com/Blightmud/rs-complete

實(shí)現(xiàn)目標(biāo)

先引用 rs-complete 項(xiàng)目 README 中的一段文字來說明本文的實(shí)現(xiàn)目標(biāo)：

假如我們有一個(gè)詞庫（能看出該項(xiàng)目的作者挺喜歡蝙蝠俠的）

我們使用這個(gè)詞庫，以每個(gè)字母為節(jié)點(diǎn)，構(gòu)建一顆樹，如下所示：

然后，我們使用單詞片段batm進(jìn)行查找，可以通過遍歷這顆樹來得到：

實(shí)現(xiàn)原理解釋

單詞插入

現(xiàn)在，讓我們假設(shè)存在一顆空樹，

我們需要插入一個(gè)單詞 "abcd"，由于當(dāng)前樹為空，我們可以很簡(jiǎn)單地遍歷這個(gè)單詞，將每一個(gè)字母新建節(jié)點(diǎn)，插入到樹中。

讓我們?cè)俨迦胍粋€(gè)單詞 "befg"，步驟與之前插入單詞類似，遍歷這個(gè)單詞，并插入到樹中。

讓我們?cè)俨迦胍粋€(gè)單詞 "abef"，步驟與之前插入單詞類似，遍歷這個(gè)單詞，并插入到樹中。

使用單詞片段查找

讓我們復(fù)用上面的這棵樹，嘗試使用單詞片段ab進(jìn)行查找。

在對(duì)單詞片段進(jìn)行遍歷后，我們得到了需要遍歷的子樹。

對(duì)這棵子樹進(jìn)行遍歷，我們就可以獲得用來補(bǔ)全單詞片段ab的字符串?dāng)?shù)組：

代碼實(shí)現(xiàn)

節(jié)點(diǎn)定義

注：由于我們是通過將單詞拆分成單獨(dú)的字母來作為節(jié)點(diǎn)進(jìn)行存儲(chǔ)，且字母本身是具有有序性的，因此在這里使用 TreeMap(BTreeMap in Rust) 的方式存儲(chǔ)數(shù)據(jù)。

節(jié)點(diǎn)方法實(shí)現(xiàn)

新建

插入

補(bǔ)全

根節(jié)點(diǎn)的定義及實(shí)現(xiàn)

這里只是對(duì)上文中節(jié)點(diǎn)方法的封裝，就不過多闡述了。

測(cè)試代碼

結(jié)果：

完整代碼