Binary Tree: Intro(簡介)

Posted by Chiu CC on 12 21, 2015


先備知識與注意事項

接續上一篇談到的Tree(樹),這篇文章將介紹Tree的其中一支大宗:Binary Tree


目錄


Binary Tree

最廣義的樹(Tree)對於樹上的node之child數目沒有限制,因此,每個node可以有多個child。


general_tree

圖一:這是一棵樹(Tree)

若限制node只能有兩個child,等價於「樹上的每一個node之degree皆為2」,此即稱為Binary Tree(二元樹),並稱兩個child pointer為left childright child


binary_tree

圖二:這是一棵Binary Tree。


程式碼

修改在Tree(樹)提供的程式實作方式,將node的child pointer設為left child與right child,以滿足Binary Tree的形式。

另外,在class TreeNode有個TreeNode *parent,顧名思義,即是指向該node之parent的pointer,以圖二為例,B的parent pointer即指向A。

  • Binary Tree的node未必需要parent pointer(或稱為parent field),不過加入parent後,對樹的資料處理如inorder traversal(中序尋訪)、node deletion(刪除node)、以及任何需要back-tracing(回溯路徑)的操作時,會更加有效率。

// 以C++為例
class Tree;
class TreeNode{
    TreeNode *leftchild;         
    TreeNode *rightchild;       
    TreeNode *parent;           
    int data1;                  
    double data2;
    ...
    friend class Tree;
};
class Tree{
    TreeNode *root;             // 以root作為存取整棵樹的起點
};


Full & Complete Binary Tree

有兩類Binary Tree十分常見,分別為Full Binary Tree以及Complete Binary Tree
(這裡不知該翻作「完滿二元樹」還是「完整二元樹」,所以就不做翻譯當作專有名詞,請見諒。)

A. Full Binary Tree:

如圖三所示,一棵Full Binary Tree(或稱作Perfect Binary Tree)具有以下性質:

  • 所有internal node都有兩個subtree(也就是兩個child pointer);
  • 所有leaf node具有相同的level(或相同的height)。

由以上性質能夠推論出:

  • 若一棵Full Binary Tree的leaf node之level為\(n\),整棵樹共有\(2^n-1\)個node。
  • 例如,若leaf node的level為4, 整棵樹共有15個node。

並且,每個node與其child有以下關係:

  • \(i\)個node的left child之index為 \(2i\)
  • \(i\)個node的right child之index為 \(2i+1\)
  • 除了root之parent為NULL之外,第\(i\)個node的parent之index為 \(\lfloor {i\over2} \rfloor\)

Full Binary Tree

圖三:若一棵Full Binary Tree的leaf node之level為\(n\),整棵樹共有\(2^n-1\)個node。



B. Complete Binary Tree:

若一棵樹的node按照Full Binary Tree的次序排列(由上至下,由左至右),則稱此樹為Complete Binary Tree

以圖四及圖五作說明:

圖四的樹共有10個node,且這十個node正好填滿Full Binary Tree的前十個位置,則此樹為Complete Binary Tree。

Complete Binary Tree

圖四:這是一棵Complete Binary Tree。

圖五的樹共有11個node,但是第11個node(K)應該要是第5個node(E)的child,因此,此樹並非Complete Binary Tree。

Not Complete Binary Tree

圖五:這不是一棵Complete Binary Tree。



學習Binary Tree的未來出路

如果有家長擔心小孩子學了Binary Tree之後對未來的出路沒有幫助,這裡有網路大神在StackOverFlow開示,以下簡單翻譯幾項Binary Tree的應用:

  • Binary Search Tree(BST):在某些資料經常要增加、刪除的應用中,BST常用來做搜尋,例如許多程式語言的Library中的mapset
  • Binary Space Partition:應用於幾乎所有的3D電玩遊戲以決定哪些物件需要rendered。
  • Binary Tries:應用於大多數high-bandwidth router(高頻寬路由器)以儲存router-tables。
  • Heaps:用以實現高效率的priority queues(優先權佇列),許多作業系統用來安排工作程序。
  • Huffman Coding Tree:例如.jpeg、.mp3等壓縮技術皆使用Huffman編碼。(在一顆20MB的硬碟要價新台幣一萬元的時代,壓縮技術就是救世主。)

以及其他應用(記得點進連結瞻仰大神風範)。

下一篇文章將介紹Binary Tree(以及往後主題)中最基本的操作:traversal(尋訪),顧名思義,就是如何在樹中移動,有了traversal之後再進一步探討search(搜尋)、insertion(新增node)、deletion(刪除node)、sorting(排序)會更加容易。



參考資料:


Binary Tree系列文章

Binary Tree: Intro(簡介)
Binary Tree: Traversal(尋訪)
Binary Tree: 建立一棵Binary Tree

回到目錄:

目錄:演算法與資料結構


tags: C++, Binary Tree, Intro,