二叉树的遍历

发表于 | 更新于 | 阅读次数
| 字数统计 933 字

二叉树的遍历分为：

  1. 深度优先搜索(Depth First Search)

    是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。深度优先搜索二叉树是先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，先将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。

  2. 广度优先搜索(Breadth First Search)

    是从根结点开始沿着树的宽度搜索遍历，可以利用队列实现广度优先搜索

二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列

深度优先实现

深度优先遍历又分为：前序、中序、后序遍历

  • 前序遍历：根节点->左子树->右子树
  • 中序遍历：左子树->根节点->右子树
  • 后序遍历：左子树->右子树->根节点

note: 二叉搜索树BST的中序遍历，返回的结果是按顺序排列的

递归实现

前序遍历伪代码：

1
2
3
4
5
6
preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)

根节点->左子树->右子树

python实现

1
2
3
4
5
6
def preorder(self, node):
    """前序遍历"""
    if node:
        print node.data
        self.preorder(node.left)
        self.preorder(node.right)

中序遍历伪代码：

1
2
3
4
5
6
inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

左子树->根节点->右子树

1
2
3
4
5
6
def inorder(self, node):
    """中序遍历"""
    if node:
        self.inorder(node.left)
        print node.data
        self.inorder(node.right)

后序遍历伪代码：

1
2
3
4
5
6
postorder(node)
  if (node = null)
    return
  postorder(node.left)
  postorder(node.right)
  visit(node)

左子树->右子树->根节点

1
2
3
4
5
6
def postorder(self, node):
    """后序遍历"""
    if node:
        self.postorder(node.left)
        self.postorder(node.right)
        print node.data

非递归实现

因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。

前序遍历伪代码：

1
2
3
4
5
6
7
8
9
iterativePreorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      visit(node)
      if (node.right ≠ null) parentStack.push(node.right)
      node = node.left   
    else     
      node = parentStack.pop()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def preorderTraversal__iterative(root):
    """
    :type root: TreeNode
    """
    node = root
    stack = []
    while node or stack:
        if node:
            print node.val
            if node.right:
                stack.append(node.right)
            node = node.left
        else:
            node = stack.pop()
    return

中序遍历伪代码：

1
2
3
4
5
6
7
8
9
10
iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    while (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def inorderTraversal_iterative(root):
    """
    :type root: TreeNode
    """
    node = root
    stack = []
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        print node.val
        node = node.right
    return result

后序遍历

后序遍历伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // if right child exists and traversing node
      // from left child, then move right
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def postorderTraversal(node):
    if node is None:
        return []
    stack = []
    result = []
    lastNodeVisited = None
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peekNode = stack[-1]
            if peekNode.right and lastNodeVisited != peekNode.right:
                node = peekNode.right
            else:
                result.append(peekNode)
                lastVisitedNode = stack.pop()
    return result

广度优先实现

伪代码

1
2
3
4
5
6
7
8
9
10
levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)
坚持原创技术分享，您的支持将鼓励我继续创作！