Wysokość drzewa binarnego

Question

Wysokość drzewa binarnego

Rozważ następujący kod:

public int heightOfBinaryTree(Node node)
{
    if (node == null)
    {
        return 0;
    }
    else
    {
        return 1 +
        Math.max(heightOfBinaryTree(node.left),
            heightOfBinaryTree(node.right));
    }
}

Chcę poznać logiczne rozumowanie tego kodu. Jak ludzie na to wpadli? Czy ktoś ma dowód indukcyjny?

Co więcej, pomyślałem o zrobieniu BFS z korzeniem drzewa binarnego jako argumentem do uzyskania wysokości drzewa binarnego. Czy poprzednie podejście jest lepsze niż moje?Dlaczego?

35

java algorithm tree

Author: marcog, 2010-12-25

Source

4 answers

Logika stojąca za tym kodem to:

Ponieważ węzeł będzie miał dwoje dzieci, wysokość drzewa będzie maksymalnie równa wysokości drzewa, którego korzeniami są lewe dziecko i prawe dziecko, i oczywiście +1 na spacer do dzieci.

Jak widać Powyższy opis jest rekurencyjny, podobnie jak kod.

BFS również powinien to zrobić, ale byłoby to przesadą zarówno ze względu na implementację, jak i złożoność czasoprzestrzeni.

Istnieje funkcja rekurencyjna, choć trudna do zrozumieć, ale są bardzo eleganckie w realizacji.

4

Author: Shamim Hafiz,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-12-25 19:55:13

Wysokość drzewa jest długością najdłuższej ścieżki w dół od jego korzenia. Funkcja ta jest rekurencyjnym sposobem liczenia poziomów drzewa binarnego. Po prostu zwiększa liczniki, gdy schodzi z drzewa, zwracając maksymalny licznik (licznik na najniższym węźle).

Mam nadzieję, że pomogłem.

2

Author: tiagovrtr,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-12-07 18:51:28

Jest funkcją rekurencyjną. Mówi, że wysokość drzewa wynosi 1 + wysokość jego najwyższej gałęzi.

Czy BFS to pierwsze wyszukiwanie? Nie jestem pewien, jaka byłaby różnica w wydajności, ale podoba mi się prostota funkcji rekurencyjnej.

0

Author: Adrian Mouat,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-12-25 21:27:24

score 48 · Accepted Answer

if (node == null)
{
    return 0;
}

Dziećmi węzłów liściowych są null. Dlatego mówi się, że gdy już minęliśmy liście, nie ma dalszych węzłów.

Jeśli nie jesteśmy poza węzłami liścia, musimy obliczyć wysokość i ten kod robi to rekurencyjnie.

return 1 +

Bieżący węzeł dodaje Wysokość 1 do wysokości aktualnie obliczanego poddrzewa.

    Math.max(heightOfBinaryTree(node.left),
        heightOfBinaryTree(node.right));

Rekurencyjnie obliczamy wysokość lewego poddrzewa (node.left) i prawego poddrzewa (node.right). Ponieważ jesteśmy obliczając maksymalną głębokość, bierzemy maksimum z tych dwóch głębokości.

Pokazałem powyżej, że funkcja rekurencyjna jest poprawna. Wywołanie funkcji na węźle nadrzędnym obliczy głębokość całego drzewa.

Oto graficzna reprezentacja wysokości drzewa z tego dokumentu. {[6] } jest wysokością drzewa, hl i hr są wysokościami odpowiednio lewej i prawej podstrefy.

Ponadto, I myślałem tylko o zrobieniu BFS z korzeniem drzewa binarnego jako argument, aby uzyskać wysokość drzewo binarne. Jest poprzedni podejście lepsze niż moje?Dlaczego?

Podany kod jest formą DFS. Ponieważ musisz przetworzyć wszystkie węzły, aby znaleźć wysokość drzewa, nie będzie różnicy między DFS i BFS, chociaż BFS będzie używać pamięci O(N), podczas gdy DFS będzie używać pamięci o (logN). BFS jest również nieco bardziej złożony do kodu, ponieważ wymaga kolejki podczas DFS korzysta z" wbudowanego " stosu rekurencyjnego.