[Powered by Google Translate] [Ενότητα 7] [λιγότερο άνετα]
[Nate Hardison] [Πανεπιστήμιο του Χάρβαρντ]
[Αυτό είναι CS50.] [CS50.TV]
>> Καλώς ήρθατε στο Τμήμα 7.
Χάρη σε τυφώνα Sandy,
αντί να έχουν ένα κανονικό τμήμα αυτής της εβδομάδας,
κάνουμε αυτό με τα πόδια-through, μέσα από την ενότητα των ερωτήσεων.
Πάω να ακολουθεί μαζί με το πρόβλημα Σετ 6 Προδιαγραφές,
και να περάσει από όλες τις ερωτήσεις στο
Ένα τμήμα των ερωτήσεων τμήμα.
Αν υπάρχουν ερωτήσεις,
παρακαλούμε να δημοσιεύσετε σε αυτά CS50 Συζητήστε.
>> Εντάξει. Ας ξεκινήσουμε.
Αυτή τη στιγμή Ψάχνω στη σελίδα 3 των προδιαγραφών Set πρόβλημα.
Εμείς πάμε για την πρώτη αρχίσουμε να μιλάμε για δυαδικά δέντρα
αφού αυτοί έχουν πολύ ενδιαφέρον για το πρόβλημα σύνολο αυτής της εβδομάδας -
η κωδικοποίηση Huffman δέντρο.
Μία από τις πρώτες δομές δεδομένων μιλήσαμε για CS50 ήταν η σειρά.
Θυμηθείτε ότι ένας πίνακας είναι μια ακολουθία των στοιχείων -
όλα του ίδιου τύπου - αποθηκεύονται δίπλα στο άλλο στη μνήμη.
Αν έχω έναν πίνακα ακεραίων ότι μπορώ να βγάλω τη χρήση αυτής κουτιά-ακέραιοι αριθμοί-στυλ -
Ας πούμε ότι έχω 5 στο πρώτο πλαίσιο, έχω 7 στο δεύτερο,
τότε έχω 8, 10, και 20 στο τελικό πλαίσιο.
Θυμηθείτε, οι δύο πραγματικά καλά πράγματα σχετικά με αυτό το φάσμα
είναι ότι έχουμε αυτό το σταθερό χρόνο πρόσβαση σε οποιοδήποτε συγκεκριμένο στοιχείο
στον πίνακα, αν γνωρίζουμε δείκτης της.
Για παράδειγμα, αν θέλετε να πάρετε το τρίτο στοιχείο του πίνακα -
στο δείκτη 2 χρησιμοποιώντας μηδενική βάση μας σύστημα ευρετηρίασης -
I κυριολεκτικά ακριβώς πρέπει να κάνετε ένα απλό μαθηματικό υπολογισμό,
hop σε αυτή τη θέση στη συστοιχία,
τραβήξτε προς τα έξω τα 8 που είναι αποθηκευμένα εκεί,
και είμαι καλό να πάει.
>> Ένα από τα κακά πράγματα για αυτό το array - για την οποία μιλήσαμε
όταν συζητήσαμε συνδεδεμένες λίστες -
είναι ότι αν θέλετε να εισάγετε ένα στοιχείο σε αυτήν την σειρά,
Πάω να χρειαστεί να κάνετε κάποια αλλαγή γύρω.
Για παράδειγμα, αυτή η συστοιχία εδώ
είναι σε ταξινομημένη σειρά - ταξινομημένο σε αύξουσα σειρά -
5, στη συνέχεια 7, στη συνέχεια 8, στη συνέχεια 10, και στη συνέχεια 20 -
αλλά αν θέλετε να εισάγετε τον αριθμό 9 σε αυτό το φάσμα,
Πάω να πρέπει να αλλάξει κάποια από τα στοιχεία για να κάνει χώρο.
Μπορούμε να αντλήσουμε από αυτό εδώ.
Πάω να χρειαστεί να μετακινήσετε το 5, το 7, και στη συνέχεια τα 8?
δημιουργήσετε ένα χάσμα όπου μπορώ να βάλω το 9,
και στη συνέχεια το 10 και το 20 μπορεί να πάει προς τα δεξιά του 9.
Αυτό είναι το είδος του πόνου, διότι στην χειρότερη περίπτωση -
όταν είμαστε να χρειάζεται να εισάγετε είτε στην αρχή ή στο τέλος
της συστοιχίας, ανάλογα με το πώς είμαστε μετατόπιση -
θα μπορούσαμε να καταλήξετε να πρέπει να μεταφερθεί το σύνολο των στοιχείων
ότι αυτή τη στιγμή αποθήκευση στη συστοιχία.
>> Έτσι, ό, τι ήταν ο τρόπος γύρω από αυτό;
Ο τρόπος γύρω από αυτό ήταν να πάει σε συνδεδεμένη λίστα, η μέθοδός μας, όπου -
αντί για την αποθήκευση των στοιχείων 5, 7, 8, 10, και 20 όλα δίπλα στο άλλο στη μνήμη -
αυτό που έκανε ήταν αντί να αποθηκεύσει το είδος του όπου θέλαμε να τις αποθηκεύσετε
σε αυτές τις συνδεδεμένες-κατάλογος κόμβων που είμαι από τη σύνταξη, εδώ το είδος των ad hoc.
Και τότε θα συνδέονται μεταξύ τους με τη χρήση αυτών των επόμενοι δείκτες.
Ι μπορεί να έχει ένα δείκτη από 5 στο 7,
ένας δείκτης από το 7 στο 8,
ένας δείκτης από το 8 στο 10,
και τέλος, ένα δείκτη από το 10 στο 20,
και στη συνέχεια ένα κενό δείκτη του 20 δείχνει ότι δεν υπάρχει τίποτα αριστερά.
Το trade-off που έχουμε εδώ
είναι ότι τώρα, αν θέλουμε να εισάγετε τον αριθμό 9 σε ταξινομημένη λίστα μας,
το μόνο που έχουμε να κάνουμε είναι να δημιουργήσουμε ένα νέο κόμβο με 9,
σύρμα μέχρι να το επισημάνω στον κατάλληλο τόπο,
και στη συνέχεια εκ νέου το καλώδιο 8 στο σημείο κάτω στο 9.
Αυτό είναι αρκετά γρήγορος, με την προϋπόθεση ξέρουμε ακριβώς πού θέλετε να εισαγάγετε το 9.
Αλλά το trade-off σε αντάλλαγμα για αυτό είναι ότι έχουμε χάσει πλέον τη συνεχή χρόνο πρόσβασης
σε οποιοδήποτε συγκεκριμένο στοιχείο σε δομή δεδομένων μας.
Για παράδειγμα, αν θέλετε να βρείτε το τέταρτο στοιχείο αυτής της συνδεδεμένης λίστας,
Πάω να πρέπει να ξεκινήσει από την αρχή της λίστας
και το έργο το δρόμο μου μέσω του κόμβου καταμέτρηση-με-κόμβο μέχρι να βρω το τέταρτο.
>> Για να πάρει την καλύτερη απόδοση από ό, τι την πρόσβαση σε συνδεδεμένη λίστα -
αλλά διατηρούν, επίσης, μερικά από τα οφέλη που είχαμε
όσον αφορά την εισαγωγή χρόνο από μια συνδεδεμένη λίστα -
ένα δυαδικό δέντρο θα χρειαστεί να χρησιμοποιήσετε λίγο περισσότερη μνήμη.
Συγκεκριμένα, αντί απλά να έχουν ένα δείκτη σε ένα δυαδικό δέντρο κόμβο -
όπως και η συνδεδεμένη λίστα-κόμβος κάνει -
θα πάμε να προσθέσετε ένα δεύτερο δείκτη στο δυαδικό κόμβο του δένδρου.
Αντί έχοντας μόνο ένα δείκτη προς την επόμενη στοιχείο,
θα πάμε να έχουν ένα δείκτη σε ένα παιδί αριστερά και δεξιά ένα παιδί.
>> Ας συντάξει μια εικόνα για να δείτε τι που πραγματικά μοιάζει.
Και πάλι, Πάω να χρησιμοποιήσετε αυτά τα κουτιά και τα βέλη.
Ένα δυαδικό δέντρο κόμβος θα ξεκινήσει με ένα απλό κουτί.
Είναι πρόκειται να έχουν ένα χώρο για την αξία,
και στη συνέχεια, αυτό είναι, επίσης, πρόκειται να έχουν ένα χώρο για το αριστερό παιδί και το δικαίωμα του παιδιού.
Πάω να τους στιγματίσει εδώ.
Εμείς πάμε για να έχουν το αριστερό παιδί, και στη συνέχεια θα πάμε να έχουν το δικαίωμα του παιδιού.
Υπάρχουν πολλοί διαφορετικοί τρόποι για να γίνει αυτό.
Μερικές φορές, για το διάστημα και την ευκολία,
Θα επιστήσω την πραγματικότητα όπως κάνω εδώ στο κάτω μέρος
όπου Πάω να έχουν την τιμή στην κορυφή,
και στη συνέχεια το δικαίωμα των παιδιών στο κάτω δεξιά,
και το αριστερό παιδί στο κάτω-αριστερά.
Πηγαίνοντας πίσω σε αυτήν την κορυφή διάγραμμα,
έχουμε την τιμή στην κορυφή,
τότε έχουμε το αριστερό παιδί-δείκτη, και τότε θα έχουμε το δικαίωμα-παιδί δείκτη.
>> Της συγγραφής υποχρεώσεων πρόβλημα,
μιλάμε για την κατάρτιση ενός κόμβου που έχει μια αξία 7,
και στη συνέχεια, ένα αριστερό παιδί δείκτη που είναι άκυρη, καθώς και το δικαίωμα του παιδιού-δείκτη που είναι null.
Μπορούμε να γράψουμε είτε NULL κεφαλαίου στο χώρο για
τόσο το αριστερό παιδί και το δικαίωμα του παιδιού, ή μπορούμε να βγάλουμε αυτό το διαγώνια κάθετο
μέσω καθενός από τα κουτιά για να δείξει ότι είναι άκυρη.
Πάω να το κάνω αυτό μόνο και μόνο επειδή αυτό είναι απλούστερο.
Αυτό που βλέπετε εδώ είναι δύο τρόποι για να διαγραμμάτων ένα πολύ απλό κόμβο του δένδρου δυαδικό
όπου έχουμε την τιμή 7 και null δείκτες παιδί.
>> Το δεύτερο μέρος των συνομιλιών τις προδιαγραφές μας για το πώς συνδέονται με τους καταλόγους -
Να θυμάστε, είχαμε μόνο να κρατήσουμε την πρώτη στοιχείο σε μια λίστα
για να θυμούνται ολόκληρη τη λίστα -
και επίσης, με ένα δυαδικό δέντρο, δεν έχουμε παρά να κρατήσει σε ένα δείκτη στο δέντρο
προκειμένου να διατηρήσει τον έλεγχο καθ 'όλη τη δομή δεδομένων.
Αυτό το ειδικό στοιχείο του δέντρου ονομάζεται κόμβο ρίζα του δένδρου.
Για παράδειγμα, εάν αυτό ένας κόμβος - αυτός ο κόμβος περιέχει την τιμή 7
με μηδενική αριστερό και το δεξί παιδί-δείκτες -
ήταν η μόνη αξία στο δέντρο μας,
τότε αυτό θα ήταν κόμβος ρίζα μας.
Είναι η αρχή του δέντρου μας.
Μπορούμε να δούμε αυτό το λίγο πιο καθαρά τη στιγμή που θα αρχίσετε να προσθέτετε περισσότερους κόμβους στο δέντρο μας.
Επιτρέψτε μου να σηκώσει μια νέα σελίδα.
>> Τώρα θα πάμε να σχεδιάσετε ένα δέντρο που έχει 7 στη ρίζα,
και 3 στο εσωτερικό του αριστερού παιδιού, και 9 στο εσωτερικό του δεξιού παιδιού.
Και πάλι, αυτό είναι αρκετά απλή.
Έχουμε 7, σχεδιάστε ένα κόμβο για την 3, ένας κόμβος για 9,
και είμαι πρόκειται να θέσει το αριστερό παιδί του δείκτη 7 για να επισημάνω στον κόμβο που περιέχει 3,
και το δεξιό δείκτη παιδί του κόμβου που περιέχει 7 με τον κόμβο που περιέχει 9.
Τώρα, από τις 3 και 9 δεν έχουν παιδιά,
θα πάμε να θέσει σε όλους τους δείκτες παιδί τους να είναι μηδενική.
Εδώ, η ρίζα του δέντρου μας αντιστοιχεί στην κόμβο να περιέχει τον αριθμό 7.
Μπορείτε να δείτε ότι αν το μόνο που έχουμε είναι ένας δείκτης σε αυτόν τον κόμβο ρίζα,
τότε μπορούμε να περπατήσετε μέσα από δέντρο μας και να έχουν πρόσβαση και τα δύο κόμβους παιδί -
τόσο 3 και 9.
Δεν χρειάζεται να διατηρεί δείκτες σε κάθε κόμβο στο δέντρο.
Εντάξει. Τώρα θα πάμε να προσθέσετε ένα άλλο κόμβο σε αυτό το διάγραμμα.
Εμείς πάμε για να προσθέσετε ένα κόμβο που περιέχει 6,
και θα πάμε για να προσθέσετε αυτό το δικαίωμα το παιδί του κόμβου που περιέχει 3.
Για να γίνει αυτό, θα πάω να διαγράψετε αυτό το κενό δείκτη στο 3-κόμβος
και το σύρμα μέχρι να επισημάνω στον κόμβο που περιέχει 6. Εντάξει.
>> Σε αυτό το σημείο, ας πάμε σε ένα μικρό κομμάτι της ορολογίας.
Για να ξεκινήσετε, το λόγο ότι αυτό ονομάζεται ένα δυαδικό δέντρο, ιδίως
είναι ότι έχει δύο δείκτες παιδί.
Υπάρχουν και άλλα είδη δέντρων που έχουν περισσότερους δείκτες παιδί.
Ειδικότερα, κάνατε μια «δοκιμάσετε» σε Σετ Πρόβλημα 5.
Θα παρατηρήσετε ότι στην εν λόγω προσπάθεια, που είχε 27 διαφορετικούς δείκτες σε διαφορετικά παιδιά -
μία για κάθε ένα από τα 26 γράμματα του αγγλικού αλφαβήτου,
και στη συνέχεια το 27ο για την απόστροφο -
έτσι, αυτό είναι παρόμοιο με το είδος του δέντρου.
Αλλά εδώ, από το δυαδικό, έχουμε μόνο δύο δείκτες παιδί.
>> Εκτός από αυτό τον κόμβο ρίζα την οποία μιλήσαμε,
έχουμε επίσης ρίχνουν γύρω από αυτόν τον όρο «παιδί».
Τι σημαίνει αυτό για έναν κόμβο να είναι ένα παιδί ενός άλλου κόμβου;
Αυτό σημαίνει κυριολεκτικά ότι ένας κόμβος παιδί είναι ένα παιδί ενός άλλου κόμβου
αν αυτό το άλλο κόμβος έχει ένα παιδί από δείκτες που να του επισημάνω σε αυτόν τον κόμβο.
Για να το θέσουμε σε πιο συγκεκριμένους όρους,
εάν 3 δείχνεται από ένα από τους δείκτες του παιδιού 7, τότε 3 είναι ένα παιδί 7.
Αν επρόκειτο να καταλάβουμε ποια είναι τα παιδιά από 7 -
καλά, βλέπουμε ότι 7 έχει ένα δείκτη προς 3 και ένα δείκτη προς 9,
έτσι 9 και 3 είναι τα παιδιά της 7.
Εννέα δεν έχει παιδιά, επειδή δείκτες παιδί του είναι μηδενική,
και 3 έχει μόνο ένα παιδί, 6.
Έξι έχει επίσης κανένα παιδί γιατί και οι δύο δείκτες του είναι μηδενική, η οποία θα συντάξει αυτή τη στιγμή.
>> Επιπλέον, μπορούμε επίσης να μιλήσουμε για τους γονείς ενός συγκεκριμένου κόμβου,
και αυτό είναι, όπως θα περίμενε κανείς, το αντίθετο αυτής της περιγραφής του παιδιού.
Κάθε κόμβος έχει μόνο ο ένας γονέας - αντί για δύο, όπως θα περίμενε κανείς με τους ανθρώπους.
Για παράδειγμα, η μητρική 3 είναι 7.
Η μητρική 9 είναι επίσης 7, και η μητρική της 6 είναι 3. Όχι πολύ σε αυτό.
Έχουμε, επίσης, τους όρους για να μιλήσουμε για τους παππούδες και τα εγγόνια,
και γενικότερα μιλάμε για τους προγόνους
και οι απόγονοι ενός συγκεκριμένου κόμβου.
Ο πρόγονος ενός κόμβου - ή προγόνους, μάλλον, ενός κόμβου -
είναι όλα από τους κόμβους που βρίσκονται στο μονοπάτι από τη ρίζα σε αυτόν τον κόμβο.
Για παράδειγμα, αν ψάχνω στον κόμβο 6,
τότε οι πρόγονοι πρόκειται να είναι τόσο 3 και 7.
Οι πρόγονοι του 9, για παράδειγμα, είναι - αν ψάχνω στον κόμβο 9 -
τότε ο πρόγονος του 9 είναι μόλις 7.
Και απόγονοι είναι ακριβώς το αντίθετο.
Αν θέλετε να δείτε όλα τα απόγονοι των 7,
τότε θα πρέπει να εξετάσουμε όλες τις κόμβους κάτω από αυτό.
Έτσι, έχω 3, 9, και 6, όλα τα ως απόγονοι του 7.
>> Η τελική όρο ότι θα μιλήσουμε για αυτό είναι η έννοια του να είσαι αδελφός.
Τα αδέλφια - το είδος της μετά μαζί με αυτούς τους όρους οικογένεια -
είναι κόμβοι που βρίσκονται στο ίδιο επίπεδο στο δέντρο.
Έτσι, 3 και 9 είναι αδέλφια επειδή είναι στο ίδιο επίπεδο στο δέντρο.
Και οι δύο έχουν την ίδια μητρική, 7.
Το 6 δεν έχει αδέλφια, επειδή 9 δεν έχουν παιδιά.
Και 7 δεν έχει καμία αδέλφια επειδή είναι η ρίζα του δέντρου μας,
και υπάρχει πάντα μόνο 1 root.
Για να έχουμε 7 αδέρφια εκεί θα πρέπει να είναι ένας κόμβος πάνω 7.
Θα πρέπει να υπάρξει ένας γονέας 7, στην οποία περίπτωση 7 δεν θα είναι πλέον η ρίζα του δένδρου.
Στη συνέχεια, η νέα μητρική 7 θα πρέπει επίσης να έχουν ένα παιδί,
και ότι το παιδί θα ήταν τότε ο αδερφός του 7.
>> Εντάξει. Προχωρώντας.
Όταν ξεκινήσαμε τη συζήτησή μας από δυαδικά δένδρα,
μιλήσαμε για το πώς επρόκειτο να τους χρησιμοποιήσει για να
αποκτήσουν ένα πλεονέκτημα σε σχέση με τις δύο συστοιχίες και συνδεδεμένες λίστες.
Και ο τρόπος που θα πάμε να το κάνουμε αυτό είναι με αυτό το ακίνητο παραγγελία.
Εμείς λέμε ότι ένα δέντρο δυαδική διέταξε, σύμφωνα με τις προδιαγραφές,
αν για κάθε κόμβο στο δέντρο μας, όλους τους απογόνους του για την αριστερά -
το αριστερό παιδί και όλους τους απογόνους του αριστερού παιδιού -
έχουν μικρότερες τιμές, και όλων των κόμβων για το δικαίωμα -
το δικαίωμα του παιδιού και όλους τους απογόνους του δικαιώματος του παιδιού -
κόμβοι έχουν μεγαλύτερη από την αξία του τρέχοντος κόμβου ότι ψάχνουμε σε.
Ακριβώς για λόγους απλότητας, θα πάμε να υποθέσουμε ότι δεν υπάρχουν διπλοί κόμβοι στο δέντρο μας.
Για παράδειγμα, σε αυτό το δέντρο εμείς δεν πρόκειται να ασχοληθεί με την υπόθεση
όπου έχουμε την τιμή 7 στη ρίζα
και στη συνέχεια έχουμε επίσης την αξία 7 αλλού στο δέντρο.
Σε αυτή την περίπτωση, θα παρατηρήσετε ότι αυτό το δέντρο είναι πράγματι παραγγείλει.
Έχουμε την τιμή 7 στη ρίζα.
Τα πάντα στα αριστερά της 7 -
αν μπορώ να αναιρέσω όλα από αυτά τα μικρά σημάδια εδώ -
πάντα στα αριστερά της 7 - το 3 και το 6 -
οι αξίες αυτές είναι και οι δύο λιγότερο από 7, και τα πάντα προς τα δεξιά - το οποίο είναι ακριβώς αυτό 9 -
είναι μεγαλύτερο από 7.
>> Αυτή δεν είναι η μόνη εντολή δένδρο περιέχει αυτές τις τιμές,
αλλά ας συντάξει μερικά περισσότερα από αυτά.
Υπάρχει πραγματικά ένα σωρό τρόπους με τους οποίους μπορούμε να το κάνουμε αυτό.
Πάω να χρησιμοποιήσετε μια συντόμευση μόνο για να κρατήσει τα πράγματα απλά, όπου -
αντί να οργανώνει το σύνολο κουτιά-και-βέλη -
Είμαι ακριβώς πρόκειται να συντάξει τους αριθμούς και να προσθέσετε βέλη σύνδεσή τους.
Για να ξεκινήσετε, θα γράφουμε μόνο πρωτότυπο δέντρο μας και πάλι, όπου είχαμε 7, και στη συνέχεια 3,
και στη συνέχεια 3 επεσήμανε πίσω προς τα δεξιά στο 6,
και 7 είχαν το δικαίωμα του παιδιού που ήταν 9.
Εντάξει. Τι είναι ένας άλλος τρόπος που θα μπορούσε να γράψει αυτό το δέντρο;
Αντί να έχουμε 3 είναι το αριστερό παιδί 7,
θα μπορούσαμε επίσης να έχουν το 6 είναι το αριστερό παιδί 7,
και κατόπιν 3 είναι το αριστερό παιδί του 6.
Αυτό θα μοιάζει με αυτό το δέντρο εδώ όπου έχω 7,
τότε 6, στη συνέχεια 3, και 9 σχετικά με το δικαίωμα.
Επίσης, δεν πρέπει να έχουν 7 ως κόμβος ρίζα μας.
Θα μπορούσε επίσης να έχει 6 ως κόμβος ρίζα μας.
Τι θα που μοιάζουν;
Αν θα πάμε για να διατηρηθεί αυτή η ιδιότητα διέταξε,
πάντα στα αριστερά της 6 πρέπει να είναι μικρότερη από αυτήν.
Υπάρχει μόνο μία δυνατότητα, και αυτό είναι 3.
Στη συνέχεια, όμως, όπως το δικαίωμα του παιδιού 6, έχουμε δύο δυνατότητες.
Πρώτον, θα μπορούσαμε να έχουμε την 7 και στη συνέχεια το 9,
ή θα μπορούσαμε να αντλήσει - σαν να είμαι έτοιμος να κάνω εδώ -
όπου έχουμε το 9 και το δικαίωμα του παιδιού 6,
και στη συνέχεια το 7 ως το αριστερό παιδί του 9.
>> Τώρα, 7 και 6 δεν είναι οι μόνες δυνατές τιμές για τη ρίζα.
Θα μπορούσαμε επίσης να έχουν 3 είναι στη ρίζα.
Τι θα συμβεί αν 3 είναι στη ρίζα;
Εδώ, τα πράγματα παίρνουν λίγο ενδιαφέρον.
Τρεις δεν έχει οποιεσδήποτε τιμές που είναι λιγότερο από αυτό,
έτσι ώστε ολόκληρη αριστερή πλευρά του δέντρου είναι ακριβώς πρόκειται να είναι μηδενική.
Δεν πρόκειται να είναι κάτι εκεί.
Στα δεξιά, θα μπορούσα να απαριθμήσω τα πράγματα σε αύξουσα σειρά.
Θα μπορούσαμε να έχουμε 3, έπειτα 6, στη συνέχεια 7, 9 στη συνέχεια.
Ή, θα μπορούσαμε να κάνουμε 3, στη συνέχεια, 6, στη συνέχεια, 9, στη συνέχεια, 7.
Ή, θα μπορούσαμε να κάνουμε 3, στη συνέχεια, 7, μετά 6, μετά 9.
Ή, 3, 7 - στην πραγματικότητα δεν είναι, δεν μπορούμε να κάνουμε πια ένα 7.
Αυτό είναι ένα πράγμα που μας εκεί.
Μπορούμε να κάνουμε 9, και έπειτα από το 9 μπορούμε να κάνουμε 6 και 7 στη συνέχεια.
Ή, μπορούμε να κάνουμε 3, και στη συνέχεια 9, στη συνέχεια 7, και στη συνέχεια 6.
>> Ένα πράγμα που πρέπει να επιστήσω την προσοχή σας είναι εδώ
ότι αυτά τα δέντρα είναι λίγο περίεργο το μέλλον.
Συγκεκριμένα, αν κοιτάξουμε τις 4 δέντρα στη δεξιά πλευρά -
Θα τους κύκλο, εδώ -
αυτά τα δέντρα φαίνονται σχεδόν ακριβώς όπως μια συνδεδεμένη λίστα.
Κάθε κόμβος έχει μόνο ένα παιδί,
και έτσι δεν έχουμε κανένα από αυτό το δέντρο-όπως δομή που βλέπουμε, για παράδειγμα,
σε αυτό μοναχικός ένα δέντρο εδώ στο αριστερό κάτω μέρος.
Αυτά τα δέντρα που ονομάζεται στην πραγματικότητα εκφυλιστεί δυαδικά δένδρα,
και θα μιλήσουμε για αυτά περισσότερο στο μέλλον -
ειδικά αν πάτε να πάρετε άλλα μαθήματα επιστήμης των υπολογιστών.
Αυτά τα δέντρα είναι εκφυλισμένες.
Δεν είναι πολύ χρήσιμο, διότι, πράγματι, αυτή η δομή προσφέρεται
για αναζήτηση φορές παρόμοια με εκείνη μία συνδεδεμένη λίστα.
Δεν έχετε να επωφεληθούν από την επιπλέον μνήμη - αυτό το πρόσθετο δείκτη -
λόγω της δομής μας είναι κακό με αυτόν τον τρόπο.
Αντί να πάει και να σκιαγραφήσει τα δυαδικά δέντρα που έχουν 9 στη ρίζα,
η οποία είναι η τελευταία περίπτωση ότι θα είχαμε,
είμαστε αντ 'αυτού, σε αυτό το σημείο, πρόκειται να μιλήσω λίγο για αυτό άλλος όρος
που χρησιμοποιούμε όταν μιλάμε για δέντρα, το οποίο ονομάζεται ύψος.
>> Το ύψος του δέντρου είναι η απόσταση από τη ρίζα προς το πιο μακρινό κόμβο,
ή μάλλον ο αριθμός του λυκίσκου που θα πρέπει να κάνει για να
ξεκινούν από την ρίζα και στη συνέχεια καταλήγουν στο πιο μακρινό κόμβο στο δέντρο.
Αν κοιτάξουμε μερικά από αυτά τα δέντρα που έχουμε δικαίωμα που εδώ,
μπορούμε να δούμε ότι αν πάρουμε αυτό το δέντρο στην πάνω αριστερή γωνία και θα ξεκινήσει στο 3,
τότε θα πρέπει να κάνει 1 hop για να φτάσουμε στο 6, το δεύτερο hop για να φτάσουμε στην 7,
και ένα τρίτο hop για να φτάσουμε στο 9.
Έτσι, το ύψος αυτού του δένδρου είναι 3.
Μπορούμε να κάνουμε την ίδια άσκηση για τα άλλα δέντρα που περιγράφονται με αυτό το πράσινο,
και βλέπουμε ότι το ύψος όλων αυτών των δέντρων είναι επίσης πράγματι 3.
Αυτό είναι μέρος του τι τους κάνει να εκφυλιστεί -
ότι το ύψος τους είναι ακριβώς κατά ένα μικρότερος από τον αριθμό των κόμβων σε ολόκληρο το δέντρο.
Αν δούμε σε αυτό το άλλο δέντρο που είναι περικυκλωμένη με κόκκινο, από την άλλη πλευρά,
βλέπουμε ότι οι πιο μακρινό κόμβους είναι το 6 και το 9 -
τα φύλλα που είναι οι κόμβοι που δεν έχουν παιδιά.
Έτσι, προκειμένου να πάρει από τον κόμβο ρίζα είτε στο 6 ή το 9,
θα πρέπει να κάνει ένα hop για να φτάσουμε στην 7 και στη συνέχεια μια δεύτερη hop για να φτάσουμε στο 9,
και επίσης, μόνο ένα δεύτερο hop από τις 7 για να φτάσουμε στο 6.
Έτσι, το ύψος του πάνω από αυτό το δέντρο εδώ είναι μόνο 2.
Μπορείτε να πάτε πίσω και να κάνουμε ότι για όλα τα άλλα δέντρα που συζητήθηκε προηγουμένως
αρχίζοντας με το 7 και το 6,
και θα διαπιστώσετε ότι το ύψος όλων αυτών των δέντρων είναι επίσης 2.
>> Ο λόγος που έχουμε μιλήσει για διέταξε δυαδικά δέντρα
και γιατί είναι δροσερό είναι επειδή μπορείτε να πραγματοποιήσετε αναζήτηση από τους
ένα πολύ παρόμοιο τρόπο με την αναζήτηση σε ταξινομημένο πίνακα.
Αυτό είναι που μιλάμε για να πάρει ότι η βελτίωση του χρόνου αναζήτησης
κατά τη διάρκεια της συνδέεται απλή λίστα.
Με μια συνδεδεμένη λίστα - αν θέλετε να βρείτε ένα συγκεκριμένο στοιχείο -
είστε σε καλύτερη πρόκειται να κάνει κάποια γραμμική αναζήτηση
όπου μπορείτε να ξεκινήσετε από την αρχή της λίστας και λυκίσκου ένα-ένα -
έναν κόμβο από έναν κόμβο -
καθ 'όλη τη λίστα μέχρι να βρείτε ό, τι αναζητάτε.
Ότι, αν έχετε ένα δυαδικό δέντρο που είναι αποθηκευμένα σε αυτό το ωραίο σχήμα,
μπορείτε να πάρετε πραγματικά περισσότερο από μια δυαδική αναζήτηση συνεχίζεται
όπου μπορείτε διαίρει και βασίλευε
και αναζήτηση μέσω της κατάλληλης μισο του δένδρου σε κάθε βήμα.
Ας δούμε πώς λειτουργεί.
>> Αν έχουμε - και πάλι, πηγαίνοντας πίσω στην αρχική μας δέντρο -
θα ξεκινήσει στις 7, έχουμε 3 στα αριστερά, 9 στη δεξιά,
και κάτω από το 3 έχουμε το 6.
Αν θέλετε να ψάξετε για τον αριθμό 6 σε αυτό το δέντρο, είχαμε ξεκινήσει από τη ρίζα.
Εμείς θα συγκρίνει την τιμή που ψάχνουμε, ας πούμε 6,
με την τιμή που είναι αποθηκευμένη στον κόμβο που είμαστε σήμερα κοιτάζοντας, 7,
διαπιστώνουμε ότι 6 είναι πράγματι λιγότερο από 7, έτσι θα κινηθεί προς τα αριστερά.
Εάν η τιμή του 6 ήταν μεγαλύτερο από 7, θα είχαμε αντίθετα κινείται προς τα δεξιά.
Επειδή γνωρίζουμε ότι - λόγω της δομής του διέταξε δυαδικού δένδρου μας -
όλες οι τιμές μικρότερες από 7 πρόκειται να αποθηκευτεί προς τα αριστερά του 7,
δεν υπάρχει καμία ανάγκη να ενοχληθεί ακόμη αναζητούν μέσα στη δεξιά πλευρά του δένδρου.
Όταν κινούμαστε προς τα αριστερά και είμαστε τώρα στον κόμβο που περιέχει 3,
μπορούμε να κάνουμε την ίδια σύγκριση και πάλι, όπου συγκρίνουμε το 3 και το 6.
Και διαπιστώνουμε ότι ενώ το 6 - η τιμή που ψάχνουμε - είναι μεγαλύτερη από 3,
μπορούμε να πάμε προς τη δεξιά πλευρά του κόμβου που περιέχει 3.
Δεν υπάρχει αριστερή πλευρά εδώ, γι 'αυτό θα μπορούσε να αγνοηθεί το γεγονός ότι.
Όμως, γνωρίζουμε μόνο ότι, επειδή ψάχνουμε το ίδιο το δέντρο,
και μπορούμε να δούμε ότι το δέντρο δεν έχει παιδιά.
>> Είναι επίσης πολύ εύκολο να αναζητήσετε 6 σε αυτό το δέντρο, αν κάνουμε τους εαυτούς μας ως άνθρωποι,
αλλά ας ακολουθήσει αυτή τη διαδικασία μηχανικά σαν έναν υπολογιστή, θα κάνει
να κατανοήσουμε πραγματικά τον αλγόριθμο.
Σε αυτό το σημείο, είμαστε τώρα ψάχνουν σε έναν κόμβο που περιέχει 6,
και ψάχνουμε για την τιμή 6,
έτσι, πράγματι, έχουμε βρει το κατάλληλο κόμβο.
Βρήκαμε την τιμή 6 σε δέντρο μας, και μπορούμε να σταματήσουμε αναζήτησής μας.
Σε αυτό το σημείο, ανάλογα με το τι συμβαίνει,
μπορούμε να πούμε, ναι, έχουμε βρει την τιμή 6, υπάρχει το δέντρο μας.
Ή, αν σχεδιάζετε να εισάγετε ένα κόμβο ή να κάνει κάτι, μπορούμε να το κάνουμε αυτό σε αυτό το σημείο.
>> Ας κάνουμε ένα ζευγάρι περισσότερες αναζητήσεις μόνο για να δούμε πώς αυτό λειτουργεί.
Ας δούμε τι θα συμβεί εάν επρόκειτο να προσπαθήσουμε και να κοιτάζω προς τα πάνω την τιμή 10.
Αν ήταν να κοιτάζω προς τα πάνω την τιμή 10, θα ξεκινήσει από τη ρίζα.
Θα βλέπατε ότι το 10 είναι μεγαλύτερο από 7, γι 'αυτό θα προχωρήσουμε προς τα δεξιά.
Είχαμε φτάσει στο 9 και συγκρίνετε τις 9 έως τις 10 και βλέπω ότι 9 είναι πράγματι λιγότερο από 10.
Έτσι, και πάλι, εμείς θα προσπαθήσουμε να προχωρήσουμε προς τα δεξιά.
Αλλά σε αυτό το σημείο, θα παρατηρήσετε ότι θα είμαστε σε μηδενική κόμβο.
Δεν υπάρχει τίποτα εκεί. Δεν υπάρχει τίποτα που το 10 θα πρέπει να είναι.
Αυτό είναι όπου μπορούμε να αναφέρουμε αποτυχία - ότι υπάρχει πράγματι όχι 10 στο δέντρο.
Και τέλος, ας περάσουν από την περίπτωση κατά την οποία προσπαθούμε να δούμε μέχρι 1 στο δέντρο.
Αυτό είναι παρόμοιο με αυτό που συμβαίνει, αν κοιτάξουμε το 10, εκτός αντί να πάει προς τα δεξιά,
θα πάμε για να πάει προς τα αριστερά.
Ξεκινάμε στο 7 και να δούμε ότι το 1 είναι μικρότερο του 7, έτσι ώστε να κινηθεί προς τα αριστερά.
Έχουμε φτάσει στο 3 και βλέπω ότι το 1 είναι μικρότερο από 3, οπότε και πάλι θα προσπαθήσουμε να προχωρήσουμε προς τα αριστερά.
Σε αυτό το σημείο έχουμε μηδενική κόμβο, έτσι και πάλι μπορούμε να αναφέρουμε την αποτυχία.
>> Αν θέλετε να μάθετε περισσότερα για δυαδικά δέντρα,
υπάρχουν ένα σωρό διασκέδαση μικρά προβλήματα που μπορείτε να κάνετε με αυτά.
Προτείνω να ασκούν το σχέδιο από αυτά τα διαγράμματα ένα-ένα
και μετά μέσα από όλα τα διαφορετικά βήματα,
γιατί αυτό θα έρθει σε υπερ-βολικό
όχι μόνο όταν κάνεις την κωδικοποίηση Huffman σετ πρόβλημα
αλλά και στις μελλοντικές μαθήματα -
μόλις μαθαίνει πώς να επιστήσω αυτές τις δομές δεδομένων και ότι μέσα από τα προβλήματα
με στυλό και χαρτί ή, στην περίπτωση αυτή, το iPad και γραφίδα.
>> Σε αυτό το σημείο όμως, θα πάμε να προχωρήσουμε για να κάνουν κάποια πρακτική κωδικοποίησης
και πραγματικά παίζουν με αυτά τα δυαδικά δένδρα και να δούμε.
Πάω να μεταβείτε πίσω πάνω στον υπολογιστή μου.
Γι 'αυτό το μέρος του τμήματος, αντί να χρησιμοποιεί CS50 ή CS50 Run χώρους,
Είμαι πρόκειται να χρησιμοποιήσετε τη συσκευή.
>> Μετά μαζί με τις προδιαγραφές του προβλήματος,
Βλέπω ότι είμαι υποτίθεται ότι πρέπει να ανοίξει τη συσκευή,
πηγαίνετε στο φάκελο Dropbox μου, να δημιουργήσετε ένα φάκελο που ονομάζεται Τμήμα 7,
και στη συνέχεια να δημιουργήσετε ένα αρχείο με το όνομα binary_tree.c.
Εδώ πάμε. Έχω τη συσκευή είναι ήδη ανοιχτό.
Πάω να τραβήξει ένα τερματικό.
Πάω να πάει στο φάκελο Dropbox, κάνει ένα κατάλογο με το όνομα section7,
και να δείτε ότι είναι εντελώς άδειο.
Τώρα είμαι πρόκειται να ανοίξει binary_tree.c.
Εντάξει. Εδώ πάμε - κενό αρχείο.
>> Ας πάμε πίσω στις προδιαγραφές.
Η προδιαγραφή ζητά να δημιουργήσετε ένα νέο ορισμό του τύπου
για ένα δυαδικό κόμβο του δένδρου που περιέχει τιμές int -
όπως ακριβώς τις αξίες που σχεδιάσαμε στο διαγραμμάτων μας πριν.
Εμείς πάμε για να χρησιμοποιήσετε αυτό το στερεότυπο typedef ότι έχουμε κάνει εδώ
ότι θα πρέπει να αναγνωρίσει από το σύνολο Πρόβλημα 5 -
αν κάνατε τον τρόπο hash πίνακα της κατάκτησης του προγράμματος ορθογράφος.
Θα πρέπει να αναγνωρίσουμε επίσης από το τμήμα την περασμένη εβδομάδα
όπου μιλήσαμε για συνδεδεμένες λίστες.
Έχουμε αυτό το typedef ενός κόμβου struct,
και έχουμε δώσει στον κόμβο struct αυτό το όνομα του κόμβου struct εκ των προτέρων
έτσι ώστε να μπορεί στη συνέχεια να αναφερθώ σε αυτό, δεδομένου ότι θα θέλουν να έχουν δείκτες κόμβο struct
ως μέρος του struct μας, αλλά έχουμε περικυκλώνεται τότε αυτό -
ή μάλλον, αυτό που περικλείεται - σε ένα typedef
έτσι ώστε, αργότερα στον κώδικα, μπορούμε να αναφερθούμε σε αυτό το struct όπως ακριβώς ένα κόμβο, αντί ενός κόμβου struct.
>> Αυτό πρόκειται να είναι πολύ παρόμοια με τη μεμονωμένα που συνδέονται με τον ορισμό λίστα που είδαμε την περασμένη εβδομάδα.
Για να το κάνετε αυτό, ας αρχίσει με το γράψιμο από το στερεότυπο.
Γνωρίζουμε ότι πρέπει να έχουμε μια ακέραια τιμή,
οπότε θα τεθεί σε int αξία, και στη συνέχεια, αντί να έχουν μόνο ένα δείκτη στο επόμενο στοιχείο -
όπως κάναμε και με μεμονωμένα-linked lists -
θα πάμε να έχουν αριστερά και δεξιά δείκτες παιδί.
Αυτό είναι αρκετά απλή πάρα πολύ - struct node * αριστερό παιδί?
και struct node * δικαίωμα του παιδιού?. Cool.
Αυτό φαίνεται σαν μια πολύ καλή αρχή.
Ας πάμε πίσω στις προδιαγραφές.
>> Τώρα πρέπει να κηρύξει μια παγκόσμια μεταβλητή * κόμβος για τη ρίζα ενός δέντρου.
Εμείς πάμε για να κάνουν αυτό το παγκόσμιο όπως ακριβώς έκανε την πρώτη του δείκτη σε συνδεδεμένη λίστα μας και παγκόσμια.
Αυτό ήταν έτσι ώστε οι λειτουργίες που γράφουμε
δεν έχουμε να κρατήσει περνώντας γύρω από αυτή τη ρίζα -
αν και θα δούμε ότι αν θέλουν να γράψουν αυτές τις λειτουργίες αναδρομικά,
θα ήταν καλύτερα να μην περάσει καν γύρω ως μια παγκόσμια στην πρώτη θέση
αρχικοποίηση και αντ 'αυτού σε τοπικό επίπεδο στην κύρια λειτουργία σας.
Αλλά, θα το κάνουμε σε παγκόσμιο επίπεδο για να ξεκινήσει.
Και πάλι, θα σας δώσουμε ένα ζευγάρι των χώρων, και θα πάω να δηλώσει έναν κόμβο ρίζα *.
Ακριβώς για να βεβαιωθείτε ότι δεν αφήνουν αυτό δεν έχει προετοιμαστεί, Πάω να ισούται με το μηδέν.
Τώρα, στην κύρια λειτουργία - που θα γράψει πολύ γρήγορα εδώ -
int main (int argc, const char * argv []) -
και είμαι πρόκειται να ξεκινήσει δηλώνοντας argv array μου ως const ακριβώς έτσι ότι ξέρω
ότι τα επιχειρήματα αυτά είναι επιχειρήματα που πιθανώς δεν θέλετε να τροποποιήσετε.
Αν θέλω να τα τροποποιήσετε εγώ θα πρέπει μάλλον να κάνει αντίγραφά τους.
Θα δείτε αυτό το πολύ σε κώδικα.
Είναι ωραία ή τον άλλο τρόπο. Είναι ωραία να το αφήσουμε ως - παραλείπουν το const αν θέλετε.
Έβαλα συνήθως ακριβώς έτσι ότι εγώ ο ίδιος υπενθυμίζω
ότι πιθανώς δεν θέλετε να τροποποιήσετε τα επιχειρήματα αυτά.
>> Όπως πάντα, θα πάω να συμπεριλάβετε αυτό το return 0 γραμμή στο τέλος της κύριας.
Εδώ, θα προετοιμάσει τον κόμβο ρίζα μου.
Όπως έχουν τα πράγματα αυτή τη στιγμή, έχω ένα δείκτη που είναι ορίζεται σε μηδέν,
γι 'αυτό είναι που δείχνει σε τίποτα.
Για να αρχίσετε πραγματικά την κατασκευή του κόμβου,
Θα πρέπει πρώτα να εκχωρήσει μνήμη για αυτό.
Πάω να κάνω ότι κάνοντας μνήμη στο σωρό με τη χρήση malloc.
Πάω να θέσει ρίζα ίσο με το αποτέλεσμα της malloc,
και είμαι πρόκειται να χρησιμοποιήσετε το sizeof χειριστή να υπολογίσει το μέγεθος ενός κόμβου.
Ο λόγος που χρησιμοποιώ sizeof κόμβο, σε αντίθεση, ας πούμε,
να κάνει κάτι τέτοιο - malloc (4 + 4 +4) ή malloc 12 -
είναι γιατί θέλω κωδικό μου να είναι όσο το δυνατόν συμβατά.
Θέλω να είμαι σε θέση να εκμεταλλευτώ αυτή. Αρχείο γ, να καταρτίσει τη συσκευή,
και την κατάρτιση στη συνέχεια σε 64-bit Mac μου -
ή σε μια εντελώς διαφορετική αρχιτεκτονική -
και θέλω όλα αυτά να λειτουργούν με τον ίδιο.
>> Αν κάνω υποθέσεις για το μέγεθος των μεταβλητών -
το μέγεθος μιας int ή το μέγεθος ενός δείκτη -
τότε κάνω και παραδοχές σχετικά με τα είδη των αρχιτεκτονικών
στις οποίες κωδικό μου μπορεί να μεταγλωττίσετε επιτυχώς όταν τρέχει.
Πάντα να χρησιμοποιείτε sizeof, σε αντίθεση με το χέρι αθροίζοντας τα πεδία struct.
Ο άλλος λόγος είναι ότι μπορεί να υπάρχουν, επίσης, να γεμίσει ότι ο μεταγλωττιστής βάζει μέσα στο struct.
Ακόμα και αθροίζοντας μόνο τα μεμονωμένα πεδία δεν είναι κάτι που συνήθως θέλουν να κάνουν,
έτσι, να διαγράψετε αυτή τη γραμμή.
Τώρα, για να προετοιμάσει αυτό το πραγματικά κόμβο ρίζα,
Πάω να πρέπει να συνδέσετε τις τιμές για κάθε ένα από διάφορους τομείς της.
Για παράδειγμα, για την αξία Ξέρω ότι θέλω να προετοιμαστεί έως 7,
και για τώρα πάω να ορίσετε το αριστερό παιδί να είναι null
και το δικαίωμα του παιδιού να είναι επίσης άκυρη. Μεγάλη!
Έχουμε κάνει το μέρος του spec.
>> Η προδιαγραφή κάτω στο κάτω μέρος της σελίδας 3 με ρωτάει να δημιουργήσει τρεις κόμβους -
μια που περιέχει 3, ένα που περιέχει 6, και ένα με 9 -
σύρμα και στη συνέχεια επάνω έτσι ώστε να φαίνεται ακριβώς όπως το διάγραμμα δέντρο μας
ότι μιλούσαμε για το παρελθόν.
Ας το κάνουμε αυτό πολύ γρήγορα εδώ.
Θα δείτε πολύ γρήγορα ότι Πάω να αρχίσετε να γράφετε μια δέσμη των διπλών κώδικα.
Πάω να δημιουργήσει έναν κόμβο * και Πάω να το ονομάσουμε τρία.
Πάω να το θέσει ίση με malloc (sizeof (κόμβος)).
Πάω να θέσει τρεις-> value = 3.
Τρεις -> left_child = NULL? Τρία -> δεξί NULL _child =?, Καθώς και.
Που φαίνεται αρκετά παρόμοια με την προετοιμασία της ρίζας, και αυτό είναι ακριβώς ό, τι
Πάω να πρέπει να κάνω αν αρχίσει την προετοιμασία 6 και 9, καθώς και.
Θα το κάνουμε αυτό πολύ γρήγορα εδώ - στην πραγματικότητα, Πάω να κάνουμε μια μικρή αντιγραφή και επικόλληση,
και βεβαιωθείτε ότι εγώ - εντάξει.
Τώρα, έχω το πήρα αντιγραφή και μπορώ να πάω μπροστά και να θέσει αυτό ίσο με 6.
Μπορείτε να δείτε ότι αυτό παίρνει λίγο χρόνο και δεν είναι υπερ-αποδοτική.
Σε μόλις λίγο, θα γράψω μια λειτουργία που θα το κάνει αυτό για εμάς.
Θέλω να το αντικαταστήσετε με ένα 9, το αντικαταστήσουμε με το 6.
>> Τώρα έχουμε όλοι μας από τους κόμβους που δημιουργήθηκε και αρχικοποιηθεί.
Έχουμε ρίζα μας ισούται με το 7, ή που περιέχει την τιμή 7,
κόμβο μας που περιέχει 3, ο κόμβος μας που περιέχει 6, και ο κόμβος μας που περιέχει 9.
Σε αυτό το σημείο, το μόνο που έχουμε να κάνουμε είναι ό, τι μέχρι σύρμα.
Ο λόγος που αρχικοποιηθεί όλα τα null δείκτες να είναι ακριβώς έτσι ώστε να μπορώ να βεβαιωθείτε ότι
Δεν έχω κανένα δεν έχει προετοιμαστεί δείκτες εκεί κατά λάθος.
Και, επίσης, δεδομένου ότι, σε αυτό το σημείο, έχω μόνο να συνδέσετε πραγματικά τους κόμβους μεταξύ τους -
με αυτές που πραγματικά είστε συνδεδεμένος με - δεν έχω να περάσει και να κάνει
βεβαιωθείτε ότι όλα τα μηδενικά είναι εκεί στις κατάλληλες θέσεις.
>> Ξεκινώντας από τη ρίζα, ξέρω ότι το αριστερό παιδί της ρίζας είναι 3.
Ξέρω ότι το δικαίωμα του παιδιού της ρίζας είναι 9.
Μετά από αυτό, το μόνο άλλο παιδί που έχω αφήσει να ανησυχείτε για
είναι σωστό παιδί 3, η οποία είναι 6.
Σε αυτό το σημείο, όλα φαίνονται πολύ καλά.
Θα διαγράψετε κάποια από αυτές τις γραμμές.
Τώρα ό, τι φαίνεται αρκετά καλό.
Ας επιστρέψουμε με τις προδιαγραφές μας και να δούμε τι πρέπει να κάνουμε στη συνέχεια.
>> Σε αυτό το σημείο, πρέπει να γράψουμε μια λειτουργία που ονομάζεται «περιέχει»
με ένα πρωτότυπο της «bool Περιέχει (int τιμή)».
Και αυτό περιλαμβάνει τη λειτουργία πρόκειται να επιστρέψει αλήθεια
αν το δέντρο επεσήμανε από την παγκόσμια μεταβλητή ρίζα μας
περιέχει την τιμή διέρχεται εντός του λειτουργία και ψευδή διαφορετικά.
Ας πάμε μπροστά και να το κάνουμε αυτό.
Αυτό πρόκειται να είναι ακριβώς όπως την αναζήτηση που κάναμε με το χέρι στο iPad μόνο λίγο πριν.
Ας μεγεθύνετε σε λίγο και μετακινηθείτε προς τα πάνω.
Εμείς πάμε για να βάλει αυτή τη λειτουργία ακριβώς πάνω από το κύριο έργο μας
έτσι ώστε δεν έχουμε να κάνουμε οποιοδήποτε είδος των πρωτοτύπων.
Έτσι, περιέχει bool (int αξία).
Εκεί πάμε. Υπάρχει δήλωση στερεότυπο μας.
Ακριβώς για να βεβαιωθείτε ότι αυτό θα συγκεντρώνει,
Πάω να προχωρήσει και αυτό που ακριβώς ίσο με επιστροφή ψευδείς.
Αυτή τη στιγμή η λειτουργία αυτή απλά δεν θα κάνει τίποτα και πάντα αναφέρουν ότι
η τιμή που ψάχνουμε δεν είναι στο δέντρο.
>> Σε αυτό το σημείο, είναι πιθανώς μια καλή ιδέα -
αφού έχουμε γράψει ένα σωρό κώδικα και δεν έχουμε καν δοκιμάσει τον έλεγχο αυτό ακόμη -
για να βεβαιωθείτε ότι συγκεντρώνει όλα.
Υπάρχουν μερικά πράγματα που πρέπει να κάνετε για να βεβαιωθείτε ότι αυτό πράγματι θα καταρτίσει.
Πρώτον, να δούμε αν έχουμε χρησιμοποιήσει οποιεσδήποτε λειτουργίες σε κάθε βιβλιοθήκες που δεν έχουν ακόμη περιληφθεί.
Οι λειτουργίες που έχουμε χρησιμοποιήσει μέχρι τώρα είναι malloc,
και στη συνέχεια, έχουμε επίσης τη χρήση αυτού του τύπου - αυτό όχι συνηθισμένες τύπου που ονομάζεται «bool' -
η οποία περιλαμβάνεται στο πρότυπο bool αρχείο κεφαλίδας.
Εμείς σίγουρα θέλετε να συμπεριλάβετε bool.h πρότυπο για την bool τύπου,
και θέλουμε επίσης να περιλαμβάνουν lib.h # πρότυπο για τις βιβλιοθήκες πρότυπο
που περιλαμβάνουν malloc, και δωρεάν, και όλα αυτά.
Έτσι, σμίκρυνση, θα πάμε να σταματήσουν το κάπνισμα.
Ας προσπαθήσουμε και να βεβαιωθείτε ότι αυτό το έκανε πραγματικότητα μεταγλώττιση.
Βλέπουμε ότι το κάνει, έτσι είμαστε στο σωστό δρόμο.
>> Ας ανοίξουμε και πάλι binary_tree.c.
Καταρτίζει. Ας πάμε κάτω και βεβαιωθείτε ότι εισάγουμε κάποιες κλήσεις προς Περιέχει λειτουργία μας -
ακριβώς για να βεβαιωθείτε ότι όλα είναι ωραία και καλά.
Για παράδειγμα, όταν κάναμε κάποιες αναζητήσεις στο δέντρο μας νωρίτερα,
προσπαθήσαμε να κοιτάζω προς τα πάνω τις τιμές 6, 10, και 1, και ξέραμε ότι 6 ήταν στο δέντρο,
10 δεν ήταν στο δέντρο, και 1 δεν ήταν στο δέντρο, είτε.
Ας χρησιμοποιήσουμε αυτές τις κλήσεις του δείγματος ως ένας τρόπος για να καταλάβω αν ή όχι
Περιέχει λειτουργία μας λειτουργεί.
Για να το κάνουμε αυτό, είμαι πρόκειται να χρησιμοποιήσετε τη λειτουργία printf,
και θα πάμε για να εκτυπώσετε το αποτέλεσμα της κλήσης να περιέχει.
Πάω να βάλει σε μια σειρά »περιέχει (% d) = επειδή
θα πάμε για να συνδέσετε την αξία που εμείς πάμε να δούμε για,
και =% s \ n "και να το χρησιμοποιήσετε ως συμβολοσειρά μορφής μας.
Είμαστε ακριβώς πρόκειται να δούμε - κυριολεκτικά εκτυπώσετε στην οθόνη -
αυτό που μοιάζει με μια κλήση συνάρτησης.
Αυτό δεν είναι στην πραγματικότητα η κλήση της συνάρτησης.
Αυτή είναι μόνο μια σειρά σχεδιαστεί για να μοιάζει με μια κλήση συνάρτησης.
>> Τώρα, θα πάμε να συνδέσετε τις τιμές.
Εμείς πάμε για να προσπαθήσουμε περιλαμβάνει στις 6,
και τότε τι θα πάμε να κάνουμε εδώ είναι να χρησιμοποιήσετε αυτό το τριαδικό χειριστή.
Ας δούμε - περιέχει 6 - έτσι, τώρα έχω περιείχε 6 και αν περιέχει 6 είναι αλήθεια,
η σειρά που θα πάμε να στείλετε σε μορφή χαρακτήρων% s
πρόκειται να είναι η συμβολοσειρά "αλήθεια".
Ας μετακινηθείτε σε λίγο.
Σε αντίθετη περίπτωση, θέλουμε να στείλουμε το string "ψευδή" εάν περιέχει 6 επιστρέφει false.
Αυτό είναι λίγο ανόητη εμφάνιση, αλλά μπορώ να καταλάβω εγώ θα μπορούσε κάλλιστα να απεικονίζουν
τι ο χειριστής τριαδικό μοιάζει αφού δεν έχουμε δει για λίγο.
Αυτό θα είναι ένα ωραίο, πρακτικός τρόπος για να καταλάβουμε αν Περιέχει λειτουργία μας λειτουργεί.
Πάω να μετακινηθείτε προς τα πίσω πάνω προς τα αριστερά,
και Πάω να αντιγράψετε και να επικολλήσετε αυτή τη γραμμή μερικές φορές.
Θα αλλάξει ορισμένες από αυτές τις αξίες γύρω,
έτσι αυτό πρόκειται να είναι 1, και αυτό πρόκειται να είναι 10.
>> Σε αυτό το σημείο έχουμε μια ωραία λειτουργία περιέχει.
Έχουμε κάποιες εξετάσεις, και θα δούμε αν αυτό όλες οι εργασίες.
Σε αυτό το σημείο έχουμε γράψει λίγο περισσότερο κώδικα.
Ώρα να σταματήσουν και να βεβαιωθείτε ότι όλα συγκεντρώνει ακόμα.
Κλείστε έξω, και τώρα ας προσπαθήσουμε κάνουν δυαδικό δέντρο και πάλι.
Λοιπόν, φαίνεται σαν να έχεις ένα λάθος,
και έχουμε αυτό δηλώνοντας ρητά τη λειτουργία της βιβλιοθήκης printf.
Μοιάζει με εμείς πρέπει να πάμε μέσα και # include standardio.h.
Και με αυτό, θα πρέπει να συγκεντρώνει τα πάντα. Είμαστε όλοι καλά.
Τώρα ας προσπαθήσουμε τρέχει δυαδικό δέντρο και να δούμε τι θα συμβεί.
Εδώ είμαστε,. / Binary_tree,
και βλέπουμε ότι, όπως ήταν αναμενόμενο -
γιατί δεν έχουν υλοποιηθεί ακόμα περιέχει,
ή μάλλον, έχουμε μόλις τεθεί σε αντάλλαγμα ψευδούς -
βλέπουμε ότι αυτό είναι μόνο για την επιστροφή ψευδή όλα αυτά,
έτσι ώστε να είναι όλοι εργάζονται ως επί το πλείστον αρκετά καλά.
>> Ας πάμε πίσω σε εφαρμογή και στην πραγματικότητα περιέχει σε αυτό το σημείο.
Πάω να μετακινηθείτε προς τα κάτω, zoom in, και -
Θυμηθείτε, ο αλγόριθμος που χρησιμοποιήθηκε ήταν ότι ξεκινήσαμε στον κόμβο ρίζα
και στη συνέχεια, σε κάθε κόμβο που συναντούμε, κάνουμε μια σύγκριση,
και με βάση αυτή τη σύγκριση που είτε κινούνται προς τα αριστερά ή παιδί στο σωστό παιδί.
Αυτό πρόκειται να εξετάσουμε πολύ παρόμοια με τον κώδικα δυαδική αναζήτηση που γράψαμε νωρίτερα στον όρο.
Όταν ξεκινήσει, ξέρουμε ότι θέλουμε να κρατήσουμε την τρέχουσα κόμβο
ότι ψάχνουμε σε, και ο τρέχων κόμβος πρόκειται να προετοιμαστεί για τον κόμβο ρίζα.
Και τώρα, θα πάμε να συνεχίσουμε μέσα από το δέντρο,
και να θυμάστε ότι μας σταματήσει κατάσταση -
όταν πραγματικά εργάστηκαν μέσα από το παράδειγμα με το χέρι -
ήταν όταν συναντήσαμε μια μηδενική κόμβο,
όταν δεν κοιτάξαμε μηδενική παιδί,
αλλά μάλλον, όταν στην πραγματικότητα κινείται με έναν κόμβο στο δέντρο
και διαπίστωσε ότι είμαστε σε ένα κόμβο null.
Εμείς πάμε για να επαναλάβει μέχρι τρέχουσα δεν είναι ίσο με το μηδέν.
Και τι θα κάνουμε;
Εμείς πάμε για να ελέγξετε αν (τρέχουσα -> αξία αξίας ==),
τότε ξέρουμε ότι έχουμε βρεθεί πραγματικά τον κόμβο που ψάχνουμε.
Έτσι, εδώ, μπορούμε να επιστρέψουμε αλήθεια.
Διαφορετικά, θέλουμε να δούμε κατά πόσον ή όχι η τιμή είναι μικρότερη από την τιμή.
Εάν η τιμή του τρέχοντος κόμβου είναι μικρότερη από την τιμή που ψάχνουμε,
θα πάμε για να μετακινηθείτε προς τα δεξιά.
Έτσι, τρέχουσα = τρέχουσα -> right_child? Και αλλιώς, θα πάμε για να μετακινηθείτε προς τα αριστερά.
τρέχουσα τρέχουσα = -> left_child?. Pretty απλή.
>> Μπορείτε πιθανώς αναγνωρίσει το βρόχο που μοιάζει πολύ με αυτό από
δυαδική αναζήτηση νωρίτερα στον όρο, εκτός από τότε έχουμε να κάνουμε με χαμηλή, μεσαία και υψηλή.
Εδώ, εμείς απλά πρέπει να δούμε σε τρέχουσα αξία,
γι 'αυτό είναι ωραίο και απλό.
Ας βεβαιωθείτε ότι αυτός ο κώδικας εργασίας.
Πρώτον, βεβαιωθείτε ότι συγκεντρώνει. Μοιάζει να κάνει.
Ας προσπαθήσουμε τρέχει.
Και πράγματι, εκτυπώνει από ό, τι περιμέναμε.
Βρίσκει τις 6 το δέντρο, δεν βρείτε 10 γιατί 10 δεν είναι στο δέντρο,
και δεν βρει 1 1 είτε επειδή δεν είναι, επίσης, στο δέντρο.
Cool πράγματα.
>> Εντάξει. Ας επιστρέψουμε με τις προδιαγραφές μας και να δούμε τι γίνεται στη συνέχεια.
Τώρα, θέλει να προσθέσει λίγο περισσότερο κόμβους στο δέντρο μας.
Δεν θέλει να προσθέσει 5, 2, και 8, και βεβαιωθείτε ότι περιέχει κώδικα μας
εξακολουθεί να λειτουργεί όπως αναμένεται.
Πάμε να το κάνουμε αυτό.
Σε αυτό το σημείο, αντί να κάνει αυτό το ενοχλητικό αντιγραφή και επικόλληση πάλι,
ας γράψει μια λειτουργία για να δημιουργήσετε πραγματικά έναν κόμβο.
Αν μετακινηθείτε προς τα κάτω σε όλη τη διαδρομή στην κύρια, βλέπουμε ότι έχουμε κάνει αυτό
πολύ παρόμοιο κώδικα ξανά και ξανά κάθε φορά που θέλουμε να δημιουργήσουμε έναν κόμβο.
>> Ας γράψουμε μια συνάρτηση η οποία θα βασιστεί στην πραγματικότητα έναν κόμβο για μας και να το επιστρέψουν.
Πάω να το ονομάσουμε build_node.
Πάω να οικοδομήσουμε ένα κόμβο με μια συγκεκριμένη αξία.
Μεγεθύνετε εδώ.
Το πρώτο πράγμα που θα κάνω είναι να δημιουργήσετε πραγματικά χώρος για τον κόμβο στο σωρό.
Έτσι, ο κόμβος * n = malloc (sizeof (κόμβος))? N -> value = τιμή?
και στη συνέχεια, εδώ, είμαι απλώς πρόκειται να προετοιμάσει όλα τα πεδία να είναι κατάλληλες τιμές.
Και στο τέλος, εμείς θα επιστρέψει κόμβο μας.
Εντάξει. Ένα πράγμα που πρέπει να σημειωθεί είναι ότι αυτό το δικαίωμα λειτουργία εδώ
πρόκειται να επιστρέψει ένα δείκτη στη μνήμη που έχει σωρό που χορηγήθηκαν.
Τι είναι ωραίο για αυτό είναι ότι αυτός ο κόμβος τώρα -
πρέπει να το δηλώσει στο σωρό, διότι αν το δηλώσει στη στοίβα
δεν θα είμαστε σε θέση να το κάνουμε σε αυτή τη λειτουργία, όπως αυτό.
Ότι η μνήμη θα βγουν έξω από το πεδίο εφαρμογής
και θα είναι άκυρη αν προσπαθήσαμε να έχουν πρόσβαση αργότερα.
Από τη στιγμή που δηλώνουν σωρό-κατανεμημένη μνήμη,
πρόκειται να πρέπει να φροντίσουν για την απελευθέρωση αργότερα
για το πρόγραμμά μας να μην διαρρεύσει καμία μνήμη.
Έχουμε βαρκάδες στο ότι για όλα τα άλλα στον κώδικα
μόνο για λόγους απλούστευσης του εκείνη την εποχή,
αλλά αν γράψετε ποτέ μια λειτουργία που μοιάζει με αυτό
όπου έχετε - μερικοί αποκαλούν μια malloc ή realloc μέσα -
θέλετε να βεβαιωθείτε ότι έχετε βάλει κάποιο είδος της σχόλιο μέχρι εδώ που λέει,
hey, ξέρετε, επιστρέφει ένα σωρό-κατένειμε κόμβο αρχικοποιείται με την πέρασαν-σε αξία.
Και τότε θα θέλετε να βεβαιωθείτε ότι έχετε θέσει σε κάποια σημείωση που λέει
ο καλών πρέπει να ελευθερώσουν την επιστροφή της μνήμης.
Με αυτόν τον τρόπο, αν κάποιος πηγαίνει ποτέ και χρησιμοποιεί αυτή τη λειτουργία,
ξέρουν πως ό, τι παίρνουν πίσω από τη λειτουργία
σε κάποιο σημείο θα πρέπει να απελευθερωθεί.
>> Υποθέτοντας ότι όλα είναι ωραία και καλά εδώ,
μπορούμε να πάμε κάτω στον κώδικα μας και να αντικαταστήσει όλες αυτές τις γραμμές εδώ
με κλήσεις προς κατασκευή κόμβου λειτουργία μας.
Ας το κάνουμε αυτό πολύ γρήγορα.
Το ένα μέρος που δεν πρόκειται να αντικαταστήσει αυτό το μέρος είναι εδώ κάτω
στο κάτω μέρος όπου μπορούμε πραγματικά σύρμα μέχρι τους κόμβους στο σημείο ο ένας στον άλλο,
επειδή αυτό δεν μπορούμε να κάνουμε στη λειτουργία μας.
Αλλά, ας κάνουμε root = build_node (7)? Κόμβο * τρεις build_node = (3)?
κόμβο * έξι = build_node (6)? κόμβο * εννιά = build_node (9)?.
Και τώρα, θελήσαμε επίσης να προσθέσετε κόμβους για -
κόμβο * πέντε = build_node (5)? ​​κόμβο * = build_node οκτώ (8)?
και ποιο ήταν το άλλο κόμβο; Ας δούμε εδώ. Θέλαμε να προσθέσουμε και ένα 2 -
* Δύο κόμβος = build_node (2)?.
Εντάξει. Σε αυτό το σημείο, ξέρουμε ότι έχουμε το 7, το 3, το 9 και το 6
όλα ενσύρματο μέχρι κατάλληλα, αλλά τι γίνεται με το 5, το 8 και το 2;
Για να διατηρήσετε τα πάντα με την κατάλληλη σειρά,
γνωρίζουμε ότι το δικαίωμα του παιδιού τρία είναι 6.
Έτσι, αν θα πάμε για να προσθέσετε το 5,
η 5 ανήκει επίσης στη δεξιά πλευρά του δένδρου της οποίας 3 είναι η ρίζα,
έτσι 5 ανήκει το αριστερό παιδί του 6.
Μπορούμε να το κάνουμε αυτό με το ρητό, έξι -> left_child = πέντε?
και στη συνέχεια το 8 ανήκει σαν αριστερό παιδί 9, οπότε εννέα -> left_child = οκτώ?
και στη συνέχεια 2 είναι το αριστερό παιδί του 3, ώστε να μπορούμε να το κάνουμε αυτό εδώ - σου -> left_child = δύο?.
Αν δεν έχετε αρκετά ακολουθήσει μαζί με αυτό, σας προτείνω να το σύρει έξω τον εαυτό σας.
>> Εντάξει. Ας σώσει αυτό. Ας βγούμε έξω και να βεβαιωθείτε ότι συγκεντρώνει,
και στη συνέχεια μπορούμε να προσθέσουμε σε κλήσεων περιέχει μας.
Μοιάζει με ό, τι συνθέτει ακόμα.
Ας πάμε και να προσθέσετε σε κάποια περιέχει κλήσεις.
Και πάλι, Πάω να κάνω ένα μικρό κομμάτι της αντιγραφής και επικόλλησης.
Τώρα ας αναζήτηση για 5, 8, και 2. Εντάξει.
Ας βεβαιωθείτε ότι όλα αυτά εξακολουθεί να φαίνεται καλό. Μεγάλη! Αποθηκεύστε και κλείστε.
Τώρα ας κάνουμε, συγκέντρωση, και τώρα ας τρέξει.
Από τα αποτελέσματα, φαίνεται ότι όλα λειτουργούν ακριβώς ωραία και καλά.
Μεγάλη! Έτσι τώρα έχουμε γράψει λειτουργούν Περιέχει μας.
Ας προχωρήσουμε και να αρχίσουν να εργάζονται για το πώς να εισάγετε τους κόμβους στο δέντρο
δεδομένου ότι, όπως το κάνουμε τώρα, τα πράγματα δεν είναι πολύ όμορφη.
>> Αν πάμε πίσω στις προδιαγραφές,
να μας ζητά να γράψει μια λειτουργία που ονομάζεται εισάγετε - και πάλι, επιστρέφοντας ένα bool
για το αν ή όχι θα μπορούσαμε να εισάγετε στην πραγματικότητα τον κόμβο στο δέντρο -
και στη συνέχεια η τιμή να εισάγετε στο δέντρο ορίζεται ως
το μόνο επιχείρημα για τη λειτουργία ένθετο μας.
Θα επιστρέψει αλήθεια αν θα μπορούσαμε να εισάγετε πράγματι τον κόμβο που περιέχει τιμή στο δέντρο,
πράγμα που σημαίνει ότι εμείς, ένα, είχε αρκετή μνήμη,
και στη συνέχεια δύο, αυτός ο κόμβος δεν υπάρχουν ήδη στο δέντρο δεδομένου -
Θυμηθείτε, δεν πρόκειται να έχουν διπλές τιμές στο δέντρο, απλά για να κάνει τα πράγματα απλά.
Εντάξει. Επιστροφή στην κωδικού.
Ανοίξτε το επάνω. Ζουμ σε λίγο, στη συνέχεια, μετακινηθείτε προς τα κάτω.
Ας θέσει τη λειτουργία ένθετο δεξιά πάνω από τα περιέχει.
Και πάλι, πρόκειται να κληθεί bool ένθετο (int αξία).
Δώστε λίγο περισσότερο χώρο, και στη συνέχεια, ως προεπιλογή,
ας βάλουμε σε αντάλλαγμα ψευδούς στο τέλος.
Τώρα, κάτω στο κάτω μέρος, πάμε μπροστά και όχι το χέρι την κατασκευή των κόμβων
στην κύρια τον εαυτό μας και τους καλωδίωση μέχρι το σημείο στο άλλο, όπως κάνουμε,
θα στηρίζονται σε λειτουργία ένθετο μας να το κάνουμε αυτό.
Εμείς δεν θα στηρίζονται σε λειτουργία ένθετο μας να χτίσουμε ολόκληρο το δέντρο από το μηδέν ακριβώς ακόμα,
αλλά μάλλον θα απαλλαγούμε από αυτές τις γραμμές - we'll σχόλιο από αυτές τις γραμμές -
που οικοδόμηση των κόμβων 5, 8, και 2.
Και αντ 'αυτού, θα εισάγετε κλήσεις σε λειτουργία ένθετο μας
για να βεβαιωθείτε ότι αυτό λειτουργεί πραγματικά.
Εδώ πάμε.
>> Τώρα έχουμε σχολίασε από αυτές τις γραμμές.
Έχουμε μόνο 7, 3, 9, και 6 στο δέντρο μας σε αυτό το σημείο.
Για να βεβαιωθείτε ότι αυτό είναι όλοι εργάζονται,
μπορούμε σμίκρυνση, να δυαδικό δέντρο μας,
τρέχει, και μπορούμε να δούμε ότι περιέχει μας λέει τώρα ότι είμαστε απόλυτα δίκιο -
5, 8 και 2 δεν είναι πλέον στο δέντρο.
Επιστροφή στον κώδικα,
και πώς θα πάμε να εισάγετε;
Θυμηθείτε τι κάναμε όταν ήμασταν πραγματικά εισαγωγή 5, 8, και 2 προηγουμένως.
Παίξαμε το παιχνίδι Plinko όπου ξεκινήσαμε στη ρίζα,
πήγε κάτω από το ένα δέντρο με ένα-ένα
μέχρι να βρεθεί το κατάλληλο κενό,
και τότε ενσύρματη στον κόμβο στο κατάλληλο σημείο.
Εμείς πάμε να κάνουμε το ίδιο πράγμα.
Αυτό είναι βασικά σα να γράφουμε τον κώδικα που χρησιμοποιούνται για την λειτουργία περιέχει
για να βρείτε το σημείο όπου ο κόμβος θα πρέπει να είναι,
και στη συνέχεια να είμαστε ακριβώς πρόκειται να τοποθετήσετε τον κόμβο εκεί.
Ας αρχίσουμε να κάνουμε αυτό.
>> Έτσι έχουμε έναν κόμβο * = τρέχουσα ρίζα? Είμαστε ακριβώς πρόκειται να ακολουθήσει ο κώδικας περιέχει
μέχρι να βρούμε ότι δεν εργάζονται αρκετά για μας.
Εμείς πάμε για να περάσει μέσα από το δέντρο, ενώ το τρέχον στοιχείο δεν είναι μηδενική,
και αν βρούμε τρέχουσα αξία που είναι ίση με την αξία που προσπαθούμε να εισάγετε -
καλά, αυτό είναι μία από τις περιπτώσεις στις οποίες δεν μπορούσαμε να εισαχθεί στην πραγματικότητα τον κόμβο
στο δέντρο, γιατί αυτό σημαίνει ότι έχουμε μια διπλή αξία.
Εδώ είμαστε πραγματικά πρόκειται να επιστρέψει ψευδείς.
Τώρα αλλιώς, αν η αξία τρέχουσα είναι μικρότερη από την αξία,
Τώρα ξέρουμε ότι κινούμαστε προς τη σωστή
επειδή η τιμή ανήκει στο δεξιό μισό του δέντρου τρέχουσα.
Διαφορετικά, θα πάμε να κινηθεί προς τα αριστερά.
Αυτό είναι βασικά Περιέχει μας λειτουργούν εκεί.
>> Σε αυτό το σημείο, αφού έχουμε ολοκληρώσει αυτό το βρόχο while,
τρέχουσα δείκτη μας θα πρέπει να δείχνει σε null
αν η λειτουργία δεν έχει ήδη επιστραφεί.
Είμαστε ως εκ τούτου έχει τρέχουσα στο σημείο όπου θέλετε να εισαγάγετε το νέο κόμβο.
Αυτό που απομένει να γίνει είναι να οικοδομήσουμε στην πραγματικότητα το νέο κόμβο,
το οποίο μπορούμε να κάνουμε αρκετά εύκολα.
Μπορούμε να χρησιμοποιήσουμε υπερ-βολική λειτουργία μας κόμβο κατασκευής,
και κάτι που δεν είχαμε κάνει νωρίτερα -
έχουμε ακριβώς το είδος του πήρε για δεδομένος, αλλά τώρα θα κάνουμε ακριβώς για να βεβαιωθείτε ότι -
θα δοκιμάσουμε να βεβαιωθείτε ότι η τιμή που επιστρέφεται από το νέο κόμβο ήταν στην πραγματικότητα
όχι μηδενική, επειδή δεν θέλουμε να αρχίσουν την πρόσβαση σε αυτή τη μνήμη, αν είναι null.
Μπορούμε να ελέγξετε για να βεβαιωθείτε ότι νέος κόμβος δεν είναι ίσο με null.
Ή αντίθετα, μπορούμε απλά να δούμε αν είναι πραγματικά μηδενική,
και αν είναι μηδενική, τότε μπορούμε απλά να επιστρέψει ψευδείς νωρίς.
>> Σε αυτό το σημείο, πρέπει να σύρμα νέου κόμβου σε κατάλληλο σημείο του στο δέντρο.
Αν κοιτάξουμε πίσω στο κεντρικό και όπου ήμασταν πραγματικά καλωδίωση σε τιμές πριν,
βλέπουμε ότι ο τρόπος με τον οποίο το έκαναν όταν θελήσαμε να βάλει 3 στο δέντρο
ήταν προσεγγίσαμε το αριστερό παιδί της ρίζας.
Όταν βάζουμε 9 στο δέντρο, θα έπρεπε να έχουν πρόσβαση στο δικαίωμα του παιδιού της ρίζας.
Έπρεπε να έχουμε ένα δείκτη προς τη μητρική εταιρεία, προκειμένου να τεθεί μια νέα τιμή στο δέντρο.
Κύλιση πίσω μέχρι να εισάγετε, το οποίο δεν πρόκειται να λειτουργήσει αρκετά εδώ
επειδή δεν έχουμε ένα δείκτη γονέα.
Αυτό που θέλουμε να είμαστε σε θέση να κάνουμε είναι, σε αυτό το σημείο,
ελέγξτε αξία της μητρικής και να δούμε - καλά, Θεέ,
αν η αξία της μητρικής είναι μικρότερη από την τρέχουσα αξία,
κάντε δεξί παιδί του γονέα θα πρέπει να είναι ο νέος κόμβος?
αλλιώς, το αριστερό παιδί του γονέα θα πρέπει να είναι ο νέος κόμβος.
Όμως, δεν έχουμε αυτό το δείκτη του γονέα αρκετά ακόμα.
>> Για να το πάρει, είμαστε στην πραγματικότητα θα πρέπει να την παρακολουθείτε καθώς περνάμε από το δέντρο
και να βρει το κατάλληλο σημείο στο βρόχο μας παραπάνω.
Μπορούμε να το κάνουμε αυτό με κύλιση προς τα πίσω μέχρι την κορυφή της λειτουργίας μας ένθετο
παρακολούθησης και μια άλλη μεταβλητή δείκτη που ονομάζεται μητρική.
Εμείς πάμε για να ισούται με το μηδέν αρχικά,
και στη συνέχεια, κάθε φορά που περνάμε από το δέντρο,
θα πάμε για να ρυθμίσετε το δείκτη του γονέα για να ταιριάζει με τον τρέχοντα δείκτη.
Ορισμός γονέα ίσο με τρέχουσα.
Με αυτό τον τρόπο, κάθε φορά που περνάμε,
θα πάμε για να διασφαλίσουν ότι η τρέχουσα δείκτης παίρνει αυξάνεται
ο δείκτης μητρικής ακολουθεί - μόνο ένα επίπεδο υψηλότερο από την τρέχουσα δείκτη στο δέντρο.
Όλα αυτά φαίνεται αρκετά καλό.
>> Νομίζω ότι το μόνο πράγμα που θα θέλετε να ρυθμίσετε αυτή την κατασκευή είναι ο κόμβος επιστρέφει null.
Για να πάρετε την κατασκευή κόμβου στην πραγματικότητα με επιτυχία επιστρέψει null,
θα πρέπει να τροποποιήσει τον εν λόγω κώδικα,
γιατί εδώ, δεν μπορούμε ποτέ δοκιμαστεί για να βεβαιωθείτε ότι η malloc επέστρεψε ένα έγκυρο δείκτη.
Έτσι, αν (n = NULL!), Τότε -
αν malloc επέστρεψε ένα έγκυρο δείκτη, τότε θα γίνει η προετοιμασία?
αλλιώς, απλά θα επιστρέψει και αυτό θα καταλήξει null επιστρέφουν για μας.
Τώρα το μόνο που φαίνεται αρκετά καλό. Ας βεβαιωθείτε ότι αυτό συγκεντρώνει πραγματικότητα.
Κάντε δυαδικό δέντρο, και OH, έχουμε κάποια πράγματα συμβαίνουν εδώ.
>> Έχουμε μια έμμεση δήλωση της λειτουργίας κατασκευή κόμβου.
Και πάλι, με αυτούς τους compilers, θα πάμε για να ξεκινήσει στην κορυφή.
Τι σημαίνει αυτό πρέπει να είναι ότι είμαι καλώντας την κατασκευή κόμβου πριν έχω δηλώσει αυτό στην πραγματικότητα.
Ας πάμε πίσω στον κώδικα πραγματικά γρήγορα.
Μετακινηθείτε προς τα κάτω, και αρκετά βέβαιος, λειτουργία ένθετο μου έχει δηλωθεί
πάνω από τη λειτουργία του κόμβου κατασκευής,
αλλά εγώ προσπαθώ να χρησιμοποιήσουν την κατασκευή κόμβου στο εσωτερικό του ένθετου.
Πάω να πάει και αντιγραφή - επικόλληση και στη συνέχεια τον κόμβο κατασκευής τρόπο λειτουργίας εδώ στην κορυφή.
Με αυτόν τον τρόπο, ελπίζουμε ότι θα λειτουργήσει. Ας δώσουμε αυτό πάει άλλο.
Τώρα θα συγκεντρώνει όλα. Όλα είναι καλά.
>> Αλλά σε αυτό το σημείο, δεν έχουμε στην πραγματικότητα ονομάζεται λειτουργία ένθετο μας.
Γνωρίζουμε, όμως, ότι συγκεντρώνει, οπότε ας πάμε και να θέσει σε μερικές κλήσεις μέσα
Ας το κάνουμε αυτό σε κύρια λειτουργία μας.
Εδώ, σχολίασε από 5, 8, και 2,
και τότε δεν τους σύρμα μέχρι εδώ κάτω.
Ας κάνουμε κάποιες κλήσεις για την εισαγωγή,
και ας χρησιμοποιήσουμε επίσης το ίδιο είδος της ουσίας που χρησιμοποιείται
όταν κάναμε αυτές τις κλήσεις printf για να βεβαιωθείτε ότι τα πάντα είχαν πάρει τοποθετηθεί σωστά.
Πάω να αντιγράψετε και να επικολλήσετε,
και αντί περιέχει θα πάμε να κάνουμε ένθετο.
Και αντί για 6, 10, και 1, θα πάμε να χρησιμοποιήσετε 5, 8, και 2.
Αυτό θα πρέπει να εισαχθεί ελπίζουμε 5, 8, και 2 στο δέντρο.
Μεταγλώττιση. Όλα είναι καλά. Τώρα θα τρέξει το πρόγραμμά μας στην πραγματικότητα.
>> Όλα επέστρεψε ψευδείς.
Έτσι, 5, 8, και 2 δεν πήγε, και μοιάζει Περιέχει δεν τα βρείτε είτε.
Τι συμβαίνει; Ας σμίκρυνση.
Το πρώτο πρόβλημα ήταν ότι ένθετο φάνηκε να επιστρέψει false,
και μοιάζει με αυτό είναι επειδή αφήσαμε σε αντάλλαγμα ψευδούς κλήσης μας,
και ποτέ δεν επέστρεψε στην πραγματικότητα αληθινή.
Μπορούμε να το ρυθμίσω αυτό.
Το δεύτερο πρόβλημα είναι, πλέον, ακόμη και αν το κάνουμε - να σώσει αυτό, κλείστε αυτό,
να τρέξει και πάλι, έχουν καταρτίσει, στη συνέχεια, εκτελέστε το -
βλέπουμε ότι κάτι άλλο συμβαίνει εδώ.
Η 5, 8, και 2 ήταν ακόμα ποτέ δεν βρέθηκαν στο δέντρο.
Έτσι, τι συμβαίνει;
>> Ας ρίξουμε μια ματιά σε αυτό τον κωδικό.
Ας δούμε αν μπορούμε να το καταλάβουν αυτό.
Ξεκινάμε με το γονέα που δεν είναι null.
Θέτουμε την τρέχουσα δείκτη ίσο με το δείκτη ρίζα,
και θα πάμε να εργαστείτε με τον τρόπο μας κάτω από το δέντρο.
Εάν ο τρέχων κόμβος δεν είναι μηδενική, τότε ξέρουμε ότι μπορούμε να μετακινηθεί προς τα κάτω λίγο.
Θέτουμε δείκτης μητρικής μας να είναι ίση με την τρέχουσα δείκτη,
ελεγχθεί η αξία - αν οι τιμές είναι οι ίδιες που επέστρεψε ψευδείς.
Εάν οι τιμές είναι λιγότερο κινηθήκαμε προς τα δεξιά?
αλλιώς, κινηθήκαμε προς τα αριστερά.
Στη συνέχεια, χτίζουμε έναν κόμβο. Θα κάνετε ζουμ σε λίγο.
Και εδώ, θα πάμε να προσπαθήσουμε να συνδέσετε έως και τις αξίες να είναι το ίδιο.
Τι συμβαίνει; Ας δούμε αν ενδεχομένως Valgrind μπορεί να μας δώσει μια ιδέα.
>> Μου αρέσει να χρησιμοποιώ μόνο και μόνο επειδή Valgrind Valgrind τρέχει πολύ γρήγορα
και σας λέει αν υπάρχουν σφάλματα μνήμης.
Όταν τρέχουμε Valgrind σχετικά με τον κώδικα,
όπως μπορείτε να δείτε δεξιά χτύπημα here--Valgrind./binary_tree--and εισάγετε.
Βλέπετε ότι δεν είχαμε κανένα σφάλμα μνήμης, έτσι ώστε να φαίνεται σαν όλα είναι εντάξει τώρα.
Έχουμε κάποιες διαρροές μνήμης, που γνωρίζουμε, γιατί δεν είμαστε
συμβαίνει να ελευθερώσει κάποια από κόμβους μας.
Ας προσπαθήσουμε τρέχει GDB για να δείτε τι πραγματικά συμβαίνει.
Θα κάνουμε το gdb. / Binary_tree. Η εκκίνηση του μια χαρά.
Ας ορίσετε ένα σημείο καμπής στο ένθετο.
Ας τρέξει.
Μοιάζει ποτέ στην πραγματικότητα ονομάζεται ένθετο.
Μοιάζει με το πρόβλημα ήταν μόνο ότι όταν άλλαξα εδώ κάτω στην κύρια -
όλες αυτές τις κλήσεις από printf περιέχει -
Ποτέ δεν άλλαξε στην πραγματικότητα αυτά να καλέσετε ένθετο.
Τώρα ας δώσει μια δοκιμή. Ας σύνταξη.
Όλα φαίνεται καλό εκεί. Τώρα ας προσπαθήσουμε να τρέχει, να δούμε τι θα συμβεί.
Εντάξει! Τα πάντα φαίνεται αρκετά καλό εκεί.
>> Το τελευταίο πράγμα που πρέπει να σκεφτούμε είναι, είναι οι περιπτώσεις άκρη σε αυτό το ένθετο εκεί;
Και αποδεικνύεται ότι, καλά, η μία περίπτωση άκρη που είναι πάντα ενδιαφέρον να σκεφτούμε
είναι, τι θα συμβεί αν το δέντρο σας είναι άδειο και σας καλούν αυτή τη λειτουργία ένθετο;
Θα λειτουργήσει; Λοιπόν, ας δώσει μια δοκιμή.
- Binary_tree c. -
Ο τρόπος με τον οποίο πρόκειται να δοκιμάσουν αυτό, θα πάμε για να πάει κάτω με το κύριο έργο μας,
και όχι καλωδίωση αυτούς τους κόμβους σαν αυτό,
είμαστε ακριβώς πρόκειται να σχολιάσει το όλο πράγμα,
και αντί της καλωδίωσης μέχρι τους κόμβους τους εαυτούς μας,
μπορούμε πραγματικά να απλά να προχωρήσει και να διαγράψετε όλα αυτά.
Εμείς πάμε για να κάνει ό, τι μια κλήση για να εισάγετε.
Οπότε, ας το κάνουμε - αντί για 5, 8, και 2, θα πάμε για να εισάγετε 7, 3, και 9.
Και στη συνέχεια, θα ήθελα επίσης να τοποθετήσετε 6, καθώς και.
Αποθήκευση. Quit. Κάντε δυαδικό δέντρο.
Θα συγκεντρώνει όλα.
Μπορούμε απλά να τρέξετε είναι όπως και να δούμε τι θα συμβεί,
αλλά είναι επίσης πρόκειται να είναι πραγματικά σημαντικό να βεβαιωθείτε ότι
δεν έχουμε κανένα σφάλματα μνήμης,
δεδομένου ότι αυτό είναι ένα από περιπτώσεις ακμής μας ότι ξέρουμε περίπου.
>> Ας βεβαιωθείτε ότι λειτουργεί καλά κάτω από Valgrind,
που θα κάνουμε με ακριβώς τρέχει Valgrind. / binary_tree.
Μοιάζει έχουμε πράγματι ένα λάθος από ένα πλαίσιο -
έχουμε αυτό το σφάλμα κατάτμησης.
Τι συνέβη;
Valgrind μας λέει στην πραγματικότητα όπου είναι.
Σμίκρυνση λίγο.
Μοιάζει με αυτό που συμβαίνει σε λειτουργία ένθετο μας,
όπου έχουμε μια μη έγκυρη ανάγνωση του μεγέθους 4 στο ένθετο, γραμμή 60.
Ας πάμε πίσω και να δούμε τι συμβαίνει εδώ.
Σμίκρυνση πραγματικά γρήγορα.
Θέλω να βεβαιωθείτε ότι δεν πάει στην άκρη της οθόνης ώστε να μπορούμε να δούμε τα πάντα.
Τραβήξτε ότι σε λίγο. Εντάξει.
Μετακινηθείτε προς τα κάτω, και το πρόβλημα είναι ακριβώς εδώ.
Τι θα συμβεί αν πιάσουμε και τρέχοντα κόμβο μας είναι ήδη μηδενική,
κόμβος γονέας μας είναι μηδενική, οπότε αν δούμε πάνω στην κορυφή, δεξιά εδώ -
αν ποτέ αυτό το βρόχο, ενώ στην πραγματικότητα εκτελεί
επειδή η τρέχουσα αξία μας είναι null - ρίζα μας είναι μηδενική τρέχουσα έτσι είναι άκυρη -
τότε μητρική μας παίρνει ποτέ οριστεί σε τρέχουσα ή σε μια έγκυρη τιμή,
έτσι, ο γονέας θα είναι επίσης μηδενική.
Πρέπει να θυμόμαστε για να ελέγξετε ότι
από τη στιγμή που έχουμε εδώ κάτω, και να αρχίσουμε την πρόσβαση αξία της μητρικής.
Λοιπόν, τι θα συμβεί; Λοιπόν, αν ο γονέας είναι null -
αν (μητρική NULL ==) - τότε γνωρίζουμε ότι
δεν πρέπει να υπάρχει τίποτα στο δέντρο.
Θα πρέπει να προσπαθούμε να το τοποθετήσετε στη ρίζα.
Μπορούμε να το κάνουμε αυτό από μόνο τον καθορισμό της ρίζας ίσο με το νέο κόμβο.
Στη συνέχεια, σε αυτό το σημείο, δεν θέλουν να περάσουν από αυτά τα άλλα πράγματα.
Αντ 'αυτού, εδώ, μπορούμε να κάνουμε είτε αλλιώς-if-else,
ή θα μπορούσαμε να συνδυάσουμε τα πάντα εδώ σε ένα άλλο,
αλλά εδώ θα χρησιμοποιούν μόνο άλλο και να το κάνουμε με αυτόν τον τρόπο.
Τώρα, θα πάμε να δοκιμάσετε για να βεβαιωθείτε ότι η μητρική μας δεν είναι null
πριν από τότε πραγματικά προσπαθεί να αποκτήσει πρόσβαση στους τομείς της.
Αυτό θα μας βοηθήσει να αποφύγουμε το σφάλμα κατάτμησης.
Έτσι, θα σταματήσουν, σμίκρυνση, την κατάρτιση, να τρέξει.
>> Δεν υπάρχουν λάθη, αλλά έχουμε ακόμα ένα μάτσο διαρροές μνήμης
γιατί δεν απελευθερώσει κάποιο από τους κόμβους μας.
Αλλά, αν πάμε εδώ και κοιτάμε εκτύπωση μας,
βλέπουμε ότι, επίσης, μοιάζει με όλα τα ένθετα μας επέστρεφαν αληθινό, το οποίο είναι καλό.
Τα ενθέματα είναι όλα αλήθεια,
και στη συνέχεια τα κατάλληλα κλήσεων περιέχει είναι επίσης αλήθεια.
>> Καλή δουλειά! Μοιάζει έχουμε γράψει με επιτυχία ένθετο.
Αυτό είναι το μόνο που έχουμε για προδιαγραφές που Πρόβλημα αυτής της εβδομάδας.
Μια διασκεδαστική πρόκληση να σκεφτούμε είναι το πώς θα πάμε πραγματικά σε
και ελεύθερη όλοι οι κόμβοι σε αυτό το δέντρο.
Μπορούμε να κάνουμε έτσι έναν αριθμό από διαφορετικούς τρόπους,
αλλά εγώ θα φύγω ότι μέχρι σας να πειραματιστούν,
και ως πρόκληση διασκέδαση, δοκιμάστε και να βεβαιωθείτε ότι μπορείτε να βεβαιωθείτε ότι
ότι η έκθεση αυτή δεν επιστρέφει Valgrind λάθη και δεν υπάρχουν διαρροές.
>> Καλή τύχη στο σύνολο Huffman πρόβλημα αυτής της εβδομάδας κωδικοποίηση,
και θα τα πούμε την επόμενη εβδομάδα!
[CS50.TV]