Wysokość drzewa z tylko jeden węzeł

Question

Według Wikipedii,

Wysokość drzewa jest długość ścieżki od korzenia do najgłębszym węzła w drzewie. Drzewo (zrootowane) z tylko jednym węzłem (korzeń ) ma wysokość zero (lub jedną).

Nie rozumiem - czy to zero, czy jedno (lub oba)?

Answer 1

To tylko assuption zrobić dla rekurencyjnego opisu wysokości binarnego drzewa. Można rozważyć drzewo złożone tylko z węzła o wysokości 0 lub o wysokości 1.

Jeśli naprawdę chcesz, aby myśleć o tym jakoś można myśleć, że

• to 0, jeśli weźmie się pod uwagę wysokość jako liczba krawędzi (tak że pojedynczy węzeł nie ma żadnej przewagi, stąd 0)
• to 1 jeśli wziąć pod uwagę wysokość jako liczba węzłów (tak, że pojedyncza liczy węzła jako 1)

to jest po prostu opisać, ile wysokość najmniejsze drzewo ma, to w każdym przypadku, gdy dodasz węzeł opadający dodasz także krawędź powiązaną, więc zwiększy się odpowiednio ly.

W przykładzie opisanym w Wikipedia:

to drzewo może mieć wysokość 4 (węzłów) lub 3 (krawędzie). Zależy to od tego, czy liczą Państwo go za pomocą krawędzi czy węzłów.

Answer 2

Zależy konwencji. Nie ma tu "właściwej" odpowiedzi. Nauczono mnie, że to 1. Ale zero jest równie poprawne.

Answer 3

zależy jak chcesz interpretować wysokość drzewa. w niektórych aplikacjach drzewo z jednym węzłem interpretuje się jako mające wysokość równą jeden, a inne uznają je za wysokość zero.

Answer 4

Jedną z zalet używania liczby węzłów zamiast liczby krawędzi jest to, że rozróżnia ona pusty przypadek (zero węzłów i poziom węzła) od minimalnego przypadku (jeden węzeł i jeden węzeł na poziomie jednego). W niektórych przypadkach puste drzewo nie będzie miało znaczenia, ale w innych przypadkach próba pusta będzie całkowicie uzasadniona.

Answer 5

Moim zdaniem, Wysokość jednego węzła głównego powinna wynosić 0. Ma to praktyczny sens, ponieważ wysokość 2^zapewnia również liczbę węzłów na tym poziomie.