Struktura danych drzewa w C#

Przykro mi to przyznać, ale skończyło się na pisaniu własnej klasy drzewa za pomocą linked list. Na niezwiązanej uwadze właśnie odkryłem tę okrągłą rzecz, która po przymocowaniu do rzeczy, którą nazywam "osią", pozwala na łatwiejszy transport towarów.

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...

Oto mój, który jest bardzo podobny do Aarona Gage ' a , tylko trochę bardziej konwencjonalny, moim zdaniem. Dla moich celów, nie napotkałem żadnych problemów z wydajnością List<T>. W razie potrzeby łatwo byłoby przełączyć się na 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()));
        }
    }
}

Jeszcze jedna 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łnowartościowe drzewo z:

• iterator
• wyszukiwanie
• Java / C #

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

The General excellent C5 Generic Collection Library ma kilka różnych struktur danych opartych na drzewie, w tym zestawy, torby i słowniki. Kod źródłowy jest dostępny, jeśli chcesz przestudiować szczegóły ich implementacji. (Użyłem kolekcji C5 w kodzie produkcyjnym z dobrymi wynikami, chociaż nie użyłem żadnej ze struktur drzewa konkretnie.)

Zobacz http://quickgraph.codeplex.com/

QuickGraph dostarcza generyczne, kierowane/nieskierowane struktury danych grafu i algorytmy dla.Net 2.0 i nowszych. QuickGraph jest wyposażony w algorytmy takie jak głębokość pierwszego seach, oddech pierwsze wyszukiwanie, a * Wyszukiwanie, najkrótsza ścieżka, K-najkrótsza ścieżka, maksymalny przepływ, Minimalne drzewo rozpiętości, najmniej wspólnych przodków, itp... QuickGraph obsługuje MSAGL, GLEE i Graphviz do renderowania Wykresów, serializacji do GraphML, itp...

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

"w 2004 roku, w ramach projektu, w ramach projektu, została wydana wersja C# 2.0.]}

Mam małe rozszerzenie do rozwiązań.

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

Zauważ, że różni się ona od implementacji niestandardowej, nie musisz dodawać 'node' do '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);  
}  

Spróbuj tej prostej próbki.

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ę węzłów , która może być pomocna dla innych ludzi. Klasa ma takie właściwości jak:

• dzieci
• przodkowie
• potomkowie
• rodzeństwo
• Poziom węzła
• rodzic
• Root
• itd.

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

Ponieważ nie jest to wymienione chciałbym zwrócić uwagę na teraz wydany. NET code-base: konkretnie kod dla SortedSet, który implementuje Red-Black-Tree:

Https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs{[5]

Uzupełniłem kod, który udostępnił @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ć inicjalizatorów:

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

Większość drzew jest tworzona przez dane, które przetwarzasz.

Powiedzmy, że masz person klasę, która zawiera szczegóły czyjejś parents, Czy wolisz mieć strukturę drzewa jako część swojej "domain class", lub użyć oddzielnej klasy drzewa, która zawierała linki do twoja osoba się sprzeciwia? Pomyśl o prostej operacji, takiej jak uzyskanie wszystkich {[2] } z person, Czy ten kod powinien być w person klasy, czy użytkownik klasy person powinien wiedzieć o osobne drzewo zajęcia?

Innym przykładem jest drzewo parsowania w kompilatorze ...

Oba te przykłady pokazują, że pojęcie drzewa jest częścią domeny danych i użycie oddzielnego drzewa ogólnego przeznaczenia przynajmniej podwaja liczbę utworzonych obiektów, a także utrudnia ponowne zaprogramowanie API.

Chcemy sposobu na ponowne wykorzystanie standardowych operacji na drzewie, bez konieczności ponownego implementowania ich dla wszystkich drzew, a jednocześnie bez konieczności aby użyć standardowej klasy drzewa. Boost próbował rozwiązać tego typu problem dla C++, ale jeszcze nie widzę żadnego efektu dla. NET get adapted.

Dodałem kompletne rozwiązanie i przykład używając powyższej klasy NTree, 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;
        }
    }

Użycie

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

Oto mój własny:

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

Wyjście:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Jeśli chcesz wyświetlić to drzewo w GUI, możesz użyć TreeView i TreeNode. (Przypuszczam, że technicznie można utworzyć TreeNode bez umieszczania go na GUI, ale ma on więcej kosztów niż zwykła implementacja TreeNode.)

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 potrzebujesz implementacji struktury danych drzewa rooted, która zużywa mniej pamięci, możesz napisać klasę węzła 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
}