c# - 有效地搜索树结构中的所有节点

Question

我正在使用一个树型结构，该结构由单个“根”TreeNodeDefinition 记录组成，其中可以包含其他 TreeNodeDefinition 类的列表，然后每个类都可以包含一个进一步的列表，依此类推。

我基本上希望能够遍历树结构中的所有节点并检查每个节点是否满足条件，然后将该定义记录添加到列表中。我想出了一种方法来做到这一点，但我忍不住认为还有一种更有效的方法:

List<ITreeNodeDefinition> treeNodeDefinitions = new List<ITreeNodeDefinition>();

treeNodeDefinitions = treeFactory.SearchNodesByRelationshipId(treeNodeDefinition, relationshipId, new List<ITreeNodeDefinition>());

第一个参数是我的根节点定义记录，第二个参数是我需要比较每个节点的内容，最后我传入一个空列表，每次有节点匹配我的检查时我都想填充它。方法如下:

    public List<ITreeNodeDefinition> SearchNodesByRelationshipId(ITreeNodeDefinition treeNodeDefinition, int? relationshipId, List<ITreeNodeDefinition> tndList)
    {
        if (treeNodeDefinition.RelationshipId == relationshipId)
        {
            tndList.Add(treeNodeDefinition);
        }

        if (treeNodeDefinition.Nodes.Count != 0)
        {
            foreach (ITreeNodeDefinition nodeDefinition in treeNodeDefinition.Nodes)
            {
                List<ITreeNodeDefinition> tempTable = this.SearchNodesByRelationshipId(nodeDefinition, relationshipId, tndList);
            }
        }
        return tndList;
    }

如您所见，该方法为在 treeNodeDefinition.Nodes 列表中找到的每个子节点调用自身。这正在返回到一个我从不做任何事情的 tempTable ......这对我来说效率低下。我想知道是否有更直接的方法来导航这种结构......我确定我只是错过了一个技巧。

Answer 1

您可以使用显式堆栈来解决此问题并完全避免递归:

public static IEnumerable<ITreeNodeDefinition> DepthFirstSearch(ITreeNodeDefinition root, int? relationshipId)
{
    var stack = new Stack<ITreeNodeDefinition>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        if (current.RelationshipId == relationshipId)
            yield return current;

        foreach(var node in current.Nodes)
            stack.Push(node);
    }
}

不过，要补充一点，完全不在关系 ID 检查中进行硬编码可能会更简单、更灵活，如果你发现你经常尝试遍历树结构，则只需在之后过滤结果:

var matches = treeFactory.Traverse(root)
                         .Where(t => t.RelationshipId == 5)
                         .ToList();

对此进行扩展，通过使用搜索谓词，您可以像 LINQ 一样将此搜索功能构建到方法中，您可以像这样实现它:

public static IEnumerable<ITreeNodeDefinition> DepthFirstSearch(ITreeNodeDefinition root, Func<ITreeNodeDefinition, bool> predicate)
{
    var stack = new Stack<ITreeNodeDefinition>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        if (predicate(current))
            yield return current;

        foreach (var node in current.Nodes)
            stack.Push(node);
    }
}

好处是您在遍历时不必在一种特定的搜索情况下进行硬编码。用 RelationshipId 调用它搜索将是:

var matches = treeFactory.DepthFirstSearch(root, t => t.RelationshipId == 5)
                         .ToList();

为了完整起见，下面是广度优先搜索的示例。注意 Queue<T> 中的区别对比Stack<T>关于遍历顺序如何变化:

public static IEnumerable<ITreeNodeDefinition> BreadthFirstSearch(ITreeNodeDefinition root, Func<ITreeNodeDefinition, bool> predicate)
{
    var queue = new Queue<ITreeNodeDefinition>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        if (predicate(current))
            yield return current;

        foreach (var node in current.Nodes)
            queue.Enqueue(node);
    }
}

对于您的用例，除了在列出节点时以通常更好的方式排序广度优先之外，任何一个都可能没有优势。