Altezza di un albero con un solo nodo

Question

Secondo Wikipedia,

  

L'altezza di un albero è la lunghezza del percorso dalla radice alla   profondo nodo nell'albero. A (radicata) albero con un solo nodo (la   root) ha un'altezza di zero (o uno).

I dont get it -? È zero o uno (o entrambi)

Answer 1

E 'solo un Assuption si effettua per la descrizione ricorsiva l'altezza di un albero binario. Si può considerare un albero composto da appena un nodo sia con 0 altezza o con 1 altezza.

Se si vuole veramente pensare in qualche modo si può pensare che

• è 0 se si considera l'altezza come conteggio bordo (in modo che un singolo nodo non ha alcun bordo, quindi 0)
• è 1 se si considera l'altezza come un numero di nodi (in modo che un singolo nodo conta come 1)

Questa è solo per descrivere quanto l'altezza dell'albero più piccola ha, quindi in ogni caso ogni volta che si aggiunge un nodo discendente si aggiungerà anche un vantaggio relativo in modo che aumenterà di conseguenza.

Nell'esempio fornito in Wikipedia:

Questo albero può avere un'altezza 4 (nodi) o 3 (bordi). Dipende se si contano che da bordi o nodi.

Answer 2

Un vantaggio di utilizzare un numero di nodi anziché un conteggio vantaggio è che distingue il caso vuota (a zero nodi, e livello di nodo) dalla scatola minima (un nodo, e un livello di nodo di uno). In alcuni casi, un albero vuoto non sarà significativo, ma in altri casi un tentativo vuoto sarà perfettamente legittima.

Answer 3

Dipende convenzione . Non c'è una risposta "giusta" qui. Mi è stato insegnato che è pari a zero 1. Ma è altrettanto corretto.

Answer 4

Ho il mio parere, altezza di un nodo radice dovrebbe essere 0. Ha senso pratico come 2 ^ altezza è anche ti fornisce il numero di nodi a quel livello.

Answer 5

Supponendo che si sta calcolando l'altezza in modo ricorsivo nella classe del nodo che avrei fatto questo per restituire l'altezza senza includere l'altezza della radice (codice Java):

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height() + 1;
    if(right != null)
        rightHeight =+ right.height() + 1;
    return Math.max(leftHeight, rightHeight);
}

se si desidera includere l'altezza della radice, quindi vorrei fare questo:

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height();
    if(right != null)
        rightHeight =+ right.height();
    return Math.max(leftHeight, rightHeight) + 1;
}

Answer 6

dipende da come si vuole interpretare l'altezza di un albero. in alcune applicazioni, un albero con un nodo viene interpretato come avente altezza di uno e gli altri considerano come aventi altezza pari a zero.