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();
Because your tree is built layer by layer, I suggest using a queue of nodes. The algorithm would look something like this:
root
node for the first symbol in the string.root
has zero arity, then STOP (the tree is complete).queue
of nodes that initially contains root
.symbol
in the string:
node
for symbol
.node
has non-zero arity, then enqueue node
at the back of queue
.current
node at the front of queue
.node
as a child of current
.current
has full arity:
current
from the front of queue
.queue
is empty, then STOP (the tree is complete).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();