Jaka jest różnica między głębokością a wysokością drzewa?

Wysokość i głębokość drzewa są równe...

Ale wysokość i głębokość węzła nie są równe, ponieważ...

Wysokość obliczana jest przez przejście od danego węzła do najgłębszego możliwego liścia.

Głębokość jest obliczana od przejścia od korzenia do danego węzła.....

Według Cormen et al. Wprowadzenie do algorytmów (Dodatek B. 5.3), głębokość węzła X w drzewie T jest zdefiniowana jako długość prostej ścieżki (liczba krawędzi) od węzła korzeniowego T do X. wysokość węzła Y jest liczbą krawędzi na najdłuższej w dół prostej ścieżki od y do liścia. Wysokość drzewa definiowana jest jako wysokość jego węzła korzeniowego.

Zauważ, że prosta ścieżka jest ścieżką bez powtórzeń wierzchołków.

Wysokość drzewa jest równa maksymalnej głębokości drzewa . Głębokość węzła i wysokość węzła niekoniecznie są równe. Patrz rysunek B. 6 z 3. Wydania Cormen et al. dla ilustracji tych pojęć.

Czasami widziałem problemy z prośbą o liczenie węzłów (wierzchołków) zamiast krawędzi, więc poproś o wyjaśnienie, jeśli nie jesteś pewien, czy powinieneś liczyć węzły lub krawędzie podczas egzaminu lub rozmowy kwalifikacyjnej.

Prosta Odpowiedź:
Głębokość:
1. drzewo: Liczba krawędzi / łuku od węzła korzeniowego do węzła liściowego drzewa nazywana jest głębokością drzewa.
2. węzeł: Liczba krawędzi / łuku od węzła głównego do tego węzła jest nazywana głębokością tego węzła.

Innym sposobem na zrozumienie tych pojęć jest następujący: Głębokość: narysuj poziomą linię w pozycji korzenia i traktuj tę linię jako grunt. Więc głębokość korzenia wynosi 0, a wszystkie jego dzieci rosną w dół, więc każdy poziom węzłów ma aktualną głębokość + 1.

Wysokość: ta sama linia pozioma, ale tym razem pozycja podłoża jest węzłami zewnętrznymi, czyli liściem drzewa i liczyć w górę.

Chciałem zrobić ten post, ponieważ jestem studentem CS ' a i coraz częściej korzystamy z Opendsy i innych podręczników open source. Wygląda na to, że z najwyżej ocenianej odpowiedzi wynika, że sposób nauczania wysokości i głębokości zmienił się z pokolenia na pokolenie, a ja publikuję to, aby każdy był świadomy, że ta rozbieżność istnieje i mam nadzieję, że nie spowoduje błędów w żadnych programach! Dzięki.

Z Opendsa Data Structures & Algos book :

Jeśli n₁, n₂,..., n _k jest sekwencją węzłów w drzewie takich że N_i jest rodzicem n_i+1 dla 11 do n _k . Długość ścieżki to k-1. Jeśli istnieje ścieżka od węzła R do węzła M, To R jest przodkiem M, A M jest potomkiem R. Tak więc wszystkie węzły w drzewie są Potomków korzenia drzewa, natomiast korzeń jest przodkiem wszystkie węzły. głębokość węzła M w drzewie jest długość ścieżka od korzenia drzewa Do M. wysokość drzewa jest jeszcze jedna niż głębokość najgłębszego węzła w drzewie. wszystkie węzły głębokości d są na poziomie d w drzewie. Root jest jedynym węzłem na poziomie 0, a jego głębokość wynosi 0.

Rysunek 7.2.1: drzewo binarne. Węzeł A jest korzeniem. Węzły B I C to Dzieci A. Węzły B I D tworzą razem poddrzewo. Węzeł B ma dwoje dzieci: jego lewym dzieckiem jest puste drzewo i jego prawe dziecko to D. węzły A, C i E są przodkami G. węzły D, E i F tworzą poziom 2 drzewa; węzeł A jest na poziomie 0. Brzegi od A do C do E do G tworzą ścieżkę o długości 3. Węzły D, G, H I I są liście. Węzły A, B, C, E i F są węzłami wewnętrznymi. Głębokość z I jest 3. Wysokość tego drzewa wynosi 4.