C#: 如何使这个方法非递归

Question

我有一个递归方法，用于删除空文件夹：

    private void DeleteEmpty(DirectoryInfo directory)
    {
        foreach (var d in directory.GetDirectories())
        {
            DeleteEmpty(d);
        }

        if (directory.GetFileSystemInfos().Length == 0)
        {
            try
            {
                directory.Delete();
            }
            catch (Exception)
            {
                // Already gone, no permission, not empty, et cetera
            }
        }
    }

如何重构这个方法，使其不再是递归的？

- Svish

---

你为什么想要这样做？ 这本质上是递归的。 - Loren Pechtel

Answer 1

标准的重构方法是将原本要传递给函数的数据存储在一个LIFO（即栈）或FIFO队列中。请注意，这并不改变渐进空间使用情况；您使用自己的数据结构而不是调用堆栈。

如果您可以定义“下一个兄弟”函数，则可以使用常数 附加 空间访问节点。这是因为目录图（不含文件）由于父指针而基本上是无向的。伪代码：

nextBranchingSibling(sibling):
  while sibling exists
    if sibling has children
      return sibling
    sibling = nextSibling(sibling)
  return null

nextBranch(node):
  if node is marked
      unmark node
  else
      if nextBranchingSibling(firstChild(node)) exists
          return nextBranchingSibling(firstChild(node))
  if nextBranchingSibling(nextSibling(node)) exists
      return nextBranchingSibling(nextSibling(node))
  mark parent(node)
  return parent(node)

prune(node):
  while node exists:
    tmpNode = node
    node    = nextBranch(node)
    if count of tmpNode's children is 0
      delete tmpNode

请注意，实际上您并没有完全使用O(1)的空间，因为目录结构本身是O(n)。像DirectoryInfo.GetDirectories这样的方法可以消除在nextBranchingSibling中循环的需要。

- outis

---

任意展开的简洁解释很好。 - user166390

刚刚注意到伪代码会在第一个分支处陷入困境，无法继续执行后续分支。将使用标记进行更新。 - outis

Answer 2

private static Queue<DirectoryInfo> directoryQueue = new Queue<DirectoryInfo>();
private void DeleteEmpty(DirectoryInfo directory)
{
    directoryQueue.Enqueue(directory);
    while (directoryQueue.Count > 0)
    {
        var current = directoryQueue.Dequeue();
        foreach (var d in current.GetDirectories())
        {
            directoryQueue.Enqueue(d);
        }

        if (directory.GetFileSystemInfos().Length == 0)
        {
            try
            {
                directory.Delete();
            }
            catch (Exception)
            {
                // Already gone, no permission, not empty, et cetera
            }
        }
    }
}

- Alex Reitbort

Answer 3

试试这个：

private void DeleteEmpty(string path)
{
    string[] directories = Directory.GetDirectories(
        path, "*", SearchOption.AllDirectories);

    // you should delete deeper directories first
    //      .OrderByDescending(
    //          dir => dir.Split(Path.DirectorySeparatorChar).Length)
    //              .ToArray();

    foreach (string directory in directories)
    {
        DirectoryInfo info = new DirectoryInfo(directory);
        if (info.GetFileSystemInfos().Length == 0)
        {
            info.Delete();
        }
    }

    // If you wanna a LINQ-ish version
    // directories.Where(dir => 
    //     new DirectoryInfo(dir).GetFileSystemInfos().Length == 0)
    //         .ToList().ForEach(dir => Directory.Delete(dir));
}

另一个提高性能的方法是：如果您尝试删除一个包含文件的目录，则应跳过所有父级，因为它们也将失败。

- Rubens Farias

---

不错，我甚至没有想到这个的SearchOption，有点棘手！ - Wil P

我喜欢这个，在这种情况下，这可能是最简单的方法。 - RichardOD

Answer 4

你可以使用本地堆栈，在堆栈不为空的情况下循环。

public void DeleteDirectories(DirectoryInfo directoryInfo, bool deleteFiles)
{
    Stack<DirectoryInfo> directories = new Stack<DirectoryInfo>();
    directories.Push(directoryInfo);

    while (directories.Count > 0)
    {
        var current = directories.Peek();

        foreach (var d in current.GetDirectories())
            directories.Push(d);

        if (current != directories.Peek())
            continue;

        if (deleteFiles)
            foreach (var f in current.GetFiles())
            {
                f.Delete();
            }

        if (current.GetFiles().Length > 0 || current.GetDirectories().Length > 0)
            throw new InvalidOperationException("The directory " + current.FullName + " was not empty and could not be deleted.");

        current.Delete();

        directories.Pop();
    }
}

- Chris Patterson

---

你想要使用栈，因为在删除父目录之前，必须先删除子目录。 - Chris Patterson

这个程序也会检查文件吗？还是只检查目录？你能简单地演示一下它的工作原理吗？我不确定我是否完全理解了它... - Svish

它从指定的目录开始。它获取所有子目录并将它们添加到堆栈中。如果找到了目录，则当前目录不再位于堆栈顶部，因此它开始通过推送到堆栈上的目录来处理目录。堆栈将根据目录树的深度填充目录 - 直到最深的路径。然后它会往回走。如果您想删除文件，请添加foreach(var f in current.GetFiles())并调用f.Delete()以删除文件。更新的源如上所示。 - Chris Patterson

Answer 5

我曾经遇到同样的问题，然后我创建了一个不错的（在我看来）解决方案：从根目录开始，我“递归”获取子目录并将它们存储在ArrayList对象中。这样，我创建了一个列表，首先包含较高级别的目录，最后是更深层次的嵌套目录。这个数组理想情况下使用levels ArrayList对象中存储的索引分成子数组。

通过这种方式，我可以首先检查更深层次的目录，如果它们为空，则删除它们，然后逐级返回到根级别。

例如：

    private void directoryCleanup(string root)
    {
        try
        {
            // Create directory "tree"
            ArrayList dirs = new ArrayList();
            // Beginning and ending indexes for each level
            ArrayList levels = new ArrayList();
            int start = 0;
            dirs.Add(root);
            while (start < dirs.Count)
            {
                ArrayList temp = new ArrayList();
                for (int i = start; i < dirs.Count; i++)
                {
                    DirectoryInfo dinfo = new DirectoryInfo((string)dirs[i]);
                    DirectoryInfo[] children = dinfo.GetDirectories();
                    for (int j = 0; j < children.Length; j++)
                    {
                        temp.Add(children[j].FullName);
                    }
                    Array.Clear(children, 0, children.Length);
                    children = null;
                    dinfo = null;
                }
                start = dirs.Count;
                levels.Add(dirs.Count);
                dirs.AddRange(temp);
                temp.Clear();
                temp = null;
            }
            levels.Reverse();
            // Navigate the directory tree level by level, starting with the deepest one
            for (int i = 0; i < levels.Count - 1; i++)
            {
                int end = (int)levels[i] - 1;
                int begin = (int)levels[i + 1];
                for (int j = end; j >= begin; j--)
                {
                    string path = (string)dirs[j];
                    if (Directory.GetFileSystemEntries(path).Length == 0)
                    {
                        Directory.Delete(path);
                    }
                }
            }
            levels.Clear();
            levels = null;
            dirs.Clear();
            dirs = null;
        }
        catch (IOException ioex)
        {
            // Manage exception
            return;
        }
        catch (Exception e)
        {
            // Manage exception
            return;
        }
    }

- Andrea Martelli

Answer 6

创建一个队列，其中包含起始目录中的所有目录，然后在队列不为空的情况下，取出下一个项目，检查目录是否为空，如果是，则删除它，如果不是，则将所有子目录添加到队列中。

我不知道C#，但如果没有标准队列类型，链表或可变数组类型也可以正常工作。

伪代码：

directories = empty queue
until directories is not empty
    next = directories.shift
    if next is an empty folder
        delete it
    or else
        add all the subdiretories to the queue

- Jeffrey Aylesworth