Frage zu binärem Baum
-
Wird die Wurzel niemals ausgegeben beim binären Baum oder sollte diese mit ausgegeben werden. Bei meinem Programm ist das jedenfalls so, dass das erste Element, welches ich eingebe auch nicht bei der Ausgabe dabei ist.
// Includes #include <stdio.h> #include <stdlib.h> #include <string.h> // Einfacher eigener Datentyp node typedef struct node { char *name; struct node *parent; struct node *left; struct node *right; } node; // Funktionsdefinitionen node *create_node(void); int insert_node(char *s); int delete_node(char *s); int show_tree(node *knoten); node *anfang; int main(void) { //Auswahl int choice=99; //Name des zu erstellenden Knotens char newname[10]; //Name des zu loeschenden Knotens char delname[10]; printf("BinaerBaum mit Loeschfunktion\n\n\n"); //...letzendlich die Abbruchbedingung fuer das ganze Programm while (choice!=0) { printf("Knoten erstellen (1),loeschen (2),ausgabe (3) oder exit (0): "); scanf("%d",&choice); //Menuefuehrung switch(choice) { case 1: printf("\nBitte Bezeichnung des Knotens waehlen\n"); //Eingabe des Bezeichners fuer den neuen Knoten scanf("%s",newname); //Erstellt den neuen Knoten insert_node(newname); printf("\nKnoten %s erstellt\n",newname); break; case 2: printf("\nBitte die EXAKTE(!!!) Bezeichnung des zu loeschenden Knotens eingeben\n"); //Dasselbe in Gruen... scanf("%s",delname); delete_node(delname); printf("\nKnoten %s geloescht\n",delname); break; case 3: printf("\n Baum wird ausgegeben:\n\n"); // Gib den Baum aus show_tree(anfang); break; } printf("\n\n\n\n"); } printf("Programmende\n\n"); return 0; } // Erstelle einen neuen Knoten (Speicher reservieren + Anfangswerte setzen) node *create_node(void) { // Reserviere Speicher fuer einen neuen Knoten node *knoten = malloc(sizeof(struct node)); // Startwerte setzen knoten->name = NULL; knoten->parent = NULL; knoten->left = NULL; knoten->right = NULL; return knoten; } // Fuege einen neuen Knoten in den Baum ein int insert_node(char *s) { node *knoten, *current, *last; int richtung = 0; int vergleich = 0; // Neuen Knoten erstellen if( (knoten = create_node()) == NULL) { printf("Duh! We ran out of memory! :-(\n"); exit(1); } // Speicher fuer den String allokieren knoten->name = malloc(sizeof(*s)); strcpy(knoten->name,s); // Hat der Baum schon eine Wurzel? if(anfang == NULL) { anfang = knoten; } else { // Hangel Dich vom Anfang durch den Baum... current = anfang; // ...und suche die passende Speicherstelle while(current != NULL) { // Merke Dir den letzten Ast last = current; // Vergleiche die Strings vergleich = strcmp(knoten->name,current->name); // Wenn der einzufuegende String "kleiner" ist, // dann gehts links lang if(vergleich < 0) { richtung = 0; current = current->left; } // Wenn er groesser ist, gehts rechts lang else if(vergleich > 0) { richtung = 1; current = current->right; } // Diesen String gibt es schon im Baum else { printf("insert_node(): String %s exists!\n",s); return 1; } } // Vater des einzufuegenden Knotens setzen knoten->parent = last; // Ist der neue Knoten links oder rechts vom Vater? if(richtung == 0) { last->left = knoten; } else { last->right = knoten; } } return 0; } // Loesche einen Knoten aus dem Baum int delete_node(char *s) { node *current, *parent, *new; int vergleich = 0; int richtung = 0; // Suche den zu loeschenden Knoten current = anfang; while(current != NULL) { // Vergleiche die Strings vergleich = strcmp(s,current->name); // Wenn der String "kleiner" ist, bieg links ab if(vergleich < 0) { richtung = 0; current = current->left; } // Ist der String "groesser", bieg rechts ab else if(vergleich > 0) { richtung = 1; current = current->right; } // Wir haben den passenden Knoten gefunden else { break; } } // Keinen passenden Eintrag gefunden? if(current == NULL) { printf("delete_node(): Cant find node %s!\n",s); return 1; } // Loeschen wir gerade das Wurzel Element? if(current == anfang) { // Ist das Wurzel Element das letzte Element des Baums? if( (current->left == NULL) && (current->right == NULL) ) { anfang = NULL; } else { // Gibt es einen linken Knoten? if(current->left != NULL) { anfang = current->left; } // Ansonsten wird der rechte genommen else { anfang = current->right; } } } // Es wird nicht das Wurzel Element geloescht else { // Hat der zu loeschende Knoten noch Kindknoten? if( (current->left != NULL) || (current->right != NULL) ) { // Falls es einen linken Knoten gibt, nimmt dieser // den Platz des zu loeschenden ein if(current->left != NULL) { new = current->left; } // Ansonsten wird der rechte genommen else { new = current->right; } } else { new = NULL; } // An welchem Ast des Vaters haengt der zu loeschende Knoten? parent = current->parent; if(richtung == 0) { parent->left = new; } else { parent->right = new; } } // Speicher des Knotens deallozieren free(current); return 0; } int show_tree(node *knoten) { if(knoten != NULL) { // Funktion rekursiv fuer den linken und rechten Ast aufrufen show_tree(knoten->left); // String ausgeben if (knoten->parent != 0) // printf("%s hat den Elternknoten %s\n",knoten->name,knoten->parent->name); printf("%s\n",knoten->name); show_tree(knoten->right); } return 0; }
-
hm, versteh ich gerade nicht so ganz. die knoten werden doch eh nicht ausgegeben, nur die verbindungen, nämlich 0 für "links" und 1 für "rechts"
-
Zu dem "Weg" hab ich 'ne Frage.
Wie wird das dann implementiert? Soll ich eine bool variable(weil nur 1 oder 0 ) in die struct mit einbringen, also bool way; oder wie sieht das dann aus? Kann ich die "Wegvariablen"Variante denn dadruch umgehen, dass ich ein Zeiger auf den Elternbaum habe?
-
ein zeiger ist unnötig, am besten ist du hast in der struktur drei felder, z.B. "linkerAst", "rechterAst", "elterAst" vom typ int, die die id des jeweiligen knoten, sprich array-element, haben.