Re: pointers and recursive algorithms

[Jaroslav Hajek]

2010/3/15 Cássio M. M. Pereira <address@hidden>:
>
> Dear list,
>
> I would like to implement a recursive tree algorithm in octave.
> As far as I know, Octave does not support pointer types.
> It seems to me that the most appropriate structure to implement a tree
> in octave would be a (nested) cell array.
>
> However, how can I, for instance, make a recursive binary search in a tree
> (implemented as a cell array) and return a pointer to the cell where the
> information is stored?
>
> If pointers are not available, is there another way to get around this?
>
> Thank you,
> Cássio Pereira

I would suggest using indices into an array instead of pointers.
For instance, you can have three arrays, holding indices of the
left/right child, and node values.

A binary search can then look like this:

i = 1;
v = searched value;

while i > 0
  x = values(j = i);
  if (x > v)
    i = left (i);
  else
    i = right (i);
  endif
endwhile

# j now holds the leaf index, x its value.

but before you do this, I'd suggest you really make sure that you
can't do what you need with the ordinary array binary search using
"lookup".

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz