K simo element in an ABB search binary tree

Question

K simo element in an ABB search binary tree

Navigation

#1 by (1 votes)

0

I'm having trouble doing a function that finds the item with position k inside a binary search tree (ABB). I have to go through it in order, that is, left, root, right. So far I have this code but it gives me Segmentation fault. If you have another way of implementing it, it also helps.

Thanks

c

asked by sabri128 24.04.2017 в 14:16

source

1 answer

Subtract varlores from one array with the last value of another array Copy data type text from excel to word VBA [closed]

score 1 · Answer 1

static info_t aux_kesimo(nat k, binario b, nat contador){

If your intention is to make a recursive call, I regret to communicate that with this function it will not be possible. The reason is that before processing the node in question you have to process your left branch beforehand and that can trigger an indeterminate number of calls that you have no way of counting, then you will not know when you reach the contador element.

Also, the function is totally useless:

static info_t aux_kesimo(nat k, binario b, nat contador){

    return aux_kesimo(k, b->izq, contador); // <<--- (1)

    if(++contador == k){
        return b->dato; // <<--- (2)
    }

    return aux_kesimo(k, b->der, contador); // <<--- (3)
}

According to the code always the return (1) will be executed, which will prevent the return (2) and (3) from being executed at some point.

You would need an auxiliary function such as:

binario* buscar_kesimo(binario nodo, nat* contador)
{
  binario* toReturn = 0;

  if( nodo->izq )
    toReturn = buscar_kesimo(nodo->izq,contador);

  if( !toReturn )
  {
    if( *contador == 0 )
      toReturn = nodo;
    else
      *contador--; // el contador solo se actualiza al procesar el nodo
  }

  if( !toReturn && nodo->der )
    toReturn = buscar_kesimo(nodo->der,contador);

  return toReturn;
}

With which your function could look like this:

static info_t aux_kesimo(nat k, binario b, nat contador){
  binario nodo = buscar_kesimo(b,&contador);

  if( nodo )
    return nodo->dato;
  else
    // No hay nodo con el indice dado
}