Qual è la differenza tra la profondità e l'altezza dell'albero?

Question

Questa è una domanda semplice da algoritmi di teoria.
La differenza tra loro è che in un caso si conta il numero di nodi e in altro numero di bordi sul percorso più breve tra radice e il nodo di cemento.
Quale è quale?

Answer 1

ho imparato che la profondità e l'altezza sono proprietà di un node :

• profondità di un nodo è il numero di archi dal nodo al nodo radice dell'albero.
  Un nodo radice avrà una profondità di 0.

• Il Altezza di un nodo è il numero di bordi sul più lungo percorso dal nodo a una foglia.
  nodo Una foglia avrà un altezza 0.

Proprietà di un albero :

• Altezza di un albero sarebbe l'altezza del suo nodo radice,
  o equivalentemente, la profondità del suo nodo più profondo.

• Il diametro (o Larghezza ) di un albero è il numero di nodi sul percorso più lungo tra due nodi foglia . L'albero di seguito ha un diametro di 6 nodi.

Answer 2

altezza e la profondità di un albero è uguale ...

ma l'altezza e la profondità di un nodo non è uguale perché ...

l'altezza viene calcolata attraversamento al nodo stesso alla più profonda foglia possibile.

profondità è calcolata da attraversamento dalla radice al nodo determinato .....

Answer 3

Secondo Cormen et al. Introduzione agli algoritmi (appendice B.5.3), la profondità di un nodo X in un albero T è definita come la lunghezza del percorso semplice (numero di archi) dal nodo radice di T a X. L'altezza di un nodo Y è il numero di bordi sul lungo ribasso cammino semplice da Y ad una foglia. L'altezza di un albero è definita come l'altezza del suo nodo radice.

Si noti che un semplice percorso è un percorso senza vertici di ripetizione.

L'altezza di un albero di è uguale alla profondità massima di un albero . La profondità di un nodo e l'altezza di un nodo non sono necessariamente uguali. Vedere la figura B.6 della 3 ° edizione del Cormen et al. per un'illustrazione di questi concetti.

A volte ho visto problemi chiedendo uno per contare nodi (vertici), invece di bordi, in modo da chiedere chiarimenti, se non siete sicuri si dovrebbe contare nodi o bordi durante un esame o un colloquio di lavoro.

Answer 4

Risposta semplice:
Profondità:      
1. Albero : Numero di bordi / arco dal nodo radice al nodo foglia dell'albero è chiamato come la profondità dell'albero.     Pagina 2. Nodo . Numero lati / arco dal nodo radice a quel nodo è chiamato come la profondità di tale nodo

Answer 5

Un altro modo per capire chi concetto è come segue: Profondità: disegnare una linea orizzontale nella posizione di radice e trattare questa linea come massa. Così la profondità della radice è 0, e tutti i suoi bambini sono crescere verso il basso in modo che ogni livello di nodi ha la profondità attuale + 1.

Altezza:. Same linea orizzontale, ma questa volta la posizione terreno è nodi esterni, che è la foglia di albero e contare verso l'alto

Answer 6

Ho voluto fare questo post, perché io sono uno studente di CS undergrad e sempre più usiamo OpenDSA e di altri libri di testo open source. Sembra che dalla sommità risposta nominale che l'altezza e la profondità modo che viene insegnato è cambiato da una generazione a quella successiva, e sto postando questo modo tutti sono consapevoli che questa discrepanza ora esiste e si spera non sarà causa di problemi di qualsiasi programmi! Grazie.

OpenDSA Strutture dati e Algos libro :

  

Se n ₁ , n ₂ , ..., n _k è una sequenza di nodi dell'albero tale   che n _i è il genitore di n _i +1 per 1 <= i 1 per n _k . La lunghezza del percorso è k-1.   Se v'è un percorso dal nodo al nodo R M, allora R è un antenato di   M, e M è un discendente di R. Così, tutti i nodi dell'albero sono   discendenti della radice dell'albero, mentre la radice è l'antenato   tutti i nodi. La profondità di un nodo M nell'albero è la lunghezza del   percorso dalla radice dell'albero a M. L'altezza di un albero è un altro   rispetto alla profondità del nodo più profondo nella struttura. Tutti i nodi di profondità d   sono a livello d nell'albero. La radice è l'unico nodo a livello 0, e   la sua profondità è 0.

     

     

Figura 7.2.1: Un albero binario. Nodo A è la radice. I nodi B e C sono   Come i bambini. Nodi B e D insieme formano una sottostruttura. Nodo B ha   due figli: il suo figlio sinistro è l'albero vuoto e il suo figlio destro è   D. nodi A, C ed E sono antenati di nodi G. D, E, e F   compongono il livello 2 della struttura; il nodo A è a livello 0. I bordi da A   a C a E a G formare un percorso di lunghezza 3. nodi D, G, H e I   sono foglie. Nodi A, B, C, E, e F sono nodi interni. La profondità   di I è 3. L'altezza di questo albero è 4.