Largest number function in a tree

Question

I’m developing a function of returning myself the largest number of a tree. I am trying this code, but I did not succeed in its compilation, printing -1 on the screen, while it was to print only the largest number of the tree.

int maiorNum(tipo_arvore * raiz)
{
 if(raiz != NULL)
  return maiorNum(raiz->dir);
 else
  return -1;
 }

Answer 1

The first step I take when solving a problem is knowing what I’m dealing with. In our case, we have a binary tree in which all nodes, not just leaves, have real value (ie, not just index values). It was not provided by André whether the tree is searching or not, although in his code snippet he leaves this implicit. I will answer here for both cases.

Generalized binary tree

A tree is a structure that is given by the following rules:

1. a node is a constituent element of a tree,
2. a knot has at most a single parent knot,
3. a node may not have parent, this case it is called root.

In addition, we have some concepts/conclusions derived from these definitions:

1. if A, B and C has as a parent knot X, it is said that A, B and C are we children of X,
2. a leaf is a knot that has no children,
3. the simplest tree is composed only of the root,
4. a knot, their children and all their descendants constitute a subtree,
5. two nodes belong to the same tree if they share the same root,
6. if I only navigate from any knot to your child knot, I will never happen to find the same descending knot by two different paths.

A binary tree is a specification of the generalized tree; it has the same rules of formation and also the following:

1. for a tree to be binary, every node is limited to having at most 2 child nodes.

As an additional concept, we have that child nodes are identified by left node and right node.

To go through a binary tree, I need to go through the root, the subtree on the left (the one formed by the left node) and the subtree on the right. The order in which I pass through each of these three elements is roughly indifferent.

So if I make the visit in order knot, left, right, I kind of have this algorithm:

navega_arvore(nodo subarvore):
    visita(subarvore)
    se subarvore->esquerda != null:
        navega_arvore(subarvore->esquerda)
    se subarvore->direita != null:
        navega_arvore(subarvore->direita)

This is the general structure of the navigation. In case the node has a value specified by inf, and want to take the biggest inf possible, we have this algorithm:

maior_inf_arvore(nodo subarvore):
    inf_atual = subarvore->inf

    maior_inf = inf_autal # até encontrar um filho com uma informação maior, o maior que eu tenho é o atual
    se subarvore->esquerda != null:
        inf_esquerda = maior_inf_arvore(subarvore->esquerda)

        se inf_esquerda > maior_inf:
            maior_inf = inf_esquerda
    se subarvore->direita != null:
        inf_direita = maior_inf_arvore(subarvore->direita)

        se inf_direita > maior_inf:
            maior_inf = inf_direita
    retorne maior_inf

In recursion, I guarantee that I will go through all the nodes descended from the last node. I also guarantee that, after this navigation, I will get as much information as possible inside the subtree.

In C, that algorithm looks something like this:

int maior_inf_arvore(tipo_arvore *subarvore) {
    int maior_inf, inf_atual, inf_esquerda, inf_direita;

    inf_atual = subarvore->inf;

    maior_inf = inf_autal; /* até encontrar um filho com uma informação maior, o maior que eu tenho é o atual */
    if (subarvore->esquerda != null) {
        inf_esquerda = maior_inf_arvore(subarvore->esq);

        if (inf_esquerda > maior_inf) {
            maior_inf = inf_esquerda;
        }
    }
    if (subarvore->direita != null) {
        inf_direita = maior_inf_arvore(subarvore->dir);

        if (inf_direita > maior_inf) {
            maior_inf = inf_direita;
        }
    }
    return maior_inf;
}

Binary tree of search

A binary search tree is a binary tree that has the following additional rules:

1. every node has comparable information,
2. the left child node has less information than its father’s,
3. the right child node has information greater than or equal to that of its parent.

So on top of that definition, we don’t need to navigate left. We also have a guarantee that if you have a child on the right, that child has more information, so I shouldn’t consider the information from the original. So, in pseudo-code, it would be:

maior_inf_arvore_busca(nodo subarvore):
    se subarvore->direita != null:
        retorne maior_inf_arvore(subarvore->direita)
    senão:
        retorne subarvore->inf

In C:

int maior_inf_arvore_busca(tipo_arvore *subarvore) {
    if (subarvore->dir != null) {
        return maior_inf_arvore(subarvore->dir);
    } else {
        return subarvore->inf;
    }
}

Only this is a simple recursive strategy. It could be replaced by a simple iteration:

int maior_inf_arvore_busca(tipo_arvore *subarvore):
    tipo_arvore *navegacao = subarvore
    while (navegacao->dir != null) {
        navegacao = navegacao->dir;
    }

    return navegacao-> inf;
}

NOTE

I haven’t done the treatment of passing the root of the null tree, but it’s easy to do that.

Answer 2

Friend tries to put tipo_arvore instead of the int.

I will edit here because someone left as negative my reply.

tipo_arvore * maior(tipo_arvore * raiz)
{
  if((raiz->dir) && (raiz->dir > raiz->inf))
    return maior(raiz->dir);
  else
    return raiz->inf;
}