3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Rose_tree $\endgroup$ – wchargin Jan 12 '16 at 19:06
  • 1
    $\begingroup$ It is actually a tree. Just not a binary tree (or n-ary tree). But it's still a tree. $\endgroup$ – Wildcard Jan 13 '16 at 1:39
  • $\begingroup$ I prefer to call these things blocks but ... $\endgroup$ – Joshua Jan 13 '16 at 5:29
13
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ (nit): "A tree is a [connected] graph without cycles" $\endgroup$ – Mike B. Jan 12 '16 at 14:24
  • 1
    $\begingroup$ Technically, even a linked list is a degenerate tree. $\endgroup$ – chrylis -on strike- Jan 12 '16 at 18:37
  • $\begingroup$ Most trees in CS are technically rooted, ordered trees. Not trees at all for graph theory purists $\endgroup$ – vonbrand Jan 13 '16 at 1:32
4
$\begingroup$

The set of

  • rooted trees with
  • arbitrary numbers of children
  • the order of which matters

is typically called the set of plane trees or simply ordered trees (the absence of further restrictions characterises the set sufficiently).

So feel free to use "tree" provided you clarify (once) which kind you mean exactly. The only possible point of confusion is the separation from graph-theoretic trees, which are not necessarily rooted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.