1

私がこの木を持っているとしましょう：

           O-ROOT
         /        \
    O-A            O-B
     /          /       \
O-A1        O-B1        O-B2

そして私はこれをC＃でやりたいです：

1. Check every node starting from root (I think the best way is trought recursion?);
2. If I found a node with value = "Hello", return true and STOP the searching function;

それを行うための最良のアルゴリズムを作成するのを手伝ってもらえますか？

4

5 に答える 5

2

あなたの問題に対する最善のアプローチは、幅優先検索を使用することだと思います。書くのは簡単で、できる限り効果的です。

編集:次のようなもの:

public bool Search(TreeNode node, string searchString)
{
   Queue<Control> q = new Queue<Node>();
   q.Enqueue(node);
   while(!q.empty()) {
     Node current = q.Dequeue();
     foreach(var childNode in node.Children)
       if(childNode.Content.CompareTo(searchString) == 0) {
         return true;
       }
       q.Enqueue(childNode);
     }
   }
   return false;
}
于 2012-04-12T07:20:17.883 に答える
2 
bool FindHello(Node node)
{
    if (node.Content == "Hello")
        return true;
    foreach (Node c in node.Children)
        if (FindHello(c))
            return true;
    return false;
}
于 2012-04-12T07:20:54.920 に答える
1

幅優先検索と深さ優先検索は、(とりわけ) 最も人気のあるツリー検索手法の 1 つであり、そこから始めることができます。また、ツリーの各ノードに最大 2 つのノードがあり、それらが何らかの方法でソートされている場合は、バイナリ サーチ ツリー手法を使用できます。

于 2012-04-12T07:19:57.370 に答える
1

再帰については正しいです。深さ優先または幅優先の検索アルゴリズムを参照してください。すでに訪問したノードのリストを保持していないため、ツリーの方がはるかに簡単です。

public bool Search(TreeNode node, string searchString)
{
   if(node.Value == searchString) return true;
   foreach(var childNode in node.Children)
     if(Search(childNode, searchString)) return true;
   return false;
}
于 2012-04-12T07:20:55.607 に答える
0
  1. 確かに、これには間違いなく再帰を使用してください。
  2. 再帰的な方法を使用している場合は、結果のような (静的) メンバー変数を設定し、設定されている場合は各反復を確認できます。設定されている場合、メソッドから飛び出して (return)、それ以上の再帰の実行を停止します。
于 2012-04-12T07:17:49.150 に答える