前些日子，写了一篇关于二叉树和遍历的文章。原因是看到有些讨论热衷于研究怎么样给一个二叉树的库实现线性的ireator.
结果文章出来，因为我本来想让代码说话，而csdn贴代码的功能太差，没人看懂了我的意思。
但是，通过在allaboutprogram上和纸鹤兄的讨论，我发现好象这个东西无论如何是值得写明白的。搞明白它对理解面向接口，基于概念而不是实现的设计思想有很大好处。
各位有兴趣的可以到http://www.allaboutprogram.com/bb/viewtopic.php?t=629 去看代码和具体的讨论。那里除了讨论了独立于任何二叉树实现的iterator的设计，也扩展到了对n叉树，如文件目录的iterator.
我这里就不贴代码了。不过简要地介绍一下想法。
我批评的那个贴子里面，详细地研究了怎么样做一个二叉树，以及怎样给这个二叉树建立线性的前序，中序和后序iterator.
我批评它的原因是，前序，中序，后序这些遍历逻辑是独立于任何二叉树的实现的。把两个互相之间没有耦合的概念搅在一起，只会把问题搞复杂了。
我在我的文章里提到了“独立实现iterator”的概念。但是，想来这个提法可能会有不同的理解，所以才造成了后来的争吵。
这里，我举一个例子。
假设你的老板跟你说： 你能不能做一个给二叉树的线性访问的iterator的东西？
你说： 没问题。对了，这个二叉树的代码在哪里？
老板：代码？还没有呢。我们在加拿大的程序员会搞定它的。不过现在还没开始写呢。
你说： 哦。好吧。那么有没有文档啦，或者spec之类的呢？
老板： 我让你写iterator, 又没让你写二叉树。再说，“二叉树”，你不懂吗？要文档干什么？我们可能自己写二叉树，也可能看看价格合适从外面买一个回来，甚至还有可能混用买来的和自己写的。所以，现在还没有文档呢。
那么，这种要求不可能实现吗？
我要说，它是完全可以实现的。实际上，你甚至可以自己写一个iterator的库，实现这些遍历逻辑，然后卖给不同的树的实现者作为附加功能。（前提是有人肯花钱买这么个简单的东西） 。或者，至少，我可以把我的iterator库卖给那位想给自己的树实现iterator的仁兄。
要实现这些标准的遍历逻辑，完全不必要知道树的具体实现。就象你可以写排序算法，而不必知道具体的容器一样。
为什么很多stl容器不提供类似排序的功能？就是因为这些算法往往是独立于具体容器的实现的。 只要你能为你的容器提供排序所要求随机iterator接口就行。
同理，树的线性化这种算法也是独立于具体的树实现的。只要你能为你的树提供线性化所要求的树接口就行。
在纸鹤和我的讨论中，我就通过实现一个adapter把一个n叉树的遍历逻辑应用到了文件目录系统上。
所以，在树实现里面研究怎么线性化就象在std::vector里面研究怎么排序一样，有点走错了方向的感觉。
本文地址：http://com.8s8s.com/it/it29220.htm