DIV CSS 佈局教程網

JavaScript 資料結構實作:二叉搜尋樹完整範例
編輯:關於JavaScript     

二叉搜尋樹(Binary Search Tree)顧名思義,每個節點最多只有左右兩個分支,且左子節點的值必定小於右子節點的值。這個特性讓插入節點、尋找最大/最小值、以及排序輸出都變得非常直覺——只要做一次中序遍歷,就能得到由小到大的有序序列。

以下用 JavaScript 完整實作節點類別與樹的操作,包含插入、最小值、最大值,以及中序、先序、後序三種遍歷。

<script type="text/javascript">
// 簡單的輸出函式
function println(msg) {
  document.write(msg + " ");
}

// 節點類別
var Node = function (v) {
  this.data  = v;      // 節點值
  this.left  = null;   // 左節點
  this.right = null;   // 右節點
};

// 二叉搜尋樹類別
var BinarySearchTree = function () {
  this.root = null;    // 初始化時根節點為空

  // 插入節點,參數 v 為節點值
  this.insert = function (v) {
    var newNode = new Node(v);
    if (this.root == null) {   // 樹為空時,新節點直接成為根
      this.root = newNode;
      return;
    }
    var currentNode = this.root;   // 工作指針,從根往下找
    var parentNode = null;
    while (true) {
      parentNode = currentNode;
      if (v < currentNode.data) {  // 比當前節點小,往左走
        currentNode = currentNode.left;
        if (currentNode == null) {
          parentNode.left = newNode;
          return;
        }
      } else {                     // 否則往右走
        currentNode = currentNode.right;
        if (currentNode == null) {
          parentNode.right = newNode;
          return;
        }
      }
    }
  };

  // 尋找最小節點:一路往左到底
  this.min = function () {
    var p = this.root;
    while (p != null && p.left != null) { p = p.left; }
    return p;
  };

  // 尋找最大節點:一路往右到底
  this.max = function () {
    var p = this.root;
    while (p != null && p.right != null) { p = p.right; }
    return p;
  };

  // 中序遍歷:左 → 根 → 右(結果為遞增序列)
  this.inOrder = function (rootNode) {
    if (rootNode != null) {
      this.inOrder(rootNode.left);
      println(rootNode.data);
      this.inOrder(rootNode.right);
    }
  };

  // 先序遍歷:根 → 左 → 右
  this.preOrder = function (rootNode) {
    if (rootNode != null) {
      println(rootNode.data);
      this.preOrder(rootNode.left);
      this.preOrder(rootNode.right);
    }
  };

  // 後序遍歷:左 → 右 → 根
  this.postOrder = function (rootNode) {
    if (rootNode != null) {
      this.postOrder(rootNode.left);
      this.postOrder(rootNode.right);
      println(rootNode.data);
    }
  };
};

// 測試
var bTree = new BinarySearchTree();
bTree.insert(6);
bTree.insert(3);
bTree.insert(8);
bTree.insert(1);
bTree.insert(4);
bTree.insert(9);

println('中序遍歷:');   bTree.inOrder(bTree.root);   println("<br/>");
println("先序遍歷:");   bTree.preOrder(bTree.root);  println("<br/>");
println("後序遍歷:");   bTree.postOrder(bTree.root); println("<br/>");

var minNode = bTree.min();
println("最小節點:" + (minNode == null ? "不存在" : minNode.data));
println("<br/>");
var maxNode = bTree.max();
println("最大節點:" + (maxNode == null ? "不存在" : maxNode.data));
// ]]>
</script>

實際輸出結果:

中序遍歷: 1 3 4 6 8 9
先序遍歷: 6 3 1 4 8 9
後序遍歷: 1 4 3 9 8 6
最小節點:1
最大節點:9

從輸出可以驗證:中序遍歷的結果正好是升冪排序,這也是搜尋樹最實用的性質之一。另外要留意,以上是最基礎的版本,沒有做平衡處理;當插入資料本身已接近有序時,樹會退化成一條鏈表,查詢複雜度從 O(log n) 掉到 O(n)。若要在 production 環境使用,建議進一步實作 AVL 樹或紅黑樹,並補上刪除節點的操作。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved