1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Ενότητα 7] [λιγότερο άνετα]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Πανεπιστήμιο του Χάρβαρντ]

3
00:00:04,890 --> 00:00:07,000
[Αυτό είναι CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Καλώς ήρθατε στο Τμήμα 7.

5
00:00:09,080 --> 00:00:11,330
Χάρη σε τυφώνα Sandy,

6
00:00:11,330 --> 00:00:13,440
αντί να έχουν ένα κανονικό τμήμα αυτής της εβδομάδας,

7
00:00:13,440 --> 00:00:17,650
κάνουμε αυτό με τα πόδια-through, μέσα από την ενότητα των ερωτήσεων.

8
00:00:17,650 --> 00:00:22,830
Πάω να ακολουθεί μαζί με το πρόβλημα Σετ 6 Προδιαγραφές,

9
00:00:22,830 --> 00:00:25,650
και να περάσει από όλες τις ερωτήσεις στο

10
00:00:25,650 --> 00:00:27,770
Ένα τμήμα των ερωτήσεων τμήμα.

11
00:00:27,770 --> 00:00:30,940
Αν υπάρχουν ερωτήσεις,

12
00:00:30,940 --> 00:00:32,960
παρακαλούμε να δημοσιεύσετε σε αυτά CS50 Συζητήστε.

13
00:00:32,960 --> 00:00:35,480
>> Εντάξει. Ας ξεκινήσουμε.

14
00:00:35,480 --> 00:00:40,780
Αυτή τη στιγμή Ψάχνω στη σελίδα 3 των προδιαγραφών Set πρόβλημα.

15
00:00:40,780 --> 00:00:44,110
Εμείς πάμε για την πρώτη αρχίσουμε να μιλάμε για δυαδικά δέντρα

16
00:00:44,110 --> 00:00:47,850
αφού αυτοί έχουν πολύ ενδιαφέρον για το πρόβλημα σύνολο αυτής της εβδομάδας -

17
00:00:47,850 --> 00:00:49,950
η κωδικοποίηση Huffman δέντρο.

18
00:00:49,950 --> 00:00:55,000
Μία από τις πρώτες δομές δεδομένων μιλήσαμε για CS50 ήταν η σειρά.

19
00:00:55,000 --> 00:01:00,170
Θυμηθείτε ότι ένας πίνακας είναι μια ακολουθία των στοιχείων -

20
00:01:00,170 --> 00:01:04,019
όλα του ίδιου τύπου - αποθηκεύονται δίπλα στο άλλο στη μνήμη.

21
00:01:04,019 --> 00:01:14,420
Αν έχω έναν πίνακα ακεραίων ότι μπορώ να βγάλω τη χρήση αυτής κουτιά-ακέραιοι αριθμοί-στυλ -

22
00:01:14,420 --> 00:01:20,290
Ας πούμε ότι έχω 5 στο πρώτο πλαίσιο, έχω 7 στο δεύτερο,

23
00:01:20,290 --> 00:01:27,760
τότε έχω 8, 10, και 20 στο τελικό πλαίσιο.

24
00:01:27,760 --> 00:01:33,000
Θυμηθείτε, οι δύο πραγματικά καλά πράγματα σχετικά με αυτό το φάσμα

25
00:01:33,000 --> 00:01:38,800
είναι ότι έχουμε αυτό το σταθερό χρόνο πρόσβαση σε οποιοδήποτε συγκεκριμένο στοιχείο

26
00:01:38,800 --> 00:01:40,500
 στον πίνακα, αν γνωρίζουμε δείκτης της.

27
00:01:40,500 --> 00:01:44,670
Για παράδειγμα, αν θέλετε να πάρετε το τρίτο στοιχείο του πίνακα -

28
00:01:44,670 --> 00:01:47,870
στο δείκτη 2 χρησιμοποιώντας μηδενική βάση μας σύστημα ευρετηρίασης -

29
00:01:47,870 --> 00:01:52,220
I κυριολεκτικά ακριβώς πρέπει να κάνετε ένα απλό μαθηματικό υπολογισμό,

30
00:01:52,220 --> 00:01:56,170
hop σε αυτή τη θέση στη συστοιχία,

31
00:01:56,170 --> 00:01:57,840
τραβήξτε προς τα έξω τα 8 που είναι αποθηκευμένα εκεί,

32
00:01:57,840 --> 00:01:59,260
και είμαι καλό να πάει.

33
00:01:59,260 --> 00:02:03,350
>> Ένα από τα κακά πράγματα για αυτό το array - για την οποία μιλήσαμε

34
00:02:03,350 --> 00:02:05,010
όταν συζητήσαμε συνδεδεμένες λίστες -

35
00:02:05,010 --> 00:02:09,120
είναι ότι αν θέλετε να εισάγετε ένα στοιχείο σε αυτήν την σειρά,

36
00:02:09,120 --> 00:02:11,090
Πάω να χρειαστεί να κάνετε κάποια αλλαγή γύρω.

37
00:02:11,090 --> 00:02:12,940
Για παράδειγμα, αυτή η συστοιχία εδώ

38
00:02:12,940 --> 00:02:16,850
είναι σε ταξινομημένη σειρά - ταξινομημένο σε αύξουσα σειρά -

39
00:02:16,850 --> 00:02:19,440
5, στη συνέχεια 7, στη συνέχεια 8, στη συνέχεια 10, και στη συνέχεια 20 -

40
00:02:19,440 --> 00:02:23,100
αλλά αν θέλετε να εισάγετε τον αριθμό 9 σε αυτό το φάσμα,

41
00:02:23,100 --> 00:02:27,460
Πάω να πρέπει να αλλάξει κάποια από τα στοιχεία για να κάνει χώρο.

42
00:02:27,460 --> 00:02:30,440
Μπορούμε να αντλήσουμε από αυτό εδώ.

43
00:02:30,440 --> 00:02:35,650
Πάω να χρειαστεί να μετακινήσετε το 5, το 7, και στη συνέχεια τα 8?

44
00:02:35,650 --> 00:02:38,720
δημιουργήσετε ένα χάσμα όπου μπορώ να βάλω το 9,

45
00:02:38,720 --> 00:02:45,910
και στη συνέχεια το 10 και το 20 μπορεί να πάει προς τα δεξιά του 9.

46
00:02:45,910 --> 00:02:49,450
Αυτό είναι το είδος του πόνου, διότι στην χειρότερη περίπτωση -

47
00:02:49,450 --> 00:02:54,350
όταν είμαστε να χρειάζεται να εισάγετε είτε στην αρχή ή στο τέλος

48
00:02:54,350 --> 00:02:56,040
της συστοιχίας, ανάλογα με το πώς είμαστε μετατόπιση -

49
00:02:56,040 --> 00:02:58,850
θα μπορούσαμε να καταλήξετε να πρέπει να μεταφερθεί το σύνολο των στοιχείων

50
00:02:58,850 --> 00:03:00,750
ότι αυτή τη στιγμή αποθήκευση στη συστοιχία.

51
00:03:00,750 --> 00:03:03,810
>> Έτσι, ό, τι ήταν ο τρόπος γύρω από αυτό;

52
00:03:03,810 --> 00:03:09,260
Ο τρόπος γύρω από αυτό ήταν να πάει σε συνδεδεμένη λίστα, η μέθοδός μας, όπου -

53
00:03:09,260 --> 00:03:19,820
αντί για την αποθήκευση των στοιχείων 5, 7, 8, 10, και 20 όλα δίπλα στο άλλο στη μνήμη -

54
00:03:19,820 --> 00:03:25,630
αυτό που έκανε ήταν αντί να αποθηκεύσει το είδος του όπου θέλαμε να τις αποθηκεύσετε

55
00:03:25,630 --> 00:03:32,470
σε αυτές τις συνδεδεμένες-κατάλογος κόμβων που είμαι από τη σύνταξη, εδώ το είδος των ad hoc.

56
00:03:32,470 --> 00:03:42,060
Και τότε θα συνδέονται μεταξύ τους με τη χρήση αυτών των επόμενοι δείκτες.

57
00:03:42,060 --> 00:03:44,370
Ι μπορεί να έχει ένα δείκτη από 5 στο 7,

58
00:03:44,370 --> 00:03:46,420
ένας δείκτης από το 7 στο 8,

59
00:03:46,420 --> 00:03:47,770
ένας δείκτης από το 8 στο 10,

60
00:03:47,770 --> 00:03:51,220
και τέλος, ένα δείκτη από το 10 στο 20,

61
00:03:51,220 --> 00:03:54,880
και στη συνέχεια ένα κενό δείκτη του 20 δείχνει ότι δεν υπάρχει τίποτα αριστερά.

62
00:03:54,880 --> 00:03:59,690
Το trade-off που έχουμε εδώ

63
00:03:59,690 --> 00:04:05,360
είναι ότι τώρα, αν θέλουμε να εισάγετε τον αριθμό 9 σε ταξινομημένη λίστα μας,

64
00:04:05,360 --> 00:04:08,270
το μόνο που έχουμε να κάνουμε είναι να δημιουργήσουμε ένα νέο κόμβο με 9,

65
00:04:08,270 --> 00:04:12,290
σύρμα μέχρι να το επισημάνω στον κατάλληλο τόπο,

66
00:04:12,290 --> 00:04:20,630
και στη συνέχεια εκ νέου το καλώδιο 8 στο σημείο κάτω στο 9.

67
00:04:20,630 --> 00:04:25,660
Αυτό είναι αρκετά γρήγορος, με την προϋπόθεση ξέρουμε ακριβώς πού θέλετε να εισαγάγετε το 9.

68
00:04:25,660 --> 00:04:32,610
Αλλά το trade-off σε αντάλλαγμα για αυτό είναι ότι έχουμε χάσει πλέον τη συνεχή χρόνο πρόσβασης

69
00:04:32,610 --> 00:04:36,230
σε οποιοδήποτε συγκεκριμένο στοιχείο σε δομή δεδομένων μας.

70
00:04:36,230 --> 00:04:40,950
Για παράδειγμα, αν θέλετε να βρείτε το τέταρτο στοιχείο αυτής της συνδεδεμένης λίστας,

71
00:04:40,950 --> 00:04:43,510
Πάω να πρέπει να ξεκινήσει από την αρχή της λίστας

72
00:04:43,510 --> 00:04:48,930
και το έργο το δρόμο μου μέσω του κόμβου καταμέτρηση-με-κόμβο μέχρι να βρω το τέταρτο.

73
00:04:48,930 --> 00:04:55,870
>> Για να πάρει την καλύτερη απόδοση από ό, τι την πρόσβαση σε συνδεδεμένη λίστα -

74
00:04:55,870 --> 00:04:59,360
αλλά διατηρούν, επίσης, μερικά από τα οφέλη που είχαμε

75
00:04:59,360 --> 00:05:01,800
όσον αφορά την εισαγωγή χρόνο από μια συνδεδεμένη λίστα -

76
00:05:01,800 --> 00:05:05,750
ένα δυαδικό δέντρο θα χρειαστεί να χρησιμοποιήσετε λίγο περισσότερη μνήμη.

77
00:05:05,750 --> 00:05:11,460
Συγκεκριμένα, αντί απλά να έχουν ένα δείκτη σε ένα δυαδικό δέντρο κόμβο -

78
00:05:11,460 --> 00:05:13,350
όπως και η συνδεδεμένη λίστα-κόμβος κάνει -

79
00:05:13,350 --> 00:05:16,950
θα πάμε να προσθέσετε ένα δεύτερο δείκτη στο δυαδικό κόμβο του δένδρου.

80
00:05:16,950 --> 00:05:19,950
Αντί έχοντας μόνο ένα δείκτη προς την επόμενη στοιχείο,

81
00:05:19,950 --> 00:05:24,420
θα πάμε να έχουν ένα δείκτη σε ένα παιδί αριστερά και δεξιά ένα παιδί.

82
00:05:24,420 --> 00:05:26,560
>> Ας συντάξει μια εικόνα για να δείτε τι που πραγματικά μοιάζει.

83
00:05:26,560 --> 00:05:31,350
Και πάλι, Πάω να χρησιμοποιήσετε αυτά τα κουτιά και τα βέλη.

84
00:05:31,350 --> 00:05:37,150
Ένα δυαδικό δέντρο κόμβος θα ξεκινήσει με ένα απλό κουτί.

85
00:05:37,150 --> 00:05:40,940
Είναι πρόκειται να έχουν ένα χώρο για την αξία,

86
00:05:40,940 --> 00:05:47,280
και στη συνέχεια, αυτό είναι, επίσης, πρόκειται να έχουν ένα χώρο για το αριστερό παιδί και το δικαίωμα του παιδιού.

87
00:05:47,280 --> 00:05:49,280
Πάω να τους στιγματίσει εδώ.

88
00:05:49,280 --> 00:05:57,560
Εμείς πάμε για να έχουν το αριστερό παιδί, και στη συνέχεια θα πάμε να έχουν το δικαίωμα του παιδιού.

89
00:05:57,560 --> 00:05:59,920
Υπάρχουν πολλοί διαφορετικοί τρόποι για να γίνει αυτό.

90
00:05:59,920 --> 00:06:02,050
Μερικές φορές, για το διάστημα και την ευκολία,

91
00:06:02,050 --> 00:06:06,460
Θα επιστήσω την πραγματικότητα όπως κάνω εδώ στο κάτω μέρος

92
00:06:06,460 --> 00:06:10,910
όπου Πάω να έχουν την τιμή στην κορυφή,

93
00:06:10,910 --> 00:06:14,060
και στη συνέχεια το δικαίωμα των παιδιών στο κάτω δεξιά,

94
00:06:14,060 --> 00:06:16,060
και το αριστερό παιδί στο κάτω-αριστερά.

95
00:06:16,060 --> 00:06:20,250
Πηγαίνοντας πίσω σε αυτήν την κορυφή διάγραμμα,

96
00:06:20,250 --> 00:06:22,560
έχουμε την τιμή στην κορυφή,

97
00:06:22,560 --> 00:06:25,560
τότε έχουμε το αριστερό παιδί-δείκτη, και τότε θα έχουμε το δικαίωμα-παιδί δείκτη.

98
00:06:25,560 --> 00:06:30,110
>> Της συγγραφής υποχρεώσεων πρόβλημα,

99
00:06:30,110 --> 00:06:33,110
μιλάμε για την κατάρτιση ενός κόμβου που έχει μια αξία 7,

100
00:06:33,110 --> 00:06:39,750
και στη συνέχεια, ένα αριστερό παιδί δείκτη που είναι άκυρη, καθώς και το δικαίωμα του παιδιού-δείκτη που είναι null.

101
00:06:39,750 --> 00:06:46,040
Μπορούμε να γράψουμε είτε NULL κεφαλαίου στο χώρο για

102
00:06:46,040 --> 00:06:51,610
τόσο το αριστερό παιδί και το δικαίωμα του παιδιού, ή μπορούμε να βγάλουμε αυτό το διαγώνια κάθετο

103
00:06:51,610 --> 00:06:53,750
μέσω καθενός από τα κουτιά για να δείξει ότι είναι άκυρη.

104
00:06:53,750 --> 00:06:57,560
Πάω να το κάνω αυτό μόνο και μόνο επειδή αυτό είναι απλούστερο.

105
00:06:57,560 --> 00:07:03,700
Αυτό που βλέπετε εδώ είναι δύο τρόποι για να διαγραμμάτων ένα πολύ απλό κόμβο του δένδρου δυαδικό

106
00:07:03,700 --> 00:07:07,960
όπου έχουμε την τιμή 7 και null δείκτες παιδί.

107
00:07:07,960 --> 00:07:15,220
>> Το δεύτερο μέρος των συνομιλιών τις προδιαγραφές μας για το πώς συνδέονται με τους καταλόγους -

108
00:07:15,220 --> 00:07:18,270
Να θυμάστε, είχαμε μόνο να κρατήσουμε την πρώτη στοιχείο σε μια λίστα

109
00:07:18,270 --> 00:07:20,270
για να θυμούνται ολόκληρη τη λίστα -

110
00:07:20,270 --> 00:07:26,140
και επίσης, με ένα δυαδικό δέντρο, δεν έχουμε παρά να κρατήσει σε ένα δείκτη στο δέντρο

111
00:07:26,140 --> 00:07:31,120
προκειμένου να διατηρήσει τον έλεγχο καθ 'όλη τη δομή δεδομένων.

112
00:07:31,120 --> 00:07:36,150
Αυτό το ειδικό στοιχείο του δέντρου ονομάζεται κόμβο ρίζα του δένδρου.

113
00:07:36,150 --> 00:07:43,360
Για παράδειγμα, εάν αυτό ένας κόμβος - αυτός ο κόμβος περιέχει την τιμή 7

114
00:07:43,360 --> 00:07:45,500
με μηδενική αριστερό και το δεξί παιδί-δείκτες -

115
00:07:45,500 --> 00:07:47,360
ήταν η μόνη αξία στο δέντρο μας,

116
00:07:47,360 --> 00:07:50,390
τότε αυτό θα ήταν κόμβος ρίζα μας.

117
00:07:50,390 --> 00:07:52,240
Είναι η αρχή του δέντρου μας.

118
00:07:52,240 --> 00:07:58,530
Μπορούμε να δούμε αυτό το λίγο πιο καθαρά τη στιγμή που θα αρχίσετε να προσθέτετε περισσότερους κόμβους στο δέντρο μας.

119
00:07:58,530 --> 00:08:01,510
Επιτρέψτε μου να σηκώσει μια νέα σελίδα.

120
00:08:01,510 --> 00:08:05,000
>> Τώρα θα πάμε να σχεδιάσετε ένα δέντρο που έχει 7 στη ρίζα,

121
00:08:05,000 --> 00:08:10,920
και 3 στο εσωτερικό του αριστερού παιδιού, και 9 στο εσωτερικό του δεξιού παιδιού.

122
00:08:10,920 --> 00:08:13,500
Και πάλι, αυτό είναι αρκετά απλή.

123
00:08:13,500 --> 00:08:26,510
Έχουμε 7, σχεδιάστε ένα κόμβο για την 3, ένας κόμβος για 9,

124
00:08:26,510 --> 00:08:32,150
και είμαι πρόκειται να θέσει το αριστερό παιδί του δείκτη 7 για να επισημάνω στον κόμβο που περιέχει 3,

125
00:08:32,150 --> 00:08:37,850
και το δεξιό δείκτη παιδί του κόμβου που περιέχει 7 με τον κόμβο που περιέχει 9.

126
00:08:37,850 --> 00:08:42,419
Τώρα, από τις 3 και 9 δεν έχουν παιδιά,

127
00:08:42,419 --> 00:08:48,500
θα πάμε να θέσει σε όλους τους δείκτες παιδί τους να είναι μηδενική.

128
00:08:48,500 --> 00:08:56,060
Εδώ, η ρίζα του δέντρου μας αντιστοιχεί στην κόμβο να περιέχει τον αριθμό 7.

129
00:08:56,060 --> 00:09:02,440
Μπορείτε να δείτε ότι αν το μόνο που έχουμε είναι ένας δείκτης σε αυτόν τον κόμβο ρίζα,

130
00:09:02,440 --> 00:09:07,330
τότε μπορούμε να περπατήσετε μέσα από δέντρο μας και να έχουν πρόσβαση και τα δύο κόμβους παιδί -

131
00:09:07,330 --> 00:09:10,630
τόσο 3 και 9.

132
00:09:10,630 --> 00:09:14,820
Δεν χρειάζεται να διατηρεί δείκτες σε κάθε κόμβο στο δέντρο.

133
00:09:14,820 --> 00:09:22,080
Εντάξει. Τώρα θα πάμε να προσθέσετε ένα άλλο κόμβο σε αυτό το διάγραμμα.

134
00:09:22,080 --> 00:09:25,370
Εμείς πάμε για να προσθέσετε ένα κόμβο που περιέχει 6,

135
00:09:25,370 --> 00:09:34,140
και θα πάμε για να προσθέσετε αυτό το δικαίωμα το παιδί του κόμβου που περιέχει 3.

136
00:09:34,140 --> 00:09:41,850
Για να γίνει αυτό, θα πάω να διαγράψετε αυτό το κενό δείκτη στο 3-κόμβος

137
00:09:41,850 --> 00:09:47,750
και το σύρμα μέχρι να επισημάνω στον κόμβο που περιέχει 6. Εντάξει.

138
00:09:47,750 --> 00:09:53,800
>> Σε αυτό το σημείο, ας πάμε σε ένα μικρό κομμάτι της ορολογίας.

139
00:09:53,800 --> 00:09:58,230
Για να ξεκινήσετε, το λόγο ότι αυτό ονομάζεται ένα δυαδικό δέντρο, ιδίως

140
00:09:58,230 --> 00:10:00,460
είναι ότι έχει δύο δείκτες παιδί.

141
00:10:00,460 --> 00:10:06,020
Υπάρχουν και άλλα είδη δέντρων που έχουν περισσότερους δείκτες παιδί.

142
00:10:06,020 --> 00:10:10,930
Ειδικότερα, κάνατε μια «δοκιμάσετε» σε Σετ Πρόβλημα 5.

143
00:10:10,930 --> 00:10:19,310
Θα παρατηρήσετε ότι στην εν λόγω προσπάθεια, που είχε 27 διαφορετικούς δείκτες σε διαφορετικά παιδιά -

144
00:10:19,310 --> 00:10:22,410
μία για κάθε ένα από τα 26 γράμματα του αγγλικού αλφαβήτου,

145
00:10:22,410 --> 00:10:25,410
και στη συνέχεια το 27ο για την απόστροφο -

146
00:10:25,410 --> 00:10:28,900
έτσι, αυτό είναι παρόμοιο με το είδος του δέντρου.

147
00:10:28,900 --> 00:10:34,070
Αλλά εδώ, από το δυαδικό, έχουμε μόνο δύο δείκτες παιδί.

148
00:10:34,070 --> 00:10:37,880
>> Εκτός από αυτό τον κόμβο ρίζα την οποία μιλήσαμε,

149
00:10:37,880 --> 00:10:41,470
έχουμε επίσης ρίχνουν γύρω από αυτόν τον όρο «παιδί».

150
00:10:41,470 --> 00:10:44,470
Τι σημαίνει αυτό για έναν κόμβο να είναι ένα παιδί ενός άλλου κόμβου;

151
00:10:44,470 --> 00:10:54,060
Αυτό σημαίνει κυριολεκτικά ότι ένας κόμβος παιδί είναι ένα παιδί ενός άλλου κόμβου

152
00:10:54,060 --> 00:10:58,760
αν αυτό το άλλο κόμβος έχει ένα παιδί από δείκτες που να του επισημάνω σε αυτόν τον κόμβο.

153
00:10:58,760 --> 00:11:01,230
Για να το θέσουμε σε πιο συγκεκριμένους όρους,

154
00:11:01,230 --> 00:11:11,170
εάν 3 δείχνεται από ένα από τους δείκτες του παιδιού 7, τότε 3 είναι ένα παιδί 7.

155
00:11:11,170 --> 00:11:14,510
Αν επρόκειτο να καταλάβουμε ποια είναι τα παιδιά από 7 -

156
00:11:14,510 --> 00:11:18,510
καλά, βλέπουμε ότι 7 έχει ένα δείκτη προς 3 και ένα δείκτη προς 9,

157
00:11:18,510 --> 00:11:22,190
έτσι 9 και 3 είναι τα παιδιά της 7.

158
00:11:22,190 --> 00:11:26,650
Εννέα δεν έχει παιδιά, επειδή δείκτες παιδί του είναι μηδενική,

159
00:11:26,650 --> 00:11:30,940
και 3 έχει μόνο ένα παιδί, 6.

160
00:11:30,940 --> 00:11:37,430
Έξι έχει επίσης κανένα παιδί γιατί και οι δύο δείκτες του είναι μηδενική, η οποία θα συντάξει αυτή τη στιγμή.

161
00:11:37,430 --> 00:11:45,010
>> Επιπλέον, μπορούμε επίσης να μιλήσουμε για τους γονείς ενός συγκεκριμένου κόμβου,

162
00:11:45,010 --> 00:11:51,100
και αυτό είναι, όπως θα περίμενε κανείς, το αντίθετο αυτής της περιγραφής του παιδιού.

163
00:11:51,100 --> 00:11:58,620
Κάθε κόμβος έχει μόνο ο ένας γονέας - αντί για δύο, όπως θα περίμενε κανείς με τους ανθρώπους.

164
00:11:58,620 --> 00:12:03,390
Για παράδειγμα, η μητρική 3 είναι 7.

165
00:12:03,390 --> 00:12:10,800
Η μητρική 9 είναι επίσης 7, και η μητρική της 6 είναι 3. Όχι πολύ σε αυτό.

166
00:12:10,800 --> 00:12:15,720
Έχουμε, επίσης, τους όρους για να μιλήσουμε για τους παππούδες και τα εγγόνια,

167
00:12:15,720 --> 00:12:18,210
και γενικότερα μιλάμε για τους προγόνους

168
00:12:18,210 --> 00:12:20,960
και οι απόγονοι ενός συγκεκριμένου κόμβου.

169
00:12:20,960 --> 00:12:25,710
Ο πρόγονος ενός κόμβου - ή προγόνους, μάλλον, ενός κόμβου -

170
00:12:25,710 --> 00:12:32,730
είναι όλα από τους κόμβους που βρίσκονται στο μονοπάτι από τη ρίζα σε αυτόν τον κόμβο.

171
00:12:32,730 --> 00:12:36,640
Για παράδειγμα, αν ψάχνω στον κόμβο 6,

172
00:12:36,640 --> 00:12:46,430
τότε οι πρόγονοι πρόκειται να είναι τόσο 3 και 7.

173
00:12:46,430 --> 00:12:55,310
Οι πρόγονοι του 9, για παράδειγμα, είναι - αν ψάχνω στον κόμβο 9 -

174
00:12:55,310 --> 00:12:59,990
τότε ο πρόγονος του 9 είναι μόλις 7.

175
00:12:59,990 --> 00:13:01,940
Και απόγονοι είναι ακριβώς το αντίθετο.

176
00:13:01,940 --> 00:13:05,430
Αν θέλετε να δείτε όλα τα απόγονοι των 7,

177
00:13:05,430 --> 00:13:11,020
τότε θα πρέπει να εξετάσουμε όλες τις κόμβους κάτω από αυτό.

178
00:13:11,020 --> 00:13:16,950
Έτσι, έχω 3, 9, και 6, όλα τα ως απόγονοι του 7.

179
00:13:16,950 --> 00:13:24,170
>> Η τελική όρο ότι θα μιλήσουμε για αυτό είναι η έννοια του να είσαι αδελφός.

180
00:13:24,170 --> 00:13:27,980
Τα αδέλφια - το είδος της μετά μαζί με αυτούς τους όρους οικογένεια -

181
00:13:27,980 --> 00:13:33,150
είναι κόμβοι που βρίσκονται στο ίδιο επίπεδο στο δέντρο.

182
00:13:33,150 --> 00:13:42,230
Έτσι, 3 και 9 είναι αδέλφια επειδή είναι στο ίδιο επίπεδο στο δέντρο.

183
00:13:42,230 --> 00:13:46,190
Και οι δύο έχουν την ίδια μητρική, 7.

184
00:13:46,190 --> 00:13:51,400
Το 6 δεν έχει αδέλφια, επειδή 9 δεν έχουν παιδιά.

185
00:13:51,400 --> 00:13:55,540
Και 7 δεν έχει καμία αδέλφια επειδή είναι η ρίζα του δέντρου μας,

186
00:13:55,540 --> 00:13:59,010
και υπάρχει πάντα μόνο 1 root.

187
00:13:59,010 --> 00:14:02,260
Για να έχουμε 7 αδέρφια εκεί θα πρέπει να είναι ένας κόμβος πάνω 7.

188
00:14:02,260 --> 00:14:07,480
Θα πρέπει να υπάρξει ένας γονέας 7, στην οποία περίπτωση 7 δεν θα είναι πλέον η ρίζα του δένδρου.

189
00:14:07,480 --> 00:14:10,480
Στη συνέχεια, η νέα μητρική 7 θα πρέπει επίσης να έχουν ένα παιδί,

190
00:14:10,480 --> 00:14:16,480
και ότι το παιδί θα ήταν τότε ο αδερφός του 7.

191
00:14:16,480 --> 00:14:21,040
>> Εντάξει. Προχωρώντας.

192
00:14:21,040 --> 00:14:24,930
Όταν ξεκινήσαμε τη συζήτησή μας από δυαδικά δένδρα,

193
00:14:24,930 --> 00:14:28,790
μιλήσαμε για το πώς επρόκειτο να τους χρησιμοποιήσει για να

194
00:14:28,790 --> 00:14:32,800
αποκτήσουν ένα πλεονέκτημα σε σχέση με τις δύο συστοιχίες και συνδεδεμένες λίστες.

195
00:14:32,800 --> 00:14:37,220
Και ο τρόπος που θα πάμε να το κάνουμε αυτό είναι με αυτό το ακίνητο παραγγελία.

196
00:14:37,220 --> 00:14:41,080
Εμείς λέμε ότι ένα δέντρο δυαδική διέταξε, σύμφωνα με τις προδιαγραφές,

197
00:14:41,080 --> 00:14:45,740
αν για κάθε κόμβο στο δέντρο μας, όλους τους απογόνους του για την αριστερά -

198
00:14:45,740 --> 00:14:48,670
το αριστερό παιδί και όλους τους απογόνους του αριστερού παιδιού -

199
00:14:48,670 --> 00:14:54,510
έχουν μικρότερες τιμές, και όλων των κόμβων για το δικαίωμα -

200
00:14:54,510 --> 00:14:57,770
το δικαίωμα του παιδιού και όλους τους απογόνους του δικαιώματος του παιδιού -

201
00:14:57,770 --> 00:15:02,800
κόμβοι έχουν μεγαλύτερη από την αξία του τρέχοντος κόμβου ότι ψάχνουμε σε.

202
00:15:02,800 --> 00:15:07,850
Ακριβώς για λόγους απλότητας, θα πάμε να υποθέσουμε ότι δεν υπάρχουν διπλοί κόμβοι στο δέντρο μας.

203
00:15:07,850 --> 00:15:11,180
Για παράδειγμα, σε αυτό το δέντρο εμείς δεν πρόκειται να ασχοληθεί με την υπόθεση

204
00:15:11,180 --> 00:15:13,680
όπου έχουμε την τιμή 7 στη ρίζα

205
00:15:13,680 --> 00:15:16,720
 και στη συνέχεια έχουμε επίσης την αξία 7 αλλού στο δέντρο.

206
00:15:16,720 --> 00:15:24,390
Σε αυτή την περίπτωση, θα παρατηρήσετε ότι αυτό το δέντρο είναι πράγματι παραγγείλει.

207
00:15:24,390 --> 00:15:26,510
Έχουμε την τιμή 7 στη ρίζα.

208
00:15:26,510 --> 00:15:29,720
Τα πάντα στα αριστερά της 7 -

209
00:15:29,720 --> 00:15:35,310
αν μπορώ να αναιρέσω όλα από αυτά τα μικρά σημάδια εδώ -

210
00:15:35,310 --> 00:15:40,450
πάντα στα αριστερά της 7 - το 3 και το 6 -

211
00:15:40,450 --> 00:15:49,410
οι αξίες αυτές είναι και οι δύο λιγότερο από 7, και τα πάντα προς τα δεξιά - το οποίο είναι ακριβώς αυτό 9 -

212
00:15:49,410 --> 00:15:53,450
είναι μεγαλύτερο από 7.

213
00:15:53,450 --> 00:15:58,650
>> Αυτή δεν είναι η μόνη εντολή δένδρο περιέχει αυτές τις τιμές,

214
00:15:58,650 --> 00:16:03,120
αλλά ας συντάξει μερικά περισσότερα από αυτά.

215
00:16:03,120 --> 00:16:05,030
Υπάρχει πραγματικά ένα σωρό τρόπους με τους οποίους μπορούμε να το κάνουμε αυτό.

216
00:16:05,030 --> 00:16:09,380
Πάω να χρησιμοποιήσετε μια συντόμευση μόνο για να κρατήσει τα πράγματα απλά, όπου -

217
00:16:09,380 --> 00:16:11,520
αντί να οργανώνει το σύνολο κουτιά-και-βέλη -

218
00:16:11,520 --> 00:16:14,220
Είμαι ακριβώς πρόκειται να συντάξει τους αριθμούς και να προσθέσετε βέλη σύνδεσή τους.

219
00:16:14,220 --> 00:16:22,920
Για να ξεκινήσετε, θα γράφουμε μόνο πρωτότυπο δέντρο μας και πάλι, όπου είχαμε 7, και στη συνέχεια 3,

220
00:16:22,920 --> 00:16:25,590
και στη συνέχεια 3 επεσήμανε πίσω προς τα δεξιά στο 6,

221
00:16:25,590 --> 00:16:30,890
και 7 είχαν το δικαίωμα του παιδιού που ήταν 9.

222
00:16:30,890 --> 00:16:33,860
Εντάξει. Τι είναι ένας άλλος τρόπος που θα μπορούσε να γράψει αυτό το δέντρο;

223
00:16:33,860 --> 00:16:38,800
Αντί να έχουμε 3 είναι το αριστερό παιδί 7,

224
00:16:38,800 --> 00:16:41,360
θα μπορούσαμε επίσης να έχουν το 6 είναι το αριστερό παιδί 7,

225
00:16:41,360 --> 00:16:44,470
και κατόπιν 3 είναι το αριστερό παιδί του 6.

226
00:16:44,470 --> 00:16:48,520
Αυτό θα μοιάζει με αυτό το δέντρο εδώ όπου έχω 7,

227
00:16:48,520 --> 00:16:57,860
τότε 6, στη συνέχεια 3, και 9 σχετικά με το δικαίωμα.

228
00:16:57,860 --> 00:17:01,490
Επίσης, δεν πρέπει να έχουν 7 ως κόμβος ρίζα μας.

229
00:17:01,490 --> 00:17:03,860
Θα μπορούσε επίσης να έχει 6 ως κόμβος ρίζα μας.

230
00:17:03,860 --> 00:17:06,470
Τι θα που μοιάζουν;

231
00:17:06,470 --> 00:17:09,230
Αν θα πάμε για να διατηρηθεί αυτή η ιδιότητα διέταξε,

232
00:17:09,230 --> 00:17:12,970
πάντα στα αριστερά της 6 πρέπει να είναι μικρότερη από αυτήν.

233
00:17:12,970 --> 00:17:16,540
Υπάρχει μόνο μία δυνατότητα, και αυτό είναι 3.

234
00:17:16,540 --> 00:17:19,869
Στη συνέχεια, όμως, όπως το δικαίωμα του παιδιού 6, έχουμε δύο δυνατότητες.

235
00:17:19,869 --> 00:17:25,380
Πρώτον, θα μπορούσαμε να έχουμε την 7 και στη συνέχεια το 9,

236
00:17:25,380 --> 00:17:28,850
ή θα μπορούσαμε να αντλήσει - σαν να είμαι έτοιμος να κάνω εδώ -

237
00:17:28,850 --> 00:17:34,790
όπου έχουμε το 9 και το δικαίωμα του παιδιού 6,

238
00:17:34,790 --> 00:17:39,050
και στη συνέχεια το 7 ως το αριστερό παιδί του 9.

239
00:17:39,050 --> 00:17:44,240
>> Τώρα, 7 και 6 δεν είναι οι μόνες δυνατές τιμές για τη ρίζα.

240
00:17:44,240 --> 00:17:50,200
Θα μπορούσαμε επίσης να έχουν 3 είναι στη ρίζα.

241
00:17:50,200 --> 00:17:52,240
Τι θα συμβεί αν 3 είναι στη ρίζα;

242
00:17:52,240 --> 00:17:54,390
Εδώ, τα πράγματα παίρνουν λίγο ενδιαφέρον.

243
00:17:54,390 --> 00:17:58,440
Τρεις δεν έχει οποιεσδήποτε τιμές που είναι λιγότερο από αυτό,

244
00:17:58,440 --> 00:18:02,070
έτσι ώστε ολόκληρη αριστερή πλευρά του δέντρου είναι ακριβώς πρόκειται να είναι μηδενική.

245
00:18:02,070 --> 00:18:03,230
Δεν πρόκειται να είναι κάτι εκεί.

246
00:18:03,230 --> 00:18:07,220
Στα δεξιά, θα μπορούσα να απαριθμήσω τα πράγματα σε αύξουσα σειρά.

247
00:18:07,220 --> 00:18:15,530
Θα μπορούσαμε να έχουμε 3, έπειτα 6, στη συνέχεια 7, 9 στη συνέχεια.

248
00:18:15,530 --> 00:18:26,710
Ή, θα μπορούσαμε να κάνουμε 3, στη συνέχεια, 6, στη συνέχεια, 9, στη συνέχεια, 7.

249
00:18:26,710 --> 00:18:35,020
Ή, θα μπορούσαμε να κάνουμε 3, στη συνέχεια, 7, μετά 6, μετά 9.

250
00:18:35,020 --> 00:18:40,950
Ή, 3, 7 - στην πραγματικότητα δεν είναι, δεν μπορούμε να κάνουμε πια ένα 7.

251
00:18:40,950 --> 00:18:43,330
Αυτό είναι ένα πράγμα που μας εκεί.

252
00:18:43,330 --> 00:18:54,710
Μπορούμε να κάνουμε 9, και έπειτα από το 9 μπορούμε να κάνουμε 6 και 7 στη συνέχεια.

253
00:18:54,710 --> 00:19:06,980
Ή, μπορούμε να κάνουμε 3, και στη συνέχεια 9, στη συνέχεια 7, και στη συνέχεια 6.

254
00:19:06,980 --> 00:19:12,490
>> Ένα πράγμα που πρέπει να επιστήσω την προσοχή σας είναι εδώ

255
00:19:12,490 --> 00:19:14,510
ότι αυτά τα δέντρα είναι λίγο περίεργο το μέλλον.

256
00:19:14,510 --> 00:19:17,840
Συγκεκριμένα, αν κοιτάξουμε τις 4 δέντρα στη δεξιά πλευρά -

257
00:19:17,840 --> 00:19:20,930
Θα τους κύκλο, εδώ -

258
00:19:20,930 --> 00:19:28,410
αυτά τα δέντρα φαίνονται σχεδόν ακριβώς όπως μια συνδεδεμένη λίστα.

259
00:19:28,410 --> 00:19:32,670
Κάθε κόμβος έχει μόνο ένα παιδί,

260
00:19:32,670 --> 00:19:38,950
και έτσι δεν έχουμε κανένα από αυτό το δέντρο-όπως δομή που βλέπουμε, για παράδειγμα,

261
00:19:38,950 --> 00:19:44,720
 σε αυτό μοναχικός ένα δέντρο εδώ στο αριστερό κάτω μέρος.

262
00:19:44,720 --> 00:19:52,490
Αυτά τα δέντρα που ονομάζεται στην πραγματικότητα εκφυλιστεί δυαδικά δένδρα,

263
00:19:52,490 --> 00:19:54,170
και θα μιλήσουμε για αυτά περισσότερο στο μέλλον -

264
00:19:54,170 --> 00:19:56,730
ειδικά αν πάτε να πάρετε άλλα μαθήματα επιστήμης των υπολογιστών.

265
00:19:56,730 --> 00:19:59,670
Αυτά τα δέντρα είναι εκφυλισμένες.

266
00:19:59,670 --> 00:20:03,780
Δεν είναι πολύ χρήσιμο, διότι, πράγματι, αυτή η δομή προσφέρεται

267
00:20:03,780 --> 00:20:08,060
 για αναζήτηση φορές παρόμοια με εκείνη μία συνδεδεμένη λίστα.

268
00:20:08,060 --> 00:20:13,050
Δεν έχετε να επωφεληθούν από την επιπλέον μνήμη - αυτό το πρόσθετο δείκτη -

269
00:20:13,050 --> 00:20:18,840
λόγω της δομής μας είναι κακό με αυτόν τον τρόπο.

270
00:20:18,840 --> 00:20:24,700
Αντί να πάει και να σκιαγραφήσει τα δυαδικά δέντρα που έχουν 9 στη ρίζα,

271
00:20:24,700 --> 00:20:27,220
η οποία είναι η τελευταία περίπτωση ότι θα είχαμε,

272
00:20:27,220 --> 00:20:32,380
είμαστε αντ 'αυτού, σε αυτό το σημείο, πρόκειται να μιλήσω λίγο για αυτό άλλος όρος

273
00:20:32,380 --> 00:20:36,150
που χρησιμοποιούμε όταν μιλάμε για δέντρα, το οποίο ονομάζεται ύψος.

274
00:20:36,150 --> 00:20:45,460
>> Το ύψος του δέντρου είναι η απόσταση από τη ρίζα προς το πιο μακρινό κόμβο,

275
00:20:45,460 --> 00:20:48,370
ή μάλλον ο αριθμός του λυκίσκου που θα πρέπει να κάνει για να

276
00:20:48,370 --> 00:20:53,750
ξεκινούν από την ρίζα και στη συνέχεια καταλήγουν στο πιο μακρινό κόμβο στο δέντρο.

277
00:20:53,750 --> 00:20:57,330
Αν κοιτάξουμε μερικά από αυτά τα δέντρα που έχουμε δικαίωμα που εδώ,

278
00:20:57,330 --> 00:21:07,870
μπορούμε να δούμε ότι αν πάρουμε αυτό το δέντρο στην πάνω αριστερή γωνία και θα ξεκινήσει στο 3,

279
00:21:07,870 --> 00:21:14,510
τότε θα πρέπει να κάνει 1 hop για να φτάσουμε στο 6, το δεύτερο hop για να φτάσουμε στην 7,

280
00:21:14,510 --> 00:21:20,560
και ένα τρίτο hop για να φτάσουμε στο 9.

281
00:21:20,560 --> 00:21:26,120
Έτσι, το ύψος αυτού του δένδρου είναι 3.

282
00:21:26,120 --> 00:21:30,640
Μπορούμε να κάνουμε την ίδια άσκηση για τα άλλα δέντρα που περιγράφονται με αυτό το πράσινο,

283
00:21:30,640 --> 00:21:40,100
και βλέπουμε ότι το ύψος όλων αυτών των δέντρων είναι επίσης πράγματι 3.

284
00:21:40,100 --> 00:21:45,230
Αυτό είναι μέρος του τι τους κάνει να εκφυλιστεί -

285
00:21:45,230 --> 00:21:53,750
ότι το ύψος τους είναι ακριβώς κατά ένα μικρότερος από τον αριθμό των κόμβων σε ολόκληρο το δέντρο.

286
00:21:53,750 --> 00:21:58,400
Αν δούμε σε αυτό το άλλο δέντρο που είναι περικυκλωμένη με κόκκινο, από την άλλη πλευρά,

287
00:21:58,400 --> 00:22:03,920
βλέπουμε ότι οι πιο μακρινό κόμβους είναι το 6 και το 9 -

288
00:22:03,920 --> 00:22:06,940
τα φύλλα που είναι οι κόμβοι που δεν έχουν παιδιά.

289
00:22:06,940 --> 00:22:11,760
Έτσι, προκειμένου να πάρει από τον κόμβο ρίζα είτε στο 6 ή το 9,

290
00:22:11,760 --> 00:22:17,840
θα πρέπει να κάνει ένα hop για να φτάσουμε στην 7 και στη συνέχεια μια δεύτερη hop για να φτάσουμε στο 9,

291
00:22:17,840 --> 00:22:21,240
και επίσης, μόνο ένα δεύτερο hop από τις 7 για να φτάσουμε στο 6.

292
00:22:21,240 --> 00:22:29,080
Έτσι, το ύψος του πάνω από αυτό το δέντρο εδώ είναι μόνο 2.

293
00:22:29,080 --> 00:22:35,330
Μπορείτε να πάτε πίσω και να κάνουμε ότι για όλα τα άλλα δέντρα που συζητήθηκε προηγουμένως

294
00:22:35,330 --> 00:22:37,380
αρχίζοντας με το 7 και το 6,

295
00:22:37,480 --> 00:22:42,500
και θα διαπιστώσετε ότι το ύψος όλων αυτών των δέντρων είναι επίσης 2.

296
00:22:42,500 --> 00:22:46,320
>> Ο λόγος που έχουμε μιλήσει για διέταξε δυαδικά δέντρα

297
00:22:46,320 --> 00:22:50,250
και γιατί είναι δροσερό είναι επειδή μπορείτε να πραγματοποιήσετε αναζήτηση από τους

298
00:22:50,250 --> 00:22:53,810
ένα πολύ παρόμοιο τρόπο με την αναζήτηση σε ταξινομημένο πίνακα.

299
00:22:53,810 --> 00:22:58,720
Αυτό είναι που μιλάμε για να πάρει ότι η βελτίωση του χρόνου αναζήτησης

300
00:22:58,720 --> 00:23:02,730
κατά τη διάρκεια της συνδέεται απλή λίστα.

301
00:23:02,730 --> 00:23:05,010
Με μια συνδεδεμένη λίστα - αν θέλετε να βρείτε ένα συγκεκριμένο στοιχείο -

302
00:23:05,010 --> 00:23:07,470
είστε σε καλύτερη πρόκειται να κάνει κάποια γραμμική αναζήτηση

303
00:23:07,470 --> 00:23:10,920
όπου μπορείτε να ξεκινήσετε από την αρχή της λίστας και λυκίσκου ένα-ένα -

304
00:23:10,920 --> 00:23:12,620
έναν κόμβο από έναν κόμβο -

305
00:23:12,620 --> 00:23:16,060
καθ 'όλη τη λίστα μέχρι να βρείτε ό, τι αναζητάτε.

306
00:23:16,060 --> 00:23:19,440
Ότι, αν έχετε ένα δυαδικό δέντρο που είναι αποθηκευμένα σε αυτό το ωραίο σχήμα,

307
00:23:19,440 --> 00:23:23,300
μπορείτε να πάρετε πραγματικά περισσότερο από μια δυαδική αναζήτηση συνεχίζεται

308
00:23:23,300 --> 00:23:25,160
όπου μπορείτε διαίρει και βασίλευε

309
00:23:25,160 --> 00:23:29,490
και αναζήτηση μέσω της κατάλληλης μισο του δένδρου σε κάθε βήμα.

310
00:23:29,490 --> 00:23:32,840
Ας δούμε πώς λειτουργεί.

311
00:23:32,840 --> 00:23:38,850
>> Αν έχουμε - και πάλι, πηγαίνοντας πίσω στην αρχική μας δέντρο -

312
00:23:38,850 --> 00:23:46,710
θα ξεκινήσει στις 7, έχουμε 3 στα αριστερά, 9 στη δεξιά,

313
00:23:46,710 --> 00:23:51,740
και κάτω από το 3 έχουμε το 6.

314
00:23:51,740 --> 00:24:01,880
Αν θέλετε να ψάξετε για τον αριθμό 6 σε αυτό το δέντρο, είχαμε ξεκινήσει από τη ρίζα.

315
00:24:01,880 --> 00:24:08,910
Εμείς θα συγκρίνει την τιμή που ψάχνουμε, ας πούμε 6,

316
00:24:08,910 --> 00:24:12,320
με την τιμή που είναι αποθηκευμένη στον κόμβο που είμαστε σήμερα κοιτάζοντας, 7,

317
00:24:12,320 --> 00:24:21,200
διαπιστώνουμε ότι 6 είναι πράγματι λιγότερο από 7, έτσι θα κινηθεί προς τα αριστερά.

318
00:24:21,200 --> 00:24:25,530
Εάν η τιμή του 6 ήταν μεγαλύτερο από 7, θα είχαμε αντίθετα κινείται προς τα δεξιά.

319
00:24:25,530 --> 00:24:29,770
Επειδή γνωρίζουμε ότι - λόγω της δομής του διέταξε δυαδικού δένδρου μας -

320
00:24:29,770 --> 00:24:33,910
όλες οι τιμές μικρότερες από 7 πρόκειται να αποθηκευτεί προς τα αριστερά του 7,

321
00:24:33,910 --> 00:24:40,520
δεν υπάρχει καμία ανάγκη να ενοχληθεί ακόμη αναζητούν μέσα στη δεξιά πλευρά του δένδρου.

322
00:24:40,520 --> 00:24:43,780
Όταν κινούμαστε προς τα αριστερά και είμαστε τώρα στον κόμβο που περιέχει 3,

323
00:24:43,780 --> 00:24:48,110
μπορούμε να κάνουμε την ίδια σύγκριση και πάλι, όπου συγκρίνουμε το 3 και το 6.

324
00:24:48,110 --> 00:24:52,430
Και διαπιστώνουμε ότι ενώ το 6 - η τιμή που ψάχνουμε - είναι μεγαλύτερη από 3,

325
00:24:52,430 --> 00:24:58,580
μπορούμε να πάμε προς τη δεξιά πλευρά του κόμβου που περιέχει 3.

326
00:24:58,580 --> 00:25:02,670
Δεν υπάρχει αριστερή πλευρά εδώ, γι 'αυτό θα μπορούσε να αγνοηθεί το γεγονός ότι.

327
00:25:02,670 --> 00:25:06,510
Όμως, γνωρίζουμε μόνο ότι, επειδή ψάχνουμε το ίδιο το δέντρο,

328
00:25:06,510 --> 00:25:08,660
και μπορούμε να δούμε ότι το δέντρο δεν έχει παιδιά.

329
00:25:08,660 --> 00:25:13,640
>> Είναι επίσης πολύ εύκολο να αναζητήσετε 6 σε αυτό το δέντρο, αν κάνουμε τους εαυτούς μας ως άνθρωποι,

330
00:25:13,640 --> 00:25:16,890
αλλά ας ακολουθήσει αυτή τη διαδικασία μηχανικά σαν έναν υπολογιστή, θα κάνει

331
00:25:16,890 --> 00:25:18,620
να κατανοήσουμε πραγματικά τον αλγόριθμο.

332
00:25:18,620 --> 00:25:26,200
Σε αυτό το σημείο, είμαστε τώρα ψάχνουν σε έναν κόμβο που περιέχει 6,

333
00:25:26,200 --> 00:25:29,180
και ψάχνουμε για την τιμή 6,

334
00:25:29,180 --> 00:25:31,740
έτσι, πράγματι, έχουμε βρει το κατάλληλο κόμβο.

335
00:25:31,740 --> 00:25:35,070
Βρήκαμε την τιμή 6 σε δέντρο μας, και μπορούμε να σταματήσουμε αναζήτησής μας.

336
00:25:35,070 --> 00:25:37,330
Σε αυτό το σημείο, ανάλογα με το τι συμβαίνει,

337
00:25:37,330 --> 00:25:41,870
μπορούμε να πούμε, ναι, έχουμε βρει την τιμή 6, υπάρχει το δέντρο μας.

338
00:25:41,870 --> 00:25:47,640
Ή, αν σχεδιάζετε να εισάγετε ένα κόμβο ή να κάνει κάτι, μπορούμε να το κάνουμε αυτό σε αυτό το σημείο.

339
00:25:47,640 --> 00:25:53,010
>> Ας κάνουμε ένα ζευγάρι περισσότερες αναζητήσεις μόνο για να δούμε πώς αυτό λειτουργεί.

340
00:25:53,010 --> 00:25:59,390
Ας δούμε τι θα συμβεί εάν επρόκειτο να προσπαθήσουμε και να κοιτάζω προς τα πάνω την τιμή 10.

341
00:25:59,390 --> 00:26:02,970
Αν ήταν να κοιτάζω προς τα πάνω την τιμή 10, θα ξεκινήσει από τη ρίζα.

342
00:26:02,970 --> 00:26:07,070
Θα βλέπατε ότι το 10 είναι μεγαλύτερο από 7, γι 'αυτό θα προχωρήσουμε προς τα δεξιά.

343
00:26:07,070 --> 00:26:13,640
Είχαμε φτάσει στο 9 και συγκρίνετε τις 9 έως τις 10 και βλέπω ότι 9 είναι πράγματι λιγότερο από 10.

344
00:26:13,640 --> 00:26:16,210
Έτσι, και πάλι, εμείς θα προσπαθήσουμε να προχωρήσουμε προς τα δεξιά.

345
00:26:16,210 --> 00:26:20,350
Αλλά σε αυτό το σημείο, θα παρατηρήσετε ότι θα είμαστε σε μηδενική κόμβο.

346
00:26:20,350 --> 00:26:23,080
Δεν υπάρχει τίποτα εκεί. Δεν υπάρχει τίποτα που το 10 θα πρέπει να είναι.

347
00:26:23,080 --> 00:26:29,360
Αυτό είναι όπου μπορούμε να αναφέρουμε αποτυχία - ότι υπάρχει πράγματι όχι 10 στο δέντρο.

348
00:26:29,360 --> 00:26:35,420
Και τέλος, ας περάσουν από την περίπτωση κατά την οποία προσπαθούμε να δούμε μέχρι 1 στο δέντρο.

349
00:26:35,420 --> 00:26:38,790
Αυτό είναι παρόμοιο με αυτό που συμβαίνει, αν κοιτάξουμε το 10, εκτός αντί να πάει προς τα δεξιά,

350
00:26:38,790 --> 00:26:41,260
θα πάμε για να πάει προς τα αριστερά.

351
00:26:41,260 --> 00:26:46,170
Ξεκινάμε στο 7 και να δούμε ότι το 1 είναι μικρότερο του 7, έτσι ώστε να κινηθεί προς τα αριστερά.

352
00:26:46,170 --> 00:26:51,750
Έχουμε φτάσει στο 3 και βλέπω ότι το 1 είναι μικρότερο από 3, οπότε και πάλι θα προσπαθήσουμε να προχωρήσουμε προς τα αριστερά.

353
00:26:51,750 --> 00:26:59,080
Σε αυτό το σημείο έχουμε μηδενική κόμβο, έτσι και πάλι μπορούμε να αναφέρουμε την αποτυχία.

354
00:26:59,080 --> 00:27:10,260
>> Αν θέλετε να μάθετε περισσότερα για δυαδικά δέντρα,

355
00:27:10,260 --> 00:27:14,420
υπάρχουν ένα σωρό διασκέδαση μικρά προβλήματα που μπορείτε να κάνετε με αυτά.

356
00:27:14,420 --> 00:27:19,450
Προτείνω να ασκούν το σχέδιο από αυτά τα διαγράμματα ένα-ένα

357
00:27:19,450 --> 00:27:21,910
και μετά μέσα από όλα τα διαφορετικά βήματα,

358
00:27:21,910 --> 00:27:25,060
γιατί αυτό θα έρθει σε υπερ-βολικό

359
00:27:25,060 --> 00:27:27,480
όχι μόνο όταν κάνεις την κωδικοποίηση Huffman σετ πρόβλημα

360
00:27:27,480 --> 00:27:29,390
αλλά και στις μελλοντικές μαθήματα -

361
00:27:29,390 --> 00:27:32,220
μόλις μαθαίνει πώς να επιστήσω αυτές τις δομές δεδομένων και ότι μέσα από τα προβλήματα

362
00:27:32,220 --> 00:27:38,000
με στυλό και χαρτί ή, στην περίπτωση αυτή, το iPad και γραφίδα.

363
00:27:38,000 --> 00:27:41,000
>> Σε αυτό το σημείο όμως, θα πάμε να προχωρήσουμε για να κάνουν κάποια πρακτική κωδικοποίησης

364
00:27:41,000 --> 00:27:44,870
και πραγματικά παίζουν με αυτά τα δυαδικά δένδρα και να δούμε.

365
00:27:44,870 --> 00:27:52,150
Πάω να μεταβείτε πίσω πάνω στον υπολογιστή μου.

366
00:27:52,150 --> 00:27:58,480
Γι 'αυτό το μέρος του τμήματος, αντί να χρησιμοποιεί CS50 ή CS50 Run χώρους,

367
00:27:58,480 --> 00:28:01,500
Είμαι πρόκειται να χρησιμοποιήσετε τη συσκευή.

368
00:28:01,500 --> 00:28:04,950
>> Μετά μαζί με τις προδιαγραφές του προβλήματος,

369
00:28:04,950 --> 00:28:07,740
Βλέπω ότι είμαι υποτίθεται ότι πρέπει να ανοίξει τη συσκευή,

370
00:28:07,740 --> 00:28:11,020
πηγαίνετε στο φάκελο Dropbox μου, να δημιουργήσετε ένα φάκελο που ονομάζεται Τμήμα 7,

371
00:28:11,020 --> 00:28:15,730
και στη συνέχεια να δημιουργήσετε ένα αρχείο με το όνομα binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Εδώ πάμε. Έχω τη συσκευή είναι ήδη ανοιχτό.

373
00:28:22,050 --> 00:28:25,910
Πάω να τραβήξει ένα τερματικό.

374
00:28:25,910 --> 00:28:38,250
Πάω να πάει στο φάκελο Dropbox, κάνει ένα κατάλογο με το όνομα section7,

375
00:28:38,250 --> 00:28:42,230
και να δείτε ότι είναι εντελώς άδειο.

376
00:28:42,230 --> 00:28:48,860
Τώρα είμαι πρόκειται να ανοίξει binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Εντάξει. Εδώ πάμε - κενό αρχείο.

378
00:28:51,750 --> 00:28:54,330
>> Ας πάμε πίσω στις προδιαγραφές.

379
00:28:54,330 --> 00:28:59,850
Η προδιαγραφή ζητά να δημιουργήσετε ένα νέο ορισμό του τύπου

380
00:28:59,850 --> 00:29:03,080
για ένα δυαδικό κόμβο του δένδρου που περιέχει τιμές int -

381
00:29:03,080 --> 00:29:07,110
όπως ακριβώς τις αξίες που σχεδιάσαμε στο διαγραμμάτων μας πριν.

382
00:29:07,110 --> 00:29:11,740
Εμείς πάμε για να χρησιμοποιήσετε αυτό το στερεότυπο typedef ότι έχουμε κάνει εδώ

383
00:29:11,740 --> 00:29:14,420
ότι θα πρέπει να αναγνωρίσει από το σύνολο Πρόβλημα 5 -

384
00:29:14,420 --> 00:29:19,190
αν κάνατε τον τρόπο hash πίνακα της κατάκτησης του προγράμματος ορθογράφος.

385
00:29:19,190 --> 00:29:22,540
Θα πρέπει να αναγνωρίσουμε επίσης από το τμήμα την περασμένη εβδομάδα

386
00:29:22,540 --> 00:29:23,890
όπου μιλήσαμε για συνδεδεμένες λίστες.

387
00:29:23,890 --> 00:29:27,870
Έχουμε αυτό το typedef ενός κόμβου struct,

388
00:29:27,870 --> 00:29:34,430
και έχουμε δώσει στον κόμβο struct αυτό το όνομα του κόμβου struct εκ των προτέρων

389
00:29:34,430 --> 00:29:39,350
έτσι ώστε να μπορεί στη συνέχεια να αναφερθώ σε αυτό, δεδομένου ότι θα θέλουν να έχουν δείκτες κόμβο struct

390
00:29:39,350 --> 00:29:45,740
ως μέρος του struct μας, αλλά έχουμε περικυκλώνεται τότε αυτό -

391
00:29:45,740 --> 00:29:47,700
ή μάλλον, αυτό που περικλείεται - σε ένα typedef

392
00:29:47,700 --> 00:29:54,600
έτσι ώστε, αργότερα στον κώδικα, μπορούμε να αναφερθούμε σε αυτό το struct όπως ακριβώς ένα κόμβο, αντί ενός κόμβου struct.

393
00:29:54,600 --> 00:30:03,120
>> Αυτό πρόκειται να είναι πολύ παρόμοια με τη μεμονωμένα που συνδέονται με τον ορισμό λίστα που είδαμε την περασμένη εβδομάδα.

394
00:30:03,120 --> 00:30:20,070
Για να το κάνετε αυτό, ας αρχίσει με το γράψιμο από το στερεότυπο.

395
00:30:20,070 --> 00:30:23,840
Γνωρίζουμε ότι πρέπει να έχουμε μια ακέραια τιμή,

396
00:30:23,840 --> 00:30:32,170
οπότε θα τεθεί σε int αξία, και στη συνέχεια, αντί να έχουν μόνο ένα δείκτη στο επόμενο στοιχείο -

397
00:30:32,170 --> 00:30:33,970
όπως κάναμε και με μεμονωμένα-linked lists -

398
00:30:33,970 --> 00:30:38,110
θα πάμε να έχουν αριστερά και δεξιά δείκτες παιδί.

399
00:30:38,110 --> 00:30:42,880
Αυτό είναι αρκετά απλή πάρα πολύ - struct node * αριστερό παιδί?

400
00:30:42,880 --> 00:30:51,190
και struct node * δικαίωμα του παιδιού?. Cool.

401
00:30:51,190 --> 00:30:54,740
Αυτό φαίνεται σαν μια πολύ καλή αρχή.

402
00:30:54,740 --> 00:30:58,530
Ας πάμε πίσω στις προδιαγραφές.

403
00:30:58,530 --> 00:31:05,030
>> Τώρα πρέπει να κηρύξει μια παγκόσμια μεταβλητή * κόμβος για τη ρίζα ενός δέντρου.

404
00:31:05,030 --> 00:31:10,590
Εμείς πάμε για να κάνουν αυτό το παγκόσμιο όπως ακριβώς έκανε την πρώτη του δείκτη σε συνδεδεμένη λίστα μας και παγκόσμια.

405
00:31:10,590 --> 00:31:12,690
Αυτό ήταν έτσι ώστε οι λειτουργίες που γράφουμε

406
00:31:12,690 --> 00:31:16,180
δεν έχουμε να κρατήσει περνώντας γύρω από αυτή τη ρίζα -

407
00:31:16,180 --> 00:31:19,620
αν και θα δούμε ότι αν θέλουν να γράψουν αυτές τις λειτουργίες αναδρομικά,

408
00:31:19,620 --> 00:31:22,830
θα ήταν καλύτερα να μην περάσει καν γύρω ως μια παγκόσμια στην πρώτη θέση

409
00:31:22,830 --> 00:31:28,090
αρχικοποίηση και αντ 'αυτού σε τοπικό επίπεδο στην κύρια λειτουργία σας.

410
00:31:28,090 --> 00:31:31,960
Αλλά, θα το κάνουμε σε παγκόσμιο επίπεδο για να ξεκινήσει.

411
00:31:31,960 --> 00:31:39,920
Και πάλι, θα σας δώσουμε ένα ζευγάρι των χώρων, και θα πάω να δηλώσει έναν κόμβο ρίζα *.

412
00:31:39,920 --> 00:31:46,770
Ακριβώς για να βεβαιωθείτε ότι δεν αφήνουν αυτό δεν έχει προετοιμαστεί, Πάω να ισούται με το μηδέν.

413
00:31:46,770 --> 00:31:52,210
Τώρα, στην κύρια λειτουργία - που θα γράψει πολύ γρήγορα εδώ -

414
00:31:52,210 --> 00:32:00,450
int main (int argc, const char * argv []) -

415
00:32:00,450 --> 00:32:10,640
και είμαι πρόκειται να ξεκινήσει δηλώνοντας argv array μου ως const ακριβώς έτσι ότι ξέρω

416
00:32:10,640 --> 00:32:14,550
ότι τα επιχειρήματα αυτά είναι επιχειρήματα που πιθανώς δεν θέλετε να τροποποιήσετε.

417
00:32:14,550 --> 00:32:18,390
Αν θέλω να τα τροποποιήσετε εγώ θα πρέπει μάλλον να κάνει αντίγραφά τους.

418
00:32:18,390 --> 00:32:21,740
Θα δείτε αυτό το πολύ σε κώδικα.

419
00:32:21,740 --> 00:32:25,440
Είναι ωραία ή τον άλλο τρόπο. Είναι ωραία να το αφήσουμε ως - παραλείπουν το const αν θέλετε.

420
00:32:25,440 --> 00:32:28,630
Έβαλα συνήθως ακριβώς έτσι ότι εγώ ο ίδιος υπενθυμίζω

421
00:32:28,630 --> 00:32:33,650
 ότι πιθανώς δεν θέλετε να τροποποιήσετε τα επιχειρήματα αυτά.

422
00:32:33,650 --> 00:32:39,240
>> Όπως πάντα, θα πάω να συμπεριλάβετε αυτό το return 0 γραμμή στο τέλος της κύριας.

423
00:32:39,240 --> 00:32:45,730
Εδώ, θα προετοιμάσει τον κόμβο ρίζα μου.

424
00:32:45,730 --> 00:32:48,900
Όπως έχουν τα πράγματα αυτή τη στιγμή, έχω ένα δείκτη που είναι ορίζεται σε μηδέν,

425
00:32:48,900 --> 00:32:52,970
γι 'αυτό είναι που δείχνει σε τίποτα.

426
00:32:52,970 --> 00:32:57,480
Για να αρχίσετε πραγματικά την κατασκευή του κόμβου,

427
00:32:57,480 --> 00:32:59,250
Θα πρέπει πρώτα να εκχωρήσει μνήμη για αυτό.

428
00:32:59,250 --> 00:33:05,910
Πάω να κάνω ότι κάνοντας μνήμη στο σωρό με τη χρήση malloc.

429
00:33:05,910 --> 00:33:10,660
Πάω να θέσει ρίζα ίσο με το αποτέλεσμα της malloc,

430
00:33:10,660 --> 00:33:19,550
και είμαι πρόκειται να χρησιμοποιήσετε το sizeof χειριστή να υπολογίσει το μέγεθος ενός κόμβου.

431
00:33:19,550 --> 00:33:24,990
Ο λόγος που χρησιμοποιώ sizeof κόμβο, σε αντίθεση, ας πούμε,

432
00:33:24,990 --> 00:33:37,020
να κάνει κάτι τέτοιο - malloc (4 + 4 +4) ή malloc 12 -

433
00:33:37,020 --> 00:33:40,820
είναι γιατί θέλω κωδικό μου να είναι όσο το δυνατόν συμβατά.

434
00:33:40,820 --> 00:33:44,540
Θέλω να είμαι σε θέση να εκμεταλλευτώ αυτή. Αρχείο γ, να καταρτίσει τη συσκευή,

435
00:33:44,540 --> 00:33:48,820
και την κατάρτιση στη συνέχεια σε 64-bit Mac μου -

436
00:33:48,820 --> 00:33:52,040
ή σε μια εντελώς διαφορετική αρχιτεκτονική -

437
00:33:52,040 --> 00:33:54,640
και θέλω όλα αυτά να λειτουργούν με τον ίδιο.

438
00:33:54,640 --> 00:33:59,510
>> Αν κάνω υποθέσεις για το μέγεθος των μεταβλητών -

439
00:33:59,510 --> 00:34:02,070
το μέγεθος μιας int ή το μέγεθος ενός δείκτη -

440
00:34:02,070 --> 00:34:06,070
τότε κάνω και παραδοχές σχετικά με τα είδη των αρχιτεκτονικών

441
00:34:06,070 --> 00:34:10,440
στις οποίες κωδικό μου μπορεί να μεταγλωττίσετε επιτυχώς όταν τρέχει.

442
00:34:10,440 --> 00:34:15,030
Πάντα να χρησιμοποιείτε sizeof, σε αντίθεση με το χέρι αθροίζοντας τα πεδία struct.

443
00:34:15,030 --> 00:34:20,500
Ο άλλος λόγος είναι ότι μπορεί να υπάρχουν, επίσης, να γεμίσει ότι ο μεταγλωττιστής βάζει μέσα στο struct.

444
00:34:20,500 --> 00:34:26,570
Ακόμα και αθροίζοντας μόνο τα μεμονωμένα πεδία δεν είναι κάτι που συνήθως θέλουν να κάνουν,

445
00:34:26,570 --> 00:34:30,340
έτσι, να διαγράψετε αυτή τη γραμμή.

446
00:34:30,340 --> 00:34:33,090
Τώρα, για να προετοιμάσει αυτό το πραγματικά κόμβο ρίζα,

447
00:34:33,090 --> 00:34:36,489
Πάω να πρέπει να συνδέσετε τις τιμές για κάθε ένα από διάφορους τομείς της.

448
00:34:36,489 --> 00:34:41,400
Για παράδειγμα, για την αξία Ξέρω ότι θέλω να προετοιμαστεί έως 7,

449
00:34:41,400 --> 00:34:46,920
και για τώρα πάω να ορίσετε το αριστερό παιδί να είναι null

450
00:34:46,920 --> 00:34:55,820
και το δικαίωμα του παιδιού να είναι επίσης άκυρη. Μεγάλη!

451
00:34:55,820 --> 00:35:02,670
Έχουμε κάνει το μέρος του spec.

452
00:35:02,670 --> 00:35:07,390
>> Η προδιαγραφή κάτω στο κάτω μέρος της σελίδας 3 με ρωτάει να δημιουργήσει τρεις κόμβους -

453
00:35:07,390 --> 00:35:10,600
μια που περιέχει 3, ένα που περιέχει 6, και ένα με 9 -

454
00:35:10,600 --> 00:35:14,210
σύρμα και στη συνέχεια επάνω έτσι ώστε να φαίνεται ακριβώς όπως το διάγραμμα δέντρο μας

455
00:35:14,210 --> 00:35:17,120
ότι μιλούσαμε για το παρελθόν.

456
00:35:17,120 --> 00:35:20,450
Ας το κάνουμε αυτό πολύ γρήγορα εδώ.

457
00:35:20,450 --> 00:35:26,270
Θα δείτε πολύ γρήγορα ότι Πάω να αρχίσετε να γράφετε μια δέσμη των διπλών κώδικα.

458
00:35:26,270 --> 00:35:32,100
Πάω να δημιουργήσει έναν κόμβο * και Πάω να το ονομάσουμε τρία.

459
00:35:32,100 --> 00:35:36,000
Πάω να το θέσει ίση με malloc (sizeof (κόμβος)).

460
00:35:36,000 --> 00:35:41,070
Πάω να θέσει τρεις-> value = 3.

461
00:35:41,070 --> 00:35:54,780
Τρεις -> left_child = NULL? Τρία -> δεξί NULL _child =?, Καθώς και.

462
00:35:54,780 --> 00:36:01,150
Που φαίνεται αρκετά παρόμοια με την προετοιμασία της ρίζας, και αυτό είναι ακριβώς ό, τι

463
00:36:01,150 --> 00:36:05,760
Πάω να πρέπει να κάνω αν αρχίσει την προετοιμασία 6 και 9, καθώς και.

464
00:36:05,760 --> 00:36:20,720
Θα το κάνουμε αυτό πολύ γρήγορα εδώ - στην πραγματικότητα, Πάω να κάνουμε μια μικρή αντιγραφή και επικόλληση,

465
00:36:20,720 --> 00:36:46,140
και βεβαιωθείτε ότι εγώ - εντάξει.

466
00:36:46,470 --> 00:37:09,900
 Τώρα, έχω το πήρα αντιγραφή και μπορώ να πάω μπροστά και να θέσει αυτό ίσο με 6.

467
00:37:09,900 --> 00:37:14,670
Μπορείτε να δείτε ότι αυτό παίρνει λίγο χρόνο και δεν είναι υπερ-αποδοτική.

468
00:37:14,670 --> 00:37:22,610
Σε μόλις λίγο, θα γράψω μια λειτουργία που θα το κάνει αυτό για εμάς.

469
00:37:22,610 --> 00:37:32,890
Θέλω να το αντικαταστήσετε με ένα 9, το αντικαταστήσουμε με το 6.

470
00:37:32,890 --> 00:37:37,360
>> Τώρα έχουμε όλοι μας από τους κόμβους που δημιουργήθηκε και αρχικοποιηθεί.

471
00:37:37,360 --> 00:37:41,200
Έχουμε ρίζα μας ισούται με το 7, ή που περιέχει την τιμή 7,

472
00:37:41,200 --> 00:37:46,510
κόμβο μας που περιέχει 3, ο κόμβος μας που περιέχει 6, και ο κόμβος μας που περιέχει 9.

473
00:37:46,510 --> 00:37:50,390
Σε αυτό το σημείο, το μόνο που έχουμε να κάνουμε είναι ό, τι μέχρι σύρμα.

474
00:37:50,390 --> 00:37:53,020
Ο λόγος που αρχικοποιηθεί όλα τα null δείκτες να είναι ακριβώς έτσι ώστε να μπορώ να βεβαιωθείτε ότι

475
00:37:53,020 --> 00:37:56,260
Δεν έχω κανένα δεν έχει προετοιμαστεί δείκτες εκεί κατά λάθος.

476
00:37:56,260 --> 00:38:02,290
Και, επίσης, δεδομένου ότι, σε αυτό το σημείο, έχω μόνο να συνδέσετε πραγματικά τους κόμβους μεταξύ τους -

477
00:38:02,290 --> 00:38:04,750
με αυτές που πραγματικά είστε συνδεδεμένος με - δεν έχω να περάσει και να κάνει

478
00:38:04,750 --> 00:38:08,240
βεβαιωθείτε ότι όλα τα μηδενικά είναι εκεί στις κατάλληλες θέσεις.

479
00:38:08,240 --> 00:38:15,630
>> Ξεκινώντας από τη ρίζα, ξέρω ότι το αριστερό παιδί της ρίζας είναι 3.

480
00:38:15,630 --> 00:38:21,250
Ξέρω ότι το δικαίωμα του παιδιού της ρίζας είναι 9.

481
00:38:21,250 --> 00:38:24,880
Μετά από αυτό, το μόνο άλλο παιδί που έχω αφήσει να ανησυχείτε για

482
00:38:24,880 --> 00:38:39,080
είναι σωστό παιδί 3, η οποία είναι 6.

483
00:38:39,080 --> 00:38:44,670
Σε αυτό το σημείο, όλα φαίνονται πολύ καλά.

484
00:38:44,670 --> 00:38:54,210
Θα διαγράψετε κάποια από αυτές τις γραμμές.

485
00:38:54,210 --> 00:38:59,540
Τώρα ό, τι φαίνεται αρκετά καλό.

486
00:38:59,540 --> 00:39:04,240
Ας επιστρέψουμε με τις προδιαγραφές μας και να δούμε τι πρέπει να κάνουμε στη συνέχεια.

487
00:39:04,240 --> 00:39:07,610
>> Σε αυτό το σημείο, πρέπει να γράψουμε μια λειτουργία που ονομάζεται «περιέχει»

488
00:39:07,610 --> 00:39:14,150
με ένα πρωτότυπο της «bool Περιέχει (int τιμή)».

489
00:39:14,150 --> 00:39:17,060
Και αυτό περιλαμβάνει τη λειτουργία πρόκειται να επιστρέψει αλήθεια

490
00:39:17,060 --> 00:39:21,200
 αν το δέντρο επεσήμανε από την παγκόσμια μεταβλητή ρίζα μας

491
00:39:21,200 --> 00:39:26,950
 περιέχει την τιμή διέρχεται εντός του λειτουργία και ψευδή διαφορετικά.

492
00:39:26,950 --> 00:39:29,000
Ας πάμε μπροστά και να το κάνουμε αυτό.

493
00:39:29,000 --> 00:39:35,380
Αυτό πρόκειται να είναι ακριβώς όπως την αναζήτηση που κάναμε με το χέρι στο iPad μόνο λίγο πριν.

494
00:39:35,380 --> 00:39:40,130
Ας μεγεθύνετε σε λίγο και μετακινηθείτε προς τα πάνω.

495
00:39:40,130 --> 00:39:43,130
Εμείς πάμε για να βάλει αυτή τη λειτουργία ακριβώς πάνω από το κύριο έργο μας

496
00:39:43,130 --> 00:39:48,990
έτσι ώστε δεν έχουμε να κάνουμε οποιοδήποτε είδος των πρωτοτύπων.

497
00:39:48,990 --> 00:39:55,960
Έτσι, περιέχει bool (int αξία).

498
00:39:55,960 --> 00:40:00,330
Εκεί πάμε. Υπάρχει δήλωση στερεότυπο μας.

499
00:40:00,330 --> 00:40:02,900
Ακριβώς για να βεβαιωθείτε ότι αυτό θα συγκεντρώνει,

500
00:40:02,900 --> 00:40:06,820
Πάω να προχωρήσει και αυτό που ακριβώς ίσο με επιστροφή ψευδείς.

501
00:40:06,820 --> 00:40:09,980
Αυτή τη στιγμή η λειτουργία αυτή απλά δεν θα κάνει τίποτα και πάντα αναφέρουν ότι

502
00:40:09,980 --> 00:40:14,010
η τιμή που ψάχνουμε δεν είναι στο δέντρο.

503
00:40:14,010 --> 00:40:16,280
>> Σε αυτό το σημείο, είναι πιθανώς μια καλή ιδέα -

504
00:40:16,280 --> 00:40:19,600
αφού έχουμε γράψει ένα σωρό κώδικα και δεν έχουμε καν δοκιμάσει τον έλεγχο αυτό ακόμη -

505
00:40:19,600 --> 00:40:22,590
για να βεβαιωθείτε ότι συγκεντρώνει όλα.

506
00:40:22,590 --> 00:40:27,460
Υπάρχουν μερικά πράγματα που πρέπει να κάνετε για να βεβαιωθείτε ότι αυτό πράγματι θα καταρτίσει.

507
00:40:27,460 --> 00:40:33,530
Πρώτον, να δούμε αν έχουμε χρησιμοποιήσει οποιεσδήποτε λειτουργίες σε κάθε βιβλιοθήκες που δεν έχουν ακόμη περιληφθεί.

508
00:40:33,530 --> 00:40:37,940
Οι λειτουργίες που έχουμε χρησιμοποιήσει μέχρι τώρα είναι malloc,

509
00:40:37,940 --> 00:40:43,310
και στη συνέχεια, έχουμε επίσης τη χρήση αυτού του τύπου - αυτό όχι συνηθισμένες τύπου που ονομάζεται «bool' -

510
00:40:43,310 --> 00:40:45,750
η οποία περιλαμβάνεται στο πρότυπο bool αρχείο κεφαλίδας.

511
00:40:45,750 --> 00:40:53,250
Εμείς σίγουρα θέλετε να συμπεριλάβετε bool.h πρότυπο για την bool τύπου,

512
00:40:53,250 --> 00:40:59,230
και θέλουμε επίσης να περιλαμβάνουν lib.h # πρότυπο για τις βιβλιοθήκες πρότυπο

513
00:40:59,230 --> 00:41:03,530
που περιλαμβάνουν malloc, και δωρεάν, και όλα αυτά.

514
00:41:03,530 --> 00:41:08,660
Έτσι, σμίκρυνση, θα πάμε να σταματήσουν το κάπνισμα.

515
00:41:08,660 --> 00:41:14,190
Ας προσπαθήσουμε και να βεβαιωθείτε ότι αυτό το έκανε πραγματικότητα μεταγλώττιση.

516
00:41:14,190 --> 00:41:18,150
Βλέπουμε ότι το κάνει, έτσι είμαστε στο σωστό δρόμο.

517
00:41:18,150 --> 00:41:22,990
>> Ας ανοίξουμε και πάλι binary_tree.c.

518
00:41:22,990 --> 00:41:34,530
Καταρτίζει. Ας πάμε κάτω και βεβαιωθείτε ότι εισάγουμε κάποιες κλήσεις προς Περιέχει λειτουργία μας -

519
00:41:34,530 --> 00:41:40,130
ακριβώς για να βεβαιωθείτε ότι όλα είναι ωραία και καλά.

520
00:41:40,130 --> 00:41:43,170
Για παράδειγμα, όταν κάναμε κάποιες αναζητήσεις στο δέντρο μας νωρίτερα,

521
00:41:43,170 --> 00:41:48,500
προσπαθήσαμε να κοιτάζω προς τα πάνω τις τιμές 6, 10, και 1, και ξέραμε ότι 6 ήταν στο δέντρο,

522
00:41:48,500 --> 00:41:52,220
10 δεν ήταν στο δέντρο, και 1 δεν ήταν στο δέντρο, είτε.

523
00:41:52,220 --> 00:41:57,230
Ας χρησιμοποιήσουμε αυτές τις κλήσεις του δείγματος ως ένας τρόπος για να καταλάβω αν ή όχι

524
00:41:57,230 --> 00:41:59,880
Περιέχει λειτουργία μας λειτουργεί.

525
00:41:59,880 --> 00:42:05,210
Για να το κάνουμε αυτό, είμαι πρόκειται να χρησιμοποιήσετε τη λειτουργία printf,

526
00:42:05,210 --> 00:42:10,280
και θα πάμε για να εκτυπώσετε το αποτέλεσμα της κλήσης να περιέχει.

527
00:42:10,280 --> 00:42:13,280
Πάω να βάλει σε μια σειρά »περιέχει (% d) = επειδή

528
00:42:13,280 --> 00:42:20,470
 θα πάμε για να συνδέσετε την αξία που εμείς πάμε να δούμε για,

529
00:42:20,470 --> 00:42:27,130
και =% s \ n "και να το χρησιμοποιήσετε ως συμβολοσειρά μορφής μας.

530
00:42:27,130 --> 00:42:30,720
Είμαστε ακριβώς πρόκειται να δούμε - κυριολεκτικά εκτυπώσετε στην οθόνη -

531
00:42:30,720 --> 00:42:32,060
αυτό που μοιάζει με μια κλήση συνάρτησης.

532
00:42:32,060 --> 00:42:33,580
Αυτό δεν είναι στην πραγματικότητα η κλήση της συνάρτησης.

533
00:42:33,580 --> 00:42:36,760
 Αυτή είναι μόνο μια σειρά σχεδιαστεί για να μοιάζει με μια κλήση συνάρτησης.

534
00:42:36,760 --> 00:42:41,140
>> Τώρα, θα πάμε να συνδέσετε τις τιμές.

535
00:42:41,140 --> 00:42:43,580
Εμείς πάμε για να προσπαθήσουμε περιλαμβάνει στις 6,

536
00:42:43,580 --> 00:42:48,340
και τότε τι θα πάμε να κάνουμε εδώ είναι να χρησιμοποιήσετε αυτό το τριαδικό χειριστή.

537
00:42:48,340 --> 00:42:56,340
Ας δούμε - περιέχει 6 - έτσι, τώρα έχω περιείχε 6 και αν περιέχει 6 είναι αλήθεια,

538
00:42:56,340 --> 00:43:01,850
η σειρά που θα πάμε να στείλετε σε μορφή χαρακτήρων% s

539
00:43:01,850 --> 00:43:04,850
πρόκειται να είναι η συμβολοσειρά "αλήθεια".

540
00:43:04,850 --> 00:43:07,690
Ας μετακινηθείτε σε λίγο.

541
00:43:07,690 --> 00:43:16,210
Σε αντίθετη περίπτωση, θέλουμε να στείλουμε το string "ψευδή" εάν περιέχει 6 επιστρέφει false.

542
00:43:16,210 --> 00:43:19,730
Αυτό είναι λίγο ανόητη εμφάνιση, αλλά μπορώ να καταλάβω εγώ θα μπορούσε κάλλιστα να απεικονίζουν

543
00:43:19,730 --> 00:43:23,780
τι ο χειριστής τριαδικό μοιάζει αφού δεν έχουμε δει για λίγο.

544
00:43:23,780 --> 00:43:27,670
Αυτό θα είναι ένα ωραίο, πρακτικός τρόπος για να καταλάβουμε αν Περιέχει λειτουργία μας λειτουργεί.

545
00:43:27,670 --> 00:43:30,040
Πάω να μετακινηθείτε προς τα πίσω πάνω προς τα αριστερά,

546
00:43:30,040 --> 00:43:39,900
και Πάω να αντιγράψετε και να επικολλήσετε αυτή τη γραμμή μερικές φορές.

547
00:43:39,900 --> 00:43:44,910
Θα αλλάξει ορισμένες από αυτές τις αξίες γύρω,

548
00:43:44,910 --> 00:43:59,380
έτσι αυτό πρόκειται να είναι 1, και αυτό πρόκειται να είναι 10.

549
00:43:59,380 --> 00:44:02,480
>> Σε αυτό το σημείο έχουμε μια ωραία λειτουργία περιέχει.

550
00:44:02,480 --> 00:44:06,080
Έχουμε κάποιες εξετάσεις, και θα δούμε αν αυτό όλες οι εργασίες.

551
00:44:06,080 --> 00:44:08,120
Σε αυτό το σημείο έχουμε γράψει λίγο περισσότερο κώδικα.

552
00:44:08,120 --> 00:44:13,160
Ώρα να σταματήσουν και να βεβαιωθείτε ότι όλα συγκεντρώνει ακόμα.

553
00:44:13,160 --> 00:44:20,360
Κλείστε έξω, και τώρα ας προσπαθήσουμε κάνουν δυαδικό δέντρο και πάλι.

554
00:44:20,360 --> 00:44:22,260
Λοιπόν, φαίνεται σαν να έχεις ένα λάθος,

555
00:44:22,260 --> 00:44:26,930
και έχουμε αυτό δηλώνοντας ρητά τη λειτουργία της βιβλιοθήκης printf.

556
00:44:26,930 --> 00:44:39,350
Μοιάζει με εμείς πρέπει να πάμε μέσα και # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Και με αυτό, θα πρέπει να συγκεντρώνει τα πάντα. Είμαστε όλοι καλά.

558
00:44:45,350 --> 00:44:50,420
Τώρα ας προσπαθήσουμε τρέχει δυαδικό δέντρο και να δούμε τι θα συμβεί.

559
00:44:50,420 --> 00:44:53,520
Εδώ είμαστε,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
και βλέπουμε ότι, όπως ήταν αναμενόμενο -

561
00:44:55,190 --> 00:44:56,910
γιατί δεν έχουν υλοποιηθεί ακόμα περιέχει,

562
00:44:56,910 --> 00:44:59,800
ή μάλλον, έχουμε μόλις τεθεί σε αντάλλαγμα ψευδούς -

563
00:44:59,800 --> 00:45:03,300
βλέπουμε ότι αυτό είναι μόνο για την επιστροφή ψευδή όλα αυτά,

564
00:45:03,300 --> 00:45:06,180
έτσι ώστε να είναι όλοι εργάζονται ως επί το πλείστον αρκετά καλά.

565
00:45:06,180 --> 00:45:11,860
>> Ας πάμε πίσω σε εφαρμογή και στην πραγματικότητα περιέχει σε αυτό το σημείο.

566
00:45:11,860 --> 00:45:17,490
Πάω να μετακινηθείτε προς τα κάτω, zoom in, και -

567
00:45:17,490 --> 00:45:22,330
Θυμηθείτε, ο αλγόριθμος που χρησιμοποιήθηκε ήταν ότι ξεκινήσαμε στον κόμβο ρίζα

568
00:45:22,330 --> 00:45:28,010
και στη συνέχεια, σε κάθε κόμβο που συναντούμε, κάνουμε μια σύγκριση,

569
00:45:28,010 --> 00:45:32,380
και με βάση αυτή τη σύγκριση που είτε κινούνται προς τα αριστερά ή παιδί στο σωστό παιδί.

570
00:45:32,380 --> 00:45:39,670
Αυτό πρόκειται να εξετάσουμε πολύ παρόμοια με τον κώδικα δυαδική αναζήτηση που γράψαμε νωρίτερα στον όρο.

571
00:45:39,670 --> 00:45:47,810
Όταν ξεκινήσει, ξέρουμε ότι θέλουμε να κρατήσουμε την τρέχουσα κόμβο

572
00:45:47,810 --> 00:45:54,050
ότι ψάχνουμε σε, και ο τρέχων κόμβος πρόκειται να προετοιμαστεί για τον κόμβο ρίζα.

573
00:45:54,050 --> 00:45:56,260
Και τώρα, θα πάμε να συνεχίσουμε μέσα από το δέντρο,

574
00:45:56,260 --> 00:45:58,140
και να θυμάστε ότι μας σταματήσει κατάσταση -

575
00:45:58,140 --> 00:46:01,870
 όταν πραγματικά εργάστηκαν μέσα από το παράδειγμα με το χέρι -

576
00:46:01,870 --> 00:46:03,960
ήταν όταν συναντήσαμε μια μηδενική κόμβο,

577
00:46:03,960 --> 00:46:05,480
όταν δεν κοιτάξαμε μηδενική παιδί,

578
00:46:05,480 --> 00:46:09,620
αλλά μάλλον, όταν στην πραγματικότητα κινείται με έναν κόμβο στο δέντρο

579
00:46:09,620 --> 00:46:12,640
και διαπίστωσε ότι είμαστε σε ένα κόμβο null.

580
00:46:12,640 --> 00:46:20,720
Εμείς πάμε για να επαναλάβει μέχρι τρέχουσα δεν είναι ίσο με το μηδέν.

581
00:46:20,720 --> 00:46:22,920
Και τι θα κάνουμε;

582
00:46:22,920 --> 00:46:31,610
Εμείς πάμε για να ελέγξετε αν (τρέχουσα -> αξία αξίας ==),

583
00:46:31,610 --> 00:46:35,160
τότε ξέρουμε ότι έχουμε βρεθεί πραγματικά τον κόμβο που ψάχνουμε.

584
00:46:35,160 --> 00:46:40,450
Έτσι, εδώ, μπορούμε να επιστρέψουμε αλήθεια.

585
00:46:40,450 --> 00:46:49,830
Διαφορετικά, θέλουμε να δούμε κατά πόσον ή όχι η τιμή είναι μικρότερη από την τιμή.

586
00:46:49,830 --> 00:46:53,850
Εάν η τιμή του τρέχοντος κόμβου είναι μικρότερη από την τιμή που ψάχνουμε,

587
00:46:53,850 --> 00:46:57,280
θα πάμε για να μετακινηθείτε προς τα δεξιά.

588
00:46:57,280 --> 00:47:10,600
Έτσι, τρέχουσα = τρέχουσα -> right_child? Και αλλιώς, θα πάμε για να μετακινηθείτε προς τα αριστερά.

589
00:47:10,600 --> 00:47:17,480
τρέχουσα τρέχουσα = -> left_child?. Pretty απλή.

590
00:47:17,480 --> 00:47:22,830
>> Μπορείτε πιθανώς αναγνωρίσει το βρόχο που μοιάζει πολύ με αυτό από

591
00:47:22,830 --> 00:47:27,580
δυαδική αναζήτηση νωρίτερα στον όρο, εκτός από τότε έχουμε να κάνουμε με χαμηλή, μεσαία και υψηλή.

592
00:47:27,580 --> 00:47:30,000
Εδώ, εμείς απλά πρέπει να δούμε σε τρέχουσα αξία,

593
00:47:30,000 --> 00:47:31,930
γι 'αυτό είναι ωραίο και απλό.

594
00:47:31,930 --> 00:47:34,960
Ας βεβαιωθείτε ότι αυτός ο κώδικας εργασίας.

595
00:47:34,960 --> 00:47:42,780
Πρώτον, βεβαιωθείτε ότι συγκεντρώνει. Μοιάζει να κάνει.

596
00:47:42,780 --> 00:47:47,920
Ας προσπαθήσουμε τρέχει.

597
00:47:47,920 --> 00:47:50,160
Και πράγματι, εκτυπώνει από ό, τι περιμέναμε.

598
00:47:50,160 --> 00:47:54,320
Βρίσκει τις 6 το δέντρο, δεν βρείτε 10 γιατί 10 δεν είναι στο δέντρο,

599
00:47:54,320 --> 00:47:57,740
και δεν βρει 1 1 είτε επειδή δεν είναι, επίσης, στο δέντρο.

600
00:47:57,740 --> 00:48:01,420
Cool πράγματα.

601
00:48:01,420 --> 00:48:04,470
>> Εντάξει. Ας επιστρέψουμε με τις προδιαγραφές μας και να δούμε τι γίνεται στη συνέχεια.

602
00:48:04,470 --> 00:48:07,990
Τώρα, θέλει να προσθέσει λίγο περισσότερο κόμβους στο δέντρο μας.

603
00:48:07,990 --> 00:48:11,690
Δεν θέλει να προσθέσει 5, 2, και 8, και βεβαιωθείτε ότι περιέχει κώδικα μας

604
00:48:11,690 --> 00:48:13,570
εξακολουθεί να λειτουργεί όπως αναμένεται.

605
00:48:13,570 --> 00:48:14,900
Πάμε να το κάνουμε αυτό.

606
00:48:14,900 --> 00:48:19,430
Σε αυτό το σημείο, αντί να κάνει αυτό το ενοχλητικό αντιγραφή και επικόλληση πάλι,

607
00:48:19,430 --> 00:48:23,770
ας γράψει μια λειτουργία για να δημιουργήσετε πραγματικά έναν κόμβο.

608
00:48:23,770 --> 00:48:27,740
Αν μετακινηθείτε προς τα κάτω σε όλη τη διαδρομή στην κύρια, βλέπουμε ότι έχουμε κάνει αυτό

609
00:48:27,740 --> 00:48:31,210
πολύ παρόμοιο κώδικα ξανά και ξανά κάθε φορά που θέλουμε να δημιουργήσουμε έναν κόμβο.

610
00:48:31,210 --> 00:48:39,540
>> Ας γράψουμε μια συνάρτηση η οποία θα βασιστεί στην πραγματικότητα έναν κόμβο για μας και να το επιστρέψουν.

611
00:48:39,540 --> 00:48:41,960
Πάω να το ονομάσουμε build_node.

612
00:48:41,960 --> 00:48:45,130
Πάω να οικοδομήσουμε ένα κόμβο με μια συγκεκριμένη αξία.

613
00:48:45,130 --> 00:48:51,040
Μεγεθύνετε εδώ.

614
00:48:51,040 --> 00:48:56,600
Το πρώτο πράγμα που θα κάνω είναι να δημιουργήσετε πραγματικά χώρος για τον κόμβο στο σωρό.

615
00:48:56,600 --> 00:49:05,400
Έτσι, ο κόμβος * n = malloc (sizeof (κόμβος))? N -> value = τιμή?

616
00:49:05,400 --> 00:49:14,960
και στη συνέχεια, εδώ, είμαι απλώς πρόκειται να προετοιμάσει όλα τα πεδία να είναι κατάλληλες τιμές.

617
00:49:14,960 --> 00:49:22,500
Και στο τέλος, εμείς θα επιστρέψει κόμβο μας.

618
00:49:22,500 --> 00:49:28,690
Εντάξει. Ένα πράγμα που πρέπει να σημειωθεί είναι ότι αυτό το δικαίωμα λειτουργία εδώ

619
00:49:28,690 --> 00:49:34,320
πρόκειται να επιστρέψει ένα δείκτη στη μνήμη που έχει σωρό που χορηγήθηκαν.

620
00:49:34,320 --> 00:49:38,880
Τι είναι ωραίο για αυτό είναι ότι αυτός ο κόμβος τώρα -

621
00:49:38,880 --> 00:49:42,420
πρέπει να το δηλώσει στο σωρό, διότι αν το δηλώσει στη στοίβα

622
00:49:42,420 --> 00:49:45,050
δεν θα είμαστε σε θέση να το κάνουμε σε αυτή τη λειτουργία, όπως αυτό.

623
00:49:45,050 --> 00:49:47,690
Ότι η μνήμη θα βγουν έξω από το πεδίο εφαρμογής

624
00:49:47,690 --> 00:49:51,590
και θα είναι άκυρη αν προσπαθήσαμε να έχουν πρόσβαση αργότερα.

625
00:49:51,590 --> 00:49:53,500
Από τη στιγμή που δηλώνουν σωρό-κατανεμημένη μνήμη,

626
00:49:53,500 --> 00:49:55,830
πρόκειται να πρέπει να φροντίσουν για την απελευθέρωση αργότερα

627
00:49:55,830 --> 00:49:58,530
για το πρόγραμμά μας να μην διαρρεύσει καμία μνήμη.

628
00:49:58,530 --> 00:50:01,270
Έχουμε βαρκάδες στο ότι για όλα τα άλλα στον κώδικα

629
00:50:01,270 --> 00:50:02,880
μόνο για λόγους απλούστευσης του εκείνη την εποχή,

630
00:50:02,880 --> 00:50:05,610
αλλά αν γράψετε ποτέ μια λειτουργία που μοιάζει με αυτό

631
00:50:05,610 --> 00:50:10,370
όπου έχετε - μερικοί αποκαλούν μια malloc ή realloc μέσα -

632
00:50:10,370 --> 00:50:14,330
θέλετε να βεβαιωθείτε ότι έχετε βάλει κάποιο είδος της σχόλιο μέχρι εδώ που λέει,

633
00:50:14,330 --> 00:50:29,970
hey, ξέρετε, επιστρέφει ένα σωρό-κατένειμε κόμβο αρχικοποιείται με την πέρασαν-σε αξία.

634
00:50:29,970 --> 00:50:33,600
Και τότε θα θέλετε να βεβαιωθείτε ότι έχετε θέσει σε κάποια σημείωση που λέει

635
00:50:33,600 --> 00:50:41,720
ο καλών πρέπει να ελευθερώσουν την επιστροφή της μνήμης.

636
00:50:41,720 --> 00:50:45,450
Με αυτόν τον τρόπο, αν κάποιος πηγαίνει ποτέ και χρησιμοποιεί αυτή τη λειτουργία,

637
00:50:45,450 --> 00:50:48,150
ξέρουν πως ό, τι παίρνουν πίσω από τη λειτουργία

638
00:50:48,150 --> 00:50:50,870
σε κάποιο σημείο θα πρέπει να απελευθερωθεί.

639
00:50:50,870 --> 00:50:53,940
>> Υποθέτοντας ότι όλα είναι ωραία και καλά εδώ,

640
00:50:53,940 --> 00:51:02,300
μπορούμε να πάμε κάτω στον κώδικα μας και να αντικαταστήσει όλες αυτές τις γραμμές εδώ

641
00:51:02,300 --> 00:51:05,410
με κλήσεις προς κατασκευή κόμβου λειτουργία μας.

642
00:51:05,410 --> 00:51:08,170
Ας το κάνουμε αυτό πολύ γρήγορα.

643
00:51:08,170 --> 00:51:15,840
Το ένα μέρος που δεν πρόκειται να αντικαταστήσει αυτό το μέρος είναι εδώ κάτω

644
00:51:15,840 --> 00:51:18,520
στο κάτω μέρος όπου μπορούμε πραγματικά σύρμα μέχρι τους κόμβους στο σημείο ο ένας στον άλλο,

645
00:51:18,520 --> 00:51:21,030
επειδή αυτό δεν μπορούμε να κάνουμε στη λειτουργία μας.

646
00:51:21,030 --> 00:51:37,400
Αλλά, ας κάνουμε root = build_node (7)? Κόμβο * τρεις build_node = (3)?

647
00:51:37,400 --> 00:51:47,980
κόμβο * έξι = build_node (6)? κόμβο * εννιά = build_node (9)?.

648
00:51:47,980 --> 00:51:52,590
Και τώρα, θελήσαμε επίσης να προσθέσετε κόμβους για -

649
00:51:52,590 --> 00:52:03,530
κόμβο * πέντε = build_node (5)? ​​κόμβο * = build_node οκτώ (8)?

650
00:52:03,530 --> 00:52:09,760
και ποιο ήταν το άλλο κόμβο; Ας δούμε εδώ. Θέλαμε να προσθέσουμε και ένα 2 -

651
00:52:09,760 --> 00:52:20,280
* Δύο κόμβος = build_node (2)?.

652
00:52:20,280 --> 00:52:26,850
Εντάξει. Σε αυτό το σημείο, ξέρουμε ότι έχουμε το 7, το 3, το 9 και το 6

653
00:52:26,850 --> 00:52:30,320
όλα ενσύρματο μέχρι κατάλληλα, αλλά τι γίνεται με το 5, το 8 και το 2;

654
00:52:30,320 --> 00:52:33,550
Για να διατηρήσετε τα πάντα με την κατάλληλη σειρά,

655
00:52:33,550 --> 00:52:39,230
γνωρίζουμε ότι το δικαίωμα του παιδιού τρία είναι 6.

656
00:52:39,230 --> 00:52:40,890
Έτσι, αν θα πάμε για να προσθέσετε το 5,

657
00:52:40,890 --> 00:52:46,670
η 5 ανήκει επίσης στη δεξιά πλευρά του δένδρου της οποίας 3 είναι η ρίζα,

658
00:52:46,670 --> 00:52:50,440
έτσι 5 ανήκει το αριστερό παιδί του 6.

659
00:52:50,440 --> 00:52:58,650
Μπορούμε να το κάνουμε αυτό με το ρητό, έξι -> left_child = πέντε?

660
00:52:58,650 --> 00:53:10,790
και στη συνέχεια το 8 ανήκει σαν αριστερό παιδί 9, οπότε εννέα -> left_child = οκτώ?

661
00:53:10,790 --> 00:53:22,190
και στη συνέχεια 2 είναι το αριστερό παιδί του 3, ώστε να μπορούμε να το κάνουμε αυτό εδώ - σου -> left_child = δύο?.

662
00:53:22,190 --> 00:53:27,730
Αν δεν έχετε αρκετά ακολουθήσει μαζί με αυτό, σας προτείνω να το σύρει έξω τον εαυτό σας.

663
00:53:27,730 --> 00:53:35,660
>> Εντάξει. Ας σώσει αυτό. Ας βγούμε έξω και να βεβαιωθείτε ότι συγκεντρώνει,

664
00:53:35,660 --> 00:53:40,760
και στη συνέχεια μπορούμε να προσθέσουμε σε κλήσεων περιέχει μας.

665
00:53:40,760 --> 00:53:44,120
Μοιάζει με ό, τι συνθέτει ακόμα.

666
00:53:44,120 --> 00:53:51,790
Ας πάμε και να προσθέσετε σε κάποια περιέχει κλήσεις.

667
00:53:51,790 --> 00:53:59,640
Και πάλι, Πάω να κάνω ένα μικρό κομμάτι της αντιγραφής και επικόλλησης.

668
00:53:59,640 --> 00:54:15,860
Τώρα ας αναζήτηση για 5, 8, και 2. Εντάξει.

669
00:54:15,860 --> 00:54:28,330
Ας βεβαιωθείτε ότι όλα αυτά εξακολουθεί να φαίνεται καλό. Μεγάλη! Αποθηκεύστε και κλείστε.

670
00:54:28,330 --> 00:54:33,220
Τώρα ας κάνουμε, συγκέντρωση, και τώρα ας τρέξει.

671
00:54:33,220 --> 00:54:37,540
Από τα αποτελέσματα, φαίνεται ότι όλα λειτουργούν ακριβώς ωραία και καλά.

672
00:54:37,540 --> 00:54:41,780
Μεγάλη! Έτσι τώρα έχουμε γράψει λειτουργούν Περιέχει μας.

673
00:54:41,780 --> 00:54:46,160
Ας προχωρήσουμε και να αρχίσουν να εργάζονται για το πώς να εισάγετε τους κόμβους στο δέντρο

674
00:54:46,160 --> 00:54:50,000
δεδομένου ότι, όπως το κάνουμε τώρα, τα πράγματα δεν είναι πολύ όμορφη.

675
00:54:50,000 --> 00:54:52,280
>> Αν πάμε πίσω στις προδιαγραφές,

676
00:54:52,280 --> 00:55:00,540
να μας ζητά να γράψει μια λειτουργία που ονομάζεται εισάγετε - και πάλι, επιστρέφοντας ένα bool

677
00:55:00,540 --> 00:55:04,400
για το αν ή όχι θα μπορούσαμε να εισάγετε στην πραγματικότητα τον κόμβο στο δέντρο -

678
00:55:04,400 --> 00:55:07,710
και στη συνέχεια η τιμή να εισάγετε στο δέντρο ορίζεται ως

679
00:55:07,710 --> 00:55:11,060
το μόνο επιχείρημα για τη λειτουργία ένθετο μας.

680
00:55:11,060 --> 00:55:18,180
Θα επιστρέψει αλήθεια αν θα μπορούσαμε να εισάγετε πράγματι τον κόμβο που περιέχει τιμή στο δέντρο,

681
00:55:18,180 --> 00:55:20,930
πράγμα που σημαίνει ότι εμείς, ένα, είχε αρκετή μνήμη,

682
00:55:20,930 --> 00:55:24,840
και στη συνέχεια δύο, αυτός ο κόμβος δεν υπάρχουν ήδη στο δέντρο δεδομένου -

683
00:55:24,840 --> 00:55:32,170
Θυμηθείτε, δεν πρόκειται να έχουν διπλές τιμές στο δέντρο, απλά για να κάνει τα πράγματα απλά.

684
00:55:32,170 --> 00:55:35,590
Εντάξει. Επιστροφή στην κωδικού.

685
00:55:35,590 --> 00:55:44,240
Ανοίξτε το επάνω. Ζουμ σε λίγο, στη συνέχεια, μετακινηθείτε προς τα κάτω.

686
00:55:44,240 --> 00:55:47,220
Ας θέσει τη λειτουργία ένθετο δεξιά πάνω από τα περιέχει.

687
00:55:47,220 --> 00:55:56,360
Και πάλι, πρόκειται να κληθεί bool ένθετο (int αξία).

688
00:55:56,360 --> 00:56:01,840
Δώστε λίγο περισσότερο χώρο, και στη συνέχεια, ως προεπιλογή,

689
00:56:01,840 --> 00:56:08,870
ας βάλουμε σε αντάλλαγμα ψευδούς στο τέλος.

690
00:56:08,870 --> 00:56:22,620
Τώρα, κάτω στο κάτω μέρος, πάμε μπροστά και όχι το χέρι την κατασκευή των κόμβων

691
00:56:22,620 --> 00:56:27,900
στην κύρια τον εαυτό μας και τους καλωδίωση μέχρι το σημείο στο άλλο, όπως κάνουμε,

692
00:56:27,900 --> 00:56:30,600
θα στηρίζονται σε λειτουργία ένθετο μας να το κάνουμε αυτό.

693
00:56:30,600 --> 00:56:35,510
Εμείς δεν θα στηρίζονται σε λειτουργία ένθετο μας να χτίσουμε ολόκληρο το δέντρο από το μηδέν ακριβώς ακόμα,

694
00:56:35,510 --> 00:56:39,970
αλλά μάλλον θα απαλλαγούμε από αυτές τις γραμμές - we'll σχόλιο από αυτές τις γραμμές -

695
00:56:39,970 --> 00:56:43,430
που οικοδόμηση των κόμβων 5, 8, και 2.

696
00:56:43,430 --> 00:56:55,740
Και αντ 'αυτού, θα εισάγετε κλήσεις σε λειτουργία ένθετο μας

697
00:56:55,740 --> 00:57:01,280
για να βεβαιωθείτε ότι αυτό λειτουργεί πραγματικά.

698
00:57:01,280 --> 00:57:05,840
Εδώ πάμε.

699
00:57:05,840 --> 00:57:09,300
>> Τώρα έχουμε σχολίασε από αυτές τις γραμμές.

700
00:57:09,300 --> 00:57:13,700
Έχουμε μόνο 7, 3, 9, και 6 στο δέντρο μας σε αυτό το σημείο.

701
00:57:13,700 --> 00:57:18,870
Για να βεβαιωθείτε ότι αυτό είναι όλοι εργάζονται,

702
00:57:18,870 --> 00:57:25,050
μπορούμε σμίκρυνση, να δυαδικό δέντρο μας,

703
00:57:25,050 --> 00:57:30,750
τρέχει, και μπορούμε να δούμε ότι περιέχει μας λέει τώρα ότι είμαστε απόλυτα δίκιο -

704
00:57:30,750 --> 00:57:33,110
5, 8 και 2 δεν είναι πλέον στο δέντρο.

705
00:57:33,110 --> 00:57:37,960
Επιστροφή στον κώδικα,

706
00:57:37,960 --> 00:57:41,070
και πώς θα πάμε να εισάγετε;

707
00:57:41,070 --> 00:57:46,290
Θυμηθείτε τι κάναμε όταν ήμασταν πραγματικά εισαγωγή 5, 8, και 2 προηγουμένως.

708
00:57:46,290 --> 00:57:50,100
Παίξαμε το παιχνίδι Plinko όπου ξεκινήσαμε στη ρίζα,

709
00:57:50,100 --> 00:57:52,780
πήγε κάτω από το ένα δέντρο με ένα-ένα

710
00:57:52,780 --> 00:57:54,980
μέχρι να βρεθεί το κατάλληλο κενό,

711
00:57:54,980 --> 00:57:57,570
και τότε ενσύρματη στον κόμβο στο κατάλληλο σημείο.

712
00:57:57,570 --> 00:57:59,480
Εμείς πάμε να κάνουμε το ίδιο πράγμα.

713
00:57:59,480 --> 00:58:04,070
Αυτό είναι βασικά σα να γράφουμε τον κώδικα που χρησιμοποιούνται για την λειτουργία περιέχει

714
00:58:04,070 --> 00:58:05,910
για να βρείτε το σημείο όπου ο κόμβος θα πρέπει να είναι,

715
00:58:05,910 --> 00:58:10,560
και στη συνέχεια να είμαστε ακριβώς πρόκειται να τοποθετήσετε τον κόμβο εκεί.

716
00:58:10,560 --> 00:58:17,000
Ας αρχίσουμε να κάνουμε αυτό.

717
00:58:17,000 --> 00:58:24,200
>> Έτσι έχουμε έναν κόμβο * = τρέχουσα ρίζα? Είμαστε ακριβώς πρόκειται να ακολουθήσει ο κώδικας περιέχει

718
00:58:24,200 --> 00:58:26,850
μέχρι να βρούμε ότι δεν εργάζονται αρκετά για μας.

719
00:58:26,850 --> 00:58:32,390
Εμείς πάμε για να περάσει μέσα από το δέντρο, ενώ το τρέχον στοιχείο δεν είναι μηδενική,

720
00:58:32,390 --> 00:58:45,280
και αν βρούμε τρέχουσα αξία που είναι ίση με την αξία που προσπαθούμε να εισάγετε -

721
00:58:45,280 --> 00:58:49,600
καλά, αυτό είναι μία από τις περιπτώσεις στις οποίες δεν μπορούσαμε να εισαχθεί στην πραγματικότητα τον κόμβο

722
00:58:49,600 --> 00:58:52,730
στο δέντρο, γιατί αυτό σημαίνει ότι έχουμε μια διπλή αξία.

723
00:58:52,730 --> 00:58:59,010
Εδώ είμαστε πραγματικά πρόκειται να επιστρέψει ψευδείς.

724
00:58:59,010 --> 00:59:08,440
Τώρα αλλιώς, αν η αξία τρέχουσα είναι μικρότερη από την αξία,

725
00:59:08,440 --> 00:59:10,930
Τώρα ξέρουμε ότι κινούμαστε προς τη σωστή

726
00:59:10,930 --> 00:59:17,190
 επειδή η τιμή ανήκει στο δεξιό μισό του δέντρου τρέχουσα.

727
00:59:17,190 --> 00:59:30,110
Διαφορετικά, θα πάμε να κινηθεί προς τα αριστερά.

728
00:59:30,110 --> 00:59:37,980
Αυτό είναι βασικά Περιέχει μας λειτουργούν εκεί.

729
00:59:37,980 --> 00:59:41,820
>> Σε αυτό το σημείο, αφού έχουμε ολοκληρώσει αυτό το βρόχο while,

730
00:59:41,820 --> 00:59:47,350
τρέχουσα δείκτη μας θα πρέπει να δείχνει σε null

731
00:59:47,350 --> 00:59:51,540
αν η λειτουργία δεν έχει ήδη επιστραφεί.

732
00:59:51,540 --> 00:59:58,710
Είμαστε ως εκ τούτου έχει τρέχουσα στο σημείο όπου θέλετε να εισαγάγετε το νέο κόμβο.

733
00:59:58,710 --> 01:00:05,210
Αυτό που απομένει να γίνει είναι να οικοδομήσουμε στην πραγματικότητα το νέο κόμβο,

734
01:00:05,210 --> 01:00:08,480
το οποίο μπορούμε να κάνουμε αρκετά εύκολα.

735
01:00:08,480 --> 01:00:14,930
Μπορούμε να χρησιμοποιήσουμε υπερ-βολική λειτουργία μας κόμβο κατασκευής,

736
01:00:14,930 --> 01:00:17,210
και κάτι που δεν είχαμε κάνει νωρίτερα -

737
01:00:17,210 --> 01:00:21,400
έχουμε ακριβώς το είδος του πήρε για δεδομένος, αλλά τώρα θα κάνουμε ακριβώς για να βεβαιωθείτε ότι -

738
01:00:21,400 --> 01:00:27,130
θα δοκιμάσουμε να βεβαιωθείτε ότι η τιμή που επιστρέφεται από το νέο κόμβο ήταν στην πραγματικότητα

739
01:00:27,130 --> 01:00:33,410
όχι μηδενική, επειδή δεν θέλουμε να αρχίσουν την πρόσβαση σε αυτή τη μνήμη, αν είναι null.

740
01:00:33,410 --> 01:00:39,910
Μπορούμε να ελέγξετε για να βεβαιωθείτε ότι νέος κόμβος δεν είναι ίσο με null.

741
01:00:39,910 --> 01:00:42,910
Ή αντίθετα, μπορούμε απλά να δούμε αν είναι πραγματικά μηδενική,

742
01:00:42,910 --> 01:00:52,120
και αν είναι μηδενική, τότε μπορούμε απλά να επιστρέψει ψευδείς νωρίς.

743
01:00:52,120 --> 01:00:59,090
>> Σε αυτό το σημείο, πρέπει να σύρμα νέου κόμβου σε κατάλληλο σημείο του στο δέντρο.

744
01:00:59,090 --> 01:01:03,510
Αν κοιτάξουμε πίσω στο κεντρικό και όπου ήμασταν πραγματικά καλωδίωση σε τιμές πριν,

745
01:01:03,510 --> 01:01:08,470
βλέπουμε ότι ο τρόπος με τον οποίο το έκαναν όταν θελήσαμε να βάλει 3 στο δέντρο

746
01:01:08,470 --> 01:01:11,750
ήταν προσεγγίσαμε το αριστερό παιδί της ρίζας.

747
01:01:11,750 --> 01:01:14,920
Όταν βάζουμε 9 στο δέντρο, θα έπρεπε να έχουν πρόσβαση στο δικαίωμα του παιδιού της ρίζας.

748
01:01:14,920 --> 01:01:21,030
Έπρεπε να έχουμε ένα δείκτη προς τη μητρική εταιρεία, προκειμένου να τεθεί μια νέα τιμή στο δέντρο.

749
01:01:21,030 --> 01:01:24,430
Κύλιση πίσω μέχρι να εισάγετε, το οποίο δεν πρόκειται να λειτουργήσει αρκετά εδώ

750
01:01:24,430 --> 01:01:27,550
επειδή δεν έχουμε ένα δείκτη γονέα.

751
01:01:27,550 --> 01:01:31,650
Αυτό που θέλουμε να είμαστε σε θέση να κάνουμε είναι, σε αυτό το σημείο,

752
01:01:31,650 --> 01:01:37,080
ελέγξτε αξία της μητρικής και να δούμε - καλά, Θεέ,

753
01:01:37,080 --> 01:01:41,990
αν η αξία της μητρικής είναι μικρότερη από την τρέχουσα αξία,

754
01:01:41,990 --> 01:01:54,440
κάντε δεξί παιδί του γονέα θα πρέπει να είναι ο νέος κόμβος?

755
01:01:54,440 --> 01:02:07,280
αλλιώς, το αριστερό παιδί του γονέα θα πρέπει να είναι ο νέος κόμβος.

756
01:02:07,280 --> 01:02:10,290
Όμως, δεν έχουμε αυτό το δείκτη του γονέα αρκετά ακόμα.

757
01:02:10,290 --> 01:02:15,010
>> Για να το πάρει, είμαστε στην πραγματικότητα θα πρέπει να την παρακολουθείτε καθώς περνάμε από το δέντρο

758
01:02:15,010 --> 01:02:18,440
και να βρει το κατάλληλο σημείο στο βρόχο μας παραπάνω.

759
01:02:18,440 --> 01:02:26,840
Μπορούμε να το κάνουμε αυτό με κύλιση προς τα πίσω μέχρι την κορυφή της λειτουργίας μας ένθετο

760
01:02:26,840 --> 01:02:32,350
παρακολούθησης και μια άλλη μεταβλητή δείκτη που ονομάζεται μητρική.

761
01:02:32,350 --> 01:02:39,340
Εμείς πάμε για να ισούται με το μηδέν αρχικά,

762
01:02:39,340 --> 01:02:43,640
και στη συνέχεια, κάθε φορά που περνάμε από το δέντρο,

763
01:02:43,640 --> 01:02:51,540
θα πάμε για να ρυθμίσετε το δείκτη του γονέα για να ταιριάζει με τον τρέχοντα δείκτη.

764
01:02:51,540 --> 01:02:59,140
Ορισμός γονέα ίσο με τρέχουσα.

765
01:02:59,140 --> 01:03:02,260
Με αυτό τον τρόπο, κάθε φορά που περνάμε,

766
01:03:02,260 --> 01:03:05,550
θα πάμε για να διασφαλίσουν ότι η τρέχουσα δείκτης παίρνει αυξάνεται

767
01:03:05,550 --> 01:03:12,640
ο δείκτης μητρικής ακολουθεί - μόνο ένα επίπεδο υψηλότερο από την τρέχουσα δείκτη στο δέντρο.

768
01:03:12,640 --> 01:03:17,370
Όλα αυτά φαίνεται αρκετά καλό.

769
01:03:17,370 --> 01:03:22,380
>> Νομίζω ότι το μόνο πράγμα που θα θέλετε να ρυθμίσετε αυτή την κατασκευή είναι ο κόμβος επιστρέφει null.

770
01:03:22,380 --> 01:03:25,380
Για να πάρετε την κατασκευή κόμβου στην πραγματικότητα με επιτυχία επιστρέψει null,

771
01:03:25,380 --> 01:03:31,060
θα πρέπει να τροποποιήσει τον εν λόγω κώδικα,

772
01:03:31,060 --> 01:03:37,270
γιατί εδώ, δεν μπορούμε ποτέ δοκιμαστεί για να βεβαιωθείτε ότι η malloc επέστρεψε ένα έγκυρο δείκτη.

773
01:03:37,270 --> 01:03:53,390
Έτσι, αν (n = NULL!), Τότε -

774
01:03:53,390 --> 01:03:55,250
αν malloc επέστρεψε ένα έγκυρο δείκτη, τότε θα γίνει η προετοιμασία?

775
01:03:55,250 --> 01:04:02,540
αλλιώς, απλά θα επιστρέψει και αυτό θα καταλήξει null επιστρέφουν για μας.

776
01:04:02,540 --> 01:04:13,050
Τώρα το μόνο που φαίνεται αρκετά καλό. Ας βεβαιωθείτε ότι αυτό συγκεντρώνει πραγματικότητα.

777
01:04:13,050 --> 01:04:22,240
Κάντε δυαδικό δέντρο, και OH, έχουμε κάποια πράγματα συμβαίνουν εδώ.

778
01:04:22,240 --> 01:04:29,230
>> Έχουμε μια έμμεση δήλωση της λειτουργίας κατασκευή κόμβου.

779
01:04:29,230 --> 01:04:31,950
Και πάλι, με αυτούς τους compilers, θα πάμε για να ξεκινήσει στην κορυφή.

780
01:04:31,950 --> 01:04:36,380
Τι σημαίνει αυτό πρέπει να είναι ότι είμαι καλώντας την κατασκευή κόμβου πριν έχω δηλώσει αυτό στην πραγματικότητα.

781
01:04:36,380 --> 01:04:37,730
Ας πάμε πίσω στον κώδικα πραγματικά γρήγορα.

782
01:04:37,730 --> 01:04:43,510
Μετακινηθείτε προς τα κάτω, και αρκετά βέβαιος, λειτουργία ένθετο μου έχει δηλωθεί

783
01:04:43,510 --> 01:04:47,400
πάνω από τη λειτουργία του κόμβου κατασκευής,

784
01:04:47,400 --> 01:04:50,070
αλλά εγώ προσπαθώ να χρησιμοποιήσουν την κατασκευή κόμβου στο εσωτερικό του ένθετου.

785
01:04:50,070 --> 01:05:06,610
Πάω να πάει και αντιγραφή - επικόλληση και στη συνέχεια τον κόμβο κατασκευής τρόπο λειτουργίας εδώ στην κορυφή.

786
01:05:06,610 --> 01:05:11,750
Με αυτόν τον τρόπο, ελπίζουμε ότι θα λειτουργήσει. Ας δώσουμε αυτό πάει άλλο.

787
01:05:11,750 --> 01:05:18,920
Τώρα θα συγκεντρώνει όλα. Όλα είναι καλά.

788
01:05:18,920 --> 01:05:21,640
>> Αλλά σε αυτό το σημείο, δεν έχουμε στην πραγματικότητα ονομάζεται λειτουργία ένθετο μας.

789
01:05:21,640 --> 01:05:26,510
Γνωρίζουμε, όμως, ότι συγκεντρώνει, οπότε ας πάμε και να θέσει σε μερικές κλήσεις μέσα

790
01:05:26,510 --> 01:05:28,240
Ας το κάνουμε αυτό σε κύρια λειτουργία μας.

791
01:05:28,240 --> 01:05:32,390
Εδώ, σχολίασε από 5, 8, και 2,

792
01:05:32,390 --> 01:05:36,680
και τότε δεν τους σύρμα μέχρι εδώ κάτω.

793
01:05:36,680 --> 01:05:41,640
Ας κάνουμε κάποιες κλήσεις για την εισαγωγή,

794
01:05:41,640 --> 01:05:46,440
και ας χρησιμοποιήσουμε επίσης το ίδιο είδος της ουσίας που χρησιμοποιείται

795
01:05:46,440 --> 01:05:52,810
όταν κάναμε αυτές τις κλήσεις printf για να βεβαιωθείτε ότι τα πάντα είχαν πάρει τοποθετηθεί σωστά.

796
01:05:52,810 --> 01:06:00,550
Πάω να αντιγράψετε και να επικολλήσετε,

797
01:06:00,550 --> 01:06:12,450
και αντί περιέχει θα πάμε να κάνουμε ένθετο.

798
01:06:12,450 --> 01:06:30,140
Και αντί για 6, 10, και 1, θα πάμε να χρησιμοποιήσετε 5, 8, και 2.

799
01:06:30,140 --> 01:06:37,320
Αυτό θα πρέπει να εισαχθεί ελπίζουμε 5, 8, και 2 στο δέντρο.

800
01:06:37,320 --> 01:06:44,050
Μεταγλώττιση. Όλα είναι καλά. Τώρα θα τρέξει το πρόγραμμά μας στην πραγματικότητα.

801
01:06:44,050 --> 01:06:47,330
>> Όλα επέστρεψε ψευδείς.

802
01:06:47,330 --> 01:06:53,830
Έτσι, 5, 8, και 2 δεν πήγε, και μοιάζει Περιέχει δεν τα βρείτε είτε.

803
01:06:53,830 --> 01:06:58,890
Τι συμβαίνει; Ας σμίκρυνση.

804
01:06:58,890 --> 01:07:02,160
Το πρώτο πρόβλημα ήταν ότι ένθετο φάνηκε να επιστρέψει false,

805
01:07:02,160 --> 01:07:08,750
και μοιάζει με αυτό είναι επειδή αφήσαμε σε αντάλλαγμα ψευδούς κλήσης μας,

806
01:07:08,750 --> 01:07:14,590
και ποτέ δεν επέστρεψε στην πραγματικότητα αληθινή.

807
01:07:14,590 --> 01:07:17,880
Μπορούμε να το ρυθμίσω αυτό.

808
01:07:17,880 --> 01:07:25,290
Το δεύτερο πρόβλημα είναι, πλέον, ακόμη και αν το κάνουμε - να σώσει αυτό, κλείστε αυτό,

809
01:07:25,290 --> 01:07:34,530
να τρέξει και πάλι, έχουν καταρτίσει, στη συνέχεια, εκτελέστε το -

810
01:07:34,530 --> 01:07:37,670
βλέπουμε ότι κάτι άλλο συμβαίνει εδώ.

811
01:07:37,670 --> 01:07:42,980
Η 5, 8, και 2 ήταν ακόμα ποτέ δεν βρέθηκαν στο δέντρο.

812
01:07:42,980 --> 01:07:44,350
Έτσι, τι συμβαίνει;

813
01:07:44,350 --> 01:07:45,700
>> Ας ρίξουμε μια ματιά σε αυτό τον κωδικό.

814
01:07:45,700 --> 01:07:49,790
Ας δούμε αν μπορούμε να το καταλάβουν αυτό.

815
01:07:49,790 --> 01:07:57,940
Ξεκινάμε με το γονέα που δεν είναι null.

816
01:07:57,940 --> 01:07:59,510
Θέτουμε την τρέχουσα δείκτη ίσο με το δείκτη ρίζα,

817
01:07:59,510 --> 01:08:04,280
και θα πάμε να εργαστείτε με τον τρόπο μας κάτω από το δέντρο.

818
01:08:04,280 --> 01:08:08,650
Εάν ο τρέχων κόμβος δεν είναι μηδενική, τότε ξέρουμε ότι μπορούμε να μετακινηθεί προς τα κάτω λίγο.

819
01:08:08,650 --> 01:08:12,330
Θέτουμε δείκτης μητρικής μας να είναι ίση με την τρέχουσα δείκτη,

820
01:08:12,330 --> 01:08:15,420
ελεγχθεί η αξία - αν οι τιμές είναι οι ίδιες που επέστρεψε ψευδείς.

821
01:08:15,420 --> 01:08:17,540
Εάν οι τιμές είναι λιγότερο κινηθήκαμε προς τα δεξιά?

822
01:08:17,540 --> 01:08:20,399
αλλιώς, κινηθήκαμε προς τα αριστερά.

823
01:08:20,399 --> 01:08:24,220
Στη συνέχεια, χτίζουμε έναν κόμβο. Θα κάνετε ζουμ σε λίγο.

824
01:08:24,220 --> 01:08:31,410
Και εδώ, θα πάμε να προσπαθήσουμε να συνδέσετε έως και τις αξίες να είναι το ίδιο.

825
01:08:31,410 --> 01:08:37,250
Τι συμβαίνει; Ας δούμε αν ενδεχομένως Valgrind μπορεί να μας δώσει μια ιδέα.

826
01:08:37,250 --> 01:08:43,910
>> Μου αρέσει να χρησιμοποιώ μόνο και μόνο επειδή Valgrind Valgrind τρέχει πολύ γρήγορα

827
01:08:43,910 --> 01:08:46,729
και σας λέει αν υπάρχουν σφάλματα μνήμης.

828
01:08:46,729 --> 01:08:48,300
Όταν τρέχουμε Valgrind σχετικά με τον κώδικα,

829
01:08:48,300 --> 01:08:55,859
όπως μπορείτε να δείτε δεξιά χτύπημα here--Valgrind./binary_tree--and εισάγετε.

830
01:08:55,859 --> 01:09:03,640
Βλέπετε ότι δεν είχαμε κανένα σφάλμα μνήμης, έτσι ώστε να φαίνεται σαν όλα είναι εντάξει τώρα.

831
01:09:03,640 --> 01:09:07,529
Έχουμε κάποιες διαρροές μνήμης, που γνωρίζουμε, γιατί δεν είμαστε

832
01:09:07,529 --> 01:09:08,910
συμβαίνει να ελευθερώσει κάποια από κόμβους μας.

833
01:09:08,910 --> 01:09:13,050
Ας προσπαθήσουμε τρέχει GDB για να δείτε τι πραγματικά συμβαίνει.

834
01:09:13,050 --> 01:09:20,010
Θα κάνουμε το gdb. / Binary_tree. Η εκκίνηση του μια χαρά.

835
01:09:20,010 --> 01:09:23,670
Ας ορίσετε ένα σημείο καμπής στο ένθετο.

836
01:09:23,670 --> 01:09:28,600
Ας τρέξει.

837
01:09:28,600 --> 01:09:31,200
Μοιάζει ποτέ στην πραγματικότητα ονομάζεται ένθετο.

838
01:09:31,200 --> 01:09:39,410
Μοιάζει με το πρόβλημα ήταν μόνο ότι όταν άλλαξα εδώ κάτω στην κύρια -

839
01:09:39,410 --> 01:09:44,279
όλες αυτές τις κλήσεις από printf περιέχει -

840
01:09:44,279 --> 01:09:56,430
Ποτέ δεν άλλαξε στην πραγματικότητα αυτά να καλέσετε ένθετο.

841
01:09:56,430 --> 01:10:01,660
Τώρα ας δώσει μια δοκιμή. Ας σύνταξη.

842
01:10:01,660 --> 01:10:09,130
Όλα φαίνεται καλό εκεί. Τώρα ας προσπαθήσουμε να τρέχει, να δούμε τι θα συμβεί.

843
01:10:09,130 --> 01:10:13,320
Εντάξει! Τα πάντα φαίνεται αρκετά καλό εκεί.

844
01:10:13,320 --> 01:10:18,130
>> Το τελευταίο πράγμα που πρέπει να σκεφτούμε είναι, είναι οι περιπτώσεις άκρη σε αυτό το ένθετο εκεί;

845
01:10:18,130 --> 01:10:23,170
Και αποδεικνύεται ότι, καλά, η μία περίπτωση άκρη που είναι πάντα ενδιαφέρον να σκεφτούμε

846
01:10:23,170 --> 01:10:26,250
είναι, τι θα συμβεί αν το δέντρο σας είναι άδειο και σας καλούν αυτή τη λειτουργία ένθετο;

847
01:10:26,250 --> 01:10:30,330
Θα λειτουργήσει; Λοιπόν, ας δώσει μια δοκιμή.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Ο τρόπος με τον οποίο πρόκειται να δοκιμάσουν αυτό, θα πάμε για να πάει κάτω με το κύριο έργο μας,

850
01:10:35,810 --> 01:10:41,690
και όχι καλωδίωση αυτούς τους κόμβους σαν αυτό,

851
01:10:41,690 --> 01:10:56,730
είμαστε ακριβώς πρόκειται να σχολιάσει το όλο πράγμα,

852
01:10:56,730 --> 01:11:02,620
και αντί της καλωδίωσης μέχρι τους κόμβους τους εαυτούς μας,

853
01:11:02,620 --> 01:11:09,400
μπορούμε πραγματικά να απλά να προχωρήσει και να διαγράψετε όλα αυτά.

854
01:11:09,400 --> 01:11:17,560
Εμείς πάμε για να κάνει ό, τι μια κλήση για να εισάγετε.

855
01:11:17,560 --> 01:11:49,020
Οπότε, ας το κάνουμε - αντί για 5, 8, και 2, θα πάμε για να εισάγετε 7, 3, και 9.

856
01:11:49,020 --> 01:11:58,440
Και στη συνέχεια, θα ήθελα επίσης να τοποθετήσετε 6, καθώς και.

857
01:11:58,440 --> 01:12:05,190
Αποθήκευση. Quit. Κάντε δυαδικό δέντρο.

858
01:12:05,190 --> 01:12:08,540
Θα συγκεντρώνει όλα.

859
01:12:08,540 --> 01:12:10,320
Μπορούμε απλά να τρέξετε είναι όπως και να δούμε τι θα συμβεί,

860
01:12:10,320 --> 01:12:12,770
αλλά είναι επίσης πρόκειται να είναι πραγματικά σημαντικό να βεβαιωθείτε ότι

861
01:12:12,770 --> 01:12:14,740
δεν έχουμε κανένα σφάλματα μνήμης,

862
01:12:14,740 --> 01:12:16,840
δεδομένου ότι αυτό είναι ένα από περιπτώσεις ακμής μας ότι ξέρουμε περίπου.

863
01:12:16,840 --> 01:12:20,150
>> Ας βεβαιωθείτε ότι λειτουργεί καλά κάτω από Valgrind,

864
01:12:20,150 --> 01:12:28,310
που θα κάνουμε με ακριβώς τρέχει Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Μοιάζει έχουμε πράγματι ένα λάθος από ένα πλαίσιο -

866
01:12:31,110 --> 01:12:33,790
έχουμε αυτό το σφάλμα κατάτμησης.

867
01:12:33,790 --> 01:12:36,690
Τι συνέβη;

868
01:12:36,690 --> 01:12:41,650
Valgrind μας λέει στην πραγματικότητα όπου είναι.

869
01:12:41,650 --> 01:12:43,050
Σμίκρυνση λίγο.

870
01:12:43,050 --> 01:12:46,040
Μοιάζει με αυτό που συμβαίνει σε λειτουργία ένθετο μας,

871
01:12:46,040 --> 01:12:53,420
όπου έχουμε μια μη έγκυρη ανάγνωση του μεγέθους 4 στο ένθετο, γραμμή 60.

872
01:12:53,420 --> 01:13:03,590
Ας πάμε πίσω και να δούμε τι συμβαίνει εδώ.

873
01:13:03,590 --> 01:13:05,350
Σμίκρυνση πραγματικά γρήγορα.

874
01:13:05,350 --> 01:13:14,230
Θέλω να βεβαιωθείτε ότι δεν πάει στην άκρη της οθόνης ώστε να μπορούμε να δούμε τα πάντα.

875
01:13:14,230 --> 01:13:18,760
Τραβήξτε ότι σε λίγο. Εντάξει.

876
01:13:18,760 --> 01:13:35,030
Μετακινηθείτε προς τα κάτω, και το πρόβλημα είναι ακριβώς εδώ.

877
01:13:35,030 --> 01:13:40,120
Τι θα συμβεί αν πιάσουμε και τρέχοντα κόμβο μας είναι ήδη μηδενική,

878
01:13:40,120 --> 01:13:44,010
κόμβος γονέας μας είναι μηδενική, οπότε αν δούμε πάνω στην κορυφή, δεξιά εδώ -

879
01:13:44,010 --> 01:13:47,340
αν ποτέ αυτό το βρόχο, ενώ στην πραγματικότητα εκτελεί

880
01:13:47,340 --> 01:13:52,330
επειδή η τρέχουσα αξία μας είναι null - ρίζα μας είναι μηδενική τρέχουσα έτσι είναι άκυρη -

881
01:13:52,330 --> 01:13:57,810
τότε μητρική μας παίρνει ποτέ οριστεί σε τρέχουσα ή σε μια έγκυρη τιμή,

882
01:13:57,810 --> 01:14:00,580
έτσι, ο γονέας θα είναι επίσης μηδενική.

883
01:14:00,580 --> 01:14:03,700
Πρέπει να θυμόμαστε για να ελέγξετε ότι

884
01:14:03,700 --> 01:14:08,750
από τη στιγμή που έχουμε εδώ κάτω, και να αρχίσουμε την πρόσβαση αξία της μητρικής.

885
01:14:08,750 --> 01:14:13,190
Λοιπόν, τι θα συμβεί; Λοιπόν, αν ο γονέας είναι null -

886
01:14:13,190 --> 01:14:17,990
αν (μητρική NULL ==) - τότε γνωρίζουμε ότι

887
01:14:17,990 --> 01:14:19,530
δεν πρέπει να υπάρχει τίποτα στο δέντρο.

888
01:14:19,530 --> 01:14:22,030
Θα πρέπει να προσπαθούμε να το τοποθετήσετε στη ρίζα.

889
01:14:22,030 --> 01:14:32,570
Μπορούμε να το κάνουμε αυτό από μόνο τον καθορισμό της ρίζας ίσο με το νέο κόμβο.

890
01:14:32,570 --> 01:14:40,010
Στη συνέχεια, σε αυτό το σημείο, δεν θέλουν να περάσουν από αυτά τα άλλα πράγματα.

891
01:14:40,010 --> 01:14:44,780
Αντ 'αυτού, εδώ, μπορούμε να κάνουμε είτε αλλιώς-if-else,

892
01:14:44,780 --> 01:14:47,610
ή θα μπορούσαμε να συνδυάσουμε τα πάντα εδώ σε ένα άλλο,

893
01:14:47,610 --> 01:14:56,300
αλλά εδώ θα χρησιμοποιούν μόνο άλλο και να το κάνουμε με αυτόν τον τρόπο.

894
01:14:56,300 --> 01:14:59,030
Τώρα, θα πάμε να δοκιμάσετε για να βεβαιωθείτε ότι η μητρική μας δεν είναι null

895
01:14:59,030 --> 01:15:02,160
πριν από τότε πραγματικά προσπαθεί να αποκτήσει πρόσβαση στους τομείς της.

896
01:15:02,160 --> 01:15:05,330
Αυτό θα μας βοηθήσει να αποφύγουμε το σφάλμα κατάτμησης.

897
01:15:05,330 --> 01:15:14,740
Έτσι, θα σταματήσουν, σμίκρυνση, την κατάρτιση, να τρέξει.

898
01:15:14,740 --> 01:15:18,130
>> Δεν υπάρχουν λάθη, αλλά έχουμε ακόμα ένα μάτσο διαρροές μνήμης

899
01:15:18,130 --> 01:15:20,650
γιατί δεν απελευθερώσει κάποιο από τους κόμβους μας.

900
01:15:20,650 --> 01:15:24,350
Αλλά, αν πάμε εδώ και κοιτάμε εκτύπωση μας,

901
01:15:24,350 --> 01:15:30,880
βλέπουμε ότι, επίσης, μοιάζει με όλα τα ένθετα μας επέστρεφαν αληθινό, το οποίο είναι καλό.

902
01:15:30,880 --> 01:15:33,050
Τα ενθέματα είναι όλα αλήθεια,

903
01:15:33,050 --> 01:15:36,670
και στη συνέχεια τα κατάλληλα κλήσεων περιέχει είναι επίσης αλήθεια.

904
01:15:36,670 --> 01:15:41,510
>> Καλή δουλειά! Μοιάζει έχουμε γράψει με επιτυχία ένθετο.

905
01:15:41,510 --> 01:15:47,430
Αυτό είναι το μόνο που έχουμε για προδιαγραφές που Πρόβλημα αυτής της εβδομάδας.

906
01:15:47,430 --> 01:15:51,720
Μια διασκεδαστική πρόκληση να σκεφτούμε είναι το πώς θα πάμε πραγματικά σε

907
01:15:51,720 --> 01:15:55,340
και ελεύθερη όλοι οι κόμβοι σε αυτό το δέντρο.

908
01:15:55,340 --> 01:15:58,830
Μπορούμε να κάνουμε έτσι έναν αριθμό από διαφορετικούς τρόπους,

909
01:15:58,830 --> 01:16:01,930
αλλά εγώ θα φύγω ότι μέχρι σας να πειραματιστούν,

910
01:16:01,930 --> 01:16:06,080
και ως πρόκληση διασκέδαση, δοκιμάστε και να βεβαιωθείτε ότι μπορείτε να βεβαιωθείτε ότι

911
01:16:06,080 --> 01:16:09,490
ότι η έκθεση αυτή δεν επιστρέφει Valgrind λάθη και δεν υπάρχουν διαρροές.

912
01:16:09,490 --> 01:16:12,880
>> Καλή τύχη στο σύνολο Huffman πρόβλημα αυτής της εβδομάδας κωδικοποίηση,

913
01:16:12,880 --> 01:16:14,380
και θα τα πούμε την επόμενη εβδομάδα!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]