Re: array

["Des Walker" <des.walker@dessy.fsnet.co.uk>]

Ted Dennison <dennison@telepath.com> wrote in message
news:DpjB6.4297$FY5.303408@www.newsranger.com...
> In article <5s2B6.32267$ii5.3236241@afrodite.telenet-ops.be>, Pieter
Thysebaert
> says...
> >Now I was looking for a function that would allow me to convert the
contents
> >of a tree into an array (and vice versa)
> >I've found something like arrays with variable range (I mean not
fixed at
> >compile-time)
> >Well I think that's what I found - does that thing exist ?
> >
> >And if it does, how would one manipulate it (add/remove elements)
>
> Back in the olden days, binary trees were ususally implmented as
arrays. I
> believe the algorithms for doing so are avilable in "The Art of
Computer
> Programming, Volume 3"
 http://www-cs-faculty.stanford.edu/~knuth/taocp.html ).
> Go find, or preferably purchase yourself, a copy.
>
>
> >
> >Or are there data structures like C++ STL stuff (vector etc)
available ?
> The Ada implementation of the Booch Components should have something
for
> size-limited trees, which I would imagine would be implemented using
arrays (but
> I haven't examined the code).
>
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
>           home email - mailto:dennison@telepath.com

Hi,
  I think the underlying implementation for some of the 'bounded' items
in the Booch Components use arrays, but the array would not be directly
accessible to the user. The BC does provide some useful binary tree
implementations for dynamically changing binary trees, I've used the AVL
tree to good effect.

One method of representing a binary tree in an array is put each node at
the index which corresponds to the order you would obtain it in a
breadth order traversal.
i.e. If you number your binary tree nodes starting at the root node

-------1
---2-------3
4----5--6----7

The numbers correspond to the array index for the element

for an element at index I,
the left child will be at index (I*2)
the right child will be at index (I*2+1)
the parent will be at index (I/2)

If your binary tree has holes in it, you'll need some way of describing
an empty array element, to maintain the correct position of a node in an
array.
In this way you'll know a node doesn't have a child if the index for the
child is greater than the maximum size of the array, or the value at
that index is the empty element.

Sorry I can't be more helpful, I've never used an array implementation
for a binary tree. Binary Trees I have used have been ones which are
dynamically changing and need continuous rebalancing, for which the AVL
tree has been satisfactory.

    Des Walker