DIV CSS 佈局教程網

JavaScript 資料結構與演算法:二元樹完整解析
編輯:JavaScript綜合知識     

二元樹是資料結構中極為重要的一環,無論是排序、搜尋還是表達式的解析,都離不開它。本文將從二元樹的基本概念出發,逐步介紹它的形態分類、儲存結構、遍歷方式,最後以二元搜尋樹(BST)的實作收尾,幫助你建立完整的知識體系。

二元樹的概念

二元樹(Binary Tree)是由 n(n ≥ 0)個結點組成的有限集合。這個集合要麼是空集(即空二元樹),要麼由一個根結點,加上兩棵互不相交、分別稱為左子樹與右子樹的二元樹組成。

二元樹的特點

每個結點最多擁有兩棵子樹,因此二元樹中不存在度數大於 2 的結點。每一個節點都是一個物件,通常具備三個指標,分別指向父母、左孩子與右孩子。所有節點透過指標彼此相連,而這些相連的關係都是父子關係。

二元樹節點的定義

以結構化的方式來看,二元樹節點可以定義如下:

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

二元樹的五種基本形態

雖然擁有相同數量結點的普通樹型態有限,但由於二元樹需要區分左右,因此會衍生出五種基本形態:

  • 空二元樹
  • 只有一個根結點
  • 根結點只有左子樹
  • 根結點只有右子樹
  • 根結點同時擁有左子樹與右子樹

特殊的二元樹

斜樹

所有結點都只有單一子樹,整體偏向一側,形狀猶如斜坡。

滿二元樹

如果一棵二元樹的所有分支結點都同時擁有左子樹與右子樹,且所有葉子都分佈在同一層上,這樣的二元樹就稱為滿二元樹。

完全二元樹

完全二元樹是指最後一層左側是填滿的,右側可能填滿也可能未填滿,而其餘各層都是填滿的。一棵深度為 k、節點數量為 2^k − 1 的二元樹即為滿二元樹。完全二元樹具備以下特點:

  • 葉子結點只能出現在最下兩層。
  • 最下層的葉子一定集中在左部的連續位置。
  • 倒數第二層若有葉子結點,一定都在右部的連續位置。
  • 若結點度數為 1,則該結點只有左孩子。
  • 在相同節點數量的前提下,完全二元樹的深度最小。

請注意:滿二元樹一定是完全二元樹,但完全二元樹不一定是滿二元樹。判斷一棵樹是否為完全二元樹,可以透過廣度優先遍歷並把 NULL 節點也放入佇列來實作:

bool is_complete(tree *root)
{
    queue q;
    tree *ptr;
    // 進行廣度優先遍歷(層次遍歷),並把 NULL 節點也放入佇列
    q.push(root);
    while ((ptr = q.pop()) != NULL)
    {
        q.push(ptr->left);
        q.push(ptr->right);
    }

    // 判斷是否還有未被訪問到的節點
    while (!q.is_empty())
    {
        ptr = q.pop();
        // 有未訪問到的非 NULL 節點,則樹存在空洞,為非完全二元樹
        if (NULL != ptr)
        {
            return false;
        }
    }
    return true;
}

二元樹的性質

  • 性質一:在二元樹的第 i 層上,至多有 2^(i−1) 個結點(i ≥ 1)。
  • 性質二:深度為 k 的二元樹,至多有 2^k − 1 個結點(k ≥ 1)。

二元樹的儲存結構

順序儲存結構

順序儲存結構使用一維陣列來存放二元樹的各個結點,並讓結點的存放位置能反映結點之間的邏輯關係。

二叉鏈表

由於順序儲存的適用性不強,實務上通常採用鏈式儲存。二元樹每個結點最多有兩個孩子,因此為它設計一個資料域與兩個指標域是很自然的做法,我們稱這樣的鏈表為「二叉鏈表」。

二元樹的遍歷

二元樹的遍歷(traversing binary tree)是指從根結點出發,按照某種次序依次拜訪所有結點,使得每個結點被拜訪一次且仅一次。常見的遍歷方式有三種:

  • 前序遍歷(DLR):先拜訪根結點,再遍歷左子樹,最後遍歷右子樹。簡記為「根—左—右」。
  • 中序遍歷(LDR):先遍歷左子樹,再拜訪根結點,最後遍歷右子樹。簡記為「左—根—右」。
  • 後序遍歷(LRD):先遍歷左子樹,再遍歷右子樹,最後拜訪根結點。簡記為「左—右—根」。

前序遍歷

若二元樹為空則返回,否則先拜訪根結點,再前序遍歷左子樹,最後前序遍歷右子樹。遍歷順序為:A B D H I E J C F K G。

// 前序遍歷
function preOrder(node){
  if(node != null){
    putstr(node.show() + " ");
    preOrder(node.left);
    preOrder(node.right);
  }
}

中序遍歷

若樹為空則返回,否則先中序遍歷左子樹,再拜訪根結點,最後中序遍歷右子樹。遍歷順序為:H D I B E J A F K C G。

// 使用遞迴方式實作中序遍歷
function inOrder(node){
  if(node != null){
    inOrder(node.left);      // 先拜訪左子樹
    putstr(node.show() + " ");// 再拜訪根節點
    inOrder(node.right);     // 最後拜訪右子樹
  }
}

後序遍歷

若樹為空則返回,否則先遍歷左右子樹,最後拜訪根結點。遍歷順序為:H I D J E B K F G C A。

// 後序遍歷
function postOrder(node){
  if(node != null){
    postOrder(node.left);
    postOrder(node.right);
    putStr(node.show() + " ");
  }
}

實作二元搜尋樹(BST)

二元搜尋樹由節點組成,我們先定義一個 Node 節點物件:

function Node(data, left, right){
  this.data = data;
  this.left = left;   // 保存 left 節點連結
  this.right = right;
  this.show = show;
}

function show(){
  return this.data;   // 顯示保存在節點中的資料
}

查找最小值

在 BST 上查找最小值非常簡單,因為較小的值總是位於左子節點。只需沿著左子樹不斷往下走,直到找到最後一個節點即可。

function getMin(){
  var current = this.root;
  while(!(current.left == null)){
    current = current.left;
  }
  return current.data;
}

當遍歷到 BST 最左側的節點(即 current.left == null)時,該節點上保存的值就是最小值。

查找最大值

同理,查找最大值只需沿著右子樹不斷往下走,直到最後一個節點,該節點保存的值即為最大值。

function getMax(){
  var current = this.root;
  while(!(current.right == null)){
    current = current.right;
  }
  return current.data;
}
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved