引言

我们将基于[1]和[2]，研究高级 WPF 树视图的实现。本文主要讨论访问树视图中的节点，这是执行加载、保存和过滤树视图节点等操作所必需的。我们将通过一个实际应用来探索这个问题，该应用用于搜索和过滤大型 WPF 树视图的内容。

背景

《高级 WPF 树视图》系列的前两部分[1][2]引发了关于在 WPF 树视图上执行加载、保存[7]或过滤节点等操作的问题。这些操作确实不简单，因为它们要求我们在不迷失方向的情况下导航复杂的结构。因此，本文试图回答这个问题：

• “如何在 WPF 树视图上执行（加载、保存、搜索等）操作？”

我们通过回顾导航树结构（树遍历）的通用算法，并将其应用于实际实现来做到这一点。

算法与结构的研究让我们有机会建立在已知超过 100 年的数学事实之上（而不是重新发明轮子）。这项研究的优点还在于，我们可以将所学到的知识应用于 .Net 之外的更多编程语言中。本文包含了一个关于下面讨论的算法的 Java 演示版本下载 Java_TreeTraversal.zip，以说明该论点的强大之处。

本文末尾的 .Net/WPF 实际应用是一种将大约 100.000 条记录加载到树视图中并能够快速搜索和过滤该树视图的方法。
 

目录 树遍历 广度优先 层级遍历 深度优先 前序遍历 中序遍历 后序遍历 使用 IEnumerable/yield 枚举树节点 通用方法 IEnumerable/Yield 方法 高效过滤和搜索大型 WPF 树视图 层级遍历转换器 后序匹配 追求性能 FilterTreeViewVis 应用程序 FilterTreeView 应用程序 摘要 额外内容 历史 参考文献

树遍历

导航树结构的艺术被称为树遍历[4]。我们关心的是具有任意形状或形式的 WPF 树视图的 ViewModel。也就是说，我们对每个节点可以拥有k个子节点（其中k = 0,1,2,3...）的树结构感兴趣。这种树结构被称为k叉树。k叉树的一个特例是二叉树，其中k=2。二叉树（或 k叉树）的一个特例是单链表，其中k=1。二叉树上的树遍历算法是众所周知且历史悠久的[4]。

二叉树遍历通常分为广度优先或深度优先算法。广度优先算法在访问节点的子节点之前，会先访问其直接邻居；而深度优先算法在访问邻居节点之前，会先访问节点的子节点。

接下来，我们评估二叉树遍历算法，并确定它们是否也可以用于导航 k > 2 的 k 叉树。

广度优先

层级遍历

• 下载 TreeLib.zip

层级遍历算法 [4] 是一种广度优先搜索算法，因为它在导航到子节点之前会访问每个相邻节点。下面的图形动画通过导航一个带有一个根元素和总共 12 个节点的树来展示这种方法。

带有红色边框表示当前正在访问的节点。所有其他节点都已访问过。动画显示了我们如何通过自上而下访问每个节点，来全面了解树，或每个父节点与其子节点之间的关系。

下面的 C# 代码实现了上面动画中描述的 Level-Order 遍历算法的要求。您可以通过下载下载 TreeLib.zip 演示并查看 TreeLibDemo/Development/LevelOrderV1.cs 代码来测试此算法。

public static void LevelOrderTraversal(Node root)
{
  Queue<Tuple<int, Node>> queue = new Queue<Tuple<int, Node>>();

  if (root != null)
    queue.Enqueue(new Tuple<int, Node>(0, root));

  while (queue.Count() > 0)
  {
    var queueItem = queue.Dequeue();
    int iLevel = queueItem.Item1;
    Node current = queueItem.Item2;

    Console.WriteLine(string.Format("{0,4} - {1}"
        , iLevel, current.GetPath()));                // Process the node

    foreach (var item in current.Children)
        queue.Enqueue(new Tuple<int, Node>(iLevel + 1, item));
  }
}

Public Shared Sub LevelOrderTraversal(root As Node)
  Dim queue As New Queue(Of Tuple(Of Integer, Node))()
  
  If root IsNot Nothing Then
    queue.Enqueue(New Tuple(Of Integer, Node)(0, root))
  End If
  
  While queue.Count() > 0
  	Dim queueItem = queue.Dequeue()
  	Dim iLevel As Integer = queueItem.Item1
  	Dim current As Node = queueItem.Item2
  
  	Console.WriteLine(String.Format("{0,4} - {1}", iLevel, current.GetPath()))
  
  	For Each item As var In current.Children
  	  queue.Enqueue(New Tuple(Of Integer, Node)(iLevel + 1, item))
  	Next
  End While
End Sub

public static void LevelOrderTraversal(Node root)
{
  Queue<Tuple<Integer, Node>> queue = new LinkedList<Tuple<Integer, Node>>();

  if (root != null)
    queue.add(new Tuple<Integer, Node>(0, root));

  while (queue.size() > 0)
  {
    Tuple<Integer, Node> queueItem = queue.remove();
    int iLevel = queueItem.Item1;
    Node current = queueItem.Item2;

    System.out.print(String.format("%04d - %2$s\n", iLevel, current.GetPath()));

    for (Node item : current.Children)
        queue.add(new Tuple<Integer, Node>(iLevel + 1, item));
  }
}

能够将 Level-Order 遍历策略应用于任何树结构是一种极其有用的工具。因为您可以用它来

• 构建一个结构（因为算法是从根到叶导航），它也可以用于
• 将一种树结构转换为另一种树结构（如下面所示）。

深度优先

深度优先算法可以通过它们访问当前节点以及其左子节点或右子节点（例如，先访问右子节点再访问左子节点，或者先访问左子节点再访问右子节点）的实际顺序进一步分类。

这里众所周知的算法是前序遍历、中序遍历和后序遍历。

前序遍历

前序遍历算法[4]按以下顺序访问：

• 当前节点，然后是
• 左子节点，然后是
• 右子节点。

k叉树没有左右子节点的明确定义。尽管如此，如果我们将以下定义应用于 k叉树，我们仍然可以对其进行前序遍历：

• 第一个子节点（索引：0）是最左边的子节点，并且
• 最后一个子节点（索引：k-1）是最右边的子节点。

此定义使我们能够在能够遍历其集合时从左到右遍历子项。

for(int i=0: i<Children.Count(); i++)
{
  visitNode(Children[i])
}

上面关于最左和最右子节点的定义对于理解下面显示的算法和动画非常重要。

下面的 C# 代码实现了前序遍历算法的要求。您可以通过下载下载 TreeLib.zip 演示并查看 TreeLibDemo/Development/PreOrderV1.cs 代码来测试此算法。

public static void PreOrder(Node root)
{
  var stack = new Stack<Node>();
  stack.Push(root);

  while (stack.Count > 0)
  {
    var current = stack.Pop();

    System.Console.WriteLine(current.GetPath()); // Process the node

    for (int i = current.Children.Count - 1; i >= 0; i--)
    {
      stack.Push(current.Children[i]);
    }
  }
}

Public Shared Sub Traverse(root As Node)
  Dim stack = New Stack(Of Node)()
  stack.Push(root)

  While stack.Count > 0
    Dim current = stack.Pop()
    
    System.Console.WriteLine(current.GetPath())
    ' Process the node
    For i As Integer = current.Children.Count - 1 To 0 Step -1
      stack.Push(current.Children(i))
    Next
  End While
End Sub

public static void PreOrder(Node root)
{
  Stack<Node> stack = new Stack<Node>();
  stack.push(root);

  while (stack.empty() == false)
  {
    Node current = stack.pop();

    System.out.print(current.GetPath() + "\n");     // Process the node

    for (int i = current.Children.size() - 1; i >= 0; i--)
    {
        stack.push(current.Children.get(i));
    }
  }
}

前序遍历算法可以有与层级遍历方法类似的应用，因为它也从根到叶遍历树，但对子节点的偏好不同。因此，如果访问子节点优于访问相邻节点，则此算法可以被视为层级遍历算法的替代方案。

中序遍历

中序遍历算法[4]按以下顺序访问：

• 左子节点，然后是
• 当前节点，然后是
• 右子节点。

如果我们假设层级遍历部分中对左子节点和右子节点的定义，那么将中序遍历算法应用于 k 叉树是困难的。中序遍历可以为 k 叉树实现，但它非常复杂，我们目前看不到这样做的动机。因此，我们参考这个定义，并请求反馈，如果有人知道 k 叉树中序遍历的用例和实现。

后序遍历

后序遍历算法[4]按以下顺序访问：

• 左子节点，然后是
• 右子节点，然后是
• 当前节点。

我们可以像在前序遍历算法中一样，使用类似的定义来建立左子节点和右子节点。然而，这次我们必须反转 for 循环，以正确的顺序遍历树结构。

for(int i=Children.Count(); i>=0 0; i--)
{
  visitNode(Children[i])
}

左子节点和右子节点的反向定义对于理解下面显示的算法细节很重要。

下面的 C# 代码实现了后序遍历算法的要求。您可以通过下载下载 TreeLib.zip 演示并查看 TreeLibDemo/Development/PostOrderV1.cs 代码来测试此算法。

public static void nonRecursivePostOrder(Node root)
{
  var toVisit = new Stack<Node>();
  var visitedAncestors = new Stack<Node>();

  toVisit.Push(root);
  while (toVisit.Count > 0)
  {
    var node = toVisit.Peek();
    if (node.Children.Count > 0)
    {
      if (PeekOrDefault(visitedAncestors) != node)
      {
        visitedAncestors.Push(node);
        PushReverse(toVisit, node.Children);
        continue;
      }

      visitedAncestors.Pop();
    }

    Console.WriteLine(node.GetPath()); // Process the node
    toVisit.Pop();
  }
}

private static Node PeekOrDefault(Stack<Node> s)
{
  return s.Count == 0 ? null : s.Peek();
}

private static void PushReverse(Stack<Node> s, List<Node> list)
{
  foreach (var l in list.ToArray().Reverse())
  {
    s.Push(l);
  }
}

Public Shared Sub nonRecursivePostOrder(root As Node)
  Dim toVisit = New Stack(Of Node)()
  Dim visitedAncestors = New Stack(Of Node)()
  
  toVisit.Push(root)
  While toVisit.Count > 0
    Dim node = toVisit.Peek()
    If node.Children.Count > 0 Then
      If PeekOrDefault(visitedAncestors) <> node Then
        visitedAncestors.Push(node)
        PushReverse(toVisit, node.Children)
        Continue While
      End If
      
      visitedAncestors.Pop()
    End If
    
    System.Console.WriteLine(node.GetPath()) ' Process the node
    toVisit.Pop()
  End While
End Sub

Private Shared Function PeekOrDefault(s As Stack(Of Node)) As Node
  Return If(s.Count = 0, Nothing, s.Peek())
End Function

Private Shared Sub PushReverse(s As Stack(Of Node), list As List(Of Node))
  For Each l As var In list.ToArray().Reverse()
    s.Push(l)
  Next
End Sub

public static void nonRecursivePostOrder(Node root)
{
  Stack<Node> toVisit = new Stack<Node>();
  Stack<Node> visitedAncestors = new Stack<Node>();

  toVisit.push(root);
  while (toVisit.empty() == false)
  {
    Node node = toVisit.peek();
    if (node.Children.size() > 0)
    {
      if (PeekOrDefault(visitedAncestors) != node)
      {
        visitedAncestors.push(node);
        PushReverse(toVisit, node.Children);
        continue;
      }

      visitedAncestors.pop();
    }

    System.out.print(node.GetPath() + "\n");     // Process the node
    toVisit.pop();
  }
}

private static Node PeekOrDefault(Stack<Node> s)
{
  if (s.empty() == true)
    return null;

  return s.peek();
}

private static void PushReverse(Stack<Node> s, List<Node> list)
{
  Collections.reverse(list);
	
  for (Node l : list)
  {
    s.push(l);
  }
}

后序遍历算法首先访问其最深的节点，然后沿树结构向上遍历，直到访问根节点。这似乎具有如此抽象和奇怪的性质，以至于很难判断它是否有用。但事实证明，如果我们需要一种算法，能够以离线模式执行操作，且对 UI 线程的可见更改最少，那么后序遍历对于 WPF 尤其有用。

后序遍历对于 WPF 树视图很重要，因为它使我们能够实现一种算法，该算法能够：

• 删除所有根节点（使其不可见），
• 从下到上评估树，以及
• 在每个根项上决定是否应该添加（使其可见）已评估的子树。

上述算法对于 WPF 来说可能是有益的，因为只有第一步和最后一步需要 UI 更新。所有其他操作，可能需要编辑树视图项，都可以在离线模式下执行，这意味着它们不需要 UI 更新。我们将在下面的追求性能部分更详细地回顾这个想法。

使用 IEnumerable/Yield 枚举树节点

通用方法

值得注意的是，在前面章节的遍历算法代码片段中，`Console.WriteLine` 语句可以代表在树结构项上执行的任何操作（在这种情况下，“操作”意味着显示树节点的内容），而所有其他代码都用于导航树。

因此，重用上述遍历算法的一种“显而易见的方式”是传入一个泛型函数，并将每个算法中的 `Console.WriteLine` 语句替换为对该泛型函数的调用（当前节点作为参数）。下载 TreeLib.zip 中的 `TreeLibNuget` 应用程序通过文件系统目录上的遍历方法演示了这一思想（参见选项 4 和 5），以计算文件夹的存储空间。层级遍历的泛型代码如下所示：

public TRESULT Traverse(T root
                       , Func<T, IEnumerable<T>> children
                       , TRESULT ret
                       , Func<TRESULT, T, TRESULT> process
                       , Action<T> progress = null
                       , Func<TRESULT, Exception, T, TRESULT> exception = null
    )
{
    Queue<Tuple<int, T>> queue = new Queue<Tuple<int, T>>();

    if (root != null)
        queue.Enqueue(new Tuple<int, T>(0, root));

    while (queue.Count() > 0)
    {
        var queueItem = queue.Dequeue();
        int iLevel = queueItem.Item1;
        T current = queueItem.Item2;

        if (progress != null)
          progress(current);    // print a simple progress indicator

        ret = process(ret, current);           // Process the node

        try
        {
            foreach (var item in children(current))
                queue.Enqueue(new Tuple<int, T>(iLevel + 1, item));
        }
        catch (Exception e)
        {
            if (exception != null)
                ret = exception(ret, e, current);
        }
    }

    return ret;
}

...更酷的是，您可以调整 DirectorySize.cs 中第 75 行附近的代码，以实现任何其他遍历算法，并且仍然得到相同的结果，例如：

var res = new DirSizeResult(); // Initialize result object

// You can use LevelOrder<T>, PostOrder<T>, and PreOrder<T> here
var Order = new PostOrder<DirSizeResult, DirectoryInfo>();

res = Order.Traverse(new DirectoryInfo(path)
                      , i => i.GetDirectories()
                      , res
                      , ComputeDirSize
                      
                      , i => Console.Write(".")   // print a simple progress indicator
                      
                      , (i, exc, j) =>            // print a simple child exception indicator
                      { Console.Write("D"); return i; }
);

每种遍历方法的结果总是相同的，因为访问的节点是相同的。每种算法之间不同的是节点被访问的顺序。遍历本地文件系统可能以任何顺序都是高效的。但是，当处理特殊的检索系统（例如数据库服务器）及其大型数据集时，顺序可能会在有用与否之间产生生与死的差异。

可枚举/Yield 方法

上一节中的通用方法只是重用树导航算法的一种方式。通过实现IEnumerable/yield也可以达到同样的结果，我们将在本节中讨论。

让我们考虑下面的代码片段，以理解为什么IEnumerable/yield在树遍历的上下文中可能是有利的。

items = TreeLib.Depthfirst.Traverse.PostOrder(root, i => i.Children);

foreach (var item in items)
{
  Console.WriteLine(item.GetPath());
}

items = TreeLib.Depthfirst.Traverse.PostOrder(root, Function(i) i.Children)
For Each item In items
  Console.WriteLine(item.GetPath())
Next

上述代码片段初始化了一个泛型遍历算法：

• 给定一个 `root` 树节点，以及
• 一个用于查找每个节点的子节点的方法（`i => i.Children`）。

然后，此信息可以在 `foreach` 循环中应用，以请求的顺序遍历树节点。并且从后序遍历更改为前序遍历，或更改为层级遍历，只需要更改上面代码片段的第一行。

该思想的实现可在 TreeLib .Net Standard 库中找到（此处已附上，也可在 GitHub 和 Nuget 上获取），该库可应用于许多不同的 .Net 环境。此贡献进一步优化了遍历，因为每个节点遍历仅在 `foreach-client-loop` 请求下一个元素时才进行评估，这也被称为惰性或延迟加载。

关于 IEnumerable/yield 开发的详细解释超出了本文的范围。请阅读 Mike Adelson 的博客 [5]，以更好地理解如何从迭代树遍历方法开发惰性 IEnumerable/yield 方法。

我们可以使用惰性 IEnumerable/yield 算法高效地遍历内存中的结构。然而，当处理异常时，这个应用有其自身的局限性，正如我们在尝试时所看到的：

• 选项 4) 计算目录大小（枚举中没有异常处理）
  在 TreeLibNugetDemo 应用程序中。

对于包含我们无权访问的子文件夹的文件夹。

重要的是要注意，DirSizeWoException.cs 中的 IEnumerable/yield 算法在遇到异常（例如，**无法访问的文件夹**）时会停止。并且抛出的异常不是在 foreach 循环中抛出的，而是在

var levorderItems = TreeLib.BreadthFirst.Traverse.LevelOrder(dirRoot, i => i.GetDirectories()); 

语句。这意味着我们必须确保 `i.GetDirectories()` 语句只生成（发出）可以处理而不会出现异常的项（例如：在生成之前检查访问权限），或者我们也可以使用上面描述的通用版本来获得更健壮的实现。无论哪种方式，两种实现似乎都有各自的权利，但它们的应用程序肯定不限于我们在 WPF 树视图中可以显示的内容。

高效过滤和搜索大型 WPF 树视图

前面的章节让我们深入了解了通过以定义的顺序访问（遍历）每个节点来处理节点（或树视图项）。我们已经看到了演示代码以及遍历文件系统中文件夹结构的方法。文章的其余部分将结合 WPF 树视图的知识，磨砺我们处理树结构数据集的工具。为此，我们将回顾本文附带的 FilterTreeView 项目。

此应用程序搜索 2012 年全球数据库 [6] 中 3 个级别（国家、地区、城市）结构中相似的字符串。但所实现的算法足够通用，也应适用于任何其他树结构。此解决方案包含以下项目：

• 组件（解决方案文件夹）
  • BusinessLib
  • FilterTreeViewLib
• FilterTreeView
• FilterTreeViewVis

BusinessLib 包含数据模型层，类似于 Josh Smith 的文章[3]，只是这次处理 101.908 个城市、4148 个地区和 246 个国家[6]。FilterTreeViewLib 包含在两个演示应用程序中使用的基类实现。我们回顾 FilterTreeView 和 FilterTreeViewVis 这两个演示应用程序，以更好地理解搜索 WPF 树视图的有效方法。

层级遍历转换器

• 下载 FilterTreeView.zip
• 下载 VB_FilterTreeView_Bonus.zip

WPF 应用程序通常遵循 MVVM 模式，该模式又由视图、视图模型和模型数据层组成。在此上下文中，典型的 WPF 树视图应用程序包括：

• 将项目从模型转换为视图模型（加载数据时），反之亦然，
• 将项目从 ViewModel 转换为 Model（保存数据时）。

本节重点介绍将数据加载到树视图的 ViewModel 时发生的转换。下面的动画展示了这种转换，左侧是模型集合，右侧是 ViewModel 集合。应用程序遍历模型集合中的每个项目，并将每个转换后的 ViewModel 项目添加到 ViewModel 集合中。

此转换的结果应该是一个可以绑定到 WPF 树视图的 ViewModel 项集合。

让我们考虑 MetaLocationViewModel 类中 FilterTreeViewLib 项目的 `GetViewModelFromModel` 方法。此方法有两种实现，每种都可以通过在以下位置设置或取消设置 TREELIB 常量来激活或停用：

• FilterTreeViewLib（项目）> 属性 > 构建 > 条件编译符号

当设置了 **TREELIB** 参数时，将实现以下算法。它将 BusinessLib 中的 MetaLocationModel 项转换为 MetaLocationViewModel 项。此转换发生是因为代码是通过调用 AppViewModel.LoadSampleDataAsync() 和 MetaLocationRootViewModel.LoadData(...) 来调用的。

internal static MetaLocationViewModel GetViewModelFromModel(MetaLocationModel srcRoot)
{
  if (srcRoot == null)
    return null;

  var srcItems = TreeLib.BreadthFirst.Traverse.LevelOrder(srcRoot, i => i.Children);
  var dstIdItems = new Dictionary<int, MetaLocationViewModel>();
  MetaLocationViewModel dstRoot = null;

  foreach (var node in srcItems.Select(i => i.Node))
  {
    if (node.Parent == null)
    {
      dstRoot = new MetaLocationViewModel(node, null);
      dstIdItems.Add(dstRoot.ID, dstRoot);
    }
    else
    {
      MetaLocationViewModel vmParentItem;     // Find parent ViewModel for Model
      dstIdItems.TryGetValue(node.Parent.ID, out vmParentItem);

      var dstNode = new MetaLocationViewModel(node, vmParentItem);
      vmParentItem.ChildrenAdd(dstNode);     // Insert converted ViewModel below ViewModel parent
      dstIdItems.Add(dstNode.ID, dstNode);
    }
  }

  dstIdItems.Clear(); // Destroy temp ID look-up structure

  return dstRoot;
}

Friend Shared Function GetViewModelFromModel(ByRef srcRoot As MetaLocationModel) As MetaLocationViewModel

  If srcRoot Is Nothing Then Return Nothing

  Dim srcItems = TreeLib.BreadthFirst.Traverse.LevelOrder(srcRoot, Function(i) i.Children)

  Dim dstIdItems = New Dictionary(Of Integer, MetaLocationViewModel)()
  Dim dstRoot As MetaLocationViewModel = Nothing

  For Each itemNode In srcItems
    Dim node = itemNode.Node

    If node.Parent Is Nothing Then
      dstRoot = New MetaLocationViewModel(node, Nothing)
      dstIdItems.Add(dstRoot.ID, dstRoot)
    Else
      Dim vmParentItem As MetaLocationViewModel = Nothing

      dstIdItems.TryGetValue(node.Parent.ID, vmParentItem)
      Dim dstNode = New MetaLocationViewModel(node, vmParentItem)

      vmParentItem.ChildrenAdd(dstNode)
      dstIdItems.Add(dstNode.ID, dstNode)
    End If
  Next

  dstIdItems.Clear()
  Return dstRoot
End Function

我们可以看到，源项集合（模型项）以层级遍历（从根到叶）的方式被遍历。

重要的是要知道每个项目都有一个 `ID` 属性，该属性保存一个集合范围内的唯一标识符。此标识符存在于 `ID` 属性中，用于唯一标识每个项目，并且也显示在 `Parent` 属性中，以提示父项目的唯一 `ID`。

上述关于 `ID` 和 `Parent` 属性的观察很重要，因为我们可以为每个项目确定：

• Parent == null
  • 该项目属于项的根集合
• Parent != null
  • 我们之前已经见过父项，因为我们从根到叶遍历。因此，我们可以通过存储在 dstIdItems 字典中的 ID 查找父项。
    dstIdItems.TryGetValue(node.Parent.ID, out vmParentItem);

这种方法确定任何项是根项还是集合中的子项；搜索并找到父项为我们将转换后的项插入到正确位置提供了一种方法。

上面显示的代码简化了遍历任务，因为它利用了 TreeLib 库中的IEnumerable/Yield实现。我们总是可以实现这种层级遍历（只需取消设置**TREELIB**常量）方法，而无需使用 TreeLib 库（这也不是那么糟糕）。

internal static MetaLocationViewModel GetViewModelFromModel(MetaLocationModel srcRoot)
{
  if (srcRoot == null)
      return null;

  MetaLocationViewModel dstRoot = new MetaLocationViewModel(srcRoot, null);

  Queue<MetaLocationModel> srcQueue = new Queue<MetaLocationModel>();
  Queue<MetaLocationViewModel> dstQueue = new Queue<MetaLocationViewModel>();

  srcQueue.Enqueue(srcRoot);
  dstQueue.Enqueue(dstRoot);

  while (srcQueue.Count() > 0)
  {
      MetaLocationModel srcCurrent = srcQueue.Dequeue();
      MetaLocationViewModel dstCurrent = dstQueue.Dequeue();

      foreach (var item in srcCurrent.Children)
      {
          var dstVM = new MetaLocationViewModel(item, dstCurrent);

          dstCurrent.ChildrenAddBackupNodes(dstVM);

          srcQueue.Enqueue(item);
          dstQueue.Enqueue(dstVM);
      }
  }

  return dstRoot;
}

Friend Shared Function GetViewModelFromModel(ByVal srcRoot As MetaLocationModel) As MetaLocationViewModel
    If srcRoot Is Nothing Then Return Nothing

    Dim dstRoot As MetaLocationViewModel = New MetaLocationViewModel(srcRoot, Nothing)
    Dim srcQueue As Queue(Of MetaLocationModel) = New Queue(Of MetaLocationModel)()
    Dim dstQueue As Queue(Of MetaLocationViewModel) = New Queue(Of MetaLocationViewModel)()

    srcQueue.Enqueue(srcRoot)
    dstQueue.Enqueue(dstRoot)

    While srcQueue.Count() > 0
        Dim srcCurrent As MetaLocationModel = srcQueue.Dequeue()
        Dim dstCurrent As MetaLocationViewModel = dstQueue.Dequeue()

        For Each item In srcCurrent.Children
            Dim dstVM = New MetaLocationViewModel(item, dstCurrent)

            dstCurrent.ChildrenAddBackupNodes(dstVM)

            srcQueue.Enqueue(item)
            dstQueue.Enqueue(dstVM)
        Next
    End While

    Return dstRoot
End Function

...但是你不同意通过 IEnumerable/Yield 隐藏遍历细节能给我们带来更好、更简化的代码，就像我们在上面展示的第一个遍历方法版本中看到的那样吗？

无论您选择哪个版本，您现在都应该能够将您的数据集合从内存中的集合（ViewModel 项）传输到模型项集合中。而且您的模型集合最好设计成支持持久化存储。

上述用于加载数据的层级遍历算法也适用于保存数据，因为我们可以交换源和目标类型，从

• ViewModel 到 Model，并存储，而不是：
• 从模型加载并转换为视图模型。

后序匹配

• 下载 FilterTreeView.zip

我们目前评估的遍历算法之所以适用，是因为我们能够通过从根到叶访问节点来解决问题。如果我们需要遍历树，用某个函数评估每个节点，并对子树进行相同的评估，以决定是否显示一个节点，或者一个节点所在的子树，那么遍历问题可能会稍微困难一些。

上述要求可以通过从下到上遍历树来高效解决。下面的动画展示了算法如何评估树中的每个项目并确定它是匹配（**绿色节点**）还是不匹配（**红色节点**）。

• 不匹配的节点或仅包含不匹配节点的子树必须不可见。
• 匹配的节点或包含匹配模式的子树（黄色节点）必须可见。

此想法通过下面的动画进行了可视化，其中帧号 12 包含假定的后序匹配算法的结果。

可视化算法的实现可在两个示例应用程序中找到：

• FilterTreeViewVis（请参阅 TestLocationRootViewModel 中的 DoSearch() 方法），以及
• FilterTreeView（请参阅 MetaLocationRootViewModel 中的 DoSearch() 方法）

这两个搜索方法都是非泛型的，因为在开发时似乎更容易，但现在应该清楚，我们也可以通过 TreeLib 库使用前面讨论的泛型或IEnumerable/Yield方法来实现它们。

下面将详细介绍这两种算法，以解释它们的工作原理以及其中一种为何优于另一种。

追求性能

• 下载 FilterTreeView.zip
• 下载 VB_FilterTreeView_Bonus.zip

本节讨论使用上一节中讨论的后序匹配算法搜索 WPF 树视图的性能细节。过滤树视图的节点对于提供支持全面 UX 架构的高质量软件可能是有益的。然而，要实现这样的壮举，个人必须重新评估他基于多个标准的方法——而性能在此过程中扮演着重要的角色。

在本节中，我们将介绍不同方法的特性，并讨论为什么一种方法似乎比另一种方法更有效。

FilterTreeViewVis 应用程序

FilterTreeViewVis 应用程序通过 TestLocationRootViewModel 类中的 DoSearch() 方法实现其搜索功能。该方法中的第一个 foreach 循环在搜索字符串为空或只包含 1 个字母时使所有项目可见。

if (searchParams.IsSearchStringEmpty == true ||
    searchParams.MinimalSearchStringLength >= searchParams.SearchString.Length)
{
  foreach (var rootItem in CountryRootItems)
  {
    if (token.IsCancellationRequested == true)
        return 0;

    rootItem.IsItemVisible = true;

    rootItem.SetExpand(false);
  }

  return 0;
}

实际的搜索算法实现在上述代码块下方。

int imatchCount = 0;

// Go through all root items and process their children
foreach (var rootItem in CountryRootItems)
{
  if (token.IsCancellationRequested == true)
      return 0;

  rootItem.Match = MatchType.NoMatch;

  // Match children of this root item
  var nodeMatchCount = MatchNodes(rootItem, searchParams);

  imatchCount += nodeMatchCount;

  // Match this root item and find correct match type between
  // parent and children below
  if (searchParams.MatchSearchString(rootItem.LocalName) == true)
  {
    rootItem.Match = MatchType.NodeMatch;
    imatchCount++;
  }

  if (nodeMatchCount > 0)
  {
    if (rootItem.Match == MatchType.NodeMatch)
      rootItem.Match = MatchType.Node_AND_SubNodeMatch;
    else
      rootItem.Match = MatchType.SubNodeMatch;
  }

  // Determine wether root item should visible and expanded or not
  if (rootItem.Match != MatchType.NoMatch)
  {
    if ((rootItem.Match & MatchType.SubNodeMatch) != 0)
        rootItem.SetExpand(true);
    else
        rootItem.SetExpand(false);

    rootItem.IsItemVisible = true;
  }
  else
      rootItem.IsItemVisible = false;
}

return imatchCount;

这段代码看起来有点复杂，但这里真正重要的项是 **MatchNode 方法**，它在每个根节点上执行实际的后序匹配遍历，并返回 `MatchType` 枚举的值，以指示根节点是否应该可见。

// FilterTreeViewLib.ViewModelsSearch.SearchModels.Enums    
public enum MatchType
{
  NoMatch = 0,               // Red nodes in Post-Order Match animation
  NodeMatch = 1,             // Green nodes in Post-Order Match animation
  SubNodeMatch = 2,          // Yellow nodes in Post-Order Match animation
  Node_AND_SubNodeMatch = 4  // Not shown in animation
}

此方法通过切换每个 ViewModel 项中的 `Visibility` 属性来实现广泛使用的搜索和过滤 [3]，这反过来又调整了绑定视图项的可见性。

请将 _**FilterTreeViewVis**_ 项目设置为启动项目，并通过在 `MainWindow.xaml` 文件中注释/取消注释以下几行来测试其带虚拟化和不带虚拟化的搜索功能（参见 第 2 部分），以跟随下面的讨论：

VirtualizingStackPanel.IsVirtualizing="True"
    VirtualizingStackPanel.VirtualizationMode="Recycling"
    Style="{StaticResource TreeViewStyle}"

不带虚拟化的 FilterTreeView 可见性属性

在 WPF 中，隐藏或显示项的任务通常通过 ViewModel 中 `Visibility` 属性的切换以及绑定的 View 来解决。因此，它无疑是过滤 WPF TreeView 控件中托管的数据集 [3] 的最常见方式。事实上，我们自己也决定采用 `Visibility` 方法，认为它将提供一种相关的过滤 TreeView 节点的方式。

但这种方法只在少数典型情况下足够快，即树视图在任何节点下都不包含超过 500 个项；然而，当我们决定进行压力测试时，我们注意到在节点下大约 1000 个子节点（或更多）时，性能急剧下降。

这种效率低下导致 UI 冻结和交互极其缓慢，尽管我们使用了优化的遍历算法（？）。让我们考虑其他选项，看看为什么这种方法似乎无法很好地扩展。

带虚拟化的 FilterTreeView 可见性属性

虚拟化[2]的应用似乎是一个公平的解决方案——加载和过滤似乎比以前更高效。但是，一旦我们尝试增加要过滤的项的数量，这种方法也失败了。我们明显注意到，当您上下滚动 TreeView 时，伴随着混乱的缓慢行为。

滚动条的滑块不断以不稳定的方式调整大小，因为它无法计算 TreeView 中元素的真实数量。这种混乱的发生是因为存在几个不可见的项，当它们位于滚动查看器的可见部分下方时，它们被视为已渲染的元素。

事实证明，如果给定节点下的子项数量远超 500 个，那么实现 `Visibility` 方法是不可行的。因此，我们将在下一节中寻找其他替代方案。

FilterTreeView 应用程序

不带虚拟化的 FilterTreeView BackNodes 过滤器

FilterTreeView 项目的 MetaLocationRootViewModel 类中的 DoSearch() 方法提供了一种替代前面讨论的 `Visibility` 方法的解决方案。使用的遍历算法相同，并且 MetaLocationRootViewModel.MatchNodesAsync() 方法中的匹配函数也实现了 `MatchType` 枚举，以建模后序匹配动画中可视化的匹配类型。这里唯一真正不同的是，我们不实现 `Visibility` 属性来隐藏或显示项目。相反，我们将所有项目存储在一个冗余的 **BackUpNodes** 集合中；并且当筛选参数需要时，在 `Observable` 集合中添加或删除项目。

为了做到这一点，我们决定创建一个额外的集合，该集合充当只读的节点保留集：

• MetaLocationRootViewModel 中的 `_BackUpCountryRoots`，以及
• MetaLocationViewModel 中的 `_BackUpNodes`

这些集合不绑定到 TreeView；我们只用它们来提取在过滤过程中寻找的符合条件的项。因此，BackUpNodes 集合可以被视为从后端系统（例如：数据库服务器）检索项的等效方式，而不是假设我们总是将所有项都存储在内存中。

如果我们不使用虚拟化来测试 FiltertreeView 应用程序，我们可以看到可接受的性能和流畅的 UI。但是，如果我们也使用虚拟化来测试它会怎样？

带虚拟化的 FilterTreeView BackNodes 过滤器

即使我们尝试过滤许多项目（尝试在选中“字符串包含”的情况下过滤“los”），虚拟化的 FilterTreeView 实现也表现流畅。滚动条不再出现不正常的行为，就像我们在 `Visibility` 属性方法的虚拟化变体中看到的那样。总而言之，使用 BackUpNodes 方法并开启虚拟化似乎是将项目数量扩展到大型集合（每个节点超过 500 个子项目）的最佳方法。

剩下的一个谜团是：

为什么树视图项的 `Visibility` 属性设置比添加/删除节点慢这么多？

这个问题的答案是，在集合中添加数千个项目只是为了让它们对用户不可见，效率不高。更糟糕的是，让这些项目占用内存和 CPU 使用率，只是为了通过绑定和转换器发现它们不应该可见，这在处理大数据集时绝不是最佳选择。

摘要

上面展示的迭代树遍历算法不仅可以放心地以复制粘贴的方式使用（只需将 **Console.WriteLine** 替换为对在每个树节点上执行所需操作的方法的调用）。还可以使用一个泛型（委托）方法参数，我们可以将其传递给算法，以重用遍历算法，而无需维护多个冗余的代码库。

上述带有泛型方法参数的方法以非常灵活的方式将几乎任何请求的节点操作插入到树遍历算法中。但我们也可以通过使用上面IEnumerable/yield部分中讨论的 `foreach` 循环将遍历的项从算法中提取出来。这种方法似乎更有优势，因为它将遍历算法与在树结构上执行的操作明确分离。并且 TreeLib 库中可用的实现可以在广泛的 .Net 环境中重用。

文章的第二部分表明，高效地加载、保存和搜索树视图中的数据远非易事，但如果我们将众所周知且成熟的算法与现代技术相结合，则可以实现。我们已经意识到，在 WPF 中处理大型集合时，**不使用标准 `Visibility` 属性**来绑定 ViewModel 和 View 项似乎是最有效的选择。

我们已经证明，使用 BackupNodes 添加和删除项目更快，并且扩展性更好。这是过滤 WPF TreeViews 最快、最具可伸缩性的方法——直到有人找到更快的解决方案。

额外内容

• 下载 FilterTreeView_Bonus.zip
• 下载 VB_FilterTreeView_Bonus.zip

快速搜索项目的方法似乎很有用，但是突出显示找到的项目呢？这个问题（和一些小的错误修复）也在本节附带的解决方案中得到解决。关于其工作原理的解释将在另一篇文章中给出：可高亮显示的 WPF/MVVM TextBlock。

历史

• 2017-11-27 添加了额外内容部分
• 2017-12-08 添加了更多 VB.Net 示例代码

参考文献

• [1] 高级 WPF 树视图 - 第 1 部分
  [2] 高级 WPF 树视图 - 第 2 部分
  [7] C#/VB.Net 中的高级 WPF 树视图 - 第 4 部分
  [8] C#/VB.Net 中的高级 WPF 树视图 - 第 5 部分
  [9] C#/VB.Net 中的高级 TreeView - 第 6 部分
   
• [3] 通过使用 ViewModel 模式简化 WPF TreeView
       可搜索的 WPF TreeView
   
• [4] 二叉树遍历：前序、中序、后序 (on youtube.com)
       树遍历 (on Wikipedia)
  
  书籍
  Robert Sedgwick 著《C 语言算法》，第 1-4 部分（基本数据结构、排序、搜索）
  Kenneth H. Rosen 主编《离散与组合数学手册》
   
• [5] C# 中的泛型树和链表遍历 作者：Mike Adelson
   
• [6] 在 C#/VB.Net 中使用 SQLite