遍历树时查找节点

Question

我希望能够实现一种方法，使我能够在树中查找节点。我的做法是通过递归使用全局变量来知道何时停止。 我有以下类：

class Node    // represents a node in the tree
{ 
     // constructor
     public Node() {
          Children = new List<Node>();
     }

     public List<Node> Children; 
     public string Name;
     public string Content;            
}

目前我拥有的方法是：

    private bool IsNodeFound = false; // global variable that I use to decide when to stop

    // method to find a particular node in the tree
    private void Find(Node node, string stringToFind, Action<Node> foundNode)
    {
        if(IsNodeFound)
           return;

        if (node.Content.Contains(stringToFind)){
            foundNode(node); 
            IsNodeFound =true;               
        }

        foreach (var child in node.Children)
        {
            if (child.Content.Contains(stringToFind)){
                foundNode(node);
                IsNodeFound =true;               
            }

            Find(child, stringToFind, foundNode);
        }

    }

我使用的Find方法如下：

   // root is a node that contain children and those children also contain children
   // root is the "root" of the tree
   IsNodeFound =false;
   Node nodeToFind = null;
   Find(root, "some string to look for", (x)=> nodeToFind=x);

所以我的问题是如何让这个方法更优雅。我希望该方法的签名看起来像：

   public Node FindNode(Node rootNode);

我认为我的做法过于冗余，可能有更好的方法来创建这个方法。或者我可以修改 Node 类，以便通过 linq 查询实现相同的效果。

- Tono Nam

Answer 1

我会这样做：

编写一个实例方法来生成一个节点的子树（如果您无法控制Node类，则可以将其作为扩展）：

public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy
{
     return new[] { this }
            .Concat(Children.SelectMany(child => child.GetNodeAndDescendants()));    
}

那么你只需要使用一点 LINQ 就可以找到节点：

var foundNode = rootNode.GetNodeAndDescendants()
                        .FirstOrDefault(node => node.Content.Contains(stringToFind));

if(foundNode != null)
{
    DoSomething(foundNode);
}

- Ani

---

+1 很好用，因为可以根据任何条件进行筛选，例如：root.GetSubTree().FirstOrDefault(x => x.Name=="Foo"); 非常感谢! - Tono Nam

如此干净、精确的答案。 - AndyUK

Answer 2

你可以使用其他使用 Linq 的答案之一，或者你可以使用递归的深度优先搜索机制：

public Node Find(string stringToFind)
{
    // find the string, starting with the current instance
    return Find(this, stringToFind);
}

// Search for a string in the specified node and all of its children
public Node Find(Node node, string stringToFind)
{
    if (node.Content.Contains(stringToFind))
        return node;

    foreach (var child in node.Children) 
    { 
        var result = Find(child, stringToFind);
        if (result != null)
            return result;
    }

    return null;
}

- Ryan

Answer 3

你可以使用递归的深度优先搜索（不需要全局变量来知道何时终止）：

Node FindNode1( Node rootNode, string stringToFind ) {
    if( rootNode.Content == stringToFind ) return rootNode;
    foreach( var child in rootNode.Children ) {
        var n = FindNode1( child, stringToFind );
        if( n != null ) return n;
    }
    return null;
}

如果您希望避免递归，您可以使用堆栈以非递归的方式完成相同的事情：

Node FindNode2( Node rootNode, string stringToFind ) {
    var stack = new Stack<Node>( new[] { rootNode } );
    while( stack.Any() ) {
        var n = stack.Pop();
        if( n.Content == stringToFind ) return n;
        foreach( var child in n.Children ) stack.Push( child );
    }
    return null;
}

- Ethan Brown

Answer 4

如果linq的答案让你像我一样困惑，这里是我如何使用简单的递归来完成它。请注意，它是深度优先的，如果对您的模型更有意义，您可能需要将其更改为广度优先。

public Node FindNode(Node rootNode)
{
    if (rootNode.Content.Contains(stringToFind))
       return rootNode;

    foreach (Node node in rootNode.Children)
    {
        if (node.Content.Contains(stringToFind))
           return node;
        else
           return FindNode(node);
    }

    return null;
}

- Kevin DiTraglia

---

完全同意。虽然有很多情况下基于LINQ的解决方案非常漂亮，可以简化代码并使其意图非常清晰，但我认为这个解决方案则相反。 - Nikola Anusev

Answer 5

递归和PLinq

    private Node Find(Node node, Func<Node, bool> predicate)
    {
        if (predicate(node))
            return node;

        foreach (var n in node.Children.AsParallel())
        {
            var found = Find(n, predicate);
            if (found != default(Node))
                return found;
        }
        return default(Node);
    }

并调用代码：

     var found = Find(root, (n) => n.Content.Contains("3"));
     if (found != default(Node))
         Console.Write("found '{0}'", found.Name);
     else Console.Write("not found");

- Juan Ayala

Answer 6

考虑制作类似于 LINQ 的 API：将“查找”和“操作”部分分离以使其简单。您甚至可能不需要任何特殊的自定义代码来处理“操作”部分，现有的 LINQ 将可以胜任。

public IEnumerable<Node> Where(Func<Node, bool> condition);

根据您的需求，您可以遍历整个树并检查每个节点以实现“Where”，或者使用延迟迭代进行正确的操作。对于延迟迭代，您将需要一些记住当前位置的结构（即要访问的节点和子节点的索引的堆栈）。

注意：请避免使用全局变量。即在您当前的代码中，从Find函数简单地返回true/false，并在返回true时停止迭代，这将是更好的方法。

- Alexei Levenkov