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?
algorithm
data-structures
tree
nodes
terminology
Gabriel Ščerbák
źródło
źródło
Odpowiedzi:
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.
źródło
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 .....
źródło
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.
źródło
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.
źródło
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ę.
źródło
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 :
źródło