Binärbaum in C ausgeben

[kanonenfutter]

Hallöchen

Ich möchte eine erstellten Binärbaum wie folgt ausgeben:

a (Wurzel)
bc
defg
...

Muss also nicht die typische Baumstruktur sein. Bisher schaff ich die Ausgabe folgendermaßen:
a b c d e f g ...

Ich würde auch
a
b c

hinbekommen, die unteren Ebenen funktionieren dann aber nicht mehr.

Also zwar schon in der richtigen Reiehnfolge, allerdings kann ich die Zeilenumbrüche nicht so setzen, dass eben genau dann umgebrochen wird, wenn eine neue Ebene erreicht wird.

Könnt ihr mir da mit einem kleinen Pseudocode helfen?

Die Augabe sieht atm so aus:

Spoiler:

void ZeigeBaum(TKnoten * p_pWurzel)
{
printf("Erzeugter Baum \n");
printf("--------------------------------\n\n");

if(p_pWurzel == NULL)
{
printf("Der Baum ist leer!");
}
else
{
printf("%d \n", p_pWurzel->iInhalt);

ZeigeBaum_Innen(p_pWurzel->pKindLinks, 1);
ZeigeBaum_Innen(p_pWurzel->pKindRechts, 1);
printf("\n");

}
}

///////////////////////////////////////////////////////////////////////////////////////

void ZeigeBaum_Innen(TKnoten * p_pWurzel, int p_iEbene)
{
if(p_pWurzel == NULL)
{
}
else
{
printf("%d ", p_pWurzel->iInhalt);
}

Damit bekomm ich oben angesprochene Struktur von
a
b c

hin, mehr leider nicht

Vllt. habt ihr ja eine Idee?

mfg

----------

In der Funktion ZeigeBaum_Innen muss ich ja wahrscheinlich wieder irgendwie rekursiv aufrufen, hab aber leider kA was wann und wie... ;(

[Fakk-asrock]

Du brauchst in jedem element 3 Zeiger:
nachfolger links, nachfolger rechts und den vorgänger.

je nachdem was du vorhast musst du dann die elemente in der richtigen reinfolge eingeben oder eine sortierfunktion einbauen.

Ich hab das ganze nur mal mit pascal gemacht, von prinzip aber das gleiche (lineare Liste).

[kanonenfutter]

Prinzipiell müsste ich ja nur folgendes machen:

Wert der Wurzel ausgeben, Zeilenwechsel (funzt)
Wert des linken und des rechten Nachfolgers ausgeben, Zeilenwechsel (geht)

Den linken/rechten Nachfolger vom linken und rechten Nachfolger der Wurzel ausgeben.

usw.

Um den linken/rechten Nachfolger des linken Nachfolgers der Wurzel ausgeben zu können kann ich zB die gleichen Funktionen verwenden und vorher den linken Nachfolger der Wurzel als neue Wurzel deklarieren. Das würde noch gehen, dann hab ich aber das Problem das ich nicht mehr in den rechten Teilbaum komme :/

Sry, bisschen verwirrend vllt. ^^

Ich will eigtl. nur folgendes:
Wurzel ausgeben, Zeilenwechsel
Ebene 1 von links nach rechts ausgeben, Zeilenwechsel
.
.

Das muss irgendwie rekursiv funzen, hab aber keine Ahnung wie?!

mfg

[redfalcon]

In einer meiner Vorlesungsfolien war das drin, allerdings Cpp:

PHP-Code:

void traverse(Knoten *node) {
if(node != NULL) {
cout << *((TDaten*) node->daten)<< endl;
traverse(node->l);
traverse(node->r);
}
} 


Später mehr.

[kanonenfutter]

Das wäre klasse

Ich versuch mich gerade an einer anderen Idee:
Ich werfe den Baum auf die Seite und gebe von links nach rechts aus:

aaac
a
aaab

statt

aaaaaaa
b aaaaac

Das geht garantiert einfacher (zumindest versteh ich es leichter ) allerdings fehlt mir auch hier noch der ultimative Algoritmus ;(

Nur wäre es hier prinzipiell so zu lösen (da ja die Konsole von oben nach unten schreibt), dass ich zuerst den größten wert (am weitesten rechts s Bsp f) ausgeben müsste, davor mit Tiefe x Tabs um ihn entsprechend weit einzurücken. Dann Zeilenwechsel. Dann entsprechend dessen Wurzel (e). Dann der linke Sohn dieser Wurzel (g). Usw....

aaaaaaaaaaf
aaaaae
aaaaaaaaaag
a
aaaaaaaaaab
aaaaac
aaaaaaaaaad

....

Die nötige Rekursion will nicht in meinen Kopf

mfg

[kanonenfutter]

Update:

Der Quellcode sieht jetzt folgendermaßen aus und gibt mir dabei den Baum wie unten auf dem Bild zu sehen aus:

Spoiler:

void ZeigeBaum(TKnoten * p_pWurzel)
{
printf("Erzeugter Baum \n");
printf("--------------------------------\n\n");

if(p_pWurzel == NULL)
{
printf("Der Baum ist leer!");
}
else
{
ZeigeBaum_Innen(p_pWurzel->pKindRechts, 1);
printf("%d \n", p_pWurzel->iInhalt);
ZeigeBaum_Innen(p_pWurzel->pKindLinks, 1);
// printf("\n");
}

}

///////////////////////////////////////////////////////////////////////////////////////

void ZeigeBaum_Innen(TKnoten * p_pStelle, int p_iEbene)
{

if (p_pStelle == NULL)
{
}
else
{
ZeigeBaum_Innen(p_pStelle->pKindRechts, p_iEbene+1);
for(int i = 1; i<=p_iEbene; i++)
{
printf("\t");
}

printf("%d \n", p_pStelle->iInhalt);


ZeigeBaum_Innen(p_pStelle->pKindLinks, p_iEbene+1);
for( i = 1; i<=p_iEbene; i++)
{
printf("\t");
}

printf("%d \n", p_pStelle->iInhalt);
}

http://www.tweakpc.de/forum/members/...-unbenannt.jpg

Das Problem seht ihr ja
Der Baum ist vollständig und die Werte stimmen, allerdings sind eben einige doppelt. kA wieso und ich find auch den Fehler im Code nicht...?!

Jmd. ne Idee?

mfg

[kanonenfutter]

Keiner ne Idee? Ich kann noch 20mal drüber schauen und find den Fehler nich So schwerwiegend kann es ja nicht sein, wird nur ein Detailfehler sein, hab aber kA wo... ^^

Anscheinend wird irgend eine Funktion doppelt aufgerufen oder so?! Wenn ihr noch Erläuterungen zum Code braucht einfach bescheid geben, sofern das bei der Problemlösung helfen kann

thx und mfg

[kanonenfutter]

Sry für Quadpost

Lösung:

Spoiler:

void ZeigeBaum(TKnoten * p_pWurzel)
{
printf("Erzeugter Baum \n");
printf("--------------------------------\n\n");

if(p_pWurzel == NULL)
{
printf("Der Baum ist leer!");
}
else
{
ZeigeBaum_Innen(p_pWurzel->pKindRechts, 1);
printf("%d \n", p_pWurzel->iInhalt);
ZeigeBaum_Innen(p_pWurzel->pKindLinks, 1);
// printf("\n");
}

}

///////////////////////////////////////////////////////////////////////////////////////

void ZeigeBaum_Innen(TKnoten * p_pStelle, int p_iEbene)
{
if (p_pStelle == NULL) //Abbruch
{
}
else
{
ZeigeBaum_Innen(p_pStelle->pKindRechts, p_iEbene+1);

for(int i = 1; i<=p_iEbene; i++)
{
printf("\t");
}

printf("%d \n", p_pStelle->iInhalt);

ZeigeBaum_Innen(p_pStelle->pKindLinks, p_iEbene+1);

}
}

Musste nur den else Zweig der zweiten Funktion etwas abändern.
Funzt wunderbar ^^

mfg