筹备过互联网公司的服务端岗位面试的人，对于二叉树的三种遍历形式想必是一五一十。假如以类 BinaryTree 定义一棵二叉树

class BinaryTree:
    def __init__(self, left, right, value):
        self.left = left
        self.right = right
        self.value = value

实现一个前序遍历的算法便是信手拈来的事件

def preorder_traversal(tree, func):
    """前序遍历二叉树的每个节点。"""
    if tree is None:
        return
    func(tree.value)
    preorder_traversal(tree.left, func)
    preorder_traversal(tree.right, func)

随着行业曲率的增大，要求写出不应用递归的版本也没什么过分的

def iterative_preorder_traversal(tree, func):
    nodes = [tree]
    while len(nodes) > 0:
        node = nodes.pop()
        func(node)
        if node.left is not None:
            nodes.append(node.right)
        if node.left is not None:
            nodes.append(node.left)

始终以来，我感觉这种用一个显式的栈来代替递归过程中隐式的栈的做法就是镜花水月。但最近却找到了它的一个用武之地——用于实现iterator。

iterator是个啥？

这年头，iterator曾经不是什么陈腐事物了，许多语言中都有反对，维基百科上有一份清单列出了比拟出名的语言的 iterator 个性。依照 Python 官网的术语表中的定义，iterator示意一个数据流，重复调用其 __next__ 办法能够一个接一个地返回流中的下一项数据。将内置函数 iter 作用于 list、str、tuple 类型的对象，能够取得相应的迭代器

$ cat get_iter.py
# -*- coding: utf8 -*-
if __name__ == '__main__':
    values = [[1, 2, 3],
        'Hello, world!',
        (True, None),
    ]
    for v in values:
        print('type of iter({}) is {}'.format(v, type(iter(v))))
$ python get_iter.py
type of iter([1, 2, 3]) is <class 'list_iterator'>
type of iter(Hello, world!) is <class 'str_iterator'>
type of iter((True, None)) is <class 'tuple_iterator'>

写一个前序遍历的iterator

一个 iterator 对象必须要实现 __iter__ 和__next__办法：

• __iter__只须要返回 iterator 对象本身即可；
• 顾名思义，__next__负责返回下一个元素。

仔细观察一下前文中的 iterative_preorder_traversal 函数能够看出：

• nodes = [tree]属于初始化逻辑；
• len(nodes) > 0用于判断是该当抛出StopIteration，还是该当持续返回下一个值（nodes.pop()）；
• 最初四行就是负责填充 nodes，好让它能够在下一次调用__next__ 的时候有值能够返回的。

到这里，iterator的具体实现代码曾经跃然纸上了

class BinaryTreePreorderIterator:
    def __init__(self, root):
        nodes = []
        if root is not None:
            nodes.append(root)
        self.nodes = nodes

    def __iter__(self):
        return self

    def __next__(self):
        if len(self.nodes) == 0:
            raise StopIteration
        node = self.nodes.pop()
        if node.right is not None:
            self.nodes.append(node.right)
        if node.left is not None:
            self.nodes.append(node.left)
        return node.value

结构一棵这样的满二叉树

用 BinaryTreePreorderIterator 能够正确地打印出每一个节点的值

if __name__ == '__main__':
    tree = BinaryTree(
        BinaryTree(BinaryTree(None, None, 1), 
            BinaryTree(None, None, 3), 
            2,
        ),
        BinaryTree(BinaryTree(None, None, 5), 
            BinaryTree(None, None, 7), 
            6,
        ),
        4,
    )
    for n in BinaryTreePreorderIterator(tree):
        print('{}\t'.format(n), end='')
# 打印内容为：4    2    1    3    6    5    7

iterator的劣势

显然，iterator比起 preorder_traversal 更为灵便——很容易在 for-in 循环内增加各种各样的管制逻辑：用 continue 跳过一些值，或者用 break 提前结束遍历过程。这些在函数 preorder_traversal 中做起来会比拟顺当。

聪慧的你应该曾经发现了，大可不必将 preorder_traversal 拆解到一个构造方法和一个 __next__ 办法中。用 generator 写起来明明更加直观

def preorder_generator(tree):
    """返回一个可能以前序遍历的秩序遍历二叉树节点的 generator。"""
    nodes = [tree]
    while len(nodes) > 0:
        node = nodes.pop()
        yield node.value
        if node.left is not None:
            nodes.append(node.right)
        if node.left is not None:
            nodes.append(node.left)

然而，很多语言并不反对 generator。与之相比，iterator 要亲民得多，更容易移植。例如，即便是 Common Lisp 这种一穷二白的语言，也能够实现和 Python 的 iterator 以及 for 相似的成果

(in-package #:cl-user)

(defpackage #:com.liutos.binary-tree
  (:use #:cl))

(in-package #:com.liutos.binary-tree)

(defclass preorder-iterator ()
  ((nodes
    :initform nil)
   (tree
    :initarg :tree))
  (:documentation "前序遍历二叉树的迭代器"))

(defmethod initialize-instance :after ((instance preorder-iterator) &key)
  (with-slots (nodes tree)
      instance
    (when tree
      (push tree nodes))))

(defgeneric next (iterator)
  (:documentation "返回迭代器的下一个值。"))

(define-condition stop-iteration (error)
  ()
  (:documentation "Python 中 StopIteration 异样的等价物。"))

(defmethod next ((iterator preorder-iterator))
  (with-slots (nodes) iterator
    (when (null nodes)
      (error 'stop-iteration))

    (let ((node (pop nodes)))
      ;; 一个节点的构造为：(值 左子树 右子树)
      (when (third node)
        (push (third node) nodes))
      (when (second node)
        (push (second node) nodes))
      (first node))))

(defmacro for-in (var iterator &body forms)
  "将 iterator 中的值一一绑定到变量 var 上，并执行 forms 中的表达式。"
  (let ((iter (gensym)))
    `(let ((,iter ,iterator))
       (handler-case
           (loop
              (let ((,var (next ,iter)))
                ,@forms))
         (stop-iteration (c)
           (declare (ignorable c)))))))

(defparameter *tree*
  '(4 (2 (1 nil nil) (3 nil nil)) (6 (5 nil nil) (7 nil nil))))

(defun test-preorder-iterator ()
  "测试前序遍历迭代器。"
  (for-in n (make-instance 'preorder-iterator
                           :tree *tree*)
    (format t "~D~C" n #\Tab)))

后记

中序遍历和后序遍历也能够写成迭代器，证实略。

浏览原文