二叉树的遍历方法有五种：（1）前序遍历（2）中序遍历（3）后序遍历（4）深度优先遍历（5）广度优先遍历（层次遍历）单这些遍历算法并不具有通用性。需要使用更通用的方法访问结点对象，于是我们在遍历二叉树上添加迭代功能。
为了方便遍历二叉树的所有结点，我们想为二叉树添加迭代功能，以实现通用的迭代工具。
二叉树的遍历算法
我们定义二叉树的结点：
1
2
3
4
5
6
| class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
|
Pyton语法简洁，我们使用Python作伪代码
前序遍历
1
2
3
4
5
6
7
8
| def preorder_traverse(node):
if not node:
return
do(node)
if node.left:
inorder_traverse(node.left)
if node.right:
inorder_traverse(node.right)
|
中序遍历
1
2
3
4
5
6
7
8
| def inorder_traverse(node):
if not node:
return
if node.left:
inorder_traverse(node.left)
do(node)
if node.right:
inorder_traverse(node.right)
|
后序遍历
1
2
3
4
5
6
7
8
| def deorder_traverse(node):
if not node:
return
if node.left:
inorder_traverse(node.left)
if node.right:
inorder_traverse(node.right)
do(node)
|
可以看到这三种遍历方法很相似，只是处理结点的位置不一样，可见递归的优雅
深度优先遍历
我们使用一个栈结构做容器以实现深度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Stack:
def __init__(self):
self._q = []
def push(self, value):
self._q.push(value)
def pop(self):
return self._q.pop()
def empty(self):
return len(self._q) == 0
|
1
2
3
4
5
6
7
8
9
10
11
12
| def traverse_tree_depth(tree):
if not tree:
return
stack = Stack()
stack.push(tree)
while not stack.empty():
p_node = stack.pop()
do_something(p_node)
if p_node.left:
stack.push(p_node.left)
if p_node.right:
stack.push(p_node.left)
|
广度优先遍历算法（层次遍历）
广度优先遍历算法参考旧文从上往下打印二叉树，具体的实现如下
实现一个简单队列做容器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Queue:
def __init__(self):
self._q = []
def put(self, item):
self._q.append(item)
def get(self):
item = self._q[0]
del self._q[0]
return item
def empty(self):
return len(self._q) == 0
|
层次遍历算法
1
2
3
4
5
6
7
8
9
10
| def print_tree_from_top_to_bottom(root):
queue = Queue()
queue.put(root)
while not queue.empty():
node = queue.get()
print(node)
if node.left:
queue.put(node.left)
if node.right:
queue.put(node.right)
|
二叉树迭代算法
上面五种二叉树的遍历算法中，并没有通用性，我们需要实现了do_someting函数，以供遍历二叉树的函数调用，但在do_someting函数的需求没有明确前，遍历二叉树的算法无法实现封装。为了解决这个问题，在Python里可以使用迭代器。
下面以中序遍历和深度优先遍历算法为例，其他的实现思路是一样的。
1
2
3
4
5
6
7
| def inorder_traverse(tree):
if tree:
for x in inorder_traverse(tree.left):
yield x
yield tree
for x in inorder_traverse(tree.right):
yield x
|
这样，在没有明确do_someting的需求是实现通用的二叉树遍历迭代器，使用方法如下
1
2
| for node in inorder_traverse(tree):
do_someting(node)
|
深度优先的遍历过程有类似的处理
1
2
3
4
5
6
7
8
9
10
11
| def traverse_tree_depth(tree):
if tree:
stack = Stack()
stack.push(tree)
while not stack.empty():
p_node = stack.pop()
if p_node.left:
stack.push(p_node.left)
if p_node.right:
stack.push(p_node.left)
yield p_node
|
我们甚至可以通过一类类封装上面的过程，通过一个类封装实现树的五种遍历方法。采用Mixin方式，如果树类继承了下面实现的类，那么它就拥有了五种遍历树的方式。
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
| class TreeIterMixin:
def __init__(self, tree):
self._root = tree
def preorder_traverse(self):
for x in self._preorder(self._root):
yield x
def _preorder(self, node):
if node:
yield node
for x in self._preorder(node.left):
yield x
for x in self._preorder(node.right):
yield x
def inorder_traverse(self):
for x in self._inorder(self._root):
yield x
def _inorder(self, node):
if node:
for x in self._preorder(node.left):
yield x
yield node
for x in self._preorder(node.right):
yield x
def postorder_traverse(self):
for x in self._inorder(self._root):
yield x
def _postorder(self, node):
if node:
for x in self._preorder(node.left):
yield x
for x in self._preorder(node.right):
yield x
yield node
def depth_first_order_traverse(self):
if self._root:
stack = Stack()
stack.push(self._root)
while not stack.empty():
node = stack.pop()
if node.left:
stack.push(node.left)
if node.right:
stack.push(node.right)
yield node
def breadth_first_order_traverse(self):
if self._root:
queue = Queue()
queue.push(self._root)
while not queue.empty():
node = queue.pop()
if node.left:
queue.push(node.left)
if node.right:
queue.push(node.right)
yield node
|
上面就是Python的二叉树遍历的迭代算法的。后期更新Go版本。
完。
��。
