二叉树的遍历

Posted on | Post modified:
分别采用递归和迭代的方式来实现遍历二叉树

二叉树的遍历实现

二叉树是每个结点最多有两个子树的树结构

遍历的方法

  • 前序遍历，根节点->左子树->右子树
  • 中序遍历，左子树->根节点->右子树
  • 后序遍历，左子树->右子树->根节点
  • 层次遍历，按照层数，从根节点依次往下找

图解

  • 前序，后序，中序都是深度优先遍历的方式
  • 层次遍历是广度优先的遍历方式

使用递归的方式比采用迭代的方式慢

递归的方式

  1. 前序遍历: 保存当前节点的值，然后递归调用左节点和右节点
  2. 后序遍历: 先递归调用左节点和右节点，然后再保存当前节点的值
  3. 中序遍历: 先递归调用左节点，保存当前节点值，再递归调用右节点

非递归的方式

  1. 前序遍历: 根据前序遍历的顺序，优先访问根结点，然后在访问左子树和右子树。所以，对于任意结点node，第一部分即直接访问之，之后在判断左子树是否为空，不为空时即重复上面的步骤，直到其为空。若为空，则需要访问右子树。注意，在访问过左孩子之后，需要反过来访问其右孩子，所以，需要栈这种数据结构的支持。对于任意一个结点node，具体步骤如下：

    • 访问之，并把结点node入栈，当前结点置为左孩子；
    • 判断结点node是否为空，若为空，则取出栈顶结点并出栈，将右孩子置为当前结点；否则重复上面的步骤直到当前结点为空或者栈为空（可以发现栈中的结点就是为了访问右孩子才存储的）

  2. 后序遍历: 使用两个栈来存储左右节点，将每个节点都保存到其中一个栈，然后将该节点的左右节点保存到这个栈，删除在这个栈的节点，保存该节点到第二个栈；然后遍历第二个栈里面的数据，这样才能保证左右节点的值先于根节点保存

  3. 中序遍历: 和前序遍历有点类似，把每个节点的左子树存入栈，删除栈中的该节点，保存值。直到左子树节点为空，把右子树作为当前节点。

  4. 层次遍历: 使用消息队列，把每个节点都存入队列中，再出队列的时候，依次访问左右子树的根节点值，如果左右子树不为空的情况下，都存入队列
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#!/usr/bin/env python
# coding=utf-8
"""
@desc:   二叉树
@author: luluo
@date:   2018-8-22

"""
import time


class Node(object):
    def __init__(self, val='-1'):
        self.val = val
        self.left = None
        self.right = None


class Tree(object):
    def __init__(self):
        self.root = Node()
        self.queue = []  # 用来检验当前节点左右子数是否都存在了，不存在的话，这个节点还能继续使用

    def add(self, val):
        """将每个数依次加入到每个节点中，新增一个节点，就这个节点存入队列，直到这个节点的左右树都已满，从队列中删除该节点"""
        if self.root.val == '-1':
            self.root = Node(val)
            self.queue.append(self.root)
        else:
            tree_node = self.queue[0]
            if tree_node.left is None:
                tree_node.left = Node(val)
                self.queue.append(tree_node.left)
            else:
                tree_node.right = Node(val)
                self.queue.append(tree_node.right)
                self.queue.pop(0)

    def front_sort(self, root):
        """使用递归的方式来前序遍历"""
        if root is None:
            return
        print(root.val)
        self.front_sort(root.left)
        self.front_sort(root.right)
        end = time.time()

    def front_sort_stack(self, root):
        """使用栈的数据结构来保存每次遍历的节点"""
        if root is None:
            return
        stack = []
        node = root
        while node or stack:
            while node:
                print(node.val)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right

    def end_sort(self, root):
        """使用递归的方式来完成后序遍历"""
        if root is None:
            return

        self.end_sort(root.left)
        self.end_sort(root.right)
        print(root.val)

    def end_sort_stack(self, root):
        """使用栈数据结构来实现后序遍历"""
        if root is None:
            return

        stack = [root]
        rest_stack = []
        while stack:
            node = stack.pop()
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            rest_stack.append(node)
        while rest_stack:
            print(rest_stack.pop().val)

    def middle_sort(self, root):
        """使用递归的方式来实现中序遍历"""
        if root is None:
            return

        self.middle_sort(root.left)
        print(root.val)
        self.middle_sort(root.right)

    def middle_sort_stack(self, root):
        """使用栈来实现中序遍历"""
        if not root:
            return

        stack = []
        node = root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            print(node.val)
            node = node.right

    def level_sort(self, root):
        """使用队列来实现层次的遍历，也就是广度优先遍历"""
        if root is None:
            return

        flag_queue = [root]
        while flag_queue:
            node = flag_queue.pop(0)
            print(node.val)
            if node.left is not None:
                flag_queue.append(node.left)
            if node.right is not None:
                flag_queue.append(node.right)


if __name__ == "__main__":
    """main function"""
    test_tree = Tree()
    for a in range(10000):
        test_tree.add(a)

    print('\n\n递归实现先序遍历:')
    start = time.time()
    test_tree.front_sort(test_tree.root)
    end = time.time()
    print(end - start)
    print('\n\n非递归，利用栈来实现前序遍历')
    start = time.time()
    test_tree.front_sort_stack(test_tree.root)
    end = time.time()
    print(end-start)
    # print('\n递归实现中序遍历:')
    # test_tree.middle_sort(test_tree.root)
    # print('\n\n非递归，使用栈来实现中序遍历')
    # test_tree.middle_sort_stack(test_tree.root)
    # print('\n递归实现后序遍历:')
    # test_tree.end_sort(test_tree.root)
    # print('\n非递归，使用栈来实现后序遍历')
    # test_tree.end_sort_stack(test_tree.root)
    # print('\n层次遍历:')
    # test_tree.level_sort(test_tree.root)