αναδρομική συναρτηση στη C

[antemar]

Εάν έχω την πιο κάτω δομή ΔΔΑ:

 

typedef struct BSTnode *node;

struct BSTnode {

int key;

node left;

node right;

};

 

πως μπορώ να φτιάξω μια αναδρομική συνάρτηση με πρότυπο

void greater_keys(node current, int value);

που θα τυπώνει όλες τις τιμές των κόμβων ενός ΔΔΑ που είναι μεγαλύτερες από την τιμή της μεταβλητής value;

[dms_tns]

Kατ'αρχάς φίλε μου θα πρέπει να επιλέξεις τον τρόπο που θα "διατρέξεις" το

 

Binary Tree.Και ύστερα να επεξεργάζεσαι το περιεχόμενο του κόμβου.

 

Ας πούμε με τον τρόπο Αριστερά Κέντρο Δεξιά -ΑΚΔ- (Υπάρχουν κι άλλοι ανάλογοι). (ενδοδιατεταγμένη μορφή (έτσι λέγεται ο "ΑΚΔ" τρόπος))

 

Η αλγοριθμική διαδικασία έχει γενικά ως εξής : με αρχή έναν κόμβο (όποιον

 

θες) ως ρίζα (root) , , έλέγχεις αν έχει αριστερό

 

παιδι (κόμβο κάτω από αυτόν στα αριστερά) , ΑΝ έχει

 

προχωράς σε αυτόν (ο δείκτης δείχνει τώρα τον κόμβο αριστερό "παιδί" του

 

κόμβου ρίζα ) , ελέγχεις πάλι αν έχει αριστερό παιδί , αν έχει προχωράς

 

στο αριστερό αυτό παιδί , αυτό γίνεται "όλο" αριστερά θέτοντας εκ νέου τον

 

αριστερό κόμβο ως ρίζα , έως ότου (έλεγχος if) δεν υπάρχει αριστερό

 

παιδί ,

 

τότε επεξεργάζεσαι το περιεχόμενο του κόμβου που ήταν την

 

τελευταία φορά ρίζα εδώ το εκτυπώνεις (key) με βάση την

 

προυπόθεση που θες (έλεγχος if)..,

 

στη συνέχεια προχωράς στο δεξιό παιδί....πάλι τα ίδια όλο δεξιά μέχρι να

 

μη βρείς κόμβο μετά...

Προφανώς αυτός είναι ένας υπεργενικευμένος

 

αλγόριθμος..η ουσία είναι να χωρίζεις το δέντρο σε αριστερό και δεξιό

 

μέρος ,όπου το καθένα να το ξαναχωρίζεις έως ότου ελαχιστοποιειθει κ δεν

 

υπάρχει άλλο..Συνοπτικά

1. Διαδρομή αριστερού υποδέντρου
   
2. Επίσκεψη επεξεργασία κόμβου πατέρα
   
3. Διαδρομή δεξιό υποδέντρο
   

Τώρα μένει ο τρόπος (προγραμματιστική τεχνική)

 

υλοποίησης..

 

Το όλο σκηνικό (εμβαθύνεις-ελαχιστοποιείς-γυρίζεις πίσω) κρύβει μια ανδρομικότητα συνεπώς υλοποίηση ανδρομικής συνάρτησης.

 

Όμως μπορείς και μη αναδρομικά με χρήση βρόχου for και Δομής Δεδομένων στοίβας.

 

Ο πιο κομψός τρόπος (όχι πάντα ο καταλυλότερος σε πόρους συστήματος) είναι ο αναδρομικός.

*******************************************************************************

Η αναδρομική (αυτοκαλούμενη) συνάρτηση έχει :

 

void greater_keys(node current, int value)

{

if (current!=null) // Έλεγχος - συνθήκη για να σταματήσει κάποια στιγμή η αναδρομή - ύπαρξη κενού υποδέντρου

{

greater_keys(current->left,value); //Κλήση της greater_key για το αριστερό παιδί

if ((current->key) > value) //Η συνθήκη που θές για εκτύπωση

{

printf("%d" , current->key);

}

greater_keys(current->right ,value); //Κλήση της greater_key για το δεξί παιδί

}

}

************************************************************************************

Έτσι με "απανοτές" εμφωλευμένες κλήσης του εαυτού της (του ίδιου κώδικα...---> αλλά με διαφορετική θέση στη μνήμη) διατρέχεται με την ενδοδιατεταγμένη μορφή το δέντρο και επεξεργάζονται οι κόμβοι.

 

Ελπίζω να σου φανούν αρκετά βοηθητικά....

[antemar]

Καταρχήν σε ευχαριστώ πολύ για όσα έγραψες γιατί πραγματικά κατάλαβα περί τίνος πρόκειται. Η βοήθειά σου ήταν καταλυτική.

Τώρα για αυτό που με ρώτησες στην αρχή, οι τιμές του δένδρου θα τυπώνονται μια ανά γραμμη σε post order διαπέραση.

Ελπίζω να μην αλλάζει τίποτα ύστερα από αυτήν την διευκρίνηση.

[dms_tns]

Αν κατάλαβα καλά πρέπει να γίνει κάτι επιπλέον στη σειμβολοσειρά τροποποίησης (έτσι λέγεται ο "χώρος" μεταξύ των εισαγωγικών) της printf . Πρέπει να μπει στο τέλος ο χαρακτήρας διαφυγής που συμβολίζει την αλλαγή νέας γραμμής (ο χαρακτήρας που συμβολίζει και το ENTER..).Για να στα εκτυπώνει σε ξεχωριστεί γραμμή..(postorder????τι εννοεις?)

 

Άρα είναι : printf("%d\n" , current->value);

 

Φαντάζομαι αυτό να θες...

[antemar]

Να τα πάρουμε τα πράγματα από την αρχή.

Έχω μια συγκεκριμένη δομή ΔΔΑ:

typedef struct BSTnode *node;

struct BSTnode {

int key;

node left;

node right;

};

Έχω επίσης γράψει μια αναδρομική συνάρτηση με προτυπο

void printKeys_postorder(node current)

{

if (!current) return;

printKeys_postorder(current->left);

printKeys_postorder(current->right);

printf("%d\n", current->key);

}

η οποία τυπώνει τις τιμές των κόμβων ενός Δυαδικού Δένδρου Αναζήτησης, μία ανα γραμμή, σε post order διαπέραση.

Μέχρι εδώ ελπίζω να τα έχω πάει καλά.

Αυτό που ζητά τώρα είναι να γράψω μια αναδρομική συνάρτηση σε γλώσσα προγραμματισμού C με πρότυπο

void greater_keys(node current, int value);

η οποία να τυπώνει όλες τις τιμές των κόμβων ενός Δυαδικού Δένδρου Αναζήτησης που είναι μεγαλύτερες από την τιμή της μεταβλητής value.

[dms_tns]

Ναι οκ σε έπιασα απλά εγώ το ήξερα ως postfix.... και ψηλοκόλλησα...

 

απλά βάζεις το block με την if και την printf στο τέλος..

[dms_tns]

Μια χαρά απλά τροποποιέις όπως σου χα γράψει πάνω και ΔΕΝ εκτυπώνεις ΟΛΕΣ τις τιμές

 

αλλά μόνο αυτές που είναι μεγλύτερες από την τιμή εισόδου της συνάρτησης ,value.

 

Όταν λοιπόν έχει έρθει η ώρα για εκτύπωση τις τιμής του κόμβου εσύ λίγο πριν την printf

 

βάζεις έναν έλεγχο if αν το περιεχόμενο current->key είναι μεγαλύτερο ή οχι από την τιμή

 

του value...ανάλογα τι είναι εκτελείται ή οχι το περιεχόμενο της if αλλιως προσπερνάτε

 

και αφού δεν υπάρχει εναλλακτική λύση (με else) συνεχίζει κανονικά προς "τα κάτω" η

 

εκτέλεση του κώδικα...

 

ΠΙΟ ΠΑΝΩ ΗΘΕΛΑ ΝΑ ΓΡΑΨΩ printf("%d\n",current->key); .... ΚΑΙ ΟΧΙ current->value