先前曾經提到：在樹狀結構中，節點（node）的分支度（degree）代表其子節點（child）數量。若是有一種樹狀結構至多只會有 n 個子節點，即樹中的任何節點分支度均小於或等於 n，則我們會將這種樹稱為一棵「n 元樹｣。
其中，大概就屬二元樹（binary tree）的應用最為廣泛。如上所述，其節點至多只會有兩個子節點。通常我們會直接將之稱為左子（left child）與右子（right child）。下圖是一棵二元樹：
在談應用之前，讓我們先來看看一個樹狀結構常見的操作：尋訪（traversal），也就是依照某種順序訪問樹中的所有節點。一般來說，常見的尋訪方式包含深度優先尋訪（depth-first traversal）與廣度優先尋訪（breadth-first traversal）。
以上面的樹狀圖來說明，深度優先尋訪會先從根節點 F 開始，走訪 F 的第一個子節點 B，再接著走訪 B 的第一個子節點 A。由於 A 不具有子節點，所以我們退回上一層，再接著走訪 B 的第二個子節點 D。完整的尋訪順序為：F B A D C E G I H。
而廣度優先尋訪相對於深度優先尋訪的不斷深入，是以層級順序（level-order）來進行尋訪。所以同樣由根節點 F 開始，走訪 F 的第一個子節點 B，再接著走訪 F 的第二個子節點 G。由於 F 只有兩個子節點，所以我們接著尋訪下一層 B 的子節點 A 與 D，然後是 G 的子節點 I。完整的尋訪順序為：F B G A D I C E H。
其中，二元樹又具有三種特殊的尋訪方式：前序（pre-order）、中序（in-order）、與後序（post-order）。若是把尋訪根節點、尋訪左子樹、尋訪右子樹分別記做 D、L、R，則前序的尋訪順序為 D L R、中序的尋訪順序為 L D R、後序的尋訪順序為 L R D。
以同樣的圖舉例的話，前序的尋訪順序為：F B A D C E G I H、中序的尋訪順序為：A B C D E F G H I、後序的尋訪順序為：A C E D B H I G F。（正確來說，二元樹只比一般的樹多了中序與後序兩種尋訪方式，因為前序尋訪與深度優先尋訪的順序其實是相同的。）
說完了尋訪，不過跟應用有什麼關聯呢？其中一個常見的用途是排序（sorting）。
我們可以定義一個特殊的二元樹：樹狀結構中，其左子樹所有節點所存的值必定小於根節點的值，且其右子樹所有節點所存的值必定大於等於根節點的值。如下圖：
有沒有發現，當我們用中序來尋訪這棵二元樹，我們便可以得到一個升序（ascending order）的數列。
若是根據定義，給出一個新增節點的操作：
Function insertNode(TreeNode root, Type value)
If root.value > value then
If root.hasLeftChild Then
insertNode(root.leftChild, value)
Else
root.leftChild = CreateNode(value)
Else
If root.hasRightChild Then
insertNode(root.rightChild, value)
Else
root.rightChild = CreateNode(value)
End
利用這個新增節點的操作，我們便可以將一堆資料建立成一棵符合定義的二元樹。於是，我們便可以利用這個操作，在加上中序尋訪來得到一串排序過的資料。
事實上，這種特殊的二元樹，被稱為二元搜尋樹（binary search tree）。其義如其名，這種二元樹也可以用以進行「已排序資料」的搜尋（search）。
根據定義我們可以得知：若是欲尋找的值小於二元搜尋樹的根節點，則其右子樹必定不可能出現欲尋找的值；同樣的，若是欲尋找的值大於二元搜尋樹的根節點，則其左子樹必定不可能出現欲尋找的值。而這種方式其實就跟二分搜尋法（binary search）的原理有異曲同工之妙。
我們可以定義搜尋的操作如下：
Function search(TreeNode root, Type value)
If root.value = value then
print "Found"
Else If root.value > value then
If root.hasLeftChild Then
search(root.leftChild, value)
Else
print "Not Found"
Else
If root.hasRightChild Then
search(root.rightChild, value)
Else
print "Not Found"
End
而這種利用二元搜尋樹的搜尋方式，其複雜度為 O(h)。其中 h 為樹的高度（height）。而若每棵子樹的左右子樹節點數量都相同（或差一），則 h 即等同於 lg n，也就是說搜尋的複雜度為 O(lg n)，與二分搜尋法相當。
由以上這些例子，可以知道「樹」不僅可以用來處理常見的排序與搜尋問題，還是種挺有效率的方式呢。
References：
