12月 20, 2008

【演算】樹 - 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)等常見的樹結構。這些讓我們之後再一一進行說明。

5 回覆:

Bcswlmpke 提到...

請問有空可以用完整的程式範例來說明 Tree and Binary Tree嗎?謝謝

C.E.W. 提到...

你好, 請問你想要怎麼樣的範例來說明呢?
最近比較忙, 可能過些時候才能撥時間來寫^^"

Bcswlmpke 提到...

你好,我想要知道 tree and binary tree 可以應用在什麼樣的問題上面,因為光看說明並不是很了解。
你的blog很多有用的文章,我會常來看的。
有空再回就好,我先從其它資料結構的文章一一看起吧:)

C.E.W. 提到...

瞭解了, 屆時貼出來我們還可以再討論~
感謝你支持我寫的文章:)

Ruby Claire 提到...

Very innovative example. I thought it should be written in some other way. Anyhow its good though.




Graphs

張貼留言