Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
2  
1  
It is actually a tree. Just not a binary tree (or n-ary tree). But it's still a tree. – Wildcard Jan 13 at 1:39
    
I prefer to call these things blocks but ... – Joshua Jan 13 at 5:29
up vote 13 down vote accepted

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

share|cite|improve this answer
3  
(nit): "A tree is a [connected] graph without cycles" – Mike B. Jan 12 at 14:24
    
@MikeB. thanks, I added that – user3158988 Jan 12 at 14:27
1  
Technically, even a linked list is a degenerate tree. – chrylis Jan 12 at 18:37
    
Most trees in CS are technically rooted, ordered trees. Not trees at all for graph theory purists – vonbrand Jan 13 at 1:32

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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