{in a binary tree, for example...}
  array[0] is root, array[1] is first child, array[2] is second child,
array[3] is first child of first child, array[4] is second child of first
child... and so on and so on.

i need to find a formula or some way of finding the following:

  - given the index of the parent, find the indexes of its children
  - given the index of a child, find the index of its parent

suggestions/help/comments?
thanx
  - Poz

: {in a binary tree, for example...}
:   array[0] is root, array[1] is first child, array[2] is second child,
: array[3] is first child of first child, array[4] is second child of first
: child... and so on and so on.

: i need to find a formula or some way of finding the following:

:   - given the index of the parent, find the indexes of its children
:   - given the index of a child, find the index of its parent

Given a 1-based array and a binary tree, parent N has children 2N, 2N+1.
So for a zero-based array, you need to offset that by one.  k-trees are
a further extension.

Will

int curPos=0, curLen = ARRLEN;
char searchStr[] = "0110";
int searchPos = 0;

for(;searchPos<4;searchPos++)
{
        curLen = curLen / k;
        curPos += (searchStr[searchPos]-'0')*curLen + 1;

hope this helps ...

if: k=constant nr of children
if: 1=number of root (so not 0)
 example : binary
      1
 2       3
...
if: i=position where u are at

then:
parent=(i+n-2)/n
first child=n*i-n+2=n*(i-1) + 2

notice that if u change parent into i and i into parent in the first
expression, u get the second...
<Bart>

defenition:
(1)
depth= how deep in tree,
thus root:depth=0.
e.g.
         1         depth 0
    2      3      depth 1
4    5  6    7  depth 2
               ...
(2)
position=in the row u are in, how far are u from the left side.
in the example, the position(4)=1;position(3)=2;position(7)=4, etc.

1. first child=k*i-k+2

(1)
the number of elements at depth=d=k^d

with recursion:

- d=0 => number of elements = 1 (root)

- lets say that it's true for d=n, now prove it's true for d=n+1

so in depth d=n there are k^n elements.everyone of those elements has
k children, so there are k*k^n=k^(n+1) elements

(2)
the first element at depth=d=1+ Sum( k^t, t=0 until t=(d-1) )
//Sum does what the big sigma sign does...
//have to use Sum as i cant put the big sigma on my screen

with recursion

- d=0 => 1+ 0=1

- true for d=n, prove it's true for d=n+1

as there are k^n elements in depth n the first element at depth n+1=
(first element at depth n) + k^n;
this proves what had to be proven

(3) now the real proof

i has a depth and position, if these two parameters are known, i is
known.

the first child i'll abreviate with Ch1.
position=p;depth=d

Ch1=(p-1)*k + k^d - p + i + 1

explanation:
the elements at depth d before position all have n children, this
explains (p-1)*n
the elements at depth d at the right of position all count for 1, this
explains n^d - p becaus n^d is number of elements in that row
we have to add these two to the element i and then add 1 to move to
the first child of element i.

with (2) we can write p as:
p=i + 1 - (1 + Sum( k^t, t=0 until t=(d-1) )

note that for d=0 the equation we have to prove holds
so, lets say d>0
Sum( k^t, t=0 until t=(d-1) )=1 + k + k^2 + ... + k^(d-1)
= (k^d - 1) / (k - 1)

=>

p= i - (k^d - 1) / (k - 1)

=>Ch1=k*i - k*(k^d - 1) / (k - 1) - k + k^d - i + (k^d - 1)/(k - 1) +
i + 1
=k*i + 2 - k

parent=(i+n-2)/n
first child=n*i-n+2=n*(i-1) + 2

2. parent= (i+ k - 2)/k

we know that
Ch1=k*parent + 2 - k

=> Ch1- 2 + k is divisable by k
=>parent= (Ch1-2+k)/k

as (Ch1 - 2 + k) is divisable by k, the next (k-1) elements wont be
and so the division will result in the parent.

<Bart>

wow, I thought the solution to the orig post
was fairly easy until you managed to somehow
complicate it.

Ed Hill

i wonder what is difficult about this

parent=(i+n-2)/n
first child=n*i-n+2=n*(i-1) + 2

the formula given for the children
2i, 2i+1
only works for binary trees.

Maybe i shouldnt have posted the proof, but it took some time and i
didnt want it to go to waste.

Really, nothing difficult about those simple formulas....