消除遞歸刪除空目錄算法

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