[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: pointers and recursive algorithms
From: |
Jaroslav Hajek |
Subject: |
Re: pointers and recursive algorithms |
Date: |
Tue, 16 Mar 2010 10:03:03 +0100 |
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