Binärbaum in C ausgeben
 

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);
}
[/spoiler]

Damit bekomm ich oben angesprochene Struktur von
a
b c

hin, mehr leider nicht :(

Vllt. habt ihr ja eine Idee? :)

mfg[COLOR="Silver"]

----------

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

AW: Binärbaum in C ausgeben
 

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).

AW: Binärbaum in C ausgeben
 

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

AW: Binärbaum in C ausgeben
 

In einer meiner Vorlesungsfolien war das drin, allerdings Cpp:

[php]
void traverse(Knoten *node) {
if(node != NULL) {
cout << *((TDaten*) node->daten)<< endl;
traverse(node->l);
traverse(node->r);
}
}
[/php]
Später mehr.

AW: Binärbaum in C ausgeben
 

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:

[COLOR=White]aaa[/COLOR]c
a
[COLOR=White]aaa[/COLOR]b

statt

[COLOR=White]aaa[/COLOR]a[COLOR=White]aaa[/COLOR]
b [COLOR=White]aaaaa[/COLOR]c

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....

[COLOR=White]aaaaaaaaaa[/COLOR]f
[COLOR=White]aaaaa[/COLOR]e
[COLOR=White]aaaaaaaaaa[/COLOR]g
a
[COLOR=White]aaaaaaaaaa[/COLOR]b
[COLOR=White]aaaaa[/COLOR]c
[COLOR=White]aaaaaaaaaa[/COLOR]d

....

Die nötige Rekursion will nicht in meinen Kopf :denker:

mfg

AW: Binärbaum in C ausgeben
 

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);
}
[/spoiler]

[IMG]http://www.tweakpc.de/forum/members/kanonenfutter-albums-test-picture598-unbenannt.jpg[/IMG]

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

AW: Binärbaum in C ausgeben
 

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

AW: Binärbaum in C ausgeben
 

Sry für Quadpost :iosys:

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);

}
}
[/spoiler]
Musste nur den else Zweig der zweiten Funktion etwas abändern.
Funzt wunderbar ^^ :-D

mfg