A Directory traversal is a very complex tree traversal!

In a normal tree structure you have three basic ways of traversal...

      Depth First           Top-Down                Breath
          7                    1                       1
        /   \                /   \                   /   \
       3     6              2     5                 2     3
      / \   / \            / \   / \               / \   / \
     1   2 4   5          3   4 6   7             4   5 6   7

In a directory traversal, each node consists of a often very list of filenames
of both sub-directory and non-directory filenames.  This vastly complicates
matters and the definition of exactly what order a directory is travered.

Note that this is not just for file directories, but also other sorts of
directories, such as LDAP directory tree of entries, or a complex data
structure.

First the exact order of the filename list to be traversed at a directoiry
node is highly variable.  Especially as the order the system presents files
to a calling program may be dependant on file creation/deletion order, or
randomised hash key order.

As such within the directory the names could be processed in...

   unsorted "as found" order
   alphetically sorted (case sensitive or insensitive?)
   a user specified order.  (EX: certian files first, then the rest after)

Then you have the question on if you seperate sub-directory components
from the list before or during processing (forming two seperate traversals of
each directory node.  So with the filename list do you...

   do each non-directory and directory in the order given.
   do each file entry  THEN do each directory entry
   do each directory entry  THEN  do each file entry

After that you have the complication of exactly when do you traverse the
sub-directories of the current directory.

Do you traverse each of the sub-directories
  before/after processing ALL the filenames in the parent directory
  only before/after looking at each non-directory filename
  traverse a sub-directory immediately before/after that directory filename

As you can see directory traversal has a lot of posibilities.

-------------------------------------------------------------------------------
Specific directory traversal programs...

UNIX "find" command...
  traverse in unsorted directory listing order (files/directory names mixed)
  by default traversal each sub-directory immediatally after processing
    the directory filename.

  What this means is that when a directory is being processes only some of the
  non-directory files in the parent directory may have been processed, and
  what has or has not been processed depends on the randomised file creation
  order.

  The "-depth" changes sub-directory traversal from immediately before
  to immediately after the contents of that directory


Perl File::Find
  Perl version 5.7
      Optional sorting of the retrieved directory listing,
      Process all file filenames in a directory first
      Then process each sub-direcory (in reverse order)
        processing a dir filename immediately before traversing it.

  Version 5.8 File::Find is exactly as 5.7 but a patch I provided makes the
  directory handling in the correct order.   The file - directory seperation
  is still present (no option), and in most cases desirable.

  The "bydepth" makes the directory filename processing AFTER that
  sub-directory is processed.  That is all it does, filenames are still
  processed in the same order as before,  non-directory files first, then
  directory files.

-------------------------------------------------------------------------------
Anthony Thyssen  7 November 2003
-------------------------------------------------------------------------------