[译]JavaScript 如何遍历树结构

本文介绍了树结构在 JavaScript 语言里面如何遍历，解释了广度优先、深度优先等多种方法的实现。

树是一种有趣的数据结构。它在各种领域都有广泛的应用。例如:

• HTML中的DOM是一种树形数据结构
• 我们的操作系统中的目录和文件都可以表示为树形
• 一个家族的层次结构可以表示为一棵树

树有很多变种（如堆、BST等），可以用来解决与调度、图像处理、数据库等相关的问题。许多复杂的问题看起来与树没有关系，但实际上可以表示为一个问题。我们也会通过这样的问题（在本系列的后面部分）来看看树是如何使看似复杂的问题更容易理解和解决的。

简介

通过一个Node来表示二叉树是非常简单的。

function Node(value){
  this.value = value
  this.left = null
  this.right = null
}
// 使用方法
const root = new Node(2)
root.left = new Node(1)
root.right = new Node(3)

这几行代码将为我们创建一个二进制树，看起来像这样

           2  
        /      \
       /         \
     1            3
   /   \        /    \
null  null   null   null

很简单，所以我们可以用它来做什么呢？

遍历

让我们试着走过这些连接的树节点（或一棵树），就像我们可以遍历一个数组一样。如果我们也能 "遍历 "树节点，那就很酷了。然而，树并不是像数组那样的线性数据结构，所以并不是只有一种方式可以遍历这些。我们可以将遍历方法大致分为以下两种：

• 广度优先遍历
• 深度优先遍历

广度优先搜索/遍历(BFS)

在这种方法中，我们逐级遍历树。我们将从根部开始，然后覆盖它的所有子代，我们覆盖所有第二层的子代，如此类推（其实也就是层序遍历）。例如，对于上面的树，遍历的结果如下：

2, 1, 3

这里有一个略带复杂的树的插图，使之更简单易懂。

为了实现这种形式的遍历，我们可以使用一个队列（先进先出）数据结构。下面是整个算法的过程

1. 初始化一个有根的队列
2. 从队列中取出第一个项目
3. 将弹出的项目的左右两个子项推入队列中
4. 重复步骤2和3，直到队列为空

下面是具体代码实现：

function walkBFS(root){
  if(root === null) return

  const queue = [root]
  while(queue.length){
      const item = queue.shift()
      // do something
      console.log(item)

      if(item.left) queue.push(item.left)
      if(item.right) queue.push(item.right)
   }
}

我们可以稍微修改上面的算法，返回一个数组，其中每个内部数组代表一个级别，元素都在里面。

function walkBFS(root){
  if(root === null) return

  const queue = [root], ans = []

  while(queue.length){
      const len = queue.length, level = []
      for(let i = 0; i < len; i++){
          const item = queue.shift()
          level.push(item)
          if(item.left) queue.push(item.left)
          if(item.right) queue.push(item.right)
       }
       ans.push(level)
   }
  return ans
}

深度优先搜索/遍历(DFS)

在DFS中，我们从一个节点开始，不断查找它的子节点，直到所有子节点都找到。这可以通过以下任意一种方式来完成。

 root node -> left node -> right node // 先序遍历
 left node -> root node -> right node // 中序遍历
 left node -> right node -> root node // 后序遍历

所有这些遍历技术都可以用递归和迭代的方式实现，让我们实现一下吧。

先序遍历

以下是先序遍历的过程。

 root node -> left node -> right node

• 技巧

我们可以使用这个简单的技巧来手动找出任何树的先序遍历：从根节点开始遍历整个树，让自己保持在左边。

具体实现：

• 递归

让我们深入了解一下这种遍历的具体实现。递归方法是相当直观的。

function walkPreOrder(root){
  if(root === null) return

  console.log(root.val)

  // 通过子节点进行递归
  if(root.left) walkPreOrder(root.left)
  if(root.right) walkPreOrder(root.right)
}

• 迭代

先序遍历的迭代方法与BFS非常相似，只是我们使用栈而不是队列，并且我们是先将右边的子节点推入栈。

function walkPreOrder(root){
  if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()

      console.log(item)

      // 左边的子节点被推到右边的子节点之后，因为我们想先打印左边的子节点，所以它在栈中必须在右边的子节点之上。
      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

中序遍历

下面是一个树的中序遍历过程。

left node -> root node -> right node

• 技巧

我们可以用这个简单的技巧来手动找出任何树的中序遍历：在树的底部水平保持一个平面镜，并取所有节点的投影。

具体实现：

• 递归：

function walkInOrder(root){
  if(root === null) return

  if(root.left) walkInOrder(root.left)

  console.log(root.val)

  if(root.right) walkInOrder(root.right)
}

• 迭代

这种算法一开始可能看起来有点隐晦，但实际上是相当直观的。让我们这样看：在中序遍历中，最左边的子节点先被打印出来，然后是根，然后是右边的子节点。所以第一个想法是想出这样的方法。

const curr = root

while(curr){
  while(curr.left){
    curr = curr.left // 拿到最左的子节点
  }

  console.log(curr) 

  curr = curr.right // 现在移到右边的子节点
}

在上述方法中，我们无法回溯，即回到导致最左边节点的父节点。所以我们需要一个栈来记录这些。因此，我们修改后的方法可能如下

const stack = []
const curr = root

while(stack.length || curr){
  while(curr){
    stack.push(curr) // 追踪记录，回溯历史
    curr = curr.left // 拿到最左的子节点
  }
  const leftMost = stack.pop()
  console.log(leftMost) 

  curr = leftMost.right // 现在移到右边的子节点
}

现在我们可以使用上述方法来实现最终的迭代算法了。

function walkInOrder(root){
  if(root === null) return

  const stack = []
  let current = root

  while(stack.length || current){
      while(current){
         stack.push(current)
         current = current.left
      }
      const last = stack.pop()

      console.log(last)

      current = last.right
   }
}

后序遍历

下面是树的后序遍历的过程。

 left node -> right node -> root node

• 技巧

对于任何树的快速手动后续遍历：逐一摘取所有最左边的叶子结点。

具体实现：

• 递归

function walkPostOrder(root){
  if(root === null) return

  if(root.left) walkPostOrder(root.left)
  if(root.right) walkPostOrder(root.right)

  console.log(root.val)

}

• 迭代

我们已经有了用于先序遍历的迭代算法。我们可以使用它吗？因为后序遍历似乎只是先序遍历的反向。让我们来看看。

// 先序:
root -> left -> right

// 先序的反向:
right -> left -> root

// 后序:
left -> right -> root

有一些轻微的差异，但我们可以通过稍微修改我们的先序算法来适应这种情况，然后反过来应该可以得到后序的结果。具体算法如下：

// 记录结果
root -> right -> left

// 反转结果
left -> right -> root

• 使用类似于上述迭代先序序算法的方法，使用一个临时栈。
  • 唯一的例外是我们走root -> right -> left，而不是root -> left -> right
• 在一个数组result中不断记录遍历的顺序
• 对结果进行反转，得到后序遍历

function walkPostOrder(root){
  if(root === null) return []

  const tempStack = [root], result = []

  while(tempStack.length){
      const last = tempStack.pop()

      result.push(last)

      if(last.left) tempStack.push(last.left)
      if(last.right) tempStack.push(last.right)
    }

    return result.reverse()
}

提示

如果我们能以如下方式遍历这棵树，那该有多好

 for(let node of walkPreOrder(tree) ){
   console.log(node)
 }

看起来真不错，而且读起来也很简单，不是吗？我们所要做的就是使用一个walk函数，它将返回一个迭代器。

下面是我们如何修改上面的walkPreOrder函数，使其按照上面分享的例子执行。

function* walkPreOrder(root){
   if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()
      yield item
      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

原文

JavaScript 如何遍历树结构