Ερωτήσεις Κατανόησης Δέντρων tree C#

[V.I.Smirnov]

Πρώτα εκτελούνται όλες οι "left" μέχρι να φτάσει η εκτέλεση στη βασική συνθήκη τερματισμού.

Μετά όλες "right" καθεμιά εκ των οποίων έχει καινούριoυς κλάδους "left" κλπ.

 

Αν δεν ενσωματώσεις συνθήκη τερματισμού θα μπερδευτείς διότι οι "left" δεν θα επιστρέψουν ποτέ και η εκτέλεση δεν φτάσει στις "right".

[MpOuKaLAs]

Πρώτα εκτελούνται όλες οι "left" μέχρι να φτάσει η εκτέλεση στη βασική συνθήκη τερματισμού.

Μετά όλες "right" καθεμιά εκ των οποίων έχει καινούριoυς κλάδους "left" κλπ.

 

Αν δεν ενσωματώσεις συνθήκη τερματισμού θα μπερδευτείς διότι οι "left" δεν θα επιστρέψουν ποτέ και η εκτέλεση δεν φτάσει στις "right".

 

 

ΟΚ!!!!

 

Δηλαδη πρωτα θα εκτελεστουν οι left ( δλδ θα στειλει ως ορισμα την διευθυνση του ΚΑΘΕ κομβου και οταν φτασει στο NULL θα εκτελεστει η if και εκει θα τελειωσει? )

 

καταλαβα σωστα?

 

Σχετικα με το + μεταξυ των συναρτησεων δεν συμβαινει τιποτα?

 

 

εστω δηλαδη οτι εχω αυτο το δεντρο:

 

>
                          1
                         / \
                        2    3
                      /  \     \
                   null   4     5
                                /   \          
                          NULL    NULL

 

Πρωτα θα παει στο 2

μετα θα παει στο 3

μετα θα τερματιστει αφου ο Pointer δειχνει στο null.

 

Σωστη η σκεψη μου?

[V.I.Smirnov]

Χμ...ναι, σωστά κατάλαβες.

 

Αυτό που κάνεις είναι DFS (δηλ. depth first search ) σε δέντρο.

 

Και το 4 πρέπει να έχει null θυγατρικό, το ξέχασες.

Βάλε printf ή cout για να δεις από που περνάει και πότε προσθέτει.

 

Πρώτα θα πάει στο 2 και θα ερευνήσει όλους τους υποκλάδους του. Συνεπώς το επόμενο είναι το 4 κι όχι το 3.

Η σειρά με την οποία περνάει από τους κόμβους είναι 1,2,4,3,5.

Η πρόσθεση γίνεται σε κάθε επιστροφή null, άρα η σειρά με την οποία γίνονται οι πράξεις είναι 4,2,5,3,1

Συνεπώς αρχικά θα προσθέσει τα περιεχόμενα των 4,2.

Όμοια και για τα υπόλοιπα.

 

(Με επιφύλαξη διότι το είδα βιαστικά...)

[MpOuKaLAs]

ok thanks για τις απαντησεις αλλα δεν μπορω να καταλαβω ποτε σε ενα κωδικα σαν αυτο

εκτελειται η πρόσθεση.

 

καλυτερα θα ηταν αν εκανες ενα παραδειγματακι ετσι ωστε να εμπεδοθει απο τον εγκεφαλο μου!

[V.I.Smirnov]

Σου είπα τι να κάνεις : βάλε printf ή cout εκεί που προσθέτει.

 

>if (t==NULL) return(0);
n1=count(t->left);
n2=count(t->right);
cout<<n1<<",  "<<n2<<"\n";
return n1+n2+1;

 

κλπ...

Άντε, καληνύχτα...

[MpOuKaLAs]

Αν χρησιμοποιησω τον παρακατω κωδικα για το παρακατω δεντρο

>
int count(PTR t)
{
if (t==NULL) return(0);
return(count(t->left)+count(t->right)+1);
}


                          1
                         / \
                        2    3
                      /  \     \
                   null   4     5
                                /   \          
                          NULL    NULL

 

Θα γινει ελεγχος αν t == ΝULL ( FALSE )

μετα θα παει στο 2 και θα εκτελεσει η count(t->left)

 

Μετα θα ΞΑΝΑγινει ελεγχος αν t == ΝULL ( TRUE ) και θα επιστρεψει 0 ( μηδεν ).

 

ΟΠΟΤΕ ΤΕΛΕΙΩΝΕΙ ΤΟ ΟΛΟ ΘΕΜΑ και δεν θα εξερευνησει ολοκληρο το δεντρο οπως λες.

 

 

ΕΡΩΤΗΣΗ 1 ) ΛΑΘΟΣ ΚΑΝΩ?

 

 

Επισης μια διευκρινηση που εχω να κανω και ας με διορθωσετε

σε περιπτωση που εχω το παρακατω δεντρο τοτε ο αλγοριθμος θα φτασει

μεχρι το 10 και εκει θα σταματησει γιατι ο t θε ειναι NULL ετσι δεν ειναι ?

 

>
                          1
                         / \
                        2    3
                      /        \
                    7           5
                  /           /   \          
                10     NULL    NULL
               /
           ΝULL

 

ΕΡΩΤΗΣΗ 2 )

και για να καταλαβω αν υποθεσουμε οτι το count( t->left ) θα εκτελειτε μεχρι καποια στιγμη ας πουμε , αμεσως μετα σειρα θα εχει να εκτελεστει η count( t->right ) ?

 

ΕΡΩΤΗΣΗ 3 )

οταν καλειται π.χ η count( t->left ) τοτε ως ορισμα στελνει στον εαυτο της την ΤΙΜΗ του κομβου ? η την ΔΙΕΥΘΥΝΣΗ του κομβου ?

 

ΕΡΩΤΗΣΗ 4 )

εγω νομιζω την διευθυνση και αφου στελνει την διευθυνση πως μπορει και τα προσθετει?

 

ΕΡΩΤΗΣΗ 5 )

ειναι δυνατον να προσθετω διευθυνσεις κομβων?

[V.I.Smirnov]

1)

Λάθος κάνεις.

Όταν συναντήσει το null αριστερά του 2 θα πάψει να ερευνά τον αριστερό υποκλάδο του 2 και θα συνεχίσει με τον δεξιό δηλ. το 4.

Και όταν συναντήσει τα null (που δεν έβαλες) στους κλάδους του 4 θα επιστρέψει στο 2.

Στο 2 έχει ψάξει τους δυο κλάδους του αρα άρα επιστρέφει στο 1.

Στο 1 έχει τελειώσει το ψάξιμο στον αριστερό κλάδο του αρα συνεχίζει με τον δεξιό.

Ο δεξιός κλάδος του 1 ξεκινά με το 3.

Το 3 αριστερά έχει null. Επιστρέφει στο 3 και ερευνά δεξιά του, δηλ. στο 5.

Ψάχνει πρώτα αριστερά του 5 και συναντά null. Eπιστρέφει στο 5 ψάχνει δεξιά. Επειδή συναντά null επιστρέφει στο 5.

Έχει ψάξει τους κλάδους του 5 άρα επιστρέφει στο 3.

Έχει ψάξει τους κλάδους του 3 άρα επιστρέφει στο 1.

Έτσι το δέντρο σαρώνεται όλο.

 

Οι δυνατότητες σάρωσης ενός δέντρου είναι τρεις : pre-order,in-order και post-order.

Τα pre-, in- και post- order αναφέρονται στο πότε επεξεργάζεται τον κόμβο από τον οποίο περνάει.

Π.χ. αν παραπάνω το βάλεις να τυπώνει τα στοιχεία, πού θα βάλεις την εντολή εκτύπωσης ;

 

>if (t==NULL) return(0);
// cout<<n1<<",  "<<n2<<"\n"; // εδώ είναι pre-order
n1=count(t->left);
// cout<<n1<<",  "<<n2<<"\n"; // εδώ είναι in-order
n2=count(t->right);
// cout<<n1<<",  "<<n2<<"\n"; // εδώ είναι post-order
return n1+n2+1;

 

Στο δεύτερο παράδειγμα που δείχνεις, θα σταματήσει στο 10 και θα επιστρέψει τελικά στην κορυφή αφού δεν υπάρχουν υποκλάδοι αριστερά του.

Μετά θα συνεχίσει με τον δεξιό κλάδο του 1, δηλ. το 3 κλπ.

Συνεπώς η σάρωση δεν διακόπτεται τελεσίδικα στο 10 αν αυτό εννοείς.

 

2) Έτσι όπως το έχεις γράψει, εκτελείται πάντα η left πρώτη.

Αν συναντήσει null επιστρέφει και συνεχίζει με την right.

Αλλά και τότε ψάχνει πρώτα τη left που έχει κάθε κόμβος right.

 

Για τις 3), 4), 5) προφανώς αυτά που προσθέτεις πρέπει να είναι κατάλληλα δεδομένα των κόμβων κι όχι διευθύνσεις.

Ειδικά για την 3), στέλνει την διεύθυνση του κόμβου.

Ο κώδικας δεν είναι σωστός.

Σε κάθε κόμβο πρέπει να αποθηκεύεις έναν δείκτη προς τα θυγατρικά του δηλ. τα left και right (εφόσον είναι δυαδικό) και το δεδομένο, πχ. έναν ακέραιο int data.

Εσύ λαθεμένα κάνεις πράξεις με τις διευθύνσεις αντί με το data.

 

 

Στο ξαναλέω : βάλε το καταρχήν να τυπώνει το περιεχόμενο (data) του κόμβου για να καταλάβεις με ποιά σειρά γίνεται η σάρωση και μετά ασχολείσαι με πράξεις.

[MpOuKaLAs]

Ευχαριστω για τον χρονο σου

 

Θα ανεβασω σε καμια ωρα κωδικα να τον δεις και να μου πεις αν ειναι οκ!