ツリーを探索する、Cをトラバースする最も簡単な方法＃

Question

私は、任意の多くの子を持つツリーを検索できるようにする必要があります。 このように見える可能性があります。各C. 内の任意の多くの子どもたちと

        P 
           /| \ 
           C C C  layer 1 
          /| \ 
          C C C   layer 2 
          | 
          C    layer 3 
         /| \ 
         C C C    layer 4 

層1の各開始ノードのための二重リンクリストを持っていることはとても便利ですか？ （レイヤー1では、拡張していないノードもまた拡張するかもしれない）。 すべてのサブツリーを評価して作業する必要があります。

最も簡単な方法は何ですか？ または深さの最初の検索/幅広い最初の検索の方が良いでしょうか？ ツリーはオンザフライで構築されています。

ありがとう

Answer 1

最も簡単な方法は、再帰を使用することです。

あなたのツリーにはT型のアイテムが格納されており、そのタイプはIEquatable<T>を実装しているとしましょう。

まず、のは非常に基本的な木のクラスを書いてみましょう：

public sealed class Node<T> 
{ 
    public Node(T value) { Value = value; } 
    public T Value { get; } 
    public IEnumerable<Node<T>> Children => _children; 

    public void Add(Node<T> child) 
    { 
     _children.Add(child); 
    } 

    readonly List<Node<T>> _children = new List<Node<T>>(); 
} 

今、私たちは非常に単純再帰を使用して、そのツリーを検索する方法を書くことができます。 これは、見つかった場合は指定された値を含む最初のノードを返します。見つからない場合はnullを返します。

public static Node<T> Find<T>(Node<T> root, T target) where T: IEquatable<T> 
{ 
    if (root.Value != null && root.Value.Equals(target)) 
     return root; 

    foreach (var child in root.Children) 
    { 
     var found = Find(child, target); 

     if (found != null) 
      return found; 
    } 

    return null; 
} 

それはターゲットに一致するすべてのノードを返すために、これを適応するのは簡単です：デモ目的のために

public static IEnumerable<Node<T>> FindAll<T>(Node<T> root, T target) where T : IEquatable<T> 
{ 
    if (root.Value != null && root.Value.Equals(target)) 
     yield return root; 

    foreach (var child in root.Children) 
    { 
     var found = FindAll(child, target); 

     foreach (var item in found) 
      yield return item; 
    } 
} 

は、ここでコンパイルコンソールアプリケーションです。それにはmakeTree()メソッドが含まれています。このメソッドでは、各ノードに5つの子がある深さ4のツリーを作成します。

次に、Find<T>(Node<T> root, T target)を使用して、指定されたターゲット値を見つけるためにツリーを再帰的に検索します。 1つは成功し、もう1つは失敗します。

using System; 
using System.Collections.Generic; 

namespace Demo 
{ 
    public sealed class Node<T> 
    { 
     public Node(T value) { Value = value; } 
     public T Value { get; } 
     public IEnumerable<Node<T>> Children => _children; 

     public void Add(Node<T> child) 
     { 
      _children.Add(child); 
     } 

     readonly List<Node<T>> _children = new List<Node<T>>(); 
    } 

    class Program 
    { 
     static void Main() 
     { 
      var root = makeTree(1, 1, 4, 5); 

      lookFor(root, "3.4"); 
      lookFor(root, "6.3"); 
     } 

     static void lookFor<T>(Node<T> root, T target) where T: IEquatable<T> 
     { 
      var found = Find(root, target); 
      Console.WriteLine(found != null ? $"Found {target}" : $"Did not find {target}"); 
     } 

     public static Node<T> Find<T>(Node<T> root, T target) where T: IEquatable<T> 
     { 
      if (root.Value != null && root.Value.Equals(target)) 
       return root; 

      foreach (var child in root.Children) 
      { 
       var found = Find(child, target); 

       if (found != null) 
        return found; 
      } 

      return null; 
     } 

     static Node<string> makeTree(int id1, int id2, int depth, int nChildren) 
     { 
      var root = new Node<string>($"{id1}.{id2}"); 

      if (depth == 0) 
       return root; 

      for (int i = 0; i < nChildren; ++i) 
       root.Add(makeTree(id1+1, i+1, depth-1, nChildren)); 

      return root; 
     } 
    } 
}