Binärere Baum/ Levelorder



  • so hab den Code jetzt soweit abgeändert.
    Die Levelvariable brauch ich eigentlich schon, weil Sie soll mir ja die ebenen angeben und nach jeder ebene einen Cut machen, das es auch eine Levelorder ausgabe wird.

    Fehler zeigt mir mein programm nun nicht an, jedoch hängt es sich auf, ich tippe auf eine endlos Schleife?

    #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);
    void printTreeLevel(struct Baum *zgr);
    void printLevelorder(struct Baum *zgr);
    int nodecount(struct Baum *zgr);

    int main()
    {
    struct Baum *wurzel = NULL;
    struct Baum *zgr;
    int zahl;

    do
    {
    printf("Eingabe: ");
    scanf("%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);
    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 -> links == NULL) return 0;
    count ++;
    nodeCount(zgr->links);
    nodeCount(zgr->rechts);
    printf("%d\n", count);
    return count;
    }

    //Ermitteln der maximalen Tiefe des Baumes
    int maxTreeDepth(struct Baum *zgr)
    {
    int lheight = 0;
    int rheight = 0;

    //if (wurzel == NULL) return 0;

    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->zahl == NULL) return;

    if (level == 1)
    printf("%d ", zgr->zahl);
    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(" ");
    }

    }



  • Editier deinen Beitrag bitte nochmal und setzte die Code-Tags.
    Am Anfang vom Code (den Cursor dahin setzen) einmal auf den C++-Button unter den 🙂 😃 klicken.
    Dann bekommt der Button einen *. Am Ende vom Code nochmal.

    Oder den Code mit der Maus markieren und einmal auf den C++Button klicken.

    So schaut den kaum einer an.



  • So hier nochmal mein richtig editierter Code.

    Mein Problem: Eine fehlermeldung bekomme ich nicht mehr, jedoch kein Ergebnis.
    Ich gehe stark davon aus das meine Übergabe und Rückgabewerte nicht passen. Finde jedoch den fehler nicht, bin also für jeden Tipp dankbar 🙂

    #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("%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 -> links == NULL) return 0; 
      count ++; 
      nodecount(zgr->links); 
      nodecount(zgr->rechts); 
      printf("%d\n", count); 
      return count; 
    } 
    
    //Ermitteln der maximalen Tiefe des Baumes 
    int maxTreeDepth(struct Baum *zgr) 
    { 
      int lheight = 0; 
      int rheight = 0; 
    
      if (zgr->zahl == 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->zahl == NULL || level <= 0) return; 
    
      if (zgr->zahl != NULL && level >0) 
        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(" "); 
        } 
    
    }
    


  • borni85 schrieb:

    So hier nochmal mein richtig editierter Code.

    Du hättest auch deinen letzten Post editieren können. (Als registrierter Nutzer geht das)

    borni85 schrieb:

    Mein Problem: Eine fehlermeldung bekomme ich nicht mehr,

    Dann beachte die Warnungen. Wenn du keine bekommst, stell den Warnlevel höher ein.
    Beispiel in printTreeLevel

    struct Baum *zgr
    ...    printf("%d ", *zgr);
    

    Mag ja sein, dass an der Stelle, auf die zgr verweist, auch ein int liegt. Das ist dem Compiler aber egal, da er eine struct Baum dereferenziert.

    borni85 schrieb:

    jedoch kein Ergebnis.

    Du machst auch sehr wenig Ausgaben.
    Zudem schreibst du auch nicht, was du eingibst, was passiert und was du erwartest.
    Wie weit kommt das Programm überhaupt?

    Zeiger kannst du bei printf mit %p ausgeben.
    Oder nutze den Debugger.



  • Also mein Programm bleibt im Debugger bei Zeile 110 stehen. Fehlermeldung: Speicher con zgr kann nicht gelesen werden.

    Ich gebe am Anfang 3 Zahlen ein, meistens nehme ich 5,6,1................ diese sollen über einsort einsortiert werden: 5 = Wurzel, 6 ist größer also rechts hin und 1 ist kleiner also links hin

    Dann soll die Knotenanzahl ausgegeben werden (wäre hier 3), sowie die länge des linken und rechten Baumes(wäre hier 1)

    Am schluss soll eine gesammte ausgabe nach dem format
    5
    1 6

    erfolgen



  • borni85 schrieb:

    Also mein Programm bleibt im Debugger bei Zeile 110 stehen. Fehlermeldung: Speicher con zgr kann nicht gelesen werden.

    Das ist doch schon mal eine Aussage.

    Schaun wir mal:

    if (zgr->zahl == NULL) return -1 ;
    

    zgr->zahl ist vom Typ int. NULL ist für Zeiger gedacht. Der Vergleich ist also schon mal seltsam. Aber ....

    ... was ist, wenn zgr selbst schon NULL ist. Dann solltest du ihn auch nicht verwenden.

    In der Funktion printTreeLevel hast du das auch noch.

    borni85 schrieb:

    Ich gebe am Anfang 3 Zahlen ein, meistens nehme ich 5,6,1................ diese sollen ....
    Dann soll ....
    Am schluss soll ...

    Aber was passiert? Was wird ausgegeben?

    Aus dem Fehler in Zeile 110 kann man zwar schließen, dass einsortieren, LWR und nodecount durchlaufen. Ob das fehlerfrei ist, weiß man aber nicht.



  • zgr->zahl
    

    dereferenziert den Zeiger zgr.
    Falls zgr == NULL ist, dereferenzierst du einen unbestimmten Zeiger, und dein Laufzeitsystem bricht ab (wenn du Glück hast).

    http://ideone.com/ZEWrUi

    #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);
    void printLevelorder(struct Baum *zgr);
    
    int main(void)
    {
      struct Baum *wurzel = NULL;
      struct Baum *zgr;
      int zahl;
    
      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)
    {
      if (zgr == NULL)
        return;
      if (level == zlevel)
      {
        printf("%d ", zgr->zahl);
        return;
      }
      else
      {
        printTreeLevel(zgr->links, level + 1, zlevel);
        printTreeLevel(zgr->rechts, level + 1, zlevel);
      }
    }
    
    // Traversierung in Levelorder
    void printLevelorder(struct Baum *zgr)
    {
      int i, j = maxTreeDepth(zgr, 0);
      for (i = 0; i <= j; ++i, puts(""))
        printTreeLevel(zgr, 0, i) ;
    }
    


  • Ich habe die genannten Fehler auch gerade gesehen und behoben.

    also es läuft 🙂 ich gebe 5,6,1 ein

    nodecount = 3 passt auch.
    die levelorder ausgabe lautet:
    5
    16

    passt soweit 🙂

    hat jemand eine Idee wie ich das auch noch als Grafischen Baum ausgeben kann?
    5
    1 6

    Ich habe überlegt ein zweidimensionales array einzulesen und das von unten nach oben zu befüllen? habe ja die Knotenzahl und die länge der Zweige in der Untefunktion

    #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("%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 "); 
        } 
    
    }
    


  • Danke Danke Wutz 🙂

    meins hat jetzt auch funktioniert, sieht natürlich nicht so gut aus wie deins 🙂 habs mal übernonmmen und versuche es nachzuvollziehen 🙂

    Hast du auch noch eine prinzipielle Idee, wie ich den Baum als Struktur ausgeben kann? also:

    5
    1 6

    Meine Idee ist ein ein oder zweidimensionales Feld, welches ich von oben nach unten fülle und dann ausgebe. Jedoch fehlt mir der Ansatz zu ermitteln, welche Stelle im Baum besetzt ist -



  • static zu verwenden, ist immer fragil; du handelst dir da unnötige Abhängigkeiten beim aufrufenden Kontext ein; mehrfache Aufrufe der Funktion ergeben unterschiedliche Ergebnisse. Das will man in den allermeisten Fällen NICHT.

    Die (formatierte) Baumstruktur auszugeben wäre möglich, indem du für jedes 1. (linke) Element jedes Levels die Anzahl der (noch weiter) linken Vorgänger aller anderen Level bestimmst und dafür dann Leerzeichen voranstellst.



  • Du könntest ein Array mit Zeigern auf deine struct machen.

    An erster Stelle steht die Wurzel. An zweiter und dritter Stelle der linke und rechte Ast.
    Da sich die Anzahl nach jeder Verzweigung verdoppelt, kannst du auch die Positionen berechnen.

    Ein unbesetzter Zweig ist halt NULL.



  • Also, meine Idee ist die folgende:
    Ich habe ja eine Struktur, die so aussehen soll:
    x
    xx
    xxxx
    xxxxxxxx

    die erste eben ist ja klar: wurzel gesetzt.
    ist der zweiten ebene steht ja der zgr. links und der zgr. rechts. in der nächsten ebene ja wieder jeweils linker und rechter zeiger.

    ich habe vorbereitend zwei funktionen geschrieben um den "weg" zu berechnen. einmal für die Ebene und einmal zur ermittlung der Zeile. Mit diesen beiden werten möchte ich dann die jeweilige Position im Feld bestimmen.

    Mit der ebene funktioniert auch soweit.
    Bei der Spalte habe ich das folgende Problem: ich möchte für links gehen die -1 zurückgeben, für rechts eine 1. jedoch rechnet er mir das net zusammen sondern gibt jeweils nur den letzten wert zurück. Hat jemand eine Idee das zu verbessern?
    Desweiteren möchte ich ja quasi für jeden einzelnen zeiger ebene und zeile haben, jedoch kriege ich nur einen durchlauf für den ganzen baum hin 😞

    Zugriff aus der main:

    er = positionEbene(wurzel);
      z =  positionSpalte(wurzel);		//z ist Rückgabewert aus der Funktion positionSpalte
    									// muss in der main deklariert werden und aufgezeigt, wo es herkommt
    
       printf("Ebene: [%d]\n", er);
      printf("Zeile: [%d]\n", z);
    

    Unterfunktionen:

    int positionEbene(struct Baum *zgr)
    {
    	/*int feld[];*/
    	static int er = 0;		// Ebene im Baum
    	int s = 0;		// Zeile im Baum
    
    	if (zgr == NULL) return 0;
    
    	if (zgr->links != NULL || zgr->rechts !=0)
    	{
    		printf("Ebene(Anfang Schleife): [%d]\n", er);
    
    			er++;		
    			positionEbene(zgr->links);
    			positionEbene(zgr->rechts);
    
    			return er;
    
    	}
    
    //Berechnen der Spalten
    int positionSpalte(struct Baum *zgr)
    {
    	static int z = 0;		//Spalte im Baum
    	int k = 0;
    
    	if (zgr == NULL) return 0;
    
    	if (zgr->links != NULL)
    	{
    		z --;
    		positionSpalte(zgr->links);
    		return z;
    
    	}
    
    	if(zgr->rechts != NULL)
    		{
    			z ++;
    			positionSpalte(zgr->rechts);
    			return z;
    		}
    
    }
    

Anmelden zum Antworten