数据结构与算法分析 —— C 语言描述：树的遍历及应用

树有很多应用，流行的用法之一是包括 UNIX、VAX/VMS 和 DOS 在内的许多常用操作系统中的目录结构。

假设我们有一个根目录 A，A 目录下有一个目录 B，B 目录下有一个目录 C，C 目录下有一个文件 D。此时，文件 D 的全路径名就为 A/B/C/D，其中，每一个 “/” 后的每一个 “/”在树中都表示一条边，这个分级文件系统非常流行，因为它能够使得用户逻辑地组织数据。不仅如此，在不同目录下的两个文件还可以享有相同的名字，因为他们必然有从根开始的不同的路径从而具有不同的路径名。在 UNIX 文件系统中的目录就是含有它的所有儿子的一个文件。（在 UNIX 文件系统中的每个目录还有一项指向该目录本身以及另一项指向该目录的父目录。因此，严格说来，UNIX 文件系统不是树，而是类树（treelike）。）

假设我们想要列出目录中所文件中所有文件的名字。我们的输出格式将是：深度为 的文件的名字被 次跳格(tab) 锁进后打印出来。

算法的核心为递归程序 ListDir。为了显示根时不进行锁进，该例程需要从目录名和深度 0 开始。这里的深度是一个内部薄记变量，而不是主调例程能够期望知道的那种参数。因此，驱动例程 ListDirectory 用于将递归例程和外界连接起来。

算法的逻辑简单易懂。ListDir 的参数是到树中的某种引用。只要引用合理，则引用涉及的名字在进行适当次数的跳格锁进后被打印出来。如果是一个目录，那么我们递归地一个一个地处理它所有的儿子。这些儿子出在一个深度上，因此需要锁进一段附加的空格。

这种遍历的策略叫做先序遍历（preorder traversal）。在先序遍历中，对节点的处理工作是在它的诸儿子节点被处理之前进行的。当程序运行时，每个父节点恰好最多只执行一次，因为每个名字只输出一次。不仅如此，对于每个节点的每一个儿子节点最多只能执行一次。在遍历过程中，每个 for 循环终止在 NULL 指针上，但每个节点最多有一个这样的指针。因此，每个节点总的工作量是常数。如果有 N 个文件名需要输出，则运行时间就是 O(N)。

另一种遍历树的方法是后序遍历（postorder traversal）。在后序遍历中，在一个节点处的工作是在它的诸儿子节点被计算后进行的。

由于目录本身也是文件，因此它们也有大小。设我们想要计算被该树所有文件占用的磁盘区块的总数。最自然的做法是找出含有子目录中的块的个数。于是，磁盘块的总数就是子目录中的块的总数加上该目录使用的一个块。

如果不是一个目录，那么 SizeDirectory 只返回所占用的块数。否则，将被占用的块数与其所有子节点（递归地）发现的块数相加。