JS中的数据结构与算法

二叉树层序遍历

二叉树结构

      // 先建立一棵二叉树
      function Tree() {
          // 定义树结点
          var Node = function(element) {
              this.element = element;
              this.left = null;
              this.right = null;
          }
          // 定义根结点
          var root = null;
      }

node节点和DOM节点的前序遍历

      // 前序遍历 根左右 
      Tree.prototype.preOrderTraverse = function(callback) {
          // callback为每个节点进行的回调操作
          preOrder(root, callback);
      }
      // 普通节点的前序递归遍历
      var preOrder = function(node, callback) {
          if (node !== null) {
              // node.element为当前节点
              callback(node.element);
              // node.left，node.right为左右子节点
              preOrder(node.left, callback);
              preOrder(node.right, callback);
          }
      }
      // DOM二叉树的前序遍历 递归方法=>深度优先遍历的特例
      var preOrder = function(node,callback) {  
          callback(node);  
          if(node.firstElementChild) {//先判断子元素节点是否存在  
              this.preOrder(node.firstElementChild,callback);  
          }  
          if(node.lastElementChild) {  
              this.preOrder(node.lastElementChild,callback);  
          }  
      };
      // DOM二叉树的前序遍历 非递归方法 借助于栈
      Tree.prototype.preOrder = function(node,callback) {  
              var stack=[];  
              while(node!== null || stack.length!=0){  
                  while(node!==null){  
                      stack.push(node);  
                      callback(node);  
                      node=node.firstElementChild;  
                  }  
                  node=stack.pop();  
                  node=node.lastElementChild;  
              }  
          }; 

node节点和DOM节点的中序遍历

      // 中序遍历 左根右
      Tree.prototype.inOrderTraverse = function(callback) {
          inOrder(root, callback);
      }
      var inOrder = function(node, callback) {
          if (node !== null) {
              inOrder(node.left, callback);
              callback(node);
              inOrder(node.right, callback);
          }
      }
      // DOM中序遍历 左根右 递归方法
      var inOrder = function(node, callback) {
          if (node.firstElementChild) {
              this.inOrder(node.firstElementChild,callback);
          }
          callback(node);
          if (node.lastElementChild) {
              this.inOrder(node.lastElementChild,callback);
          }
      }
      // DOM中序遍历 左根右 非递归方法
      Tree.prototype.inOrder = function(node,callback) {  
          var stack=[];  
          while(node!== null || stack.length!=0){  
              while(node!==null){  
                  stack.push(node);  
                  node=node.firstElementChild;  
              }  
              node=stack.pop();  
              callback(node);  
              node=node.lastElementChild;  
          }  
      }; 

node节点和DOM节点的后序遍历

      // 后序遍历 左右根
      Tree.prototype.postOrderTraverse = function(callback){  
          postOrder(root, callback);  
      }  
      var postOrder = function(node,callback){  
          if(node !== null){  
              postOrder(node.left,callback);     
              postOrder(node.right, calback);  
              callback(node);     
          }  
      }  
      // DOM的后序遍历 递归方法
      var postOrder = function(node,callback){  
          if(node.firstElementChild) {  
              this.postOrder(node.firstElementChild);  
          }   
          if(node.lastElementChild) {  
              this.postOrder(node.lastElementChild);  
          }  
          callback(node);   
      } 
      // DOM后序遍历 左根右 非递归方法
      // 每个节点，都压入栈两次；
      // 在循环体中，每次弹出一个节点赋给node
      // 如果node仍然等于栈的头结点，说明node的孩子们还没有被操作过，应该把它的孩子们加入栈中
      // 否则，说明是第二次弹出该节点，访问node。
      // 也就是说，第一次弹出，将node的孩子压入栈中，第二次弹出，访问node
      Tree.prototype.postOrder = function(node, callback) { //非递归实现
          var stack = [];
          stack.push(node);
          stack.push(node);
          while (stack.length != 0) {
              node = stack.pop();
              if (stack.length != 0 && node == stack[stack.length - 1]) {
                  if (node.lastElementChild) {
                      stack.push(node.lastElementChild);
                      stack.push(node.lastElementChild);
                  }
                  if (node.firstElementChild) {
                      stack.push(node.firstElementChild);
                      stack.push(node.firstElementChild);
                  }
              } else
                  callback(node);
              }
          }   
      }

多叉树的遍历

BFS(广度优先搜索)

      // 层序遍历，借助队列，非递归方式
      // 首先遍历根节点，然后访问第一层节点，第二层节点，....,直到访问到最后一层。
      Tree.prototype.BFSearch = function(node, callback) {
          var queue = [];
          while (node != null) {
          callback(node);
          if (node.children.length != 0) {
              for (var i = 0; i < node.children.length; i++) {
              queue.push(node.children[i]); //借助于队列,暂存当前节点的所有子节点  
              }
          }
          node = queue.shift(); //先入先出，借助于数据结构：队列  
          }
      };

DFS 深度优先

      // 借助栈，首先遍历根节点，然后沿着一条路径遍历到最深的一层，最后在逐层返回
      Tree.prototype.DFSearch = function(node, callback) {
          var stack = [];
          while (node != null) {
              callback(node);
              if (node.children.length != 0) {
                  for (var i = node.children.length - 1; i >= 0; i--) { //按照相反的子节点顺序压入栈  
                      stack.push(node.children[i]); //将该节点的所有子节点压入栈  
                  }
              }
              node = stack.pop(); //弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)        
          }
      };

      // 多叉树遍历示例
      // 有一个模板的节点
      root：{
          Name:名称，
          children：{
              count：7，
              List:[{},{},{},{},{},{},{}]
          }
      }
      // 其中List中的每个对象都与root结构相同。
      {
          Name:名称，
          children：[{},{},{},{},{},{},{}]
      }

      // 递归

      function traverseTree(list) {
          for (let node of list) {
              if (node.children) {
                  if (node.children.List) {
                      node.children = node.children.List
                  }
                  traverseTree(node.children)
              }
          }
      }

      traverseTree(root)

B树和B+树

待补充

递归

     // 费波拉契数列
     function factorial(n){
         return n > 1 ? n * factorial(n-1) : 1;
     }
     // 递归要考虑计算溢出的问题，以及中间会有需要的无用计算

数组的降维方法

递归法

      function flatten(arr) {
          var result = [];
          for (var i = 0, len = arr.length; i < len; i++) {
              if (Array.isArray(arr[i])) {
                  result = result.concat(flatten(arr[i]))
              }
              else {
                  result.push(arr[i])
              }
          }
      return result;
      }

toString

      // 数组的toString方法可以将数组变为字符串，多维也一样
      // split()方法将字符串变成数组
      function flatten(arr) {
          return arr.toString().split(',').map(function(item){
              // +运算符将字符串变成数字
              return +item
          })
      }

reduce

      arr.reduce(callback,[initialValue])
      // reduce 为数组中的每一个元素依次执行回调函数，接受2个参数或者1个参数：回调函数和初始值(可省略)
      // callback接受四个参数：初始值（或者上一次回调函数的返回值），当前元素值，当前索引，调用 reduce 的数组。

      // 例1
      var arr = [1, 2, 3, 4];
      var sum = arr.reduce(function(prev, cur, index, arr) {
          console.log(prev, cur, index);
          return prev + cur;
      })
      console.log(arr, sum);
      /*
      1 2 1
      3 3 2
      6 4 3
      [1, 2, 3, 4] 10
      这里可以看出，上面的例子index是从1开始的，第一次的prev的值是数组的第一个值。数组长度是4，但是reduce函数循环3次。
      */
      // 例2
      var  arr = [1, 2, 3, 4];
      var sum = arr.reduce(function(prev, cur, index, arr) {
          console.log(prev, cur, index);
          return prev + cur;
      }，0) //注意这里设置了初始值
      console.log(arr, sum);
      /*
      0 1 0
      1 2 1
      3 3 2
      6 4 3
      [1, 2, 3, 4] 10
      这个例子index是从0开始的，第一次的prev的值是我们设置的初始值0，数组长度是4，reduce函数循环4次。
      */
      // 数组为空且未设置初始值会报错
      var  arr = [];
      var sum = arr.reduce(function(prev, cur, index, arr) {
          console.log(prev, cur, index);
          return prev + cur;
      })
      //报错，"TypeError: Reduce of empty array with no initial value"

      // 正确用法

      var  arr = [];
      var sum = arr.reduce(function(prev, cur, index, arr) {
          console.log(prev, cur, index);
          return prev + cur;
      }，0)
      console.log(arr, sum); // [] 0

      // reduce的简单用法

      var  arr = [1, 2, 3, 4];
      var sum = arr.reduce((x,y)=>x+y)
      var mul = arr.reduce((x,y)=>x*y)
      console.log( sum ); //求和，10
      console.log( mul ); //求乘积，24

      // 计算数组中每个元素出现的次数

      let names = ['Alice', 'Bob', 'Tiff', 'Bruce', 'Alice'];

      let nameNum = names.reduce((pre,cur)=>{
          if(cur in pre){
              pre[cur]++
          }else{
              pre[cur] = 1 
          }
          return pre
      },{})
      console.log(nameNum); //{Alice: 2, Bob: 1, Tiff: 1, Bruce: 1}

      // 数组去重

      let arr = [1,2,3,4,4,1]
      let newArr = arr.reduce((pre,cur)=>{
          if(!pre.includes(cur)){
              return pre.concat(cur)
          }else{
              return pre
          }
      },[])
      console.log(newArr);// [1, 2, 3, 4]

      // 将多维数组转化为一维(递归)

      let arr = [[0, 1], [2, 3], [4,[5,6,7]]]
      const newArr = function(arr){
          return arr.reduce((pre,cur)=>pre.concat(Array.isArray(cur)?newArr(cur):cur),[])
      }
      console.log(newArr(arr)); //[0, 1, 2, 3, 4, 5, 6, 7]

      // 对象里的属性求和

      var result = [
          {
              subject: 'math',
              score: 10
          },
          {
              subject: 'chinese',
              score: 20
          },
          {
              subject: 'english',
              score: 30
          }
      ];

      var sum = result.reduce(function(prev, cur) {
          return cur.score + prev;
      }, 0);
      console.log(sum) //60

      function flatten(arr) {
          return arr.reduce(function(prev, next){
              return prev.concat(Array.isArray(next) ? flatten(next) : next)
          }, [])
      }

rest运算符

      function flatten(arr) {
          while (arr.some(item => Array.isArray(item))) {
              arr = [].concat(...arr);
          }
          return arr;
      }

  6. 排序算法

见排序整理文章

JS中的数据结构与算法

JS中的数据结构与算法

CATALOG

FEATURED TAGS

FRIENDS