## digitalmars.D.learn - Tree datatype

• Namal (4/4) Oct 14 2015 Hello,
• cym13 (13/17) Oct 14 2015 If it is a binary tree, sure: just put your elements in an array
• Tobias Pankrath (6/10) Oct 14 2015 struct Tree {
• Meta (5/9) Oct 14 2015 The answer is more or less no, unless you sort of fake it like in
• cym13 (17/22) Oct 14 2015 I disagree. The representation I showed isn't a fake of any sort:
Namal <sotis22 mail.ru> writes:
```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?
```
Oct 14 2015
cym13 <cpicard openmailbox.org> writes:
```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]
```
Oct 14 2015
Tobias Pankrath <tobias pankrath.net> writes:
```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.
```
Oct 14 2015
"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
```On Wed, Oct 14, 2015 at 03:00:51PM +0000, 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...
```
Oct 14 2015
Meta <jared771 gmail.com> writes:
```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.
```
Oct 14 2015
cym13 <cpicard openmailbox.org> writes:
```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