javascript數據結構之二叉搜索樹實現方法

本文實例講述了javascript二叉搜索樹實現方法。分享給大家供大家參考，具體如下：

二叉搜索樹：顧名思義，樹上每個節點最多只有二根分叉；而且左分叉節點的值 < 右分叉節點的值。

特點：插入節點、找最大/最小節點、節點值排序非常方便

二叉搜索樹-javascript實現

<script type="text/javascript">

// <![CDATA[

//打印輸出

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();

//《沙特.算法設計技巧與分析》書上圖3.9 左側的樹

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>