Calcolare l'altezza di un albero

Question

Sto cercando di calcolare l'altezza di un albero. Sto doint con il codice scritto in basso.

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

}

Mi dà risultato corret. Ma in alcuni post (pagina su google) è stato suggerito di fare un attraversamento postorder e l'uso questo metodo altezza per calcolare l'altezza. Qual è il motivo specifico?

Answer 1

Ma non è un attraversamento postorder esattamente quello che stai facendo? Supponendo sinistra e destra sono entrambi non nullo, per prima cosa fate height(left), poi height(right), e poi alcuni di elaborazione nel nodo corrente. Ecco postorder attraversamento secondo me.

Ma vorrei scrivere in questo modo:

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

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

Modifica: a seconda di come si definisce l'altezza degli alberi, il caso base (per un albero vuoto) dovrebbe essere 0 o -1

.

Answer 2

Il codice non sarà riuscito in alberi in cui almeno uno dei nodi ha un solo figlio:

// 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 l'albero è dotato di due nodi (la radice e sia un bambino a sinistra oa destra) chiamando il metodo sulla radice non soddisfare la prima condizione (almeno uno dei sotto-alberi è non-vuoto) e sarà chiamata in modo ricorsivo su entrambi i bambini. Uno di loro è nullo, ma ancora si dereference il puntatore nullo per eseguire la if.

Una soluzione corretta è quella pubblicato da Hans qui. In ogni caso si deve scegliere ciò che i vostri metodi invarianti sono: o si permettono le chiamate in cui l'argomento è nullo e si gestiscono che con grazia, altrimenti si richiede l'argomento ad essere non nullo e la garanzia che non si chiama il metodo con puntatori nulli .

Il primo caso è più sicuro se non si controlla tutti i punti di ingresso (il metodo è pubblico come nel codice) dal momento che non si può garantire che il codice esterno non passerà puntatori nulli. La seconda soluzione (cambiando la firma di riferimento, e che lo rende un metodo membro della classe tree) potrebbe essere più pulito (o meno) se è possibile controllare tutti i punti di ingresso.

Answer 3

L'altezza dell'albero non cambia con l'attraversamento. Rimane costante. E 'la sequenza dei nodi che cambiano a seconda della attraversamento.

Answer 4

wikipedia .

  

Preorder (in profondità):

     

  
1. Visita alla radice.
  
2. Traverse la sottostruttura sinistra.
  
3. Traverse il sottoalbero destro.
  

     

Inorder (simmetrico):

     

  
1. Traverse la sottostruttura sinistra.
  
2. Visita alla radice.
  
3. Traverse il sottoalbero destro.
  

     

postorder:

     

  
1. Traverse la sottostruttura sinistra.
  
2. Traverse il sottoalbero destro.
  
3. Visita alla radice.
  

"visita" nelle definizioni significa "calcolare l'altezza del nodo". Che nel tuo caso è o zero (sia a sinistra che a destra sono null) o 1 + altezza combinata dei bambini.

Nella tua implementazione, l'ordine di attraversamento non importa, darebbe gli stessi risultati. Posso davvero dirvi qualcosa di più di che, senza un link al tuo fonte affermando postorder è quello di preferire.

Answer 5

Ecco la risposta:

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