准备过互联网公司服务端工作面试的人，一定对二叉树的三种遍历方式很熟悉。假设一棵二叉树由类BinaryTree定义classBinaryTree:def__init__(self,left,right,value):self.left=leftself.right=rightself.value=value很容易实现一个前序遍历算法defpreorder_traversal(tree,func):"""Preorder遍历二叉树的每个节点。"""iftreeisNone:returnfunc(tree.value)preorder_traversal(tree.left,func)preorder_traversal(tree.right,func)随着行业曲率的增加，要求写一个不使用递归的版本并不过分defiterative_preorder_traversal(tree,func):nodes=[tree]whilelen(nodes)>0:node=nodes.pop()func(node)ifnode.leftisnotNone:nodes.append(node.right)ifnode.leftisnotNone:nodes.append(node.left)很长一段时间，我认为这个被替换了一个显式栈和递归过程中的隐式栈方法就像是一个镜像。但是最近它找到了一个地方可以用来实现迭代器。什么是迭代器？如今，迭代器并不是什么新鲜事物，而且它在许多语言中都得到支持。维基百科有一个知名语言的迭代器特性列表。根据Python官方词汇表中的定义，iterator代表一个数据流，它的__next__方法可以被反复调用，逐条返回流中的下一项数据。将内置函数iter应用于list、str、tuple类型的对象，得到对应的迭代器$catget_iter.py#-*-coding:utf8-*-if__name__=='__main__':values=[1,2,3],'Hello,world!',(True,None),]forvinvalues:print('iter({})的类型是{}'.format(v,type(iter(v))))$pythonget_iter.pytypeofiter([1,2,3])isiter的类型(Hello,world!)isiter的类型((True,None))is写一个前序遍历的迭代器一个迭代器对象必须实现__iter__和__next__方法：__iter__只需要返回迭代器对象本身；顾名思义，__next__负责返回下一个元素。仔细看上一篇中的iterative_preorder_traversal函数可知：nodes=[tree]属于初始化逻辑；len(nodes)>0用来判断是应该抛出StopIteration，还是应该继续返回下一个值(nodes.pop());最后四行是负责填充节点，这样当它可以返回值的时候__next__下次调用。至此，迭代器的具体实现代码就准备好了。类BinaryTreePreorderIterator:def__init__(self,root):nodes=[]ifrootisnotNone:nodes.append(root)self.nodes=nodesdef__iter__(self):returnselfdef__next__(self):iflen(self.nodes)==0:raiseStopIterationnode=self.nodes.pop()ifnode.rightisnotNone:self.nodes.append(node.right)ifnode.leftisnotNone:self.nodes.append(node.left)returnnode.value构造这样一棵完整的二叉树使用BinaryTreePreorderIterator正确打印出每个节点的值if__name__=='__main__':tree=BinaryTree(BinaryTree(二叉树（无，无，1），二叉树（无，无，3），2，），二叉树（二叉树（无，无，5），二叉树（无，无，7），6，），4，）为ninBinaryTreePreorderIterator(tree):print('{}\t'.format(n),end='')#打印出来的内容是：4213657iterator的优点很明显，iterator比preorder_traversal灵活多了——很容易在for-in循环中加入各种控制逻辑：跳转和continue传递一些值，或者在函数preorder_traversal中使用break提前结束遍历过程会很尴尬。聪明的你应该已经发现，没有必要将preorder_traversal反汇编成一个构造函数和一个__next__方法。用generatordefpreorder_generator(tree)这样写显然更直观："""返回一个可以按照前序遍历的顺序遍历二叉树节点的生成器。"""nodes=[tree]whilelen(nodes)>0:节点=节点。pop()yieldnode.valueifnode.leftisnotNone:nodes.append(node.right)ifnode.leftisnotNone:nodes.append(node.left)但是很多语言不支持生成器。相比之下，迭代器要友好得多，也更容易移植。例如，即使像CommonLisp这样糟糕的语言也可以实现与Python的迭代器和for(in-package#:cl-user)(defpackage#:com.liutos.binary-tree(:use#:cl))(in-package#:com.liutos.binary-tree)(defclasspreorder-iterator()((nodes:initformnil)(tree:initarg:tree))(:documentation"Iteratorforpreordertraversalofbinarytree"))(defmethodinitialize-instance:after((instancepreorder-iterator)&key)(with-slots(nodestree)instance(whentree(pushtreenodes))))(defgenericnext(iterator)(:documentation"return的下一个值迭代器。”))(define-conditionstop-iteration(error)()(:documentation"等同于Python中的StopIteration异常。"))(defmethodnext((iteratorpreorder-iterator))(with-slots(nodes)iterator(when(nullnodes)(error'stop-iteration))(let((node(popnodes)));;a节点的结构为：(value左子树右子树)(when(第三个节点)(push(thirdnode)节点))(when(secondnode)(push(secondnode)节点))(firstnode))))(defmacrofor-in(variterator&bodyforms)"将迭代器中的值一一绑定到变量var上，并执行forms中的表达式。"(let((iter(gensym)))`(let((,iter,iterator))(handler-case(loop(let((,var(next,iter))),@forms))(stop-iteration(c)(declare(ignorablec))))))(defparameter*tree*'(4(2(1nilnil)(3nilnil))(6(5nilnil)(7nilnil))))(defuntest-preorder-iterator()"测试前序遍历迭代器。"(for-inn(make-instance'preorder-iterator:tree*tree*)(formatt"~D~C"n#\Tab)))后记中序遍历和后序遍历也可以写成迭代Device，证明从略。阅读原文
