Moin!
Ich habe eine Aufgabe die wie folgt aussieht!
Die Voraussetzungen sieht wie folgt aus:
Ich habe folgende baumartige Struktur:
Alles anzeigen
1. Der Baum ist von 0 bis n-1 durchnummeriert.
2. Knoten, die keinen linken bzw. rechten Sohn besitzen, haben stattdessen den Wert -1
3. Die Wurzel hat den Wert 0
4. Der Ausgänge besitzen den Wert -2
Ich soll jetzt beginnend vom Eingang (0) einen Ausgang mittels Backtracking finden.
Ich habe versucht den "Baum" zu zeichnen:
[Blockierte Grafik: http://bildupload.sro.at/a/images/5.1.a_baum.JPG]
(Keine Gewähr, dass er richtig ist)
Mein Code sieht wie folgt dazu aus:
Alles anzeigen
Nun hab eich ein problem!
Er findet zwar den Ausgang, aber irgendwie scheint er immer nur die erste bedingung anzuwählen! Er geht gar nicht in die zweite Bedingung für den rechten Knoten rein!!
Und er durckt jeden knoten aus! Dass das Programm jeden Knoten durchgeht, ist mir klar, aber soll nur den richtigen Weg ausdrucken!
Kann mir mal jemand helfen?
ich komme einfach nicht weiter!
gruß
Ich habe eine Aufgabe die wie folgt aussieht!
Die Voraussetzungen sieht wie folgt aus:
Ich habe folgende baumartige Struktur:
Quellcode
1. Der Baum ist von 0 bis n-1 durchnummeriert.
2. Knoten, die keinen linken bzw. rechten Sohn besitzen, haben stattdessen den Wert -1
3. Die Wurzel hat den Wert 0
4. Der Ausgänge besitzen den Wert -2
Ich soll jetzt beginnend vom Eingang (0) einen Ausgang mittels Backtracking finden.
Ich habe versucht den "Baum" zu zeichnen:
[Blockierte Grafik: http://bildupload.sro.at/a/images/5.1.a_baum.JPG]
(Keine Gewähr, dass er richtig ist)
Mein Code sieht wie folgt dazu aus:
Quellcode
- #include<stdio.h>
- typedef struct {
- int lnode, rnode;
- } node_t;
- node_t tree[] = {
- {1, 2}, {3, 4}, {5, 6}, {-1, 7},
- {8, 9}, {10, 11}, {12,-1}, {-1,-1},
- {13, 14}, {-1,-1}, {-1,-1}, {-1,-1},
- {-1,-1}, {15, 16}, {-1,-1}, {-1,-1}, {-2,-2}
- };
- int SearchExit (node_t *T, int node_no)
- {
- static int x=1;
- if(T[node_no].lnode==-2 || T[node_no].rnode==-2)
- {
- if(T[node_no].lnode==-2)
- printf("Ausgang beim linken Kind von Knoten %d gefunden\n",node_no);
- if(T[node_no].rnode==-2)
- printf("Ausgang beim rechten Kind von Knoten %d gefunden\n",node_no);
- return 1;
- }
- // zu erst immer links gehen
- //if(T[node_no].lnode!=1){
- if(SearchExit(T,(node_no+1))==1){ // nächster LINKER knoten - WIE?!??!?! UND vergleich auf 1 ist auch falsch, so ist sie immer wahr und er gibt automatisch die zeilen aus
- printf("%2d. Knoten: %d | LINKS\n",x++,node_no);
- return 1;
- }
- //}
- //if(T[node_no].rnode!=1){
- if(SearchExit(T,(node_no+1))==2){
- printf("%2d. Knoten: %d | RECHTS\n",x++,node_no);
- return 2;
- }
- //}
- return 0;
- }
- int main ( void )
- {
- if ( SearchExit(tree, 0) == 1 )
- printf("Ausgang gefunden!\n");
- else
- printf("Ausgang nicht gefunden!\n");
- return 0;
- }
Nun hab eich ein problem!
Er findet zwar den Ausgang, aber irgendwie scheint er immer nur die erste bedingung anzuwählen! Er geht gar nicht in die zweite Bedingung für den rechten Knoten rein!!
Und er durckt jeden knoten aus! Dass das Programm jeden Knoten durchgeht, ist mir klar, aber soll nur den richtigen Weg ausdrucken!
Kann mir mal jemand helfen?
ich komme einfach nicht weiter!
gruß