it-swarm-eu.dev

Baumdatenstruktur in C #

Ich habe in C # nach einer Baum- oder Diagrammdatenstruktur gesucht, aber es wird wohl keine bereitgestellt. Eine ausführliche Untersuchung von Datenstrukturen mit C # 2. erklärt ein wenig, warum. Gibt es eine praktische Bibliothek, die häufig verwendet wird, um diese Funktionalität bereitzustellen? Vielleicht durch ein Strategiemuster, um die im Artikel vorgestellten Probleme zu lösen.

Ich fühle mich ein bisschen albern, meinen eigenen Baum zu implementieren, genauso wie ich meine eigene ArrayList implementieren würde.

Ich möchte nur einen generischen Baum, der aus dem Gleichgewicht gebracht werden kann. Stellen Sie sich einen Verzeichnisbaum vor. C5 sieht gut aus, aber ihre Baumstrukturen scheinen als ausgeglichene rot-schwarze Bäume implementiert zu sein, die besser für die Suche geeignet sind als die Darstellung einer Hierarchie von Knoten.

233
stimms

Mein bester Rat wäre, dass es keine standardmäßige Baumdatenstruktur gibt, da es so viele Möglichkeiten gibt, diese zu implementieren, dass es unmöglich wäre, alle Grundlagen mit einer Lösung abzudecken. Je spezifischer eine Lösung ist, desto weniger wahrscheinlich ist sie auf ein bestimmtes Problem anwendbar. Ich ärgere mich sogar über LinkedList - was ist, wenn ich eine zirkuläre verknüpfte Liste möchte?

Die grundlegende Struktur, die Sie implementieren müssen, besteht aus einer Sammlung von Knoten. Hier sind einige Optionen, mit denen Sie beginnen können. Angenommen, die Klasse Node ist die Basisklasse der gesamten Lösung.

Wenn Sie nur in der Baumstruktur navigieren müssen, benötigt eine Node class eine Liste der untergeordneten Elemente.

Wenn Sie in der Struktur nach oben navigieren müssen, benötigt die Node class eine Verknüpfung zu ihrem übergeordneten Knoten.

Erstellen Sie eine AddChild-Methode, die alle Details dieser beiden Punkte und alle anderen Geschäftslogiken berücksichtigt, die implementiert werden müssen (untergeordnete Grenzen, Sortieren der untergeordneten Elemente usw.).

145
David Boike

Ich gebe es nicht gerne zu, aber ich habe am Ende meine eigene Baumklasse mit einer verknüpften Liste geschrieben. Aus einem anderen Grund habe ich gerade diese runde Sache entdeckt, die, wenn sie an einer Sache befestigt ist, die ich 'Achse' nenne, einen leichteren Warentransport ermöglicht.

194
stimms
delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    private T data;
    private LinkedList<NTree<T>> children;

    public NTree(T data)
    {
         this.data = data;
        children = new LinkedList<NTree<T>>();
    }

    public void AddChild(T data)
    {
        children.AddFirst(new NTree<T>(data));
    }

    public NTree<T> GetChild(int i)
    {
        foreach (NTree<T> n in children)
            if (--i == 0)
                return n;
        return null;
    }

    public void Traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            Traverse(kid, visitor);
    }
}

Einfache rekursive Implementierung ... <40 Codezeilen ... Sie müssen nur einen Verweis auf die Wurzel des Baums außerhalb der Klasse behalten oder ihn in eine andere Klasse einschließen, vielleicht in TreeNode umbenennen?

116
Aaron Gage

Hier ist meine, die meiner Meinung nach Aaron Gage's sehr ähnlich ist, nur ein bisschen konventioneller. Für meine Zwecke habe ich keine Leistungsprobleme mit List<T>. Es wäre einfach genug, bei Bedarf zu einer LinkedList zu wechseln.


namespace Overby.Collections
{
    public class TreeNode<T>
    {
        private readonly T _value;
        private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

        public TreeNode(T value)
        {
            _value = value;
        }

        public TreeNode<T> this[int i]
        {
            get { return _children[i]; }
        }

        public TreeNode<T> Parent { get; private set; }

        public T Value { get { return _value; } }

        public ReadOnlyCollection<TreeNode<T>> Children
        {
            get { return _children.AsReadOnly(); }
        }

        public TreeNode<T> AddChild(T value)
        {
            var node = new TreeNode<T>(value) {Parent = this};
            _children.Add(node);
            return node;
        }

        public TreeNode<T>[] AddChildren(params T[] values)
        {
            return values.Select(AddChild).ToArray();
        }

        public bool RemoveChild(TreeNode<T> node)
        {
            return _children.Remove(node);
        }

        public void Traverse(Action<T> action)
        {
            action(Value);
            foreach (var child in _children)
                child.Traverse(action);
        }

        public IEnumerable<T> Flatten()
        {
            return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten()));
        }
    }
}
50
Ronnie Overby

Noch eine andere Baumstruktur:

public class TreeNode<T> : IEnumerable<TreeNode<T>>
{

    public T Data { get; set; }
    public TreeNode<T> Parent { get; set; }
    public ICollection<TreeNode<T>> Children { get; set; }

    public TreeNode(T data)
    {
        this.Data = data;
        this.Children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> AddChild(T child)
    {
        TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
        this.Children.Add(childNode);
        return childNode;
    }

    ... // for iterator details see below link
}

Beispielnutzung:

TreeNode<string> root = new TreeNode<string>("root");
{
    TreeNode<string> node0 = root.AddChild("node0");
    TreeNode<string> node1 = root.AddChild("node1");
    TreeNode<string> node2 = root.AddChild("node2");
    {
        TreeNode<string> node20 = node2.AddChild(null);
        TreeNode<string> node21 = node2.AddChild("node21");
        {
            TreeNode<string> node210 = node21.AddChild("node210");
            TreeNode<string> node211 = node21.AddChild("node211");
        }
    }
    TreeNode<string> node3 = root.AddChild("node3");
    {
        TreeNode<string> node30 = node3.AddChild("node30");
    }
}

[~ # ~] Bonus [~ # ~]
Siehe vollwertigen Baum mit:

  • iterator
  • suche
  • Java/C #

https://github.com/gt4dev/yet-another-tree-structure

44
Grzegorz Dev

Das allgemein ausgezeichnete C5 Generic Collection Library verfügt über verschiedene baumbasierte Datenstrukturen, einschließlich Mengen, Taschen und Wörterbüchern. Der Quellcode ist verfügbar, wenn Sie deren Implementierungsdetails untersuchen möchten. (Ich habe C5-Sammlungen im Produktionscode mit guten Ergebnissen verwendet, obwohl ich keine der Baumstrukturen speziell verwendet habe.)

22
McKenzieG1

Siehe http://quickgraph.codeplex.com/

QuickGraph bietet generische gerichtete/ungerichtete Graphdatenstrukturen und Algorithmen für .Net 2.0 und höher. QuickGraph enthält Algorithmen wie Tiefensuche, Atemzugssuche, A * -Suche, kürzester Pfad, k-kürzester Pfad, maximaler Fluss, minimaler Spannbaum, am wenigsten verbreitete Vorfahren usw. QuickGraph unterstützt MSAGL, GLEE und Graphviz bis Rendern der Grafiken, Serialisierung nach GraphML usw.

10
nietras

Wenn Sie selbst schreiben möchten, können Sie mit diesem sechsteiligen Dokument beginnen, in dem die effektive Verwendung von C # 2.0-Datenstrukturen und die Analyse Ihrer Implementierung von Datenstrukturen in C # beschrieben werden. Jeder Artikel enthält Beispiele und ein Installationsprogramm mit Beispielen, denen Sie folgen können.

„Eine umfassende Untersuchung von Datenstrukturen mit C # 2.0“ von Scott Mitchell

8
user7116

Ich habe eine kleine Erweiterung der Lösungen.

Mit einer rekursiven generischen Deklaration und einer daraus abgeleiteten Unterklasse können Sie sich besser auf Ihr eigentliches Ziel konzentrieren.

Beachten Sie, dass es sich von einer nicht generischen Implementierung unterscheidet. Sie müssen "node" nicht in "NodeWorker" umwandeln.

Hier ist mein Beispiel:

public class GenericTree<T> where T : GenericTree<T> // recursive constraint  
{
  // no specific data declaration  

  protected List<T> children;

  public GenericTree()
  {
    this.children = new List<T>();
  }

  public virtual void AddChild(T newChild)
  {
    this.children.Add(newChild);
  }

  public void Traverse(Action<int, T> visitor)
  {
    this.traverse(0, visitor);
  }

  protected virtual void traverse(int depth, Action<int, T> visitor)
  {
    visitor(depth, (T)this);
    foreach (T child in this.children)
      child.traverse(depth + 1, visitor);
  }
}

public class GenericTreeNext : GenericTree<GenericTreeNext> // concrete derivation
{
  public string Name {get; set;} // user-data example

  public GenericTreeNext(string name)
  {
    this.Name = name;
  }
}

static void Main(string[] args)  
{  
  GenericTreeNext tree = new GenericTreeNext("Main-Harry");  
  tree.AddChild(new GenericTreeNext("Main-Sub-Willy"));  
  GenericTreeNext inter = new GenericTreeNext("Main-Inter-Willy");  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Tom"));  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Magda"));  
  tree.AddChild(inter);  
  tree.AddChild(new GenericTreeNext("Main-Sub-Chantal"));  
  tree.Traverse(NodeWorker);  
}  

static void NodeWorker(int depth, GenericTreeNext node)  
{                                // a little one-line string-concatenation (n-times)
  Console.WriteLine("{0}{1}: {2}", String.Join("   ", new string[depth + 1]), depth, node.Name);  
}  
6
Erik Nagel

Probieren Sie dieses einfache Beispiel aus.

public class TreeNode<TValue>
{
    #region Properties
    public TValue Value { get; set; }
    public List<TreeNode<TValue>> Children { get; private set; }
    public bool HasChild { get { return Children.Any(); } }
    #endregion
    #region Constructor
    public TreeNode()
    {
        this.Children = new List<TreeNode<TValue>>();
    }
    public TreeNode(TValue value)
        : this()
    {
        this.Value = value;
    }
    #endregion
    #region Methods
    public void AddChild(TreeNode<TValue> treeNode)
    {
        Children.Add(treeNode);
    }
    public void AddChild(TValue value)
    {
        var treeNode = new TreeNode<TValue>(value);
        AddChild(treeNode);
    }
    #endregion
}
4
Berezh

Ich erstelle eine Node-Klasse , die für andere hilfreich sein könnte. Die Klasse hat Eigenschaften wie:

  • Kinder
  • Ahnen
  • Nachkommenschaft
  • Geschwister
  • Ebene des Knotens
  • Elternteil
  • Root
  • Usw.

Es besteht auch die Möglichkeit, eine flache Liste von Elementen mit einer ID und einer ParentId in einen Baum zu konvertieren. Der Knoten enthält einen Verweis sowohl auf die untergeordneten als auch auf die übergeordneten Knoten, sodass die Iteration von Knoten sehr schnell erfolgt.

2
Alex Siepman

Da es nicht erwähnt wird, möchte ich Sie auf die jetzt veröffentlichte .net-Codebasis aufmerksam machen: speziell auf den Code für ein SortedSet, das einen Rot-Schwarz-Baum implementiert:

https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs

Dies ist jedoch eine ausgewogene Baumstruktur. Meine Antwort ist also eher ein Verweis auf die meiner Meinung nach einzige native Baumstruktur in der .net-Kernbibliothek.

2
Meirion Hughes

Hier ist ein Baum

public class Tree<T> : List<Tree<T>>
{
    public  T Data { get; private set; }

    public Tree(T data)
    {
        this.Data = data;
    }

    public Tree<T> Add(T data)
    {
        var node = new Tree<T>(data);
        this.Add(node);
        return node;
    }
}

Sie können sogar Initialisierer verwenden:

    var tree = new Tree<string>("root")
    {
        new Tree<string>("sample")
        {
            "console1"
        }
    };
2
Visar

Hier ist meine eigene:

class Program
{
    static void Main(string[] args)
    {
        var tree = new Tree<string>()
            .Begin("Fastfood")
                .Begin("Pizza")
                    .Add("Margherita")
                    .Add("Marinara")
                .End()
                .Begin("Burger")
                    .Add("Cheese burger")
                    .Add("Chili burger")
                    .Add("Rice burger")
                .End()
            .End();

        tree.Nodes.ForEach(p => PrintNode(p, 0));
        Console.ReadKey();
    }

    static void PrintNode<T>(TreeNode<T> node, int level)
    {
        Console.WriteLine("{0}{1}", new string(' ', level * 3), node.Value);
        level++;
        node.Children.ForEach(p => PrintNode(p, level));
    }
}

public class Tree<T>
{
    private Stack<TreeNode<T>> m_Stack = new Stack<TreeNode<T>>();

    public List<TreeNode<T>> Nodes { get; } = new List<TreeNode<T>>();

    public Tree<T> Begin(T val)
    {
        if (m_Stack.Count == 0)
        {
            var node = new TreeNode<T>(val, null);
            Nodes.Add(node);
            m_Stack.Push(node);
        }
        else
        {
            var node = m_Stack.Peek().Add(val);
            m_Stack.Push(node);
        }

        return this;
    }

    public Tree<T> Add(T val)
    {
        m_Stack.Peek().Add(val);
        return this;
    }

    public Tree<T> End()
    {
        m_Stack.Pop();
        return this;
    }
}

public class TreeNode<T>
{
    public T Value { get; }
    public TreeNode<T> Parent { get; }
    public List<TreeNode<T>> Children { get; }

    public TreeNode(T val, TreeNode<T> parent)
    {
        Value = val;
        Parent = parent;
        Children = new List<TreeNode<T>>();
    }

    public TreeNode<T> Add(T val)
    {
        var node = new TreeNode<T>(val, this);
        Children.Add(node);
        return node;
    }
}

Ausgabe:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger
2
moien

Ich habe den Code vervollständigt, den @Berezh freigegeben hat.

  public class TreeNode<T> : IEnumerable<TreeNode<T>>
    {

        public T Data { get; set; }
        public TreeNode<T> Parent { get; set; }
        public ICollection<TreeNode<T>> Children { get; set; }

        public TreeNode(T data)
        {
            this.Data = data;
            this.Children = new LinkedList<TreeNode<T>>();
        }

        public TreeNode<T> AddChild(T child)
        {
            TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
            this.Children.Add(childNode);
            return childNode;
        }

        public IEnumerator<TreeNode<T>> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return (IEnumerator)GetEnumerator();
        }
    }
    public class TreeNodeEnum<T> : IEnumerator<TreeNode<T>>
    {

        int position = -1;
        public List<TreeNode<T>> Nodes { get; set; }

        public TreeNode<T> Current
        {
            get
            {
                try
                {
                    return Nodes[position];
                }
                catch (IndexOutOfRangeException)
                {
                    throw new InvalidOperationException();
                }
            }
        }


        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }


        public TreeNodeEnum(List<TreeNode<T>> nodes)
        {
            Nodes = nodes;
        }

        public void Dispose()
        {
        }

        public bool MoveNext()
        {
            position++;
            return (position < Nodes.Count);
        }

        public void Reset()
        {
            position = -1;
        }
    }
2
Ashkan Sirous

Die meisten Bäume werden von den Daten gebildet, die Sie verarbeiten.

Angenommen, Sie haben eine person -Klasse, die Details zu der parents -Klasse einer anderen Person enthält. Möchten Sie die Baumstruktur lieber als Teil Ihrer „Domänenklasse“ verwenden oder eine separate Baumklasse verwenden, die Links zu Ihrer Klasse enthält? Person Objekte? Denken Sie an eine einfache Operation wie das Abrufen aller grandchildren eines person, sollte dieser Code in der person -Klasse enthalten sein, oder sollte der Benutzer des person Klasse müssen über eine separate Baumklasse wissen?

Ein weiteres Beispiel ist ein Analysebaum in einem Compiler…

Diese beiden Beispiele zeigen, dass das Konzept eines Baums Teil der Domäne der Daten ist und die Verwendung eines separaten Mehrzweckbaums die Anzahl der erstellten Objekte und die Anzahl der erstellten Objekte mindestens verdoppelt API schwerer wieder zu programmieren.

Was wir wollen, ist eine Möglichkeit, die Standardbaumoperationen wiederzuverwenden, ohne sie für alle Bäume erneut implementieren zu müssen, während gleichzeitig keine Standardbaumklasse verwendet werden muss. Boost hat versucht, diese Art von Problem für C++ zu lösen, aber ich sehe noch keinen Effekt für .NET, der angepasst wird.

1
Ian Ringrose

Ich habe eine vollständige Lösung und ein Beispiel mit der obigen NTree-Klasse hinzugefügt und auch die Methode "AddChild" hinzugefügt ...

    public class NTree<T>
    {
        public T data;
        public LinkedList<NTree<T>> children;

        public NTree(T data)
        {
            this.data = data;
            children = new LinkedList<NTree<T>>();
        }

        public void AddChild(T data)
        {
            var node = new NTree<T>(data) { Parent = this };
            children.AddFirst(node);
        }

        public NTree<T> Parent { get; private set; }

        public NTree<T> GetChild(int i)
        {
            foreach (NTree<T> n in children)
                if (--i == 0)
                    return n;
            return null;
        }

        public void Traverse(NTree<T> node, TreeVisitor<T> visitor, string t, ref NTree<T> r)
        {
            visitor(node.data, node, t, ref r);
            foreach (NTree<T> kid in node.children)
                Traverse(kid, visitor, t, ref r);
        }
    }
    public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r)
    {
        string a = string.Empty;
        if (node.data.Key == t)
        {
            r = node;
            return;
        }
    }

mit

 NTree<KeyValuePair<string, string>> ret = null;
 tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret);
1
Dmitry

Wenn Sie diesen Baum auf der GUI anzeigen möchten, können Sie TreeView und TreeNode verwenden. (Ich nehme an, Sie können einen TreeNode technisch erstellen, ohne ihn auf einer GUI zu platzieren, aber der Aufwand ist höher als bei einer einfachen hausgemachten TreeNode-Implementierung.)

0
Denise Skidmore