Search code examples
c#tree

Creating Tree From Symbol List Based on Symbol Arity in C#


I am trying to figure out how to create a tree from a list of symbols which have a varying number of arity. For example, lets say I have the following symbols with the specified arity:

Symbol Arity
A 2
B 1
C 2
D 0
E 0

and I have the following string representation:

AABCDDEEDED

I am trying to build the following tree:

      A
     / \
    A   B
   / \  |
  C   D D
 / \
E   E

In this case, the last three symbols (DED) did not need to be used because the tree is already full.

I have already defined by symbols with the specific arity, and each of which contains a property which can hold a list of other symbols; all symbols implement ISymbol<T>. I also can generate the AABCDDE... string.

But I am kind of lost on how to get the tree-built. Is there a name for this kind of tree I am attempting to build? I wasn't able to find anything specific about varying number of nodes and to build it in this specific way (i.e., build it up layer by layer until all symbols of the current layer have their child populated before going to the next layer).

Any help with this would be greatly appreciated. TIA.

[EDIT] Implementations based on @michael-liu suggestion

var root = GeneCoding![0] as Symbol<T>;
if (root!.Arity == 0)
{
    return root!;
}

var queue = new Queue<Symbol<T>>();
queue.Enqueue(root);

Symbol<T> node;
Symbol<T> current;

foreach (var symbol in GeneCoding!.Skip(1))
{
    node = (Symbol<T>)symbol;
    if (node.Arity != 0)
    {
        queue.Enqueue(node);
    }

    current = queue.Peek();
    current.Nodes.Add(node);
    if (current.Arity == current.Nodes.Count)
    {
        var dequeued = queue.Dequeue();
        if (queue.Count > 0)
        {
            queue.Enqueue(dequeued);
        }
        else
        {
            return dequeued;
        }
    }
}

throw new Exception();

Solution

  • Because your tree is built layer by layer, I suggest using a queue of nodes. The algorithm would look something like this:

    1. Create the root node for the first symbol in the string.
    2. If root has zero arity, then STOP (the tree is complete).
    3. Create a queue of nodes that initially contains root.
    4. For each remaining symbol in the string:
      1. Create a node for symbol.
      2. If node has non-zero arity, then enqueue node at the back of queue.
      3. Peek the current node at the front of queue.
      4. Add node as a child of current.
      5. If current has full arity:
        1. Dequeue current from the front of queue.
        2. If queue is empty, then STOP (the tree is complete).
    5. [STOP] Return root as the output of the algorithm.

    Here's a corrected version of the code you posted:

    var root = (Symbol<T>)GeneCoding![0];
    if (root.Arity == 0)
    {
        return root;
    }
    
    var queue = new Queue<Symbol<T>>();
    queue.Enqueue(root);
    
    Symbol<T> node;
    Symbol<T> current;
    
    foreach (var symbol in GeneCoding!.Skip(1))
    {
        node = (Symbol<T>)symbol;
        if (node.Arity != 0)
        {
            queue.Enqueue(node);
        }
    
        current = queue.Peek();
        current.Nodes.Add(node);
        if (current.Arity == current.Nodes.Count)
        {
            queue.Dequeue();
            if (queue.Count == 0)
            {
                return root;
            }
        }
    }
    
    throw new Exception();