Tree datatype

[cym13 via Digitalmars-d-learn]

On Wednesday, 14 October 2015 at 18:07:25 UTC, Meta wrote:
> The answer is more or less no, unless you sort of fake it like 
> in cym13's example. A tree is not possible without pointers due 
> to its recursive nature. Even if it looks like the 
> implementation doesn't use pointers, they're just hidden under 
> some abstraction.

I disagree. The representation I showed isn't a fake of any sort: 
forgetting that a tree is an abstract object that can have many 
different representations (involving pointers or not) is an 
error. Recursion isn't what drives the need for pointer (my 
definition is perfectly recursive for example and can be extended 
to n-ary trees with multidimensionnal arrays).

They're are only three reasons to prefer a pointer-based 
implementation:
     1) The ability to rearrange the tree's elements with changing 
their address
     2) It uses less memory if the tree isn't filled
     3) A generic tree can have any number of children (and that's 
the most crucial point)

This explains why any standard implementation I know of is 
pointer (or reference) based, but that doesn't mean any other 
representation is invalid.