Binärbaum strukturiert ausgeben



  • so, ich hab jetzt eine Ausgabefunktion geschrieben, die funktioniert auch. jedoch habe ich wie man sieht etwas geschummelt -, habe die zeiger per Hand zugewiesen. Wie müsste denn eine Funktion im Grunde aussehen, die mir ein Feld automatisch füllt?

    feld soll aussehen:
    4
    26
    1357

    quasi nur jede eben des baumes in einer zeile.

    Danke schonmal im vorraus 🙂

    void Ebene(struct Baum *zgr)
    {
    	int Ausgabe[3][5] = { 0 };
    	int a = 0;
    	int b = 0;
    	int i, breite = 80;
    	int ersteBreite = breite / 2;
    	int zweiteBreite = ersteBreite - 13;
    	int dritteBreite = breite / 5;
    	int spalten = 4;
    	/*
    	int i	:	Anzahl der Ebenen
    
    	*/
    
    	if (zgr->zahl == NULL)
    	{
    		return;
    	}
    
    	Ausgabe[0][0] = zgr->zahl;
    	Ausgabe[1][0] = zgr->links->zahl;
    	Ausgabe[1][1] = zgr->rechts->zahl;
    	Ausgabe[2][0] = zgr->links->links->zahl;
    	Ausgabe[2][1] = zgr->links->rechts->zahl;
    	Ausgabe[2][2] = zgr->rechts->links->zahl;
    	Ausgabe[2][3] = zgr->rechts->rechts->zahl;
    
    		//Ausgabe der ersten Ebene in der Mitte
    		printf("%*d\n", ersteBreite, Ausgabe[0][0]);
    		printf("\n\n");
    
    		//Ausgabe der zweiten Ebene darunter
    		for (i = 0; i < 2; i++){
    			printf("%*d", zweiteBreite, Ausgabe[1][i]);
    		}
    		printf("\n\n");
    		printf("\n\n");
    
    		//Ausgabe der dritten Ebene darunter
    		for (i = 0; i < 4; i++){
    			printf("%*d", dritteBreite, Ausgabe[2][i]);
    
    		}
    
    	printf("\n\n");
    	printf("Ende\n");
    
    }
    

  • Mod

    Als ich mir mal eine sehr spezielle Baumstruktur geschrieben habe, da habe ich zu Debuggingzwecken ebenfalls den Baum ausgegeben und hatte die gleichen Probleme. Die einfache und sogar schöner anzusehende Lösung war, anstatt selber die Ausgabe zu formatieren, eine Ausgabe in DOT zu erzeugen und die dann durch ein entsprechendes Programm zu jagen. DOT-Code kann man nämlich vergleichsweise einfach aus so einer Baumstruktur erzeugen, indem man rekursiv den Baum runter geht.

    Beispiel, wie das bei mir aussah (einfach ein paar Zahlen in einen Baum eingefügt, wie sie mir beim Tippen unter die Finger kamen):
    http://i61.tinypic.com/whlg8g.png
    (Die Zahlen an den Pfeilen und die Farben der Knoten sind Verwaltungsdaten meiner speziellen Datenstruktur, die kannst du ignorieren) Ist zwar nicht perfekt symmetrisch, aber es erfüllt seinen Zweck und war ganz einfach zu machen. Ist jedenfalls viel besser, als alles, was man ohne großen Aufwand von Hand machen kann.

    Dieser Baum wurde erzeugt, indem mein Programm folgende Ausgabe erzeugte, die ich danach als Eingabe für graphviz/dot benutzt habe:

    digraph G {
    	node [color=black];
    	root -> 7;
    	node [color=black];
    	7 -> 4 [label="5"];
    	node [color=black];
    	7 -> 9 [label="6"];
    	7 -> root;
    	node [color=black];
    	4 -> 2 [label="2"];
    	node [color=black];
    	4 -> 5 [label="2"];
    	4 -> 7;
    	2 -> nill2 [label="0"];
    	nill2 [color = black, label = "nil"];
    	node [color=red];
    	2 -> 3 [label="1"];
    	2 -> 4;
    	3 -> nill3 [label="0"];
    	nill3 [color = black, label = "nil"];
    	3 -> nilr3 [label="0"];
    	nilr3 [color = black, label = "nil"];
    	3 -> 2;
    	5 -> nill5 [label="0"];
    	nill5 [color = black, label = "nil"];
    	node [color=red];
    	5 -> 6 [label="1"];
    	5 -> 4;
    	6 -> nill6 [label="0"];
    	nill6 [color = black, label = "nil"];
    	6 -> nilr6 [label="0"];
    	nilr6 [color = black, label = "nil"];
    	6 -> 5;
    	node [color=black];
    	9 -> 8 [label="1"];
    	node [color=red];
    	9 -> 76 [label="4"];
    	9 -> 7;
    	8 -> nill8 [label="0"];
    	nill8 [color = black, label = "nil"];
    	8 -> nilr8 [label="0"];
    	nilr8 [color = black, label = "nil"];
    	8 -> 9;
    	node [color=black];
    	76 -> 43 [label="2"];
    	node [color=black];
    	76 -> 433 [label="1"];
    	76 -> 9;
    	node [color=red];
    	43 -> 34 [label="1"];
    	43 -> nilr43 [label="0"];
    	nilr43 [color = black, label = "nil"];
    	43 -> 76;
    	34 -> nill34 [label="0"];
    	nill34 [color = black, label = "nil"];
    	34 -> nilr34 [label="0"];
    	nilr34 [color = black, label = "nil"];
    	34 -> 43;
    	433 -> nill433 [label="0"];
    	nill433 [color = black, label = "nil"];
    	433 -> nilr433 [label="0"];
    	nilr433 [color = black, label = "nil"];
    	433 -> 76;
    }
    

    Das Programm ist in C++ geschrieben, daher würde dir der Code wohl nicht viel nützen. Der Algorithmus ist teilweise speziell für meinen Baum, du hast es vermutlich etwas einfacher, da deine Knoten keine zusätzlichen Verwaltungsdaten tragen. Ich werde bei meiner folgenden Beschreibung aber trotzdem die Verwaltungsdaten angeben, da:
    1. Es für mich weniger Arbeit ist, da ich einfach Copy & Paste machen kann und dann den Code von C++ in Pseudocode übertragen kann.
    2. Dann siehst du mehr Beispielcode, wie man solche Ausgaben erzeugen kann.

    Der Code:

    -Starte mit node = wurzelknoten
    -Falls node existiert:
    --Ausgabe: "digraph G {\n\tnode [color=black];\n\troot -> " + Wert von node + ";\n"
    --Falls linkes Kind existiert:
    ---Falls es rot ist:
    ----Ausgabe:  "\tnode [color=red];\n"
    ---Andernfalls:
    ----Ausgabe: "\tnode [color=black];\n"
    ---Ausgabe: '\t' + Wert von node +  " -> " + Wert von linkem Kind + " [label=\"" + Verwaltungsdaten für linken Zeiger + "\"];\n"
    --Andernfalls:
    ---Ausgabe: '\t' + Wert von node + " -> nill" + Wert von node + " [label=\"0\"];\n\tnill" + Wert von node +  " [color = black, label = \"nil\"];\n"
    --Falls rechtes Kind existiert:
    ---Gleiches wie oben, aber eben für rechts. Ersetze zudem "nill" (nil links) durch "nilr" (nil rechts).
    --Ausgabe:  '\t' + Wert von Node + " -> root;\n"
    --Falls linkes Kind existiert:
    ---Rekursive Ausgabe von linkem Kind
    --Falls rechtes Kind existiert:
    ---Rekursive Ausgabe von rechtem Kind
    --Ausgabe: "}\n"
    

    Dabei ist die rekursive Ausgabe der Unterknoten ganz ähnlich, bloß braucht man dieses mal keine Präambel für den dot-Code und auch keine Sonderbezeichnung für den Wurzelknoten:

    Rekursive Ausgabe von node:
    -Falls linkes Kind existiert:
    --Falls es rot ist:
    ---Ausgabe:  "\tnode [color=red];\n"
    --Andernfalls:
    ---Ausgabe: "\tnode [color=black];\n"
    --Ausgabe:  '\t' + Wert von Node + " -> " +  Wert von linkem Kind + " [label=\"" + Verwaltungsdaten linker Zeiger + "\"];\n"
    -Andernfalls:
    --Ausgabe:  '\t' + Wert von Node + " -> nill"  + Wert von Node + " [label=\"0\"];\n\tnill" + Wert von Node + " [color = black, label = \"nil\"];\n"
    -Falls rechtes Kind existiert:
    --Wieder das gleiche wie oben, aber jeweils für rechts und mit "nilr" statt "nill".
    -Falls Elternknoten existiert:
    --Ausgabe:  '\t' + Wert von Node + " -> " + Wert von Elternknoten + ";\n"
    -Andernfalls:
    --Ausgabe: '\t' + Wert von Node + " -> root;\n"
    --Falls linkes Kind existiert:
    ---Rekursive Ausgabe von linkem Kind
    --Falls rechtes Kind existiert:
    ---Rekursive Ausgabe von rechtem Kind
    

    Hoffentlich haben sich bei der Übertragung von C++ nach Pseudocode keine Fehler eingeschlichen. Sicherlich nichts, was man durch ein bisschen mitdenken nicht korrigieren könnte.

    Die Idee ist, wie du hoffentlich schon mitbekommen hast, dass man hier dafür sorgt, dass jeder Bezeichner genau einmal vorkommen kann. Dies wird erreicht, indem hier der Inhalt der Knotens selbst als Bezeichner für den Knoten im Dot-Code genommen wird. Weil bei mir jeder Wert nur einmal vorkommen kann, geht das auf. Falls bei dir ein Wert mehrmals vorkommen kann, musst du labels benutzen und mitzählen. Da kannst du dich da dran orientieren, wie ich das mit den nil-Knoten gemacht habe. Es gibt zwar viele Knoten, an denen nil-steht, aber sie haben alle einen eindeutigen Bezeichner, den ich zusammengesetzt habe aus ihrer Links- bzw. Rechtsseitigkeit und aus dem Wert ihres Elternknotens.

    Und das war es dann auch schon. Ein "Digraph" scheint auch für deine Zwecke die richtige Struktur zu sein, falls nicht, lies dir die Dokumentation durch. Man muss nur eine lange Liste erzeugen, welche Knoten mit welchen anderen Knoten verbunden sind und die Bezeichner der Knoten müssen eindeutig sein. Wenn man bei der Ausgabe immer erst nach links geht, dann passt das zu dem, wie graphviz hinterher die Ausgabe erzeugt und man bekommt die korrekte links-rechts Anordnung.



  • Klingt recht interessant und danke für die Mühe das aufzuschreiben 🙂

    Denke wenn ich mal Zeit hab werde ich mir diese Methode genauer zu gemüte führen 🙂

    jedoch muss ich nach aufgabenstellung den Baum in ein Feld schreiben 😞

    Heisst ich muss irgendwie durch den baum wandern, wenn ich die ebene im Baum wechsel wechsel ich auch in die nächste zeile von meinem Feld.

    Ist wohl nicht so schwer nur komm ich nich auf den anfang...........

    Jemand einen Denkanstoss parat? 🙂


  • Mod

    borni85 schrieb:

    Jemand einen Denkanstoss parat? 🙂

    Oben in der Mitte anfangen, dann bei Verzweigung nach links eins nach unten und nach links und entsprechend bei rechts. Zurueck geht's dann automatisch mit dem Stack unrolling.

    void ausgabe(node* knoten, char *ausgabefeld, size_t pos_x, size_t pos_y, size_t length_x)
    {
      if (knoten)
      {
        sprintf(ausgabefeld + pos_x + pos_y * length_x, "%d", knoten->value);
        ausgabe(knoten->left, ausgabefeld, pos_x - length_x / (pos_y + 1), pos_y + 1);  
        ausgabe(knoten->right, ausgabefeld, pos_x + length_x / (pos_y + 1), pos_y + 1);
      }
    }
    
    int main()
    {
      // ...
      char foo[800] = {' '};
      ausgabe(root, foo, 40, 0, 80);
      for(int y = 0; y < 10; ++y)
      { 
        for(int x = 0; x < 80; ++x)
          putchar(foo[x + y * 80]);
        putchar('\n');
      }
    }
    

    Ist wahrscheinlich nicht ganz richtig, da eben schnell hier im Forum programmiert ,aber so geht das ungefaehr.



  • ok klingt irgendwie logisch 🙂

    ich habs mal versucht einzubauen und das programm aufs wesentliche zu reduzieren.

    Jedoch kriege ich bei der Funktion sprintf immer Probleme. Kann es daran liegen, dass ich ja eigentlich mit int werten im Baum Arbeite und so wie ich das rausgefunden habe sprintf für char is?

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    struct Baum
    {
    	int zahl;
    	struct Baum *links, *rechts;
    };
    
    void einsort(struct Baum *wurzel, struct Baum *zgr);
    
    void ausgabe(struct Baum *zgr, char *ausgabefeld, size_t pos_x, size_t pos_y, size_t length_x);
    
    int main(void)
    {
    	struct Baum *wurzel = NULL;
    	struct Baum *zgr;
    	int zahl;
    	char ausgabefeld[800] = { ' ' };
    
    	do
    	{
    		printf("Eingabe: ");
    		scanf_s("%d", &zahl);
    		if (zahl)
    		{
    			zgr = (struct Baum*)malloc(sizeof(struct Baum)); // neues element angelegt
    			zgr->zahl = zahl; // Element mit Wert von Zahl befüllt
    			zgr->links = zgr->rechts = NULL; // Zeiger des Elementes werden auf NULL gesetzt, dass ein Ende gefunden werden kann
    			if (wurzel == NULL) wurzel = zgr;
    			else einsort(wurzel, zgr); // Element soll über die Funktion einsort einsortiert werden
    
    		}
    	} while (zahl);
    
    	ausgabe(wurzel, ausgabefeld, 40, 0, 80);
    	for (int y = 0; y < 10; ++y)
    	{
    		for (int x = 0; x < 80; ++x)
    			putchar(ausgabefeld[x + y * 80]);
    		putchar('\n');
    	}
    
    	printf("\n");
    
    	return 0;
    }
    
    void einsort(struct Baum *wurzel, struct Baum *zgr)
    {
    	int flag = 1;
    	do
    	{
    		if (zgr->zahl < wurzel->zahl)
    		{
    			if (wurzel->links != 0) wurzel = wurzel->links; // gehe nach links
    			else
    			{
    				flag = 0;
    				wurzel->links = zgr;
    			}
    
    		}
    		else
    		{
    			if (wurzel->rechts != 0) wurzel = wurzel->rechts; // gehe nach rechts
    			else
    			{
    				flag = 0;
    				wurzel->rechts = zgr;
    			}
    		}
    
    	} while (flag);
    
    }
    
    void ausgabe(struct Baum *zgr, char *ausgabefeld, size_t pos_x, size_t pos_y, size_t length_x)
    {
    
    	if (zgr)
    	{
    		sprintf(ausgabefeld + pos_x + pos_y * length_x, "%d", zgr->zahl);
    		ausgabe(zgr->links, ausgabefeld, pos_x - length_x / (pos_y + 1), pos_y + 1, length_x);
    		ausgabe(zgr->rechts, ausgabefeld, pos_x + length_x / (pos_y + 1), pos_y + 1, length_x);
    	}
    }
    

  • Mod

    Jedoch kriege ich bei der Funktion sprintf immer Probleme.

    🙄 Was ist an dieser Fehlerbeschreibung falsch? Richtig: Es ist keine Fehlerbeschreibung!

    Kann es daran liegen, dass ich ja eigentlich mit int werten im Baum Arbeite und so wie ich das rausgefunden habe sprintf für char is?

    Nein, du hast sprintf nicht verstanden. Das ist wie printf, bloss dass es in ein char-array schreibt. Was es da rein schreibt, das kann das gleiche sein (und geht auch genau so) wie bei printf.



  • stimmt die beschreibung is etwas dürftig 🙂

    ich habs jetzt soweit, dass es fehlerfrei kompiliert.

    Es funktioniert auch, so dass er mir die rechten Zeiger gut formatiert ausgibt. nur dir linken zeiger lässt er alle weg 😞

    #ifdef _MSC_VER
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    struct Baum
    {
    	int zahl;
    	struct Baum *links, *rechts;
    };
    
    void einsort(struct Baum *wurzel, struct Baum *zgr);
    
    void ausgabe(struct Baum *zgr, char *ausgabefeld, size_t pos_x, size_t pos_y, size_t length_x);
    
    int main(void)
    {
    	struct Baum *wurzel = NULL;
    	struct Baum *zgr;
    	int zahl;
    	char ausgabefeld[800] = { ' ' };
    
    	do
    	{
    		printf("Eingabe: ");
    		scanf_s("%d", &zahl);
    		if (zahl)
    		{
    			zgr = (struct Baum*)malloc(sizeof(struct Baum)); // neues element angelegt
    			zgr->zahl = zahl; // Element mit Wert von Zahl befüllt
    			zgr->links = zgr->rechts = NULL; // Zeiger des Elementes werden auf NULL gesetzt, dass ein Ende gefunden werden kann
    			if (wurzel == NULL) wurzel = zgr;
    			else einsort(wurzel, zgr); // Element soll über die Funktion einsort einsortiert werden
    
    		}
    	} while (zahl);
    
    	ausgabe(wurzel, ausgabefeld, 40, 0, 80);
    	for (int y = 0; y < 10; ++y)
    	{
    		for (int x = 0; x < 80; ++x)
    			putchar(ausgabefeld[x + y * 80]);
    		putchar(' ');
    	}
    
    	printf("\n");
    
    	return 0;
    }
    
    void einsort(struct Baum *wurzel, struct Baum *zgr)
    {
    	int flag = 1;
    	do
    	{
    		if (zgr->zahl < wurzel->zahl)
    		{
    			if (wurzel->links != 0) wurzel = wurzel->links; // gehe nach links
    			else
    			{
    				flag = 0;
    				wurzel->links = zgr;
    			}
    
    		}
    		else
    		{
    			if (wurzel->rechts != 0) wurzel = wurzel->rechts; // gehe nach rechts
    			else
    			{
    				flag = 0;
    				wurzel->rechts = zgr;
    			}
    		}
    
    	} while (flag);
    
    }
    
    void ausgabe(struct Baum *zgr, char *ausgabefeld, size_t pos_x, size_t pos_y, size_t length_x)
    {
    
    	if (zgr)
    	{
    		sprintf(ausgabefeld + pos_x + pos_y * length_x, "%d", zgr->zahl);
    		ausgabe(zgr->links,ausgabefeld, pos_x - length_x , (pos_y + 1), length_x);
    		ausgabe(zgr->rechts, ausgabefeld, pos_x + length_x , (pos_y + 1), length_x);
    	}
    }
    

  • Mod

    Rechne doch mal aus, an welcher Stelle du landest, wenn du um die ganze Laenge nach links gehst.



  • naja, eigentlich muss ich ja für den ersten schritt nach links so gehen:

    ausgabe(zgr->links,ausgabefeld, pos_x -  (pos_x / 2) , pos_y + 1, length_x );
    

    nach rechts so:

    ausgabe(zgr->rechts, ausgabefeld, pos_x + (pos_x / 2) , pos_y + 1, length_x );
    

    funktioniert aber nur für die ersten zwei ebenen, dann passt des net mehr.

    Rein theoretisch betrachtet setzte ich ja den ersten wert auf (40/0)
    für die zweite ebene erhöhe ich y um 1.
    der nächste x.wert is ja eigentlich : x = letztes x - letzter x-wert / 2

    ausgabe(zgr->links,ausgabefeld,pos_x - pos_x / 2 , pos_y + 1, length_x );
    

    sieht soweit im test auch gut aus, wenn ich einen Baum aus linken Zeigern mache.

    wenn ich rechte eingebe rutscht der ständig in die nächste zeile. is die berechnung falsch?


  • Mod

    Hast du mal meinen Vorschlag probiert? Der war durchaus durchdacht (Aber nicht getestet). Die Idee war, dass so aufzubauen:

    A
          B               C
      D       E       F       G
    H    I J    K  L     M  N    O
    

    Womit mir auch glatt ein Fehler auffällt. Das muss eher so heißen:

    pos_x - length_x / pow(2,(pos_y + 2))
    

    Immer noch ungetestet. Aber erkennst du die Idee? Beachte, dass die y-Position in die Rechnung einfließt! Je weiter unten, desto kleiner die Verschiebungen.



  • das war aus deinem vorschlag nur ein bissche umgeschrieben 🙂

    ok ich probier mich heute abend nochmal, den y-wert mit einzurechnen


Anmelden zum Antworten