Binärbaum < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:04 Sa 09.05.2009 | | Autor: | farnold |
Hallo :)
Stellen wir uns vor, vor uns befindet sich ein binärbaum den wir in-,pre-, oder postorder ausgeben wollen.
das struct für den Binärbaum sieht so aus:
struct binBaum
{
int data;
binBaum* left;
binBaum* right;
};
damit der baum in in-,pre- oder postorder ausgegeben wird kann man das ja ganz leicht rekursiv programmieren.
Hättet ihr einen Denkanstoß wie man das ganze "nicht rekursiv" lösen kann?
Wäre es schon "nichtrekursiv" wenn ich den baum mithilfe von if-anweisungen und for-schleifen ausgeben lassen würde?
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:24 Sa 09.05.2009 | | Autor: | farnold |
habe einen weg gefunden wie ich es preorder traversieren kann und zwar rekursionsfrei:
preorder(node *tree)
{
push(tree);
while (!stackempty())
{
tree = pop();
visit(t);
if(tree->r!= NULL)
{
push(t->r)
}
if(tree->l!= NULL)
{
push(t->l)
}
}
}
Für Postorder habe ich auch eine Lösung gefunden.
habe nun alles erdenkliche probiert, bekomme es aber bei inorder einfach nicht rekursionsfrei hin.
Hat evtl. jemand einen kleinen denkanstoß für mich :)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:19 Mo 11.05.2009 | | Autor: | Gilga |
Vielleicht mit Listen arbeiten?(Queue oder Stack)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:18 Mo 11.05.2009 | | Autor: | Gilga |
Wäre es schon "nichtrekursiv" wenn ich den baum mithilfe von if-anweisungen und for-schleifen ausgeben lassen würde?
JA
rekursiv=Funktion ruft sich selbst auf
|
|
|
|
