什麼是字典樹？
- 叫字首樹更容易了解
- 字典樹的樣子
Trie樹（字典樹，單詞查找樹）
Trie又被稱為字首樹、字典樹，是以當然是一棵樹。上面這棵Trie樹包含的字元串集合是{in, inn, int, tea, ten, to}。每個節點的編号是我們為了描述友善加上去的。比如上圖中3号節點對應的路徑0123上的字元串是inn，8号節點對應的路徑0568上的字元串是ten。終結點與集合中的字元串是一一對應的。
Trie的兩個操作
1. 插入操作 insert（S）：将字元串S添加到Trie樹中
假設我們要插入字元串”in”。我們一開始位于根，也就是0号節點，我們用P=0表示。我們先看P是不是有一條辨別着i的連向子節點的邊。沒有這條邊，于是我們就建立一個節點，也就是1号節點，然後把1号節點設定為P也就是0号節點的子節點，并且将邊辨別為i。最後我們移動到1号節點，也就是令P=1。
這樣我們就把”in”的i字元插入到Trie中了。然後我們再插入字元n，也是先找P也就是1号節點有沒有标記為n的邊。還是沒有，于是再建立一個節點2，設定為P也就是1号節點的子節點，并且把邊辨別為n。最後再移動到P=2。這樣我們就把n也插入了。由于n是”in”的最後一個字元，是以我們還需要将P=2這個節點标記為終結點。