c# - 遍历树时查找节点

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 查询实现相同的目的。

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