这篇文章主要为大家详细介绍了JS中的二叉树遍历，何为二叉树，什么是二叉树的遍历，感兴趣的小伙伴们可以参考一下

二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。

这篇文章主要在JS中实现二叉树的遍历。

一个二叉树的例子

var tree = {

 value: 1,

 left: {

  value: 2,

  left: {

   value: 4

  }

 },

 right: {

  value: 3,

  left: {

   value: 5,

   left: {

    value: 7

   },

   right: {

    value: 8

   }

  },

  right: {

   value: 6

  }

 }

}

广度优先遍历

广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

实现：

<!--more-->

使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。

（描述有点不清楚，直接看代码吧。）

var levelOrderTraversal = function(node) { 

 if(!node) {  

  throw new Error('Empty Tree')

 } 

 var 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)

 }

}

递归遍历

觉得用这几个字母表示递归遍历的三种方法不错：

D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。

先序遍历：DLR

中序遍历：LDR

后序遍历：LRD

顺着字母表示的意思念下来就是遍历的顺序了 ^ ^

这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-First Search，DFS），因为它总

是优先往深处访问。

先序遍历的递归算法：

var preOrder = function (node) { 

 if (node) {  

  console.log(node.value);

  preOrder(node.left);

  preOrder(node.right);

 }

}

中序遍历的递归算法：

var inOrder = function (node) { 

 if (node) {

  inOrder(node.left);  

  console.log(node.value);

  inOrder(node.right);

 }

}

后序遍历的递归算法：

var postOrder = function (node) { 

 if (node) {

  postOrder(node.left);

  postOrder(node.right);  

  console.log(node.value);

 }

}

非递归深度优先遍历

其实对于这些概念谁是属于谁的我也搞不太清楚。有的书里将二叉树的遍历只讲了上面三种递归遍历。有的分广度优先遍历和深度优先遍历两种，把递归遍历都分入深度遍历当中;有的分递归遍历和非递归遍历两种，非递归遍历里包括广度优先遍历和下面这种遍历。个人觉得怎么分其实并不重要，掌握方法和用途就好 ：）

刚刚在广度优先遍历中使用的是队列，相应的，在这种不递归的深度优先遍历中我们使用栈。在JS中还是使用一个数组来模拟它。

这里只说先序的：

额，我尝试了描述这个算法，然而并描述不清楚，按照代码走一边你就懂了。

var preOrderUnRecur = function(node) { 

 if(!node) {  

  throw new Error('Empty Tree')

 } 

 var 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)

 }

}

看了这一篇，找到了非递归后序的算法，所以在这里把非递归的遍历方法补充完整。

非递归中序

先把数的左节点推入栈，然后取出，再推右节点。

var inOrderUnRecur = function(node) { 

 if(!node) {  

  throw new Error('Empty Tree')

 } 

 var 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

  }

 }

}

非递归后序(使用一个栈)

这里使用了一个临时变量记录上次入栈/出栈的节点。思路是先把根节点和左树推入栈，然后取出左树，再推入右树，取出，最后取跟节点。

var posOrderUnRecur = function(node) { 

 if(!node) {  

  throw new Error('Empty Tree')

 } 

 var stack = []

 stack.push(node) 

 var tmp = null

 while(stack.length !== 0) {

  tmp = stack[stack.length - 1]  

  if(tmp.left && node !== tmp.left && node !== tmp.right) {

   stack.push(tmp.left)

  } else if(tmp.right && node !== tmp.right) {

   stack.push(tmp.right)

  } else {   

   console.log(stack.pop().value)

   node = tmp

  }

 }

}

非递归后序(使用两个栈)

这个算法的思路和上面那个差不多，s1有点像一个临时变量。

var posOrderUnRecur = function(node) { 

 if(node) {  

  var s1 = []  

  var 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);

  }

 }

}

Morris遍历

这个方法即不用递归也不用栈实现三种深度遍历，空间复杂度为O(1)（这个概念我也不是特别清楚org）

（这三种算法我先放着，有空再研究）

Morris先序:

var morrisPre = function(head) { 

 if(!head) {  

  return

 } 

 var cur1 = 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中序:

var morrisIn = function(head) { 

 if(!head) {  

  return

 } 

 var cur1 = 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后序:

var morrisPost = function(head) { 

 if(!head) {  

  return

 } 

 var cur1 = 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)

}

var printEdge = function(head) { 

以上就是本文的全部内容，希望对大家的学习有所帮助。