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 child和right 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中的map和set。
  • 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,