JS中的二叉树遍历详解
二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。
这篇文章主要在JS中实现二叉树的遍历。
一个二叉树的例子
vartree={
value:1,
left:{
value:2,
left:{
value:4
}
},
right:{
value:3,
left:{
value:5,
left:{
value:7
},
right:{
value:8
}
},
right:{
value:6
}
}
}
广度优先遍历
广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。
实现：
<!--more-->
使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。
（描述有点不清楚，直接看代码吧。）
varlevelOrderTraversal=function(node){
if(!node){
thrownewError('EmptyTree')
}
varque=[]
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)
}
}
递归遍历
觉得用这几个字母表示递归遍历的三种方法不错：
D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。
先序遍历：DLR
中序遍历：LDR
后序遍历：LRD
顺着字母表示的意思念下来就是遍历的顺序了^^
这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-FirstSearch，DFS），因为它总
是优先往深处访问。
先序遍历的递归算法：
varpreOrder=function(node){
if(node){
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
}
}
中序遍历的递归算法：
varinOrder=function(node){
if(node){
inOrder(node.left);
console.log(node.value);
inOrder(node.right);
}
}
后序遍历的递归算法：
varpostOrder=function(node){
if(node){
postOrder(node.left);
postOrder(node.right);
console.log(node.value);
}
}
非递归深度优先遍历
其实对于这些概念谁是属于谁的我也搞不太清楚。有的书里将二叉树的遍历只讲了上面三种递归遍历。有的分广度优先遍历和深度优先遍历两种，把递归遍历都分入深度遍历当中;有的分递归遍历和非递归遍历两种，非递归遍历里包括广度优先遍历和下面这种遍历。个人觉得怎么分其实并不重要，掌握方法和用途就好：）
刚刚在广度优先遍历中使用的是队列，相应的，在这种不递归的深度优先遍历中我们使用栈。在JS中还是使用一个数组来模拟它。
这里只说先序的：
额，我尝试了描述这个算法，然而并描述不清楚，按照代码走一边你就懂了。
varpreOrderUnRecur=function(node){
if(!node){
thrownewError('EmptyTree')
}
varstack=[]
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)
}
}
看了这一篇，找到了非递归后序的算法，所以在这里把非递归的遍历方法补充完整。
非递归中序
先把数的左节点推入栈，然后取出，再推右节点。
varinOrderUnRecur=function(node){
if(!node){
thrownewError('EmptyTree')
}
varstack=[]
while(stack.length!==0||node){
if(node){
stack.push(node)
node=node.left
}else{
node=stack.pop()
console.log(node.value)
node=node.right
}
}
}
非递归后序(使用一个栈)
这里使用了一个临时变量记录上次入栈/出栈的节点。思路是先把根节点和左树推入栈，然后取出左树，再推入右树，取出，最后取跟节点。
varposOrderUnRecur=function(node){
if(!node){
thrownewError('EmptyTree')
}
varstack=[]
stack.push(node)
vartmp=null
while(stack.length!==0){
tmp=stack[stack.length-1]
if(tmp.left&&node!==tmp.left&&node!==tmp.right){
stack.push(tmp.left)
}elseif(tmp.right&&node!==tmp.right){
stack.push(tmp.right)
}else{
console.log(stack.pop().value)
node=tmp
}
}
}
非递归后序(使用两个栈)
这个算法的思路和上面那个差不多，s1有点像一个临时变量。
varposOrderUnRecur=function(node){
if(node){
vars1=[]
vars2=[]
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);
}
}
}
Morris遍历
这个方法即不用递归也不用栈实现三种深度遍历，空间复杂度为O(1)（这个概念我也不是特别清楚org）
（这三种算法我先放着，有空再研究）
Morris先序:
varmorrisPre=function(head){
if(!head){
return
}
varcur1=head,
cur2=null
while(cur1){
cur2=cur1.left
if(cur2){
while(cur2.right&&cur2.right!=cur1){
cur2=cur2.right
}
if(!cur2.right){
cur2.right=cur1
console.log(cur1.value)
cur1=cur1.left
continue
}else{
cur2.right=null
}
}else{
console.log(cur1.value)
}
cur1=cur1.right
}
}
Morris中序:
varmorrisIn=function(head){
if(!head){
return
}
varcur1=head,
cur2=null
while(cur1){
cur2=cur1.left
if(cur2){
while(cur2.right&&cur2.right!==cur1){
cur2=cur2.right
}
if(!cur2.right){
cur2.right=cur1
cur1=cur1.left
continue
}else{
cur2.right=null
}
}
console.log(cur1.value)
cur1=cur1.right
}
}
Morris后序:
varmorrisPost=function(head){
if(!head){
return
}
varcur1=head,
cur2=null
while(cur1){
cur2=cur1.left
if(cur2){
while(cur2.right&&cur2.right!==cur1){
cur2=cur2.right
}
if(!cur2.right){
cur2.right=cur1
cur1=cur1.left
continue
}else{
cur2.right=null
printEdge(cur1.left)
}
}
cur1=cur1.right
}
printEdge(head)
}
varprintEdge=function(head){
以上就是本文的全部内容，希望对大家的学习有所帮助。