JS二叉树遍历详解：广度优先、递归及Morris算法实现

二叉树基础与广度优先遍历

二叉树由根节点、左子树和右子树构成，其中左子树和右子树本身也是二叉树。本文旨在介绍如何在 JavaScript 中实现二叉树的遍历操作。

一个二叉树的例子


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
  }
 }
}

广度优先遍历从二叉树的第一层（即根节点）开始，自上而下逐层访问；在同一层内，按照从左到右的顺序依次访问各个节点。实现思路如下：  利用数组模拟队列结构。首先将根节点加入队列。当队列不为空时，执行循环：取出队首节点，若其左子树非空，则将左子节点入队；若右子树非空，则将右子节点入队。（描述可能不够直观，建议结合代码理解。）


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 按照字母含义朗读即可得到遍历顺序 ^ ^

这三种遍历均属于递归遍历，也可称为深度优先遍历（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);
 }
}

非递归深度优先遍历

非递归深度优先遍历关于概念的归属，不同资料分类略有差异。有的书籍仅介绍上述三种递归遍历；有的将其分为广度优先和深度优先两类，并将所有递归遍历归入深度遍历；还有的分为递归与非递归两类，其中非递归包含广度优先及下文介绍的遍历方式。个人认为分类并非关键，掌握具体方法和应用场景更为重要：）

在广度优先遍历中使用了队列，而在非递归的深度优先遍历中，我们使用栈。在 JavaScript 中，同样可以使用数组来模拟栈的行为。此处仅介绍先序遍历：尝试描述该算法较为困难，建议直接运行代码以理解流程。


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 遍历算法

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

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

JavaScript 二叉树遍历全解：递归与非递归实现

二叉树基础与广度优先遍历

递归遍历：先序、中序与后序

非递归深度优先遍历

Morris 遍历算法

实用工具推荐