Struktura danych drzewa w C #

Szukałem struktury danych drzewa lub wykresu w języku C #, ale chyba nie ma takiej. Wyczerpujące badanie struktur danych za pomocą C # 2.0 wyjaśnia nieco dlaczego. Czy istnieje wygodna biblioteka, która jest powszechnie używana do zapewnienia tej funkcjonalności? Być może poprzez strategię rozwiązywania problemów przedstawionych w artykule.

Czuję się trochę głupio, wdrażając własne drzewo, podobnie jak implementuję własną ArrayList.

Chcę tylko ogólne drzewo, które może być niezrównoważone. Pomyśl o drzewie katalogów. C5 wygląda sprytnie, ale ich struktury drzew wydają się być zaimplementowane jako zrównoważone czerwono-czarne drzewa lepiej nadające się do wyszukiwania niż reprezentujące hierarchię węzłów.

Moja najlepsza rada byłaby taka, że ​​nie ma standardowej struktury danych drzewa, ponieważ istnieje tak wiele sposobów jej implementacji, że niemożliwe byłoby objęcie wszystkich baz jednym rozwiązaniem. Im bardziej konkretne rozwiązanie, tym mniej prawdopodobne, że będzie ono miało zastosowanie do danego problemu. Denerwuje mnie nawet LinkedList - co jeśli chcę okrągłej listy łączy?

Podstawową strukturą, którą musisz zaimplementować, będzie kolekcja węzłów, a oto kilka opcji na dobry początek. Załóżmy, że węzeł klasy jest klasą bazową całego rozwiązania.

Jeśli potrzebujesz tylko nawigować w dół drzewa, klasa Node potrzebuje listy dzieci.

Jeśli potrzebujesz nawigować w górę drzewa, klasa Node potrzebuje łącza do swojego węzła nadrzędnego.

Zbuduj metodę AddChild, która zajmie się wszystkimi szczegółami tych dwóch punktów i wszelkimi innymi logikami biznesowymi, które muszą zostać zaimplementowane (limity potomne, sortowanie dzieci itp.)

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

Prosta rekurencyjna implementacja ... <40 linii kodu ... Musisz tylko zachować odniesienie do katalogu głównego drzewa poza klasą lub zawinąć w inną klasę, może zmienić nazwę na TreeNode?

Oto moja, bardzo podobna do Aarona Gage'a , moim zdaniem nieco bardziej konwencjonalna. Dla moich celów nie napotkałem żadnych problemów z wydajnością List<T>. W razie potrzeby przejście do LinkedList byłoby łatwe.

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

Jeszcze inna struktura drzewa:

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
}

Przykładowe użycie:

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
Zobacz pełne drzewo z:

• iterator
• badawczy
• Java / C #

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

Ogólnie doskonała ogólna biblioteka kolekcji C5 ma kilka różnych struktur danych opartych na drzewach, w tym zestawy, torby i słowniki. Kod źródłowy jest dostępny, jeśli chcesz przestudiować szczegóły jego implementacji. (Użyłem kolekcji C5 w kodzie produkcyjnym z dobrymi wynikami, chociaż nie użyłem żadnej konkretnej struktury drzewa).

Zobacz http://quickgraph.codeplex.com/

QuickGraph zapewnia ogólne struktury danych i algorytmy ukierunkowanych / niekierowanych grafów dla .Net 2.0 i wyższych. QuickGraph jest wyposażony w algorytmy, takie jak głębokość pierwszego wyszukiwania, pierwsze wyszukiwanie oddechu, wyszukiwanie A *, najkrótsza ścieżka, k-najkrótsza ścieżka, maksymalny przepływ, minimalne drzewo opinające, najmniej powszechni przodkowie itp. QuickGraph obsługuje MSAGL, GLEE i Graphviz do renderuj wykresy, serializację do GraphML itp.

Jeśli chcesz napisać własny, możesz zacząć od tego sześcioczęściowego dokumentu szczegółowo opisującego efektywne wykorzystanie struktur danych C # 2.0 i jak zacząć analizować implementację struktur danych w C #. Każdy artykuł zawiera przykłady i instalatora z przykładami, które możesz śledzić.

„Wszechstronne badanie struktur danych za pomocą C # 2.0” Scott Mitchell

Mam małe rozszerzenie do rozwiązań.

Korzystając z rekurencyjnej deklaracji ogólnej i pochodnej podklasy, możesz lepiej skoncentrować się na rzeczywistym celu.

Zauważ, że różni się od implementacji innej niż ogólna, nie musisz rzutować „node” w „NodeWorker”.

Oto mój przykład:

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

Oto moje własne:

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

Wynik:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Wypróbuj tę prostą próbkę.

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
}

Tworzę klasę Node, która może być pomocna dla innych osób. Klasa ma właściwości takie jak:

• Dzieci
• Przodkowie
• Potomków
• Rodzeństwo
• Poziom węzła
• Rodzic
• Korzeń
• Itp.

Istnieje również możliwość przekonwertowania płaskiej listy elementów o Id i ParentId na drzewo. Węzły zawierają odniesienie zarówno do dzieci, jak i rodzica, dzięki czemu iteracja węzłów jest dość szybka.

Ponieważ nie wspomniano o tym, chciałbym zwrócić uwagę na uwolnioną teraz bazę kodu .net: w szczególności kod dla SortedSetimplementacji Red-Black-Tree:

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

Jest to jednak zrównoważona struktura drzewa. Więc moja odpowiedź jest bardziej odniesieniem do tego, co uważam za jedyną natywną strukturę drzewa w bibliotece rdzenia .net.

Ukończyłem kod udostępniony przez @Berezh.

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

Oto drzewo

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

Możesz nawet użyć inicjatorów:

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

Większość drzew składa się z przetwarzanych danych.

Powiedzmy, że masz personklasę, która zawiera szczegóły czyjejś osoby parents, czy wolałbyś raczej mieć strukturę drzewa jako część „klasy domeny”, czy użyć osobnej klasy drzewa, która zawierała linki do obiektów twojej osoby? Pomyśl o prostej operacji jak dostaję cały grandchildrentematyce person, powinno to być kod w person klasie, czy też użytkownik personklasie muszą wiedzieć o osobnej klasy drzewa?

Innym przykładem jest parsowanie drzewa w kompilatorze…

Oba te przykłady pokazują, że koncepcja drzewa jest częścią domeny danych, a użycie osobnego drzewa ogólnego przeznaczenia co najmniej podwaja liczbę tworzonych obiektów, a także utrudnia programowanie interfejsu API.

Chcemy sposobu ponownego wykorzystania standardowych operacji na drzewach, bez konieczności ich ponownego wdrażania dla wszystkich drzew, przy jednoczesnym braku konieczności używania standardowej klasy drzewa. Boost próbował rozwiązać ten problem w C ++, ale jeszcze nie widziałem żadnego efektu dla .NET.

Dodałem kompletne rozwiązanie i przykład, używając klasy NTree powyżej, dodałem również metodę „AddChild” ...

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

za pomocą

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

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

Jeśli zamierzasz wyświetlić to drzewo w GUI, możesz użyć TreeView i TreeNode . (Podejrzewam, że technicznie można utworzyć TreeNode bez nakładania go na GUI, ale ma on większy narzut niż prosta implementacja TreeNode u siebie).

Jeśli potrzebujesz implementacji struktury danych zrootowanych drzew, która zużywa mniej pamięci, możesz napisać klasę Node w następujący sposób (implementacja C ++):

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
}