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

To proste pytanie z teorii algorytmów.
Różnica między nimi polega na tym, że w jednym przypadku liczy się liczbę węzłów, a drugą liczbę krawędzi na najkrótszej ścieżce między węzłem głównym a węzłem betonowym.
Który jest który?

Dowiedziałem się, że głębokość i wysokość to właściwości węzła :

• Głębokość węzła jest liczba krawędzi od węzła do węzła korzenia drzewa.
  Węzeł główny będzie miał głębokość 0.

• Wysokość węzła jest liczba krawędzi na najdłuższej ścieżki od węzła do liścia.
  Węzeł liścia będzie miał wysokość 0.

Właściwości drzewa :

• Wysokość drzewa byłaby wysokość jego korzenia,
  lub równoważnie, głębokość najgłębszej węzła.

• Średnica (lub szerokość ) drzewa jest liczba węzłów na najdłuższej ścieżce między dwoma dowolnymi węzłami liści. Drzewo poniżej ma średnicę 6 węzłów.

wysokość i głębokość drzewa jest równa ...

ale wysokość i głębokość węzła nie jest równa, ponieważ ...

wysokość oblicza się, przechodząc od danego węzła do najgłębszego możliwego liścia.

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

Według Cormen i in. Wprowadzenie do algorytmów (Załącznik 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 głównego T do X. Wysokość węzła Y wynosi liczba krawędzi na najdłuższej prostej ścieżce w dół od Y do liścia. Wysokość drzewa jest definiowana jako wysokość jego węzła głównego.

Zauważ, że prosta ścieżka to ścieżka bez powtarzalnych 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 trzeciej edycji Cormen i in. dla ilustracji tych pojęć.

Czasami widziałem problemy z proszeniem jednego o policzenie węzłów (wierzchołków) zamiast krawędzi, więc poproś o wyjaśnienie, jeśli nie jesteś pewien, czy powinieneś policzyć 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 głównego do węzła liścia 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 koncepcji jest: Głębokość: Narysuj poziomą linię w pozycji pierwiastkowej i potraktuj tę linię jako grunt. Tak więc głębokość korzenia wynosi 0, a wszystkie jej elementy potomne rosną w dół, więc każdy poziom węzłów ma bieżącą głębokość + 1.

Wysokość: ta sama linia pozioma, ale tym razem pozycją ziemi są zewnętrzne węzły, które są liściem drzewa i liczą w górę.

Chciałem napisać ten post, ponieważ jestem studentem studiów licencjackich i coraz częściej korzystamy z OpenDSA i innych podręczników typu open source. Wydaje się, że z najwyżej ocenianej odpowiedzi, że sposób uczenia się wysokości i głębokości zmienił się z pokolenia na pokolenie, i zamieszczam to, więc wszyscy są świadomi, że ta rozbieżność istnieje teraz i mam nadzieję, że nie spowoduje żadnych błędów programy! Dzięki.

Z książki OpenDSA Data Structures & Algos :

Jeśli n ₁ , n ₂ , ..., n _k jest taką sekwencją węzłów w drzewie, że n _i jest rodzicem n _i +1 dla 1 <= i <k, to sekwencja ta nazywana jest ścieżką od n _{Od 1} do n _k . Długość ścieżki wynosi k-1. Jeśli istnieje ścieżka od węzła R do węzła M, wówczas R jest przodkiem M, a M jest potomkiem R. Tak więc wszystkie węzły w drzewie są potomkami katalogu głównego drzewa, podczas gdy katalog główny jest przodkiem wszystkich węzłów. Głębokość węzła M w drzewie to długość ścieżki od korzenia drzewa do M. Wysokość drzewa jest o jeden większa niż głębokość najgłębszego węzła w drzewie.Wszystkie węzły głębokości d znajdują się na poziomie d w drzewie. Rdzeń 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 są dziećmi A. Węzły B i D razem tworzą poddrzewo. Węzeł B ma dwoje dzieci: jego lewe dziecko jest pustym drzewem, a prawe dziecko D. D. Węzły A, C i E są przodkami G. Węzły D, E i F tworzą 2 poziom drzewa; węzeł A znajduje się na poziomie 0. Krawędzie 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śćmi. Węzły A, B, C, E i F są węzłami wewnętrznymi. Głębokość I wynosi 3. Wysokość tego drzewa wynosi 4.