JS実装のツリーアルゴリズムの完全な例

5706 ワード

この例では,JS実装のツリーアルゴリズムについて述べる.皆さんの参考にしてください.具体的には以下の通りです.



   20130328BinaryTree
   




  //           ,     
  //1     binary Tree =bt
  //1.1 node
  function Node() {        //bt  
    this.text = '';       //     
    this.leftChild = null;    //        
    this.rightild = null;     //       
  }
  //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 ;        //     
  var nodes = new Array();          //        ,         
  //               
  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();        //      
        //  
        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);    //         
      stack.isEmpty();   //false ,     
      //alert(stack.pop()); //  ,   1
      stack.isEmpty();   //true,      ,      stack.pop()       ,    
  //2.1    :
  function buildBt1(node, i) {
    var leftIndex = 2*i+1,             //        
      rightIndex = 2*i+2;             //        
    if(leftIndex < charecters.length) {       //            charecters     
      var childNode = new Node();         //          
      childNode.text = charecters[leftIndex];   //     
      node.leftChild = childNode;         //     node       
      buildBt1(childNode, leftIndex);      //       
    }
    if(rightIndex < charecters.length) {      //  
      var childNode = new Node();
      childNode.text = charecters[rightIndex];
      node.rightChild = childNode;
      buildBt1(childNode, rightIndex);
    }
  }
  //2.2     
  function buildBt2() {
    index = 0;               //   0  
    //             
    while(index < len) {
      var leftIndex = 2*index+1,       //         
        rightIndex = 2*index+2;       //         
      //          
      nodes[index].leftChild = nodes[leftIndex];
      //          
      nodes[index].rightChild = nodes[rightIndex];
      index++;
    }
  }
  //3  
  //3.1.1      
  function firstIteration(node) {
        if(node.leftChild) {          //            
          firstIteration(node.leftChild);  //     
        }
        if(node.rightChild) {         //            
          firstIteration(node.rightChild);  //     
        }
      }
      //       
      firstIteration(root);
  //3.1.2      
  function notFirstIteration(node) {
        var stack = new Stack(),         //         
          resultText = '';           //              
        stack.push(root);            //  root                      
        var node = root;
        resultText += node.text;
        while(!stack.isEmpty()) {
          while(node.leftChild) {       //              
            node = node.leftChild;      //           
            resultText += node.text;     //      
            stack.push(node);        //         
          }
          stack.pop();             //  
          node = stack.pop().rightChild;    //           (     )
          if(node) {              //            
            resultText += node.text;     //      
            stack.push(node);        //         
          }
          else {                //           
            node = stack.pop();       //       
          }
        }
      }
      //       
    //  notFirstIteration(root);
  //3.2.1      
  function btIteration21(node) {
    //     
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        btIteration21(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //     
    strText += node.text;
    //     
    if(node.rightChild) {
      if(node.rightChild.leftChild) {
        btIteration21(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
  }
  //   
  //2.1.1      
  var node = new Node();
  node.text = charecters[0];
  buildBt1(node, 0);  //  i  0    
  btIteration21(node);
  alert(strText);



JavaScriptに関する詳細について興味のある読者は、「JavaScriptデータ構造とアルゴリズムテクニック総括」、「JavaScript数学演算用法総括」、「JavaScriptソートアルゴリズム総括」、「JavaScript遍歴アルゴリズムとテクニック総括」、「JavaScript検索アルゴリズムテクニック総括」および「JavaScriptエラーとデバッグテクニック総括」のトピックを参照してください.
JavaScriptプログラムの設計に役立つことを願っています.