Function count left tree

Asked

Viewed 115 times

1

This function below compiles correctly, works.

int qtd_niveis (tipo_arvore * raiz)
{
if (raiz == NULL)
    return 0;
int esquerda = qtd_niveis(raiz -> esq);
int direita = qtd_niveis(raiz -> dir);
if (esquerda > direita)
    return ++ esquerda;
return ++ direita;
}

I tried something like this:

int qtd_niveis_esq (tipo_arvore * raiz)
{
if (raiz == NULL)
    return 0;
int esquerda = qtd_niveis_esq(raiz -> esq);
if (esquerda > direita)
    return ++ esquerda;    
}`

Only it does not return me the correct amount of levels left. someone could help me find where the error is. Thank you

c
  • 1

    Do you want the amount of elements left of the root or do you want to get the length of the leftmost branch of the tree? In the code, apparently you’re doing the second, but something tells me you want the first.

  • I want to know only how many levels has left, the first code returns how many levels has a tree, if it has 6 left and 7 right, will return me 7, that in the first code, and in the second code, have to return me for example only 6.

  • 1

    Just so we’re clear on this one image, what elements should be considered? FBA because it is the leftmost branch, or FBDC for being the largest to the left of the root?

  • Elements: ABCDEF (em_order )left, has to return 4 levels. If the right side had more levels, for example 5 levels, I would not be interested. I only care left which is 4 levels.

  • 1

    Something thus works?

  • Here returned 7instead of 4

  • I think this code of yours is counting all levels on each side, being in my example 4 left and 3 right, so 7

  • 1

    Let’s go continue this discussion in chat.

Show 3 more comments

1 answer

1


int
qtd_niveis_esq(tipo_arvore * raiz) {
    return 1 + qtd_niveis(raiz->esq);
}

The problem is you just want to ignore the right son from the root node. From the left child of the root, you want to use the normal algorithm for determining tree height. The only difference is that you have to add one because of the level that the root node occupies.

The code you made for qtd_niveis_esq() determines the height the left-most sheet of all (the one that would be visited first in a search for depth), which is not necessarily the height of the left subtree (unless coincidence).

EDIT: Apparently, the solution needs to be recursive? In this case, we can reimplement the qtd_niveis() just to meet schedule:

static int
altura_aux(tipo_arvore * raiz) {
    int e, d;

    if (!raiz) return 0;
    e = altura_aux(raiz->esq);
    d = altura_aux(raiz->dir);

    return 1 + (e > d ? e : d);
}

int
qtd_niveis_esq(tipo_arvore * raiz) {
    return 1 + altura_aux(raiz->esq);
}

It is writing code for nothing, but now recursivity is (re)implemented.

  • Thank you gave it right here.

  • Problem is that you do not use recursiveness in your code, already the top uses, but it worked normal here.

  • He calls the qtd_niveis(), which is recursive; but in any case, there is nothing in the question that mentions recursion.

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.