How to traverse a windows explorer like tree structure

Question

Hello All.

I am working on designing a FTP client and need some help with designing a feature which its sole purpose is to be able to traverse a tree like structure and upload the folders and files which have been selected by the user.

So essentially the user can select multiple folders and files at one time from the local file and folder View. Then I need to be able to traverse each folder selected to search and locate sub folders until all folders and sub folders and files have been uploaded to the FTP Server.

I am somewhat familiar with Tree like data structure and traversing a binary tree using recursion. However in my case the user may have many/several sub folders and files for all paths and thought the the overhead of using recursion would be substantial. I also realize that anything done with recursion can be done with do/while looping structure.

Any suggestions or advice would be appreciated. If there is already readily available code please provide a link.

Thanks

Answer 1

http://en.wikipedia.org/wiki/Tree_traversal

Basically you got Preorder, Inorder, Postorder and Level-order. Each one with their own pro's n con's, but in the end, they do the same thing.

The wikipage got pseudo-code implementations for the recursive and the iterative versions of the algorithms. I won't bother re-doing them here, but if you need help to understand them, please post here, and I'll go through them step-by-step :P

[EDIT] Eeek, yikes, etc! :D Seems like I were just a tad too fast on my trigger finger there. The link only provides algorithms for traversing binary trees. However, the principle remains the same, except that instead of a "left" and a "right" child on a given node, you now got 0 to many children.

Say you have a tree with an arbitary number of childs on each node, you'd traverse it like this, using some sort of In/Out data structure (queues or stacks, basically). The one you choose for this will dictate in which order you search your tree. In this example Ill use a queue:

public void TraverseTree(Node rootNode)
{
   Queue nodeQueue();
   nodeQueue.push(rootNode);   //The first node to examine is the rootNode
   Node currentNode;

   //Okay, here we go. We will continue till the queue is empty. The queue will
   //be empty when we've seen all children of all children :)
   while (!nodeQueue.IsEmpty())   
   {
       currentNode = nodeQueue.Pop();   //Get the next node to examine

       DoStuffToNode(currentNode);      //Do whatever we want to the node (in your case
                                        //do some FTP stuff to the node (aka. the file)

       //Okay, we're done with this node. Now, let's add all the children of this node
       //To the queue of nodes we want to examine
       foreach(Node child in currentNode.children)   
          nodeQueue.push(child);
   }
}

You can do this with an array if you want to, but it will take some hoax, highly likely to be ineffective and not really intuitive.

Let's assume you want to transfer C: to an FTP-site (for the sake of explanation)

Using a stack, you will traverse ALL of the children of your current node, before going to the grand-children. So, you'd first Create a folder called "C:", then "Program Files", then "Windows" - And then afterwards you'd go into "Program files" and create "Adobe", then "Microsoft" etc. etc..

Using a queue, you will traverse all ancestors of a child before going to the next child. We would then first create "Program files", then "Adobe", then "Microsoft" etc. etc. and afterwards create "Windows".

I really hope I'm making myself clear here :) It's a lot easier to explain with a single animation.

The basic algorithm is this:

1. Go to the next node in our queue or stack
2. Do stuff to current node
3. Add all children of the current node to the queue or stack
4. Go to 1

Oh, btw, I dont have any experience with MFC, but can't you use a std::queue<> instead of a CArray? :)

Answer 2

For an operation like this, I would recommend creating a function to parse a folder that adds all the files in the folder into an array or hash of some sort. If the function comes across a folder in the directory, then it will call it self. Here's some pseudo code for you.

static void processFolder(string folderName, string[][] array)
{
    if (FolderLibs::hasChildFolders(folderName))
    {
        foreach(string childFolderName in FolderLibs::getChildFolderNames(folderName))
        {
            processFolder(childFolderName, array);
        }
    }

    foreach(string fileName in FolderLibs::getChildFileNames)
    {
        array[folderName].push(fileName);
    }    
}

void main()
{
    string rootFolder = "/";
    processFolder(rootFolder);
}

Anyway, that's my sad attempt at pseudo code :) Hopefully it helps though.

Answer 3

Thanks to both replies I'll definitely take a look at both options and hopefully put something together that works.

Answer 4

Meeh I did have some questions about the pseudo code that wikipedia provides. Here is one of the psuedo code using interations. My comments are next to each line.

public void traverseTree(Node root)
{
   Stack nodes = new Stack();          // this can be a CArray ?
   nodes.push(root);                   // are we adding to back or front of CArray ?
   Node currentNode;                   // OK
   while (! nodes.isEmpty()){          // OK
      currentNode = nodes.pop();       // pop from front of CArray ?
      Node right = currentNode.right(); // don't know what is node to right ? parent ?
      if (right != null)
         nodes.push(right);
      Node left = currentNode.left();   // don't know what is node to left ? child ?
      if (left != null)
         nodes.push(left);      
      System.out.println("Node data: "+currentNode.data);
   }
}

Answer 5

You are too caught up on the idea that you need to avoid recursion. There is no need -- recursion will make the algorithms infinitely simpler.

We were using recursion intensively back when we had only 16 MB of RAM. Surely with today's Gigabyte machines, memory is abundant.

To look at it another way: typically a folder will be at most 5 deep. Let's assume that it is much deeper -- say 1000. And say that you typically have 5 local variables, of size e.g. a long -- 4 x 2 = 8 bytes. For folders of depth 1000, you need 8,000 bytes on the stack - 8MB.

Say you have 4 GB of main memory -- you will use only .0007 % of your memory on a recursive algorithm. So don't worry about the "inefficiency" of recursion - what would be inefficient is to make a verbose, inelegant, bug-prone non-recursive version of an essentially recursive algorithm.

Answer 6

Just to show you how easy trees are to handle using recursion, here's recursive algorithms for generating a random tree, printing it out recursively, and printing out just the selected nodes recursively.

Module Module1

Private randGen As New Random()

''' <summary>
''' Max depth of the tree.
''' </summary>
Private MAX_DEPTH As Integer = 3

Private MAX_CHILDREN As Integer = 5

''' <summary>
''' Node of a tree with any number of children.
''' Leave Nodes have no children.
''' </summary>
''' <remarks></remarks>
Private Class Node
    Public children As List(Of Node) = Nothing
    Public name As String
    Public isSelected As Boolean = False
End Class

''' <summary>
''' Create a random tree, of at most depth, and return
''' the root.
''' </summary>
Private Function createTreeAux(ByVal depth As Integer) As Node
    Dim node As New Node
    ' generate random name
    node.name = "leaf" & randGen.Next().ToString
    ' randomly select it or not.
    node.isSelected = randGen.Next(0, 100) > 50

    ' create leaf node
    If depth = 0 Then
        Return node
    End If

    ' create children
    Dim numChildren As Integer = randGen.Next(1, MAX_CHILDREN)
    node.children = New List(Of Node)
    For i As Integer = 0 To numChildren - 1
        node.children.Add(createTreeAux(depth - 1))
    Next
    Return node
End Function

''' <summary>
''' Top level function for creating a random tree.
''' </summary>
''' <returns></returns>
''' <remarks></remarks>
Private Function createTree() As Node
    Return createTreeAux(MAX_DEPTH)
End Function

''' <summary>
''' Auxiliary function for printing out the selected nodes of
''' the tree. if selectedOnly is true, then only the selected nodes
''' are printed out. Otherwise the selected nodes have their name
''' pre-pended with an asterix "*".
''' </summary>
''' <param name="node"></param>
''' <param name="depth"></param>
Private Sub printTreeAux(ByVal node As Node, ByVal depth As Integer, _
                             ByVal selectedOnly As Boolean)
    If node Is Nothing Then
        Return
    End If

    ' indent
    For i As Integer = 0 To depth - 1
        Console.Write("  ")
    Next
    ' print node label
    If Not selectedOnly Or node.isSelected Then
        If node.isSelected Then
            Console.Write("*")
        End If
        Console.WriteLine(node.name)
    End If
    If Not node.children Is Nothing Then
        For Each child In node.children
            printTreeAux(child, depth + 1, selectedOnly)
        Next
    End If
End Sub

''' <summary>
''' Print out the selected nodes of the tree rooted 
''' at root.
''' </summary>
''' <param name="root">root of the tree to be printed</param>
Private Sub printSelected(ByVal root As Node)
    Console.WriteLine("Printing Selected Nodes Only")
    printTreeAux(root, 0, True)
End Sub

''' <summary>
''' Prints out the entire tree 
''' </summary>
''' <param name="root">root of the tree to be printed</param>
Private Sub printTree(ByVal root As Node)
    Console.WriteLine("Printing Entire Tree")
    printTreeAux(root, 0, False)
End Sub

''' <summary>
''' Do a test run by generating a random tree and then printing out
''' the entire tree, then just the selected nodes.
''' </summary>
Private Sub test()
    Dim tree As Node = createTree()
    printTree(tree)
    printSelected(tree)

End Sub

Sub Main()
    ' just do 5 test runs
    For i As Integer = 1 To 1
        Console.WriteLine("Run " & i.ToString())
        test()
    Next
    Console.ReadLine()
End Sub

End Module

Answer 7

Just wanted to thank everyone for taking time to post their comments. I simply followed the algorithm which Meeh has posted and used the interation approach (maybe for fun I will later on try using using recursion to see if runs faster) and so far I have code that works.

Appreciate everone's help.

Victor