Wypisywanie elementów drzewa binarnego

Question

Cześć, siedzę od pewnego czasu nad problemem jak wypisać elementy drzewa binarnego (w dowolnej kolejności) i w sumie rekurencja w tym przypadku dużo upraszcza, jest to zaledwie kilka linijek, ale czy ma ktoś pomysł jak osiągnąć to samo bez rekurencji?

* drzewo ma postać:

struct drzewo
{
int w;
drzewo *lewy;
drzewo *prawy;
}

więc wskaźniki są tylko na dzieci

Answer 1

Tutaj masz kilka przykładów iteracyjnego dfs-a https://stackoverflow.com/questions/5278580/non-recursive-depth-first-search-algorithm

Answer 2

Może coś takiego, że wypisujesz lewe dziecko, prawe dziecko węzła i dodajesz węzeł do tablicy węzłów odwiedzonych. Następnie przeskakujesz z aktualnego węzła, na lewe dziecko, i wypisujesz lewą i prawą wartość dzieci. I teraz jeżeli węzeł nie ma już dzieci to wracasz do węzła rodzica (zakładam, że węzeł zna swojego rodzica) i jeżeli wszystkie dzieci węzła rodzica są już w tablicy odwiedzonych, to wracasz do kolejnego rodzica do momentu aż wszystkie dzieci korzenia drzewa będą znajdowały się w tablicy węzłów odwiedzonych. Pominąłem tutaj sprawdzanie czy węzeł jest NULL, ale coś takiego mi się nasunęło. Pewnie jest lepsze rozwiązanie, ale to tak na szybko.

Comments

Spoko w sumie, tylko nie dodałem :/ że może drzewo to coś w stylu:

struct drzewo
{
int w;
drzewo *lewy;
drzewo *prawy;
}

więc dziecko nie zna rodzica, 

---

więc dziecko nie zna rodzica, 

Wredne życie, smutny los. :<