二叉树,遍历

二叉树的前序、中序、后序以及层次遍历总结

Posted by Jack on 2020-07-27
Words 1.1k and Reading Time 4 Minutes
Viewed Times

1. 二叉树的定义

首先我们需要定义二叉树中的节点，它应该包含当前节点的值、一个指向左子树的指针以及一个指向右子树的指针这三个属性，因此二叉树节点的定义如下：

1
2
3
4
5
6
7
8
9
class TreeNode(object):
    """
    Tree Node definition
    """

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

为了方便后续对二叉树的遍历进行讲解，此处我们先构建一棵简单的树。
1
2
3
4
5
6
7
8
9
10
11
root = TreeNode(1)
a = TreeNode(3)
b = TreeNode(4)
c = TreeNode(2)
d = TreeNode(5)
e = TreeNode(6)
root.left = a
root.right = b
a.left = c
a.right = d
b.right = e

这棵二叉树的结构如下：

      1
     / \
    3   4
   /\    \
  2  5    6

2. 二叉树的前序遍历

二叉树的前序遍历顺序为：根节点 -> 左子树 -> 右子树，通常有递归和非递归两种实现方式。
递归的实现方式其实很简单，遍历完父节点后，再通过递归依次遍历左孩子和右孩子即可。具体的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
def preorder_traverse_recu(root):
    """
    前序遍历（递归）
    """
    if root is None:
        return
    print(root.val)
    # 遍历左子树
    preorder_traverse_recu(root.left)
    # 遍历右子树
    preorder_traverse_recu(root.right)

非递归的方式则需要使用栈，借助其先进后出的特性，具体的实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def preorder_traverse_nonrecu(root):
    """
    前序遍历（非递归）
    """
    if root is None:
        return
    stack = [root]
    while stack:
        print(root.val)
        # 注意要先入栈右孩子，再入栈左孩子（先进后出）
        if root.right:
            stack.append(root.right)
        if root.left:
            stack.append(root.left)
        root = stack.pop(-1)

通过以上两种方式，对前面构造的二叉树进行前序遍历的结果为：1, 3, 2, 5, 4, 6。

3. 二叉树的中序遍历

二叉树的中序遍历顺序为：左子树 -> 根节点 -> 右子树，同样有递归和非递归两种实现方式。
递归的实现方式其实就是在每层递归里面，先遍历左孩子，然后遍历父节点，最后遍历右孩子，具体的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
def inorder_traverse_recu(root):
    """
    中序遍历（递归）
    """
    if root is None:
        return
    # 遍历左子树
    inorder_traverse_recu(root.left)
    print(root.val)
    # 遍历右子树
    inorder_traverse_recu(root.right)

非递归方式则是使用栈，具体的实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def inorder_traverse_nonrecu(root):
    """
    中序遍历（递归）
    """
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            # 如果有左孩子，会一直入栈，直到叶子节点
            root = root.left
        # 出栈，然后处理右孩子
        root = stack.pop(-1)
        print(root.val)
        root = root.right

通过以上两种方式，对前面构造的二叉树进行中序遍历的结果为：2, 3, 5, 1, 4, 6。

4. 二叉树的后序遍历

二叉树的前序遍历顺序为：左子树 -> 右子树 -> 根节点，通常有递归和非递归两种实现方式。
递归的实现方式是在每层递归里面，先遍历左孩子，然后遍历右孩子，最后遍历父节点，具体的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
def backorder_traverse_recu(root):
    """
    后序遍历（递归）
    """
    if root is None:
        return
    # 遍历左子树
    backorder_traverse_recu(root.left)
    # 遍历右子树
    backorder_traverse_recu(root.right)
    print(root.val)

非递归方式需要使用两个栈，一个是辅助栈，用于找出后序遍历的逆序；另一个则是用来存储后序遍历的逆序，然后出栈就获得了后序遍历结果。具体的实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def backorder_traverse_nonrecu(root):
    """
    后序遍历（非递归）
    """
    if root is None:
        return
    stack1, stack2 = [root], []
    # 利用stack1找出后序遍历的逆序，并存入stack2
    while stack1:
        root = stack1.pop(-1)
        stack2.append(root)
        if root.left:
            stack1.append(root.left)
        if root.right:
            stack1.append(root.right)
    # 将stack2中的元素出栈，即为后序遍历顺序
    while stack2:
        node = stack2.pop(-1)
        print(node.val)

通过以上两种方式，对前面构造的二叉树进行后序遍历的结果为：2, 5, 3, 6, 4, 1。

5. 二叉树的层次遍历

二叉树的层次遍历是从根节点开始，然后一层一层的遍历。通常是使用队列来实现，利用了其先进先出的特点。具体的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def layer_traverse(root):
    """
    层次遍历
    """
    if root is None:
        return
    queue = [root]
    while queue:
        # 取第一个（先进先出）
        node = queue.pop(0)
        print(node.val)
        # 左孩子入队
        if node.left:
            queue.append(node.left)
        # 右孩子入队
        if node.right:
            queue.append(node.right)

对前面构造的二叉树进行层次遍历的结果为：1, 3, 4, 2, 5, 6。

...

...

00:00
00:00
FEATURED TAGS
二叉树,遍历
FRIENDS