9

ツリー内のノードを見つけることができるメソッドを実装したいと思います。私のやり方は、グローバル変数を再帰的に使用して、いつ停止するかを知ることです。

私はクラスを持っています：

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

私がしていることを冗長にすることであり、おそらくそのメソッドを作成するためのより良い方法があると思います。または、ノードクラスを変更して、linqクエリで同じことを実行できるようにすることもできます。

4

6 に答える 6

16

私はそれをこのようにします：

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);
}
于 2012-06-22T17:56:53.563 に答える
14

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;
}
于 2012-06-22T18:02:19.383 に答える
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;
}
于 2012-06-22T18:06:54.447 に答える
2

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;
}
于 2012-06-22T18:06:01.623 に答える
1

再帰、および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");
于 2012-06-22T18:24:46.403 に答える
0

LINQのようなAPIを作成することを検討してください。「検索」と「実行」の部分を分割して単純にします。「Act」部分には特別なカスタムコードは必要ないかもしれませんが、既存のLINQで十分です。

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

ニーズに応じて、ツリー全体を1回ウォークし、各ノードをチェックしてWhereを実装するか、遅延反復で適切に実行します。怠惰な反復の場合、現在の位置を記憶するある種の構造が必要になります（つまり、アクセスするノードのスタックと子のインデックス）。

注：グローバル変数の使用は避けてください。つまり、現在のコードでは、Find関数からtrue / falseを返すだけで、trueが返されたときに反復を停止する方が適切なアプローチです。

于 2012-06-22T17:55:26.610 に答える