Suchbaum, einfachste Methode zum Durchlaufen C#

Question

Ich muss einen Baum mit beliebig vielen Kindern suchen können. Es könnte so aussehen.

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

mit beliebig vielen Kindern in jedem C. Ist es convinient eine doppelt verkettete Liste für jeden Knoten in Schicht 1 beginnen zu haben? (In Schicht 1 können die nicht expandierenden Knoten natürlich auch expandieren). Ich muss evaluieren und mit jedem Unterbaum arbeiten.

Was ist die einfachste Methode? Oder vielleicht eine Art Tiefe zuerst Suche/Breite erste Suche ist besser? Der Baum wird im laufenden Betrieb gebaut.

dank

Answer 1

Der einfachste Weg, dies zu tun Rekursion verwendet.

Angenommen, in Ihrem Baum werden Elemente vom Typ T gespeichert, und dieser Typ implementiert IEquatable<T>.

Zunächst werfen wir einen sehr einfachen Baum-Klasse schreiben:

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

Jetzt können wir eine Methode schreiben sehr einfach diesen Baum mit Rekursion zu suchen. Dies wird den ersten Knoten zurückgeben, der den angegebenen Wert enthält, falls er gefunden wurde, oder null, wenn kein solcher Knoten gefunden wurde.

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

Es ist einfach, diese anzupassen alle Knoten zurückzukehren, die das Ziel entsprechen:

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

Für Demozwecke, hier ist eine übersetzbare Konsolenanwendung. Es enthält eine makeTree() Methode, die ich benutze, um einen Baum der Tiefe 4 zu machen, wo jeder Knoten 5 Kinder hat.

Dann wird Find<T>(Node<T> root, T target) verwendet, um den Baum rekursiv zu durchsuchen, um die angegebenen Zielwerte zu finden. Einer wird erfolgreich sein, der andere wird scheitern:

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