了解：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
用递归能做的,用非递归都可以做.
因为递归其实就是利用函数栈来保存信息,如果用自己的数据结构来代替函数栈,自然可以实现相同的功能.
如果需要用队列实现深度遍历，我的思路是用两个队列模拟一个栈。
