javascript---データ構造(コード編)

データ構造
二叉の木
二叉の木の中序を巡回します.
二叉の木を与えて、その中の順を返します.

  : [1,null,2,3]
   1
    \
     2
    /
   3
  : [1,3,2]

まず復習します.
まず、ルートノード、左サブツリー、右サブツリーを巡回します.
中の順番は、左のサブツリー、ルートノード、右のサブツリーを巡回します.
左サブツリー、右サブツリー、ルートノードを巡回します.
再帰する

var inorderTraversal = function (root, array = []) {
      if (root) {
        inorderTraversal(root.left, array);
        array.push(root.val);
        inorderTraversal(root.right, array);
      }
      return array;
    };

 
再帰的に実現しない

は、ノードを対象として、

を巡回開始する.

1.左の子供がスタックに入る→左の子供が空のノード

まで.

.ノードスタック->は、ノード

にアクセスする.

.右の子供を対象としたノードで、1、2、3

を順次実行する.

var inorderTraversal = function (root) {
      const result = [];
      const stack = [];
      let current = root;
      while (current || stack.length > 0) {
        while (current) {
          stack.push(current);
          current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
      }
      return result;
    };

シングルチェーン表の実現

function LinkedList () {
  //Node          
  var Node = function (element) {
      this.element = element;;//        
      this.next = null;//              
  };

  var length = 0;//      
  var head = null;//          

  //         
  this.append = function (element) {
       var node = new Node(element),   //  Node 
           current;

       if (head === null) {// head   null，             
           head = node;
       } else {
           current = head; //        ，         
           while (current.next) {  
           // current.next   null ，             
               current = current.next;
           }
           current.next = node;
       }
   length++;
  };

  //        
 this.removeAt = function (position) {
     if (position > -1 && position < length) { //      
        var current = head,   // current              
           previous, index = 0;
        if (position === 0) {
           head = current.next;  //         ，  head       
        } else {
           while (index++ < position) {//          
               previous = current;
               current = current.next;
           }
           // previous current        ：  current，     
           previous.next = current.next;  
        }
        length--;
        return current.element;
     } else {
         return null;
     }   
 };

 //           
 this.insert = function (positon, element) {
     if (position >= 0 && position <= length) {//      
          var node = new Node(element);
          var index = 0, previous, current = head;
          if (position === 0) {//        
               node.next = current;
               head = node;
          } else {
               while (index++ < position) {
                   previous = current;
                   current = current.next;
               }
               node.next = current;
               previous.next = node;
          }
          length++;//      
          return true;
     } else {  
         return false;//      false
     }
 }; 

 // LinkedList          
 this.toString = function () {
     var current = head, //  
         string = '';
     while (current) {//        
         string += ', ' + current.element;//      
         current = current.next;     
     }
     return string.slice(1);
 };

 //indexOf  
 this.indexOf = function (element) {
     var current = head,
         index = 0;//     
     while (current) {//      
        if (element === current.element) {//              
           return index;
        }
        index++;
        current = current.next;
     }   
     return -1;
 };

 //   indexOf                
 this.remove = function (element) {
     var index = this.indexOf(element);
     return this.removeAt(element);
 };

 //isEmpty   size            
 this.isEmpty = function () {
     return length === 0;//         ，isEmpty     true，    false
 };
 this.size = function () {
     return length;
 };

 /**
  *head   LinkedList      
  *       LinkedList         ，    LinkedList     
  */
 this.getHead = function () {
     return head;
 };
 //    
 this.reverse=function(){
  let tempNode=null;
  let ansNode=head;
  while(head&&head.next){
      tempNode=head.next;
      head.next=tempNode.next;
      tempNode.next=ansNode;
      ansNode=tempNode;
      
  }
  return ansNode;
 }
}
let list=new LinkedList();
list.append(9);
list.append(8);
list.append(3);
list.append(5);
console.log(list.toString());
console.log(list.reverse());