c++ - 如何遍历类似树结构的Windows资源管理器

Question

我正在设计一个 FTP 客户端，需要一些帮助来设计一个功能，该功能的唯一目的是能够遍历树状结构并上传用户选择的文件夹和文件。

所以基本上用户可以从本地文件和文件夹 View 中一次选择多个文件夹和文件。然后我需要能够遍历每个选择的文件夹来搜索和定位子文件夹，直到所有的文件夹和子文件夹和文件都已经上传到FTP服务器。

我对类似树的数据结构和使用递归遍历二叉树比较熟悉。然而，在我的例子中，用户可能有许多/几个子文件夹和所有路径的文件，并认为使用递归的开销会很大。我还意识到任何用递归完成的事情都可以用 do/while 循环结构完成。

如有任何建议或建议，我们将不胜感激。如果已经有现成的代码，请提供链接。

谢谢

Answer 1

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

基本上你得到了预序、中序、后序和水平序。每个人都有自己的优点和缺点，但最终，他们做同样的事情。

维基页面获得了算法的递归和迭代版本的伪代码实现。我不会费心在这里重做它们，但是如果您需要帮助来理解它们，请在这里发帖，我将逐步完成它们:P

[编辑] Eeek，yikes，等等! :D 好像我的扳机手指有点太快了。该链接仅提供遍历二叉树的算法。然而，原则保持不变，只是给定节点上不再有“左”和“右”子节点，而是现在有 0 个子节点。

假设您有一棵树，每个节点上有任意数量的子节点，您将像这样遍历它，使用某种输入/输出数据结构(基本上是队列或堆栈)。您为此选择的将决定您搜索树的顺序。在这个例子中，我将使用一个队列:

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”等。等..

使用队列，您将遍历一个 child 的所有祖先，然后再转到下一个 child 。然后我们将首先创建“程序文件”，然后是“Adobe”，然后是“Microsoft”等等，然后再创建“Windows”。

我真的希望我在这里说清楚了:)用一个动画解释起来要容易得多。

基本算法是这样的:

1. 转到队列或堆栈中的下一个节点
2. 对当前节点做一些事情
3. 将当前节点的所有子节点加入队列或栈
4. 转到 1

哦，顺便说一句，我对 MFC 没有任何经验，但是你不能使用 std::queue<> 而不是 CArray 吗？ :)