000
28.05.2007, 21:06 Uhr
~ritter
Gast
|
Moin!
Ich habe eine Aufgabe die wie folgt aussieht!
Die Voraussetzungen sieht wie folgt aus:
Ich habe folgende baumartige Struktur:
| C++: |
typedef struct {
int left, right;
} pair;
pair paare[] = {
{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}
};
|
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:
BAUM
(Keine Gewähr, dass er richtig ist)
Mein Code sieht wie folgt dazu aus:
| C++: |
#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;
}
if(T[node_no].lnode!=-2){
if(SearchExit(T,(node_no+1))==1){
printf("%2d. Knoten: %d | LINKS\n",x++,node_no);
return 1;
}
}
if(T[node_no].rnode!=-2){
if(SearchExit(T,(node_no+1))==1){
printf("%2d. Knoten: %d | RECHTS\n",x++,node_no);
return 1;
}
}
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 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ß |
