树的遍历

发表于 | 分类于 ，

树的遍历也被称之为树的搜索。分为深度优先搜索和广度优先搜索。

深度优先搜索

深度优先搜索是指尽可能远地遍历每一条分支直到分支结束，再通过回溯遍历另一条分支。按照访问节点及其左右子树的顺序可以将其实现细分为三种：先序遍历、中序遍历、后续遍历。

先序遍历

  1. 打印当前节点
  2. 使用先序遍历遍历及打印左子树
  3. 使用先序遍历遍历及打印右子树
递归实现
1
2
3
4
5
6
preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)
非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
preorder(node)
  if (node = null)
    return
  s ← empty stack
  s.push(node)
  while (!s.isEmpty())
    node ← s.pop()
    visit(node)
    // push right child first so that the left subtree will be traversed first
    if (node.right != null)
      s.push(node.right)
    if (node.left != null)
      s.push(node.left)

中序遍历

  1. 使用中序遍历遍历及打印左子树
  2. 打印当前节点
  3. 使用中序遍历遍历及打印右子树
递归实现
1
2
3
4
5
6
7
inorder(node)
  if (node = null)
    return

  inorder(node.left)
  visit(node)
  inorder(node.right)
非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
inorder(node)
  if (node = null) 
    return

  s ← empty stack
  while (!s.isEmpty() || node != null)
    if (node != null)
      s.push(node)
      node ← node.left
    else 
      node = s.pop()
      visit(node)
      node ← node.right

后序遍历

  1. 使用后序遍历遍历及打印左子树
  2. 使用后序遍历遍历及打印右子树
  3. 打印当前节点
递归实现
1
2
3
4
5
6
7
postorder(node)
  if (node = null)
    return

  postorder(node.left)
  postorder(node.right)
  visit(node)
非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
postorder(node)
  if (node = null)
    return

  s ← empty stack
  lastVisitedNode ← null
  while (!s.isEmpty() || node != null)
    if (node != null)
      s.push(node)
      node ← node.left
    else
      // do not pop it immediately
      peek ← s.peek()
      // if the right subtree exists and has not been traversed,
      // then traverse it; else display current node.
      if (peek.right != null && peek != lastVisitedNode)
        node ← peek.right
      else
        lastVisitedNode ← s.pop();
        visit(lastVisitedNode)

广度优先搜索

广度优先搜索是自根节点起依次遍历每层的节点的方法。伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
bfs(node)
  if (node = null) 
    return

  q ← empty queue
  q.enqueue(node)
  while (!node.isEmpty())
    n ← q.dequeue()
    visit(n)
    if (n.left != null)
      q.enqueue(n.left)
    if (n.right != null)
      q.enqueue(n.right)

References

Tree traversal
DFS
BFS
LIFO
FIFO