Binärbaum strukturiert ausgeben



  • Hallo zusammen,

    ich habe an meinem binären Baum mal weiter gebastelt. Habe es auch hinbekommen, jedoch mehr schlecht als recht. Es geht darum:

    ich möchte einen binären Baum strukturiert ausgeben, heisst

    5
    2 7
    1 3 6 8

    Dazu lese ich zahlen ein, sortiere sie. und schreibe sie in abhängigkeit von spalte und zeile in ein zweidimensionales feld. dieses gebe ich dann aus.

    jedoch habe ich bei der ausgabe etwas gemogelt. ich habe einen zähler eingebaut und durch probieren rausgefunden, dass der baum nur einmal ausgegeben wird bei einem bestimmten zählerwert. lasse ich den baum weg wird mir jedesmal wenn ein neues element hinzugefügt wird der baum erneut ausgegeben.

    hat wer eine idee ob der punkt wo ich in die ausgabe springe flasch ist?

    gruß daniel

    #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 LWR(struct Baum *zgr); 
    int nodecount(struct Baum *zgr); 
    void printTreeLevel(struct Baum *zgr, int, int,static int); 
    void printLevelorder(struct Baum *zgr); 
    int positionEbene(struct Baum *zgr);
    int positionSpalte(struct Baum *zgr); 
    //void FinalPrint(int Ausgabe[10][10]);
    void FinalPrint(int, static int, static int);
    
    int main(void) 
    { 
      struct Baum *wurzel = NULL; 
      struct Baum *zgr; 
      int zahl; 
      int z = 0;
      int er = 0;
    
      do 
      { 
        printf("Eingabe: "); 
        scanf("%d", &zahl); 
        if (zahl) 
        { 
          zgr = calloc(1,sizeof*zgr); // 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); 
      /*LWR(wurzel);*/ 
      /*printf("\n\nnodes: %d\n\n", nodecount(wurzel)); */
      printLevelorder(wurzel); 
    
      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 LWR(struct Baum *zgr) // Links Wurzel Rechts - aufsteigend sortiert 
    //{ 
    //  if (zgr == NULL) 
    //    return; 
    //  if (zgr->links != NULL) LWR(zgr->links); 
    //  printf(" %d", zgr->zahl); 
    //  if (zgr->rechts != NULL) LWR(zgr->rechts); 
    //} 
    
    // Zählen der Knoten im Baum 
    int nodecount(struct Baum *zgr) 
    { 
      if (zgr == NULL) 
        return 0; 
      if (zgr->links == NULL && zgr->rechts == NULL) 
        return 1; 
      else 
        return nodecount(zgr->links) + 
        nodecount(zgr->rechts); 
    } 
    
    #define MAXX(x,y) ((x)>(y)?(x):(y)) 
    int maxTreeDepth(struct Baum *zgr, int level) 
    { 
      if (zgr == NULL) 
        return 0; 
    
      if (zgr->links == NULL && zgr->rechts == NULL) 
        return level; 
    
      return MAXX(maxTreeDepth(zgr->links, level + 1), maxTreeDepth(zgr->rechts, level + 1)); 
    } 
    
    // Alle Knoten einer Stufe ermitteln 
    void printTreeLevel(struct Baum *zgr, int level, int zlevel, static int sp) 
    {
    	static int Ausgabe[2][8] = {0};
    	static int count = 0;
    	int a = 0;
    
    	if (zgr == NULL) 
        return; 
    	if (level == zlevel) 
      { /*printf("SP = [%d]", sp);
    	printf("COUNT = [%d]", count);*/
    
    	  Ausgabe[level][sp] = zgr-> zahl;
    
    	 return; 
      } 
      else 
      {
    
    	  if (level == 0)
    	  {
    		  a = 2;
    	  }
    	  if (level == 1)
    	  {
    		  a = 1;
    	  }
    	 /* if (level == 2)
    	  {
    		  a = 1;
    	  }*/
    
    	  printTreeLevel(zgr->links, level + 1, zlevel,sp - a);
    
    	  printTreeLevel(zgr->rechts, level + 1, zlevel, sp + a);
    	  count ++;
    
      } 
    	if (count == 4)
    	{
    		 FinalPrint(level, sp, Ausgabe);
    	}
    
    } 
    
    void FinalPrint(int level,static int sp, static int Ausgabe[2][8])
    {
    	int i, j;
    
      for (i = 0; i < 3; i++)
      {
        for(j = 0; j < 8; j++)
        {
    		if (Ausgabe[i][j] == 0)
    		{
    			printf(" \t ");
    		}
    		else
    		{
    		printf("%d \t  ", Ausgabe[i][j]);
    		}
        }
        printf("\n \n \n");
      }
    }
    // Traversierung in Levelorder 
    void printLevelorder(struct Baum *zgr) 
    { 
      int i, j = maxTreeDepth(zgr, 0); 
      static int sp = 4;
      for (i = 0; i <= j; ++i, puts("")) 
        printTreeLevel(zgr, 0, i,sp) ; 
    }
    

  • Mod

    Wenn dein finalPrint in der Funktion aufgerufen wird, die rekursiv duch den Baum wandert, dann wird es natuerlich auch fuer jede Instanz dieser Funktion aufgerufen. Deine if-Abfrage viorher prueft ja nur, ob das tiefste Level erreicht wurde. Dies wird aber (in deinem Beispiel) 4 x erreicht (1,3,6 und 8).

    Fuer solche Probleme ist uebrigens ein Debugger gut.

    Das Ganze koennte man auch ohne static Variablen machen und gleichzeitig dein Problem loesen:
    -Eine Ausgabefunktion, die ein passendes Array besorgt.
    -Diese ruft die rekursive Durchlauffunktion auf, die dann in das Array schreibt
    -Danach gibt die Ausgabefunktion das Array aus



  • So, ich hab mich nochmal probiert und mich bemüht, es so umzuschreiben, wie mir geraten wurde.

    Weiss jemand ob ich so besser liege?

    Kriege jedoch die Fehlermeldung:

    1>Quelle.obj : error LNK2019: Verweis auf nicht aufgelöstes externes Symbol "_PrintTreeLevel" in Funktion "_FinalPrint".

    Hier nochmal die aktualisierten Funktionen. Bin für jeden Tipp dankbar, verzweifle nämlich langsam dran................

    #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 LWR(struct Baum *zgr);
    int nodecount(struct Baum *zgr);
    int printTreeLevel(struct Baum *zgr, int level, int zlevel, static int sp, int Ausgabe[2][8]);
    void printLevelorder(struct Baum *zgr);
    int positionEbene(struct Baum *zgr);
    int positionSpalte(struct Baum *zgr);
    //void FinalPrint(int Ausgabe[10][10]);
    void FinalPrint(struct Baum * zgr, int level, int zlevel, static int sp);
    
    int main(void)
    {
    	struct Baum *wurzel = NULL;
    	struct Baum *zgr;
    	int zahl;
    	int z = 0;
    	int er = 0;
    
    	do
    	{
    		printf("Eingabe: ");
    		scanf("%d", &zahl);
    		if (zahl)
    		{
    			zgr = calloc(1, sizeof*zgr); // 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);
    	/*LWR(wurzel);*/
    	/*printf("\n\nnodes: %d\n\n", nodecount(wurzel)); */
    	printLevelorder(wurzel);
    
    	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 LWR(struct Baum *zgr) // Links Wurzel Rechts - aufsteigend sortiert
    //{
    //  if (zgr == NULL)
    //    return;
    //  if (zgr->links != NULL) LWR(zgr->links);
    //  printf(" %d", zgr->zahl);
    //  if (zgr->rechts != NULL) LWR(zgr->rechts);
    //}
    
    // Zählen der Knoten im Baum
    int nodecount(struct Baum *zgr)
    {
    	if (zgr == NULL)
    		return 0;
    	if (zgr->links == NULL && zgr->rechts == NULL)
    		return 1;
    	else
    		return nodecount(zgr->links) +
    		nodecount(zgr->rechts);
    }
    
    #define MAXX(x,y) ((x)>(y)?(x):(y))
    int maxTreeDepth(struct Baum *zgr, int level)
    {
    	if (zgr == NULL)
    		return 0;
    
    	if (zgr->links == NULL && zgr->rechts == NULL)
    		return level;
    
    	return MAXX(maxTreeDepth(zgr->links, level + 1), maxTreeDepth(zgr->rechts, level + 1));
    }
    
    // Alle Knoten einer Stufe ermitteln
    int printTreeLevel(struct Baum *zgr, int level, int zlevel, static int sp, int Ausgabe[2][8])
    {
    	int a = 0;
    
    	if (zgr == NULL)
    		return;
    	if (level == zlevel)
    	{ /*printf("SP = [%d]", sp);
    	  printf("COUNT = [%d]", count);*/
    
    		Ausgabe[level][sp] = zgr->zahl;
    
    		return;
    	}
    	else
    	{
    
    		if (level == 0)
    		{
    			a = 2;
    		}
    		if (level == 1)
    		{
    			a = 1;
    		}
    		/* if (level == 2)
    		{
    		a = 1;
    		}*/
    
    		printTreeLevel(zgr->links, level + 1, zlevel, sp - a, Ausgabe);
    
    		printTreeLevel(zgr->rechts, level + 1, zlevel, sp + a, Ausgabe);
    	}
    
    	return (Ausgabe);
    
    }
    
    void FinalPrint(struct Baum * zgr, int level, int zlevel, static int sp)
    {
    	int i, j = 0;
    	int Ausgabe[2][8] = { 0 };
    
    	PrintTreeLevel(zgr, 0, zlevel, sp, Ausgabe);
    
    	for (i = 0; i < 3; i++)
    	{
    		for (j = 0; j < 8; j++)
    		{ 
    			printf("%d", Ausgabe[i][j]);
    		}
    		printf("\n");
    	}
    	printf("\n");
    
    }
    // Traversierung in Levelorder
    void printLevelorder(struct Baum *zgr)
    {
    	int i, j = maxTreeDepth(zgr, 0);
    	static int sp = 4;
    	for (i = 0; i <= j; ++i, puts(""))
    		FinalPrint(zgr, 0, i, sp);
    }
    


  • Achte auf Groß- und Kleinschreibung!



  • ok, danke habs gefunden. Ausversehen ein großes P geschrieben *_*

    jedoch kriege ich nür müll raus.

    irgendwie gibt er nur adressen raus und hängt sich dann auf 😞


  • Mod

    Das kann gar nicht compilieren. Du hast ein static vor einem Funktionsparameter! Mehrmals! Du returnst ohne Wert aus Funktionen mit Rückgabewert. Du scheinst irgendwie Arrays als Rückgabewert nutzen zu wollen, was Unsinn ist. Aber dann ignorierst du dir Rückgabewerte sowieso.

    Das gucke ich mir weder genauer an, noch debugge ich das, bevor das Programm nicht fehler- und warnungsfrei compiliert.

    P.S.: Von deinem Linkerfehler her habe ich auch den Verdacht, dass du einen C++-Compiler nutzt. Tu das nicht! Der MSVC kann auch C, wenn man ihm sagt, dass er C benutzen soll.

    P.S.: Hier mal die Warnungen und Fehler, die der GCC zu deinem Programm hat:

    test.c:22:72: error: storage class specified for parameter ‘sp’
     int printTreeLevel(struct Baum *zgr, int level, int zlevel, static int sp, int Ausgabe[2][8]);
                                                                            ^
    test.c:27:70: error: storage class specified for parameter ‘sp’
     void FinalPrint(struct Baum * zgr, int level, int zlevel, static int sp);
                                                                          ^
    test.c: In function ‘main’:
    test.c:36:9: warning: unused variable ‘er’ [-Wunused-variable]
         int er = 0;
             ^
    test.c:35:9: warning: unused variable ‘z’ [-Wunused-variable]
         int z = 0;
             ^
    test.c: At top level:
    test.c:129:72: error: storage class specified for parameter ‘sp’
     int PrintTreeLevel(struct Baum *zgr, int level, int zlevel, static int sp, int Ausgabe[2][8])
                                                                            ^
    test.c: In function ‘PrintTreeLevel’:
    test.c:134:9: warning: ‘return’ with no value, in function returning non-void [enabled by default]
             return;
             ^
    test.c:141:9: warning: ‘return’ with no value, in function returning non-void [enabled by default]
             return;
             ^
    test.c:165:5: warning: return makes integer from pointer without a cast [enabled by default]
         return (Ausgabe);
         ^
    test.c: At top level:
    test.c:169:70: error: storage class specified for parameter ‘sp’
     void FinalPrint(struct Baum * zgr, int level, int zlevel, static int sp)
                                                                          ^
    test.c: In function ‘FinalPrint’:
    test.c:172:5: warning: missing braces around initializer [-Wmissing-braces]
         int Ausgabe[2][8] = { 0 };
         ^
    test.c:172:5: warning: (near initialization for ‘Ausgabe[0]’) [-Wmissing-braces]
    test.c:169:40: warning: unused parameter ‘level’ [-Wunused-parameter]
     void FinalPrint(struct Baum * zgr, int level, int zlevel, static int sp)
                                            ^
    

    Und er hat Recht, bei allem, außer den Klammern bei der Initialisierung von Ausgabe (Das kann zwar ein paar mehr Klammern vertragen, sie sind aber nicht unbedingt nötig).



  • ok, seh ich ein 🙂

    ich habs mal komplett umgeschrieben.

    Ich hab jetzt eine Ausgabe, die mir jede Ebene des Baumes untereinander ausgibt. sprich ich gebe ein:

    5, 6, 1, 7, 8, 9

    Ausgabe:
    5
    16
    7
    8
    9

    Ist soweit ja ganz ok. jedoch möchte ich ja eine strukturierte Ausgabe, dass es aussieht wie ein Baum.

    Meine Idee ist ja:

    ich erzeuge ein 2. dimensionales Feld, und müsste mir den Versatz halt ausrechnen. bei zgr->links gehe ich eine Spalte nach links, bei zgr->rechts gehe ich eine Spalte nach rechts. und schreibe dies dann in des Feld und gebe das Feld dann aus.

    Jedoch kriege ich dass programmtechnisch irgendwie net zu packen. kann mir jemand einen Anfang geben, wie ich das am besten aufziehen?

    #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 LWR(struct Baum *zgr);
    int nodecount(struct Baum *zgr);
    int maxTreeDepth(struct Baum *zgr);
    void printTreeLevel(struct Baum *zgr);
    void printLevelorder(struct Baum *zgr);
    
    int main(void)
    {
    	struct Baum *wurzel = NULL;
    	struct Baum *zgr;
    	int zahl;
    
    	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);
    	LWR(wurzel);
    	printf("\n");
    	nodecount(wurzel);
    	maxTreeDepth(wurzel);
    	printTreeLevel(wurzel);
    	printLevelorder(wurzel);
    
    	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 LWR(struct Baum* zgr) // Links Wurzel Rechts - aufsteigend sortiert
    {
    	if (zgr->links != NULL) LWR(zgr->links);
    	printf(" %d", zgr->zahl);
    	if (zgr->rechts != NULL) LWR(zgr->rechts);
    
    }
    // Zählen der Knoten im Baum
    int nodecount(struct Baum*  zgr)
    {
    	static int count = 0;
    
    	if (zgr == NULL) return 1;
    	else
    	{
    		count++;
    		nodecount(zgr->links);
    		nodecount(zgr->rechts);
    	}
    	/*printf("counts : %d\n", count);*/
    	return count;
    }
    
    /*Ermitteln der maximalen Tiefe des Baumes*/
    int maxTreeDepth(struct Baum *zgr)
    {
    	int lheight = 0;
    	int rheight = 0;
    
    	if (zgr == NULL) return -1;
    	else
    	{
    		lheight = maxTreeDepth(zgr->links);
    		rheight = maxTreeDepth(zgr->rechts);
    	}
    	/*printf("linke laenge: %d ------ rechts laenge: %d \n", lheight, rheight);*/
    
    	return (lheight > rheight) ? lheight + 1 : rheight + 1;
    }
    
    // Alle Knoten einer Stufe ermitteln
    void printTreeLevel(struct Baum *zgr, int level)
    {
    	if (zgr == NULL || level <= 0) return;
    
    	/*if (zgr != NULL && level >0) */
    	if (level == 1)
    	{
    		printf("%d ", *zgr);
    	}
    	else
    	{
    		printTreeLevel(zgr->links, level - 1);
    		printTreeLevel(zgr->rechts, level - 1);
    
    	}
    
    }
    
    /*Traversierung in Levelorder */
    void printLevelorder(struct Baum *zgr)
    {
    	int size = 0;
    	int i = 0;
    
    	size = maxTreeDepth(zgr) + 1;
    	for (i = 1; i <= size; i++)
    	{
    		printTreeLevel(zgr, i);
    		printf("\n");
    	}
    
    }
    


  • 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


Log in to reply