C#: How to make this method non-recursive

I have this recursive method which deletes empty folders:

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

  开发者_如何学JAVA      if (directory.GetFileSystemInfos().Length == 0)
        {
            try
            {
                directory.Delete();
            }
            catch (Exception)
            {
                // Already gone, no permission, not empty, et cetera
            }
        }
    }

How can I refactor this method so that it is not recursive?

The standard refactoring is to store the data you would otherwise be passing to the function in a LIFO (i.e. a stack) or FIFO queue. Note that this doesn't change asymptotic space usage; you're using your own data structure rather than the call stack.

If you can define a "next sibling" function, you can visit the nodes with constant additional space. This is because the graph of directories (sans files) is essentially undirected due to parent pointers. Pseudocode:

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

Note that you're not actually using O(1) space total, since the directory structure is itself O(n). Methods like DirectoryInfo.GetDirectories can remove the need for loops in nextBranchingSibling.

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

Try this:

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

Another performance step could be: if you tried to remove a directory and it contains files, all parent levels should be skipped since they WILL fail too.

You could use a local Stack and loop while the stack is not empty.

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

I had the same problem and I created a nice (imho) solution: beggining in a root directory, I "recursively" get the children directories and I store them in an ArrayList object. In this way, I create a list contaning first the higher level dirs, and at the end the deeper nested directories. This array is ideally divided in sub-arrays using the indexes stored in the levels ArrayList object. Doing this, I can first check the deeper directories and delete them if they're empty, and then go back to the root level by level.

For example:

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

Create a queue that has all the directories in the starting directory, then while it's not empty, take the next item, check if the directory's empty, if it is delete it, if not add all the subdirectories to the queue.

I don't know C#, but if there isn't a standard queue type, a linked list or mutable array type thing would work just as well.

Pseudocode;

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