General tree - non binary- height

Question

Sorry for my bad english. Is not my original language.

My problem is that I want to know the height of a general tree, I dont know if that is how it call in english.

The struct of the tree is:

struct GTnode{
    int data;
    nodeGT *fc; //first child
    nodeGT *nb; //next brother
}

Every next brother are in the same level as the first child, and every first child have a +1 level.

This is my code but i'm not sure if is right:

int height(GT *root){
    if(root == null){
        return 0;
    }
    else{
        int max=0;
        int h;
        h = height(root->fc);
        if(h > max){
            max = h;
        }
        max = max + 1;
        h = height(root->nb);
        if(h > max){
           max = h;
        }
        return max;
    }
}

Anton Savin · Answer 1 · 2014-09-11T22:20:22.460

2

Your code seems to be fine. I would just make it a bit more compact:

#include <algorithm>

int height(GT *root) {
    return root ? std::max(height(root->fc) + 1, height(root->nb)) : 0;
}

edited Sep 11 '14 at 22:20

answered Sep 11 '14 at 22:07

Anton Savin

40,838
8
54
90

You are right, that is a shorter way to right it. I don't understand what is std. – Manuel Larrosa Sep 11 '14 at 22:16
@ManuelLarrosa `std` is a namespace for all standard classes and functions in C++. It seems you are new to the language, you may need to read a decent book on it. – Anton Savin Sep 11 '14 at 22:19
Thanks. I know std but I used it doing using namespace std, that's why didn't recognized it. And im pretty new in c++. Thanks for the help – Manuel Larrosa Sep 11 '14 at 22:46
@ManuelLarrosa BTW `using namespace std` [is considered bad practice](http://stackoverflow.com/q/1452721/3959454). – Anton Savin Sep 11 '14 at 22:51

score 0 · Answer 2 · answered Sep 12 '14 at 08:07

I see only one problem: you fail to check if there are children or brothers.

Sure, there's a bit of verbosity. I'd write the code as follows:

int GTnode::height()
{
    int hb = fb ? height(fb) : 0;
    int hc = fc ? height(fc) : 0;
    return std::max(hb, hc+1);
}

General tree - non binary- height

2 Answers2