了解：js可通过数组内置方法push与shift实现队列；通过push与pop实现栈；

构造二叉树

function Node() {
  this.value = null
  this.left = null
  this.right = null
}

生成一个二叉树列子；

var tree = {
  value: 10,
  left: {
    value: 2,
    left: {
      value: 4
    }
  },
  right: {
    value: 11,
    left: {
      value: 9,
      left: {
        value: 5
      },
      right: {
        value: 12
      }
    },
    right: {
      value: 14
    }
  }
}

广度优先遍历(队列)

• 从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止

  
  Animated_BFS.gif

入队根节点、取出，入队左节点、队右节点；取出左节点，取出右节点；

  let leverOrder=function(node){
        let que=[];
        que.push(node)
        while(que.length!==0){
            node =que.shift()
            console.log(node.value)
            if(node.left) que.push(node.left);
            if(node.right) que.push(node.right);
        }
    }
levelOrder(tree);// 10 2 11 4 9 14 5 12

深度优先遍历（栈）

• 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
• 当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
• 这一过程一直进行到已发现从源节点可达的所有节点为止。
• 如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止

O代表访问根节点：L代表访问左节点：R代表访问右节点；

先序遍历：OLR（递归）

var preOrder = function (node) {
  if (node) {
    console.log(node.value);
    preOrder(node.left);
    preOrder(node.right);
  }
};
preOrder(tree);//10 2 4 11 9 5 12 14

栈

先推入根节点入栈、取出，再推右节点、左节点入栈，取出；

let preOrder= function (node) {
    let stack =[];
    stack.push(node);
    while(stack.length!==0){
        node =stack.pop();
        console.log(node.value);
        if(node.right) stack.push(node.right);
        if(node.left)  stack.push(node.left);
    }
}

    preOrder(tree)//10 2 4 11 9 5 12 14

中序遍历：LOR（）

递归

var inOrder = function (node) {
  if (node) {
    inOrder(node.left);
    console.log(node.value);
    inOrder(node.right);
  }
}
inOrder(tree);// 4 2 10 5  9  12 11 14

栈

先把根节点、左节点推入栈，然后取出左节点，再推右节点入栈，取出根节点与右节点；

 let inOrder=function (node){
     stack=[];
     while(stack.length!==0||node ){
         if(node){
             stack.push(node);
             node=node.left ;
         }else{
             node = stack.pop();
             console.log(node.value);
             node= node.right;
         }
     }
 }
inOrder(tree)// 4 2 10 5  9  12 11 14

后序遍历：LRO

递归

var postOrder = function (node) {
  if (node) {
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.value);
  }
}
postOrder(tree);// 4  2 5  12 9  14 11 10

栈

定义2个栈是s1,s2：s1暂存数据：先把根节点和左树推入栈，然后取出左树，再推入右树，取出，最后取根节点。

let postOrder= function (node){
    let s1=[];
    let s2=[];
    s1.push(node);
    while(s1.length!==0) {
        node = s1.pop();
        s2.push(node);
        if (node.left) s1.push(node.left);
        if (node.right) s1.push(node.right);
    }
        while(s2.length!==0){
            console.log(s2.pop().value);
        }

}
 postOrder(tree)//4  2 5  12 9  14 11 10

用递归能做的,用非递归都可以做.

• 因为递归其实就是利用函数栈来保存信息,如果用自己的数据结构来代替函数栈,自然可以实现相同的功能.

• 如果需要用队列实现深度遍历，我的思路是用两个队列模拟一个栈。