DIV CSS 佈局教程網

JavaScript 資料結構與演算法:二叉樹詳解
編輯:JavaScript基礎知識     

二叉樹是資料結構中非常基礎且重要的主題。它由節點與分支組成,每個節點最多擁有兩個子節點,分別稱為左子樹與右子樹。二叉樹廣泛應用於表達式解析、搜尋結構、排序演算法與檔案系統等場景。

二叉樹的概念

二叉樹是 n 個節點的有限集合。這個集合可能為空,也可能由一個根節點,以及左右兩棵互不相交的二叉樹組成。

二叉樹的特點

  • 每個節點最多有兩個子節點。
  • 不存在度數大於 2 的節點。
  • 節點之間透過指標或引用互相連接。
  • 左右子樹具有明確順序,不能隨意交換。

二叉樹節點的定義

以結構化方式表示時,二叉樹節點通常包含資料與左右子節點參考:

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

在 JavaScript 中,也可以用物件來表示節點:

function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}

function show() {
  return this.data;
}

二叉樹的五種基本形態

二叉樹可以呈現多種形態,基本可概括為:

  1. 空二叉樹。
  2. 只有一個根節點。
  3. 根節點只有左子樹。
  4. 根節點只有右子樹。
  5. 根節點同時擁有左子樹與右子樹。

特殊二叉樹

斜樹

若所有節點都只有左子樹或都只有右子樹,會形成類似鏈表狀的斜樹。

滿二叉樹

若二叉樹中每個分支節點都有左右子樹,且所有葉節點都在同一層,則稱為滿二叉樹。

完全二叉樹

完全二叉樹是指除了最後一層之外,其他層都是滿的,且最後一層的葉節點集中在左側連續位置。

完全二叉樹的特性包括:

  • 葉節點只能出現在最後兩層。
  • 最後一層的葉節點集中在左側。
  • 倒數第二層若有葉節點,會集中在右側連續位置。
  • 若某節點度數為 1,則它只有左孩子。

二叉樹的性質

二叉樹有兩個重要性質:

  1. 第 i 層最多有 2 的 (i - 1) 次方個節點。
  2. 深度為 k 的二叉樹最多有 2 的 k 次方減 1 個節點。

二叉樹的儲存結構

順序儲存結構

順序儲存結構使用一維陣列來存放二叉樹節點,並透過索引位置來表示節點之間的關係。

二叉鏈表

由於順序儲存對非完全二叉樹較不友善,實務上更常使用鏈式儲存。每個節點包含資料域、左子節點指標與右子節點指標。

二叉樹的遍歷

遍歷是指按照某種順序訪問二叉樹中的所有節點,且每個節點只被訪問一次。常見方式有三種:

  1. 前序遍歷:根、左、右。
  2. 中序遍歷:左、根、右。
  3. 後序遍歷:左、右、根。

前序遍歷

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

中序遍歷

// 中序遍歷
function inOrder(node) {
  if (node) {
    inOrder(node.left);
    putstr(node.show() + ' ');
    inOrder(node.right);
  }
}

後序遍歷

// 後序遍歷
function postOrder(node) {
  if (node) {
    postOrder(node.left);
    postOrder(node.right);
    putstr(node.show() + ' ');
  }
}

二叉查找樹

二叉查找樹,又稱 BST,是一種特殊的二叉樹。它要求左子樹上的所有節點值小於根節點,右子樹上的所有節點值大於根節點。這種特性讓搜尋、插入與刪除都能保持較高效率。

查找最小值與最大值

在二叉查找樹中,最小值一定位於左子樹最左側,最大值一定位於右子樹最右側。

查找最小值

function getMin() {
  var current = this.root;

  while (current.left !== null) {
    current = current.left;
  }

  return current.data;
}

查找最大值

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