【演算】樹 - Tree

　　樹(tree)是一種資料結構(data structure)，也就是我們一般所謂的「樹狀結構」或「樹狀圖」，為一個由根(root)向下延伸到葉子(leaf)的圖(graph)。




　　一棵樹由多個節點(node)，以及連結各節點的邊(edge)所組成。

　　如同上面所提及的，樹的最頂層有一個唯一的根節點(root node)，也就是上圖的節點 A，以及最末端的葉節點(leaf node)，如上圖的節點 K、J、F、L、O、P。除了這些節點外，其餘的節點被稱為內部節點(internal node)。


　　每個節點都有其階層(level)、高度(height)以及深度(depth)。節點的階層代表節點間的世代關係，以根節點為第 1 階層，其子節點為第 2 階層，再下層為第 3 階層......，以此類推；節點的高度為節點到向下最遠葉節點的距離；而深度則為節點到根節點的距離。以上圖為例，G 節點的階層為 3、高度為 2、深度為 2。


　　而與節點連接的上層節點被稱為父節點(parent node)，如上圖中的 G 即為 L 與 M 的父節點；與節點連接的下層結點被稱為子節點(child node)，如上圖的 N 即為 H 的子節點。

　　且對於每一節點而言，除了根節點不具有父節點之外，其他節點都恰有一個父節點，及零個以上的子節點(葉節點不具有子節點)。除此之外，具有相同父節點的節點，則被稱為兄弟節點(sibling node)，如上圖中的 D、E、F。


　　最後，節點的分支度(degree)代表子節點數量，如 A 節點的分支度為 2、B 節點的分支度為 3、C 節點的分支度為 2。


　　若就程式的觀點來看，樹是一個包含了其資料內容與 n (≧ 0)個指向子節點的指標的結構。一個樹的節點宣告方式大致如下：

struct Node
{
    Type data;
    Node *next1;
    Node *next2;
    Node *next3;
        .
        .
        .
    Node *nextN;
}

　　而「樹」本身，只不過是一個總括的概念，其本身又可以細分為如二元樹(binary tree)等常見的樹結構。這些讓我們之後再一一進行說明。