Calculate tree height

Question

I am trying to calculate the height of a tree. I doint with the code written below.

#include<iostream.h>

struct tree
{
    int data;
    struct tree * left;
    struct tree * right;
};

typedef struct tree tree;

class Tree
{
private:
    int n;
    int data;
    int l,r;
public:
    tree * Root;
    Tree(int x)
    {
        n=x;
        l=0;
        r=0;
        Root=NULL;
    }
    void create();
    int height(tree * Height);

};

void Tree::create()
{
    //Creting the tree structure
} 

int Tree::height(tree * Height)
{
    if(Height->left==NULL && Height->right==NULL)
    {return 0;
    }
    else
    {
        l=height(Height->left);
        r=height(Height->right);

        if (l>r)
        {l=l+1;
        return l;
        }
        else
        {
            r=r+1;
            return r;
        }
    }
}

int main()
{
    Tree A(10);//Initializing 10 node Tree object
    A.create();//Creating a 10 node tree

    cout<<"The height of tree"<<A.height(A.Root);*/

}

This gives me the result of corret. But in a few posts (googled page), it was suggested to bypass the Postorder and use this height method to calculate the height. Any specific reason?

Answer 1

But isn't this a post-operative bypass of exactly what you are doing? Assuming both left and right are both non-zero, first do height(left), then height(right), and then some processing on the current node. This postoperative bypass is for me.

But I would write it as follows:

int Tree::height(tree *node) {
    if (!node) return -1;

    return 1 + max(height(node->left), height(node->right));
}

: , , ( ) 0 -1.

Answer 2

, :

// code snippet (space condensed for brevity)
int Tree::height(tree * Height) {
    if(Height->left==NULL && Height->right==NULL) { return 0; }
    else {
        l=height(Height->left);
        r=height(Height->right);
//...

( , ), ( ) . , if.

- , Hans . , : , null, , , , .

, ( , ), , . ( - tree) ( ), .

Answer 3

. . , .

Answer 4

wikipedia.

( ):

• .
• .
• .

Inorder ():

• .
• .
• .

Postorder:

• .
• .
• .

"" " node". ( , - ) 1 + .

, . , , , , .

Answer 5

:

int Help :: heightTree (node *nodeptr)
{
    if (!nodeptr)
        return 0;
    else
    {
        return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
    }
}