Tree datatype

[Namal via Digitalmars-d-learn]

Hello,

I don't remember exactly but I think when I first saw D code 
there was tree datatype implemented without pointers. Is it 
possible to make a tree struct without pointers?

Re: Tree datatype

[cym13 via Digitalmars-d-learn]

On Wednesday, 14 October 2015 at 14:42:31 UTC, Namal wrote:

Hello,

I don't remember exactly but I think when I first saw D code 
there was tree datatype implemented without pointers. Is it 
possible to make a tree struct without pointers?


If it is a binary tree, sure: just put your elements in an array 
and state
that the left child of element at index i is the element at index 
2i+1, and

that its right child is at index 2i+2

For example this tree:

1
   / \
  2   3
 / \ / \
4  5 6  7

Will be represented by this array: [1, 2, 3, 4, 5, 6, 7]

Re: Tree datatype

[Tobias Pankrath via Digitalmars-d-learn]

On Wednesday, 14 October 2015 at 14:42:31 UTC, Namal wrote:

Hello,

I don't remember exactly but I think when I first saw D code 
there was tree datatype implemented without pointers. Is it 
possible to make a tree struct without pointers?


struct Tree {
   Tree[] children;
}

That works quite well as long as you don't have to change the 
tree.

Re: Tree datatype

[Meta via Digitalmars-d-learn]

On Wednesday, 14 October 2015 at 14:42:31 UTC, Namal wrote:

Hello,

I don't remember exactly but I think when I first saw D code 
there was tree datatype implemented without pointers. Is it 
possible to make a tree struct without pointers?


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.

Re: 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.

Re: Tree datatype

[H. S. Teoh via Digitalmars-d-learn]

On Wed, Oct 14, 2015 at 03:00:51PM +, Tobias Pankrath via 
Digitalmars-d-learn wrote:
> On Wednesday, 14 October 2015 at 14:42:31 UTC, Namal wrote:
> >Hello,
> >
> >I don't remember exactly but I think when I first saw D code there
> >was tree datatype implemented without pointers. Is it possible to
> >make a tree struct without pointers?
> 
> struct Tree {
>Tree[] children;
> }
> 
> That works quite well as long as you don't have to change the tree.

There are implicit pointers in Tree[].


T

-- 
I think the conspiracy theorists are out to get us...