[Algorytmy] wysokość drzewa binarnego

[kasia00]

Witam. Mam do napisania algorytm, który oblicza wysokość poszczególnych liści drzewa binarnego przy użyciu stosu bez użycia rekurencji. Z rekurencja to prosta sprawa, a jak się zabrać do tego w takim przypadku?

[M Maciejewski]

Użycie stosu to niejako użycie rekurencji. Rzeczywiście, wywoływanie kolejny raz danej funkcji, i potem powrót do poprzedniej funkcji, opiera się na stosie. Tak więc można to działanie naśladować.

Działanie jest mniej więcej takie: gdy wchodzisz do kolejnej gałęzi, wrzucasz odpowiednie dane na stos (gdzie wrócić), jak już nie masz gdzie iść głębiej, jesteś w liściu i wracasz. Wiesz, gdzie wrócić, bo te dane masz na stosie.