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.
