消除递归删除空目录算法

Question

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

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

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

我试图消除这种算法递归，与其说是“固定”的算法（即， the similar question不使用remove变量，但我想保留它）。

我已经开始了一个新的功能，采用Stack<>类，但我想不出一个好办法，回到基本路径，并采取了子目录已经确定的行动。我想解开非尾递归需要多一点努力。

Answer 1

因为加布使用递归的时候我的灵感，使这项工作没有它提到一个StackOverflowException的可能性。我用代码here作为起点。这里就是我想出了...

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来完成此操作）。

我想有更有效的方法，但这并不算太坏，它似乎在我的测试工作。

更新： 我摆脱了颠倒的字典，赞成第二堆栈。不过，我仍然使用字典进行快速查找。

Answer 2

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