Ignoring the last element in recursive call

Question

Ignoring the last element in recursive call

Navigation

#1 by (3 votes)

1

I'm implementing a tree in C, and one of my methods prints my tree in preorder, and separating the numbers with - .

I created this function:

void ImprimePreOrdem(TipoApontador arv){
    if(arv!=NULL){
        printf("%d-",arv->chave);
        ImprimePreOrdem(arv->esq);
        ImprimePreOrdem(arv->dir);
    }
}

However, for example if my tree contains the numbers from 1 to 10, when I print the elements of the tree recursively, the application drops the - at the end, leaving the output like this:

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

How do I delete this last - from my output?

c

asked by anonymous 09.12.2018 / 20:18

1 answer

Run multiple processes on Linux with Python How to dim the size of a Blob image?

score 3 · Accepted Answer

There are several ways you can implement the logic you want. The solution I show you is to reverse the logic a bit, so that you show the first element normally, and each element in the front first shows the trace and then the number. This way it always comes out right and you do not need to know the last element to "cancel the last trace".

How do you know which first element to print differently?

Well you also have several alternatives, a simple is to pass the level of the element you are printing, the root is the 0 level. At the 0 level prints only the number, and at the other levels prints the trace first to connect to the previous one, and then the number.

To maintain the function you have with the same prototype you need another auxiliary function that includes the level and increases with each call.

Implementation of suggested logic:

void ImprimePreOrdemAux(TipoApontador arv, int nivel){
    if(arv != NULL){
        if (nivel != 0){ //so imprime o traço do anterior se não for o primeiro
            printf("-");
        }
        printf("%d",arv->chave);
        ImprimePreOrdemAux(arv->esq, nivel + 1);
        ImprimePreOrdemAux(arv->dir, nivel + 1);
    }
}

void ImprimePreOrdem(TipoApontador arv){
    ImprimePreOrdemAux(arv, 0); //chama a função auxiliar com nivel 0
}

You can also implement the same without an auxiliary function and putting nivel as a global variable, but it is certainly a worse solution even though it is simpler.

See an example of this implementation working on Ideone

Note also that this solution will work for any of the three ways to go through the tree, infix , prefix or postfix / p>