萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 資料結構與演算法:二元樹完整實作(遍歷、查找、插入、刪除)

二元樹基本定義

二元樹為 n (n≥0) 節點有限集:或為空樹,或由根節點 + 左右兩棵互不相交的二元樹組成。每節點度 ≤ 2,嚴格區分左/右子樹。

五種基本形態

  1. 空樹
  2. 僅根節點
  3. 僅左子樹
  4. 僅右子樹
  5. 左右子樹皆有

特殊二元樹

  • 斜樹:所有節點僅有左/右孩子,退化為鏈表。
  • 滿二元樹:深度 k,節點數 2^k - 1,所有葉子同層、所有分支節點雙子。
  • 完全二元樹:前 k-1 層滿,第 k 層葉子靠左連續,無右無左。
    滿二元樹必是完全二元樹,反之不成立。

完全二元樹判斷演算法(層序遍歷 + 隊列)


function isCompleteTree(root) {
  if (!root) return true;
  var queue = [root];
  var encounteredNull = false;

  while (queue.length) {
    var node = queue.shift();
    if (!node) {
      encounteredNull = true;
    } else {
      if (encounteredNull) return false; // 出現 null 後又有節點 → 不完全
      queue.push(node.left);
      queue.push(node.right);
    }
  }
  return true;
}

二元樹節點定義與基本操作


function Node(data, left, right) {
  this.data = data;
  this.left = left || null;
  this.right = right || null;
}
Node.prototype.show = function() { return this.data; };

三種深度優先遍歷(遞迴版)


// 前序:根 → 左 → 右
function preOrder(node) {
  if (!node) return;
  console.log(node.show());
  preOrder(node.left);
  preOrder(node.right);
}

// 中序:左 → 根 → 右
function inOrder(node) {
  if (!node) return;
  inOrder(node.left);
  console.log(node.show());
  inOrder(node.right);
}

// 後序:左 → 右 → 根
function postOrder(node) {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.show());
}

二元搜尋樹(BST)實作


function BST() {
  this.root = null;
}

BST.prototype.insert = function(data) {
  var n = new Node(data);
  if (!this.root) { this.root = n; return; }
  var current = this.root;
  while (true) {
    if (data < current.data) {
      if (!current.left) { current.left = n; return; }
      current = current.left;
    } else {
      if (!current.right) { current.right = n; return; }
      current = current.right;
    }
  }
};

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

BST.prototype.getMax = function() {
  var current = this.root;
  while (current.right) current = current.right;
  return current.data;
};

BST.prototype.find = function(data) {
  var current = this.root;
  while (current) {
    if (data === current.data) return current;
    current = data < current.data ? current.left : current.right;
  }
  return null;
};

// 中序遍歷即可得到排序序列
BST.prototype.inOrderTraverse = function(callback) {
  function traverse(node) {
    if (!node) return;
    traverse(node.left);
    callback(node);
    traverse(node.right);
  }
  traverse(this.root);
};

刪除節點(三種情況)

  1. 葉子節點:直接移除父節點對應指標。
  2. 單一子節點:用子節點取代被刪節點。
  3. 雙子節點:找右子樹最小節點(或左子樹最大)取代,再遞迴刪除該後繼節點。

BST.prototype.remove = function(data) {
  this.root = removeNode(this.root, data);
};

function removeNode(node, data) {
  if (!node) return null;
  if (data < node.data) {
    node.left = removeNode(node.left, data);
    return node;
  } else if (data > node.data) {
    node.right = removeNode(node.right, data);
    return node;
  } else { // 找到目標
    // 情況 1:葉子
    if (!node.left && !node.right) return null;
    // 情況 2:單一子節點
    if (!node.left) return node.right;
    if (!node.right) return node.left;
    // 情況 3:雙子節點
    var minRight = getMinNode(node.right);
    node.data = minRight.data;
    node.right = removeNode(node.right, minRight.data);
    return node;
  }
}
function getMinNode(node) {
  while (node.left) node = node.left;
  return node;
}

結語

二元樹是無數進階資料結構(紅黑樹、AVL、B-Tree、Trie、堆)的基石。熟練實作 BST 的增刪查與三種遍歷,並理解完全二元樹判斷邏輯,是演算法面試與高效能索引設計的必修課。

copyright © 萬盛學電腦網 all rights reserved