By

Contents
  1. 1. 节点的表示
  2. 2. 前中后序－递归
    1. 2.1. 前序：
    2. 2.2. 中序
    3. 2.3. 后序
  3. 3. 非递归方法
    1. 3.1. 前序
    2. 3.2. 中序
    3. 3.3. 后序
  4. 4. 层序-队列
  5. 5. 附录 完整代码

　　树的遍历应该是一个很基础的问题，但如果要求选手写算法一次通过却不容易，所以又拿来好好研究（熟悉）一番，力求以后再遇到这样的问题能够快速准确地解决。

　　以下给出了四种遍历的一种或多种解法，为了快速表达，使用了python语言。四种遍历分别是层序、前序、中序和后序，所谓层序就是由上到下一次遍历一层，所谓前中后则是父节点的打印顺序，Ｎ代表父节点，ＬＲ代表左右子节点的话，ＮＬＲ为前序，LNR为中序，ＬＲＮ为后序。

节点的表示

　　接下来的代码都对如下定义的节点组成的树作操作：

1
2
3
4
5
6
7
8
class Node:
    def __init__(self, name, left, right):
        self.name = name
        self.left = left
        self.right = right
    def __str__(self):
        return self.name

前中后序－递归

　　递归的方法是最简单也是最容易想到的方法，因为二叉树的结构是固定的，遍历的规则也一定的，每到一个节点上作相同的处理即可。

前序：

  1. 如节点不为空，打印本身
  2. 如左不为空，进入左
  3. 如右不为空，进入右

表现为代码就是：

1
2
3
4
5
6
7
8
def recnlr(node):
    if node is None:
        return
    print node,
    if node.left:
        recnlr(node.left)
    if node.right:
        recnlr(node.right)

打印结果为：A B D C E G H F I
接下来的中、后序都本分类似：

中序

1
2
3
4
5
6
7
8
def reclnr(node):
    if node is None:
        return
    if node.left:
        reclnr(node.left)
    print node,
    if node.right:
        reclnr(node.right)

输出结果：D B A G E H C F I

后序

1
2
3
4
5
6
7
8
def reclrn(node):
    if node is None:
        return
    if node.left:
        reclrn(node.left)
    if node.right:
        reclrn(node.right)
    print node,

输出结果：D B G H E I F C A

非递归方法

　　非递归方法才是相对比较困难的，像很多递归问题的非递归解法一样，这里我们也要用到栈。因为树的结构是不确定的，拿前序的方法来举例，本来的顺序是ＮＬＲ，到达一个节点，打印Ｎ之后，就应该进入Ｌ，处理完Ｌ后处理Ｒ，但是无法确定何时能够回到Ｒ，所以我们在进入Ｌ之前应该先将Ｒ保存到栈中，这有点类似函数调用时的保存现场，都是利用栈的先进后出的特性来还原真实过程。

前序

1
2
3
4
5
6
7
8
9
def stacknlr(root):
    s = [root]
    while s:
        node = s.pop()
        while node:
            print node,
            if node.right:
                s.append(node.right)
            node = node.left

输出：A B D C E G H F I

中序

　　中序和前序相分类似

1
2
3
4
5
6
7
8
9
10
def stacklnr(root):
    node = root
    s = []
    while node or s:
        while node:
            s.append(node)
            node = node.left
        node = s.pop()
        print node,
        node = node.right

result:D B A G E H C F I

后序

　　后序就相对复杂一些，因为父节点是最后打印的，之前要进入左右子节点再返回，所以并不能一次压栈出栈就完成，而是需要判断更多的条件。
　　以下情况下，可以打印当前节点：

  1. 左右节点为空
  2. 从左节点返回，而右子节点为空
  3. 从右节点返回

以下是程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def stacklrn(root):
  pre = None
  s = [root]
  while s:
      node = s.pop()
      if node.left is None and node.right is None or \
                              node.right is not None and node.right == pre or \
                              node.left == pre and node.right is None:
          print node,
          pre = node
      elif node.left and node.left != pre:
          s.append(node)
          s.append( node.left)
      elif node.right:
          s.append(node)
          s.append( node.right)

结果：D B G H E I F C A

层序-队列

层序是比较特殊的，不适合和递归也不适合栈，但是用队列却十分简单。从根节点开始，打印一个节点时将其左右子节点加入队列，直到队列为空。

1
2
3
4
5
6
7
8
9
10
11
def tier(root):
    import Queue
    q = Queue.Queue(maxsize=0)
    q.put(root)
    while not q.empty():
        c = q.get()
        print c,
        if c.left:
            q.put(c.left)
        if c.right:
            q.put(c.right)

输出：A B C D E F G H I

附录 完整代码

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
__author__ = 'chen'
class Node:
    def __init__(self, name, left, right):
        self.name = name
        self.left = left
        self.right = right
    def __str__(self):
        return self.name
def recnlr(node):
    if node is None:
        return
    print node,
    if node.left:
        recnlr(node.left)
    if node.right:
        recnlr(node.right)
def reclnr(node):
    if node is None:
        return
    if node.left:
        reclnr(node.left)
    print node,
    if node.right:
        reclnr(node.right)
def reclrn(node):
    if node is None:
        return
    if node.left:
        reclrn(node.left)
    if node.right:
        reclrn(node.right)
    print node,
def stacknlr(root):
    s = []
    node = root
    while node:
        while node:
            print node,
            if node.right:
                s.append(node.right)
            node = node.left
        if s:
            node = s.pop()
def stacknlr3(root):
    s = [root]
    while s:
        node = s.pop()
        while node:
            print node,
            if node.right:
                s.append(node.right)
            node = node.left
def stacknlr2(root):
    s = []
    node = root
    while node:
        print node,
        if node.left:
            if node.right:
                s.append(node.right)
            node = node.left
        elif node.right:
            node = node.right
        elif s:
            node = s.pop()
        else:
            break
def stacklnr(root):
    node = root
    s = []
    while node or s:
        while node:
            s.append(node)
            node = node.left
        node = s.pop()
        print node,
        node = node.right
def tier(root):
    import Queue
    q = Queue.Queue(maxsize=0)
    q.put(root)
    while not q.empty():
        c = q.get()
        print c,
        if c.left:
            q.put(c.left)
        if c.right:
            q.put(c.right)
def stacklrn(root):
    pre = None
    s = [root]
    while s:
        node = s.pop()
        if node.left is None and node.right is None or \
                                node.right is not None and node.right == pre or \
                                node.left == pre and node.right is None:
            print node,
            pre = node
        elif node.left and node.left != pre:
            s.append(node)
            s.append( node.left)
        elif node.right:
            s.append(node)
            s.append( node.right)
if __name__ == "__main__":
    root = Node("A", Node("B", Node("D", None, None), None),
                Node("C", Node("E", Node("G", None, None), Node("H", None, None)),
                     Node("F", None, Node("I", None, None))))
    print "recursive nlr:",
    recnlr(root)
    print ""
    print "recursive lnr:",
    reclnr(root)
    print ""
    print "recursive lrn:",
    reclrn(root)
    print ""
    print "stack    nlr3:",
    stacknlr3(root)
    print ""
    print "stack    nlr2:",
    stacknlr2(root)
    print ""
    print "stack     lnr:",
    stacklnr(root)
    print ""
    print "stack     lrn:",
    stacklrn(root)
    print ""
    print "tier      lnr:",
    tier(root)
    print ""

output:

1
2
3
4
5
6
7
8
9
chen@vaio:/data/PycharmProjects/tree$ python tree.py 
recursive nlr: A B D C E G H F I 
recursive lnr: D B A G E H C F I 
recursive lrn: D B G H E I F C A 
stack    nlr3: A B D C E G H F I 
stack    nlr2: A B D C E G H F I 
stack     lnr: D B A G E H C F I 
stack     lrn: D B G H E I F C A 
tier      lnr: A B C D E F G H I

Contents
  1. 1. 节点的表示
  2. 2. 前中后序－递归
    1. 2.1. 前序：
    2. 2.2. 中序
    3. 2.3. 后序
  3. 3. 非递归方法
    1. 3.1. 前序
    2. 3.2. 中序
    3. 3.3. 后序
  4. 4. 层序-队列
  5. 5. 附录 完整代码