Как пройти через Windows Explorer, как древовидная структура

Question

Я работаю над созданием FTP-клиента и мне нужна помощь в разработке функции, единственной целью которой является возможность обхода древовидной структуры и загрузка папок и файлов, выбранных пользователем.

Таким образом, по сути, пользователь может выбрать несколько папок и файлов одновременно из локального просмотра файлов и папок. Затем мне нужно пройти через каждую выбранную папку для поиска и поиска подпапок, пока все папки, подпапки и файлы не будут загружены на FTP-сервер.

Я немного знаком с древовидной структурой данных и обходом двоичного дерева с помощью рекурсии. Однако в моем случае пользователь может иметь много / несколько вложенных папок и файлов для всех путей и думал, что издержки использования рекурсии будут существенными. Я также понимаю, что все, что делается с помощью рекурсии, может быть сделано с помощью do / while структуры цикла.

Любые предложения или советы будут оценены. Если код уже доступен, укажите ссылку.

Спасибо

Answer 1

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

По сути, у вас есть Предзаказ, Отмена, Постзаказ и Уровень порядка. У каждого свои «за» и «против», но, в конце концов, они делают то же самое.

В вики-странице были реализованы псевдокоды для рекурсивной и итеративной версий алгоритмов. Я не буду повторять их здесь, но если вам нужна помощь, чтобы понять их, пожалуйста, напишите здесь, и я пошагово расскажу о них: P

[редактировать] Eeek, Yikes, и т. Д.! : D Похоже, я был слишком быстр на моем спусковом пальце. Ссылка содержит только алгоритмы обхода двоичных деревьев. Однако принцип остается тем же, за исключением того, что вместо «левого» и «правого» дочернего элемента в данном узле теперь у вас есть 0 для многих дочерних элементов.

Скажем, у вас есть дерево с произвольным числом дочерних элементов на каждом узле, и вы должны проходить его таким образом, используя некую структуру данных In / Out (в основном очереди или стеки). Тот, который вы выберете для этого, будет определять, в каком порядке вы будете искать свое дерево. В этом примере я буду использовать очередь:

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);
   }
}

Вы можете сделать это с массивом, если хотите, но это потребует некоторого обмана, весьма вероятно, что он будет неэффективным и не очень интуитивным.

Предположим, вы хотите перенести C: на FTP-сайт (для пояснения)

Используя стек, вы пройдете ВСЕ дочерние элементы вашего текущего узла, прежде чем перейти к внукам. Итак, вы сначала создадите папку с именем «C:», затем «Program Files», затем «Windows» - а затем перейдите в «Program Files» и создайте «Adobe», затем «Microsoft» и т. Д. и т.д ..

Используя очередь, вы пройдете всех предков ребенка, прежде чем перейти к следующему ребенку. Затем мы сначала создадим «Программные файлы», затем «Adobe», затем «Microsoft» и т. Д. И т. Д., А затем создадим «Windows».

Я действительно надеюсь, что я проясняю себя здесь :) Это намного проще объяснить с помощью одной анимации.

Основной алгоритм таков:

1. Перейти к следующему узлу в нашей очереди или стеке
2. Делать вещи на текущий узел
3. Добавить все дочерние узлы текущего узла в очередь или стек
4. Перейти к 1

Да, кстати, у меня нет опыта работы с MFC, но разве вы не можете использовать std :: queue <> вместо CArray? :)

Answer 2

Просто чтобы показать вам, как легко обрабатывать деревья с помощью рекурсии, вот рекурсивные алгоритмы для генерации случайного дерева, его рекурсивной печати и рекурсивной печати только выбранных узлов.

Модуль Модуль1

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

Конечный модуль

Answer 3

Вы слишком увлечены идеей, что вам нужно избегать рекурсии. В этом нет необходимости - рекурсия сделает алгоритмы бесконечно проще.

Мы интенсивно использовали рекурсию, когда у нас было только 16 МБ ОЗУ. Конечно, на современных машинах Gigabyte памяти достаточно.

Чтобы взглянуть на это иначе: обычно папка будет не более 5 глубиной. Давайте предположим, что это намного глубже - скажем, 1000. И скажем, что у вас обычно есть 5 локальных переменных размером, например. длинный - 4 х 2 = 8 байт. Для папок глубиной 1000 в стеке требуется 8000 байт - 8 МБ.

Скажем, у вас есть 4 ГБ основной памяти - вы будете использовать только 0,0007% вашей памяти по рекурсивному алгоритму. Так что не беспокойтесь о «неэффективности» рекурсии - то, что было бы неэффективно, это сделать подробную, не элегантную, подверженную ошибкам нерекурсивную версию по существу рекурсивного алгоритма.

Answer 4

У меня есть несколько вопросов о псевдокоде, который предоставляет Википедия. Вот один из кодов psuedo, использующий целые числа. Мои комментарии рядом с каждой строкой.

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

Для такой операции я бы порекомендовал создать функцию для анализа папки, которая добавляет все файлы в папке в какой-либо массив или хэш. Если функция попадает в папку в каталоге, она будет вызывать ее самостоятельно. Вот какой-то псевдокод для вас.

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);
}

В любом случае, это моя грустная попытка псевдокода :) Надеюсь, это поможет.