Tree data structure in C

Question

I was looking for a tree or graph data structure in C  but I guess there isn t one provided  An Extensive Examination of Data Structures Using C  2 0 explains a bit about why   Is there a convenient library which is commonly used to provide this functionality   Perhaps through a strategy pattern to solve the issues presented in the article   I feel a bit silly implementing my own tree  just as I would implementing my own ArrayList      I just want a generic tree which can be unbalanced   Think of a directory tree   C5 looks nifty  but their tree structures seem to be implemented as balanced red-black trees better suited to search than representing a hierarchy of nodes

User · Answer

The generally excellent C5 Generic Collection Library has several different tree-based data structures  including sets  bags and dictionaries  Source code is available if you want to study their implementation details   I have used C5 collections in production code with good results  although I haven t used any of the tree structures specifically

User · Answer

Yet another tree structure   public class TreeNode lt T gt    IEnumerable lt TreeNode lt T gt  gt         public T Data   get  set        public TreeNode lt T gt  Parent   get  set        public ICollection lt TreeNode lt T gt  gt  Children   get  set         public TreeNode T data                this Data   data          this Children   new LinkedList lt TreeNode lt T gt  gt                public TreeNode lt T gt  AddChild T child                TreeNode lt T gt  childNode   new TreeNode lt T gt  child    Parent   this            this Children Add childNode           return childNode                    for iterator details see below link     Sample usage   TreeNode lt string gt  root   new TreeNode lt string gt   root          TreeNode lt string gt  node0   root AddChild  node0        TreeNode lt string gt  node1   root AddChild  node1        TreeNode lt string gt  node2   root AddChild  node2                  TreeNode lt string gt  node20   node2 AddChild null           TreeNode lt string gt  node21   node2 AddChild  node21                          TreeNode lt string gt  node210   node21 AddChild  node210                TreeNode lt string gt  node211   node21 AddChild  node211                        TreeNode lt string gt  node3   root AddChild  node3                  TreeNode lt string gt  node30   node3 AddChild  node30              BONUS See fully-fledged tree with    iterator searching Java C    https   github com gt4dev yet-another-tree-structure

User · Answer

Here s my own   class Program       static void Main string   args                var tree   new Tree lt string gt                 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   gt  PrintNode p  0            Console ReadKey               static void PrintNode lt T gt  TreeNode lt T gt  node  int level                Console WriteLine   0  1    new string      level   3   node Value           level            node Children ForEach p   gt  PrintNode p  level             public class Tree lt T gt        private Stack lt TreeNode lt T gt  gt  m Stack   new Stack lt TreeNode lt T gt  gt          public List lt TreeNode lt T gt  gt  Nodes   get      new List lt TreeNode lt T gt  gt          public Tree lt T gt  Begin T val                if  m Stack Count    0                        var node   new TreeNode lt T gt  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 lt T gt  Add T val                m Stack Peek   Add val           return this             public Tree lt T gt  End                 m Stack Pop            return this           public class TreeNode lt T gt        public T Value   get        public TreeNode lt T gt  Parent   get        public List lt TreeNode lt T gt  gt  Children   get         public TreeNode T val  TreeNode lt T gt  parent                Value   val          Parent   parent          Children   new List lt TreeNode lt T gt  gt                public TreeNode lt T gt  Add T val                var node   new TreeNode lt T gt  val  this           Children Add node           return node            Output   Fastfood    Pizza       Margherita       Marinara    Burger       Cheese burger       Chili burger       Rice burger

User · Answer

The generally excellent C5 Generic Collection Library has several different tree-based data structures  including sets  bags and dictionaries  Source code is available if you want to study their implementation details   I have used C5 collections in production code with good results  although I haven t used any of the tree structures specifically

User · Answer

See http   quickgraph codeplex com   QuickGraph provides generic directed undirected graph datastructures and algorithms for  Net 2 0 and up  QuickGraph comes with algorithms such as depth first seach  breath first search  A  search  shortest path  k-shortest path  maximum flow  minimum spanning tree  least common ancestors  etc    QuickGraph supports MSAGL  GLEE  and Graphviz to render the graphs  serialization to GraphML  etc

User · Answer

Tree With Generic Data using System  using System Collections Concurrent  using System Collections Generic  using System Linq  using System Threading  using System Threading Tasks   public class Tree lt T gt        public T Data   get  set        public LinkedList lt Tree lt T gt  gt  Children   get  set      new LinkedList lt Tree lt T gt  gt         public Task Traverse Func lt T  Task gt  actionOnNode  int maxDegreeOfParallelism   1    gt  Traverse actionOnNode  new SemaphoreSlim maxDegreeOfParallelism  maxDegreeOfParallelism        private async Task Traverse Func lt T  Task gt  actionOnNode  SemaphoreSlim semaphore                await actionOnNode Data           SafeRelease semaphore           IEnumerable lt Task gt  tasks   Children Select async input   gt                        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       quot Adding the specified count to the semaphore would cause it to exceed its maximum count  quot  ToLower                                  throw                                     public async Task lt IEnumerable lt T gt  gt  ToList                 ConcurrentBag lt T gt  lst   new ConcurrentBag lt T gt             await Traverse async  data    gt  lst Add data            return lst            public async Task lt int gt  Count     gt   await ToList    Count          Unit Tests using System Threading Tasks  using Xunit   public class Tree Tests        Fact      public async Task Tree ToList Count                 Tree lt int gt  head   new Tree lt int gt              Assert NotEmpty await head ToList             Assert True await head Count      1               child         var child   new Tree lt int gt             head Children AddFirst child           Assert True await head Count      2           Assert NotEmpty await head ToList                 grandson         child Children AddFirst new Tree lt int gt              child Children AddFirst new Tree lt int gt              Assert True await head Count      4           Assert NotEmpty await head ToList                 Fact      public async Task Tree Traverse                 Tree lt int gt  head   new Tree lt int gt      Data   1                child         var child   new Tree lt int gt      Data   2            head Children AddFirst child               grandson         child Children AddFirst new Tree lt int gt      Data   3             child Children AddLast new Tree lt int gt      Data   4              int counter   0          await head Traverse async  data    gt  counter    data           Assert True counter    10            counter   0          await child Traverse async  data    gt  counter    data           Assert True counter    9            counter   0          await child Children First  Value Traverse async  data    gt  counter    data           Assert True counter    3            counter   0          await child Children Last  Value Traverse async  data    gt  counter    data           Assert True counter    4

User · Answer

If you would like to write your own  you can start with this six-part document detailing effective usage of C  2 0 data structures and how to go about analyzing your implementation of data structures in C   Each article has examples and an installer with samples you can follow along with      An Extensive Examination of Data Structures Using C  2 0    by Scott Mitchell

User · Answer

Most trees are formed by the data you are processing        Say you have a person class that includes details of someone   s   parents  would you rather have the tree structure as part of your      domain class     or use a separate tree class that contained links to   your person objects    Think about a simple operation like getting all   the grandchildren of a person  should this code be in the person   class  or should the user of the person class have to know about a   separate tree class    Another example is a parse tree in a compiler     What both of these examples show is that the concept of a tree is part of the domain of the data and using a separate general purpose tree at least doubles the number of objects that are created as well as making the API harder to program again   What we want is a way to reuse the standard tree operations  without having to re-implement them for all trees  while at the same time  not having to use a standard tree class    Boost has tried to solve this type of problem for C    but I yet to see any effect for  NET get adapted

User · Answer

I have a little extension to the solutions   Using a recursive generic declaration and a deriving subclass you can better concentrate on your actual target   Notice  it s different from a non generic implementation  you don t need to cast  node  in  NodeWorker     Here s my example   public class GenericTree lt T gt  where T   GenericTree lt T gt     recursive constraint          no specific data declaration      protected List lt T gt  children     public GenericTree           this children   new List lt T gt            public virtual void AddChild T newChild          this children Add newChild          public void Traverse Action lt int  T gt  visitor          this traverse 0  visitor          protected virtual void traverse int depth  Action lt int  T gt  visitor          visitor depth   T this       foreach  T child in this children        child traverse depth   1  visitor          public class GenericTreeNext   GenericTree lt GenericTreeNext gt     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

User · Answer

Because it isn t mentioned I would like you draw attention the now released  net code-base  specifically the code for a SortedSet that implements a Red-Black-Tree    https   github com Microsoft referencesource blob master System compmod system collections generic sortedset cs   This is  however  a balanced tree structure  So my answer is more a reference to what I believe is the only native tree-structure in the  net core library

User · Answer

Try this simple sample   public class TreeNode lt TValue gt         region Properties     public TValue Value   get  set        public List lt TreeNode lt TValue gt  gt  Children   get  private set        public bool HasChild   get   return Children Any             endregion      region Constructor     public TreeNode                 this Children   new List lt TreeNode lt TValue gt  gt               public TreeNode TValue value            this                 this Value   value             endregion      region Methods     public void AddChild TreeNode lt TValue gt  treeNode                Children Add treeNode             public void AddChild TValue value                var treeNode   new TreeNode lt TValue gt  value           AddChild treeNode              endregion

User · Answer

Here s a Tree public class Tree lt T gt    List lt Tree lt T gt  gt        public  T Data   get  private set         public Tree T data                this Data   data

User · Answer

If you would like to write your own  you can start with this six-part document detailing effective usage of C  2 0 data structures and how to go about analyzing your implementation of data structures in C   Each article has examples and an installer with samples you can follow along with      An Extensive Examination of Data Structures Using C  2 0    by Scott Mitchell

User · Answer

In case you need a rooted tree data structure implementation that uses less memory  you can write your Node class as follows  C   implementation    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

User · Answer

Try this simple sample   public class TreeNode lt TValue gt         region Properties     public TValue Value   get  set        public List lt TreeNode lt TValue gt  gt  Children   get  private set        public bool HasChild   get   return Children Any             endregion      region Constructor     public TreeNode                 this Children   new List lt TreeNode lt TValue gt  gt               public TreeNode TValue value            this                 this Value   value             endregion      region Methods     public void AddChild TreeNode lt TValue gt  treeNode                Children Add treeNode             public void AddChild TValue value                var treeNode   new TreeNode lt TValue gt  value           AddChild treeNode              endregion

User · Answer

Here s mine  which is very similar to Aaron Gage s  just a little more conventional  in my opinion  For my purposes  I haven t ran into any performance issues with List lt T gt   It would be easy enough to switch to a LinkedList if needed     namespace Overby Collections       public class TreeNode lt T gt                private readonly T  value          private readonly List lt TreeNode lt T gt  gt   children   new List lt TreeNode lt T gt  gt              public TreeNode T value                         value   value                     public TreeNode lt T gt  this int i                        get   return  children i                        public TreeNode lt T gt  Parent   get  private set             public T Value   get   return  value               public ReadOnlyCollection lt TreeNode lt T gt  gt  Children                       get   return  children AsReadOnly                         public TreeNode lt T gt  AddChild T value                        var node   new TreeNode lt T gt  value   Parent   this                children Add node               return node                     public TreeNode lt T gt    AddChildren params T   values                        return values Select AddChild  ToArray                       public bool RemoveChild TreeNode lt T gt  node                        return  children Remove node                      public void Traverse Action lt T gt  action                        action Value               foreach  var child in  children                  child Traverse action                      public IEnumerable lt T gt  Flatten                         return new    Value  Concat  children SelectMany x   gt  x Flatten

User · Answer

Because it isn t mentioned I would like you draw attention the now released  net code-base  specifically the code for a SortedSet that implements a Red-Black-Tree    https   github com Microsoft referencesource blob master System compmod system collections generic sortedset cs   This is  however  a balanced tree structure  So my answer is more a reference to what I believe is the only native tree-structure in the  net core library

User · Answer

I create a Node class that could be helpfull for other people  The class has properties like    Children Ancestors Descendants Siblings Level of the node Parent Root Etc    There is also the possibility to convert a flat list of items with an Id and a ParentId to a tree  The nodes holds a reference to both the children and the parent  so that makes iterating nodes quite fast

User · Answer

I ve completed the code that  Berezh has shared     public class TreeNode lt T gt    IEnumerable lt TreeNode lt T gt  gt                 public T Data   get  set            public TreeNode lt T gt  Parent   get  set            public ICollection lt TreeNode lt T gt  gt  Children   get  set             public TreeNode T data                        this Data   data              this Children   new LinkedList lt TreeNode lt T gt  gt                        public TreeNode lt T gt  AddChild T child                        TreeNode lt T gt  childNode   new TreeNode lt T gt  child    Parent   this                this Children Add childNode               return childNode                     public IEnumerator lt TreeNode lt T gt  gt  GetEnumerator                         throw new NotImplementedException                       IEnumerator IEnumerable GetEnumerator                         return  IEnumerator GetEnumerator                        public class TreeNodeEnum lt T gt    IEnumerator lt TreeNode lt T gt  gt                 int position   -1          public List lt TreeNode lt T gt  gt  Nodes   get  set             public TreeNode lt T gt  Current                       get                               try                                       return Nodes position                                     catch  IndexOutOfRangeException                                        throw new InvalidOperationException                                                        object IEnumerator Current                       get                               return Current                                    public TreeNodeEnum List lt TreeNode lt T gt  gt  nodes                        Nodes   nodes                     public void Dispose                                public bool MoveNext                         position                return  position  lt  Nodes Count                      public void Reset                         position   -1

User · Answer

If you would like to write your own  you can start with this six-part document detailing effective usage of C  2 0 data structures and how to go about analyzing your implementation of data structures in C   Each article has examples and an installer with samples you can follow along with      An Extensive Examination of Data Structures Using C  2 0    by Scott Mitchell

User · Answer

My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution   The more specific a solution  the less likely it is applicable to any given problem   I even get annoyed with LinkedList - what if I want a circular linked list   The basic structure you ll need to implement will be a collection of nodes  and here are some options to get you started   Let s assume that the class Node is the base class of the entire solution   If you need to only navigate down the tree  then a Node class needs a List of children   If you need to navigate up the tree  then the Node class needs a link to its parent node   Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented  child limits  sorting the children  etc

User · Answer

My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution   The more specific a solution  the less likely it is applicable to any given problem   I even get annoyed with LinkedList - what if I want a circular linked list   The basic structure you ll need to implement will be a collection of nodes  and here are some options to get you started   Let s assume that the class Node is the base class of the entire solution   If you need to only navigate down the tree  then a Node class needs a List of children   If you need to navigate up the tree  then the Node class needs a link to its parent node   Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented  child limits  sorting the children  etc

User · Answer

My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution   The more specific a solution  the less likely it is applicable to any given problem   I even get annoyed with LinkedList - what if I want a circular linked list   The basic structure you ll need to implement will be a collection of nodes  and here are some options to get you started   Let s assume that the class Node is the base class of the entire solution   If you need to only navigate down the tree  then a Node class needs a List of children   If you need to navigate up the tree  then the Node class needs a link to its parent node   Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented  child limits  sorting the children  etc

User · Answer

delegate void TreeVisitor lt T gt  T nodeData    class NTree lt T gt        private T data      private LinkedList lt NTree lt T gt  gt  children       public NTree T data                 this data   data          children   new LinkedList lt NTree lt T gt  gt                public void AddChild T data                children AddFirst new NTree lt T gt  data               public NTree lt T gt  GetChild int i                foreach  NTree lt T gt  n in children              if  --i    0                  return n          return null             public void Traverse NTree lt T gt  node  TreeVisitor lt T gt  visitor                visitor node data           foreach  NTree lt T gt  kid in node children              Traverse kid  visitor             Simple recursive implementation     lt  40 lines of code    You just need to keep a reference to the root of the tree outside of the class  or wrap it in another class  maybe rename to TreeNode

User · Answer

I am surprised nobody mentioned the possibility to use XML with Linq   https   docs microsoft com fr-fr dotnet standard linq create-xml-trees XML is the most mature and flexible solution when it comes to using trees and Linq provides you with all the tools that you need  The configuration of your tree also gets much cleaner and user-friendly as you can simply use an XML file for the initialization  If you need to work with objects  you can use XML serialization   https   docs microsoft com fr-fr dotnet standard serialization introducing-xml-serialization

User · Answer

Here is my implementation of 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  gt   int this Data                                if  this Right    null                                        this Right   new Node Data                                     else                                       this Right Insert Data                                               if  Data  lt    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

User · Answer

Yet another tree structure   public class TreeNode lt T gt    IEnumerable lt TreeNode lt T gt  gt         public T Data   get  set        public TreeNode lt T gt  Parent   get  set        public ICollection lt TreeNode lt T gt  gt  Children   get  set         public TreeNode T data                this Data   data          this Children   new LinkedList lt TreeNode lt T gt  gt                public TreeNode lt T gt  AddChild T child                TreeNode lt T gt  childNode   new TreeNode lt T gt  child    Parent   this            this Children Add childNode           return childNode                    for iterator details see below link     Sample usage   TreeNode lt string gt  root   new TreeNode lt string gt   root          TreeNode lt string gt  node0   root AddChild  node0        TreeNode lt string gt  node1   root AddChild  node1        TreeNode lt string gt  node2   root AddChild  node2                  TreeNode lt string gt  node20   node2 AddChild null           TreeNode lt string gt  node21   node2 AddChild  node21                          TreeNode lt string gt  node210   node21 AddChild  node210                TreeNode lt string gt  node211   node21 AddChild  node211                        TreeNode lt string gt  node3   root AddChild  node3                  TreeNode lt string gt  node30   node3 AddChild  node30              BONUS See fully-fledged tree with    iterator searching Java C    https   github com gt4dev yet-another-tree-structure

User · Answer

I am surprised nobody mentioned the possibility to use XML with Linq   https   docs microsoft com fr-fr dotnet standard linq create-xml-trees XML is the most mature and flexible solution when it comes to using trees and Linq provides you with all the tools that you need  The configuration of your tree also gets much cleaner and user-friendly as you can simply use an XML file for the initialization  If you need to work with objects  you can use XML serialization   https   docs microsoft com fr-fr dotnet standard serialization introducing-xml-serialization

User · Answer

The generally excellent C5 Generic Collection Library has several different tree-based data structures  including sets  bags and dictionaries  Source code is available if you want to study their implementation details   I have used C5 collections in production code with good results  although I haven t used any of the tree structures specifically

User · Answer

If you are going to display this tree on the GUI  you can use TreeView and TreeNode    I suppose technically you can create a TreeNode without putting it on a GUI  but it does have more overhead than a simple homegrown TreeNode implementation

User · Answer

My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution   The more specific a solution  the less likely it is applicable to any given problem   I even get annoyed with LinkedList - what if I want a circular linked list   The basic structure you ll need to implement will be a collection of nodes  and here are some options to get you started   Let s assume that the class Node is the base class of the entire solution   If you need to only navigate down the tree  then a Node class needs a List of children   If you need to navigate up the tree  then the Node class needs a link to its parent node   Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented  child limits  sorting the children  etc

User · Answer

If you are going to display this tree on the GUI  you can use TreeView and TreeNode    I suppose technically you can create a TreeNode without putting it on a GUI  but it does have more overhead than a simple homegrown TreeNode implementation

User · Answer

In case you need a rooted tree data structure implementation that uses less memory  you can write your Node class as follows  C   implementation    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

User · Answer

I have added complete solution and example using NTree class above  also added  AddChild  method         public class NTree lt T gt                public T data          public LinkedList lt NTree lt T gt  gt  children           public NTree T data                        this data   data              children   new LinkedList lt NTree lt T gt  gt                        public void AddChild T data                        var node   new NTree lt T gt  data    Parent   this                children AddFirst node                      public NTree lt T gt  Parent   get  private set             public NTree lt T gt  GetChild int i                        foreach  NTree lt T gt  n in children                  if  --i    0                      return n              return null                     public void Traverse NTree lt T gt  node  TreeVisitor lt T gt  visitor  string t  ref NTree lt T gt  r                        visitor node data  node  t  ref r               foreach  NTree lt T gt  kid in node children                  Traverse kid  visitor  t  ref r                       public static void DelegateMethod KeyValuePair lt string  string gt  data  NTree lt KeyValuePair lt string  string gt  gt  node  string t  ref NTree lt KeyValuePair lt string  string gt  gt  r                string a   string Empty          if  node data Key    t                        r   node              return                    using   NTree lt KeyValuePair lt string  string gt  gt  ret   null   tree Traverse tree  DelegateMethod  node  categoryId   InnerText  ref ret

User · Answer

See http   quickgraph codeplex com   QuickGraph provides generic directed undirected graph datastructures and algorithms for  Net 2 0 and up  QuickGraph comes with algorithms such as depth first seach  breath first search  A  search  shortest path  k-shortest path  maximum flow  minimum spanning tree  least common ancestors  etc    QuickGraph supports MSAGL  GLEE  and Graphviz to render the graphs  serialization to GraphML  etc

User · Answer

I create a Node class that could be helpfull for other people  The class has properties like    Children Ancestors Descendants Siblings Level of the node Parent Root Etc    There is also the possibility to convert a flat list of items with an Id and a ParentId to a tree  The nodes holds a reference to both the children and the parent  so that makes iterating nodes quite fast

User · Answer

Tree With Generic Data using System  using System Collections Concurrent  using System Collections Generic  using System Linq  using System Threading  using System Threading Tasks   public class Tree lt T gt        public T Data   get  set        public LinkedList lt Tree lt T gt  gt  Children   get  set      new LinkedList lt Tree lt T gt  gt         public Task Traverse Func lt T  Task gt  actionOnNode  int maxDegreeOfParallelism   1    gt  Traverse actionOnNode  new SemaphoreSlim maxDegreeOfParallelism  maxDegreeOfParallelism        private async Task Traverse Func lt T  Task gt  actionOnNode  SemaphoreSlim semaphore                await actionOnNode Data           SafeRelease semaphore           IEnumerable lt Task gt  tasks   Children Select async input   gt                        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       quot Adding the specified count to the semaphore would cause it to exceed its maximum count  quot  ToLower                                  throw                                     public async Task lt IEnumerable lt T gt  gt  ToList                 ConcurrentBag lt T gt  lst   new ConcurrentBag lt T gt             await Traverse async  data    gt  lst Add data            return lst            public async Task lt int gt  Count     gt   await ToList    Count          Unit Tests using System Threading Tasks  using Xunit   public class Tree Tests        Fact      public async Task Tree ToList Count                 Tree lt int gt  head   new Tree lt int gt              Assert NotEmpty await head ToList             Assert True await head Count      1               child         var child   new Tree lt int gt             head Children AddFirst child           Assert True await head Count      2           Assert NotEmpty await head ToList                 grandson         child Children AddFirst new Tree lt int gt              child Children AddFirst new Tree lt int gt              Assert True await head Count      4           Assert NotEmpty await head ToList                 Fact      public async Task Tree Traverse                 Tree lt int gt  head   new Tree lt int gt      Data   1                child         var child   new Tree lt int gt      Data   2            head Children AddFirst child               grandson         child Children AddFirst new Tree lt int gt      Data   3             child Children AddLast new Tree lt int gt      Data   4              int counter   0          await head Traverse async  data    gt  counter    data           Assert True counter    10            counter   0          await child Traverse async  data    gt  counter    data           Assert True counter    9            counter   0          await child Children First  Value Traverse async  data    gt  counter    data           Assert True counter    3            counter   0          await child Children Last  Value Traverse async  data    gt  counter    data           Assert True counter    4

User · Answer

delegate void TreeVisitor lt T gt  T nodeData    class NTree lt T gt        private T data      private LinkedList lt NTree lt T gt  gt  children       public NTree T data                 this data   data          children   new LinkedList lt NTree lt T gt  gt                public void AddChild T data                children AddFirst new NTree lt T gt  data               public NTree lt T gt  GetChild int i                foreach  NTree lt T gt  n in children              if  --i    0                  return n          return null             public void Traverse NTree lt T gt  node  TreeVisitor lt T gt  visitor                visitor node data           foreach  NTree lt T gt  kid in node children              Traverse kid  visitor             Simple recursive implementation     lt  40 lines of code    You just need to keep a reference to the root of the tree outside of the class  or wrap it in another class  maybe rename to TreeNode

User · Answer

I have added complete solution and example using NTree class above  also added  AddChild  method         public class NTree lt T gt                public T data          public LinkedList lt NTree lt T gt  gt  children           public NTree T data                        this data   data              children   new LinkedList lt NTree lt T gt  gt                        public void AddChild T data                        var node   new NTree lt T gt  data    Parent   this                children AddFirst node                      public NTree lt T gt  Parent   get  private set             public NTree lt T gt  GetChild int i                        foreach  NTree lt T gt  n in children                  if  --i    0                      return n              return null                     public void Traverse NTree lt T gt  node  TreeVisitor lt T gt  visitor  string t  ref NTree lt T gt  r                        visitor node data  node  t  ref r               foreach  NTree lt T gt  kid in node children                  Traverse kid  visitor  t  ref r                       public static void DelegateMethod KeyValuePair lt string  string gt  data  NTree lt KeyValuePair lt string  string gt  gt  node  string t  ref NTree lt KeyValuePair lt string  string gt  gt  r                string a   string Empty          if  node data Key    t                        r   node              return                    using   NTree lt KeyValuePair lt string  string gt  gt  ret   null   tree Traverse tree  DelegateMethod  node  categoryId   InnerText  ref ret

User · Answer

Most trees are formed by the data you are processing        Say you have a person class that includes details of someone   s   parents  would you rather have the tree structure as part of your      domain class     or use a separate tree class that contained links to   your person objects    Think about a simple operation like getting all   the grandchildren of a person  should this code be in the person   class  or should the user of the person class have to know about a   separate tree class    Another example is a parse tree in a compiler     What both of these examples show is that the concept of a tree is part of the domain of the data and using a separate general purpose tree at least doubles the number of objects that are created as well as making the API harder to program again   What we want is a way to reuse the standard tree operations  without having to re-implement them for all trees  while at the same time  not having to use a standard tree class    Boost has tried to solve this type of problem for C    but I yet to see any effect for  NET get adapted

User · Answer

Here s a Tree public class Tree lt T gt    List lt Tree lt T gt  gt        public  T Data   get  private set         public Tree T data                this Data   data

User · Answer

The generally excellent C5 Generic Collection Library has several different tree-based data structures  including sets  bags and dictionaries  Source code is available if you want to study their implementation details   I have used C5 collections in production code with good results  although I haven t used any of the tree structures specifically

User · Answer

If you would like to write your own  you can start with this six-part document detailing effective usage of C  2 0 data structures and how to go about analyzing your implementation of data structures in C   Each article has examples and an installer with samples you can follow along with      An Extensive Examination of Data Structures Using C  2 0    by Scott Mitchell

User · Answer

Here s my own   class Program       static void Main string   args                var tree   new Tree lt string gt                 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   gt  PrintNode p  0            Console ReadKey               static void PrintNode lt T gt  TreeNode lt T gt  node  int level                Console WriteLine   0  1    new string      level   3   node Value           level            node Children ForEach p   gt  PrintNode p  level             public class Tree lt T gt        private Stack lt TreeNode lt T gt  gt  m Stack   new Stack lt TreeNode lt T gt  gt          public List lt TreeNode lt T gt  gt  Nodes   get      new List lt TreeNode lt T gt  gt          public Tree lt T gt  Begin T val                if  m Stack Count    0                        var node   new TreeNode lt T gt  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 lt T gt  Add T val                m Stack Peek   Add val           return this             public Tree lt T gt  End                 m Stack Pop            return this           public class TreeNode lt T gt        public T Value   get        public TreeNode lt T gt  Parent   get        public List lt TreeNode lt T gt  gt  Children   get         public TreeNode T val  TreeNode lt T gt  parent                Value   val          Parent   parent          Children   new List lt TreeNode lt T gt  gt                public TreeNode lt T gt  Add T val                var node   new TreeNode lt T gt  val  this           Children Add node           return node            Output   Fastfood    Pizza       Margherita       Marinara    Burger       Cheese burger       Chili burger       Rice burger

User · Answer

Here s mine  which is very similar to Aaron Gage s  just a little more conventional  in my opinion  For my purposes  I haven t ran into any performance issues with List lt T gt   It would be easy enough to switch to a LinkedList if needed     namespace Overby Collections       public class TreeNode lt T gt                private readonly T  value          private readonly List lt TreeNode lt T gt  gt   children   new List lt TreeNode lt T gt  gt              public TreeNode T value                         value   value                     public TreeNode lt T gt  this int i                        get   return  children i                        public TreeNode lt T gt  Parent   get  private set             public T Value   get   return  value               public ReadOnlyCollection lt TreeNode lt T gt  gt  Children                       get   return  children AsReadOnly                         public TreeNode lt T gt  AddChild T value                        var node   new TreeNode lt T gt  value   Parent   this                children Add node               return node                     public TreeNode lt T gt    AddChildren params T   values                        return values Select AddChild  ToArray                       public bool RemoveChild TreeNode lt T gt  node                        return  children Remove node                      public void Traverse Action lt T gt  action                        action Value               foreach  var child in  children                  child Traverse action                      public IEnumerable lt T gt  Flatten                         return new    Value  Concat  children SelectMany x   gt  x Flatten

User · Answer

I ve completed the code that  Berezh has shared     public class TreeNode lt T gt    IEnumerable lt TreeNode lt T gt  gt                 public T Data   get  set            public TreeNode lt T gt  Parent   get  set            public ICollection lt TreeNode lt T gt  gt  Children   get  set             public TreeNode T data                        this Data   data              this Children   new LinkedList lt TreeNode lt T gt  gt                        public TreeNode lt T gt  AddChild T child                        TreeNode lt T gt  childNode   new TreeNode lt T gt  child    Parent   this                this Children Add childNode               return childNode                     public IEnumerator lt TreeNode lt T gt  gt  GetEnumerator                         throw new NotImplementedException                       IEnumerator IEnumerable GetEnumerator                         return  IEnumerator GetEnumerator                        public class TreeNodeEnum lt T gt    IEnumerator lt TreeNode lt T gt  gt                 int position   -1          public List lt TreeNode lt T gt  gt  Nodes   get  set             public TreeNode lt T gt  Current                       get                               try                                       return Nodes position                                     catch  IndexOutOfRangeException                                        throw new InvalidOperationException                                                        object IEnumerator Current                       get                               return Current                                    public TreeNodeEnum List lt TreeNode lt T gt  gt  nodes                        Nodes   nodes                     public void Dispose                                public bool MoveNext                         position                return  position  lt  Nodes Count                      public void Reset                         position   -1

User · Answer

Here is my implementation of 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  gt   int this Data                                if  this Right    null                                        this Right   new Node Data                                     else                                       this Right Insert Data                                               if  Data  lt    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

User · Answer

I have a little extension to the solutions   Using a recursive generic declaration and a deriving subclass you can better concentrate on your actual target   Notice  it s different from a non generic implementation  you don t need to cast  node  in  NodeWorker     Here s my example   public class GenericTree lt T gt  where T   GenericTree lt T gt     recursive constraint          no specific data declaration      protected List lt T gt  children     public GenericTree           this children   new List lt T gt            public virtual void AddChild T newChild          this children Add newChild          public void Traverse Action lt int  T gt  visitor          this traverse 0  visitor          protected virtual void traverse int depth  Action lt int  T gt  visitor          visitor depth   T this       foreach  T child in this children        child traverse depth   1  visitor          public class GenericTreeNext   GenericTree lt GenericTreeNext gt     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

[c#] Tree data structure in C#

Examples related to c#

Examples related to data-structures