递归应用“yield return” - 遍历树数据结构

• 下载源代码 - 15.2 KB

引言

“树形数据结构”被广泛使用（例如：XML、目录系统、Forms.ControlCollection）。它们功能强大，但有点不方便。

• 你无法使用 foreach 枚举它们。对于你想在每个树形叶子上执行的每个操作，你都必须实现一个专门的递归方法。
• 在达到自然结束之前提前退出递归执行并非易事。
• 传递一些参数（例如递归搜索的搜索模式）会使函数堆栈溢出。

如果能使用简单的 foreach 进行树形叶子的“深度迭代”该有多好！

• 不再需要递归函数
• 使用 "break" 退出“递归”
• 叶子节点接收搜索模式，反之亦然：将搜索模式注入到递归调用中。

我们可以做到这一点，而且并不复杂。

public static class Recurser<TItem, TCollection> 
       where TCollection : IEnumerable {

  private static MethodInfo _GetChilds;
  
  // ...
  
  public static IEnumerable<TItem> TopDown(TCollection Coll) {
     foreach (TItem Itm in Coll) {
        yield return Itm;
        TCollection Coll2 = (TCollection)_GetChilds.Invoke(Itm, null);
        foreach (TItem Itm2 in TopDown(Coll2)) { yield return Itm2; }
     }
  }
}

为什么这个函数叫做“TopDown”？哈哈，因为我也做了一个“BottomUp”；)

public static IEnumerable<TItem> BottomUp(TCollection Coll) {
 foreach (TItem Itm in Coll) {
    TCollection Coll2 = (TCollection)_GetChilds.Invoke(Itm, null);
    foreach (TItem Itm2 in BottomUp(Coll2)) { yield return Itm2; }
    yield return Itm;
 }
}

“TopDown”首先产生根项目，然后是……（我认为不需要更多解释）。

那么，唯一的问题应该是：“如何获取 _GetChilds？”我使用反射“调查”类型“TItem”和“TCollection”来获取它。这种“调查”是非常慢的操作——为此，我只对 Recurser 的“泛型形状”执行一次。具体来说，是在静态构造函数中。

static Recurser() {
    // since Reflection is very slow, this static constructor will be
    // executed only once per generic shaping
    Type tpItm = typeof(TItem);
    Type tpColl = typeof(TCollection);
    const BindingFlags BindFlags = BindingFlags.Public | BindingFlags.Instance;
    foreach (MemberInfo mi in tpItm.GetMembers(BindFlags)) {
        MethodInfo Proposed = null;
        switch (mi.MemberType) {
           case MemberTypes.Property:
              PropertyInfo p = (PropertyInfo)mi;
              if (p.PropertyType == tpColl) {
                 Proposed = p.GetGetMethod();
                 break;
              }
              continue;
           case MemberTypes.Method:
              MethodInfo m = (MethodInfo)mi;
              if (m.ReturnType == tpColl) {
                 Proposed = m;
                 break;
              }
              continue;
           default:
              continue;
        }
        if (Proposed.GetParameters().Length == 0) {
           _GetChilds = Proposed;
           return;
        }
    }
    throw new ArgumentException(string.Concat("can't find a " + 
       "recursive member in ", tpItm.Name, "!"));
}

Using the Code

这里，我们有三次“深度迭代”：迭代 TreeNode、DirectoryInfo 和 Form 上的 Control。

using System;
using System.Drawing;
using System.Windows.Forms;
using System.Collections.Generic;
// To declare a generic shape of Recurser causes a quite long codeline.
// For that I prefer to pull it together in an using-statement
using Allnodes = Globals.Recurser<System.Windows.Forms.TreeNode,
   System.Windows.Forms.TreeNodeCollection>;
using AllDirs = Globals.Recurser<System.IO.DirectoryInfo,
   System.IO.DirectoryInfo[]>;
using AllControls = Globals.Recurser<System.Windows.Forms.Control,
   System.Windows.Forms.Control.ControlCollection>; 

namespace TreeIterations {
   public partial class frmMain : Form {

      public frmMain() {
         InitializeComponent();
         this.treeView1.ExpandAll();
      }

      private void btTest_Click(object sender, EventArgs e) {
         textBox1.Clear();
         WriteLine("Enumerating Treenodes from bottom upwards");
         foreach (TreeNode Nd in Allnodes.BottomUp(treeView1.Nodes)) {
            WriteLine("Depth: ", Allnodes.Depth, ", Name: ", Nd.ToString());
         }
         WriteLine();
         WriteLine("Enumerating Directories TopDown");
         System.IO.DirectoryInfo Root = new System.IO.DirectoryInfo(@"..\..\");
         foreach (System.IO.DirectoryInfo DI in AllDirs.TopDown(Root)) {
            WriteLine("Depth: ", AllDirs.Depth, ", FullName: ", DI.FullName);
         }
         WriteLine();
         WriteLine("Enumerating Controls TopDown");
         // call Recurser without using the useful "using AllControls" - Statement
         foreach (Control Ctl in Globals.Recurser
               <Control, Control.ControlCollection>.TopDown(this)) {
            // display tree indented
            WriteLine(
               new String(' ', AllControls.Depth * 2), 
               Ctl.GetType().Name, @" """, Ctl.Name, @"""");
         }
      }

      private void WriteLine(params object[] Segments) {
         textBox1.AppendText(string.Concat(Segments));
         textBox1.AppendText(Environment.NewLine);
      }
   }
}

也许你已经注意到：我的一个秘密在于，有用的东西“Depth”是如何实现的。你可以在附带的下载中找到答案；)

关注点

“TopDown()”和“BottomUp()”方法的数据类型是“IEnumerable<TItem>”。因此，在 C# 3.0 中，它们将支持类型推断，以及出色的 LINQ 功能。

我不太确定应该分配什么“技能等级”。对于初学者来说，这是一种以简单的 foreach 方式进行递归的有用方法。该功能更适合“中级”或“高级”水平，因为“yield return”、静态构造函数、使用 using 语句重新定义类、反射——这些特性在我看来并非纯粹的初学者内容。