<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Prefix Tree(Trie Tree) - 前綴樹 -------- #### 描述 前綴樹是一種支持在一個英文單詞集合中快速查詢是否包含某個單詞，或者包含某個前綴的一些單詞的數據結構，或者記錄某個單詞出現過的次數。 為了簡化問題，本問題假設字典中只會出現$$ a - z $$這$$ 26 $$個小寫字母，前綴樹中每個節點都包含$$ 26 $$個孩子節點，將跟節點的孩子節點作為所有單詞的首字母，向下查找直到跟節點就可以得到完整的單詞。一個包含$$ boy $$、$$ dog $$、$$ bible $$、$$ bill $$的前綴樹如圖：  這樣每次查找單詞時，按照前綴從根節點開始向下匹配每個孩子節點的字符即可。前綴樹查找一個長度為$$ n $$的單詞的時間復雜度為$$ O(n) $$。 -------- #### 源碼 [PrefixTree.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/PrefixTree.h) [PrefixTree.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/PrefixTree.cpp) #### 測試 [PrefixTreeTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/PrefixTreeTest.cpp)