JS實現(xiàn)的二叉樹算法完整實例

更新時間：2017年04月06日 08:51:52 作者：夏遠(yuǎn)

這篇文章主要介紹了JS實現(xiàn)的二叉樹算法,結(jié)合完整實例形式分析了基于JS定義、創(chuàng)建二叉樹及常用的各種遍歷、訪問二叉樹操作技巧,需要的朋友可以參考下

本文實例講述了JS實現(xiàn)的二叉樹算法。分享給大家供大家參考，具體如下：

<!DOCTYPE HTML>
<head>
   <title>20130328BinaryTree</title>
   <metahttp-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<html>
<body>
<script>
  //今天學(xué)習(xí)了下二叉樹算法，總結(jié)在這里
  //1全局變量 binary Tree =bt
  //1.1 node
  function Node() {        //bt節(jié)點
    this.text = '';       //節(jié)點的文本
    this.leftChild = null;    //節(jié)點的左孩子引用
    this.rightild = null;     //節(jié)點右孩子引用
  }
  //1.2 二叉樹裝載的字符串
  var strText = "";
  var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
  var len = charecters.length ;        //數(shù)組的長度
  var nodes = new Array();          //創(chuàng)建一個臨時數(shù)組，用于存放二叉樹節(jié)點
  //循環(huán)創(chuàng)建二叉樹節(jié)點存放到數(shù)組中
  for (var i = 0 ; i < len ; i++) {
    var node = new Node();
    node.text = charecters[i];
    nodes.push(node);
  }
  var root = nodes[0];
  //1.3 棧
  function Stack() {
        var stack = new Array();        //存放棧的數(shù)組
        //壓棧
        this.push = function(o) {
          stack.push(o);
        };
        //出棧
        this.pop = function() {
          var o = stack[stack.length-1];
          stack.splice(stack.length-1, 1);
          return o;
        };
        //檢查棧是否為空
        this.isEmpty = function() {
          if(stack.length <= 0) {
            return true;
          }
          else {
            return false;
          }
        };
      }
      //使用方式如下
      var stack = new Stack();
      stack.push(1);    //現(xiàn)在棧中有一個元素
      stack.isEmpty();   //false , 棧不為空
      //alert(stack.pop()); //出棧, 打印1
      stack.isEmpty();   //true, 此時棧為空，因為在調(diào)用了stack.pop()之后元素出棧了，所以為空
  //2.1遞歸實現(xiàn)：
  function buildBt1(node, i) {
    var leftIndex = 2*i+1,             //左孩子節(jié)點的索引
      rightIndex = 2*i+2;             //右孩子節(jié)點的索引
    if(leftIndex < charecters.length) {       //判斷索引的長度是否超過了charecters數(shù)組的大小
      var childNode = new Node();         //創(chuàng)建一個新的節(jié)點對象
      childNode.text = charecters[leftIndex];   //給節(jié)點賦值
      node.leftChild = childNode;         //給當(dāng)前節(jié)點node加入左孩子節(jié)點
      buildBt1(childNode, leftIndex);      //遞歸創(chuàng)建左孩子
    }
    if(rightIndex < charecters.length) {      //同上
      var childNode = new Node();
      childNode.text = charecters[rightIndex];
      node.rightChild = childNode;
      buildBt1(childNode, rightIndex);
    }
  }
  //2.2非遞歸實現(xiàn)
  function buildBt2() {
    index = 0;               //索引從0開始
    //循環(huán)建立二叉樹子節(jié)點的引用
    while(index < len) {
      var leftIndex = 2*index+1,       //當(dāng)前節(jié)點左孩子索引
        rightIndex = 2*index+2;       //當(dāng)前節(jié)點右孩子索引
      //給當(dāng)前節(jié)點添加左孩子
      nodes[index].leftChild = nodes[leftIndex];
      //給當(dāng)前節(jié)點添加右孩子
      nodes[index].rightChild = nodes[rightIndex];
      index++;
    }
  }
  //3遍歷
  //3.1.1先序遞歸遍歷
  function firstIteration(node) {
        if(node.leftChild) {          //判斷當(dāng)前節(jié)點是否有左孩子
          firstIteration(node.leftChild);  //遞歸左孩子
        }
        if(node.rightChild) {         //判斷當(dāng)前節(jié)點是否有右孩子
          firstIteration(node.rightChild);  //遞歸右孩子
        }
      }
      //遞歸遍歷二叉樹
      firstIteration(root);
  //3.1.2先序普通遍歷
  function notFirstIteration(node) {
        var stack = new Stack(),         //開辟一個新的棧對象
          resultText = '';           //存放非遞歸遍歷之后的字母順序
        stack.push(root);            //這個root在上面非遞歸方式構(gòu)建二叉樹的時候已經(jīng)構(gòu)建好的
        var node = root;
        resultText += node.text;
        while(!stack.isEmpty()) {
          while(node.leftChild) {       //判斷當(dāng)前節(jié)點是否有左孩子節(jié)點
            node = node.leftChild;      //取當(dāng)前節(jié)點的左孩子節(jié)點
            resultText += node.text;     //訪問當(dāng)前節(jié)點
            stack.push(node);        //將當(dāng)前節(jié)點壓入棧中
          }
          stack.pop();             //出棧
          node = stack.pop().rightChild;    //訪問當(dāng)前節(jié)點的兄弟節(jié)點（右孩子節(jié)點）
          if(node) {              //當(dāng)前節(jié)點的兄弟節(jié)點不為空
            resultText += node.text;     //訪問當(dāng)前節(jié)點
            stack.push(node);        //將當(dāng)前節(jié)點壓入棧中
          }
          else {                //當(dāng)前節(jié)點的兄弟節(jié)點為空
            node = stack.pop();       //在回溯到上一層
          }
        }
      }
      //非遞歸先序遍歷
    //  notFirstIteration(root);
  //3.2.1中序遞歸遍歷
  function btIteration21(node) {
    //訪問左節(jié)點
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        btIteration21(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //訪問根節(jié)點
    strText += node.text;
    //訪問右節(jié)點
    if(node.rightChild) {
      if(node.rightChild.leftChild) {
        btIteration21(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
  }
  //測試區(qū)
  //2.1.1測試遞歸實現(xiàn)
  var node = new Node();
  node.text = charecters[0];
  buildBt1(node, 0);  //索引i是從0開始構(gòu)建
  btIteration21(node);
  alert(strText);
</script>
</body>
</html>

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

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

您可能感興趣的文章: