欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

javascript數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹實(shí)現(xiàn)方法

 更新時(shí)間：2015年11月25日 15:04:18   作者：菩提樹下的楊過  
這篇文章主要介紹了javascript數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹實(shí)現(xiàn)方法,較為詳細(xì)的分析了二叉搜索樹的概念、原理與JavaScript實(shí)現(xiàn)二叉搜索樹的方法,對于學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)具有一定參考借鑒價(jià)值,需要的朋友可以參考下

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

二叉搜索樹：顧名思義，樹上每個(gè)節(jié)點(diǎn)最多只有二根分叉；而且左分叉節(jié)點(diǎn)的值 < 右分叉節(jié)點(diǎn)的值 。

特點(diǎn)：插入節(jié)點(diǎn)、找最大/最小節(jié)點(diǎn)、節(jié)點(diǎn)值排序 非常方便

二叉搜索樹-javascript實(shí)現(xiàn)

<script type="text/javascript">
// <![CDATA[
 //打印輸出
 function println(msg) {
  document.write(msg + " ");
 }
 //節(jié)點(diǎn)類
 var Node = function (v) {
  this.data = v; //節(jié)點(diǎn)值
  this.left = null; //左節(jié)點(diǎn)
  this.right = null; //右節(jié)點(diǎn)
 }
 //二叉搜索樹類
 var BinarySearchTree = function () {
  this.root = null; //初始化時(shí),根節(jié)點(diǎn)為空
  //插入節(jié)點(diǎn)
  //參數(shù)：v 為節(jié)點(diǎn)的值
  this.insert = function (v) {
   var newNode = new Node(v);
   if (this.root == null) {
    //樹為空時(shí)，新節(jié)點(diǎn)，直接成為根節(jié)點(diǎn)
    this.root = newNode;
    return;
   }
   var currentNode = this.root; //工作“指針”節(jié)點(diǎn)（從根開始向下找）
   var parentNode = null;
   while (true) {
    parentNode = currentNode;
    if (v < currentNode.data) {
     //當(dāng)前節(jié)點(diǎn)的值 > 目標(biāo)節(jié)點(diǎn)的值     
     //應(yīng)該向左插，工作節(jié)點(diǎn)移到左節(jié)點(diǎn)
     currentNode = currentNode.left;
     if (currentNode == null) {
      //沒有左節(jié)點(diǎn)，則新節(jié)點(diǎn)，直接成為左節(jié)點(diǎn)
      parentNode.left = newNode;
      return; //退出循環(huán)
     }
    }
    else {
     //否則向右插，工作節(jié)點(diǎn)移到右節(jié)點(diǎn)
     currentNode = currentNode.right;
     if (currentNode == null) {
      parentNode.right = newNode;
      return;
     }
    }
   }
  }
  //查找最小節(jié)點(diǎn)
  this.min = function () {
   var p = this.root; //工作節(jié)點(diǎn) 
   while (p != null && p.left != null) {
    p = p.left;
   }
   return p;
  }
  //查找最大節(jié)點(diǎn)
  this.max = function () {
   var p = this.root; //工作節(jié)點(diǎn) 
   while (p != null && p.right != null) {
    p = p.right;
   }
   return p;
  }
  //中序遍歷
  this.inOrder = function (rootNode) {
   if (rootNode != null) {
    this.inOrder(rootNode.left); //先左節(jié)點(diǎn)
    println(rootNode.data); //再根節(jié)點(diǎn)
    this.inOrder(rootNode.right); //再右節(jié)點(diǎn)
   }
  }
  //先序遍歷
  this.preOrder = function (rootNode) {
   if (rootNode != null) {
    println(rootNode.data); //先根
    this.preOrder(rootNode.left); //再左節(jié)點(diǎn)
    this.preOrder(rootNode.right); //再右節(jié)點(diǎn)
   }
  }
  //后序遍歷
  this.postOrder = function (rootNode) {
   if (rootNode != null) {
    this.postOrder(rootNode.left); //先左節(jié)點(diǎn)
    this.postOrder(rootNode.right); //再右節(jié)點(diǎn)
    println(rootNode.data); //再根節(jié)點(diǎn)
   }
  }
 }
 //以下是測試
 var bTree = new BinarySearchTree();
 //《沙特.算法設(shè)計(jì)技巧與分析》書上圖3.9 左側(cè)的樹
 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("最小節(jié)點(diǎn)：" + (minNode == null ? "不存在" : minNode.data));
 println("<br/>");
 var maxNode = bTree.max();
 println("最大節(jié)點(diǎn)：" + (maxNode == null ? "不存在" : maxNode.data));
// ]]>
</script>
<!--中序遍歷： 1 3 4 6 8 9 <br> 先序遍歷： 6 3 1 4 8 9 <br> 后序遍歷： 1 4 3 9 8 6 <br> 最小節(jié)點(diǎn)：1 <br> 最大節(jié)點(diǎn)：9-->

輸出結(jié)果：

中序遍歷： 1 3 4 6 8 9 
先序遍歷： 6 3 1 4 8 9 
后序遍歷： 1 4 3 9 8 6 
最小節(jié)點(diǎn)：1 
最大節(jié)點(diǎn)：9

希望本文所述對大家JavaScript程序設(shè)計(jì)有所幫助。

相關(guān)文章

最新評(píng)論