/****************************************************************/ /* Prof. Dr. Carsten Vogt */ /* FH Koeln, Fak. 07 / Nachrichtentechnik */ /* http://www.nt.fh-koeln.de/vogt */ /* */ /* Beispielprogramme Nr. 67-69 */ /* der frueheren Vorlesung Datenverarbeitung */ /* */ /* Das Programm gibt einen Baum auf verschiedene Arten aus: */ /* - Alle Eintraege in einer Zeile, wahlweise in Pre-, In- oder */ /* Postorder (Bsp. 67) */ /* - Jeder Eintrag in einer eigenen Zeile, seinem Niveau ent- */ /* sprechend eingerückt (Bsp. 68) */ /* - Als ASCII-Grafik mit Kanten zwischen den Knoten (Bsp. 69) */ /* */ /* Als Beispiel dient der Strukturbaum eines arithmetischen */ /* Ausdrucks. Es kann ein beliebiger Ausdruck in Praefixnota- */ /* tion eingegeben werden (z.B. *+12-34 für (1+2)*(3-4)), */ /* woraus das Programm dann den Baum erzeugt. */ /****************************************************************/ #include #include #include #include /**********************************/ /* Typdefinition für Baumelemente */ /**********************************/ typedef struct treeelem { char wert; /* Eintrag des Baumknotens */ struct treeelem *left; /* Zeiger auf li. Sohn */ struct treeelem *right; /* Zeiger auf re. Sohn */ } treeelem; /**********************************************/ /* Beispiel 67: Durchlaufen der Baumeintraege */ /* wahlweise in Pre-In- oder Post-Order. */ /**********************************************/ #define preorder 0 #define inorder 1 #define postorder 2 void durchlauf(treeelem *baum,int order) { /* baum: zu durchlaufender Baum order: Durchlaufreihenfolge */ if (baum==NULL) return; switch(order) { case preorder: /* Wurzel -> linker Unterbaum -> rechter Unterbaum */ printf("%c ",baum->wert); durchlauf(baum->left,order); durchlauf(baum->right,order); break; case inorder: /* linker Unterbaum -> Wurzel -> rechter Unterbaum */ durchlauf(baum->left,order); printf("%c ",baum->wert); durchlauf(baum->right,order); break; case postorder: /* linker Unterbaum -> rechter Unterbaum -> Wurzel */ durchlauf(baum->left,order); durchlauf(baum->right,order); printf("%c ",baum->wert); break; } /* Ende von switch */ } /*****************************************************/ /* Beispiel 68: Ausgabe der Baumstruktur zeilenweise */ /* mit entsprechenden Einrueckungen */ /*****************************************************/ void drucke_rek_bsp68(treeelem *baum,int space) { /* baum: auszugebender Baum. space: Einrückung des Wurzeleintrags */ const int tab=4; /* Tabulatorwert */ int i; /* Laufindex */ if (baum==NULL) /* leerer Baum: nichts zu tun */ return; /* Ausgabe des rechten Unterbaums. Dabei Einrueckung um eine weitere Tabulatorstufe */ drucke_rek_bsp68(baum->right,space+1); /* Einrueckung für den Wurzeleintrag */ for (i=1;i<=space*tab;i++) printf(" "); /* Ausgabe des Wurzeleintrags */ printf("%c\n",baum->wert); /* Ausgabe des linken Unterbaums. Dabei Einrueckung um eine weitere Tabulatorstufe */ drucke_rek_bsp68(baum->left,space+1); } void drucke_bsp68(treeelem *baum) { /* Ausgabe des Gesamtbaums baum mit Hilfe von drucke_rek_bsp68() */ drucke_rek_bsp68(baum,0); } /*********************************************/ /* Beispiel 69: Ausgabe der Baumstruktur als */ /* ASCII-Grafik */ /*********************************************/ void drucke_rek_bsp69(treeelem *baum, int left,int top,int right,int bottom) { /* baum: auszugebender Baum left, top, right, bottom: Teilfenster für die Ausgabe (linke obere und rechte untere Ecke) */ int i; /* Laufvariable */ if (baum==NULL) /* leerer Baum: nichts zu tun */ return; /* Definition eines Teilfensters */ window(left,top,right,bottom); /* Ausgabe einer senkrechten Kante */ gotoxy(1+(right-left)/2,1); printf(":"); gotoxy(1+(right-left)/2,2); printf(":"); /* Test, ob linker Unterbaum vorhanden */ if (baum->left!=NULL) { /* Wenn ja: Ausgabe einer Kante, die nach links fuehrt */ gotoxy((right-left)/4+1,3); for (i=(right-left)/4+1;i<(right-left)/2;i++) printf("-"); } /* Test, ob rechter Unterbaum vorhanden */ if (baum->right!=NULL) { /* Wenn ja: Ausgabe einer Kante, die nach rechts fuehrt */ gotoxy((right-left)/2,3); for (i=(right-left)/2;i<=1+(3*(right-left))/4;i++) printf("-"); } /* Ausgabe des Werts des aktuellen Wurzelknotens */ gotoxy((right-left)/2,3); printf(" %c ",baum->wert); /* rekursive Aufrufe zur Ausgabe des linken und rechten Unterbaums in entsprechenden Teilfenstern */ drucke_rek_bsp69(baum->left,left,top+3, left+(right-left)/2,bottom); drucke_rek_bsp69(baum->right, left+(right-left)/2+1,top+3,right,bottom); } void drucke_bsp69(treeelem *baum) { /* Ausgabe des Gesamtbaums baum mit Hilfe von drucke_rek_bsp69() */ clrscr(); drucke_rek_bsp69(baum,1,1,80,25); window(1,1,80,25); } /********************/ /* Aufbau des Baums */ /********************/ treeelem *baumaufbau(char ausdr[],unsigned *pos) { /* ausdr enthaelt einen Ausdruck in Praefixnotation. Die Funktion baut daraus einen Strukturbaum auf und gibt einen Zeiger auf dessen Wurzelknoten zurück. Sie beginnt beim Aufbau an der durch *pos gegebenen Position und endet, wenn der Baum vollstaendig ist, d.h. alle seine Blattknoten Operanden (= Ziffern) enthalten. In pos wird dann die erste Position des Arrays zurueckgegeben, die dabei noch nicht berueck- sichtigt wurde. Bei einem Syntaxfehler wird das Programm mit Feh- lermeldung abgebrochen. */ treeelem *neu; /* für neues Baumelement */ /* Test, ob noch Zeichen vorhanden. Wenn nein: Fehler */ if (*pos==strlen(ausdr)) { printf("Syntaxfehler"); getch(); exit(-1); } /* Erzeugung eines neuen Baumelements */ neu = (treeelem *)malloc(sizeof(treeelem)); if (neu==NULL) { printf("Fehler bei malloc()"); getch(); exit(-1); } /* Test, ob das Zeichen eine Ziffer ist */ if (ausdr[*pos]>='0'&&ausdr[*pos]<='9') { /* Ziffer in Knoten eintragen und Nachfolger auf NULL setzen, da Blattknoten */ neu->wert=ausdr[*pos]; neu->left=neu->right=NULL; /* Inkrementierung der Position */ *pos = *pos+1; /* Baum zurückgeben */ return neu; } /* Test, ob das Zeichen ein zulaessiger Operator ist */ if ((ausdr[*pos]!='+')&&(ausdr[*pos]!='-') &&(ausdr[*pos]!='*')&&(ausdr[*pos]!='/')) { printf("Syntaxfehler"); getch(); exit(-1); } /* Wert des neuen Baumknotens ist der Operator */ neu->wert=ausdr[*pos]; /* Inkrementierung der Position */ *pos = *pos+1; /* Erzeugung des linken Unterbaums */ neu->left=baumaufbau(ausdr,pos); /* Erzeugung des rechten Unterbaums */ neu->right=baumaufbau(ausdr,pos); /* Rueckgabe des neuen Baums */ return neu; } /*****************/ /* Hauptprogramm */ /*****************/ main() { treeelem *root; /* Wurzel des Baums */ char ausdruck[80]; /* arithmetischer Ausdruck als String */ unsigned index=0; /* Hilfsvariable zur Verwendung beim Baumaufbau */ /* Eingabe des Ausdrucks */ printf("Bitte arithmetischen Ausdruck in Praefixnotation eingeben.\n"); printf(" Als Operatoren sind +,-,*,/ zugelassen.\n"); printf(" Die Zahlen duerfen nur aus einer Ziffer bestehen.\n"); printf(" Klammern sind nicht erlaubt.\n"); printf(" Beispieleingabe: *+12-34\n\n"); scanf("%s",ausdruck); printf("\n"); /* Umsetzung des Ausdrucks in einen Baum. Zeiger auf die Baumwurzel wird in root abgespeichert. */ root=baumaufbau(ausdruck,&index); if (index