Boom datastructuur in C#

Ik was op zoek naar een boom- of grafiekgegevensstructuur in C#, maar ik vermoed dat die er niet is. Een uitgebreid onderzoek van gegevensstructuren met C# 2.0legt een beetje uit waarom. Is er een handige bibliotheek die vaak wordt gebruikt om deze functionaliteit te bieden? Misschien door een strategiepatroon om de problemen in het artikel op te lossen.

Ik voel me een beetje dom om mijn eigen boom te implementeren, net zoals ik mijn eigen ArrayList zou implementeren.

Ik wil gewoon een generieke boom die uit balans kan zijn. Denk aan een mappenboom. C5 ziet er handig uit, maar hun boomstructuren lijken te zijn geïmplementeerd als uitgebalanceerde rood-zwarte bomen die beter geschikt zijn om te zoeken dan een hiërarchie van knooppunten te vertegenwoordigen.

Antwoord 1, autoriteit 100%

Mijn beste advies zou zijn dat er geen standaard boomdatastructuur is, omdat er zoveel manieren zijn waarop je het zou kunnen implementeren dat het onmogelijk zou zijn om alle bases te dekken met één oplossing. Hoe specifieker een oplossing, hoe kleiner de kans dat deze op een bepaald probleem van toepassing is. Ik erger me zelfs aan LinkedList – wat als ik een circulaire gekoppelde lijst wil?

De basisstructuur die u moet implementeren, is een verzameling knooppunten, en hier zijn enkele opties om u op weg te helpen. Laten we aannemen dat de klasse Node de basisklasse is van de hele oplossing.

Als u alleen door de boom hoeft te navigeren, heeft een Node-klasse een lijst met kinderen nodig.

Als u omhoog in de boomstructuur moet navigeren, heeft de Node-klasse een link naar het bovenliggende knooppunt nodig.

Bouw een AddChild-methode die zorgt voor alle details van deze twee punten en alle andere bedrijfslogica die moet worden geïmplementeerd (onderliggende limieten, sorteren van de kinderen, enz.)

Antwoord 2, autoriteit 77%

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

Eenvoudige recursieve implementatie …
& LT; 40 regels code …
Je hoeft alleen maar een verwijzing te houden naar de wortel van de boom buiten de klas,
of wikkel het in een andere klas, misschien hernoemen naar treenode ??

3, Autoriteit 39%

Hier is de mijne, die erg lijkt op Aaron Gage’s , slechts een beetje conventioneel, naar mijn mening. Voor mijn doeleinden heb ik geen prestatieproblemen met List<T>. Het zou gemakkelijk genoeg zijn om indien nodig over te schakelen naar een Linkedlist.

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

4, Autoriteit 31%

Nog een andere boomstructuur:

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
}

Voorbeeld van gebruik:

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
Zie volwaardige boom met:

• iterator
• zoeken
• Java/C#

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

Antwoord 5, autoriteit 14%

De over het algemeen uitstekende C5 Generic Collection Libraryheeft verschillende op boom gebaseerde datastructuren, waaronder sets, tassen en woordenboeken. Broncode is beschikbaar als u hun implementatiedetails wilt bestuderen. (Ik heb C5-verzamelingen in productiecode met goede resultaten gebruikt, hoewel ik geen van de boomstructuren specifiek heb gebruikt.)

Antwoord 6, autoriteit 7%

Zie http://quickgraph.codeplex.com/

QuickGraph biedt generieke gerichte/ongerichte grafische datastructuren en algoritmen voor .Net 2.0 en hoger. QuickGraph wordt geleverd met algoritmen zoals diepte eerst zoeken, eerst adem zoeken, A* zoeken, kortste pad, k-kortste pad, maximale stroom, minimale opspannende boom, minst gemeenschappelijke voorouders, enz… QuickGraph ondersteunt MSAGL, GLEE en Graphviz om render de grafieken, serialisatie naar GraphML, enz…

Antwoord 7, autoriteit 5%

Als u uw eigen gegevens wilt schrijven, kunt u beginnen met dit zesdelige document waarin het effectieve gebruik van C# 2.0-gegevensstructuren wordt beschreven en hoe u uw implementatie van gegevensstructuren in C# kunt analyseren. Elk artikel heeft voorbeelden en een installatieprogramma met voorbeelden die u kunt volgen.

“Een uitgebreid onderzoek van gegevensstructuren met C# 2.0” door Scott Mitchell

Antwoord 8, autoriteit 5%

Ik heb een kleine uitbreiding van de oplossingen.

Met behulp van een recursieve generieke declaratie en een afgeleide subklasse kunt u zich beter concentreren op uw werkelijke doel.

Let op, het is anders dan een niet-generieke implementatie, u hoeft ‘node’ niet in ‘NodeWorker’ te casten.

Dit is mijn voorbeeld:

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

9, Autoriteit 5%

Hier is mijn eigen:

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

Uitvoer:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Antwoord 10, autoriteit 2%

Probeer dit eenvoudige voorbeeld.

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
}

Antwoord 11

Ik maak een Node klassedie nuttig kan zijn voor andere mensen. De klasse heeft eigenschappen zoals:

• Kinderen
• Voorouders
• Afstammelingen
• Broers en zussen
• Niveau van het knooppunt
• Ouder
• Root
• Enz.

Er is ook de mogelijkheid om een platte lijst van items met een Id en een ParentId om te zetten naar een boom. De knooppunten bevatten een verwijzing naar zowel de kinderen als de bovenliggende, dus dat maakt het herhalen van knooppunten vrij snel.

Antwoord 12

Omdat het niet wordt genoemd, zou ik graag willen dat u de nu vrijgegeven .net code-base onder de aandacht brengt: specifiek de code voor een SortedSetdie een Red-Black-Tree implementeert:

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

Dit is echter een uitgebalanceerde boomstructuur. Dus mijn antwoord is meer een verwijzing naar wat volgens mij de enige native boomstructuur is in de .net-kernbibliotheek.

Antwoord 13

Ik heb de code voltooid die @Berezh heeft gedeeld.

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

14

Ik heb volledige oplossing toegevoegd en voorbeeld met Ntree-klasse hierboven, ook “Addchild” -methode toegevoegd …

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

met

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

Antwoord 15

Het verbaast me dat niemand de mogelijkheid noemde om XML te gebruiken met Linq :

https://docs.microsoft.com /fr-fr/dotnet/standard/linq/create-xml-trees

XML is de meest volwassen en flexibele oplossing als het gaat om het gebruik van bomen en Linq biedt je alle tools die je nodig hebt.
De configuratie van uw boomstructuur wordt ook veel schoner en gebruiksvriendelijker omdat u eenvoudig een XML-bestand kunt gebruiken voor de initialisatie.

Als u met objecten moet werken, kunt u XML-serialisatie gebruiken:

https://docs.microsoft.com /fr-fr/dotnet/standard/serialisatie/introducing-xml-serialisatie

Antwoord 16

Hier is mijn implementatie van 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();
    }
}

17

Als u deze boom op de GUI gaat weergeven, kunt u TreeView en treenode . (Ik veronderstel dat u technisch gezien een treenode kunt maken zonder het op een GUI te plaatsen, maar het heeft meer overhead dan een eenvoudige implementatie van de TRIODEODE.)

18

Boom met generieke gegevens

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
public class Tree<T>
{
    public T Data { get; set; }
    public LinkedList<Tree<T>> Children { get; set; } = new LinkedList<Tree<T>>();
    public Task Traverse(Func<T, Task> actionOnNode, int maxDegreeOfParallelism = 1) => Traverse(actionOnNode, new SemaphoreSlim(maxDegreeOfParallelism, maxDegreeOfParallelism));
    private async Task Traverse(Func<T, Task> actionOnNode, SemaphoreSlim semaphore)
    {
        await actionOnNode(Data);
        SafeRelease(semaphore);
        IEnumerable<Task> tasks = Children.Select(async input =>
        {
            await semaphore.WaitAsync().ConfigureAwait(false);
            try
            {
                await input.Traverse(actionOnNode, semaphore).ConfigureAwait(false);
            }
            finally
            {
                SafeRelease(semaphore);
            }
        });
        await Task.WhenAll(tasks);
    }
    private void SafeRelease(SemaphoreSlim semaphore)
    {
        try
        {
            semaphore.Release();
        }
        catch (Exception ex)
        {
            if (ex.Message.ToLower() != "Adding the specified count to the semaphore would cause it to exceed its maximum count.".ToLower())
            {
                throw;
            }
        }
    }
    public async Task<IEnumerable<T>> ToList()
    {
        ConcurrentBag<T> lst = new ConcurrentBag<T>();
        await Traverse(async (data) => lst.Add(data));
        return lst;
    }
    public async Task<int> Count() => (await ToList()).Count();
}

Eenheidstests

using System.Threading.Tasks;
using Xunit;
public class Tree_Tests
{
    [Fact]
    public async Task Tree_ToList_Count()
    {
        Tree<int> head = new Tree<int>();
        Assert.NotEmpty(await head.ToList());
        Assert.True(await head.Count() == 1);
        // child
        var child = new Tree<int>();
        head.Children.AddFirst(child);
        Assert.True(await head.Count() == 2);
        Assert.NotEmpty(await head.ToList());
        // grandson
        child.Children.AddFirst(new Tree<int>());
        child.Children.AddFirst(new Tree<int>());
        Assert.True(await head.Count() == 4);
        Assert.NotEmpty(await head.ToList());
    }
    [Fact]
    public async Task Tree_Traverse()
    {
        Tree<int> head = new Tree<int>() { Data = 1 };
        // child
        var child = new Tree<int>() { Data = 2 };
        head.Children.AddFirst(child);
        // grandson
        child.Children.AddFirst(new Tree<int>() { Data = 3 });
        child.Children.AddLast(new Tree<int>() { Data = 4 });
        int counter = 0;
        await head.Traverse(async (data) => counter += data);
        Assert.True(counter == 10);
        counter = 0;
        await child.Traverse(async (data) => counter += data);
        Assert.True(counter == 9);
        counter = 0;
        await child.Children.First!.Value.Traverse(async (data) => counter += data);
        Assert.True(counter == 3);
        counter = 0;
        await child.Children.Last!.Value.Traverse(async (data) => counter += data);
        Assert.True(counter == 4);
    }
}

Antwoord 19

In het geval dat u een geroote boomdatastructuur-implementatie nodig hebt die minder geheugen gebruikt, kunt u uw Node-klasse als volgt schrijven (C++-implementatie):

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
}