Calculate tree height oriented C ++

Question

Calculate tree height oriented C ++

Navigation

#1 by (3 votes)
#2 by (2 votes)

3

I have a tree class to represent oriented trees (No binaries). The nodes are represented by a cell, which has the method lchild () that gives us the most left and right () son or simply increasing (as in list) to get his brother who follows him. Here I leave code to list previous order, to take into account.

void oprev(tree<int> &T, tree<int>::iterator p){
tree<int>::iterator q;
if (p == T.end()){ 
    return;
}
cout<<*p<<" ";
q = p.lchild();
while( q != T.end() ){
    oprev (T, q++);
}

void oprev(tree<int> &T){
oprev(T,T.begin());}

I need to calucar the height of a tree. I have this code but it is not correct

int altura(tree<int> &T,tree<int>::iterator p, int &x){
tree<int>::iterator q;
if (p == T.end()){ 
    return x;
}
q = p.lchild();
while( q != T.end() ){
    altura(T, q++,x);
}
if(p.lchild()!=T.end()){
    x++;
}
return x;}

Having this tree.

As height I get 5.

I recognize that the error is in that the counter, sometimes adds back when it passes through levels that previously has already passed. I do not know how I can avoid this. Thank you very much. Greetings

c++

asked by Leandro Berli 11.10.2017 в 16:18

source

2 answers

Return data from a php server using AJAX List Order

score 3 · Answer 1

If by "height of the tree" you mean how long are your "branches" you are not doing well. You have several problems of concept.

Proposal.

Add to your class template tree a function altura that will consult all the nodes of its root how deep they are and will keep the maximum of them:

int tree::altura()
{
    int a = 0;

    for (auto &nodo : raiz)
        a = std::max(a, deep(nodo, 0))

    return a;
}

The above code assumes that your class tree has a node named raiz and that the node provides the functions begin and end .

The previous function calls the recursive function deep that does almost the same as the function altura with the difference that each level of recursion increases the level by 1, for this function the node must receive from the what to calculate and the depth from which to start counting:

int tree::deep(Nodo &n, int nivel)
{
    int a = nivel;

    for (auto &nodo : raiz_del_arbol)
        a = std::max(a, deep(nodo, nivel + 1))

    return a;
}

If the node we have reached has no children, its level will be the level provided in the call.

Other things to consider.

You have some design flaws that I would like to comment on:

Do not use free functions to do these operations, these functions force you to expose the data of your class, thus breaking the encapsulation.
If you really have to use free functions, use a template function, or you'll be forced to create a version for each instantiation of the template tree .

score 2 · Answer 2

You are counting the number of children, not the height.

The difference is that, for any node, the height will be the maximum of the heights of the two children, not the sum of the heights.

So pull to (pseudocode to not take away the pleasure of programming):

int altura(nodo n) {

   int alturaDerecha = 0; int alturaIzquierda = 0;

   si es n un nodo terminal {
      return 1;
   }

   si existeHijoDerecho de n {
      alturaDerecha = altura(n.hijoDerecho());
   }

   si existeHijoIzquierdo de n {
      alturaIzquierda = altura(n.hijoIzquierdo());
   }

   int alturaHijos = max(alturaDerecha, alturaIzquierda);
   return alturaHijos + 1;
}

If you find it more readable, you can move the terminal node check before looking up the children's heights.