[Powered by Google Translate] [Ενότητα 7: Άνετα Περισσότερα]
[Rob Bowden] [Πανεπιστήμιο του Χάρβαρντ]
[Αυτό είναι CS50] [CS50.TV]
Εντάξει. Έτσι, όπως είπα και στο e-mail μου,
αυτό πρόκειται να είναι ένα δυαδικό δέντρο-υψηλής έντασης τμήμα.
Υπάρχουν, όμως, δεν είναι ότι πολλά ερωτήματα.
Έτσι θα πάμε για να προσπαθήσουμε και να σύρει έξω κάθε ερώτηση
και να πάει σε οδυνηρές λεπτομέρειες όλων των καλύτερους τρόπους για να κάνουμε πράγματα.
Έτσι, το δικαίωμα στην αρχή, περνάμε σχέδια δείγμα των δυαδικών δέντρων και πράγματα.
Έτσι, εδώ, "Να θυμάστε ότι ένα δυαδικό δέντρο έχει κόμβους παρόμοιες με εκείνες ενός συνδεδεμένη λίστα,
εκτός αντί για ένα δείκτη υπάρχουν δύο: ένα για «παιδί» της Αριστεράς
και μία για το δεξί «παιδί».
Έτσι, ένα δυαδικό δέντρο είναι ακριβώς όπως μια συνδεδεμένη λίστα,
εκτός από το struct πρόκειται να έχει δύο δείκτες.
Υπάρχει trinary δέντρα, τα οποία θα έχουν τρεις δείκτες,
υπάρχουν Ν-ary δέντρα, τα οποία έχουν μόνο ένα γενικό δείκτη
ότι θα πρέπει στη συνέχεια να malloc να είναι αρκετά μεγάλη ώστε να έχουν
αρκετά δείκτες σε όλες τις πιθανές παιδιά.
Έτσι δυαδικό δέντρο που συμβαίνει μόνο για να έχουν ένα σταθερό αριθμό δύο.
Αν θέλετε, μπορείτε να δώσετε μια συνδεδεμένη λίστα ως μοναδιαίο δέντρο,
αλλά δεν νομίζω ότι κάποιος ονομάζει αυτό.
"Σχεδιάστε ένα κουτιά και βέλη-διάγραμμα του κόμβου ενός δυαδικού δέντρου
που περιέχει το αγαπημένο αριθμό του Nate, 7, όπου το κάθε παιδί δείκτης είναι άκυρη. "
Έτσι iPad λειτουργία.
>> Είναι πρόκειται να είναι αρκετά απλή.
Εμείς απλά θα έχουν έναν κόμβο, θα το συντάξει ως ένα τετράγωνο.
Και εγώ θα συντάξει τις τιμές εδώ.
Έτσι, η τιμή θα πέσει μέσα εδώ,
και στη συνέχεια κάτω εδώ θα έχουμε το αριστερό δείκτη στο αριστερό και το δεξιό δείκτη στα δεξιά.
Και αυτό είναι πάρα πολύ ώστε σύμβαση να το ονομάσουμε αριστερά και δεξιά, τα ονόματα δείκτη.
Και οι δύο θα είναι μηδενική.
Αυτό θα είναι μόνο άκυρη και ότι απλά θα είναι μηδενική.
Εντάξει. Έτσι, πίσω στο εδώ.
"Με μια συνδεδεμένη λίστα, το μόνο που έπρεπε να αποθηκεύουν ένα δείκτη
στον πρώτο κόμβο της λίστας, ώστε να θυμούνται ολόκληρο το συνδεδεμένη λίστα, ή ολόκληρη τη λίστα.
Ομοίως, με τα δέντρα, δεν έχουμε παρά να αποθηκεύσετε ένα δείκτη
σε ένα μόνο κόμβο, προκειμένου να θυμούνται ολόκληρο το δέντρο.
Αυτός ο κόμβος είναι calle η «ρίζα» του δέντρου.
Κατασκευάστηκε κατά διάγραμμα σας από πριν ή να σχεδιάσετε ένα νέο
έτσι ώστε να έχετε μια κιβώτια-και-βέλη απεικόνιση ενός δυαδικού δέντρου
με το η τιμή 7, μετά 3 στο αριστερό,
τότε 9 σχετικά με το δικαίωμα, και στη συνέχεια 6 σχετικά με το δικαίωμα του 3. "
Ας δούμε αν μπορώ να θυμηθώ όλα αυτά στο κεφάλι μου.
Έτσι, αυτό πρόκειται να είναι ρίζα μας εδώ.
Θα έχουμε κάποια δείκτη, κάπου κάτι που θα καλέσουμε ρίζα,
και αυτό είναι που δείχνουν προς αυτόν τον τύπο.
Τώρα για να κάνει ένα νέο κόμβο,
τι έχουμε, 3 στο αριστερό;
Έτσι, ένας νέος κόμβος με 3, και επισημαίνει αρχικά άκυρη.
Θα βάλω ακριβώς Ν.
Τώρα θέλουμε να κάνουμε ότι πάμε προς τα αριστερά του 7.
Έτσι θα αλλάξουμε αυτό το δείκτη να επισημάνω τώρα με αυτόν τον τύπο.
Και εμείς κάνουμε το ίδιο. Θέλουμε ένα 9 εδώ
το οποίο αρχικά μόνο λέει null.
Εμείς πάμε για να αλλάξει αυτό το δείκτη, το σημείο έως 9,
και τώρα θέλετε να βάλετε 6 στο δικαίωμα της 3.
Έτσι πρόκειται να - κάνει 6.
Και αυτός ο τύπος θα δείξει εκεί.
Εντάξει. Έτσι, αυτό είναι το μόνο που μας ζητάει να κάνουμε.
>> Τώρα ας πάμε πάνω από κάποια ορολογία.
Έχουμε ήδη μιλήσει για το πώς η ρίζα του δέντρου είναι η κορυφαία-πιο κόμβος στο δέντρο.
Το ένα περιέχει 7. Οι κόμβοι στο κάτω μέρος του δέντρου που ονομάζεται τα φύλλα.
Κάθε κόμβος που μόλις έχει μηδενική, όπως τα παιδιά του είναι ένα φύλλο.
Έτσι είναι δυνατόν, αν δυαδικού δένδρου μας είναι ένα μόνο κόμβο,
ότι ένα δέντρο είναι ένα φύλλο, και αυτό είναι αυτό.
"Το« ύψος »του δέντρου είναι ο αριθμός του λυκίσκου που έχετε να κάνετε
για να πάρει από την κορυφή σε ένα φύλλο. "
Θα μπει σε μια δεύτερη, η διαφορά
μεταξύ ισορροπημένη και μη ισορροπημένη δυαδικά δένδρα,
αλλά για τώρα, το συνολικό ύψος του δέντρου
Θα έλεγα ότι είναι 3, ενώ αν συμπεριλάβουμε και τον αριθμό του λυκίσκου
που έχετε να κάνετε για να φτάσετε στο 9, τότε είναι πραγματικά μόνο ένα ύψος 2.
Αυτή τη στιγμή αυτό είναι μια μη ισορροπημένη δυαδικό δέντρο,
αλλά θα μιλήσει για ισορροπημένη όταν παίρνει να είναι σχετικό.
Έτσι, τώρα μπορούμε να μιλήσουμε για τους κόμβους σε ένα δέντρο σε όρους
σε σχέση με τους άλλους κόμβους στο δέντρο.
Έτσι τώρα έχουμε γονείς, παιδιά, αδέλφια, τους προγόνους και τους απογόνους.
Είναι αρκετά κοινή λογική, τι σημαίνουν.
Αν ρωτήσουμε - οι γονείς του.
Έτσι ποια είναι η μητρική του 3;
[Φοιτητές] 7. Ναι >>. Ο γονέας είναι ακριβώς πρόκειται να είναι αυτό που δείχνει σας.
Τότε ποια είναι τα παιδιά από 7;
[Φοιτητές] 3 και 9. Ναι >>.
Σημειώστε ότι "τα παιδιά" σημαίνει κυριολεκτικά τα παιδιά,
έτσι 6 δεν θα εφαρμοστεί, διότι είναι σαν ένα εγγόνι.
Στη συνέχεια, όμως, αν πάμε απογόνους, ναι, ποιες είναι οι απόγονοι των 7;
[Φοιτητές] 3, 6 και 9. Ναι >>.
Οι απόγονοι του ριζικού κόμβου θα είναι πάντα στο δέντρο,
εκτός ίσως από την ίδια ρίζα, αν δεν θέλετε να θεωρούν ότι ένας απόγονος.
Και, τέλος, τους προγόνους, γι 'αυτό είναι η αντίθετη κατεύθυνση.
Έτσι, ποιες είναι οι πρόγονοι των 6;
[Φοιτητές] 3 και 7. Ναι >>. 9 δεν περιλαμβάνεται.
Είναι ακριβώς η άμεση καταγωγή πίσω στη ρίζα
πρόκειται να είναι οι πρόγονοί σας.
>> "Λέμε ότι ένα δυαδικό δέντρο είναι« διέταξε »αν για κάθε κόμβο στο δέντρο,
όλους τους απογόνους του στο αριστερό έχουν μικρότερες τιμές
και όλα αυτά σχετικά με το δικαίωμα να έχει μεγαλύτερες τιμές.
Για παράδειγμα, το δέντρο είναι πάνω από παραγγελθεί αλλά δεν είναι η μόνη δυνατή διευθέτηση διέταξε. "
Πριν φτάσουμε σε αυτό,
ένα διατεταγμένο δυαδικού δένδρου είναι επίσης γνωστή ως ένα δυαδικό δέντρο αναζήτησης.
Εδώ τυχαίνει να αποκαλεί ένα δυαδικό δέντρο διέταξε,
αλλά δεν έχω ακούσει να λέγεται ένα δυαδικό δέντρο διέταξε πριν,
και σε ένα κουίζ που είναι πολύ πιο πιθανό να θέσει δυαδικό δέντρο αναζήτησης.
Είναι ένα και το αυτό,
και είναι σημαντικό να αναγνωρίσουμε τη διάκριση μεταξύ δυαδικό δέντρο και δυαδικό δέντρο αναζήτησης.
Ένα δυαδικό δένδρο είναι απλά ένα δέντρο που δείχνει δύο πράγματα.
Κάθε κόμβος δείχνει δύο πράγματα.
Δεν υπάρχει καμία λογική για τις αξίες που δείχνει.
Έτσι, όπως εδώ, δεδομένου ότι είναι ένα δυαδικό δέντρο αναζήτησης,
γνωρίζουμε ότι αν πάμε αριστερά από 7,
τότε όλες οι τιμές που μπορεί ενδεχομένως να φθάσουν
πηγαίνοντας από αριστερά 7 πρέπει να είναι μικρότερη από 7.
Παρατηρήστε ότι όλες οι τιμές λιγότερο από 7 είναι 3 και 6.
Αυτές είναι όλες προς τα αριστερά της 7.
Αν πάμε προς τα δεξιά του 7, τα πάντα πρέπει να είναι μεγαλύτερη από 7,
9 είναι έτσι το δικαίωμα των 7, έτσι είμαστε καλοί.
Αυτή δεν είναι η περίπτωση για ένα δυαδικό δέντρο,
για ένα κανονικό δυαδικού δένδρου που μπορούμε να έχουμε μόνο 3 στην κορυφή, 7 προς τα αριστερά,
9 προς τα αριστερά του 7? Δεν υπάρχει διάταξη των τιμών απολύτως.
Τώρα, εμείς δεν θα κάνουμε πραγματικότητα αυτό γιατί είναι κουραστική και περιττή,
αλλά «θέλουμε να βγάλουμε όσες διέταξε δέντρα, όπως μπορείτε να σκεφτείτε
χρησιμοποιώντας τους αριθμούς 7, 3, 9, και 6.
Πόσες διαφορετικές ρυθμίσεις υπάρχουν; Ποιο είναι το ύψος του κάθε ένα; "
>> Θα κάνουμε ένα ζευγάρι, αλλά η βασική ιδέα είναι,
αυτό είναι με κανένα τρόπο μία μοναδική αναπαράσταση ενός δυαδικού δένδρου που περιέχει αυτές τις τιμές.
Το μόνο που χρειαζόμαστε είναι μερικά δυαδικό δέντρο που περιέχει 7, 3, 6, και 9.
Μια άλλη πιθανή έγκυρη θα είναι η ρίζα είναι 3,
πάει προς τα αριστερά και είναι 6, πηγαίνετε προς τα αριστερά και είναι 7,
πηγαίνουν προς τα αριστερά και είναι 9.
Αυτό είναι ένα απολύτως έγκυρο δέντρο δυαδική αναζήτηση.
Δεν είναι πολύ χρήσιμο, επειδή είναι ακριβώς όπως μια συνδεδεμένη λίστα
και όλες αυτές οι δείκτες είναι ακριβώς μηδενική.
Αλλά είναι μια έγκυρη δέντρο. Ναι;
[Φοιτητικό] Μην οι τιμές πρέπει να είναι μεγαλύτερη στα δεξιά;
Ή είναι αυτό -; >> Αυτά εννοούσα να πάει ο άλλος τρόπος.
Υπάρχει, επίσης, - ναι, ας αλλάξουν αυτό.
9, 7, 6, 3. Καλή αλιευμάτων.
Θα πρέπει ακόμη να υπακούσει τι ένα δυαδικό δέντρο αναζήτησης πρόκειται να κάνει.
Έτσι τα πάντα προς τα αριστερά πρέπει να είναι μικρότερη από ένα οποιοδήποτε δεδομένο κόμβο.
Θα μπορούσαν απλώς να μετακομίσουν, ας πούμε, αυτό το 6 και το βάζουμε εδώ.
Όχι, δεν μπορούμε. Γιατί μπορώ να συνεχίσω να το κάνω αυτό;
Ας κάνουμε - εδώ είναι 6, εδώ είναι 7, 6 πόντους και 3.
Αυτή εξακολουθεί να είναι ένα έγκυρο δέντρο δυαδική αναζήτηση.
Ποιο είναι το πρόβλημα αν εγώ - ας δούμε αν μπορώ να καταλήξουμε σε μια συμφωνία.
Ναι, εντάξει. Έτσι τι είναι λάθος με αυτό το δέντρο;
Υποθέτω ότι έχω ήδη δώσει έναν υπαινιγμό ότι υπάρχει κάτι λάθος με αυτό.
Γιατί μπορώ να συνεχίσω να το κάνω αυτό;
Εντάξει. Αυτό φαίνεται λογικό.
Αν κοιτάξουμε σε κάθε κόμβο, όπως το 7, τότε στα αριστερά του 7 είναι ένα 3.
Έτσι έχουμε 3, το πράγμα στα δεξιά του 3 είναι 6.
Και αν κοιτάξετε 6, το πράγμα προς τα δεξιά του 6 είναι ένα 9.
Γιατί, λοιπόν, είναι αυτή δεν είναι έγκυρη δέντρο δυαδικής αναζήτησης;
[Φοιτητές] 9 εξακολουθεί να είναι προς τα αριστερά της 7. Ναι >>.
Πρέπει να είναι αλήθεια ότι όλες οι τιμές που μπορείτε ενδεχομένως να φτάσει, πηγαίνοντας προς τα αριστερά του 7 είναι μικρότερο του 7.
Αν πάμε αριστερά 7, έχουμε την ευκαιρία να 3 και μπορούμε ακόμα να πάρετε έως 6,
μπορούμε ακόμα να πάρετε έως 9, αλλά έχοντας περάσει λιγότερο από 7,
δεν θα πρέπει να είναι σε θέση να πάρει σε έναν αριθμό που είναι μεγαλύτερο από 7.
Έτσι, αυτό δεν είναι ένα έγκυρο δέντρο δυαδική αναζήτηση.
>> Ο αδελφός μου είχε πραγματικά μια ερώτηση συνέντευξης
αυτό ήταν βασικά αυτό, απλά κωδικός κάτι για την επικύρωση
αν ένα δένδρο είναι ένα δυαδικό δέντρο αναζήτησης,
και έτσι το πρώτο πράγμα που έκανε ήταν απλά να ελέγξετε
αν η αριστερά και δεξιά είναι σωστές και, στη συνέχεια επαναλάβει εκεί κάτω.
Αλλά δεν μπορείτε να το κάνετε απλά ότι? Θα πρέπει να παρακολουθείτε
από το γεγονός ότι τώρα που έχω φύγει από αριστερά 7,
τα πάντα σε αυτό το υποδένδρο πρέπει να είναι μικρότερο του 7.
Η σωστή αλγόριθμος πρέπει να παρακολουθείτε
από τα όρια που οι τιμές μπορούν ενδεχομένως να πέσει μέσα
Δεν θα περάσουν από όλα αυτά.
Υπάρχει μια ωραία σχέση επανάληψης,
αν και δεν έχουμε φτάσει σε αυτούς, ή δεν θα πάρετε σε αυτές,
τον καθορισμό πόσα πραγματικά υπάρχουν.
Έτσι, υπάρχουν 14 από αυτά.
Η ιδέα για το πώς θα το κάνουμε είναι σαν μαθηματικά,
μπορείτε να επιλέξετε οποιαδήποτε έστω και έναν να είναι ο κόμβος ρίζα,
και στη συνέχεια, αν έχω πάρει 7 να είναι ο κόμβος ρίζα,
τότε υπάρχουν, λένε, ορισμένοι αριθμοί που μπορεί να πάει να είναι το αριστερό κόμβο μου,
και υπάρχουν κάποιοι αριθμοί που μπορεί να είναι σωστό κόμβο μου,
αλλά αν έχω n ο συνολικός αριθμός, τότε το ποσό που μπορεί να πάει προς τα αριστερά
συν το ποσό που μπορεί να πάει προς τα δεξιά είναι n - 1.
Έτσι από τους υπόλοιπους αριθμούς, θα πρέπει να είναι σε θέση να πάει είτε προς τα αριστερά ή τα δεξιά.
Φαίνεται ότι είναι δύσκολο, αν έβαλα 3 πρώτο, τότε τα πάντα πρέπει να πάει προς τα αριστερά,
αλλά αν έβαλα 7, τότε κάποια πράγματα που μπορεί να πάει το αριστερό και κάποια πράγματα που μπορούν να πάνε προς τα δεξιά.
Και από '3 πρώτη «Εννοούσα τα πάντα μπορεί να πάει προς τα δεξιά.
Είναι πραγματικά, απλά πρέπει να το σκεφτώ, όπως,
πόσα πράγματα μπορούν να πάνε στο επόμενο επίπεδο του δέντρου.
Και αυτό βγαίνει να είναι 14? Ή μπορείτε να σχεδιάσετε όλα αυτά,
και στη συνέχεια θα πάρει 14.
>> Πηγαίνοντας πίσω εδώ,
"Καταδικάζει δυαδικά δέντρα είναι δροσερά, επειδή μπορούμε να ψάξουμε μέσα από αυτά
με πολύ παρόμοιο τρόπο με την αναζήτηση σε ταξινομημένο πίνακα.
Για να γίνει αυτό, ξεκινάμε από τη ρίζα και το έργο μας κάτω από το δέντρο
προς τα φύλλα, τον έλεγχο των τιμών του κάθε κόμβου σχέση με τις τιμές που αναζητάτε.
Εάν η τιμή του τρέχοντος κόμβου είναι μικρότερη από την τιμή που ψάχνουμε,
πηγαίνετε δίπλα στο δεξί παιδί του κόμβου.
Διαφορετικά, πηγαίνετε στο αριστερό παιδί του κόμβου.
Σε κάποιο σημείο, θα βρείτε είτε την αξία που ψάχνετε, ή θα τρέξει σε ένα null,
που υποδηλώνει την τιμή δεν είναι στο δέντρο. "
Έχω να ξανασχεδιάσουμε το δέντρο που είχαμε πριν? Που θα λάβει μια δεύτερη.
Αλλά θέλουμε να δούμε αν μέχρι 6, 10, και 1 είναι το δέντρο.
Έτσι, ό, τι ήταν, 7, 9, 3, 6. Εντάξει.
Οι αριθμοί που θέλετε να αναζητήσετε, θέλουμε να δούμε μέχρι 6.
Πώς λειτουργεί αυτός ο αλγόριθμος;
Λοιπόν, έχουμε και κάποια ρίζα δείκτη στο δέντρο μας.
Και εμείς θα πάμε στη ρίζα και να πω, είναι αυτή η τιμή ίση με την τιμή που αναζητάτε;
Έτσι ψάχνουμε για 6, έτσι δεν είναι ίσοι.
Γι 'αυτό και συνεχίζω, και τώρα λέμε, εντάξει, έτσι 6 είναι μικρότερο του 7.
Μήπως αυτό σημαίνει ότι θέλουμε να πάμε προς τα αριστερά, ή θέλουμε να πάμε προς τα δεξιά;
[Φοιτητικό] Αριστερά. Ναι >>.
Είναι πολύ εύκολο, το μόνο που έχετε να κάνετε είναι να συντάξει ένα δυνατό κόμβο του δέντρου
και στη συνέχεια να μην τα - αντί να προσπαθούν να σκέφτονται στο κεφάλι σας,
εντάξει, αν είναι λιγότερο, μπορώ να πάω προς τα αριστερά ή πηγαίνετε το δικαίωμα,
απλά κοιτάζοντας αυτή την εικόνα, είναι πολύ σαφές ότι πρέπει να πάω προς τα αριστερά
αν αυτός ο κόμβος είναι μεγαλύτερη από την αξία που ψάχνω.
Έτσι, πηγαίνετε προς τα αριστερά, τώρα είμαι στο 3.
Θέλω να - 3 είναι μικρότερη από την τιμή που ψάχνω, το οποίο είναι 6.
Γι 'αυτό και πάμε προς τα δεξιά, και τώρα έχω καταλήξει σε 6,
που είναι η αξία που ψάχνω, γι 'αυτό επιστρέφει αλήθεια.
Το επόμενο αξία Πάω να αναζητήσουμε είναι 10.
Εντάξει. Έτσι, 10, τώρα, πρόκειται να - κόψει ότι - πρόκειται να ακολουθήσει τη ρίζα.
Τώρα, 10 πρόκειται να είναι μεγαλύτερο από 7, γι 'αυτό θέλω να κοιτάζω προς τα δεξιά.
Πάω να έρθω εδώ, 10 πρόκειται να είναι μεγαλύτερη από 9,
έτσι είμαι πρόκειται να θέλουν να κοιτάξουμε προς τα δεξιά.
Έρχομαι εδώ, αλλά εδώ τώρα είμαι σε null.
Τι μπορώ να κάνω αν χτυπήσει null;
[Φοιτητικό] Επιστροφή λάθος; Ναι >>. Δεν βρήκα 10.
1 πρόκειται να είναι μια σχεδόν ταυτόσημη περίπτωση,
εκτός του ότι είναι ακριβώς πρόκειται να γυρίσει? αντί να κοιτάμε
κάτω από τη δεξιά πλευρά, Πάω να κοιτάξει κάτω την αριστερή πλευρά.
>> Τώρα νομίζω ότι πραγματικά να πάρει τον κώδικα.
Εδώ είναι όπου - το άνοιγμα της συσκευής CS50 και να περιηγηθείτε το δρόμο σας εκεί,
αλλά μπορείτε να κάνετε ακριβώς αυτό και στο χώρο.
Είναι πιθανώς ιδανικό για να το κάνει στο χώρο,
επειδή μπορούμε να εργαστούμε στο χώρο.
"Πρώτα θα χρειαστείτε ένα νέο ορισμό τύπου για ένα δυαδικό δέντρο κόμβο που περιέχει τιμές τύπου int.
Χρησιμοποιώντας το στερεότυπο typedef παρακάτω,
δημιουργία ενός νέου τύπου για ορισμό ενός κόμβου σε ένα δυαδικό δένδρο.
Αν έχετε κολλήσει. . . «Μπλα, μπλα, μπλα. Εντάξει.
Ας βάλουμε το στερεότυπο εδώ,
typedef struct node, και ο κόμβος. Ναι, εντάξει.
Έτσι, ποια είναι τα πεδία θα πάμε να θέλουν στον κόμβο μας;
[Φοιτητικό] Int και στη συνέχεια δίποντα;
>> Αξία Int, δίποντα; Πώς μπορώ να γράψω τους δείκτες;
[Φοιτητικό] Struct. >> Θα πρέπει να μεγεθύνετε Ναι, έτσι struct node * αριστερά,
και struct node * δικαίωμα.
Και να θυμάστε τη συζήτηση από την τελευταία φορά,
ότι αυτό δεν έχει κανένα νόημα, αυτό δεν έχει κανένα νόημα,
αυτό δεν έχει κανένα νόημα.
Χρειάζεται πάντα εκεί για να καθορίσουν αυτό το αναδρομικό struct.
Εντάξει, έτσι αυτό είναι που μας δέντρο πρόκειται να μοιάσει.
Αν κάναμε ένα trinary δέντρο, στη συνέχεια, ένας κόμβος μπορεί να μοιάζει b1, b2, struct node * b3,
όπου β είναι ένας κλάδος - στην πραγματικότητα, έχω ακούσει πιο αριστερά, κέντρο, δεξιά, αλλά και οτιδήποτε άλλο.
Το μόνο που νοιάζονται για δυαδικό, τόσο δεξιά, αριστερά.
"Δηλώνουν τώρα μια καθολική μεταβλητή * κόμβος για τη ρίζα του δέντρου."
Γι 'αυτό και δεν πρόκειται να το κάνουμε αυτό.
Για να κάνει τα πράγματα λίγο πιο δύσκολο και πιο γενικευμένη,
δεν θα έχουμε μια παγκόσμια μεταβλητό κόμβο.
Αντ 'αυτού, σε κύριο εμείς θα κηρύξει όλα τα πράγματα κόμβο μας,
και αυτό σημαίνει ότι στη συνέχεια, όταν θα αρχίσουν να προβάλλονται
Περιέχει τη λειτουργία μας και τη λειτουργία μας ένθετο,
αντί Περιέχει μας λειτουργούν μόνο με τη χρήση αυτής της παγκόσμιας μεταβλητό κόμβο,
θα πάμε να το πάρετε ως επιχείρημα το δέντρο που θέλουμε να επεξεργαστούμε.
Έχοντας την καθολική μεταβλητή υποτίθεται ότι θα κάνει τα πράγματα ευκολότερα.
Εμείς πάμε για να κάνει τα πράγματα σκληρότερα.
Τώρα πάρτε ένα λεπτό ή έτσι απλά για να κάνουμε αυτό το είδος του πράγματος,
όπου μέσα από τα κύρια θέλετε να δημιουργήσετε αυτό το δέντρο, και αυτό είναι το μόνο που θέλετε να κάνετε.
Δοκιμάστε και να κατασκευάσει αυτό το δέντρο σε κύρια λειτουργία σας.
>> Εντάξει. Έτσι, δεν χρειάζεται καν να έχουν κατασκευαστεί το δέντρο ολόκληρο το δρόμο ακόμα.
Αλλά ο καθένας έχει κάτι που θα μπορούσε να σηκώσει
να δείξει πώς θα μπορούσε κανείς να ξεκινήσει την κατασκευή ενός τέτοιου δέντρο;
[Φοιτητικό] χτυπάς κάποιον, προσπαθώντας να βγει.
[Bowden] Όποιος άνετα με την κατασκευή δέντρο τους;
[Φοιτητικό] Σίγουρα. Δεν το κάνει. >> Είναι μια χαρά. Εμείς μπορούμε απλά να τελειώσει -
Ω, μπορείτε να το αποθηκεύσετε; Ζήτω.
Έτσι, εδώ έχουμε - Ω, είμαι κάπως αποκομμένοι.
Είμαι σε μεγέθυνση;
Μεγέθυνση, μετακινηθείτε προς τα έξω. >> Έχω μια ερώτηση. Ναι >>;
[Φοιτητικό] Όταν ορίζετε struct, είναι τα πράγματα όπως αρχικοποιείται σε τίποτα;
[Bowden] Όχι >> Εντάξει. Έτσι, θα πρέπει να προετοιμαστεί -
[Bowden] Όχι Όταν ορίζετε, ή όταν δηλώνετε μια struct,
δεν ξεκινά από προεπιλογή? είναι ακριβώς όπως αν κηρύξει int.
Είναι ακριβώς το ίδιο πράγμα. Είναι σαν κάθε επιμέρους τομείς της
μπορεί να έχει μια τιμή σκουπίδια σε αυτό. >> Και είναι δυνατόν να καθορίσει - ή να δηλώσει ένα struct
κατά τρόπο ώστε να τους κάνει αρχικοποίηση;
[Bowden] Ναι. Έτσι, σύνταξη προετοιμασίας συντόμευση
πρόκειται να μοιάσει -
Υπάρχουν δύο τρόποι που μπορούμε να το κάνουμε αυτό. Νομίζω ότι πρέπει να το υπολογίσουν
για να βεβαιωθείτε ότι Clang κάνει αυτό επίσης.
Η σειρά των επιχειρημάτων που έρχεται στο struct,
βάζετε ως τη σειρά των επιχειρημάτων μέσα από αυτές τις αγκύλες.
Έτσι, εάν θέλετε να το αρχικοποιήσει έως 9 και άφησε να άκυρη και στη συνέχεια δικαίωμα να είναι μηδενική,
θα ήταν 9, null, null.
Η εναλλακτική λύση είναι, και ο εκδότης δεν ήθελε αυτήν τη σύνταξη,
και πιστεύει θέλω ένα νέο μπλοκ,
αλλά η εναλλακτική λύση είναι κάτι σαν -
εδώ, εγώ θα το θέσω σε μια νέα γραμμή.
Μπορείτε να πείτε ρητά, ξεχνάω την ακριβή σύνταξη.
Έτσι, μπορείτε να απευθυνθείτε ρητά από το όνομα, και λένε,
. Αξία γ, ή. = 9,. Αριστερά = NULL.
Υποθέτω αυτά πρέπει να είναι κόμματα.
. Δεξιά = NULL, ώστε με αυτό τον τρόπο δεν έχετε
πραγματικά χρειάζεται να γνωρίζουν τη σειρά του struct,
και όταν διαβάζετε αυτό, είναι πολύ πιο σαφής
σχετικά με το τι είναι η τιμή που ξεκινά με.
>> Αυτό συμβαίνει να είναι ένα από τα πράγματα που -
έτσι, για το μεγαλύτερο μέρος, C + + είναι υπερσύνολο της C.
Μπορείτε να πάρετε C κώδικα, να το μετακινήσετε πάνω σε C + +, και θα πρέπει να συγκεντρώνουν.
Αυτό είναι ένα από τα πράγματα ότι η C + + δεν υποστηρίζει, ώστε οι άνθρωποι τείνουν να μην το κάνει.
Δεν ξέρω αν αυτός είναι ο μόνος λόγος που οι άνθρωποι έχουν την τάση να μην το κάνει,
αλλά η περίπτωση κατά την οποία έπρεπε να το χρησιμοποιήσετε για να συνεργαστεί με C + + και γι 'αυτό δεν θα μπορούσε να χρησιμοποιήσει αυτό.
Ένα άλλο παράδειγμα από κάτι που δεν λειτουργεί με C + + είναι
πώς malloc επιστρέφει ένα "* κενό,« τεχνικά,
αλλά θα μπορούσαμε να πούμε ακριβώς char * x = οτιδήποτε άλλο malloc,
και αυτόματα θα ρίχνει σε ένα char *.
Ότι η αυτόματη καστ δεν θα συμβεί σε C + +.
Αυτό δεν θα καταρτίσει, και που θα πρέπει ρητά να πω
char *, malloc, όποια και αν είναι, να το ρίχνει σε ένα char *.
Δεν υπάρχουν πολλά πράγματα που C και C + + διαφωνούν,
αλλά αυτά είναι δύο.
Έτσι θα πάμε με αυτή τη σύνταξη.
Αλλά ακόμα και αν δεν είχαμε πάει με το εν λόγω σύνταξη,
τι είναι - θα μπορούσε να είναι λάθος με αυτό;
[Φοιτητικό] δεν χρειάζεται να dereference αυτό; Ναι >>.
Να θυμάστε ότι το βέλος έχει μια σιωπηρή dereference,
και έτσι όταν είμαστε ακριβώς κάνουμε με ένα struct,
θέλουμε να χρησιμοποιήσουμε. για να πάρει μέσα σε ένα πεδίο του struct.
Και η μόνη φορά που θα χρησιμοποιήσετε το βέλος είναι όταν θέλουμε να κάνουμε -
καλά, βέλος είναι ισοδύναμο με -
αυτό είναι ό, τι θα σήμαινε αν χρησιμοποιηθεί βέλος.
Όλα τα μέσα βέλος, dereference αυτό, τώρα είμαι σε μια struct, και μπορώ να πάρω το πεδίο.
Είτε να πάρει το πεδίο άμεσα ή dereference και να πάρει το πεδίο -
Υποθέτω ότι αυτό θα πρέπει να είναι αξία.
Αλλά εδώ είμαι ασχολούνται μόνο με ένα struct δεν είναι, ένα δείκτη σε struct,
και γι 'αυτό δεν μπορεί να χρησιμοποιήσει το βέλος.
Αλλά αυτό το είδος των πράγμα που μπορούμε να κάνουμε για όλους τους κόμβους.
Θεέ μου.
Αυτό είναι 6, 7, και 3.
Στη συνέχεια, μπορούμε να δημιουργήσει τα κλαδιά στο δέντρο μας, μπορούμε να έχουμε 7 -
μπορούμε να έχουμε, αριστερά της πρέπει να παραπέμπει σε 3.
Λοιπόν, πώς θα το κάνουμε αυτό;
[Φοιτητές, ακατάληπτο] >> Ναι. Η διεύθυνση του node3,
και αν δεν έχουν διεύθυνση, τότε απλά δεν θα μεταγλωττίσετε.
Αλλά να θυμάστε ότι αυτά είναι δείκτες για τους επόμενους κόμβους.
Το δικαίωμα αυτό θα πρέπει να το σημείο 9,
και 3 θα πρέπει να επισημάνω σχετικά με το δικαίωμα 6.
Νομίζω ότι αυτό είναι όλα έτοιμα. Οποιαδήποτε σχόλια ή ερωτήσεις;
[Φοιτητών, ακατάληπτο] Η ρίζα θα είναι 7.
Μπορούμε να πούμε μόνο κόμβο * ptr =
ή ρίζα, = & node7.
>> Για τους σκοπούς μας, θα πάμε να ασχολούνται με την εισαγωγή,
έτσι θα πάμε να θέλουν να γράψουν μια λειτουργία για την εισαγωγή σε αυτό το δυαδικό δέντρο
και ένθετο αναπόφευκτα θα καλέσει malloc για να δημιουργήσετε ένα νέο κόμβο για αυτό το δέντρο.
Έτσι, τα πράγματα πρόκειται να πάρει βρώμικο με το γεγονός ότι κάποιοι κόμβοι
είναι σήμερα στην στοίβα
και άλλους κόμβους πρόκειται να καταλήξουν στο σωρό όταν τα εισάγετε.
Αυτό είναι απόλυτα έγκυρη, αλλά ο μόνος λόγος
είμαστε σε θέση να το κάνουμε αυτό στη στοίβα
είναι επειδή είναι ένα τέτοιο παράδειγμα σκηνοθετημένη που γνωρίζουμε
το δέντρο υποτίθεται να κατασκευαστεί, όπως 7, 3, 6, 9.
Αν δεν είχαμε αυτό, τότε δεν θα πρέπει να malloc στην πρώτη θέση.
Όπως θα δούμε λίγο αργότερα, θα πρέπει να malloc'ing.
Αυτή τη στιγμή είναι απολύτως λογικό να θέσει στη στοίβα,
αλλά ας αλλάξουμε αυτό σε εφαρμογή malloc.
Έτσι, κάθε μια από αυτές είναι τώρα πρόκειται να είναι κάτι σαν
κόμβο * node9 = malloc (sizeof (κόμβος)).
Και τώρα θα πάμε να πρέπει να κάνουμε έλεγχο μας.
αν (node9 == NULL) - εγώ δεν θέλω αυτό -
επιστρέψει 1, και στη συνέχεια μπορούμε να κάνουμε node9-> γιατί τώρα είναι ένας δείκτης,
value = 6, node9-> left = NULL,
node9-> δεξιά = NULL,
και θα πάμε να πρέπει να το κάνουμε αυτό για κάθε μία από αυτές τις κόμβους.
Έτσι, αντί, ας το βάλει μέσα σε μια ξεχωριστή λειτουργία.
Ας το ονομάσουμε κόμβο * build_node,
και αυτό είναι κάπως παρόμοια με την APIs παρέχουμε για κωδικοποίηση Huffman.
Σας δίνουμε λειτουργίες initializer για ένα δέντρο
και Deconstructor "λειτουργίες" για τα δέντρα και το ίδιο για τα δάση.
>> Έτσι, εδώ θα πάμε να έχουν μια λειτουργία initializer
να χτίσουμε έναν κόμβο για μας.
Και πρόκειται να δούμε λίγο πολύ ακριβώς όπως αυτό.
Και είμαι ακόμα πρόκειται να είναι τεμπέλης και να μην αλλάξει το όνομα της μεταβλητής,
ακόμα κι αν node9 δεν έχει νόημα πια.
Ω, υποθέτω node9 αξία του δεν θα πρέπει να έχουν 6.
Τώρα μπορούμε να επιστρέψουμε node9.
Και εδώ θα πρέπει να επιστρέψει null.
Όλοι συμφωνούν σε αυτό το build-a-κόμβος λειτουργία;
Έτσι, τώρα μπορούμε να αποκαλούμε απλά ότι για να χτίσει κάθε κόμβο με μια δεδομένη αξία και null δείκτες.
Τώρα μπορούμε να ονομάσουμε αυτό, μπορούμε να κάνουμε κόμβο * node9 = build_node (9).
Και ας το κάνουμε. . .
6, 3, 7, 6, 3, 7.
Και τώρα θέλουμε να δημιουργήσουν τα ίδια δείκτες,
εκτός από ό, τι τώρα είναι ήδη σε όρους δεικτών
έτσι δεν χρειάζεται πλέον τη διεύθυνση του.
Εντάξει. Έτσι, ποιο είναι το τελευταίο πράγμα που θέλω να κάνω;
Υπάρχει ένα σφάλμα ελέγχου ότι δεν κάνω.
Τι σημαίνει επιστροφή κατασκευή κόμβου;
[Φοιτητών, ακατάληπτο] >> Ναι. Αν malloc αποτύχει, αυτό θα επιστρέψει null.
Έτσι, Πάω να το θέσω νωχελικά κάτω εδώ, αντί να κάνει μια συνθήκη για το καθένα.
Αν (node9 == NULL, ή - ακόμα πιο απλή,
αυτό είναι ισοδύναμο με ακριβώς αν όχι node9.
Έτσι, αν δεν node9, ή δεν node6, ή δεν node3, ή δεν node7, επιστρέφει 1.
Ίσως θα πρέπει να εκτυπώσετε malloc αποτύχει, ή κάτι τέτοιο.
[Φοιτητικό] Είναι ψευδής ίσο με null, καθώς;
[Bowden] Κάθε μηδενική τιμή είναι ψευδής.
Έτσι, null είναι μια μηδενική τιμή.
Μηδέν είναι μια μηδενική τιμή. Λάθος είναι μηδενική αξία.
Οποιαδήποτε - λίγο πολύ τα 2 μόνο μηδενικές τιμές είναι μηδενική και το μηδέν,
ψευδή είναι απλά hash ορίζεται ως μηδέν.
Αυτό ισχύει επίσης εάν δεν δηλώνουν global μεταβλητή.
Αν είχαμε τον κόμβο ρίζα * μέχρι εδώ,
τότε - το ωραίο πράγμα για την παγκόσμια μεταβλητών είναι ότι έχουν πάντα μια αρχική τιμή.
Αυτό δεν είναι αλήθεια λειτουργιών, πώς μέσα από εδώ,
αν έχουμε, όπως, ο κόμβος * x ή κόμβο.
Δεν έχουμε ιδέα τι x.value, x.whatever,
ή θα μπορούσαμε να τις εκτυπώσετε και θα μπορούσαν να είναι αυθαίρετη.
Αυτό δεν είναι αλήθεια της παγκόσμιας μεταβλητών.
Έτσι, ο κόμβος ρίζα ή κόμβο x.
Από προεπιλογή, όλα αυτά που είναι παγκόσμια, αν όχι ρητά προετοιμαστεί για κάποια αξία,
έχει μηδενική τιμή ως τιμή.
Έτσι, εδώ, ο κόμβος ρίζα *, δεν προετοιμαστεί ρητά σε τίποτα,
έτσι προεπιλεγμένη τιμή της θα είναι μηδενική, η οποία είναι η μηδενική αξία των δεικτών.
Η προεπιλεγμένη τιμή του x θα σημαίνει ότι x.value είναι μηδέν,
x.left είναι μηδενική, και x.right είναι μηδενική.
Έτσι, δεδομένου ότι είναι ένα struct, όλα τα πεδία του struct θα είναι μηδενικές τιμές.
Δεν χρειάζεται να χρησιμοποιήσετε ότι εδώ, όμως.
[Student] Οι structs είναι διαφορετικές από άλλες μεταβλητές, καθώς και οι άλλες μεταβλητές είναι
αξιών σκουπίδια? αυτά είναι μηδενικά;
[Bowden] Άλλες τιμές πάρα πολύ. Έτσι, σε χ, χ θα είναι μηδέν.
Αν είναι σε παγκόσμια εμβέλεια, έχει μια αρχική τιμή. Εντάξει >>.
[Bowden] Είτε η αρχική τιμή που έδωσε ή μηδέν.
Νομίζω ότι φροντίζει για όλα αυτά.
>> Εντάξει. Έτσι, το επόμενο μέρος της ερώτηση,
"Τώρα θέλουμε να γράψω μια λειτουργία που ονομάζεται περιέχει
με ένα πρωτότυπο περιέχει bool τιμή τύπου int. "
Εμείς δεν πρόκειται να κάνουμε bool περιέχει int αξία.
Πρωτότυπο μας πρόκειται να μοιάσει
bool περιέχει (int αξία.
Και τότε θα είστε, επίσης, πρόκειται να περάσει αυτό το δέντρο
ότι θα πρέπει να έλεγχο για να δούμε αν έχει αυτή την τιμή.
Έτσι, ο κόμβος * δέντρο). Εντάξει.
Και τότε μπορούμε να την αποκαλούμε με κάτι σαν,
ίσως θα θέλουν να printf ή κάτι τέτοιο.
Περιέχει 6, ρίζα μας.
Αυτό θα πρέπει να επιστρέψει ένα, ή αλήθεια,
ενώ περιέχει 5 ρίζα πρέπει να επιστρέψει ψευδείς.
Πάρτε λοιπόν μια δεύτερη για την εφαρμογή της παρούσας.
Μπορείτε να το κάνετε είτε επαναληπτικά ή αναδρομικά.
Το θετικό σχετικά με τον τρόπο με τον οποίο έχετε ρυθμίσει τα πράγματα είναι ότι
επιδέχεται αναδρομική λύση μας πολύ πιο εύκολη
από ό, τι η παγκόσμια μεταβλητή τρόπο έκανε.
Διότι, αν εμείς απλά πρέπει περιέχει int αξία, τότε δεν έχουμε κανένα τρόπο αναδρομική ανάκτηση κάτω υποδένδρων.
Θα πρέπει να έχετε μια ξεχωριστή λειτουργία βοηθός που recurses τις υποδένδρων για μας.
Αλλά επειδή έχουμε αλλάξει για να λάβει το δέντρο ως επιχείρημα,
το οποίο θα έπρεπε να ήταν πάντα στην πρώτη θέση,
τώρα μπορούμε recurse πιο εύκολα.
Έτσι, επαναληπτική ή επαναλαμβανόμενη, θα πάμε πάνω από τα δύο,
αλλά θα δούμε ότι οι αναδρομικές καταλήγει να είναι αρκετά εύκολο.
Εντάξει. Υπάρχει κάποιος που έχει κάτι που μπορεί να λειτουργήσει με;
>> [Φοιτητικό] Έχω μια επαναληπτική λύση. >> Εντάξει, επαναληπτική.
Εντάξει, αυτό φαίνεται καλό.
Έτσι, θέλουν να μας καθοδηγήσει αυτό;
[Φοιτητικό] Σίγουρα. Έτσι, μπορώ να ορίσω μια μεταβλητή temp για να πάρει το πρώτο κόμβο του δέντρου.
Και τότε ακριβώς looped μέσω temp ενώ δεν ισούται null,
έτσι ενώ ήταν ακόμη στο δέντρο, υποθέτω.
Και αν η τιμή είναι ίση με την αξία που temp δείχνει να,
τότε επιστρέφει την τιμή.
Διαφορετικά, ελέγχει αν είναι στη δεξιά πλευρά ή στην αριστερή πλευρά.
Αν έχετε ποτέ μια κατάσταση όπου δεν υπάρχει πιο δέντρο,
τότε επιστρέφει - βγαίνει από το βρόχο και επιστρέφει false.
[Bowden] Εντάξει. Έτσι, αυτό φαίνεται καλό.
Όποιος έχει οποιαδήποτε σχόλια σχετικά με οτιδήποτε;
Δεν έχω κανένα σχόλιο ορθότητα καθόλου.
Το μόνο πράγμα που μπορούμε να κάνουμε είναι αυτός ο τύπος.
Ω, πρόκειται να προχωρήσουμε λίγο μακρουλό.
Θα καθορίσει το εν λόγω επάνω. Εντάξει.
>> Ο καθένας θα πρέπει να θυμάστε πως τριμερή λειτουργεί.
Υπάρχουν σίγουρα έχουν κουίζ στο παρελθόν
που να σας δώσει μια λειτουργία με ένα χειριστή τριμερών
και να πω, να μεταφράσει αυτό, να κάνει κάτι που δεν χρησιμοποιεί τριμερή.
Έτσι, αυτό είναι μια πολύ συνηθισμένη περίπτωση, όταν θα σκεφτόταν να χρησιμοποιήσει τριμερή,
όπου αν κάποια κατάσταση που μια μεταβλητή σε κάτι,
άλλο που την ίδια μεταβλητή για κάτι άλλο.
Αυτό είναι κάτι που πολύ συχνά μπορεί να μετατραπεί σε αυτό το είδος του πράγματος
όπου ορίζεται ότι η μεταβλητή για αυτό - ή, επίσης, είναι αλήθεια αυτό; Στη συνέχεια, αυτό, άλλο αυτό.
[Φοιτητικό] Η πρώτη είναι εάν είναι αλήθεια, έτσι δεν είναι;
[Bowden] Ναι. Ο τρόπος που έχω διαβάσει πάντα είναι, θερμοκρασία ισούται με αξία μεγαλύτερη από την αξία θερμοκρασία,
τότε αυτό, άλλο αυτό. Είναι μια ερώτηση.
Είναι περισσότερο; Στη συνέχεια, κάνει το πρώτο πράγμα. Αλλιώς κάνουμε το δεύτερο πράγμα.
I σχεδόν πάντα - η άνω και κάτω τελεία, απλά - στο κεφάλι μου, διάβασα το άλλο.
>> Υπάρχει κάποιος που έχει μια αναδρομική λύση;
Εντάξει. Αυτό και μόνο θα πάμε να - θα μπορούσε να είναι ήδη μεγάλη,
αλλά θα πάμε να την κάνουμε ακόμα καλύτερη.
Αυτό είναι λίγο πολύ το ίδιο ακριβή ιδέα.
Είναι απλά, καλά, δεν θέλετε να εξηγήσει;
[Φοιτητικό] Σίγουρα. Έτσι είμαστε σίγουροι ότι κάνει το δέντρο δεν είναι null πρώτη,
γιατί αν το δέντρο είναι μηδενική τότε πρόκειται να επιστρέψει false γιατί δεν έχουν βρεθεί.
Και αν υπάρχει ακόμα ένα δέντρο, πάμε σε - εμείς πρώτα να ελέγξετε εάν η τιμή είναι ο τρέχων κόμβος.
Επιστροφή αλήθεια και αν είναι, και αν δεν έχουμε recurse αριστερά ή προς τα δεξιά.
Μήπως αυτό ακούγεται κατάλληλο; >> Χμμ. (Συμφωνία)
Έτσι παρατηρούμε ότι αυτό είναι σχεδόν - δομικά πολύ παρόμοια με την επαναληπτική διάλυμα.
Είναι απλά ότι αντί να αναδρομική ανάκτηση, είχαμε ένα βρόχο while.
Και η βασική περίπτωση όπου εδώ δέντρο δεν ισούται null
ήταν η κατάσταση κατά την οποία χωρίσαμε από τον βρόχο while.
Είναι πολύ παρόμοια. Αλλά θα πάμε να πάρετε ένα βήμα παραπέρα.
Τώρα, κάνουμε το ίδιο πράγμα εδώ.
Παρατηρήστε γυρίζουμε το ίδιο πράγμα και στις δύο από αυτές τις γραμμές,
εκτός από ένα όρισμα είναι διαφορετική.
Έτσι θα πάμε για να κάνουν ότι σε μια τριμερή.
Χτύπησα κάτι επιλογή, και έκανε ένα σύμβολο. Εντάξει.
Έτσι θα πάμε για να επιστρέψει περιέχει αυτό.
Αυτό γίνεται για να είναι πολλαπλές γραμμές, καλά, μεγεθύνεται είναι.
Συνήθως, ως υφολογική πράγμα, δεν νομίζω ότι πολλοί άνθρωποι
βάλετε ένα κενό διάστημα μετά το βέλος, αλλά υποθέτω αν είσαι συνεπής, είναι μια χαρά.
Εάν η τιμή είναι μικρότερη από την τιμή δέντρο, θέλουμε να recurse στο αριστερό δέντρο,
αλλιώς θέλουμε να recurse στο δεξί δέντρο.
Έτσι, αυτό ήταν το πρώτο βήμα της κάνει αυτό το βλέμμα μικρότερο.
Βήμα δύο κάνουν αυτό το βλέμμα μικρότερο -
μπορούμε να χωρίσουμε αυτό σε πολλές γραμμές.
Εντάξει. Βήμα δύο καθιστώντας φαίνεται μικρότερο είναι εδώ,
έτσι αξία ισούται με την επιστροφή αξία δέντρο, ή οτιδήποτε άλλο περιέχει.
>> Αυτό είναι ένα σημαντικό πράγμα.
Δεν είμαι σίγουρος αν είπε ρητά στην τάξη,
αλλά λέγεται βραχυκύκλωμα αξιολόγησης.
Η ιδέα εδώ είναι η αξία == αξία δέντρο.
Αν αυτό είναι αλήθεια, τότε αυτό είναι αλήθεια, και θέλουμε να »ή« ότι με ό, τι είναι πάνω από εδώ.
Έτσι, χωρίς καν να το σκεφτούμε ό, τι είναι πάνω από εδώ,
τι είναι ολόκληρη η έκφραση θα επιστρέψει;
[Φοιτητικό] Αληθές; >> Ναι, επειδή ισχύει τίποτα,
or'd - ή αλήθεια or'd με οτιδήποτε είναι απαραίτητα αλήθεια.
Έτσι, το συντομότερο βλέπουμε τιμή επιστροφής = τιμή δέντρο,
είμαστε ακριβώς πρόκειται να επιστρέψει αλήθεια.
Ούτε πρόκειται να recurse περιέχει περαιτέρω κάτω από τη γραμμή.
Μπορούμε να πάρουμε ένα βήμα παραπέρα.
Επιστροφή δέντρο δεν ισούται άκυρη και όλα αυτά.
Έκανε ένα one-line λειτουργία.
Αυτό είναι επίσης ένα παράδειγμα των βραχυκυκλώματος αξιολόγησης.
Τώρα, όμως, είναι η ίδια ιδέα -
αντί της - οπότε αν δέντρο δεν είναι ίσο με null - ή, επίσης,
αν το δένδρο ίση null, η οποία είναι η κακή περίπτωση,
εάν δέντρο ισούται με μηδέν, τότε η πρώτη προϋπόθεση θα είναι ψευδής.
Έτσι ψευδείς anded με οτιδήποτε πρόκειται να είναι αυτό;
[Φοιτητικό] Λάθος. Ναι >>. Αυτό είναι το άλλο μισό του βραχυκυκλώματος αξιολόγησης,
όπου αν δεν δέντρο ίση null, τότε δεν πρόκειται να πάμε ακόμα -
ή αν το δένδρο ίση null, τότε δεν πρόκειται να κάνουμε αξία == αξία δέντρο.
Είμαστε ακριβώς πρόκειται να επιστρέψει αμέσως ψευδή.
Ποια είναι σημαντικό, διότι αν δεν το έκανε βραχυκύκλωμα αξιολογεί,
στη συνέχεια, αν είναι ίσο δέντρο null, αυτή η δεύτερη προϋπόθεση θα σφάλμα seg,
επειδή δέντρο-> τιμή εύρεση τιμών null.
Έτσι αυτό είναι αυτό. Μπορεί να κάνει αυτό - τη μετατόπιση πάνω από μία φορά.
Αυτό είναι ένα πολύ κοινό πράγμα, επίσης, δεν κάνει αυτό μια γραμμή με αυτό,
αλλά είναι ένα κοινό πράγμα σε συνθήκες, ίσως όχι ακριβώς εδώ,
αλλά αν (δέντρο! = NULL, και δέντρο-> αξία αξίας ==), κάνει ό, τι.
Αυτή είναι μια πολύ κοινή κατάσταση, όπου αντί του έχοντας
να σπάσει αυτό σε δύο ifs, όπου θέλετε, είναι η μηδενική δέντρο;
Εντάξει, δεν είναι μηδενική, οπότε τώρα είναι η αξία δέντρο ίση με την τιμή; Κάνετε αυτό.
Αντ 'αυτού, αυτή η κατάσταση, αυτό δεν πρόκειται ποτέ να διαχωρίζονται από σφάλμα
γιατί θα ξεσπάσει αν αυτό συμβαίνει να είναι μηδενική.
Καλά, υποθέτω ότι αν το δέντρο σας είναι ένα εντελώς άκυρο δείκτη, μπορεί να διαχωρίζονται από ακόμα σφάλμα,
αλλά δεν μπορεί να διαχωρίζονται από υπαιτιότητα αν το δέντρο είναι μηδενική.
Αν ήταν μηδενική, θα ξεσπάσει πριν αναχθούν ποτέ το δείκτη στην πρώτη θέση.
[Φοιτητικό] Είναι αυτό που ονομάζεται lazy evaluation;
>> [Bowden] Lazy αξιολόγησης είναι ένα ξεχωριστό πράγμα.
Lazy αξιολόγησης είναι περισσότερο όπως σας ρωτήσω για μια τιμή,
σας ζητήσει να υπολογιστεί η τιμή, το είδος του, αλλά εσείς δεν το χρειάζεστε άμεσα.
Έτσι, μέχρι να χρειαστεί πραγματικά, δεν αξιολογείται.
Αυτό δεν είναι ακριβώς το ίδιο πράγμα, αλλά στην Huffman PSET,
λέει ότι «νωχελικά» γράφουν.
Ο λόγος που το κάνουμε αυτό είναι γιατί είμαστε buffering πραγματικά τη διαγραφή -
δεν θέλουμε να γράψετε μεμονωμένα κομμάτια σε ένα χρόνο,
ή μεμονωμένες bytes σε μια στιγμή, αντί να θέλουν να πάρουν ένα κομμάτι από bytes.
Στη συνέχεια, αφού έχουμε ένα μεγάλο κομμάτι των bytes, τότε θα το γράψει.
Ακόμα κι αν το ζητήσετε να γράψω - και fwrite και fread κάνουν το ίδιο πράγμα.
Θα σας buffer διαβάζει και γράφει.
Ακόμα κι αν το ζητήσει αμέσως να γράψει, κατά πάσα πιθανότητα δεν θα.
Και δεν μπορείτε να είστε σίγουροι ότι τα πράγματα πρόκειται να γραφτεί
μέχρι να καλέσετε hfclose ή ό, τι είναι,
η οποία στη συνέχεια λέει, εντάξει, είμαι το κλείσιμο του αρχείου μου,
αυτό σημαίνει ότι θα ήθελα να γράψω καλύτερα ό, τι δεν έχω γράψει ακόμα.
Έχει δεν χρειάζεται να γράψετε τα πάντα
μέχρι να κλείσετε το αρχείο, και τότε θα πρέπει να.
Έτσι, αυτό είναι ακριβώς ό, τι τεμπέλης - περιμένει έως ότου έχει να συμβεί.
Αυτό - λαμβάνουν 51 και θα πάμε σε αυτό με περισσότερες λεπτομέρειες,
επειδή ocaml και τα πάντα σε 51, τα πάντα είναι αναδρομή.
Δεν υπάρχουν επαναληπτικές λύσεις, βασικά.
Όλα είναι αναδρομή, και lazy evaluation
πρόκειται να είναι σημαντική για πολλές περιστάσεις
όπου, αν δεν έχετε αξιολογήσει νωχελικά, αυτό θα σήμαινε ότι -
Το παράδειγμα είναι ρεύματα, τα οποία είναι απείρως μεγάλη.
Στη θεωρία, μπορείτε να σκεφτείτε από τους φυσικούς αριθμούς ως ένα ρεύμα 1-2-3-4-5-6-7,
Έτσι, νωχελικά αξιολογούνται τα πράγματα είναι μια χαρά.
Αν πω θέλω τη δέκατη αριθμό, τότε θα μπορεί να αξιολογήσει μέχρι το δέκατο αριθμό.
Αν θέλω την εκατοστή αριθμό, τότε θα μπορεί να αξιολογήσει μέχρι το εκατοστό αριθμό.
Χωρίς τεμπέλης αξιολόγησης, τότε πρόκειται να προσπαθήσει να αξιολογήσει όλους τους αριθμούς αμέσως.
Είσαι αξιολόγηση απείρως πολλούς αριθμούς, και αυτό δεν είναι μόνο δυνατό.
Έτσι, υπάρχουν πολλές περιπτώσεις όπου lazy evaluation
είναι απλά απαραίτητη για να πάρει τα πράγματα στην εργασία.
>> Τώρα θέλουμε να γράψω ένθετο ένθετο όπου θα είναι
ομοίως αλλαγή στον ορισμό του.
Έτσι, αυτή τη στιγμή είναι bool ένθετο (int αξία).
Εμείς πάμε για να το αλλάξουμε αυτό να bool ένθετο (int αξία, κόμβο του δένδρου *).
Είμαστε πραγματικά πρόκειται να αλλάξει και πάλι ότι σε λίγο, θα δούμε γιατί.
Και ας προχωρήσουμε build_node, μόνο για το καλό του,
εισάγετε παραπάνω έτσι δεν έχουμε να γράψει ένα πρωτότυπο της συνάρτησης.
Ποια είναι ένας υπαινιγμός ότι θα πάμε να χρησιμοποιούν build_node στο ένθετο.
Εντάξει. Πάρτε ένα λεπτό για αυτό.
Νομίζω ότι έσωσε την αναθεώρηση, αν θέλετε να τραβήξει από αυτό,
ή, τουλάχιστον, το έκανα τώρα.
Ήθελα ένα μικρό διάλειμμα για να σκεφτεί για τη λογική του ένθετου,
αν δεν μπορείτε να σκεφτείτε από το.
Βασικά, το μόνο που θα πρέπει να τοποθετήσετε ποτέ σε φύλλα.
Όπως, αν εισάγω 1, τότε είμαι αναπόφευκτα θα πρέπει να τοποθετήσετε 1 -
Θα αλλάξει σε μαύρο - I'll να τοποθετήσετε 1 πάνω από εδώ.
Ή αν εισάγω 4, θέλω να τοποθετήσετε 4 πάνω εδώ.
Έτσι, δεν έχει σημασία τι θα κάνεις, θα πάμε να τοποθετήσετε σε ένα φύλλο.
Το μόνο που έχετε να κάνετε είναι να επαναλάβει κάτω από το δέντρο μέχρι να φτάσετε στον κόμβο
αυτό θα πρέπει να είναι γονέας του κόμβου, της μητρικής της νέας κόμβου,
και στη συνέχεια, αλλάξτε τα αριστερά ή προς τα δεξιά του δείκτη, ανάλογα με το αν
είναι μεγαλύτερη από ή μικρότερη από τον τρέχοντα κόμβο.
Αλλάξτε αυτό το δείκτη να επισημάνει νέος κόμβος σας.
Έτσι επαναλάβει κάτω από το δέντρο, να κάνει το σημείο φύλλο στο νέο κόμβο.
Επίσης, σκεφτείτε γιατί ότι απαγορεύει το είδος της κατάστασης πριν,
όπου θα κατασκευαστεί το δυαδικό δέντρο όπου ήταν σωστή
αν μόνο κοίταξε ένα μόνο κόμβο,
αλλά 9 ήταν στα αριστερά από 7 αν επαναληφθεί κάτω σε όλη τη διαδρομή.
Έτσι, αυτό είναι αδύνατο σε αυτό το σενάριο, δεδομένου ότι -
σκέφτονται την εισαγωγή περίπου 9 ή κάτι τέτοιο? στην πρώτη κόμβο,
Πάω να δω 7 και είμαι απλώς πρόκειται να πάει προς τα δεξιά.
Έτσι, δεν έχει σημασία τι κάνω, αν είμαι εισαγωγή από τη μετάβαση σε ένα φύλλο,
και σε ένα φύλλο χρησιμοποιώντας τον κατάλληλο αλγόριθμο,
πρόκειται να είναι αδύνατο για μένα να εισάγετε 9 έως αριστερά από 7
γιατί μόλις χτύπησα 7 Πάω να πάμε προς τα δεξιά.
Υπάρχει κάποιος που έχει κάτι για να αρχίσει με;
[Φοιτητικό] κάνω. Σίγουρα >>.
[Φοιτητών, ακατάληπτο]
[Άλλες φοιτητής, ακατάληπτο]
[Bowden] Είναι ευπρόσδεκτη. Εντάξει. Θέλετε να εξηγήσει;
>> [Φοιτητικό] Από τη στιγμή που ξέρουμε ότι εισάγοντας
νέοι κόμβοι στο τέλος του δέντρου,
I τυλιγμένο μέσα από το δέντρο επαναληπτικό
έως ότου πήρα σε ένα κόμβο που επεσήμανε σε null.
Και τότε αποφάσισα να το θέσω είτε στη δεξιά είτε στην αριστερή πλευρά
με τη χρήση αυτού του δικαιώματος μεταβλητή? μου είπε πού να το θέσω.
Και τότε, κατ 'ουσίαν, Έκανα ότι η τελευταία -
ότι το σημείο κόμβος θερμοκρασία στο νέο κόμβο που ήταν η δημιουργία,
είτε στην αριστερή πλευρά ή στην δεξιά πλευρά, ανάλογα με το ποια είναι η αξία σωστό ήταν.
Τέλος, μπορώ να ορίσω τη νέα τιμή κόμβο με την αξία της δοκιμής του.
[Bowden] Εντάξει, έτσι βλέπω ένα θέμα εδώ.
Αυτό είναι όπως το 95% του τρόπου εκεί.
Το μόνο θέμα που βλέπω, καλά, δεν βλέπω κανέναν άλλο ένα ζήτημα;
Ποια είναι η περίσταση βάσει των οποίων θα σπάσει έξω από το βρόχο;
[Φοιτητικό] Αν temp είναι άκυρη; Ναι >>. Λοιπόν, πώς μπορείτε να σπάσει έξω από το βρόχο αν είναι temp είναι μηδενική.
Αλλά αυτό που μπορώ να κάνω εδώ;
I dereference θερμοκρασία, η οποία είναι αναπόφευκτα null.
Έτσι, το άλλο πράγμα που πρέπει να κάνετε είναι όχι μόνο να παρακολουθείτε μέχρι temp είναι μηδενική,
θέλετε να παρακολουθείτε της μητρικής ανά πάσα στιγμή.
Θέλουμε, επίσης, ο κόμβος γονέας *, υποθέτω ότι μπορεί να κρατήσει ότι σε null την πρώτη.
Αυτό πρόκειται να έχουν περίεργη συμπεριφορά για την ρίζα του δέντρου,
αλλά θα φτάσουμε σε αυτό.
Εάν η τιμή είναι μεγαλύτερη από οτιδήποτε άλλο, τότε temp = temp δικαίωμα.
Αλλά πριν το κάνουμε αυτό, γονέας = temp.
Ή οι γονείς πάντα θα ίση θερμοκρασία; Είναι ότι η υπόθεση;
Αν temp δεν είναι μηδενική, τότε θα πάω να μετακινηθείτε προς τα κάτω, δεν το θέμα αυτό,
σε έναν κόμβο για την οποία temp είναι ο γονέας.
Έτσι γονέας πρόκειται να είναι temp, και στη συνέχεια θα προχωρήσουμε θερμοκρασία κάτω.
Τώρα temp είναι μηδενική, αλλά επισημαίνει γονέα στη μητρική του πράγματος που είναι null.
Έτσι, εδώ κάτω, δεν θέλω να ρυθμίσετε το δικαίωμα ισούται με 1.
Γι 'αυτό και κινήθηκε προς τα δεξιά, οπότε αν δεξιά = 1,
και υποθέτω ότι και εσείς θέλετε να κάνετε -
αν μετακινηθείτε προς τα αριστερά, θέλετε να ρυθμίσετε το δικαίωμα ίση με 0.
Ή αλλιώς, αν ποτέ μετακινηθεί προς τα δεξιά.
Έτσι, δεξιά = 0. Αν δεξιά = 1,
Τώρα θέλουμε να κάνουμε το μητρικό δικαίωμα newnode δείκτη,
αλλιώς θέλουμε να κάνουμε το γονέα αριστερά newnode δείκτη.
Ερωτήσεις σχετικά με αυτό;
Εντάξει. Έτσι, αυτός είναι ο τρόπος με τον οποίο - και, στην πραγματικότητα, αντί να γίνει αυτό,
έχουμε ένα δεύτερο αναμένεται μπορείτε να χρησιμοποιήσετε build_node.
Και στη συνέχεια, αν newnode ισούται με null, επιστρέφει false.
Αυτό είναι αυτό. Τώρα, αυτό είναι ό, τι περιμέναμε να το κάνετε.
>> Αυτό είναι ό, τι κάνουν οι λύσεις του προσωπικού.
Διαφωνώ με αυτό, όπως το "σωστό" τρόπο να πάει γι 'αυτό
αλλά αυτό είναι απολύτως εντάξει και αυτό θα λειτουργήσει.
Ένα πράγμα που είναι λίγο παράξενο τώρα είναι
αν το δέντρο ξεκινά ως null, περνάμε σε ένα δέντρο null.
Υποθέτω ότι εξαρτάται από το πώς θα καθορίσει τη συμπεριφορά του περνώντας σε ένα δέντρο null.
Θα ήθελα να πιστεύω ότι αν περάσει σε ένα δέντρο null,
στη συνέχεια, εισάγοντας την τιμή null σε ένα δέντρο
πρέπει απλά να επιστρέψει ένα δέντρο, όπου η μόνη αξία είναι ότι μόνο κόμβο.
Υπάρχουν άτομα που συμφωνούν με αυτό; Θα μπορούσε, αν ήθελε,
αν περάσει σε ένα δέντρο null
και θέλετε να εισαγάγετε μια τιμή σε αυτό, επιστρέφουν ψευδείς.
Είναι στο χέρι σας να καθορίσει αυτό.
Για να κάνει το πρώτο πράγμα που είπα και τότε -
καλά, θα πάμε να έχουν πρόβλημα να το κάνουμε αυτό, επειδή
θα ήταν ευκολότερο αν είχαμε ένα παγκόσμιο δείκτη στο πράγμα,
αλλά δεν, οπότε αν το δέντρο είναι μηδενική, δεν υπάρχει τίποτα που μπορούμε να κάνουμε γι 'αυτό.
Εμείς μπορούμε απλά να επιστρέψει false.
Έτσι, Πάω να αλλάξει ένθετο.
Εμείς τεχνικά θα μπορούσε να αλλάξει μόνο αυτό το δικαίωμα εδώ,
πώς είναι τα πράγματα για την επανάληψη,
αλλά Πάω να αλλάξει ένθετο να λάβει ένας κόμβος ** δέντρο.
Διπλό δείκτες.
Τι σημαίνει αυτό;
Αντί να ασχολείται με δείκτες προς τους κόμβους,
το πράγμα Πάω να είναι αυτή η χειραγώγηση δείκτη.
Πάω να χειρίζονται αυτό το δείκτη.
Πάω να χειρίζονται απευθείας δείκτες.
Αυτό είναι λογικό δεδομένου ότι, σκεφτείτε κάτω -
καλά, τώρα αυτό δείχνει σε null.
Αυτό που θέλω να κάνετε είναι να χειραγωγήσουν το δείκτη στο σημείο να μην null.
Θέλω να επισημάνω ότι στο νέο κόμβο μου.
Αν έχω κρατήσει μόνο κομμάτι του δείκτες σε δείκτες μου,
τότε δεν χρειάζεται να παρακολουθείτε το δείκτη του γονέα.
Μπορώ να κρατήσει μόνο δρόμο για να δούμε αν ο δείκτης δείχνει σε null,
και εάν ο δείκτης δείχνει σε null,
αλλάξετε σε σημείο να τον κόμβο που θέλω.
Και μπορώ να το αλλάξει από τότε έχω ένα δείκτη για το δείκτη.
Ας δούμε αυτό το δικαίωμα τώρα.
Μπορείτε να το κάνετε πραγματικά αναδρομικά αρκετά εύκολα.
Θέλουμε να το κάνουμε αυτό;
Ναι, το κάνουμε.
>> Ας το δούμε αναδρομικά.
Κατ 'αρχάς, τι είναι βασική περίπτωση μας πρόκειται να είναι;
Σχεδόν πάντα βασική περίπτωση μας? Αλλά στην πραγματικότητα, αυτό είναι το είδος του δύσκολη.
Τα πρώτα πράγματα πρώτα, αν (δέντρο == NULL)
Υποθέτω ότι είμαστε ακριβώς πρόκειται να επιστρέψει ψευδείς.
Αυτό είναι διαφορετικό από το δέντρο σας να είναι null.
Αυτός είναι ο δείκτης σε δείκτη ρίζας σας είναι null
πράγμα που σημαίνει ότι ο δείκτης ρίζα σας δεν υπάρχει.
Έτσι, εδώ κάτω, αν το κάνω
* κόμβος - ας επαναχρησιμοποίηση ακριβώς αυτό.
Κόμβος ρίζα * = NULL,
και στη συνέχεια, Πάω να καλέσω ένθετο κάνοντας κάτι σαν,
εισάγετε & 4 σε ρίζα.
Έτσι & ρίζα, ρίζα, αν είναι κόμβος *
τότε και ρίζα πρόκειται να είναι ένα ** κόμβο.
Αυτό είναι έγκυρο. Σε αυτή την περίπτωση, δέντρο, μέχρι εδώ,
δέντρο δεν είναι null - ή ένθετο.
Εδώ. Δέντρο δεν είναι null? * Δέντρο είναι μηδενική, το οποίο είναι μια χαρά
γιατί αν δέντρο * είναι null, τότε μπορώ να το χειριστείτε
τώρα να επισημάνω σε αυτό που θέλω να επισημάνω.
Αλλά αν το δέντρο είναι μηδενική, αυτό σημαίνει ότι ήρθα εδώ κάτω και είπε null.
Αυτό δεν έχει νόημα. Δεν μπορώ να κάνω τίποτα με αυτό.
Αν το δέντρο είναι null, επιστρέφει false.
Γι 'αυτό και βασικά ήδη πει ποια είναι η πραγματική βασική περίπτωση μας είναι.
Και αυτό είναι ότι πρόκειται να είναι;
[Φοιτητών, ακατάληπτο]
[Bowden] Ναι. Έτσι, αν (* δέντρο == NULL).
Αυτό σχετίζεται με την υπόθεση εδώ
όπου αν μου κόκκινο δείκτης είναι ο δείκτης είμαι επικεντρώθηκε,
έτσι όπως είμαι συγκεντρωμένος σε αυτό το δείκτη, τώρα είμαι συγκεντρωμένος σε αυτό το δείκτη.
Τώρα είμαι συγκεντρωμένος σε αυτό το δείκτη.
Έτσι, αν μου κόκκινο δείκτη, η οποία είναι ** κόμβο μου,
είναι ποτέ - σε περίπτωση *, κόκκινο δείκτη μου, δεν είναι ποτέ μηδενική,
αυτό σημαίνει ότι είμαι σε περίπτωση που είμαι εστιάζοντας σε ένα δείκτη που δείχνει -
αυτό είναι ένας δείκτης που ανήκει σε ένα φύλλο.
Θέλω να αλλάξω το δείκτη στο σημείο στο νέο κόμβο μου.
Έλα εδώ.
Newnode μου θα είναι μόνο ο κόμβος * n = build_node (αξία)
τότε n, αν n = NULL, επιστρέφουν ψευδείς.
Αλλιώς θέλουμε να αλλάξουμε ό, τι ο δείκτης δείχνει αυτή τη στιγμή να
τώρα να επισημάνω για νεότευκτα κόμβο μας.
Μπορούμε να το κάνουμε αυτό πραγματικότητα εδώ.
Αντί να λέτε n, λέμε * δέντρο * = εάν δέντρο.
Όλοι καταλαβαίνουν ότι; Ότι με την αντιμετώπιση δείκτες σε δείκτες,
μπορούμε να αλλάξουμε null δείκτες να δείχνουν τα πράγματα που θέλουμε να επισημάνω.
Αυτό είναι το βασικό σενάριο μας.
>> Τώρα υποτροπή μας, ή αναδρομή μας,
πρόκειται να είναι πολύ παρόμοια σε όλες τις άλλες επαναλήψεις έχουμε κάνει.
Εμείς πάμε να θέλετε να εισάγετε αξίας,
και τώρα είμαι πρόκειται να χρησιμοποιήσετε τριμερή πάλι, αλλά αυτό που μας κατάσταση θα είναι;
Τι είναι αυτό που ψάχνουμε για να αποφασίσουμε αν θέλουμε να πάμε προς τα αριστερά ή δεξιά;
Ας το κάνουμε σε ξεχωριστά βήματα.
Αν (τιμή <) τι;
[Φοιτητικό] Η αξία του δέντρου;
[Bowden] Έτσι, να θυμάστε ότι είμαι σήμερα -
[Φοιτητές, ακατάληπτο]
[Bowden] Ναι, έτσι ακριβώς εδώ, ας πούμε ότι αυτό το πράσινο βέλος
είναι ένα παράδειγμα του τι είναι σήμερα δέντρου, είναι ένας δείκτης για αυτό το δείκτη.
Έτσι ώστε σημαίνει ότι είμαι ένας δείκτης σε δείκτη 3.
Η dereference δύο φορές ακούγονται ωραία.
Τι να κάνω - πώς μπορώ να το κάνω αυτό;
[Φοιτητικό] Αποαναφορά μια φορά, και στη συνέχεια κάντε βέλος με αυτόν τον τρόπο;
[Bowden] Έτσι (* δέντρο) είναι η dereference μια φορά, -> αξία
πρόκειται να μου δώσει την τιμή του κόμβου ότι είμαι έμμεσα δείχνοντας.
Έτσι, μπορώ επίσης να γράψετε ** tree.value αν προτιμάτε αυτό.
Είτε δουλεύει.
Αν αυτή είναι η περίπτωση, τότε θα θέλετε να καλέσετε εισάγετε με αξία.
Και τι ενημερώνεται κόμβο μου ** πρόκειται να είναι;
Θέλω να πάω προς τα αριστερά, έτσι ** tree.left πρόκειται να είναι αριστερά μου.
Και θέλω να το δείκτη αυτό το πράγμα
έτσι ώστε εάν το αριστερό καταλήγει να είναι η μηδενική δείκτη,
Μπορώ να το τροποποιήσετε ώστε να δείχνει προς νέο κόμβο μου.
>> Και η άλλη περίπτωση μπορεί να είναι πολύ παρόμοια.
Ας κάνουν ότι πραγματικά τριμερή μου αυτή τη στιγμή.
Τοποθετήστε αξία εάν η αξία <(** δέντρο). Αξία.
Τότε θέλουμε να ενημερώσετε ** μας προς τα αριστερά,
αλλιώς θέλουμε να ενημερώσετε ** μας προς τα δεξιά.
[Φοιτητικό] Μήπως να πάρει ότι το δείκτη στο δείκτη;
[Bowden] Θυμηθείτε ότι - ** tree.right είναι ένας κόμβος αστέρι.
[Φοιτητών, ακατάληπτο] >> Ναι.
** Tree.right είναι σαν αυτό το δείκτη ή κάτι τέτοιο.
Έτσι, με τη λήψη ενός δείκτη με αυτό, που μου δίνει αυτό που θέλω
του δείκτη σε αυτόν τον τύπο.
[Φοιτητικό] Θα μπορούσαμε να πάμε ξανά γιατί χρησιμοποιούμε τα δίποντα;
[Bowden] Ναι. Έτσι - δεν μπορείτε, και ότι η λύση πριν από
Ήταν ένας τρόπος για να γίνει αυτό χωρίς να κάνει δύο δείκτες.
Θα πρέπει να είναι σε θέση να κατανοήσουν τη χρήση δίποντα,
και αυτό είναι ένα καθαρότερο διάλυμα.
Επίσης, παρατηρούμε ότι, ό, τι θα συμβεί αν το δέντρο μου -
τι θα συμβεί αν ρίζα μου ήταν μηδενική; Τι θα συμβεί αν κάνω αυτή την περίπτωση εδώ;
Έτσι, ο κόμβος ρίζα * = NULL, εισάγετε & 4 σε ρίζα.
Τι είναι η ρίζα πρόκειται να είναι μετά από αυτό;
[Φοιτητών, ακατάληπτο] >> Ναι.
Root αξία θα είναι 4.
Root αριστερά θα είναι μηδενική, το δικαίωμα ρίζα θα είναι μηδενική.
Στην περίπτωση όπου δεν περνούν ρίζας κατά διεύθυνση,
δεν θα μπορούσε να τροποποιήσει ρίζα.
Στην περίπτωση όπου το δέντρο - όπου root ήταν μηδενική,
εμείς απλά έπρεπε να επιστρέψει ψευδείς. Δεν υπάρχει τίποτα που θα μπορούσαμε να κάνουμε.
Δεν μπορείτε να εισαγάγετε έναν κόμβο σε ένα άδειο δέντρο.
Αλλά τώρα μπορούμε? Κάνουμε απλώς ένα άδειο δέντρο σε ένα κόμβο του δένδρου.
Ποιο είναι συνήθως το αναμενόμενο τρόπο ώστε να είναι υποτίθεται ότι πρέπει να εργάζονται.
>> Επιπλέον, αυτό είναι σημαντικά μικρότερος από ό, τι
επίσης την παρακολούθηση της μητρικής, και έτσι μπορείτε επαναλάβει τα κάτω σε όλη τη διαδρομή.
Τώρα έχω γονέα μου, και έχω μόνο γονέα δείκτη μου δικαίωμα να το οτιδήποτε.
Αντ 'αυτού, αν το κάναμε αυτό επαναληπτικό, θα ήθελα να είναι η ίδια ιδέα με ένα βρόχο while.
Όμως, αντί να πρέπει να ασχοληθεί με το δείκτη των γονιών μου,
αντί τρέχουσα δείκτης μου θα είναι το πράγμα
ότι είμαι άμεσα τροποποίηση στο σημείο στο νέο κόμβο μου.
Δεν έχω να ασχοληθεί με το αν είναι στραμμένη προς τα αριστερά.
Δεν έχω να ασχοληθεί με το αν είναι στραμμένη προς τα δεξιά.
Είναι ακριβώς ό, τι αυτό δείκτης, Πάω να το ρυθμίσετε να επισημάνει νέο κόμβο μου.
Όλοι καταλαβαίνουν πώς λειτουργεί;
Αν γιατί δεν θέλουμε να το κάνουμε με αυτόν τον τρόπο,
αλλά τουλάχιστον ότι αυτό λειτουργεί ως λύση;
[Φοιτητικό] Πού θα επιστρέψει αλήθεια;
[Bowden] Αυτό είναι πιθανώς ακριβώς εδώ.
Αν τοποθετήσετε σωστά, επιστρέψτε αλήθεια.
Αλλιώς, εδώ κάτω θα πάμε να θέλουν να επιστρέψουν και υπό οποιεσδήποτε δηλώσεις ένθετο.
>> Και τι είναι αυτό το ιδιαίτερο αναδρομική συνάρτηση;
Είναι ουρά επαναληπτικό, έτσι εφ 'όσον έχουμε καταρτίσει με κάποια βελτιστοποίηση,
θα αναγνωρίσουμε ότι και εσείς ποτέ δεν θα πάρετε μια στοίβα από υπερχείλιση αυτό,
ακόμη και αν μας δέντρο έχει ύψος 10.000 ή 10 εκατ. ευρώ.
[Φοιτητών, ακατάληπτο]
[Bowden] Νομίζω ότι το κάνει στο Dash - ή τι επίπεδο βελτιστοποίησης
απαιτείται για ένα αναδρομή ουράς να αναγνωριστεί.
Νομίζω ότι αναγνωρίζει - Συμβουλίου Συνεργασίας του Κόλπου και Clang
Επίσης, έχει διαφορετικές σημασίες για τη βελτιστοποίηση των επιπέδων τους.
Θέλω να πω ότι είναι Dasho 2, είναι σίγουρο ότι θα αναγνωρίσουν την ουρά αναδρομή.
Αλλά εμείς - θα μπορούσατε να κατασκευάσει σαν παράδειγμα Fibonocci ή κάτι τέτοιο.
Δεν είναι εύκολο να δοκιμάσει με αυτό, επειδή είναι δύσκολο να κατασκευάσει
ένα δυαδικό δέντρο που είναι τόσο μεγάλο.
Αλλά ναι, νομίζω ότι είναι Dasho 2, που
αν φτιάξετε με Dasho 2, θα ψάξει για αναδρομή ουρά
και τη βελτιστοποίηση ότι έξω.
Ας πάμε πίσω στο - εισαγωγή είναι κυριολεκτικά το τελευταίο πράγμα που χρειάζεται.
Ας πάμε πίσω στο ένθετο εδώ
όπου θα πάμε για να κάνουμε την ίδια ιδέα.
Θα εξακολουθούν να έχουν το ελάττωμα να μην είναι σε θέση να χειριστεί εξ ολοκλήρου
όταν η ίδια η ρίζα είναι μηδενική, ή η τελευταία είσοδος είναι μηδενική,
αλλά αντί ασχολούνται με ένα δείκτη γονέα,
ας εφαρμόσουμε την ίδια λογική της διατήρησης δείκτες σε δείκτες.
Αν εδώ κρατάμε τον κόμβο μας ** τρέχουσα,
και δεν χρειάζεται να παρακολουθείτε το δικαίωμα πια,
αλλά κόμβος ** τρέχουσα = & δέντρο.
Και τώρα βρόχο, ενώ μας πρόκειται να είναι, ενώ τρέχουσα * δεν ισούται null.
Δεν χρειάζεται να παρακολουθείτε γονείς πια.
Δεν χρειάζεται να παρακολουθείτε από αριστερά και δεξιά.
Και εγώ θα το ονομάσουμε θερμοκρασία, γιατί είμαστε ήδη χρησιμοποιούν temp.
Εντάξει. Έτσι, αν (τιμή> * temp),
τότε & (* temp) -> δικαίωμα
άλλο temp = & (* temp) -> αριστερά.
Και τώρα, σε αυτό το σημείο, μετά από αυτό το βρόχο while,
Κάνω μόνο αυτό, γιατί ίσως είναι πιο εύκολο να σκεφτούμε επαναληπτικά από αναδρομικά,
αλλά μετά από αυτό το βρόχο while,
* Temp είναι ο δείκτης που θέλουμε να αλλάξουμε.
>> Πριν είχαμε γονέα, και θα ήθελε να αλλάξει είτε αριστερά γονέα ή γονέων δικαίωμα,
αλλά αν θέλουμε να αλλάξουμε το δικαίωμα γονέα,
* temp τότε είναι σωστό γονέα, και μπορούμε να το αλλάξουμε άμεσα.
Έτσι, εδώ κάτω, μπορούμε να κάνουμε * temp = newnode, και αυτό είναι αυτό.
Έτσι ειδοποίηση, όλοι κάναμε σε αυτό ήταν να πάρουν τις γραμμές του κώδικα.
Για να παρακολουθείτε της μητρικής σε όλα αυτά είναι επιπλέον προσπάθεια.
Εδώ, αν κρατάμε μόνο κομμάτι του δείκτη στο δείκτη,
και ακόμα και αν θέλαμε να απαλλαγούμε από όλα αυτά τα άγκιστρα τώρα,
να φανεί μικρότερο.
Αυτή είναι τώρα η ίδια ακριβώς λύση,
αλλά λιγότερες γραμμές κώδικα.
Μόλις αρχίσετε να αναγνωρίζει ως έγκυρη λύση,
Είναι επίσης ευκολότερο να λόγος για παρά σαν, εντάξει,
γιατί έχω αυτή την σημαία σε int δικαίωμα;
Τι σημαίνει αυτό; Ω, αυτό είναι που σημαίνει ότι
κάθε φορά που πάω δεξιά, πρέπει να το ρυθμίσετε,
αλλιώς αν πάω αριστερά θα πρέπει να οριστεί σε μηδέν.
Εδώ, δεν έχω λόγο να γι 'αυτό? Είναι απλά πιο εύκολο να σκεφτούμε.
Ερωτήσεις;
[Φοιτητών, ακατάληπτο] >> Ναι.
Εντάξει, έτσι το τελευταίο κομμάτι -
Υποθέτω ότι μια γρήγορη και εύκολη λειτουργία που μπορούμε να κάνουμε είναι,
let's - μαζί, υποθέτω, προσπαθήστε και γράψτε μια συνάρτηση περιέχει
η οποία δεν ενδιαφέρεται αν είναι ένα δυαδικό δέντρο αναζήτησης.
Αυτό περιλαμβάνει τη λειτουργία θα πρέπει να επιστρέψει αλήθεια
αν οπουδήποτε σε αυτό το γενικό δυαδικού δένδρου είναι η τιμή που ψάχνουμε.
Ας κάνουμε πρώτα αναδρομικά και στη συνέχεια θα το κάνουμε επαναληπτικά.
Μπορούμε πραγματικά να κάνουμε αυτό ακριβώς μαζί, γιατί αυτό θα είναι πολύ σύντομη.
>> Τι είναι η βασική περίπτωση μου πρόκειται να;
[Φοιτητών, ακατάληπτο]
[Bowden] Έτσι, εάν (δέντρο == NULL), τότε τι;
[Φοιτητικό] Επιστροφή ψευδείς.
[Bowden] Αλλιώς, καλά, δεν χρειάζεται το άλλο.
Αν ήταν άλλη περίπτωση βάσης μου.
Αξία [Φοιτητών] Δέντρο της; Ναι >>.
Έτσι, αν (δέντρο-> == αξία αξίας.
Παρατηρήστε ότι είμαστε πίσω σε κόμβο * όχι, ο κόμβος s **;
Περιέχει ποτέ δεν θα χρειαστεί να χρησιμοποιήσετε ένα ** κόμβο,
δεδομένου ότι δεν τροποποιούν δείκτες.
Είμαστε απλώς διέρχονται από αυτούς.
Αν αυτό συμβεί, τότε θα θέλουν να επιστρέψουν αλήθεια.
Αλλιώς θέλουμε να διασχίζουν τα παιδιά.
Έτσι, δεν μπορούμε να σκεφτούν σχετικά με το αν τα πάντα προς τα αριστερά είναι λιγότερο
και τα πάντα προς τα δεξιά είναι μεγαλύτερη.
Έτσι, αυτό που μας κατάσταση θα είναι εδώ - ή, τι θα κάνουμε;
[Φοιτητών, ακατάληπτο] >> Ναι.
Επιστροφή περιέχει (αξία, δέντρο-> αριστερά)
ή περιέχει (αξία, δέντρο-> δεξιά). Και αυτό είναι αυτό.
Και παρατηρήσετε υπάρχει κάποια βραχυκύκλωμα αξιολόγησης,
όπου αν τυχαίνει να βρείτε την τιμή στο αριστερό δέντρο,
ποτέ δεν πρέπει να κοιτάξουμε στο σωστό δέντρο.
Αυτή είναι η όλη λειτουργία.
Τώρα, ας το κάνουμε επαναληπτικά,
η οποία θα είναι λιγότερο ωραίο.
Θα λάβει τη συνήθη έναρξη του κόμβου * = τρέχουσα δέντρο.
Ενώ (τρέχουσα! = NULL).
Γρήγορα θα δείτε ένα πρόβλημα.
Αν τρέχουσα - από εδώ, αν ποτέ ξεφύγει από αυτό,
τότε έχουμε εξαντληθεί τα πράγματα να δούμε, έτσι επιστρέφουν ψευδείς.
Αν (τρέχουσα-> αξία αξίας ==), επιστρέφουν αλήθεια.
Μέχρι τώρα, είμαστε σε θέση -
δεν ξέρουμε αν θέλουμε να πάμε αριστερά ή προς τα δεξιά.
Έτσι αυθαίρετα, ας πάμε αριστερά.
Έχω προφανώς τρέχει σε ένα θέμα για το οποίο έχω εγκαταλείψει εντελώς τα πάντα -
Θα ελέγξει ποτέ μόνο την αριστερή πλευρά του δέντρου.
Ποτέ δεν θα ελέγξει κάτι που αποτελεί δικαίωμα του παιδιού τίποτα.
Πώς μπορώ να το διορθώσω αυτό;
[Φοιτητικό] Θα πρέπει να παρακολουθείτε την αριστερή και δεξιά σε μια στοίβα.
[Bowden] Ναι. Ας κάνουν
struct λίστα, ο κόμβος * n, και στη συνέχεια ο κόμβος ** επόμενος;
Νομίζω ότι δουλεύει μια χαρά.
Θέλουμε να πάμε πάνω από το αριστερό, ή let's - μέχρι εδώ.
Struct = κατάλογος λίστα, αυτό θα αρχίσει
από αυτή τη λίστα struct.
* List = NULL. Έτσι, αυτό πρόκειται να είναι συνδεδεμένη λίστα μας
των υποδένδρων ότι έχουμε παρακάμπτονται.
Θα διασχίσει φύγει τώρα,
αλλά από τη στιγμή που αναπόφευκτα πρέπει να έρθουν πίσω προς τα δεξιά,
Εμείς πάμε για να κρατήσει τη δεξιά πλευρά στο εσωτερικό της λίστας struct μας.
Τότε θα έχουμε new_list ή struct,
* struct λίστα, new_list = malloc (sizeof (κατάλογος)).
Πάω να αγνοήσει λάθος-ότι ο έλεγχος, αλλά θα πρέπει να ελέγξετε για να δείτε null αν είναι.
New_list τον κόμβο πρόκειται να επισημάνω -
Ω, αυτός είναι ο λόγος που ήθελε εδώ. Είναι πρόκειται να επισημάνω για μια δεύτερη λίστα struct.
Αυτό είναι ακριβώς το πώς συνδέονται λίστες εργασίας.
Αυτό είναι το ίδιο με ένα κατάλογο που συνδέονται int
εκτός είμαστε αντικαθιστώντας απλά int * με τον κόμβο.
Είναι ακριβώς η ίδια.
Έτσι new_list, η τιμή του κόμβου new_list μας,
πρόκειται να είναι τρέχουσα-> δεξιά.
Η αξία των new_list μας-> επόμενο θα είναι αρχική λίστα μας,
και στη συνέχεια θα πάμε να ενημερώσετε τον κατάλογο μας στο σημείο να new_list.
>> Τώρα χρειαζόμαστε κάποιο είδος της τρόπο τραβώντας τα πράγματα,
όπως έχουμε διασχίσει ολόκληρο το αριστερό υποδέντρο.
Τώρα πρέπει να τραβήξει τα πράγματα έξω από αυτό,
όπως η τρέχουσα είναι null? δεν θέλουμε απλά να επιστρέψει ψευδείς.
Θέλουμε να τραβήξει έξω τώρα στη νέα λίστα μας.
Ένας εύκολος τρόπος για να γίνει αυτό - και, στην πραγματικότητα, δεν υπάρχει πολλαπλούς τρόπους για να γίνει αυτό.
Όποιος έχει κάποια πρόταση;
Πού πρέπει να κάνω αυτό ή το πώς θα πρέπει να το κάνετε αυτό;
Έχουμε μόνο μερικά λεπτά, αλλά οποιεσδήποτε προτάσεις;
Αντί - ένας τρόπος, αντί να μας κατάσταση ενώ,
ό, τι είμαστε σήμερα κοιτάζοντας δεν είναι μηδενική,
αντί να πάμε να συνεχίσουμε να πάει μέχρι λίστα μας είναι η ίδια άκυρη.
Έτσι, αν λίστα μας καταλήγει να είναι μηδενική,
τότε έχουμε εξαντληθεί τα πράγματα να αναζητήσουμε, να αναζητήσετε πάνω.
Αλλά αυτό σημαίνει ότι το πρώτο πράγμα στη λίστα μας είναι ακριβώς πρόκειται να είναι ο πρώτος κόμβος.
Το πρώτο πράγμα που θα είναι - δεν έχουμε πλέον πρέπει να δούμε ότι.
Έτσι λίστα-> n θα είναι δέντρο μας.
list-> επόμενο θα είναι μηδενική.
Και τώρα, ενώ λίστα δεν είναι ίσο με null.
Cur πρόκειται να τραβήξει κάτι από την λίστα μας.
Έτσι τρέχουσα πρόκειται για ίση λίστα-> n.
Και τότε η λίστα θα ίση λίστα-> n, ή λίστα-> επόμενο.
Έτσι, αν η αξία ισούται με τρέχουσα αξία.
Τώρα μπορούμε να προσθέσουμε και τα δύο δεξιά δείκτη μας και αριστερά μας το δείκτη
εφ 'όσον δεν είστε null.
Εδώ κάτω, υποθέτω ότι θα έπρεπε να είχαμε κάνει αυτό στην πρώτη θέση.
Αν (τρέχουσα-> δεξιά! = NULL)
τότε θα πρόκειται να εισαγάγει τις κόμβο στη λίστα μας.
Αν (τρέχουσα-> αριστερά), αυτό είναι ένα μικρό κομμάτι του φόρτου εργασίας, αλλά είναι μια χαρά.
Αν (τρέχουσα-> αριστερά! = NULL),
και θα πάμε για να εισάγετε το αριστερό σε συνδεδεμένη λίστα μας,
και ότι θα πρέπει να είναι αυτό.
Έχουμε επαναλάβει - εφ 'όσον έχουμε κάτι στη λίστα μας,
έχουμε ένα άλλο κόμβο να δούμε.
Έτσι βλέπουμε σε αυτόν τον κόμβο,
προχωρούμε λίστα μας για το επόμενο.
Αν αυτός ο κόμβος είναι η τιμή που ψάχνουμε, μπορούμε να επιστρέψουμε αλήθεια.
Αλλιώς τοποθετήστε τα δύο αριστερά και δεξιά υποδένδρων μας,
εφ 'όσον δεν είστε null, στην λίστα μας
έτσι ώστε να πάμε αναπόφευκτα πάνω τους.
Έτσι, αν δεν ήταν άκυρη,
αν ο δείκτης ρίζα μας επεσήμανε δύο πράγματα,
τότε στο πρώτο μας τράβηξε κάτι έτσι λίστα μας καταλήγει να είναι null.
Και στη συνέχεια, βάζουμε δύο πράγματα πίσω στο, έτσι τώρα λίστα μας είναι το μέγεθος 2.
Στη συνέχεια θα πάμε στο βρόχο πίσω και είμαστε ακριβώς πρόκειται να τραβήξει,
ας πούμε, το αριστερό δείκτη του ριζικού κόμβου μας.
Και αυτό ακριβώς θα συνεχίζουν να συμβαίνουν? Θα καταλήξουμε looping πάνω από όλα.
>> Παρατηρήστε ότι αυτή ήταν σημαντικά πιο περίπλοκη
στο επαναληπτικό διάλυμα.
Και έχω πει πολλές φορές
ότι η αναδρομική λύση έχει συνήθως πολλά κοινά με την επαναληπτική λύση.
Εδώ αυτό είναι ακριβώς ό, τι η αναδρομική λύση είναι να κάνει.
Η μόνη μεταβολή είναι ότι αντί της εμμέσως χρησιμοποιώντας τη στοίβα, η στοίβα του προγράμματος,
ως το δρόμο σας από την παρακολούθηση του τι κόμβους θα πρέπει ακόμα να επισκεφθείτε,
τώρα θα πρέπει να χρησιμοποιήσετε ρητά μια συνδεδεμένη λίστα.
Και στις δύο περιπτώσεις που η παρακολούθηση του κόμβου τι χρειάζεται ακόμη να επισκεφθεί.
Σε περίπτωση επαναληπτικής είναι απλά πιο εύκολο, διότι μια στοίβα
υλοποιείται για εσάς ως τη στοίβα του προγράμματος.
Παρατηρήστε ότι αυτή η συνδεδεμένη λίστα, είναι μια στοίβα.
Ό, τι ακριβώς τοποθετούνται στη στοίβα
είναι αμέσως τι θα πάμε να τραβήξει από τη στοίβα για να επισκεφθείτε επόμενη.
Είμαστε έξω από το χρόνο, αλλά κάποιες ερωτήσεις;
[Φοιτητών, ακατάληπτο]
[Bowden] Ναι. Έτσι, αν έχουμε συνδεδεμένη λίστα μας,
ρεύμα πρόκειται να επισημάνει αυτόν τον τύπο,
και τώρα είμαστε μόλις προώθηση συνδεδεμένη λίστα μας για να επικεντρωθεί σε αυτόν τον τύπο.
Είμαστε διέρχονται πάνω από τη συνδεδεμένη λίστα σε αυτή τη γραμμή.
Και τότε υποθέτω ότι θα πρέπει να ελευθερώσετε συνδεδεμένη λίστα και τα πράγματα μας
μία φορά πριν επιστρέψει αληθής ή ψευδής, θα πρέπει να
επαναλάβει σε συνδεδεμένη λίστα μας και πάντα εδώ κάτω, υποθέτω,
αν τρέχουσα δικαίωμα δεν είναι ίσο με το προσθέσετε, έτσι και τώρα θέλουμε να ελευθερώσετε
τρέχουσα επειδή, καλά, δεν μπορούμε να ξεχάσουμε εντελώς την λίστα; Ναι.
Έτσι, αυτό είναι που θέλουμε να κάνουμε εδώ.
Πού είναι ο δείκτης;
Cur ήταν τότε - θέλουμε μια λίστα struct * 10 ισούται με λίστα δίπλα.
Δωρεάν κατάλογος, κατάλογος = temp.
Και στην περίπτωση που θα επιστρέψει αλήθεια, χρειαζόμαστε να επαναλάβει
πάνω από το υπόλοιπο των συνδεδεμένων λίστα μας απελευθερώνοντας τα πράγματα.
Το θετικό σχετικά με την αναδρομική λύση είναι απελευθερώνοντας τα πράγματα
ακριβώς σημαίνει βρεθώ factorings από τη στοίβα που θα συμβεί για σας.
Έτσι, έχουμε περάσει από κάτι που είναι σαν 3 γραμμές είναι δύσκολο να σκεφτούμε-για τον κωδικό
σε κάτι που είναι σημαντικά πιο πολλά είναι δύσκολο να σκεφτούμε-για τις γραμμές του κώδικα.
Κάθε άλλες ερωτήσεις;
Εντάξει. Είμαστε καλά. Αντίο!
[CS50.TV]