时间戳

首页 > 解决方案 > 高效搜索树结构中的所有节点

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

问题描述

我正在使用由单个“根”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 列表中的每个子节点调用自身。这回到了一个我从不做任何事情的临时表......这对我来说效率低下。我想知道是否有更直接的方式来导航这种结构......我确定我只是错过了一个技巧。

标签： c#recursiontreenode

解决方案

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

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

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

推荐阅读