【雜記】漫談樹狀結構

　　在之前寫的「樹（tree）」這篇文章中，有網友提到：希望能夠瞭解 tree 能夠在應用上什麼問題上面。不過，由於我本身對樹的瞭解也很粗淺，所以這篇就野人獻曝一下，隨意講講一些我知道的東西。學得不甚透徹，可能會有些不完整或是錯誤的地方，就請各位別見怪囉 :P


　　先前曾經提到：在樹狀結構中，節點（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：

• Tree (data structure) - Wikipedia
• Binary tree - Wikipedia
• Tree traversal - Wikipedia
• Binary search tree - Wikipedia
• Tree - 演算法筆記
• 由樹的前序、中序、後序走法來談資料結構 - MMDays
• 二元樹在排序的應用 - MMDays
• 二元樹排序對搜尋的影響 - MMDays