Calcule a altura de uma árvore

Question

Estou tentando calcular a altura de uma árvore. Estou com o código escrito abaixo.

#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);*/

}

Isso me dá resultado correto. Mas em Algumas postagens(Página Google) Sugeriu -se que faça uma travessia postocerte e use esse método de altura para calcular a altura. Algum motivo específico?

Answer 1

Mas uma travessia da Postome não é exatamente o que você está fazendo? Supondo que a esquerda e a direita não sejam nulos, você primeiro height(left), então height(right), e depois algum processamento no nó atual. Isso é travessia da Postome, de acordo com mim.

Mas eu escrevia assim:

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

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

Editar: Dependendo de como você define a altura da árvore, o caso base (para uma árvore vazia) deve ser 0 ou -1.

Answer 2

O código falhará nas árvores onde pelo menos um dos nós tem apenas um filho:

// 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);
//...

Se a árvore tiver dois nós (a raiz e uma criança esquerda ou direita), chamar o método na raiz não cumprirá a primeira condição (pelo menos uma das subárvores não está vazia) e ligará recursivamente para as duas crianças. Um deles é nulo, mas ainda assim será desreferente ao ponteiro nulo para executar o if.

Uma solução correta é a postada por Hans aqui. De qualquer forma, você deve escolher quais são seus invariantes de método: ou você permite chamadas onde o argumento é nulo e lida com isso graciosamente ou precisa que o argumento seja não nulo e garante que você não chama o método com ponteiros nulos .

O primeiro caso é mais seguro se você não controlar todos os pontos de entrada (o método é público como no seu código), pois você não pode garantir que o código externo não passará por indicadores nulos. A segunda solução (alterando a assinatura para referência e tornando -a um método de membro do tree classe) pode ser mais limpo (ou não) se você puder controlar todos os pontos de entrada.

Answer 3

A altura da árvore não muda com a travessia. Permanece constante. É a sequência dos nós que mudam dependendo da travessia.

Answer 4

Definições de Wikipedia.

Pré-encomenda (profundidade primeiro):

1. Visite a raiz.
2. Atravessar a subárvore esquerda.
3. Atravessar a subárvore direita.

InOrder (simétrico):

1. Atravessar a subárvore esquerda.
2. Visite a raiz.
3. Atravessar a subárvore direita.

PROTORMA:

1. Atravessar a subárvore esquerda.
2. Atravessar a subárvore direita.
3. Visite a raiz.

"Visite" nas definições significa "calcular a altura do nó". Que no seu caso é zero (à esquerda e à direita são nulos) ou 1 + altura combinada das crianças.

Na sua implementação, a ordem de travessia não importa, daria os mesmos resultados. Não posso realmente dizer nada além disso, sem um link para sua fonte, afirmando que a Postler prefere.

Answer 5

Aqui está a resposta:

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