Baumdatenstruktur in C #

248

Ich habe nach einer Baum- oder Diagrammdatenstruktur in C # gesucht, aber ich denke, es ist keine vorhanden. Eine ausführliche Untersuchung von Datenstrukturen mit C # 2.0 erklärt ein wenig, warum. Gibt es eine praktische Bibliothek, die üblicherweise zur Bereitstellung dieser Funktionalität verwendet wird? Vielleicht durch ein Strategiemuster, um die im Artikel vorgestellten Probleme zu lösen.

Ich finde es 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 unausgeglichen sein 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.

stimms
quelle
2
Bit extremeren Bäume: stackoverflow.com/questions/196294/... ;-)
Tuomas Hietanen
Gibt es einen Grund, warum man eine TreeView nicht in das Projekt aufnehmen und verwenden kann? Es gibt keinen Grund, es einem Benutzer tatsächlich zu zeigen. Natürlich gibt es verschiedene Arten von Projekten, bei denen dies keine Option ist. Man kann immer neue Klassen erstellen, die vom Beispiel TreeNode erben, wenn besondere Komplexität erforderlich ist.
Einfach G.
9
Ich würde es für eine schlechte Idee halten, eine gesamte UI-Bibliothek für einen sehr einfachen Baum zu importieren.
Stimms
1
Könnten Sie motivieren? Es ist nicht mehr so, dass der tatsächliche Platzbedarf auf der Festplatte ein Problem darstellt. Ungeschickt? Wie ich bereits erwähnt habe, kann ich verstehen, dass dies keine Lösung für eine spezielle Software oder etwas ohne vorhandene Benutzeroberfläche ist. Ich bin ein fauler Programmierer, wenn ich eine Struktur kostenlos bekommen kann, ist alles gut. Und eine vorhandene Bibliothek hat viel umsonst, man kann viel Code von Leuten finden, die ihn für viele Dinge benutzt haben.
Einfach G.
Ich streite nicht, ich möchte nur Ihre Argumentation wissen.
Einfach G.

Antworten:

155

Mein bester Rat wäre, dass es keine Standardstruktur für Baumdaten gibt, da es so viele Möglichkeiten gibt, diese zu implementieren, dass es unmöglich wäre, alle Basen 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 Grundstruktur, die Sie implementieren müssen, besteht aus einer Sammlung von Knoten. Hier finden Sie einige Optionen, mit denen Sie beginnen können. Nehmen wir an, dass der Klassenknoten die Basisklasse der gesamten Lösung ist.

Wenn Sie nur im Baum nach unten navigieren müssen, benötigt eine Knotenklasse eine Liste der untergeordneten Elemente.

Wenn Sie im Baum nach oben navigieren müssen, benötigt die Node-Klasse einen Link 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 Grenzwerte, Sortieren der untergeordneten Elemente usw.).

David Boike
quelle
5
persönlich würde es mir nichts ausmachen, eine Art selbstausgleichenden Binärbaum zur Bibliothek hinzuzufügen, da dies eine zusätzliche Arbeit ist, als nur eine Adjazenzliste zu verwenden.
jk.
8
@jk Ich glaube, dass SortedDictionary und SortedSet auf rot / schwarzen Bäumen aufgebaut sind, daher sollte die Verwendung dieser Bäume funktionieren.
Jonp
Schauen Sie sich das zusammengesetzte Muster an ;-) Genau das, wonach Sie suchen
Nicolas Voron
119
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?

Aaron Gage
quelle
22
In diesem Fall können Sie in C # das Schreiben Ihres eigenen Delegaten vermeiden und den vorgefertigten Action<T>Delegaten verwenden : public void traverse(NTree<T> node, Action<T> visitor). Die Signatur von Aktion <> lautet : void Action<T>( T obj ). Es gibt auch Versionen von 0 bis 4 verschiedenen Parametern. Es gibt auch einen analogen Delegaten für Funktionen namens Func<>.
Benny Jobigan
2
Wie würde ich diesen Delegierten anrufen?
Freakishly
3
Es wäre eine gute Idee, die Traverse-Methode statisch zu ändern oder sie möglicherweise zu verpacken, um die rekursive Natur zu verbergen. Es ist jedoch einfach zu durchlaufen: Erstellen Sie eine Methode mit der Signatur des Delegaten, dh für einen Baum von Ints: void my_visitor_impl (int datum) - Machen Sie es bei Bedarf statisch und instanziieren Sie ein Delgate: TreeVisitor <int> my_visitor = my_visitor_impl; und dann auf dem Stammknoten oder der NTree-Klasse aufrufen, wenn Sie es statisch machen: NTree <int> .traverse (my_tree, my_visitor)
Aaron Gage
10
Wenn addChild () den hinzugefügten NTree zurückgibt, wird das Hinzufügen von Daten zu einem Baum einfacher. (Es sei denn, ich vermisse eine listige Methode, um damit einen Baum zu erstellen, ohne mich auf die Implementierungsdetails zu verlassen, die ein neu hinzugefügtes Kind == getChild (1)?)
Rory
1
Ich denke, diese Aussage --i == 0wird nur im Einzelfall funktionieren? Ist das wahr. Das hat mich verwirrt
Waseem Ahmad Naeem
57

Hier ist meine, die meiner Meinung nach Aaron Gages 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()));
        }
    }
}
Ronnie Overby
quelle
Warum wird Ihre Value-Eigenschaft angezeigt, wenn Sie sie im Konstruktor festlegen? das lässt es für Manipulationen offen, nachdem Sie es bereits über den Konstruktor eingestellt haben, oder? Sollte privat eingestellt sein?
PositiveGuy
Klar, warum nicht unveränderlich machen? Bearbeitet.
Ronnie Overby
Vielen Dank! Ich mochte es sehr, nicht meine eigenen schreiben zu müssen. (Ich kann immer noch nicht glauben, dass es keine native Sache gibt. Ich dachte immer, .net oder zumindest .net 4.0 hätte alles .)
neminem
3
Diese Lösung hat mir gefallen. Ich fand auch, dass ich einfügen musste, ich fügte die folgende Methode hinzu, um das zu tun. public TreeNode<T> InsertChild(TreeNode<T> parent, T value) { var node = new TreeNode<T>(value) { Parent = parent }; parent._children.Add(node); return node; } var five = myTree.AddChild(5); myTree.InsertChild(five, 55);
JabberwockyDecompiler
48

Noch eine 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
  • suchen
  • Java / C #

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

Grzegorz Dev
quelle
Wie verwende ich die Suche in Ihrem Codebeispiel? Woher kommt nodedas? Bedeutet das, dass ich über den Baum iterieren muss, um den Suchcode zu verwenden?
BadmintonCat
@GrzegorzDev Vielleicht -1, weil nicht alle IEnumerable<>Mitglieder implementiert sind und daher nicht kompiliert werden.
Uwe Keim
1
@UweKeim Good Job, versuchen Sie das nächste Mal, den Code mit den tatsächlichen Verwendungen zu verwenden.
szab.kel
Das einzige Problem, das ich sehe, ist, dass es mit Basic JsonConvert nicht korrekt serialisiert wird, da es IEnumerable <>
Rakiah
22

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

McKenzieG1
quelle
7
Ich weiß nicht, ob sich vielleicht etwas geändert hat, aber im Moment kann das Buch kostenlos als PDF von der C5-Site heruntergeladen werden.
Oskar
4
Der Mangel an Dokumentation ist kein Problem mehr, da es ein 272 Seiten langes PDF gibt, das die Bibliothek ergänzt ... Ich kann die Codequalität nicht kommentieren, aber nach der Dokumentqualität zu urteilen, freue ich mich wirklich darauf, mich heute Abend damit zu befassen!
Florian Doyon
2
Soweit ich weiß, enthält diese C5-Bibliothek überhaupt keine Bäume, sondern nur einige von Bäumen abgeleitete Datenstrukturen.
Roim
10

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 Tiefen-Erst-Suche, Atem-Erst-Suche, A * -Suche, kürzester Pfad, k-kürzester Pfad, maximaler Fluss, minimaler Spanning Tree, am wenigsten verbreitete Vorfahren usw. QuickGraph unterstützt MSAGL, GLEE und Graphviz to Rendern der Grafiken, Serialisierung in GraphML usw.

Nietras
quelle
8

Wenn Sie Ihre eigenen Daten 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

user7116
quelle
7

Ich habe eine kleine Erweiterung der Lösungen.

Mit einer rekursiven generischen Deklaration und einer ableitenden Unterklasse können Sie sich besser auf Ihr tatsächliches 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);  
}  
Erik Nagel
quelle
Was ist Tiefe und wo und wie bekommt man sie?
PositiveGuy
@ WeDoTDD.com Wenn Sie sich seine Klasse ansehen, sehen Sie, dass Traverse sie als 0 deklariert, um am Wurzelknoten zu beginnen, und dann die Methode traverse verwendet, die bei jeder Iteration zu dieser int hinzugefügt wird.
Edward
Wie würden Sie den gesamten Baum nach einem bestimmten Knoten durchsuchen?
Mattpm
6

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
Moien
quelle
4

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
}
Berezh
quelle
2

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

  • Kinder
  • Vorfahren
  • Nachkommenschaft
  • Geschwister
  • Ebene des Knotens
  • Elternteil
  • Wurzel
  • Etc.

Es besteht auch die Möglichkeit, eine flache Liste von Elementen mit einer ID und einer ParentId in einen Baum zu konvertieren. Die Knoten enthalten einen Verweis sowohl auf die untergeordneten als auch auf die übergeordneten Knoten, sodass iterierende Knoten sehr schnell ausgeführt werden können.

Alex Siepman
quelle
2

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 a SortedSet , der einen Rot-Schwarz-Baum implementiert:

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

Dies ist jedoch eine ausgeglichene Baumstruktur. Meine Antwort bezieht sich also eher auf die meiner Meinung nach einzige native Baumstruktur in der .net-Kernbibliothek.

Meirion Hughes
quelle
2

Ich habe den Code vervollständigt, den @Berezh geteilt 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;
        }
    }
Ashkan Sirous
quelle
Gutes Design. Ich bin mir jedoch nicht sicher, ob ein Knoten eine Folge seines untergeordneten Knotens ist. Ich würde Folgendes in Betracht ziehen: Ein Knoten hat null oder mehr untergeordnete Knoten, sodass ein Knoten nicht aus einer Folge von
untergeordneten
2

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"
        }
    };
Visar
quelle
1

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

Angenommen, Sie haben eine personKlasse, die Details zu einer Person enthält. Möchten parentsSie die Baumstruktur lieber als Teil Ihrer „Domänenklasse“ verwenden oder eine separate Baumklasse verwenden, die Links zu Ihren Personenobjekten enthält? Denken Sie über einen einfachen Vorgang wie immer alle grandchildrenvon ein person, soll dieser Code in der seine person Klasse, oder sollte der Benutzer der personKlasse hat über eine separaten Baum Klasse wissen?

Ein weiteres Beispiel ist ein Analysebaum in einem Compiler…

Beide Beispiele zeigen, dass das Konzept eines Baums Teil der Domäne der Daten ist und die Verwendung eines separaten Allzweckbaums mindestens die Anzahl der erstellten Objekte verdoppelt und die erneute Programmierung der API erschwert.

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.

Ian Ringrose
quelle
@Puchacz, tut mir leid, ich habe 15 Jahre keine Daten mehr zu C ++. Schauen Sie sich Boost und Vorlagen an. Nach ein paar schwachen Studien können Sie sie verstehen. Leistung hat hohe Lernkosten !!
Ian Ringrose
1

Ich habe eine vollständige Lösung und ein Beispiel mit der obigen NTree-Klasse hinzugefügt und auch die "AddChild" -Methode 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);
Dmitry
quelle
Sollte Traverse vielleicht eine statische Methode sein? Es scheint sehr umständlich zu sein, wenn eine Instanzmethode in sich selbst
übergeht
0

Hier ist meine Implementierung von BST

class BST
{
    public class Node
    {
        public Node Left { get; set; }
        public object Data { get; set; }
        public Node Right { get; set; }

        public Node()
        {
            Data = null;
        }

        public Node(int Data)
        {
            this.Data = (object)Data;
        }

        public void Insert(int Data)
        {
            if (this.Data == null)
            {
                this.Data = (object)Data;
                return;
            }
            if (Data > (int)this.Data)
            {
                if (this.Right == null)
                {
                    this.Right = new Node(Data);
                }
                else
                {
                    this.Right.Insert(Data);
                }
            }
            if (Data <= (int)this.Data)
            {
                if (this.Left == null)
                {
                    this.Left = new Node(Data);
                }
                else
                {
                    this.Left.Insert(Data);
                }
            }
        }

        public void TraverseInOrder()
        {
            if(this.Left != null)
                this.Left.TraverseInOrder();
            Console.Write("{0} ", this.Data);
            if (this.Right != null)
                this.Right.TraverseInOrder();
        }
    }

    public Node Root { get; set; }
    public BST()
    {
        Root = new Node();
    }
}

quelle
0

Wenn Sie diesen Baum auf der GUI anzeigen möchten , können Sie TreeView und TreeNode verwenden . (Ich nehme an, technisch gesehen können Sie einen TreeNode erstellen, ohne ihn auf einer GUI zu platzieren, aber er hat mehr Overhead als eine einfache selbst entwickelte TreeNode-Implementierung.)

Denise Skidmore
quelle
-4

Wenn Sie eine Implementierung einer verwurzelten Baumdatenstruktur benötigen, die weniger Speicher benötigt, können Sie Ihre Node-Klasse wie folgt schreiben (C ++ - Implementierung):

class Node {
       Node* parent;
       int item; // depending on your needs

       Node* firstChild; //pointer to left most child of node
       Node* nextSibling; //pointer to the sibling to the right
}
Jake
quelle
12
Es ist nicht die beste Idee, C ++ - Code für eine Frage speziell für C # zu veröffentlichen, Jake. Besonders eine, die Zeiger enthält. Sie wissen, dass Zeiger in C # gnadenlos aufgespürt werden, oder? : p
ThunderGr
2
@ThunderGr das ist nicht fair. Das Antworten in C # wäre besser gewesen, aber diese C ++ - Zeiger können von C # -Sprechern als Referenzen verstanden werden (sie sind weniger sicher, ok). Nachdem David Boike, Aaron Gage, Ronnie Overby, Grzegorz Dev, Berezh und Erik Nagel im Wesentlichen dieselbe Datenstruktur mit geringfügigen Unterschieden nur im Ausdruck vorgeschlagen hatten, schlug Jake vor, die verknüpfte Liste aufzuschlüsseln, was zu einfacheren Strukturen mit nur einem Knotentyp und führte Geschwisternavigierbarkeit. Drücken Sie Ihre Abneigung gegen C ++ nicht aus, indem Sie eine konstruktive Antwort ablehnen.
Migle
3
@migle Ich habe die Antwort nicht abgelehnt (auch nicht positiv bewertet). Und ich mag C ++ nicht. Ich sah, dass die Antwort abgelehnt wurde, ohne dass jemand Jake etwas darüber vorschlug, warum und wie er seine Antwort verbessern würde. Es geht nicht darum, "besser zu sein". Die Frage ist nur für C # markiert. Das Posten von Antworten in einer anderen Sprache als dem Tag wird nicht empfohlen, und einige Leute stimmen ab.
ThunderGr