二叉树的几种遍历方式

数据结构

二叉树的遍历在数据结构课程考试以及IT公司面试和笔试中还是相当常见的，这里稍作整理，以Python代码给出。

二叉树一般有四种遍历方式：

  1. 前序遍历
  2. 中序遍历
  3. 后序遍历
  4. 层级遍历

前序遍历

  1. 访问根节点
  2. 以前序遍历的方式访问左子树
  3. 以前序遍历的方式访问右子树

中序遍历

  1. 以中序遍历的方式访问左子树
  2. 访问根节点
  3. 以中序遍历的方式访问右子树

后序遍历

  1. 以后序遍历的方式访问左子树
  2. 以后序遍历的方式访问右子树
  3. 访问根节点

层级遍历

  1. 从根节点开始根据树的层次从左至右，从上到下访问节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#!/usr/bin/python
#coding=utf-8

class Node():
    """
    二叉树节点
    """

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

class BTree():
    """
    二叉树
    """

    def __init__(self):
        self.root = None

    def add(self, data):
        """
        向二叉树添加节点
        """
        if self.root is None:
            self.root = Node(data)
            return
        
        q = [self.root]
        while True:
            node = q.pop()
            if node.left is None:
                node.left = Node(data)
                return
            elif node.right is None:
                node.right = Node(data)
                return
            else:
                q.append(node.left)
                q.append(node.right)

    def preOrder(self, root):
        """
        前序遍历(递归方式)
        """
        res = []
        if root is None:
            return
        print(root.data),
        self.preOrder(root.left)
        self.preOrder(root.right)

    def inOrder(self, root):
        """
        中序遍历(递归方式)
        """
        if root is None:
            return
        self.inOrder(root.left)
        print(root.data),
        self.inOrder(root.right)

    def postOrder(self, root):
        """
        后序遍历(递归方式)
        """
        if root is None:
            return
        self.postOrder(root.left)
        self.postOrder(root.right)
        print(root.data),

    def levelOrder(self):
        """
        层级遍历
        """
        if self.root is None:
            return []

        res = []
        q = [self.root]
        
        while q:
            q1 = []
            level = [] # 当前层级的节点列表
            for node in q:
                level.append(node.data)
                if node.left is not None:
                    q1.append(node.left)
                if node.right is not None:
                    q1.append(node.right)
                q = q1
            res.append(level)
        return res


if __name__ == '__main__':
    tree = BTree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)

    print("前序遍历:")
    tree.preOrder(tree.root)
    print("\n")

    print("中序遍历:")
    tree.inOrder(tree.root)
    print("\n")

    print("后序遍历:")
    tree.postOrder(tree.root)
    print("\n")

    print("层级遍历:")
    res = tree.levelOrder()
    print(res)
数据结构