Count left tree function

Question

Count left tree function

Navigation

#1 by (1 votes)

1

This function below compiles correctly, it 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;    
}'

It just does not return the right amount of levels from the left. could someone help me find out where the error is. Thanks

c

asked by anonymous 17.05.2017 / 14:28

1 answer

Redirect with htaccess Malloc does not work in C code

score 1 · Accepted Answer

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

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

The code that you made for qtd_niveis_esq() determines the height of the leftmost leaf of all (the one that would be visited first in a depth search), which is not necessarily the height of the sub -tree left (except for coincidence).

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

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 at random, but now recursion is (re) implemented.