从删除空目录算法中消除递归

本文关键字：递归 算法 删除 | 更新日期: 2023-09-27 18:26:33

我想我以前知道如何做到这一点，但似乎我已经忘记了。

我有一个递归算法来删除目录树中的所有空目录：

static bool DeleteDirectoriesRecursive(string path)
{
    var remove = true;
    foreach (var dir in System.IO.Directory.GetDirectories(path))
    {
        remove &= DeleteDirectoriesRecursive(dir);
    }
    if (remove &= (System.IO.Directory.GetFiles(path).Length == 0))
        System.IO.Directory.Delete(path);
    return remove;
}

我试图从这个算法中消除递归，而不是"修复"算法（即，类似的问题不使用remove变量，但我想保留它）。

我已经使用Stack<>类启动了一个新函数，但我想不出一个好的方法来返回基本路径并执行子目录确定的操作。我想解开无尾递归需要付出更多的努力。

从删除空目录算法中消除递归

由于Gabe在使用递归时提到了StackOverflowException的可能性，我受到启发，在没有它的情况下完成了这项工作。我将这里的代码作为起点。以下是我的想法。。。

public static bool DeleteDirectories(string root)
{
    bool removed = false;
    var dirs = new Stack<string>();
    var emptyDirStack = new Stack<string>();
    var emptyDirs = new Dictionary<string, int>();
    if (!System.IO.Directory.Exists(root))
    {
        throw new ArgumentException();
    }
    dirs.Push(root);
    while (dirs.Count > 0)
    {
        string currentDir = dirs.Pop();
        string[] subDirs;
        try
        {
            subDirs = System.IO.Directory.GetDirectories(currentDir);
        }
        catch (UnauthorizedAccessException e)
        {
            Console.WriteLine(e.Message);
            continue;
        }
        catch (System.IO.DirectoryNotFoundException e)
        {
            Console.WriteLine(e.Message);
            continue;
        }
        if (Directory.GetFiles(currentDir).Length == 0)
        {
            emptyDirStack.Push(currentDir);
            emptyDirs.Add(currentDir, subDirs.Length); // add directory path and number of sub directories
        }
        // Push the subdirectories onto the stack for traversal.
        foreach (string str in subDirs)
            dirs.Push(str);
    }
    while (emptyDirStack.Count > 0)
    {   
        string currentDir = emptyDirStack.Pop();
        if (emptyDirs[currentDir] == 0)
        {
            string parentDir = Directory.GetParent(currentDir).FullName;
            Console.WriteLine(currentDir); // comment this line
            //Directory.Delete(currentDir); // uncomment this line to delete
            if (emptyDirs.ContainsKey(parentDir))
            {
                emptyDirs[parentDir]--; // decrement number of subdirectories of parent
            }
            removed = true;
        }
    }
    return removed;
}

几个注意事项：

  1. 在没有递归的情况下爬行一棵树并不太困难，我在上面链接的MSDN文章中已经完成了这项工作。但这个特殊的例子比他们的要复杂一点
  2. 我将在emptyDirs字典中存储每个不包含文件的目录，以及它包含的子目录数
  3. 由于删除目录的顺序至关重要，我不得不以相反的顺序运行emptyDirs字典（我使用Linq来完成这一操作）

我想还有更有效的方法，但这还不错，而且在我的测试中似乎有效。

更新：我去掉了颠倒的字典，改用第二本。不过，我仍然使用字典进行快速查找。

sans递归版本要困难得多，效率也不高，所以我建议保留递归。此外，这里有一个稍微干净一点的版本：

static bool DeleteDirectoriesRecursive(DirectoryInfo d)
{
    bool remove = true;
    foreach (DirectoryInfo c in d.GetDirectories())
    {
        remove &= DeleteDirectoriesRecursive(c);
    }
    if (remove && d.GetFiles().Length == 0) {
        d.Delete();
        return true;
    }
    return false;
}
相关文章：