HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

What would we call this datastructure?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thiswhatwouldcalldatastructure

Problem

Suppose we have a datastructure that is a list containing elements that are either a leaf or another layer of the datastructure (recursively defined). What would we call this? It isn't a tree, since it has variable number of leaves and branches on each node. It isn't a forest, since it doesn't consist of a list of trees. I'm not exactly sure what to call it.

For context, the specific structure I'm designing is used as part of a compiler. The language is indentation structured, so blocks of code are grouped by their indentation level.

I have an Indentation_______, which is a list of nodes where the node is either a statement in the program, or a new Indentation_______ containing the next nested indentation level.

Any ideas?

Solution

A tree is not restricted to a certain branching factor. A n-ary tree may only have a branching factor of n (or less), but in an unrestricted tree, each node may contain an arbitrary number of subnodes.

A tree is a connected graph without cycles, so your datastructure still satisfies that definition.

Alternatively you could call your structure something like "nested lists".

Context

StackExchange Computer Science Q#51757, answer score: 13

Revisions (0)

No revisions yet.