1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Ενότητα 7: Άνετα Περισσότερα]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Πανεπιστήμιο του Χάρβαρντ]

3
00:00:05,090 --> 00:00:07,930
[Αυτό είναι CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Εντάξει. Έτσι, όπως είπα και στο e-mail μου,

5
00:00:10,110 --> 00:00:14,060
αυτό πρόκειται να είναι ένα δυαδικό δέντρο-υψηλής έντασης τμήμα.

6
00:00:14,060 --> 00:00:16,820
Υπάρχουν, όμως, δεν είναι ότι πολλά ερωτήματα.

7
00:00:16,820 --> 00:00:18,920
Έτσι θα πάμε για να προσπαθήσουμε και να σύρει έξω κάθε ερώτηση

8
00:00:18,920 --> 00:00:25,430
και να πάει σε οδυνηρές λεπτομέρειες όλων των καλύτερους τρόπους για να κάνουμε πράγματα.

9
00:00:25,430 --> 00:00:31,200
Έτσι, το δικαίωμα στην αρχή, περνάμε σχέδια δείγμα των δυαδικών δέντρων και πράγματα.

10
00:00:31,200 --> 00:00:35,970
Έτσι, εδώ, "Να θυμάστε ότι ένα δυαδικό δέντρο έχει κόμβους παρόμοιες με εκείνες ενός συνδεδεμένη λίστα,

11
00:00:35,970 --> 00:00:38,150
εκτός αντί για ένα δείκτη υπάρχουν δύο: ένα για «παιδί» της Αριστεράς

12
00:00:38,150 --> 00:00:41,950
και μία για το δεξί «παιδί».

13
00:00:41,950 --> 00:00:45,630
Έτσι, ένα δυαδικό δέντρο είναι ακριβώς όπως μια συνδεδεμένη λίστα,

14
00:00:45,630 --> 00:00:47,910
εκτός από το struct πρόκειται να έχει δύο δείκτες.

15
00:00:47,910 --> 00:00:51,390
Υπάρχει trinary δέντρα, τα οποία θα έχουν τρεις δείκτες,

16
00:00:51,390 --> 00:00:56,540
υπάρχουν Ν-ary δέντρα, τα οποία έχουν μόνο ένα γενικό δείκτη

17
00:00:56,540 --> 00:01:00,320
ότι θα πρέπει στη συνέχεια να malloc να είναι αρκετά μεγάλη ώστε να έχουν

18
00:01:00,320 --> 00:01:04,840
αρκετά δείκτες σε όλες τις πιθανές παιδιά.

19
00:01:04,840 --> 00:01:08,200
Έτσι δυαδικό δέντρο που συμβαίνει μόνο για να έχουν ένα σταθερό αριθμό δύο.

20
00:01:08,200 --> 00:01:11,260
Αν θέλετε, μπορείτε να δώσετε μια συνδεδεμένη λίστα ως μοναδιαίο δέντρο,

21
00:01:11,260 --> 00:01:15,360
αλλά δεν νομίζω ότι κάποιος ονομάζει αυτό.

22
00:01:15,360 --> 00:01:18,060
"Σχεδιάστε ένα κουτιά και βέλη-διάγραμμα του κόμβου ενός δυαδικού δέντρου

23
00:01:18,060 --> 00:01:24,110
που περιέχει το αγαπημένο αριθμό του Nate, 7, όπου το κάθε παιδί δείκτης είναι άκυρη. "

24
00:01:24,110 --> 00:01:27,780
Έτσι iPad λειτουργία.

25
00:01:27,780 --> 00:01:30,280
>> Είναι πρόκειται να είναι αρκετά απλή.

26
00:01:30,280 --> 00:01:36,150
Εμείς απλά θα έχουν έναν κόμβο, θα το συντάξει ως ένα τετράγωνο.

27
00:01:36,150 --> 00:01:38,730
Και εγώ θα συντάξει τις τιμές εδώ.

28
00:01:38,730 --> 00:01:41,090
Έτσι, η τιμή θα πέσει μέσα εδώ,

29
00:01:41,090 --> 00:01:44,770
και στη συνέχεια κάτω εδώ θα έχουμε το αριστερό δείκτη στο αριστερό και το δεξιό δείκτη στα δεξιά.

30
00:01:44,770 --> 00:01:50,430
Και αυτό είναι πάρα πολύ ώστε σύμβαση να το ονομάσουμε αριστερά και δεξιά, τα ονόματα δείκτη.

31
00:01:50,430 --> 00:01:52,460
Και οι δύο θα είναι μηδενική.

32
00:01:52,460 --> 00:01:57,870
Αυτό θα είναι μόνο άκυρη και ότι απλά θα είναι μηδενική.

33
00:01:57,870 --> 00:02:03,630
Εντάξει. Έτσι, πίσω στο εδώ.

34
00:02:03,630 --> 00:02:05,700
"Με μια συνδεδεμένη λίστα, το μόνο που έπρεπε να αποθηκεύουν ένα δείκτη

35
00:02:05,700 --> 00:02:09,639
στον πρώτο κόμβο της λίστας, ώστε να θυμούνται ολόκληρο το συνδεδεμένη λίστα, ή ολόκληρη τη λίστα.

36
00:02:09,639 --> 00:02:11,650
Ομοίως, με τα δέντρα, δεν έχουμε παρά να αποθηκεύσετε ένα δείκτη

37
00:02:11,650 --> 00:02:13,420
σε ένα μόνο κόμβο, προκειμένου να θυμούνται ολόκληρο το δέντρο.

38
00:02:13,420 --> 00:02:15,980
Αυτός ο κόμβος είναι calle η «ρίζα» του δέντρου.

39
00:02:15,980 --> 00:02:18,320
Κατασκευάστηκε κατά διάγραμμα σας από πριν ή να σχεδιάσετε ένα νέο

40
00:02:18,320 --> 00:02:21,690
έτσι ώστε να έχετε μια κιβώτια-και-βέλη απεικόνιση ενός δυαδικού δέντρου

41
00:02:21,690 --> 00:02:25,730
με το η τιμή 7, μετά 3 στο αριστερό,

42
00:02:25,730 --> 00:02:32,760
τότε 9 σχετικά με το δικαίωμα, και στη συνέχεια 6 σχετικά με το δικαίωμα του 3. "

43
00:02:32,760 --> 00:02:34,810
Ας δούμε αν μπορώ να θυμηθώ όλα αυτά στο κεφάλι μου.

44
00:02:34,810 --> 00:02:37,670
Έτσι, αυτό πρόκειται να είναι ρίζα μας εδώ.

45
00:02:37,670 --> 00:02:41,600
Θα έχουμε κάποια δείκτη, κάπου κάτι που θα καλέσουμε ρίζα,

46
00:02:41,600 --> 00:02:45,140
και αυτό είναι που δείχνουν προς αυτόν τον τύπο.

47
00:02:45,140 --> 00:02:48,490
Τώρα για να κάνει ένα νέο κόμβο,

48
00:02:48,490 --> 00:02:52,870
τι έχουμε, 3 στο αριστερό;

49
00:02:52,870 --> 00:02:57,140
Έτσι, ένας νέος κόμβος με 3, και επισημαίνει αρχικά άκυρη.

50
00:02:57,140 --> 00:02:59,190
Θα βάλω ακριβώς Ν.

51
00:02:59,190 --> 00:03:02,250
Τώρα θέλουμε να κάνουμε ότι πάμε προς τα αριστερά του 7.

52
00:03:02,250 --> 00:03:06,840
Έτσι θα αλλάξουμε αυτό το δείκτη να επισημάνω τώρα με αυτόν τον τύπο.

53
00:03:06,840 --> 00:03:12,420
Και εμείς κάνουμε το ίδιο. Θέλουμε ένα 9 εδώ

54
00:03:12,420 --> 00:03:14,620
το οποίο αρχικά μόνο λέει null.

55
00:03:14,620 --> 00:03:19,600
Εμείς πάμε για να αλλάξει αυτό το δείκτη, το σημείο έως 9,

56
00:03:19,600 --> 00:03:23,310
και τώρα θέλετε να βάλετε 6 στο δικαίωμα της 3.

57
00:03:23,310 --> 00:03:32,170
Έτσι πρόκειται να - κάνει 6.

58
00:03:32,170 --> 00:03:34,310
Και αυτός ο τύπος θα δείξει εκεί.

59
00:03:34,310 --> 00:03:38,320
Εντάξει. Έτσι, αυτό είναι το μόνο που μας ζητάει να κάνουμε.

60
00:03:38,320 --> 00:03:42,770
>> Τώρα ας πάμε πάνω από κάποια ορολογία.

61
00:03:42,770 --> 00:03:46,690
Έχουμε ήδη μιλήσει για το πώς η ρίζα του δέντρου είναι η κορυφαία-πιο κόμβος στο δέντρο.

62
00:03:46,690 --> 00:03:54,720
Το ένα περιέχει 7. Οι κόμβοι στο κάτω μέρος του δέντρου που ονομάζεται τα φύλλα.

63
00:03:54,720 --> 00:04:01,240
Κάθε κόμβος που μόλις έχει μηδενική, όπως τα παιδιά του είναι ένα φύλλο.

64
00:04:01,240 --> 00:04:03,680
Έτσι είναι δυνατόν, αν δυαδικού δένδρου μας είναι ένα μόνο κόμβο,

65
00:04:03,680 --> 00:04:10,130
ότι ένα δέντρο είναι ένα φύλλο, και αυτό είναι αυτό.

66
00:04:10,130 --> 00:04:12,060
"Το« ύψος »του δέντρου είναι ο αριθμός του λυκίσκου που έχετε να κάνετε

67
00:04:12,060 --> 00:04:16,620
για να πάρει από την κορυφή σε ένα φύλλο. "

68
00:04:16,620 --> 00:04:18,640
Θα μπει σε μια δεύτερη, η διαφορά

69
00:04:18,640 --> 00:04:21,940
μεταξύ ισορροπημένη και μη ισορροπημένη δυαδικά δένδρα,

70
00:04:21,940 --> 00:04:29,470
αλλά για τώρα, το συνολικό ύψος του δέντρου

71
00:04:29,470 --> 00:04:34,520
Θα έλεγα ότι είναι 3, ενώ αν συμπεριλάβουμε και τον αριθμό του λυκίσκου

72
00:04:34,520 --> 00:04:39,710
που έχετε να κάνετε για να φτάσετε στο 9, τότε είναι πραγματικά μόνο ένα ύψος 2.

73
00:04:39,710 --> 00:04:43,340
Αυτή τη στιγμή αυτό είναι μια μη ισορροπημένη δυαδικό δέντρο,

74
00:04:43,340 --> 00:04:49,840
αλλά θα μιλήσει για ισορροπημένη όταν παίρνει να είναι σχετικό.

75
00:04:49,840 --> 00:04:52,040
Έτσι, τώρα μπορούμε να μιλήσουμε για τους κόμβους σε ένα δέντρο σε όρους

76
00:04:52,040 --> 00:04:54,700
σε σχέση με τους άλλους κόμβους στο δέντρο.

77
00:04:54,700 --> 00:04:59,730
Έτσι τώρα έχουμε γονείς, παιδιά, αδέλφια, τους προγόνους και τους απογόνους.

78
00:04:59,730 --> 00:05:05,650
Είναι αρκετά κοινή λογική, τι σημαίνουν.

79
00:05:05,650 --> 00:05:09,610
Αν ρωτήσουμε - οι γονείς του.

80
00:05:09,610 --> 00:05:12,830
Έτσι ποια είναι η μητρική του 3;

81
00:05:12,830 --> 00:05:16,090
[Φοιτητές] 7. Ναι >>. Ο γονέας είναι ακριβώς πρόκειται να είναι αυτό που δείχνει σας.

82
00:05:16,090 --> 00:05:20,510
Τότε ποια είναι τα παιδιά από 7;

83
00:05:20,510 --> 00:05:23,860
[Φοιτητές] 3 και 9. Ναι >>.

84
00:05:23,860 --> 00:05:26,460
Σημειώστε ότι "τα παιδιά" σημαίνει κυριολεκτικά τα παιδιά,

85
00:05:26,460 --> 00:05:31,010
έτσι 6 δεν θα εφαρμοστεί, διότι είναι σαν ένα εγγόνι.

86
00:05:31,010 --> 00:05:35,540
Στη συνέχεια, όμως, αν πάμε απογόνους, ναι, ποιες είναι οι απόγονοι των 7;

87
00:05:35,540 --> 00:05:37,500
[Φοιτητές] 3, 6 και 9. Ναι >>.

88
00:05:37,500 --> 00:05:42,330
Οι απόγονοι του ριζικού κόμβου θα είναι πάντα στο δέντρο,

89
00:05:42,330 --> 00:05:47,950
εκτός ίσως από την ίδια ρίζα, αν δεν θέλετε να θεωρούν ότι ένας απόγονος.

90
00:05:47,950 --> 00:05:50,750
Και, τέλος, τους προγόνους, γι 'αυτό είναι η αντίθετη κατεύθυνση.

91
00:05:50,750 --> 00:05:55,740
Έτσι, ποιες είναι οι πρόγονοι των 6;

92
00:05:55,740 --> 00:05:58,920
[Φοιτητές] 3 και 7. Ναι >>. 9 δεν περιλαμβάνεται.

93
00:05:58,920 --> 00:06:02,520
Είναι ακριβώς η άμεση καταγωγή πίσω στη ρίζα

94
00:06:02,520 --> 00:06:13,230
πρόκειται να είναι οι πρόγονοί σας.

95
00:06:13,230 --> 00:06:16,300
>> "Λέμε ότι ένα δυαδικό δέντρο είναι« διέταξε »αν για κάθε κόμβο στο δέντρο,

96
00:06:16,300 --> 00:06:19,530
όλους τους απογόνους του στο αριστερό έχουν μικρότερες τιμές

97
00:06:19,530 --> 00:06:22,890
και όλα αυτά σχετικά με το δικαίωμα να έχει μεγαλύτερες τιμές.

98
00:06:22,890 --> 00:06:27,060
Για παράδειγμα, το δέντρο είναι πάνω από παραγγελθεί αλλά δεν είναι η μόνη δυνατή διευθέτηση διέταξε. "

99
00:06:27,060 --> 00:06:30,180
Πριν φτάσουμε σε αυτό,

100
00:06:30,180 --> 00:06:36,420
ένα διατεταγμένο δυαδικού δένδρου είναι επίσης γνωστή ως ένα δυαδικό δέντρο αναζήτησης.

101
00:06:36,420 --> 00:06:38,660
Εδώ τυχαίνει να αποκαλεί ένα δυαδικό δέντρο διέταξε,

102
00:06:38,660 --> 00:06:41,850
αλλά δεν έχω ακούσει να λέγεται ένα δυαδικό δέντρο διέταξε πριν,

103
00:06:41,850 --> 00:06:46,650
και σε ένα κουίζ που είναι πολύ πιο πιθανό να θέσει δυαδικό δέντρο αναζήτησης.

104
00:06:46,650 --> 00:06:49,250
Είναι ένα και το αυτό,

105
00:06:49,250 --> 00:06:54,580
και είναι σημαντικό να αναγνωρίσουμε τη διάκριση μεταξύ δυαδικό δέντρο και δυαδικό δέντρο αναζήτησης.

106
00:06:54,580 --> 00:06:58,830
Ένα δυαδικό δένδρο είναι απλά ένα δέντρο που δείχνει δύο πράγματα.

107
00:06:58,830 --> 00:07:02,120
Κάθε κόμβος δείχνει δύο πράγματα.

108
00:07:02,120 --> 00:07:06,310
Δεν υπάρχει καμία λογική για τις αξίες που δείχνει.

109
00:07:06,310 --> 00:07:11,370
Έτσι, όπως εδώ, δεδομένου ότι είναι ένα δυαδικό δέντρο αναζήτησης,

110
00:07:11,370 --> 00:07:14,030
γνωρίζουμε ότι αν πάμε αριστερά από 7,

111
00:07:14,030 --> 00:07:16,670
τότε όλες οι τιμές που μπορεί ενδεχομένως να φθάσουν

112
00:07:16,670 --> 00:07:19,310
πηγαίνοντας από αριστερά 7 πρέπει να είναι μικρότερη από 7.

113
00:07:19,310 --> 00:07:24,070
Παρατηρήστε ότι όλες οι τιμές λιγότερο από 7 είναι 3 και 6.

114
00:07:24,070 --> 00:07:26,040
Αυτές είναι όλες προς τα αριστερά της 7.

115
00:07:26,040 --> 00:07:29,020
Αν πάμε προς τα δεξιά του 7, τα πάντα πρέπει να είναι μεγαλύτερη από 7,

116
00:07:29,020 --> 00:07:33,220
9 είναι έτσι το δικαίωμα των 7, έτσι είμαστε καλοί.

117
00:07:33,220 --> 00:07:36,150
Αυτή δεν είναι η περίπτωση για ένα δυαδικό δέντρο,

118
00:07:36,150 --> 00:07:40,020
για ένα κανονικό δυαδικού δένδρου που μπορούμε να έχουμε μόνο 3 στην κορυφή, 7 προς τα αριστερά,

119
00:07:40,020 --> 00:07:47,630
9 προς τα αριστερά του 7? Δεν υπάρχει διάταξη των τιμών απολύτως.

120
00:07:47,630 --> 00:07:56,140
Τώρα, εμείς δεν θα κάνουμε πραγματικότητα αυτό γιατί είναι κουραστική και περιττή,

121
00:07:56,140 --> 00:07:59,400
αλλά «θέλουμε να βγάλουμε όσες διέταξε δέντρα, όπως μπορείτε να σκεφτείτε

122
00:07:59,400 --> 00:08:01,900
χρησιμοποιώντας τους αριθμούς 7, 3, 9, και 6.

123
00:08:01,900 --> 00:08:06,800
Πόσες διαφορετικές ρυθμίσεις υπάρχουν; Ποιο είναι το ύψος του κάθε ένα; "

124
00:08:06,800 --> 00:08:10,480
>> Θα κάνουμε ένα ζευγάρι, αλλά η βασική ιδέα είναι,

125
00:08:10,480 --> 00:08:16,530
αυτό είναι με κανένα τρόπο μία μοναδική αναπαράσταση ενός δυαδικού δένδρου που περιέχει αυτές τις τιμές.

126
00:08:16,530 --> 00:08:22,760
Το μόνο που χρειαζόμαστε είναι μερικά δυαδικό δέντρο που περιέχει 7, 3, 6, και 9.

127
00:08:22,760 --> 00:08:25,960
Μια άλλη πιθανή έγκυρη θα είναι η ρίζα είναι 3,

128
00:08:25,960 --> 00:08:30,260
πάει προς τα αριστερά και είναι 6, πηγαίνετε προς τα αριστερά και είναι 7,

129
00:08:30,260 --> 00:08:32,730
πηγαίνουν προς τα αριστερά και είναι 9.

130
00:08:32,730 --> 00:08:36,169
Αυτό είναι ένα απολύτως έγκυρο δέντρο δυαδική αναζήτηση.

131
00:08:36,169 --> 00:08:39,570
Δεν είναι πολύ χρήσιμο, επειδή είναι ακριβώς όπως μια συνδεδεμένη λίστα

132
00:08:39,570 --> 00:08:43,750
και όλες αυτές οι δείκτες είναι ακριβώς μηδενική.

133
00:08:43,750 --> 00:08:48,900
Αλλά είναι μια έγκυρη δέντρο. Ναι;

134
00:08:48,900 --> 00:08:51,310
[Φοιτητικό] Μην οι τιμές πρέπει να είναι μεγαλύτερη στα δεξιά;

135
00:08:51,310 --> 00:08:56,700
Ή είναι αυτό -; >> Αυτά εννοούσα να πάει ο άλλος τρόπος.

136
00:08:56,700 --> 00:09:00,960
Υπάρχει, επίσης, - ναι, ας αλλάξουν αυτό.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Καλή αλιευμάτων.

138
00:09:07,770 --> 00:09:11,730
Θα πρέπει ακόμη να υπακούσει τι ένα δυαδικό δέντρο αναζήτησης πρόκειται να κάνει.

139
00:09:11,730 --> 00:09:15,650
Έτσι τα πάντα προς τα αριστερά πρέπει να είναι μικρότερη από ένα οποιοδήποτε δεδομένο κόμβο.

140
00:09:15,650 --> 00:09:23,180
Θα μπορούσαν απλώς να μετακομίσουν, ας πούμε, αυτό το 6 και το βάζουμε εδώ.

141
00:09:23,180 --> 00:09:26,880
Όχι, δεν μπορούμε. Γιατί μπορώ να συνεχίσω να το κάνω αυτό;

142
00:09:26,880 --> 00:09:35,350
Ας κάνουμε - εδώ είναι 6, εδώ είναι 7, 6 πόντους και 3.

143
00:09:35,350 --> 00:09:39,290
Αυτή εξακολουθεί να είναι ένα έγκυρο δέντρο δυαδική αναζήτηση.

144
00:09:39,290 --> 00:09:49,260
Ποιο είναι το πρόβλημα αν εγώ - ας δούμε αν μπορώ να καταλήξουμε σε μια συμφωνία.

145
00:09:49,260 --> 00:09:52,280
Ναι, εντάξει. Έτσι τι είναι λάθος με αυτό το δέντρο;

146
00:09:52,280 --> 00:10:08,920
Υποθέτω ότι έχω ήδη δώσει έναν υπαινιγμό ότι υπάρχει κάτι λάθος με αυτό.

147
00:10:08,920 --> 00:10:14,430
Γιατί μπορώ να συνεχίσω να το κάνω αυτό;

148
00:10:14,430 --> 00:10:18,510
Εντάξει. Αυτό φαίνεται λογικό.

149
00:10:18,510 --> 00:10:22,590
Αν κοιτάξουμε σε κάθε κόμβο, όπως το 7, τότε στα αριστερά του 7 είναι ένα 3.

150
00:10:22,590 --> 00:10:24,960
Έτσι έχουμε 3, το πράγμα στα δεξιά του 3 είναι 6.

151
00:10:24,960 --> 00:10:27,750
Και αν κοιτάξετε 6, το πράγμα προς τα δεξιά του 6 είναι ένα 9.

152
00:10:27,750 --> 00:10:30,910
Γιατί, λοιπόν, είναι αυτή δεν είναι έγκυρη δέντρο δυαδικής αναζήτησης;

153
00:10:30,910 --> 00:10:36,330
[Φοιτητές] 9 εξακολουθεί να είναι προς τα αριστερά της 7. Ναι >>.

154
00:10:36,330 --> 00:10:43,710
Πρέπει να είναι αλήθεια ότι όλες οι τιμές που μπορείτε ενδεχομένως να φτάσει, πηγαίνοντας προς τα αριστερά του 7 είναι μικρότερο του 7.

155
00:10:43,710 --> 00:10:49,120
Αν πάμε αριστερά 7, έχουμε την ευκαιρία να 3 και μπορούμε ακόμα να πάρετε έως 6,

156
00:10:49,120 --> 00:10:52,520
μπορούμε ακόμα να πάρετε έως 9, αλλά έχοντας περάσει λιγότερο από 7,

157
00:10:52,520 --> 00:10:55,070
δεν θα πρέπει να είναι σε θέση να πάρει σε έναν αριθμό που είναι μεγαλύτερο από 7.

158
00:10:55,070 --> 00:10:59,830
Έτσι, αυτό δεν είναι ένα έγκυρο δέντρο δυαδική αναζήτηση.

159
00:10:59,830 --> 00:11:02,330
>> Ο αδελφός μου είχε πραγματικά μια ερώτηση συνέντευξης

160
00:11:02,330 --> 00:11:07,760
αυτό ήταν βασικά αυτό, απλά κωδικός κάτι για την επικύρωση

161
00:11:07,760 --> 00:11:10,500
αν ένα δένδρο είναι ένα δυαδικό δέντρο αναζήτησης,

162
00:11:10,500 --> 00:11:13,580
και έτσι το πρώτο πράγμα που έκανε ήταν απλά να ελέγξετε

163
00:11:13,580 --> 00:11:17,020
αν η αριστερά και δεξιά είναι σωστές και, στη συνέχεια επαναλάβει εκεί κάτω.

164
00:11:17,020 --> 00:11:19,700
Αλλά δεν μπορείτε να το κάνετε απλά ότι? Θα πρέπει να παρακολουθείτε

165
00:11:19,700 --> 00:11:22,550
από το γεγονός ότι τώρα που έχω φύγει από αριστερά 7,

166
00:11:22,550 --> 00:11:26,340
τα πάντα σε αυτό το υποδένδρο πρέπει να είναι μικρότερο του 7.

167
00:11:26,340 --> 00:11:28,430
Η σωστή αλγόριθμος πρέπει να παρακολουθείτε

168
00:11:28,430 --> 00:11:35,970
από τα όρια που οι τιμές μπορούν ενδεχομένως να πέσει μέσα

169
00:11:35,970 --> 00:11:38,360
Δεν θα περάσουν από όλα αυτά.

170
00:11:38,360 --> 00:11:41,630
Υπάρχει μια ωραία σχέση επανάληψης,

171
00:11:41,630 --> 00:11:44,810
αν και δεν έχουμε φτάσει σε αυτούς, ή δεν θα πάρετε σε αυτές,

172
00:11:44,810 --> 00:11:47,030
τον καθορισμό πόσα πραγματικά υπάρχουν.

173
00:11:47,030 --> 00:11:53,180
Έτσι, υπάρχουν 14 από αυτά.

174
00:11:53,180 --> 00:11:56,020
Η ιδέα για το πώς θα το κάνουμε είναι σαν μαθηματικά,

175
00:11:56,020 --> 00:11:59,770
μπορείτε να επιλέξετε οποιαδήποτε έστω και έναν να είναι ο κόμβος ρίζα,

176
00:11:59,770 --> 00:12:03,160
και στη συνέχεια, αν έχω πάρει 7 να είναι ο κόμβος ρίζα,

177
00:12:03,160 --> 00:12:08,150
τότε υπάρχουν, λένε, ορισμένοι αριθμοί που μπορεί να πάει να είναι το αριστερό κόμβο μου,

178
00:12:08,150 --> 00:12:10,440
και υπάρχουν κάποιοι αριθμοί που μπορεί να είναι σωστό κόμβο μου,

179
00:12:10,440 --> 00:12:15,090
αλλά αν έχω n ο συνολικός αριθμός, τότε το ποσό που μπορεί να πάει προς τα αριστερά

180
00:12:15,090 --> 00:12:18,820
συν το ποσό που μπορεί να πάει προς τα δεξιά είναι n - 1.

181
00:12:18,820 --> 00:12:26,130
Έτσι από τους υπόλοιπους αριθμούς, θα πρέπει να είναι σε θέση να πάει είτε προς τα αριστερά ή τα δεξιά.

182
00:12:26,130 --> 00:12:31,580
Φαίνεται ότι είναι δύσκολο, αν έβαλα 3 πρώτο, τότε τα πάντα πρέπει να πάει προς τα αριστερά,

183
00:12:31,580 --> 00:12:35,080
αλλά αν έβαλα 7, τότε κάποια πράγματα που μπορεί να πάει το αριστερό και κάποια πράγματα που μπορούν να πάνε προς τα δεξιά.

184
00:12:35,080 --> 00:12:39,570
Και από '3 πρώτη «Εννοούσα τα πάντα μπορεί να πάει προς τα δεξιά.

185
00:12:39,570 --> 00:12:42,350
Είναι πραγματικά, απλά πρέπει να το σκεφτώ, όπως,

186
00:12:42,350 --> 00:12:47,980
πόσα πράγματα μπορούν να πάνε στο επόμενο επίπεδο του δέντρου.

187
00:12:47,980 --> 00:12:50,420
Και αυτό βγαίνει να είναι 14? Ή μπορείτε να σχεδιάσετε όλα αυτά,

188
00:12:50,420 --> 00:12:54,650
και στη συνέχεια θα πάρει 14.

189
00:12:54,650 --> 00:13:01,120
>> Πηγαίνοντας πίσω εδώ,

190
00:13:01,120 --> 00:13:03,510
"Καταδικάζει δυαδικά δέντρα είναι δροσερά, επειδή μπορούμε να ψάξουμε μέσα από αυτά

191
00:13:03,510 --> 00:13:06,910
με πολύ παρόμοιο τρόπο με την αναζήτηση σε ταξινομημένο πίνακα.

192
00:13:06,910 --> 00:13:10,120
Για να γίνει αυτό, ξεκινάμε από τη ρίζα και το έργο μας κάτω από το δέντρο

193
00:13:10,120 --> 00:13:13,440
προς τα φύλλα, τον έλεγχο των τιμών του κάθε κόμβου σχέση με τις τιμές που αναζητάτε.

194
00:13:13,440 --> 00:13:15,810
Εάν η τιμή του τρέχοντος κόμβου είναι μικρότερη από την τιμή που ψάχνουμε,

195
00:13:15,810 --> 00:13:18,050
πηγαίνετε δίπλα στο δεξί παιδί του κόμβου.

196
00:13:18,050 --> 00:13:20,030
Διαφορετικά, πηγαίνετε στο αριστερό παιδί του κόμβου.

197
00:13:20,030 --> 00:13:22,800
Σε κάποιο σημείο, θα βρείτε είτε την αξία που ψάχνετε, ή θα τρέξει σε ένα null,

198
00:13:22,800 --> 00:13:28,520
που υποδηλώνει την τιμή δεν είναι στο δέντρο. "

199
00:13:28,520 --> 00:13:32,450
Έχω να ξανασχεδιάσουμε το δέντρο που είχαμε πριν? Που θα λάβει μια δεύτερη.

200
00:13:32,450 --> 00:13:38,280
Αλλά θέλουμε να δούμε αν μέχρι 6, 10, και 1 είναι το δέντρο.

201
00:13:38,280 --> 00:13:49,180
Έτσι, ό, τι ήταν, 7, 9, 3, 6. Εντάξει.

202
00:13:49,180 --> 00:13:52,730
Οι αριθμοί που θέλετε να αναζητήσετε, θέλουμε να δούμε μέχρι 6.

203
00:13:52,730 --> 00:13:55,440
Πώς λειτουργεί αυτός ο αλγόριθμος;

204
00:13:55,440 --> 00:14:03,040
Λοιπόν, έχουμε και κάποια ρίζα δείκτη στο δέντρο μας.

205
00:14:03,040 --> 00:14:12,460
Και εμείς θα πάμε στη ρίζα και να πω, είναι αυτή η τιμή ίση με την τιμή που αναζητάτε;

206
00:14:12,460 --> 00:14:15,000
Έτσι ψάχνουμε για 6, έτσι δεν είναι ίσοι.

207
00:14:15,000 --> 00:14:20,140
Γι 'αυτό και συνεχίζω, και τώρα λέμε, εντάξει, έτσι 6 είναι μικρότερο του 7.

208
00:14:20,140 --> 00:14:23,940
Μήπως αυτό σημαίνει ότι θέλουμε να πάμε προς τα αριστερά, ή θέλουμε να πάμε προς τα δεξιά;

209
00:14:23,940 --> 00:14:27,340
[Φοιτητικό] Αριστερά. Ναι >>.

210
00:14:27,340 --> 00:14:33,340
Είναι πολύ εύκολο, το μόνο που έχετε να κάνετε είναι να συντάξει ένα δυνατό κόμβο του δέντρου

211
00:14:33,340 --> 00:14:37,760
και στη συνέχεια να μην τα - αντί να προσπαθούν να σκέφτονται στο κεφάλι σας,

212
00:14:37,760 --> 00:14:40,020
εντάξει, αν είναι λιγότερο, μπορώ να πάω προς τα αριστερά ή πηγαίνετε το δικαίωμα,

213
00:14:40,020 --> 00:14:43,030
απλά κοιτάζοντας αυτή την εικόνα, είναι πολύ σαφές ότι πρέπει να πάω προς τα αριστερά

214
00:14:43,030 --> 00:14:47,700
αν αυτός ο κόμβος είναι μεγαλύτερη από την αξία που ψάχνω.

215
00:14:47,700 --> 00:14:52,600
Έτσι, πηγαίνετε προς τα αριστερά, τώρα είμαι στο 3.

216
00:14:52,600 --> 00:14:57,770
Θέλω να - 3 είναι μικρότερη από την τιμή που ψάχνω, το οποίο είναι 6.

217
00:14:57,770 --> 00:15:03,420
Γι 'αυτό και πάμε προς τα δεξιά, και τώρα έχω καταλήξει σε 6,

218
00:15:03,420 --> 00:15:07,380
που είναι η αξία που ψάχνω, γι 'αυτό επιστρέφει αλήθεια.

219
00:15:07,380 --> 00:15:15,760
Το επόμενο αξία Πάω να αναζητήσουμε είναι 10.

220
00:15:15,760 --> 00:15:23,230
Εντάξει. Έτσι, 10, τώρα, πρόκειται να - κόψει ότι - πρόκειται να ακολουθήσει τη ρίζα.

221
00:15:23,230 --> 00:15:27,670
Τώρα, 10 πρόκειται να είναι μεγαλύτερο από 7, γι 'αυτό θέλω να κοιτάζω προς τα δεξιά.

222
00:15:27,670 --> 00:15:31,660
Πάω να έρθω εδώ, 10 πρόκειται να είναι μεγαλύτερη από 9,

223
00:15:31,660 --> 00:15:34,520
έτσι είμαι πρόκειται να θέλουν να κοιτάξουμε προς τα δεξιά.

224
00:15:34,520 --> 00:15:42,100
Έρχομαι εδώ, αλλά εδώ τώρα είμαι σε null.

225
00:15:42,100 --> 00:15:44,170
Τι μπορώ να κάνω αν χτυπήσει null;

226
00:15:44,170 --> 00:15:47,440
[Φοιτητικό] Επιστροφή λάθος; Ναι >>. Δεν βρήκα 10.

227
00:15:47,440 --> 00:15:49,800
1 πρόκειται να είναι μια σχεδόν ταυτόσημη περίπτωση,

228
00:15:49,800 --> 00:15:51,950
εκτός του ότι είναι ακριβώς πρόκειται να γυρίσει? αντί να κοιτάμε

229
00:15:51,950 --> 00:15:56,540
κάτω από τη δεξιά πλευρά, Πάω να κοιτάξει κάτω την αριστερή πλευρά.

230
00:15:56,540 --> 00:16:00,430
>> Τώρα νομίζω ότι πραγματικά να πάρει τον κώδικα.

231
00:16:00,430 --> 00:16:04,070
Εδώ είναι όπου - το άνοιγμα της συσκευής CS50 και να περιηγηθείτε το δρόμο σας εκεί,

232
00:16:04,070 --> 00:16:07,010
αλλά μπορείτε να κάνετε ακριβώς αυτό και στο χώρο.

233
00:16:07,010 --> 00:16:09,170
Είναι πιθανώς ιδανικό για να το κάνει στο χώρο,

234
00:16:09,170 --> 00:16:13,760
επειδή μπορούμε να εργαστούμε στο χώρο.

235
00:16:13,760 --> 00:16:19,170
"Πρώτα θα χρειαστείτε ένα νέο ορισμό τύπου για ένα δυαδικό δέντρο κόμβο που περιέχει τιμές τύπου int.

236
00:16:19,170 --> 00:16:21,400
Χρησιμοποιώντας το στερεότυπο typedef παρακάτω,

237
00:16:21,400 --> 00:16:24,510
δημιουργία ενός νέου τύπου για ορισμό ενός κόμβου σε ένα δυαδικό δένδρο.

238
00:16:24,510 --> 00:16:27,930
Αν έχετε κολλήσει. . . «Μπλα, μπλα, μπλα. Εντάξει.

239
00:16:27,930 --> 00:16:30,380
Ας βάλουμε το στερεότυπο εδώ,

240
00:16:30,380 --> 00:16:41,630
typedef struct node, και ο κόμβος. Ναι, εντάξει.

241
00:16:41,630 --> 00:16:44,270
Έτσι, ποια είναι τα πεδία θα πάμε να θέλουν στον κόμβο μας;

242
00:16:44,270 --> 00:16:46,520
[Φοιτητικό] Int και στη συνέχεια δίποντα;

243
00:16:46,520 --> 00:16:49,700
>> Αξία Int, δίποντα; Πώς μπορώ να γράψω τους δείκτες;

244
00:16:49,700 --> 00:16:58,440
[Φοιτητικό] Struct. >> Θα πρέπει να μεγεθύνετε Ναι, έτσι struct node * αριστερά,

245
00:16:58,440 --> 00:17:01,320
και struct node * δικαίωμα.

246
00:17:01,320 --> 00:17:03,460
Και να θυμάστε τη συζήτηση από την τελευταία φορά,

247
00:17:03,460 --> 00:17:15,290
ότι αυτό δεν έχει κανένα νόημα, αυτό δεν έχει κανένα νόημα,

248
00:17:15,290 --> 00:17:18,270
αυτό δεν έχει κανένα νόημα.

249
00:17:18,270 --> 00:17:25,000
Χρειάζεται πάντα εκεί για να καθορίσουν αυτό το αναδρομικό struct.

250
00:17:25,000 --> 00:17:27,970
Εντάξει, έτσι αυτό είναι που μας δέντρο πρόκειται να μοιάσει.

251
00:17:27,970 --> 00:17:37,670
Αν κάναμε ένα trinary δέντρο, στη συνέχεια, ένας κόμβος μπορεί να μοιάζει b1, b2, struct node * b3,

252
00:17:37,670 --> 00:17:43,470
όπου β είναι ένας κλάδος - στην πραγματικότητα, έχω ακούσει πιο αριστερά, κέντρο, δεξιά, αλλά και οτιδήποτε άλλο.

253
00:17:43,470 --> 00:17:55,610
Το μόνο που νοιάζονται για δυαδικό, τόσο δεξιά, αριστερά.

254
00:17:55,610 --> 00:17:59,110
"Δηλώνουν τώρα μια καθολική μεταβλητή * κόμβος για τη ρίζα του δέντρου."

255
00:17:59,110 --> 00:18:01,510
Γι 'αυτό και δεν πρόκειται να το κάνουμε αυτό.

256
00:18:01,510 --> 00:18:08,950
Για να κάνει τα πράγματα λίγο πιο δύσκολο και πιο γενικευμένη,

257
00:18:08,950 --> 00:18:11,570
δεν θα έχουμε μια παγκόσμια μεταβλητό κόμβο.

258
00:18:11,570 --> 00:18:16,710
Αντ 'αυτού, σε κύριο εμείς θα κηρύξει όλα τα πράγματα κόμβο μας,

259
00:18:16,710 --> 00:18:20,500
και αυτό σημαίνει ότι στη συνέχεια, όταν θα αρχίσουν να προβάλλονται

260
00:18:20,500 --> 00:18:23,130
Περιέχει τη λειτουργία μας και τη λειτουργία μας ένθετο,

261
00:18:23,130 --> 00:18:27,410
αντί Περιέχει μας λειτουργούν μόνο με τη χρήση αυτής της παγκόσμιας μεταβλητό κόμβο,

262
00:18:27,410 --> 00:18:34,280
θα πάμε να το πάρετε ως επιχείρημα το δέντρο που θέλουμε να επεξεργαστούμε.

263
00:18:34,280 --> 00:18:36,650
Έχοντας την καθολική μεταβλητή υποτίθεται ότι θα κάνει τα πράγματα ευκολότερα.

264
00:18:36,650 --> 00:18:42,310
Εμείς πάμε για να κάνει τα πράγματα σκληρότερα.

265
00:18:42,310 --> 00:18:51,210
Τώρα πάρτε ένα λεπτό ή έτσι απλά για να κάνουμε αυτό το είδος του πράγματος,

266
00:18:51,210 --> 00:18:57,690
όπου μέσα από τα κύρια θέλετε να δημιουργήσετε αυτό το δέντρο, και αυτό είναι το μόνο που θέλετε να κάνετε.

267
00:18:57,690 --> 00:19:04,530
Δοκιμάστε και να κατασκευάσει αυτό το δέντρο σε κύρια λειτουργία σας.

268
00:19:42,760 --> 00:19:47,610
>> Εντάξει. Έτσι, δεν χρειάζεται καν να έχουν κατασκευαστεί το δέντρο ολόκληρο το δρόμο ακόμα.

269
00:19:47,610 --> 00:19:49,840
Αλλά ο καθένας έχει κάτι που θα μπορούσε να σηκώσει

270
00:19:49,840 --> 00:20:03,130
να δείξει πώς θα μπορούσε κανείς να ξεκινήσει την κατασκευή ενός τέτοιου δέντρο;

271
00:20:03,130 --> 00:20:08,080
[Φοιτητικό] χτυπάς κάποιον, προσπαθώντας να βγει.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Όποιος άνετα με την κατασκευή δέντρο τους;

273
00:20:13,100 --> 00:20:15,520
[Φοιτητικό] Σίγουρα. Δεν το κάνει. >> Είναι μια χαρά. Εμείς μπορούμε απλά να τελειώσει -

274
00:20:15,520 --> 00:20:26,860
Ω, μπορείτε να το αποθηκεύσετε; Ζήτω.

275
00:20:26,860 --> 00:20:32,020
Έτσι, εδώ έχουμε - Ω, είμαι κάπως αποκομμένοι.

276
00:20:32,020 --> 00:20:34,770
Είμαι σε μεγέθυνση;

277
00:20:34,770 --> 00:20:37,730
Μεγέθυνση, μετακινηθείτε προς τα έξω. >> Έχω μια ερώτηση. Ναι >>;

278
00:20:37,730 --> 00:20:44,410
[Φοιτητικό] Όταν ορίζετε struct, είναι τα πράγματα όπως αρχικοποιείται σε τίποτα;

279
00:20:44,410 --> 00:20:47,160
[Bowden] Όχι >> Εντάξει. Έτσι, θα πρέπει να προετοιμαστεί -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Όχι Όταν ορίζετε, ή όταν δηλώνετε μια struct,

281
00:20:50,450 --> 00:20:55,600
δεν ξεκινά από προεπιλογή? είναι ακριβώς όπως αν κηρύξει int.

282
00:20:55,600 --> 00:20:59,020
Είναι ακριβώς το ίδιο πράγμα. Είναι σαν κάθε επιμέρους τομείς της

283
00:20:59,020 --> 00:21:04,460
μπορεί να έχει μια τιμή σκουπίδια σε αυτό. >> Και είναι δυνατόν να καθορίσει - ή να δηλώσει ένα struct

284
00:21:04,460 --> 00:21:07,740
κατά τρόπο ώστε να τους κάνει αρχικοποίηση;

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ναι. Έτσι, σύνταξη προετοιμασίας συντόμευση

286
00:21:13,200 --> 00:21:18,660
πρόκειται να μοιάσει -

287
00:21:18,660 --> 00:21:22,200
Υπάρχουν δύο τρόποι που μπορούμε να το κάνουμε αυτό. Νομίζω ότι πρέπει να το υπολογίσουν

288
00:21:22,200 --> 00:21:25,840
για να βεβαιωθείτε ότι Clang κάνει αυτό επίσης.

289
00:21:25,840 --> 00:21:28,510
Η σειρά των επιχειρημάτων που έρχεται στο struct,

290
00:21:28,510 --> 00:21:32,170
βάζετε ως τη σειρά των επιχειρημάτων μέσα από αυτές τις αγκύλες.

291
00:21:32,170 --> 00:21:35,690
Έτσι, εάν θέλετε να το αρχικοποιήσει έως 9 και άφησε να άκυρη και στη συνέχεια δικαίωμα να είναι μηδενική,

292
00:21:35,690 --> 00:21:41,570
θα ήταν 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Η εναλλακτική λύση είναι, και ο εκδότης δεν ήθελε αυτήν τη σύνταξη,

294
00:21:47,890 --> 00:21:50,300
και πιστεύει θέλω ένα νέο μπλοκ,

295
00:21:50,300 --> 00:22:01,800
αλλά η εναλλακτική λύση είναι κάτι σαν -

296
00:22:01,800 --> 00:22:04,190
εδώ, εγώ θα το θέσω σε μια νέα γραμμή.

297
00:22:04,190 --> 00:22:09,140
Μπορείτε να πείτε ρητά, ξεχνάω την ακριβή σύνταξη.

298
00:22:09,140 --> 00:22:13,110
Έτσι, μπορείτε να απευθυνθείτε ρητά από το όνομα, και λένε,

299
00:22:13,110 --> 00:22:21,570
. Αξία γ, ή. = 9,. Αριστερά = NULL.

300
00:22:21,570 --> 00:22:24,540
Υποθέτω αυτά πρέπει να είναι κόμματα.

301
00:22:24,540 --> 00:22:29,110
. Δεξιά = NULL, ώστε με αυτό τον τρόπο δεν έχετε

302
00:22:29,110 --> 00:22:33,780
πραγματικά χρειάζεται να γνωρίζουν τη σειρά του struct,

303
00:22:33,780 --> 00:22:36,650
και όταν διαβάζετε αυτό, είναι πολύ πιο σαφής

304
00:22:36,650 --> 00:22:41,920
σχετικά με το τι είναι η τιμή που ξεκινά με.

305
00:22:41,920 --> 00:22:44,080
>> Αυτό συμβαίνει να είναι ένα από τα πράγματα που -

306
00:22:44,080 --> 00:22:49,100
έτσι, για το μεγαλύτερο μέρος, C + + είναι υπερσύνολο της C.

307
00:22:49,100 --> 00:22:54,160
Μπορείτε να πάρετε C κώδικα, να το μετακινήσετε πάνω σε C + +, και θα πρέπει να συγκεντρώνουν.

308
00:22:54,160 --> 00:22:59,570
Αυτό είναι ένα από τα πράγματα ότι η C + + δεν υποστηρίζει, ώστε οι άνθρωποι τείνουν να μην το κάνει.

309
00:22:59,570 --> 00:23:01,850
Δεν ξέρω αν αυτός είναι ο μόνος λόγος που οι άνθρωποι έχουν την τάση να μην το κάνει,

310
00:23:01,850 --> 00:23:10,540
αλλά η περίπτωση κατά την οποία έπρεπε να το χρησιμοποιήσετε για να συνεργαστεί με C + + και γι 'αυτό δεν θα μπορούσε να χρησιμοποιήσει αυτό.

311
00:23:10,540 --> 00:23:14,000
Ένα άλλο παράδειγμα από κάτι που δεν λειτουργεί με C + + είναι

312
00:23:14,000 --> 00:23:16,940
πώς malloc επιστρέφει ένα "* κενό,« τεχνικά,

313
00:23:16,940 --> 00:23:20,200
αλλά θα μπορούσαμε να πούμε ακριβώς char * x = οτιδήποτε άλλο malloc,

314
00:23:20,200 --> 00:23:22,840
και αυτόματα θα ρίχνει σε ένα char *.

315
00:23:22,840 --> 00:23:25,450
Ότι η αυτόματη καστ δεν θα συμβεί σε C + +.

316
00:23:25,450 --> 00:23:28,150
Αυτό δεν θα καταρτίσει, και που θα πρέπει ρητά να πω

317
00:23:28,150 --> 00:23:34,510
char *, malloc, όποια και αν είναι, να το ρίχνει σε ένα char *.

318
00:23:34,510 --> 00:23:37,270
Δεν υπάρχουν πολλά πράγματα που C και C + + διαφωνούν,

319
00:23:37,270 --> 00:23:40,620
αλλά αυτά είναι δύο.

320
00:23:40,620 --> 00:23:43,120
Έτσι θα πάμε με αυτή τη σύνταξη.

321
00:23:43,120 --> 00:23:46,150
Αλλά ακόμα και αν δεν είχαμε πάει με το εν λόγω σύνταξη,

322
00:23:46,150 --> 00:23:49,470
τι είναι - θα μπορούσε να είναι λάθος με αυτό;

323
00:23:49,470 --> 00:23:52,170
[Φοιτητικό] δεν χρειάζεται να dereference αυτό; Ναι >>.

324
00:23:52,170 --> 00:23:55,110
Να θυμάστε ότι το βέλος έχει μια σιωπηρή dereference,

325
00:23:55,110 --> 00:23:58,230
και έτσι όταν είμαστε ακριβώς κάνουμε με ένα struct,

326
00:23:58,230 --> 00:24:04,300
θέλουμε να χρησιμοποιήσουμε. για να πάρει μέσα σε ένα πεδίο του struct.

327
00:24:04,300 --> 00:24:07,200
Και η μόνη φορά που θα χρησιμοποιήσετε το βέλος είναι όταν θέλουμε να κάνουμε -

328
00:24:07,200 --> 00:24:13,450
καλά, βέλος είναι ισοδύναμο με -

329
00:24:13,450 --> 00:24:17,020
αυτό είναι ό, τι θα σήμαινε αν χρησιμοποιηθεί βέλος.

330
00:24:17,020 --> 00:24:24,600
Όλα τα μέσα βέλος, dereference αυτό, τώρα είμαι σε μια struct, και μπορώ να πάρω το πεδίο.

331
00:24:24,600 --> 00:24:28,040
Είτε να πάρει το πεδίο άμεσα ή dereference και να πάρει το πεδίο -

332
00:24:28,040 --> 00:24:30,380
Υποθέτω ότι αυτό θα πρέπει να είναι αξία.

333
00:24:30,380 --> 00:24:33,910
Αλλά εδώ είμαι ασχολούνται μόνο με ένα struct δεν είναι, ένα δείκτη σε struct,

334
00:24:33,910 --> 00:24:38,780
και γι 'αυτό δεν μπορεί να χρησιμοποιήσει το βέλος.

335
00:24:38,780 --> 00:24:47,510
Αλλά αυτό το είδος των πράγμα που μπορούμε να κάνουμε για όλους τους κόμβους.

336
00:24:47,510 --> 00:24:55,790
Θεέ μου.

337
00:24:55,790 --> 00:25:09,540
Αυτό είναι 6, 7, και 3.

338
00:25:09,540 --> 00:25:16,470
Στη συνέχεια, μπορούμε να δημιουργήσει τα κλαδιά στο δέντρο μας, μπορούμε να έχουμε 7 -

339
00:25:16,470 --> 00:25:21,650
μπορούμε να έχουμε, αριστερά της πρέπει να παραπέμπει σε 3.

340
00:25:21,650 --> 00:25:25,130
Λοιπόν, πώς θα το κάνουμε αυτό;

341
00:25:25,130 --> 00:25:29,320
[Φοιτητές, ακατάληπτο] >> Ναι. Η διεύθυνση του node3,

342
00:25:29,320 --> 00:25:34,170
και αν δεν έχουν διεύθυνση, τότε απλά δεν θα μεταγλωττίσετε.

343
00:25:34,170 --> 00:25:38,190
Αλλά να θυμάστε ότι αυτά είναι δείκτες για τους επόμενους κόμβους.

344
00:25:38,190 --> 00:25:44,930
Το δικαίωμα αυτό θα πρέπει να το σημείο 9,

345
00:25:44,930 --> 00:25:53,330
και 3 θα πρέπει να επισημάνω σχετικά με το δικαίωμα 6.

346
00:25:53,330 --> 00:25:58,480
Νομίζω ότι αυτό είναι όλα έτοιμα. Οποιαδήποτε σχόλια ή ερωτήσεις;

347
00:25:58,480 --> 00:26:02,060
[Φοιτητών, ακατάληπτο] Η ρίζα θα είναι 7.

348
00:26:02,060 --> 00:26:08,210
Μπορούμε να πούμε μόνο κόμβο * ptr =

349
00:26:08,210 --> 00:26:14,160
ή ρίζα, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Για τους σκοπούς μας, θα πάμε να ασχολούνται με την εισαγωγή,

351
00:26:20,730 --> 00:26:25,490
έτσι θα πάμε να θέλουν να γράψουν μια λειτουργία για την εισαγωγή σε αυτό το δυαδικό δέντρο

352
00:26:25,490 --> 00:26:34,230
και ένθετο αναπόφευκτα θα καλέσει malloc για να δημιουργήσετε ένα νέο κόμβο για αυτό το δέντρο.

353
00:26:34,230 --> 00:26:36,590
Έτσι, τα πράγματα πρόκειται να πάρει βρώμικο με το γεγονός ότι κάποιοι κόμβοι

354
00:26:36,590 --> 00:26:38,590
είναι σήμερα στην στοίβα

355
00:26:38,590 --> 00:26:43,680
και άλλους κόμβους πρόκειται να καταλήξουν στο σωρό όταν τα εισάγετε.

356
00:26:43,680 --> 00:26:47,640
Αυτό είναι απόλυτα έγκυρη, αλλά ο μόνος λόγος

357
00:26:47,640 --> 00:26:49,600
είμαστε σε θέση να το κάνουμε αυτό στη στοίβα

358
00:26:49,600 --> 00:26:51,840
είναι επειδή είναι ένα τέτοιο παράδειγμα σκηνοθετημένη που γνωρίζουμε

359
00:26:51,840 --> 00:26:56,360
το δέντρο υποτίθεται να κατασκευαστεί, όπως 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Αν δεν είχαμε αυτό, τότε δεν θα πρέπει να malloc στην πρώτη θέση.

361
00:27:02,970 --> 00:27:06,160
Όπως θα δούμε λίγο αργότερα, θα πρέπει να malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Αυτή τη στιγμή είναι απολύτως λογικό να θέσει στη στοίβα,

363
00:27:08,570 --> 00:27:14,750
αλλά ας αλλάξουμε αυτό σε εφαρμογή malloc.

364
00:27:14,750 --> 00:27:17,160
Έτσι, κάθε μια από αυτές είναι τώρα πρόκειται να είναι κάτι σαν

365
00:27:17,160 --> 00:27:24,240
κόμβο * node9 = malloc (sizeof (κόμβος)).

366
00:27:24,240 --> 00:27:28,040
Και τώρα θα πάμε να πρέπει να κάνουμε έλεγχο μας.

367
00:27:28,040 --> 00:27:34,010
αν (node9 == NULL) - εγώ δεν θέλω αυτό -

368
00:27:34,010 --> 00:27:40,950
επιστρέψει 1, και στη συνέχεια μπορούμε να κάνουμε node9-> γιατί τώρα είναι ένας δείκτης,

369
00:27:40,950 --> 00:27:45,300
value = 6, node9-> left = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> δεξιά = NULL,

371
00:27:48,930 --> 00:27:51,410
και θα πάμε να πρέπει να το κάνουμε αυτό για κάθε μία από αυτές τις κόμβους.

372
00:27:51,410 --> 00:27:57,490
Έτσι, αντί, ας το βάλει μέσα σε μια ξεχωριστή λειτουργία.

373
00:27:57,490 --> 00:28:00,620
Ας το ονομάσουμε κόμβο * build_node,

374
00:28:00,620 --> 00:28:09,050
και αυτό είναι κάπως παρόμοια με την APIs παρέχουμε για κωδικοποίηση Huffman.

375
00:28:09,050 --> 00:28:12,730
Σας δίνουμε λειτουργίες initializer για ένα δέντρο

376
00:28:12,730 --> 00:28:20,520
και Deconstructor "λειτουργίες" για τα δέντρα και το ίδιο για τα δάση.

377
00:28:20,520 --> 00:28:22,570
>> Έτσι, εδώ θα πάμε να έχουν μια λειτουργία initializer

378
00:28:22,570 --> 00:28:25,170
να χτίσουμε έναν κόμβο για μας.

379
00:28:25,170 --> 00:28:29,320
Και πρόκειται να δούμε λίγο πολύ ακριβώς όπως αυτό.

380
00:28:29,320 --> 00:28:32,230
Και είμαι ακόμα πρόκειται να είναι τεμπέλης και να μην αλλάξει το όνομα της μεταβλητής,

381
00:28:32,230 --> 00:28:34,380
ακόμα κι αν node9 δεν έχει νόημα πια.

382
00:28:34,380 --> 00:28:38,610
Ω, υποθέτω node9 αξία του δεν θα πρέπει να έχουν 6.

383
00:28:38,610 --> 00:28:42,800
Τώρα μπορούμε να επιστρέψουμε node9.

384
00:28:42,800 --> 00:28:49,550
Και εδώ θα πρέπει να επιστρέψει null.

385
00:28:49,550 --> 00:28:52,690
Όλοι συμφωνούν σε αυτό το build-a-κόμβος λειτουργία;

386
00:28:52,690 --> 00:28:59,780
Έτσι, τώρα μπορούμε να αποκαλούμε απλά ότι για να χτίσει κάθε κόμβο με μια δεδομένη αξία και null δείκτες.

387
00:28:59,780 --> 00:29:09,750
Τώρα μπορούμε να ονομάσουμε αυτό, μπορούμε να κάνουμε κόμβο * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Και ας το κάνουμε. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
Και τώρα θέλουμε να δημιουργήσουν τα ίδια δείκτες,

391
00:29:39,330 --> 00:29:42,470
εκτός από ό, τι τώρα είναι ήδη σε όρους δεικτών

392
00:29:42,470 --> 00:29:48,480
έτσι δεν χρειάζεται πλέον τη διεύθυνση του.

393
00:29:48,480 --> 00:29:56,300
Εντάξει. Έτσι, ποιο είναι το τελευταίο πράγμα που θέλω να κάνω;

394
00:29:56,300 --> 00:30:03,850
Υπάρχει ένα σφάλμα ελέγχου ότι δεν κάνω.

395
00:30:03,850 --> 00:30:06,800
Τι σημαίνει επιστροφή κατασκευή κόμβου;

396
00:30:06,800 --> 00:30:11,660
[Φοιτητών, ακατάληπτο] >> Ναι. Αν malloc αποτύχει, αυτό θα επιστρέψει null.

397
00:30:11,660 --> 00:30:16,460
Έτσι, Πάω να το θέσω νωχελικά κάτω εδώ, αντί να κάνει μια συνθήκη για το καθένα.

398
00:30:16,460 --> 00:30:22,320
Αν (node9 == NULL, ή - ακόμα πιο απλή,

399
00:30:22,320 --> 00:30:28,020
αυτό είναι ισοδύναμο με ακριβώς αν όχι node9.

400
00:30:28,020 --> 00:30:38,310
Έτσι, αν δεν node9, ή δεν node6, ή δεν node3, ή δεν node7, επιστρέφει 1.

401
00:30:38,310 --> 00:30:42,850
Ίσως θα πρέπει να εκτυπώσετε malloc αποτύχει, ή κάτι τέτοιο.

402
00:30:42,850 --> 00:30:46,680
[Φοιτητικό] Είναι ψευδής ίσο με null, καθώς;

403
00:30:46,680 --> 00:30:51,290
[Bowden] Κάθε μηδενική τιμή είναι ψευδής.

404
00:30:51,290 --> 00:30:53,920
Έτσι, null είναι μια μηδενική τιμή.

405
00:30:53,920 --> 00:30:56,780
Μηδέν είναι μια μηδενική τιμή. Λάθος είναι μηδενική αξία.

406
00:30:56,780 --> 00:31:02,130
Οποιαδήποτε - λίγο πολύ τα 2 μόνο μηδενικές τιμές είναι μηδενική και το μηδέν,

407
00:31:02,130 --> 00:31:07,900
ψευδή είναι απλά hash ορίζεται ως μηδέν.

408
00:31:07,900 --> 00:31:13,030
Αυτό ισχύει επίσης εάν δεν δηλώνουν global μεταβλητή.

409
00:31:13,030 --> 00:31:17,890
Αν είχαμε τον κόμβο ρίζα * μέχρι εδώ,

410
00:31:17,890 --> 00:31:24,150
τότε - το ωραίο πράγμα για την παγκόσμια μεταβλητών είναι ότι έχουν πάντα μια αρχική τιμή.

411
00:31:24,150 --> 00:31:27,500
Αυτό δεν είναι αλήθεια λειτουργιών, πώς μέσα από εδώ,

412
00:31:27,500 --> 00:31:34,870
αν έχουμε, όπως, ο κόμβος * x ή κόμβο.

413
00:31:34,870 --> 00:31:37,380
Δεν έχουμε ιδέα τι x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
ή θα μπορούσαμε να τις εκτυπώσετε και θα μπορούσαν να είναι αυθαίρετη.

415
00:31:40,700 --> 00:31:44,980
Αυτό δεν είναι αλήθεια της παγκόσμιας μεταβλητών.

416
00:31:44,980 --> 00:31:47,450
Έτσι, ο κόμβος ρίζα ή κόμβο x.

417
00:31:47,450 --> 00:31:53,410
Από προεπιλογή, όλα αυτά που είναι παγκόσμια, αν όχι ρητά προετοιμαστεί για κάποια αξία,

418
00:31:53,410 --> 00:31:57,390
έχει μηδενική τιμή ως τιμή.

419
00:31:57,390 --> 00:32:01,150
Έτσι, εδώ, ο κόμβος ρίζα *, δεν προετοιμαστεί ρητά σε τίποτα,

420
00:32:01,150 --> 00:32:06,350
έτσι προεπιλεγμένη τιμή της θα είναι μηδενική, η οποία είναι η μηδενική αξία των δεικτών.

421
00:32:06,350 --> 00:32:11,870
Η προεπιλεγμένη τιμή του x θα σημαίνει ότι x.value είναι μηδέν,

422
00:32:11,870 --> 00:32:14,260
x.left είναι μηδενική, και x.right είναι μηδενική.

423
00:32:14,260 --> 00:32:21,070
Έτσι, δεδομένου ότι είναι ένα struct, όλα τα πεδία του struct θα είναι μηδενικές τιμές.

424
00:32:21,070 --> 00:32:24,410
Δεν χρειάζεται να χρησιμοποιήσετε ότι εδώ, όμως.

425
00:32:24,410 --> 00:32:27,320
[Student] Οι structs είναι διαφορετικές από άλλες μεταβλητές, καθώς και οι άλλες μεταβλητές είναι

426
00:32:27,320 --> 00:32:31,400
αξιών σκουπίδια? αυτά είναι μηδενικά;

427
00:32:31,400 --> 00:32:36,220
[Bowden] Άλλες τιμές πάρα πολύ. Έτσι, σε χ, χ θα είναι μηδέν.

428
00:32:36,220 --> 00:32:40,070
Αν είναι σε παγκόσμια εμβέλεια, έχει μια αρχική τιμή. Εντάξει >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Είτε η αρχική τιμή που έδωσε ή μηδέν.

430
00:32:48,950 --> 00:32:53,260
Νομίζω ότι φροντίζει για όλα αυτά.

431
00:32:53,260 --> 00:32:58,390
>> Εντάξει. Έτσι, το επόμενο μέρος της ερώτηση,

432
00:32:58,390 --> 00:33:01,260
"Τώρα θέλουμε να γράψω μια λειτουργία που ονομάζεται περιέχει

433
00:33:01,260 --> 00:33:04,930
με ένα πρωτότυπο περιέχει bool τιμή τύπου int. "

434
00:33:04,930 --> 00:33:08,340
Εμείς δεν πρόκειται να κάνουμε bool περιέχει int αξία.

435
00:33:08,340 --> 00:33:15,110
Πρωτότυπο μας πρόκειται να μοιάσει

436
00:33:15,110 --> 00:33:22,380
bool περιέχει (int αξία.

437
00:33:22,380 --> 00:33:24,490
Και τότε θα είστε, επίσης, πρόκειται να περάσει αυτό το δέντρο

438
00:33:24,490 --> 00:33:28,870
ότι θα πρέπει να έλεγχο για να δούμε αν έχει αυτή την τιμή.

439
00:33:28,870 --> 00:33:38,290
Έτσι, ο κόμβος * δέντρο). Εντάξει.

440
00:33:38,290 --> 00:33:44,440
Και τότε μπορούμε να την αποκαλούμε με κάτι σαν,

441
00:33:44,440 --> 00:33:46,090
ίσως θα θέλουν να printf ή κάτι τέτοιο.

442
00:33:46,090 --> 00:33:51,040
Περιέχει 6, ρίζα μας.

443
00:33:51,040 --> 00:33:54,300
Αυτό θα πρέπει να επιστρέψει ένα, ή αλήθεια,

444
00:33:54,300 --> 00:33:59,390
ενώ περιέχει 5 ρίζα πρέπει να επιστρέψει ψευδείς.

445
00:33:59,390 --> 00:34:02,690
Πάρτε λοιπόν μια δεύτερη για την εφαρμογή της παρούσας.

446
00:34:02,690 --> 00:34:06,780
Μπορείτε να το κάνετε είτε επαναληπτικά ή αναδρομικά.

447
00:34:06,780 --> 00:34:09,739
Το θετικό σχετικά με τον τρόπο με τον οποίο έχετε ρυθμίσει τα πράγματα είναι ότι

448
00:34:09,739 --> 00:34:12,300
επιδέχεται αναδρομική λύση μας πολύ πιο εύκολη

449
00:34:12,300 --> 00:34:14,719
από ό, τι η παγκόσμια μεταβλητή τρόπο έκανε.

450
00:34:14,719 --> 00:34:19,750
Διότι, αν εμείς απλά πρέπει περιέχει int αξία, τότε δεν έχουμε κανένα τρόπο αναδρομική ανάκτηση κάτω υποδένδρων.

451
00:34:19,750 --> 00:34:24,130
Θα πρέπει να έχετε μια ξεχωριστή λειτουργία βοηθός που recurses τις υποδένδρων για μας.

452
00:34:24,130 --> 00:34:29,610
Αλλά επειδή έχουμε αλλάξει για να λάβει το δέντρο ως επιχείρημα,

453
00:34:29,610 --> 00:34:32,760
το οποίο θα έπρεπε να ήταν πάντα στην πρώτη θέση,

454
00:34:32,760 --> 00:34:35,710
τώρα μπορούμε recurse πιο εύκολα.

455
00:34:35,710 --> 00:34:38,960
Έτσι, επαναληπτική ή επαναλαμβανόμενη, θα πάμε πάνω από τα δύο,

456
00:34:38,960 --> 00:34:46,139
αλλά θα δούμε ότι οι αναδρομικές καταλήγει να είναι αρκετά εύκολο.

457
00:34:59,140 --> 00:35:02,480
Εντάξει. Υπάρχει κάποιος που έχει κάτι που μπορεί να λειτουργήσει με;

458
00:35:02,480 --> 00:35:12,000
>> [Φοιτητικό] Έχω μια επαναληπτική λύση. >> Εντάξει, επαναληπτική.

459
00:35:12,000 --> 00:35:16,030
Εντάξει, αυτό φαίνεται καλό.

460
00:35:16,030 --> 00:35:18,920
Έτσι, θέλουν να μας καθοδηγήσει αυτό;

461
00:35:18,920 --> 00:35:25,780
[Φοιτητικό] Σίγουρα. Έτσι, μπορώ να ορίσω μια μεταβλητή temp για να πάρει το πρώτο κόμβο του δέντρου.

462
00:35:25,780 --> 00:35:28,330
Και τότε ακριβώς looped μέσω temp ενώ δεν ισούται null,

463
00:35:28,330 --> 00:35:31,700
έτσι ενώ ήταν ακόμη στο δέντρο, υποθέτω.

464
00:35:31,700 --> 00:35:35,710
Και αν η τιμή είναι ίση με την αξία που temp δείχνει να,

465
00:35:35,710 --> 00:35:37,640
τότε επιστρέφει την τιμή.

466
00:35:37,640 --> 00:35:40,210
Διαφορετικά, ελέγχει αν είναι στη δεξιά πλευρά ή στην αριστερή πλευρά.

467
00:35:40,210 --> 00:35:43,400
Αν έχετε ποτέ μια κατάσταση όπου δεν υπάρχει πιο δέντρο,

468
00:35:43,400 --> 00:35:47,330
τότε επιστρέφει - βγαίνει από το βρόχο και επιστρέφει false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Εντάξει. Έτσι, αυτό φαίνεται καλό.

470
00:35:52,190 --> 00:35:58,470
Όποιος έχει οποιαδήποτε σχόλια σχετικά με οτιδήποτε;

471
00:35:58,470 --> 00:36:02,400
Δεν έχω κανένα σχόλιο ορθότητα καθόλου.

472
00:36:02,400 --> 00:36:11,020
Το μόνο πράγμα που μπορούμε να κάνουμε είναι αυτός ο τύπος.

473
00:36:11,020 --> 00:36:21,660
Ω, πρόκειται να προχωρήσουμε λίγο μακρουλό.

474
00:36:21,660 --> 00:36:33,460
Θα καθορίσει το εν λόγω επάνω. Εντάξει.

475
00:36:33,460 --> 00:36:37,150
>> Ο καθένας θα πρέπει να θυμάστε πως τριμερή λειτουργεί.

476
00:36:37,150 --> 00:36:38,610
Υπάρχουν σίγουρα έχουν κουίζ στο παρελθόν

477
00:36:38,610 --> 00:36:41,170
που να σας δώσει μια λειτουργία με ένα χειριστή τριμερών

478
00:36:41,170 --> 00:36:45,750
και να πω, να μεταφράσει αυτό, να κάνει κάτι που δεν χρησιμοποιεί τριμερή.

479
00:36:45,750 --> 00:36:49,140
Έτσι, αυτό είναι μια πολύ συνηθισμένη περίπτωση, όταν θα σκεφτόταν να χρησιμοποιήσει τριμερή,

480
00:36:49,140 --> 00:36:54,610
όπου αν κάποια κατάσταση που μια μεταβλητή σε κάτι,

481
00:36:54,610 --> 00:36:58,580
άλλο που την ίδια μεταβλητή για κάτι άλλο.

482
00:36:58,580 --> 00:37:03,390
Αυτό είναι κάτι που πολύ συχνά μπορεί να μετατραπεί σε αυτό το είδος του πράγματος

483
00:37:03,390 --> 00:37:14,420
όπου ορίζεται ότι η μεταβλητή για αυτό - ή, επίσης, είναι αλήθεια αυτό; Στη συνέχεια, αυτό, άλλο αυτό.

484
00:37:14,420 --> 00:37:18,550
[Φοιτητικό] Η πρώτη είναι εάν είναι αλήθεια, έτσι δεν είναι;

485
00:37:18,550 --> 00:37:25,570
[Bowden] Ναι. Ο τρόπος που έχω διαβάσει πάντα είναι, θερμοκρασία ισούται με αξία μεγαλύτερη από την αξία θερμοκρασία,

486
00:37:25,570 --> 00:37:30,680
τότε αυτό, άλλο αυτό. Είναι μια ερώτηση.

487
00:37:30,680 --> 00:37:35,200
Είναι περισσότερο; Στη συνέχεια, κάνει το πρώτο πράγμα. Αλλιώς κάνουμε το δεύτερο πράγμα.

488
00:37:35,200 --> 00:37:41,670
I σχεδόν πάντα - η άνω και κάτω τελεία, απλά - στο κεφάλι μου, διάβασα το άλλο.

489
00:37:41,670 --> 00:37:47,180
>> Υπάρχει κάποιος που έχει μια αναδρομική λύση;

490
00:37:47,180 --> 00:37:49,670
Εντάξει. Αυτό και μόνο θα πάμε να - θα μπορούσε να είναι ήδη μεγάλη,

491
00:37:49,670 --> 00:37:53,990
αλλά θα πάμε να την κάνουμε ακόμα καλύτερη.

492
00:37:53,990 --> 00:37:58,720
Αυτό είναι λίγο πολύ το ίδιο ακριβή ιδέα.

493
00:37:58,720 --> 00:38:03,060
Είναι απλά, καλά, δεν θέλετε να εξηγήσει;

494
00:38:03,060 --> 00:38:08,340
[Φοιτητικό] Σίγουρα. Έτσι είμαστε σίγουροι ότι κάνει το δέντρο δεν είναι null πρώτη,

495
00:38:08,340 --> 00:38:13,380
γιατί αν το δέντρο είναι μηδενική τότε πρόκειται να επιστρέψει false γιατί δεν έχουν βρεθεί.

496
00:38:13,380 --> 00:38:19,200
Και αν υπάρχει ακόμα ένα δέντρο, πάμε σε - εμείς πρώτα να ελέγξετε εάν η τιμή είναι ο τρέχων κόμβος.

497
00:38:19,200 --> 00:38:23,740
Επιστροφή αλήθεια και αν είναι, και αν δεν έχουμε recurse αριστερά ή προς τα δεξιά.

498
00:38:23,740 --> 00:38:25,970
Μήπως αυτό ακούγεται κατάλληλο; >> Χμμ. (Συμφωνία)

499
00:38:25,970 --> 00:38:33,880
Έτσι παρατηρούμε ότι αυτό είναι σχεδόν - δομικά πολύ παρόμοια με την επαναληπτική διάλυμα.

500
00:38:33,880 --> 00:38:38,200
Είναι απλά ότι αντί να αναδρομική ανάκτηση, είχαμε ένα βρόχο while.

501
00:38:38,200 --> 00:38:40,840
Και η βασική περίπτωση όπου εδώ δέντρο δεν ισούται null

502
00:38:40,840 --> 00:38:44,850
ήταν η κατάσταση κατά την οποία χωρίσαμε από τον βρόχο while.

503
00:38:44,850 --> 00:38:50,200
Είναι πολύ παρόμοια. Αλλά θα πάμε να πάρετε ένα βήμα παραπέρα.

504
00:38:50,200 --> 00:38:54,190
Τώρα, κάνουμε το ίδιο πράγμα εδώ.

505
00:38:54,190 --> 00:38:57,680
Παρατηρήστε γυρίζουμε το ίδιο πράγμα και στις δύο από αυτές τις γραμμές,

506
00:38:57,680 --> 00:39:00,220
εκτός από ένα όρισμα είναι διαφορετική.

507
00:39:00,220 --> 00:39:07,950
Έτσι θα πάμε για να κάνουν ότι σε μια τριμερή.

508
00:39:07,950 --> 00:39:13,790
Χτύπησα κάτι επιλογή, και έκανε ένα σύμβολο. Εντάξει.

509
00:39:13,790 --> 00:39:21,720
Έτσι θα πάμε για να επιστρέψει περιέχει αυτό.

510
00:39:21,720 --> 00:39:28,030
Αυτό γίνεται για να είναι πολλαπλές γραμμές, καλά, μεγεθύνεται είναι.

511
00:39:28,030 --> 00:39:31,060
Συνήθως, ως υφολογική πράγμα, δεν νομίζω ότι πολλοί άνθρωποι

512
00:39:31,060 --> 00:39:38,640
βάλετε ένα κενό διάστημα μετά το βέλος, αλλά υποθέτω αν είσαι συνεπής, είναι μια χαρά.

513
00:39:38,640 --> 00:39:44,320
Εάν η τιμή είναι μικρότερη από την τιμή δέντρο, θέλουμε να recurse στο αριστερό δέντρο,

514
00:39:44,320 --> 00:39:53,890
αλλιώς θέλουμε να recurse στο δεξί δέντρο.

515
00:39:53,890 --> 00:39:58,610
Έτσι, αυτό ήταν το πρώτο βήμα της κάνει αυτό το βλέμμα μικρότερο.

516
00:39:58,610 --> 00:40:02,660
Βήμα δύο κάνουν αυτό το βλέμμα μικρότερο -

517
00:40:02,660 --> 00:40:09,150
μπορούμε να χωρίσουμε αυτό σε πολλές γραμμές.

518
00:40:09,150 --> 00:40:16,500
Εντάξει. Βήμα δύο καθιστώντας φαίνεται μικρότερο είναι εδώ,

519
00:40:16,500 --> 00:40:25,860
έτσι αξία ισούται με την επιστροφή αξία δέντρο, ή οτιδήποτε άλλο περιέχει.

520
00:40:25,860 --> 00:40:28,340
>> Αυτό είναι ένα σημαντικό πράγμα.

521
00:40:28,340 --> 00:40:30,860
Δεν είμαι σίγουρος αν είπε ρητά στην τάξη,

522
00:40:30,860 --> 00:40:34,740
αλλά λέγεται βραχυκύκλωμα αξιολόγησης.

523
00:40:34,740 --> 00:40:41,060
Η ιδέα εδώ είναι η αξία == αξία δέντρο.

524
00:40:41,060 --> 00:40:49,960
Αν αυτό είναι αλήθεια, τότε αυτό είναι αλήθεια, και θέλουμε να »ή« ότι με ό, τι είναι πάνω από εδώ.

525
00:40:49,960 --> 00:40:52,520
Έτσι, χωρίς καν να το σκεφτούμε ό, τι είναι πάνω από εδώ,

526
00:40:52,520 --> 00:40:55,070
τι είναι ολόκληρη η έκφραση θα επιστρέψει;

527
00:40:55,070 --> 00:40:59,430
[Φοιτητικό] Αληθές; >> Ναι, επειδή ισχύει τίποτα,

528
00:40:59,430 --> 00:41:04,990
or'd - ή αλήθεια or'd με οτιδήποτε είναι απαραίτητα αλήθεια.

529
00:41:04,990 --> 00:41:08,150
Έτσι, το συντομότερο βλέπουμε τιμή επιστροφής = τιμή δέντρο,

530
00:41:08,150 --> 00:41:10,140
είμαστε ακριβώς πρόκειται να επιστρέψει αλήθεια.

531
00:41:10,140 --> 00:41:15,710
Ούτε πρόκειται να recurse περιέχει περαιτέρω κάτω από τη γραμμή.

532
00:41:15,710 --> 00:41:20,980
Μπορούμε να πάρουμε ένα βήμα παραπέρα.

533
00:41:20,980 --> 00:41:29,490
Επιστροφή δέντρο δεν ισούται άκυρη και όλα αυτά.

534
00:41:29,490 --> 00:41:32,650
Έκανε ένα one-line λειτουργία.

535
00:41:32,650 --> 00:41:36,790
Αυτό είναι επίσης ένα παράδειγμα των βραχυκυκλώματος αξιολόγησης.

536
00:41:36,790 --> 00:41:40,680
Τώρα, όμως, είναι η ίδια ιδέα -

537
00:41:40,680 --> 00:41:47,320
αντί της - οπότε αν δέντρο δεν είναι ίσο με null - ή, επίσης,

538
00:41:47,320 --> 00:41:49,580
αν το δένδρο ίση null, η οποία είναι η κακή περίπτωση,

539
00:41:49,580 --> 00:41:54,790
εάν δέντρο ισούται με μηδέν, τότε η πρώτη προϋπόθεση θα είναι ψευδής.

540
00:41:54,790 --> 00:42:00,550
Έτσι ψευδείς anded με οτιδήποτε πρόκειται να είναι αυτό;

541
00:42:00,550 --> 00:42:04,640
[Φοιτητικό] Λάθος. Ναι >>. Αυτό είναι το άλλο μισό του βραχυκυκλώματος αξιολόγησης,

542
00:42:04,640 --> 00:42:10,710
όπου αν δεν δέντρο ίση null, τότε δεν πρόκειται να πάμε ακόμα -

543
00:42:10,710 --> 00:42:14,930
ή αν το δένδρο ίση null, τότε δεν πρόκειται να κάνουμε αξία == αξία δέντρο.

544
00:42:14,930 --> 00:42:17,010
Είμαστε ακριβώς πρόκειται να επιστρέψει αμέσως ψευδή.

545
00:42:17,010 --> 00:42:20,970
Ποια είναι σημαντικό, διότι αν δεν το έκανε βραχυκύκλωμα αξιολογεί,

546
00:42:20,970 --> 00:42:25,860
στη συνέχεια, αν είναι ίσο δέντρο null, αυτή η δεύτερη προϋπόθεση θα σφάλμα seg,

547
00:42:25,860 --> 00:42:32,510
επειδή δέντρο-> τιμή εύρεση τιμών null.

548
00:42:32,510 --> 00:42:40,490
Έτσι αυτό είναι αυτό. Μπορεί να κάνει αυτό - τη μετατόπιση πάνω από μία φορά.

549
00:42:40,490 --> 00:42:44,840
Αυτό είναι ένα πολύ κοινό πράγμα, επίσης, δεν κάνει αυτό μια γραμμή με αυτό,

550
00:42:44,840 --> 00:42:49,000
αλλά είναι ένα κοινό πράγμα σε συνθήκες, ίσως όχι ακριβώς εδώ,

551
00:42:49,000 --> 00:42:59,380
αλλά αν (δέντρο! = NULL, και δέντρο-> αξία αξίας ==), κάνει ό, τι.

552
00:42:59,380 --> 00:43:01,560
Αυτή είναι μια πολύ κοινή κατάσταση, όπου αντί του έχοντας

553
00:43:01,560 --> 00:43:06,770
να σπάσει αυτό σε δύο ifs, όπου θέλετε, είναι η μηδενική δέντρο;

554
00:43:06,770 --> 00:43:11,780
Εντάξει, δεν είναι μηδενική, οπότε τώρα είναι η αξία δέντρο ίση με την τιμή; Κάνετε αυτό.

555
00:43:11,780 --> 00:43:17,300
Αντ 'αυτού, αυτή η κατάσταση, αυτό δεν πρόκειται ποτέ να διαχωρίζονται από σφάλμα

556
00:43:17,300 --> 00:43:21,220
γιατί θα ξεσπάσει αν αυτό συμβαίνει να είναι μηδενική.

557
00:43:21,220 --> 00:43:24,000
Καλά, υποθέτω ότι αν το δέντρο σας είναι ένα εντελώς άκυρο δείκτη, μπορεί να διαχωρίζονται από ακόμα σφάλμα,

558
00:43:24,000 --> 00:43:26,620
αλλά δεν μπορεί να διαχωρίζονται από υπαιτιότητα αν το δέντρο είναι μηδενική.

559
00:43:26,620 --> 00:43:32,900
Αν ήταν μηδενική, θα ξεσπάσει πριν αναχθούν ποτέ το δείκτη στην πρώτη θέση.

560
00:43:32,900 --> 00:43:35,000
[Φοιτητικό] Είναι αυτό που ονομάζεται lazy evaluation;

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy αξιολόγησης είναι ένα ξεχωριστό πράγμα.

562
00:43:40,770 --> 00:43:49,880
Lazy αξιολόγησης είναι περισσότερο όπως σας ρωτήσω για μια τιμή,

563
00:43:49,880 --> 00:43:54,270
σας ζητήσει να υπολογιστεί η τιμή, το είδος του, αλλά εσείς δεν το χρειάζεστε άμεσα.

564
00:43:54,270 --> 00:43:59,040
Έτσι, μέχρι να χρειαστεί πραγματικά, δεν αξιολογείται.

565
00:43:59,040 --> 00:44:03,920
Αυτό δεν είναι ακριβώς το ίδιο πράγμα, αλλά στην Huffman PSET,

566
00:44:03,920 --> 00:44:06,520
λέει ότι «νωχελικά» γράφουν.

567
00:44:06,520 --> 00:44:08,670
Ο λόγος που το κάνουμε αυτό είναι γιατί είμαστε buffering πραγματικά τη διαγραφή -

568
00:44:08,670 --> 00:44:11,820
δεν θέλουμε να γράψετε μεμονωμένα κομμάτια σε ένα χρόνο,

569
00:44:11,820 --> 00:44:15,450
ή μεμονωμένες bytes σε μια στιγμή, αντί να θέλουν να πάρουν ένα κομμάτι από bytes.

570
00:44:15,450 --> 00:44:19,270
Στη συνέχεια, αφού έχουμε ένα μεγάλο κομμάτι των bytes, τότε θα το γράψει.

571
00:44:19,270 --> 00:44:22,640
Ακόμα κι αν το ζητήσετε να γράψω - και fwrite και fread κάνουν το ίδιο πράγμα.

572
00:44:22,640 --> 00:44:26,260
Θα σας buffer διαβάζει και γράφει.

573
00:44:26,260 --> 00:44:31,610
Ακόμα κι αν το ζητήσει αμέσως να γράψει, κατά πάσα πιθανότητα δεν θα.

574
00:44:31,610 --> 00:44:34,540
Και δεν μπορείτε να είστε σίγουροι ότι τα πράγματα πρόκειται να γραφτεί

575
00:44:34,540 --> 00:44:37,540
μέχρι να καλέσετε hfclose ή ό, τι είναι,

576
00:44:37,540 --> 00:44:39,620
η οποία στη συνέχεια λέει, εντάξει, είμαι το κλείσιμο του αρχείου μου,

577
00:44:39,620 --> 00:44:43,450
αυτό σημαίνει ότι θα ήθελα να γράψω καλύτερα ό, τι δεν έχω γράψει ακόμα.

578
00:44:43,450 --> 00:44:45,770
Έχει δεν χρειάζεται να γράψετε τα πάντα

579
00:44:45,770 --> 00:44:49,010
μέχρι να κλείσετε το αρχείο, και τότε θα πρέπει να.

580
00:44:49,010 --> 00:44:56,220
Έτσι, αυτό είναι ακριβώς ό, τι τεμπέλης - περιμένει έως ότου έχει να συμβεί.

581
00:44:56,220 --> 00:44:59,990
Αυτό - λαμβάνουν 51 και θα πάμε σε αυτό με περισσότερες λεπτομέρειες,

582
00:44:59,990 --> 00:45:05,470
επειδή ocaml και τα πάντα σε 51, τα πάντα είναι αναδρομή.

583
00:45:05,470 --> 00:45:08,890
Δεν υπάρχουν επαναληπτικές λύσεις, βασικά.

584
00:45:08,890 --> 00:45:11,550
Όλα είναι αναδρομή, και lazy evaluation

585
00:45:11,550 --> 00:45:14,790
πρόκειται να είναι σημαντική για πολλές περιστάσεις

586
00:45:14,790 --> 00:45:19,920
όπου, αν δεν έχετε αξιολογήσει νωχελικά, αυτό θα σήμαινε ότι -

587
00:45:19,920 --> 00:45:24,760
Το παράδειγμα είναι ρεύματα, τα οποία είναι απείρως μεγάλη.

588
00:45:24,760 --> 00:45:30,990
Στη θεωρία, μπορείτε να σκεφτείτε από τους φυσικούς αριθμούς ως ένα ρεύμα 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Έτσι, νωχελικά αξιολογούνται τα πράγματα είναι μια χαρά.

590
00:45:33,090 --> 00:45:37,210
Αν πω θέλω τη δέκατη αριθμό, τότε θα μπορεί να αξιολογήσει μέχρι το δέκατο αριθμό.

591
00:45:37,210 --> 00:45:40,300
Αν θέλω την εκατοστή αριθμό, τότε θα μπορεί να αξιολογήσει μέχρι το εκατοστό αριθμό.

592
00:45:40,300 --> 00:45:46,290
Χωρίς τεμπέλης αξιολόγησης, τότε πρόκειται να προσπαθήσει να αξιολογήσει όλους τους αριθμούς αμέσως.

593
00:45:46,290 --> 00:45:50,000
Είσαι αξιολόγηση απείρως πολλούς αριθμούς, και αυτό δεν είναι μόνο δυνατό.

594
00:45:50,000 --> 00:45:52,080
Έτσι, υπάρχουν πολλές περιπτώσεις όπου lazy evaluation

595
00:45:52,080 --> 00:45:57,840
είναι απλά απαραίτητη για να πάρει τα πράγματα στην εργασία.

596
00:45:57,840 --> 00:46:05,260
>> Τώρα θέλουμε να γράψω ένθετο ένθετο όπου θα είναι

597
00:46:05,260 --> 00:46:08,430
ομοίως αλλαγή στον ορισμό του.

598
00:46:08,430 --> 00:46:10,470
Έτσι, αυτή τη στιγμή είναι bool ένθετο (int αξία).

599
00:46:10,470 --> 00:46:23,850
Εμείς πάμε για να το αλλάξουμε αυτό να bool ένθετο (int αξία, κόμβο του δένδρου *).

600
00:46:23,850 --> 00:46:29,120
Είμαστε πραγματικά πρόκειται να αλλάξει και πάλι ότι σε λίγο, θα δούμε γιατί.

601
00:46:29,120 --> 00:46:32,210
Και ας προχωρήσουμε build_node, μόνο για το καλό του,

602
00:46:32,210 --> 00:46:36,730
εισάγετε παραπάνω έτσι δεν έχουμε να γράψει ένα πρωτότυπο της συνάρτησης.

603
00:46:36,730 --> 00:46:42,450
Ποια είναι ένας υπαινιγμός ότι θα πάμε να χρησιμοποιούν build_node στο ένθετο.

604
00:46:42,450 --> 00:46:49,590
Εντάξει. Πάρτε ένα λεπτό για αυτό.

605
00:46:49,590 --> 00:46:52,130
Νομίζω ότι έσωσε την αναθεώρηση, αν θέλετε να τραβήξει από αυτό,

606
00:46:52,130 --> 00:47:00,240
ή, τουλάχιστον, το έκανα τώρα.

607
00:47:00,240 --> 00:47:04,190
Ήθελα ένα μικρό διάλειμμα για να σκεφτεί για τη λογική του ένθετου,

608
00:47:04,190 --> 00:47:08,750
αν δεν μπορείτε να σκεφτείτε από το.

609
00:47:08,750 --> 00:47:12,860
Βασικά, το μόνο που θα πρέπει να τοποθετήσετε ποτέ σε φύλλα.

610
00:47:12,860 --> 00:47:18,640
Όπως, αν εισάγω 1, τότε είμαι αναπόφευκτα θα πρέπει να τοποθετήσετε 1 -

611
00:47:18,640 --> 00:47:21,820
Θα αλλάξει σε μαύρο - I'll να τοποθετήσετε 1 πάνω από εδώ.

612
00:47:21,820 --> 00:47:28,070
Ή αν εισάγω 4, θέλω να τοποθετήσετε 4 πάνω εδώ.

613
00:47:28,070 --> 00:47:32,180
Έτσι, δεν έχει σημασία τι θα κάνεις, θα πάμε να τοποθετήσετε σε ένα φύλλο.

614
00:47:32,180 --> 00:47:36,130
Το μόνο που έχετε να κάνετε είναι να επαναλάβει κάτω από το δέντρο μέχρι να φτάσετε στον κόμβο

615
00:47:36,130 --> 00:47:40,890
αυτό θα πρέπει να είναι γονέας του κόμβου, της μητρικής της νέας κόμβου,

616
00:47:40,890 --> 00:47:44,560
και στη συνέχεια, αλλάξτε τα αριστερά ή προς τα δεξιά του δείκτη, ανάλογα με το αν

617
00:47:44,560 --> 00:47:47,060
είναι μεγαλύτερη από ή μικρότερη από τον τρέχοντα κόμβο.

618
00:47:47,060 --> 00:47:51,180
Αλλάξτε αυτό το δείκτη να επισημάνει νέος κόμβος σας.

619
00:47:51,180 --> 00:48:05,490
Έτσι επαναλάβει κάτω από το δέντρο, να κάνει το σημείο φύλλο στο νέο κόμβο.

620
00:48:05,490 --> 00:48:09,810
Επίσης, σκεφτείτε γιατί ότι απαγορεύει το είδος της κατάστασης πριν,

621
00:48:09,810 --> 00:48:17,990
όπου θα κατασκευαστεί το δυαδικό δέντρο όπου ήταν σωστή

622
00:48:17,990 --> 00:48:19,920
αν μόνο κοίταξε ένα μόνο κόμβο,

623
00:48:19,920 --> 00:48:24,830
αλλά 9 ήταν στα αριστερά από 7 αν επαναληφθεί κάτω σε όλη τη διαδρομή.

624
00:48:24,830 --> 00:48:29,770
Έτσι, αυτό είναι αδύνατο σε αυτό το σενάριο, δεδομένου ότι -

625
00:48:29,770 --> 00:48:32,530
σκέφτονται την εισαγωγή περίπου 9 ή κάτι τέτοιο? στην πρώτη κόμβο,

626
00:48:32,530 --> 00:48:35,350
Πάω να δω 7 και είμαι απλώς πρόκειται να πάει προς τα δεξιά.

627
00:48:35,350 --> 00:48:38,490
Έτσι, δεν έχει σημασία τι κάνω, αν είμαι εισαγωγή από τη μετάβαση σε ένα φύλλο,

628
00:48:38,490 --> 00:48:40,790
και σε ένα φύλλο χρησιμοποιώντας τον κατάλληλο αλγόριθμο,

629
00:48:40,790 --> 00:48:43,130
πρόκειται να είναι αδύνατο για μένα να εισάγετε 9 έως αριστερά από 7

630
00:48:43,130 --> 00:48:48,250
γιατί μόλις χτύπησα 7 Πάω να πάμε προς τα δεξιά.

631
00:48:59,740 --> 00:49:02,070
Υπάρχει κάποιος που έχει κάτι για να αρχίσει με;

632
00:49:02,070 --> 00:49:05,480
[Φοιτητικό] κάνω. Σίγουρα >>.

633
00:49:05,480 --> 00:49:09,200
[Φοιτητών, ακατάληπτο]

634
00:49:09,200 --> 00:49:14,390
[Άλλες φοιτητής, ακατάληπτο]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Είναι ευπρόσδεκτη. Εντάξει. Θέλετε να εξηγήσει;

636
00:49:18,330 --> 00:49:20,690
>> [Φοιτητικό] Από τη στιγμή που ξέρουμε ότι εισάγοντας

637
00:49:20,690 --> 00:49:24,060
νέοι κόμβοι στο τέλος του δέντρου,

638
00:49:24,060 --> 00:49:28,070
I τυλιγμένο μέσα από το δέντρο επαναληπτικό

639
00:49:28,070 --> 00:49:31,360
έως ότου πήρα σε ένα κόμβο που επεσήμανε σε null.

640
00:49:31,360 --> 00:49:34,220
Και τότε αποφάσισα να το θέσω είτε στη δεξιά είτε στην αριστερή πλευρά

641
00:49:34,220 --> 00:49:37,420
με τη χρήση αυτού του δικαιώματος μεταβλητή? μου είπε πού να το θέσω.

642
00:49:37,420 --> 00:49:41,850
Και τότε, κατ 'ουσίαν, Έκανα ότι η τελευταία -

643
00:49:41,850 --> 00:49:47,520
ότι το σημείο κόμβος θερμοκρασία στο νέο κόμβο που ήταν η δημιουργία,

644
00:49:47,520 --> 00:49:50,770
είτε στην αριστερή πλευρά ή στην δεξιά πλευρά, ανάλογα με το ποια είναι η αξία σωστό ήταν.

645
00:49:50,770 --> 00:49:56,530
Τέλος, μπορώ να ορίσω τη νέα τιμή κόμβο με την αξία της δοκιμής του.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Εντάξει, έτσι βλέπω ένα θέμα εδώ.

647
00:49:59,550 --> 00:50:02,050
Αυτό είναι όπως το 95% του τρόπου εκεί.

648
00:50:02,050 --> 00:50:07,550
Το μόνο θέμα που βλέπω, καλά, δεν βλέπω κανέναν άλλο ένα ζήτημα;

649
00:50:07,550 --> 00:50:18,400
Ποια είναι η περίσταση βάσει των οποίων θα σπάσει έξω από το βρόχο;

650
00:50:18,400 --> 00:50:22,100
[Φοιτητικό] Αν temp είναι άκυρη; Ναι >>. Λοιπόν, πώς μπορείτε να σπάσει έξω από το βρόχο αν είναι temp είναι μηδενική.

651
00:50:22,100 --> 00:50:30,220
Αλλά αυτό που μπορώ να κάνω εδώ;

652
00:50:30,220 --> 00:50:35,410
I dereference θερμοκρασία, η οποία είναι αναπόφευκτα null.

653
00:50:35,410 --> 00:50:39,840
Έτσι, το άλλο πράγμα που πρέπει να κάνετε είναι όχι μόνο να παρακολουθείτε μέχρι temp είναι μηδενική,

654
00:50:39,840 --> 00:50:45,590
θέλετε να παρακολουθείτε της μητρικής ανά πάσα στιγμή.

655
00:50:45,590 --> 00:50:52,190
Θέλουμε, επίσης, ο κόμβος γονέας *, υποθέτω ότι μπορεί να κρατήσει ότι σε null την πρώτη.

656
00:50:52,190 --> 00:50:55,480
Αυτό πρόκειται να έχουν περίεργη συμπεριφορά για την ρίζα του δέντρου,

657
00:50:55,480 --> 00:50:59,210
αλλά θα φτάσουμε σε αυτό.

658
00:50:59,210 --> 00:51:03,950
Εάν η τιμή είναι μεγαλύτερη από οτιδήποτε άλλο, τότε temp = temp δικαίωμα.

659
00:51:03,950 --> 00:51:07,910
Αλλά πριν το κάνουμε αυτό, γονέας = temp.

660
00:51:07,910 --> 00:51:14,500
Ή οι γονείς πάντα θα ίση θερμοκρασία; Είναι ότι η υπόθεση;

661
00:51:14,500 --> 00:51:19,560
Αν temp δεν είναι μηδενική, τότε θα πάω να μετακινηθείτε προς τα κάτω, δεν το θέμα αυτό,

662
00:51:19,560 --> 00:51:24,030
σε έναν κόμβο για την οποία temp είναι ο γονέας.

663
00:51:24,030 --> 00:51:27,500
Έτσι γονέας πρόκειται να είναι temp, και στη συνέχεια θα προχωρήσουμε θερμοκρασία κάτω.

664
00:51:27,500 --> 00:51:32,410
Τώρα temp είναι μηδενική, αλλά επισημαίνει γονέα στη μητρική του πράγματος που είναι null.

665
00:51:32,410 --> 00:51:39,110
Έτσι, εδώ κάτω, δεν θέλω να ρυθμίσετε το δικαίωμα ισούται με 1.

666
00:51:39,110 --> 00:51:41,300
Γι 'αυτό και κινήθηκε προς τα δεξιά, οπότε αν δεξιά = 1,

667
00:51:41,300 --> 00:51:45,130
και υποθέτω ότι και εσείς θέλετε να κάνετε -

668
00:51:45,130 --> 00:51:48,530
αν μετακινηθείτε προς τα αριστερά, θέλετε να ρυθμίσετε το δικαίωμα ίση με 0.

669
00:51:48,530 --> 00:51:55,950
Ή αλλιώς, αν ποτέ μετακινηθεί προς τα δεξιά.

670
00:51:55,950 --> 00:51:58,590
Έτσι, δεξιά = 0. Αν δεξιά = 1,

671
00:51:58,590 --> 00:52:04,260
Τώρα θέλουμε να κάνουμε το μητρικό δικαίωμα newnode δείκτη,

672
00:52:04,260 --> 00:52:08,520
αλλιώς θέλουμε να κάνουμε το γονέα αριστερά newnode δείκτη.

673
00:52:08,520 --> 00:52:16,850
Ερωτήσεις σχετικά με αυτό;

674
00:52:16,850 --> 00:52:24,880
Εντάξει. Έτσι, αυτός είναι ο τρόπος με τον οποίο - και, στην πραγματικότητα, αντί να γίνει αυτό,

675
00:52:24,880 --> 00:52:29,630
έχουμε ένα δεύτερο αναμένεται μπορείτε να χρησιμοποιήσετε build_node.

676
00:52:29,630 --> 00:52:40,450
Και στη συνέχεια, αν newnode ισούται με null, επιστρέφει false.

677
00:52:40,450 --> 00:52:44,170
Αυτό είναι αυτό. Τώρα, αυτό είναι ό, τι περιμέναμε να το κάνετε.

678
00:52:44,170 --> 00:52:47,690
>> Αυτό είναι ό, τι κάνουν οι λύσεις του προσωπικού.

679
00:52:47,690 --> 00:52:52,360
Διαφωνώ με αυτό, όπως το "σωστό" τρόπο να πάει γι 'αυτό

680
00:52:52,360 --> 00:52:57,820
αλλά αυτό είναι απολύτως εντάξει και αυτό θα λειτουργήσει.

681
00:52:57,820 --> 00:53:02,840
Ένα πράγμα που είναι λίγο παράξενο τώρα είναι

682
00:53:02,840 --> 00:53:08,310
αν το δέντρο ξεκινά ως null, περνάμε σε ένα δέντρο null.

683
00:53:08,310 --> 00:53:12,650
Υποθέτω ότι εξαρτάται από το πώς θα καθορίσει τη συμπεριφορά του περνώντας σε ένα δέντρο null.

684
00:53:12,650 --> 00:53:15,490
Θα ήθελα να πιστεύω ότι αν περάσει σε ένα δέντρο null,

685
00:53:15,490 --> 00:53:17,520
στη συνέχεια, εισάγοντας την τιμή null σε ένα δέντρο

686
00:53:17,520 --> 00:53:23,030
πρέπει απλά να επιστρέψει ένα δέντρο, όπου η μόνη αξία είναι ότι μόνο κόμβο.

687
00:53:23,030 --> 00:53:25,830
Υπάρχουν άτομα που συμφωνούν με αυτό; Θα μπορούσε, αν ήθελε,

688
00:53:25,830 --> 00:53:28,050
αν περάσει σε ένα δέντρο null

689
00:53:28,050 --> 00:53:31,320
και θέλετε να εισαγάγετε μια τιμή σε αυτό, επιστρέφουν ψευδείς.

690
00:53:31,320 --> 00:53:33,830
Είναι στο χέρι σας να καθορίσει αυτό.

691
00:53:33,830 --> 00:53:38,320
Για να κάνει το πρώτο πράγμα που είπα και τότε -

692
00:53:38,320 --> 00:53:40,720
καλά, θα πάμε να έχουν πρόβλημα να το κάνουμε αυτό, επειδή

693
00:53:40,720 --> 00:53:44,090
θα ήταν ευκολότερο αν είχαμε ένα παγκόσμιο δείκτη στο πράγμα,

694
00:53:44,090 --> 00:53:48,570
αλλά δεν, οπότε αν το δέντρο είναι μηδενική, δεν υπάρχει τίποτα που μπορούμε να κάνουμε γι 'αυτό.

695
00:53:48,570 --> 00:53:50,960
Εμείς μπορούμε απλά να επιστρέψει false.

696
00:53:50,960 --> 00:53:52,840
Έτσι, Πάω να αλλάξει ένθετο.

697
00:53:52,840 --> 00:53:56,540
Εμείς τεχνικά θα μπορούσε να αλλάξει μόνο αυτό το δικαίωμα εδώ,

698
00:53:56,540 --> 00:53:58,400
πώς είναι τα πράγματα για την επανάληψη,

699
00:53:58,400 --> 00:54:04,530
αλλά Πάω να αλλάξει ένθετο να λάβει ένας κόμβος ** δέντρο.

700
00:54:04,530 --> 00:54:07,510
Διπλό δείκτες.

701
00:54:07,510 --> 00:54:09,710
Τι σημαίνει αυτό;

702
00:54:09,710 --> 00:54:12,330
Αντί να ασχολείται με δείκτες προς τους κόμβους,

703
00:54:12,330 --> 00:54:16,690
το πράγμα Πάω να είναι αυτή η χειραγώγηση δείκτη.

704
00:54:16,690 --> 00:54:18,790
Πάω να χειρίζονται αυτό το δείκτη.

705
00:54:18,790 --> 00:54:21,770
Πάω να χειρίζονται απευθείας δείκτες.

706
00:54:21,770 --> 00:54:25,760
Αυτό είναι λογικό δεδομένου ότι, σκεφτείτε κάτω -

707
00:54:25,760 --> 00:54:33,340
καλά, τώρα αυτό δείχνει σε null.

708
00:54:33,340 --> 00:54:38,130
Αυτό που θέλω να κάνετε είναι να χειραγωγήσουν το δείκτη στο σημείο να μην null.

709
00:54:38,130 --> 00:54:40,970
Θέλω να επισημάνω ότι στο νέο κόμβο μου.

710
00:54:40,970 --> 00:54:44,870
Αν έχω κρατήσει μόνο κομμάτι του δείκτες σε δείκτες μου,

711
00:54:44,870 --> 00:54:47,840
τότε δεν χρειάζεται να παρακολουθείτε το δείκτη του γονέα.

712
00:54:47,840 --> 00:54:52,640
Μπορώ να κρατήσει μόνο δρόμο για να δούμε αν ο δείκτης δείχνει σε null,

713
00:54:52,640 --> 00:54:54,580
και εάν ο δείκτης δείχνει σε null,

714
00:54:54,580 --> 00:54:57,370
αλλάξετε σε σημείο να τον κόμβο που θέλω.

715
00:54:57,370 --> 00:55:00,070
Και μπορώ να το αλλάξει από τότε έχω ένα δείκτη για το δείκτη.

716
00:55:00,070 --> 00:55:02,040
Ας δούμε αυτό το δικαίωμα τώρα.

717
00:55:02,040 --> 00:55:05,470
Μπορείτε να το κάνετε πραγματικά αναδρομικά αρκετά εύκολα.

718
00:55:05,470 --> 00:55:08,080
Θέλουμε να το κάνουμε αυτό;

719
00:55:08,080 --> 00:55:10,980
Ναι, το κάνουμε.

720
00:55:10,980 --> 00:55:16,790
>> Ας το δούμε αναδρομικά.

721
00:55:16,790 --> 00:55:24,070
Κατ 'αρχάς, τι είναι βασική περίπτωση μας πρόκειται να είναι;

722
00:55:24,070 --> 00:55:29,140
Σχεδόν πάντα βασική περίπτωση μας? Αλλά στην πραγματικότητα, αυτό είναι το είδος του δύσκολη.

723
00:55:29,140 --> 00:55:34,370
Τα πρώτα πράγματα πρώτα, αν (δέντρο == NULL)

724
00:55:34,370 --> 00:55:37,550
Υποθέτω ότι είμαστε ακριβώς πρόκειται να επιστρέψει ψευδείς.

725
00:55:37,550 --> 00:55:40,460
Αυτό είναι διαφορετικό από το δέντρο σας να είναι null.

726
00:55:40,460 --> 00:55:44,510
Αυτός είναι ο δείκτης σε δείκτη ρίζας σας είναι null

727
00:55:44,510 --> 00:55:48,360
πράγμα που σημαίνει ότι ο δείκτης ρίζα σας δεν υπάρχει.

728
00:55:48,360 --> 00:55:52,390
Έτσι, εδώ κάτω, αν το κάνω

729
00:55:52,390 --> 00:55:55,760
* κόμβος - ας επαναχρησιμοποίηση ακριβώς αυτό.

730
00:55:55,760 --> 00:55:58,960
Κόμβος ρίζα * = NULL,

731
00:55:58,960 --> 00:56:00,730
και στη συνέχεια, Πάω να καλέσω ένθετο κάνοντας κάτι σαν,

732
00:56:00,730 --> 00:56:04,540
εισάγετε & 4 σε ρίζα.

733
00:56:04,540 --> 00:56:06,560
Έτσι & ρίζα, ρίζα, αν είναι κόμβος *

734
00:56:06,560 --> 00:56:11,170
τότε και ρίζα πρόκειται να είναι ένα ** κόμβο.

735
00:56:11,170 --> 00:56:15,120
Αυτό είναι έγκυρο. Σε αυτή την περίπτωση, δέντρο, μέχρι εδώ,

736
00:56:15,120 --> 00:56:20,120
δέντρο δεν είναι null - ή ένθετο.

737
00:56:20,120 --> 00:56:24,630
Εδώ. Δέντρο δεν είναι null? * Δέντρο είναι μηδενική, το οποίο είναι μια χαρά

738
00:56:24,630 --> 00:56:26,680
γιατί αν δέντρο * είναι null, τότε μπορώ να το χειριστείτε

739
00:56:26,680 --> 00:56:29,210
τώρα να επισημάνω σε αυτό που θέλω να επισημάνω.

740
00:56:29,210 --> 00:56:34,750
Αλλά αν το δέντρο είναι μηδενική, αυτό σημαίνει ότι ήρθα εδώ κάτω και είπε null.

741
00:56:34,750 --> 00:56:42,710
Αυτό δεν έχει νόημα. Δεν μπορώ να κάνω τίποτα με αυτό.

742
00:56:42,710 --> 00:56:45,540
Αν το δέντρο είναι null, επιστρέφει false.

743
00:56:45,540 --> 00:56:48,220
Γι 'αυτό και βασικά ήδη πει ποια είναι η πραγματική βασική περίπτωση μας είναι.

744
00:56:48,220 --> 00:56:50,580
Και αυτό είναι ότι πρόκειται να είναι;

745
00:56:50,580 --> 00:56:55,030
[Φοιτητών, ακατάληπτο]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ναι. Έτσι, αν (* δέντρο == NULL).

747
00:57:00,000 --> 00:57:04,520
Αυτό σχετίζεται με την υπόθεση εδώ

748
00:57:04,520 --> 00:57:09,640
όπου αν μου κόκκινο δείκτης είναι ο δείκτης είμαι επικεντρώθηκε,

749
00:57:09,640 --> 00:57:12,960
έτσι όπως είμαι συγκεντρωμένος σε αυτό το δείκτη, τώρα είμαι συγκεντρωμένος σε αυτό το δείκτη.

750
00:57:12,960 --> 00:57:15,150
Τώρα είμαι συγκεντρωμένος σε αυτό το δείκτη.

751
00:57:15,150 --> 00:57:18,160
Έτσι, αν μου κόκκινο δείκτη, η οποία είναι ** κόμβο μου,

752
00:57:18,160 --> 00:57:22,880
είναι ποτέ - σε περίπτωση *, κόκκινο δείκτη μου, δεν είναι ποτέ μηδενική,

753
00:57:22,880 --> 00:57:28,470
αυτό σημαίνει ότι είμαι σε περίπτωση που είμαι εστιάζοντας σε ένα δείκτη που δείχνει -

754
00:57:28,470 --> 00:57:32,530
αυτό είναι ένας δείκτης που ανήκει σε ένα φύλλο.

755
00:57:32,530 --> 00:57:41,090
Θέλω να αλλάξω το δείκτη στο σημείο στο νέο κόμβο μου.

756
00:57:41,090 --> 00:57:45,230
Έλα εδώ.

757
00:57:45,230 --> 00:57:56,490
Newnode μου θα είναι μόνο ο κόμβος * n = build_node (αξία)

758
00:57:56,490 --> 00:58:07,300
τότε n, αν n = NULL, επιστρέφουν ψευδείς.

759
00:58:07,300 --> 00:58:12,600
Αλλιώς θέλουμε να αλλάξουμε ό, τι ο δείκτης δείχνει αυτή τη στιγμή να

760
00:58:12,600 --> 00:58:17,830
τώρα να επισημάνω για νεότευκτα κόμβο μας.

761
00:58:17,830 --> 00:58:20,280
Μπορούμε να το κάνουμε αυτό πραγματικότητα εδώ.

762
00:58:20,280 --> 00:58:30,660
Αντί να λέτε n, λέμε * δέντρο * = εάν δέντρο.

763
00:58:30,660 --> 00:58:35,450
Όλοι καταλαβαίνουν ότι; Ότι με την αντιμετώπιση δείκτες σε δείκτες,

764
00:58:35,450 --> 00:58:40,750
μπορούμε να αλλάξουμε null δείκτες να δείχνουν τα πράγματα που θέλουμε να επισημάνω.

765
00:58:40,750 --> 00:58:42,820
Αυτό είναι το βασικό σενάριο μας.

766
00:58:42,820 --> 00:58:45,740
>> Τώρα υποτροπή μας, ή αναδρομή μας,

767
00:58:45,740 --> 00:58:51,430
πρόκειται να είναι πολύ παρόμοια σε όλες τις άλλες επαναλήψεις έχουμε κάνει.

768
00:58:51,430 --> 00:58:55,830
Εμείς πάμε να θέλετε να εισάγετε αξίας,

769
00:58:55,830 --> 00:58:59,040
και τώρα είμαι πρόκειται να χρησιμοποιήσετε τριμερή πάλι, αλλά αυτό που μας κατάσταση θα είναι;

770
00:58:59,040 --> 00:59:05,180
Τι είναι αυτό που ψάχνουμε για να αποφασίσουμε αν θέλουμε να πάμε προς τα αριστερά ή δεξιά;

771
00:59:05,180 --> 00:59:07,760
Ας το κάνουμε σε ξεχωριστά βήματα.

772
00:59:07,760 --> 00:59:18,850
Αν (τιμή <) τι;

773
00:59:18,850 --> 00:59:23,200
[Φοιτητικό] Η αξία του δέντρου;

774
00:59:23,200 --> 00:59:27,490
[Bowden] Έτσι, να θυμάστε ότι είμαι σήμερα -

775
00:59:27,490 --> 00:59:31,260
[Φοιτητές, ακατάληπτο]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Ναι, έτσι ακριβώς εδώ, ας πούμε ότι αυτό το πράσινο βέλος

777
00:59:34,140 --> 00:59:39,050
είναι ένα παράδειγμα του τι είναι σήμερα δέντρου, είναι ένας δείκτης για αυτό το δείκτη.

778
00:59:39,050 --> 00:59:46,610
Έτσι ώστε σημαίνει ότι είμαι ένας δείκτης σε δείκτη 3.

779
00:59:46,610 --> 00:59:48,800
Η dereference δύο φορές ακούγονται ωραία.

780
00:59:48,800 --> 00:59:51,010
Τι να κάνω - πώς μπορώ να το κάνω αυτό;

781
00:59:51,010 --> 00:59:53,210
[Φοιτητικό] Αποαναφορά μια φορά, και στη συνέχεια κάντε βέλος με αυτόν τον τρόπο;

782
00:59:53,210 --> 00:59:58,420
[Bowden] Έτσι (* δέντρο) είναι η dereference μια φορά, -> αξία

783
00:59:58,420 --> 01:00:05,960
πρόκειται να μου δώσει την τιμή του κόμβου ότι είμαι έμμεσα δείχνοντας.

784
01:00:05,960 --> 01:00:11,980
Έτσι, μπορώ επίσης να γράψετε ** tree.value αν προτιμάτε αυτό.

785
01:00:11,980 --> 01:00:18,490
Είτε δουλεύει.

786
01:00:18,490 --> 01:00:26,190
Αν αυτή είναι η περίπτωση, τότε θα θέλετε να καλέσετε εισάγετε με αξία.

787
01:00:26,190 --> 01:00:32,590
Και τι ενημερώνεται κόμβο μου ** πρόκειται να είναι;

788
01:00:32,590 --> 01:00:39,440
Θέλω να πάω προς τα αριστερά, έτσι ** tree.left πρόκειται να είναι αριστερά μου.

789
01:00:39,440 --> 01:00:41,900
Και θέλω να το δείκτη αυτό το πράγμα

790
01:00:41,900 --> 01:00:44,930
έτσι ώστε εάν το αριστερό καταλήγει να είναι η μηδενική δείκτη,

791
01:00:44,930 --> 01:00:48,360
Μπορώ να το τροποποιήσετε ώστε να δείχνει προς νέο κόμβο μου.

792
01:00:48,360 --> 01:00:51,460
>> Και η άλλη περίπτωση μπορεί να είναι πολύ παρόμοια.

793
01:00:51,460 --> 01:00:55,600
Ας κάνουν ότι πραγματικά τριμερή μου αυτή τη στιγμή.

794
01:00:55,600 --> 01:01:04,480
Τοποθετήστε αξία εάν η αξία <(** δέντρο). Αξία.

795
01:01:04,480 --> 01:01:11,040
Τότε θέλουμε να ενημερώσετε ** μας προς τα αριστερά,

796
01:01:11,040 --> 01:01:17,030
αλλιώς θέλουμε να ενημερώσετε ** μας προς τα δεξιά.

797
01:01:17,030 --> 01:01:22,540
[Φοιτητικό] Μήπως να πάρει ότι το δείκτη στο δείκτη;

798
01:01:22,540 --> 01:01:30,940
[Bowden] Θυμηθείτε ότι - ** tree.right είναι ένας κόμβος αστέρι.

799
01:01:30,940 --> 01:01:35,040
[Φοιτητών, ακατάληπτο] >> Ναι.

800
01:01:35,040 --> 01:01:41,140
** Tree.right είναι σαν αυτό το δείκτη ή κάτι τέτοιο.

801
01:01:41,140 --> 01:01:45,140
Έτσι, με τη λήψη ενός δείκτη με αυτό, που μου δίνει αυτό που θέλω

802
01:01:45,140 --> 01:01:50,090
του δείκτη σε αυτόν τον τύπο.

803
01:01:50,090 --> 01:01:54,260
[Φοιτητικό] Θα μπορούσαμε να πάμε ξανά γιατί χρησιμοποιούμε τα δίποντα;

804
01:01:54,260 --> 01:01:58,220
[Bowden] Ναι. Έτσι - δεν μπορείτε, και ότι η λύση πριν από

805
01:01:58,220 --> 01:02:04,540
Ήταν ένας τρόπος για να γίνει αυτό χωρίς να κάνει δύο δείκτες.

806
01:02:04,540 --> 01:02:08,740
Θα πρέπει να είναι σε θέση να κατανοήσουν τη χρήση δίποντα,

807
01:02:08,740 --> 01:02:11,660
και αυτό είναι ένα καθαρότερο διάλυμα.

808
01:02:11,660 --> 01:02:16,090
Επίσης, παρατηρούμε ότι, ό, τι θα συμβεί αν το δέντρο μου -

809
01:02:16,090 --> 01:02:24,480
τι θα συμβεί αν ρίζα μου ήταν μηδενική; Τι θα συμβεί αν κάνω αυτή την περίπτωση εδώ;

810
01:02:24,480 --> 01:02:30,540
Έτσι, ο κόμβος ρίζα * = NULL, εισάγετε & 4 σε ρίζα.

811
01:02:30,540 --> 01:02:35,110
Τι είναι η ρίζα πρόκειται να είναι μετά από αυτό;

812
01:02:35,110 --> 01:02:37,470
[Φοιτητών, ακατάληπτο] >> Ναι.

813
01:02:37,470 --> 01:02:41,710
Root αξία θα είναι 4.

814
01:02:41,710 --> 01:02:45,510
Root αριστερά θα είναι μηδενική, το δικαίωμα ρίζα θα είναι μηδενική.

815
01:02:45,510 --> 01:02:49,490
Στην περίπτωση όπου δεν περνούν ρίζας κατά διεύθυνση,

816
01:02:49,490 --> 01:02:52,490
δεν θα μπορούσε να τροποποιήσει ρίζα.

817
01:02:52,490 --> 01:02:56,020
Στην περίπτωση όπου το δέντρο - όπου root ήταν μηδενική,

818
01:02:56,020 --> 01:02:58,410
εμείς απλά έπρεπε να επιστρέψει ψευδείς. Δεν υπάρχει τίποτα που θα μπορούσαμε να κάνουμε.

819
01:02:58,410 --> 01:03:01,520
Δεν μπορείτε να εισαγάγετε έναν κόμβο σε ένα άδειο δέντρο.

820
01:03:01,520 --> 01:03:06,810
Αλλά τώρα μπορούμε? Κάνουμε απλώς ένα άδειο δέντρο σε ένα κόμβο του δένδρου.

821
01:03:06,810 --> 01:03:13,400
Ποιο είναι συνήθως το αναμενόμενο τρόπο ώστε να είναι υποτίθεται ότι πρέπει να εργάζονται.

822
01:03:13,400 --> 01:03:21,610
>> Επιπλέον, αυτό είναι σημαντικά μικρότερος από ό, τι

823
01:03:21,610 --> 01:03:26,240
επίσης την παρακολούθηση της μητρικής, και έτσι μπορείτε επαναλάβει τα κάτω σε όλη τη διαδρομή.

824
01:03:26,240 --> 01:03:30,140
Τώρα έχω γονέα μου, και έχω μόνο γονέα δείκτη μου δικαίωμα να το οτιδήποτε.

825
01:03:30,140 --> 01:03:35,640
Αντ 'αυτού, αν το κάναμε αυτό επαναληπτικό, θα ήθελα να είναι η ίδια ιδέα με ένα βρόχο while.

826
01:03:35,640 --> 01:03:38,100
Όμως, αντί να πρέπει να ασχοληθεί με το δείκτη των γονιών μου,

827
01:03:38,100 --> 01:03:40,600
αντί τρέχουσα δείκτης μου θα είναι το πράγμα

828
01:03:40,600 --> 01:03:43,790
ότι είμαι άμεσα τροποποίηση στο σημείο στο νέο κόμβο μου.

829
01:03:43,790 --> 01:03:46,090
Δεν έχω να ασχοληθεί με το αν είναι στραμμένη προς τα αριστερά.

830
01:03:46,090 --> 01:03:48,810
Δεν έχω να ασχοληθεί με το αν είναι στραμμένη προς τα δεξιά.

831
01:03:48,810 --> 01:04:00,860
Είναι ακριβώς ό, τι αυτό δείκτης, Πάω να το ρυθμίσετε να επισημάνει νέο κόμβο μου.

832
01:04:00,860 --> 01:04:05,740
Όλοι καταλαβαίνουν πώς λειτουργεί;

833
01:04:05,740 --> 01:04:09,460
Αν γιατί δεν θέλουμε να το κάνουμε με αυτόν τον τρόπο,

834
01:04:09,460 --> 01:04:14,920
αλλά τουλάχιστον ότι αυτό λειτουργεί ως λύση;

835
01:04:14,920 --> 01:04:17,110
[Φοιτητικό] Πού θα επιστρέψει αλήθεια;

836
01:04:17,110 --> 01:04:21,550
[Bowden] Αυτό είναι πιθανώς ακριβώς εδώ.

837
01:04:21,550 --> 01:04:26,690
Αν τοποθετήσετε σωστά, επιστρέψτε αλήθεια.

838
01:04:26,690 --> 01:04:32,010
Αλλιώς, εδώ κάτω θα πάμε να θέλουν να επιστρέψουν και υπό οποιεσδήποτε δηλώσεις ένθετο.

839
01:04:32,010 --> 01:04:35,950
>> Και τι είναι αυτό το ιδιαίτερο αναδρομική συνάρτηση;

840
01:04:35,950 --> 01:04:43,010
Είναι ουρά επαναληπτικό, έτσι εφ 'όσον έχουμε καταρτίσει με κάποια βελτιστοποίηση,

841
01:04:43,010 --> 01:04:48,060
θα αναγνωρίσουμε ότι και εσείς ποτέ δεν θα πάρετε μια στοίβα από υπερχείλιση αυτό,

842
01:04:48,060 --> 01:04:53,230
ακόμη και αν μας δέντρο έχει ύψος 10.000 ή 10 εκατ. ευρώ.

843
01:04:53,230 --> 01:04:55,630
[Φοιτητών, ακατάληπτο]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Νομίζω ότι το κάνει στο Dash - ή τι επίπεδο βελτιστοποίησης

845
01:05:00,310 --> 01:05:03,820
απαιτείται για ένα αναδρομή ουράς να αναγνωριστεί.

846
01:05:03,820 --> 01:05:09,350
Νομίζω ότι αναγνωρίζει - Συμβουλίου Συνεργασίας του Κόλπου και Clang

847
01:05:09,350 --> 01:05:12,610
Επίσης, έχει διαφορετικές σημασίες για τη βελτιστοποίηση των επιπέδων τους.

848
01:05:12,610 --> 01:05:17,870
Θέλω να πω ότι είναι Dasho 2, είναι σίγουρο ότι θα αναγνωρίσουν την ουρά αναδρομή.

849
01:05:17,870 --> 01:05:27,880
Αλλά εμείς - θα μπορούσατε να κατασκευάσει σαν παράδειγμα Fibonocci ή κάτι τέτοιο.

850
01:05:27,880 --> 01:05:30,030
Δεν είναι εύκολο να δοκιμάσει με αυτό, επειδή είναι δύσκολο να κατασκευάσει

851
01:05:30,030 --> 01:05:32,600
ένα δυαδικό δέντρο που είναι τόσο μεγάλο.

852
01:05:32,600 --> 01:05:37,140
Αλλά ναι, νομίζω ότι είναι Dasho 2, που

853
01:05:37,140 --> 01:05:40,580
αν φτιάξετε με Dasho 2, θα ψάξει για αναδρομή ουρά

854
01:05:40,580 --> 01:05:54,030
και τη βελτιστοποίηση ότι έξω.

855
01:05:54,030 --> 01:05:58,190
Ας πάμε πίσω στο - εισαγωγή είναι κυριολεκτικά το τελευταίο πράγμα που χρειάζεται.

856
01:05:58,190 --> 01:06:04,900
Ας πάμε πίσω στο ένθετο εδώ

857
01:06:04,900 --> 01:06:07,840
όπου θα πάμε για να κάνουμε την ίδια ιδέα.

858
01:06:07,840 --> 01:06:14,340
Θα εξακολουθούν να έχουν το ελάττωμα να μην είναι σε θέση να χειριστεί εξ ολοκλήρου

859
01:06:14,340 --> 01:06:17,940
όταν η ίδια η ρίζα είναι μηδενική, ή η τελευταία είσοδος είναι μηδενική,

860
01:06:17,940 --> 01:06:20,060
αλλά αντί ασχολούνται με ένα δείκτη γονέα,

861
01:06:20,060 --> 01:06:27,430
ας εφαρμόσουμε την ίδια λογική της διατήρησης δείκτες σε δείκτες.

862
01:06:27,430 --> 01:06:35,580
Αν εδώ κρατάμε τον κόμβο μας ** τρέχουσα,

863
01:06:35,580 --> 01:06:37,860
και δεν χρειάζεται να παρακολουθείτε το δικαίωμα πια,

864
01:06:37,860 --> 01:06:47,190
αλλά κόμβος ** τρέχουσα = & δέντρο.

865
01:06:47,190 --> 01:06:54,800
Και τώρα βρόχο, ενώ μας πρόκειται να είναι, ενώ τρέχουσα * δεν ισούται null.

866
01:06:54,800 --> 01:07:00,270
Δεν χρειάζεται να παρακολουθείτε γονείς πια.

867
01:07:00,270 --> 01:07:04,180
Δεν χρειάζεται να παρακολουθείτε από αριστερά και δεξιά.

868
01:07:04,180 --> 01:07:10,190
Και εγώ θα το ονομάσουμε θερμοκρασία, γιατί είμαστε ήδη χρησιμοποιούν temp.

869
01:07:10,190 --> 01:07:17,200
Εντάξει. Έτσι, αν (τιμή> * temp),

870
01:07:17,200 --> 01:07:24,010
τότε & (* temp) -> δικαίωμα

871
01:07:24,010 --> 01:07:29,250
άλλο temp = & (* temp) -> αριστερά.

872
01:07:29,250 --> 01:07:32,730
Και τώρα, σε αυτό το σημείο, μετά από αυτό το βρόχο while,

873
01:07:32,730 --> 01:07:36,380
Κάνω μόνο αυτό, γιατί ίσως είναι πιο εύκολο να σκεφτούμε επαναληπτικά από αναδρομικά,

874
01:07:36,380 --> 01:07:39,010
αλλά μετά από αυτό το βρόχο while,

875
01:07:39,010 --> 01:07:43,820
* Temp είναι ο δείκτης που θέλουμε να αλλάξουμε.

876
01:07:43,820 --> 01:07:48,960
>> Πριν είχαμε γονέα, και θα ήθελε να αλλάξει είτε αριστερά γονέα ή γονέων δικαίωμα,

877
01:07:48,960 --> 01:07:51,310
αλλά αν θέλουμε να αλλάξουμε το δικαίωμα γονέα,

878
01:07:51,310 --> 01:07:54,550
* temp τότε είναι σωστό γονέα, και μπορούμε να το αλλάξουμε άμεσα.

879
01:07:54,550 --> 01:08:05,860
Έτσι, εδώ κάτω, μπορούμε να κάνουμε * temp = newnode, και αυτό είναι αυτό.

880
01:08:05,860 --> 01:08:09,540
Έτσι ειδοποίηση, όλοι κάναμε σε αυτό ήταν να πάρουν τις γραμμές του κώδικα.

881
01:08:09,540 --> 01:08:14,770
Για να παρακολουθείτε της μητρικής σε όλα αυτά είναι επιπλέον προσπάθεια.

882
01:08:14,770 --> 01:08:18,689
Εδώ, αν κρατάμε μόνο κομμάτι του δείκτη στο δείκτη,

883
01:08:18,689 --> 01:08:22,990
και ακόμα και αν θέλαμε να απαλλαγούμε από όλα αυτά τα άγκιστρα τώρα,

884
01:08:22,990 --> 01:08:27,170
να φανεί μικρότερο.

885
01:08:27,170 --> 01:08:32,529
Αυτή είναι τώρα η ίδια ακριβώς λύση,

886
01:08:32,529 --> 01:08:38,210
αλλά λιγότερες γραμμές κώδικα.

887
01:08:38,210 --> 01:08:41,229
Μόλις αρχίσετε να αναγνωρίζει ως έγκυρη λύση,

888
01:08:41,229 --> 01:08:43,529
Είναι επίσης ευκολότερο να λόγος για παρά σαν, εντάξει,

889
01:08:43,529 --> 01:08:45,779
γιατί έχω αυτή την σημαία σε int δικαίωμα;

890
01:08:45,779 --> 01:08:49,290
Τι σημαίνει αυτό; Ω, αυτό είναι που σημαίνει ότι

891
01:08:49,290 --> 01:08:51,370
κάθε φορά που πάω δεξιά, πρέπει να το ρυθμίσετε,

892
01:08:51,370 --> 01:08:53,819
αλλιώς αν πάω αριστερά θα πρέπει να οριστεί σε μηδέν.

893
01:08:53,819 --> 01:09:04,060
Εδώ, δεν έχω λόγο να γι 'αυτό? Είναι απλά πιο εύκολο να σκεφτούμε.

894
01:09:04,060 --> 01:09:06,710
Ερωτήσεις;

895
01:09:06,710 --> 01:09:16,290
[Φοιτητών, ακατάληπτο] >> Ναι.

896
01:09:16,290 --> 01:09:23,359
Εντάξει, έτσι το τελευταίο κομμάτι -

897
01:09:23,359 --> 01:09:28,080
Υποθέτω ότι μια γρήγορη και εύκολη λειτουργία που μπορούμε να κάνουμε είναι,

898
01:09:28,080 --> 01:09:34,910
let's - μαζί, υποθέτω, προσπαθήστε και γράψτε μια συνάρτηση περιέχει

899
01:09:34,910 --> 01:09:38,899
η οποία δεν ενδιαφέρεται αν είναι ένα δυαδικό δέντρο αναζήτησης.

900
01:09:38,899 --> 01:09:43,770
Αυτό περιλαμβάνει τη λειτουργία θα πρέπει να επιστρέψει αλήθεια

901
01:09:43,770 --> 01:09:58,330
αν οπουδήποτε σε αυτό το γενικό δυαδικού δένδρου είναι η τιμή που ψάχνουμε.

902
01:09:58,330 --> 01:10:02,520
Ας κάνουμε πρώτα αναδρομικά και στη συνέχεια θα το κάνουμε επαναληπτικά.

903
01:10:02,520 --> 01:10:07,300
Μπορούμε πραγματικά να κάνουμε αυτό ακριβώς μαζί, γιατί αυτό θα είναι πολύ σύντομη.

904
01:10:07,300 --> 01:10:11,510
>> Τι είναι η βασική περίπτωση μου πρόκειται να;

905
01:10:11,510 --> 01:10:13,890
[Φοιτητών, ακατάληπτο]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Έτσι, εάν (δέντρο == NULL), τότε τι;

907
01:10:18,230 --> 01:10:22,740
[Φοιτητικό] Επιστροφή ψευδείς.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Αλλιώς, καλά, δεν χρειάζεται το άλλο.

909
01:10:26,160 --> 01:10:30,250
Αν ήταν άλλη περίπτωση βάσης μου.

910
01:10:30,250 --> 01:10:32,450
Αξία [Φοιτητών] Δέντρο της; Ναι >>.

911
01:10:32,450 --> 01:10:36,430
Έτσι, αν (δέντρο-> == αξία αξίας.

912
01:10:36,430 --> 01:10:39,920
Παρατηρήστε ότι είμαστε πίσω σε κόμβο * όχι, ο κόμβος s **;

913
01:10:39,920 --> 01:10:42,990
Περιέχει ποτέ δεν θα χρειαστεί να χρησιμοποιήσετε ένα ** κόμβο,

914
01:10:42,990 --> 01:10:45,480
δεδομένου ότι δεν τροποποιούν δείκτες.

915
01:10:45,480 --> 01:10:50,540
Είμαστε απλώς διέρχονται από αυτούς.

916
01:10:50,540 --> 01:10:53,830
Αν αυτό συμβεί, τότε θα θέλουν να επιστρέψουν αλήθεια.

917
01:10:53,830 --> 01:10:58,270
Αλλιώς θέλουμε να διασχίζουν τα παιδιά.

918
01:10:58,270 --> 01:11:02,620
Έτσι, δεν μπορούμε να σκεφτούν σχετικά με το αν τα πάντα προς τα αριστερά είναι λιγότερο

919
01:11:02,620 --> 01:11:05,390
και τα πάντα προς τα δεξιά είναι μεγαλύτερη.

920
01:11:05,390 --> 01:11:09,590
Έτσι, αυτό που μας κατάσταση θα είναι εδώ - ή, τι θα κάνουμε;

921
01:11:09,590 --> 01:11:11,840
[Φοιτητών, ακατάληπτο] >> Ναι.

922
01:11:11,840 --> 01:11:17,400
Επιστροφή περιέχει (αξία, δέντρο-> αριστερά)

923
01:11:17,400 --> 01:11:26,860
ή περιέχει (αξία, δέντρο-> δεξιά). Και αυτό είναι αυτό.

924
01:11:26,860 --> 01:11:29,080
Και παρατηρήσετε υπάρχει κάποια βραχυκύκλωμα αξιολόγησης,

925
01:11:29,080 --> 01:11:32,520
όπου αν τυχαίνει να βρείτε την τιμή στο αριστερό δέντρο,

926
01:11:32,520 --> 01:11:36,820
ποτέ δεν πρέπει να κοιτάξουμε στο σωστό δέντρο.

927
01:11:36,820 --> 01:11:40,430
Αυτή είναι η όλη λειτουργία.

928
01:11:40,430 --> 01:11:43,690
Τώρα, ας το κάνουμε επαναληπτικά,

929
01:11:43,690 --> 01:11:48,060
η οποία θα είναι λιγότερο ωραίο.

930
01:11:48,060 --> 01:11:54,750
Θα λάβει τη συνήθη έναρξη του κόμβου * = τρέχουσα δέντρο.

931
01:11:54,750 --> 01:12:03,250
Ενώ (τρέχουσα! = NULL).

932
01:12:03,250 --> 01:12:08,600
Γρήγορα θα δείτε ένα πρόβλημα.

933
01:12:08,600 --> 01:12:12,250
Αν τρέχουσα - από εδώ, αν ποτέ ξεφύγει από αυτό,

934
01:12:12,250 --> 01:12:16,020
τότε έχουμε εξαντληθεί τα πράγματα να δούμε, έτσι επιστρέφουν ψευδείς.

935
01:12:16,020 --> 01:12:24,810
Αν (τρέχουσα-> αξία αξίας ==), επιστρέφουν αλήθεια.

936
01:12:24,810 --> 01:12:32,910
Μέχρι τώρα, είμαστε σε θέση -

937
01:12:32,910 --> 01:12:36,250
δεν ξέρουμε αν θέλουμε να πάμε αριστερά ή προς τα δεξιά.

938
01:12:36,250 --> 01:12:44,590
Έτσι αυθαίρετα, ας πάμε αριστερά.

939
01:12:44,590 --> 01:12:47,910
Έχω προφανώς τρέχει σε ένα θέμα για το οποίο έχω εγκαταλείψει εντελώς τα πάντα -

940
01:12:47,910 --> 01:12:50,760
Θα ελέγξει ποτέ μόνο την αριστερή πλευρά του δέντρου.

941
01:12:50,760 --> 01:12:56,050
Ποτέ δεν θα ελέγξει κάτι που αποτελεί δικαίωμα του παιδιού τίποτα.

942
01:12:56,050 --> 01:13:00,910
Πώς μπορώ να το διορθώσω αυτό;

943
01:13:00,910 --> 01:13:05,260
[Φοιτητικό] Θα πρέπει να παρακολουθείτε την αριστερή και δεξιά σε μια στοίβα.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Ναι. Ας κάνουν

945
01:13:13,710 --> 01:13:32,360
struct λίστα, ο κόμβος * n, και στη συνέχεια ο κόμβος ** επόμενος;

946
01:13:32,360 --> 01:13:40,240
Νομίζω ότι δουλεύει μια χαρά.

947
01:13:40,240 --> 01:13:45,940
Θέλουμε να πάμε πάνω από το αριστερό, ή let's - μέχρι εδώ.

948
01:13:45,940 --> 01:13:54,350
Struct = κατάλογος λίστα, αυτό θα αρχίσει

949
01:13:54,350 --> 01:13:58,170
από αυτή τη λίστα struct.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Έτσι, αυτό πρόκειται να είναι συνδεδεμένη λίστα μας

951
01:14:04,040 --> 01:14:08,430
των υποδένδρων ότι έχουμε παρακάμπτονται.

952
01:14:08,430 --> 01:14:13,800
Θα διασχίσει φύγει τώρα,

953
01:14:13,800 --> 01:14:17,870
αλλά από τη στιγμή που αναπόφευκτα πρέπει να έρθουν πίσω προς τα δεξιά,

954
01:14:17,870 --> 01:14:26,140
Εμείς πάμε για να κρατήσει τη δεξιά πλευρά στο εσωτερικό της λίστας struct μας.

955
01:14:26,140 --> 01:14:32,620
Τότε θα έχουμε new_list ή struct,

956
01:14:32,620 --> 01:14:41,080
* struct λίστα, new_list = malloc (sizeof (κατάλογος)).

957
01:14:41,080 --> 01:14:44,920
Πάω να αγνοήσει λάθος-ότι ο έλεγχος, αλλά θα πρέπει να ελέγξετε για να δείτε null αν είναι.

958
01:14:44,920 --> 01:14:50,540
New_list τον κόμβο πρόκειται να επισημάνω -

959
01:14:50,540 --> 01:14:56,890
Ω, αυτός είναι ο λόγος που ήθελε εδώ. Είναι πρόκειται να επισημάνω για μια δεύτερη λίστα struct.

960
01:14:56,890 --> 01:15:02,380
Αυτό είναι ακριβώς το πώς συνδέονται λίστες εργασίας.

961
01:15:02,380 --> 01:15:04,810
Αυτό είναι το ίδιο με ένα κατάλογο που συνδέονται int

962
01:15:04,810 --> 01:15:06,960
εκτός είμαστε αντικαθιστώντας απλά int * με τον κόμβο.

963
01:15:06,960 --> 01:15:11,040
Είναι ακριβώς η ίδια.

964
01:15:11,040 --> 01:15:15,100
Έτσι new_list, η τιμή του κόμβου new_list μας,

965
01:15:15,100 --> 01:15:19,120
πρόκειται να είναι τρέχουσα-> δεξιά.

966
01:15:19,120 --> 01:15:24,280
Η αξία των new_list μας-> επόμενο θα είναι αρχική λίστα μας,

967
01:15:24,280 --> 01:15:30,760
και στη συνέχεια θα πάμε να ενημερώσετε τον κατάλογο μας στο σημείο να new_list.

968
01:15:30,760 --> 01:15:33,650
>> Τώρα χρειαζόμαστε κάποιο είδος της τρόπο τραβώντας τα πράγματα,

969
01:15:33,650 --> 01:15:37,020
όπως έχουμε διασχίσει ολόκληρο το αριστερό υποδέντρο.

970
01:15:37,020 --> 01:15:40,480
Τώρα πρέπει να τραβήξει τα πράγματα έξω από αυτό,

971
01:15:40,480 --> 01:15:43,850
όπως η τρέχουσα είναι null? δεν θέλουμε απλά να επιστρέψει ψευδείς.

972
01:15:43,850 --> 01:15:50,370
Θέλουμε να τραβήξει έξω τώρα στη νέα λίστα μας.

973
01:15:50,370 --> 01:15:53,690
Ένας εύκολος τρόπος για να γίνει αυτό - και, στην πραγματικότητα, δεν υπάρχει πολλαπλούς τρόπους για να γίνει αυτό.

974
01:15:53,690 --> 01:15:56,680
Όποιος έχει κάποια πρόταση;

975
01:15:56,680 --> 01:15:58,790
Πού πρέπει να κάνω αυτό ή το πώς θα πρέπει να το κάνετε αυτό;

976
01:15:58,790 --> 01:16:08,010
Έχουμε μόνο μερικά λεπτά, αλλά οποιεσδήποτε προτάσεις;

977
01:16:08,010 --> 01:16:14,750
Αντί - ένας τρόπος, αντί να μας κατάσταση ενώ,

978
01:16:14,750 --> 01:16:17,090
ό, τι είμαστε σήμερα κοιτάζοντας δεν είναι μηδενική,

979
01:16:17,090 --> 01:16:22,340
αντί να πάμε να συνεχίσουμε να πάει μέχρι λίστα μας είναι η ίδια άκυρη.

980
01:16:22,340 --> 01:16:25,680
Έτσι, αν λίστα μας καταλήγει να είναι μηδενική,

981
01:16:25,680 --> 01:16:30,680
τότε έχουμε εξαντληθεί τα πράγματα να αναζητήσουμε, να αναζητήσετε πάνω.

982
01:16:30,680 --> 01:16:39,860
Αλλά αυτό σημαίνει ότι το πρώτο πράγμα στη λίστα μας είναι ακριβώς πρόκειται να είναι ο πρώτος κόμβος.

983
01:16:39,860 --> 01:16:49,730
Το πρώτο πράγμα που θα είναι - δεν έχουμε πλέον πρέπει να δούμε ότι.

984
01:16:49,730 --> 01:16:58,710
Έτσι λίστα-> n θα είναι δέντρο μας.

985
01:16:58,710 --> 01:17:02,860
list-> επόμενο θα είναι μηδενική.

986
01:17:02,860 --> 01:17:07,580
Και τώρα, ενώ λίστα δεν είναι ίσο με null.

987
01:17:07,580 --> 01:17:11,610
Cur πρόκειται να τραβήξει κάτι από την λίστα μας.

988
01:17:11,610 --> 01:17:13,500
Έτσι τρέχουσα πρόκειται για ίση λίστα-> n.

989
01:17:13,500 --> 01:17:20,850
Και τότε η λίστα θα ίση λίστα-> n, ή λίστα-> επόμενο.

990
01:17:20,850 --> 01:17:23,480
Έτσι, αν η αξία ισούται με τρέχουσα αξία.

991
01:17:23,480 --> 01:17:28,790
Τώρα μπορούμε να προσθέσουμε και τα δύο δεξιά δείκτη μας και αριστερά μας το δείκτη

992
01:17:28,790 --> 01:17:32,900
εφ 'όσον δεν είστε null.

993
01:17:32,900 --> 01:17:36,390
Εδώ κάτω, υποθέτω ότι θα έπρεπε να είχαμε κάνει αυτό στην πρώτη θέση.

994
01:17:36,390 --> 01:17:44,080
Αν (τρέχουσα-> δεξιά! = NULL)

995
01:17:44,080 --> 01:17:56,380
τότε θα πρόκειται να εισαγάγει τις κόμβο στη λίστα μας.

996
01:17:56,380 --> 01:17:59,290
Αν (τρέχουσα-> αριστερά), αυτό είναι ένα μικρό κομμάτι του φόρτου εργασίας, αλλά είναι μια χαρά.

997
01:17:59,290 --> 01:18:02,690
Αν (τρέχουσα-> αριστερά! = NULL),

998
01:18:02,690 --> 01:18:14,310
και θα πάμε για να εισάγετε το αριστερό σε συνδεδεμένη λίστα μας,

999
01:18:14,310 --> 01:18:19,700
και ότι θα πρέπει να είναι αυτό.

1000
01:18:19,700 --> 01:18:22,670
Έχουμε επαναλάβει - εφ 'όσον έχουμε κάτι στη λίστα μας,

1001
01:18:22,670 --> 01:18:26,640
έχουμε ένα άλλο κόμβο να δούμε.

1002
01:18:26,640 --> 01:18:28,920
Έτσι βλέπουμε σε αυτόν τον κόμβο,

1003
01:18:28,920 --> 01:18:31,390
προχωρούμε λίστα μας για το επόμενο.

1004
01:18:31,390 --> 01:18:34,060
Αν αυτός ο κόμβος είναι η τιμή που ψάχνουμε, μπορούμε να επιστρέψουμε αλήθεια.

1005
01:18:34,060 --> 01:18:37,640
Αλλιώς τοποθετήστε τα δύο αριστερά και δεξιά υποδένδρων μας,

1006
01:18:37,640 --> 01:18:40,510
εφ 'όσον δεν είστε null, στην λίστα μας

1007
01:18:40,510 --> 01:18:43,120
έτσι ώστε να πάμε αναπόφευκτα πάνω τους.

1008
01:18:43,120 --> 01:18:45,160
Έτσι, αν δεν ήταν άκυρη,

1009
01:18:45,160 --> 01:18:47,950
αν ο δείκτης ρίζα μας επεσήμανε δύο πράγματα,

1010
01:18:47,950 --> 01:18:51,670
τότε στο πρώτο μας τράβηξε κάτι έτσι λίστα μας καταλήγει να είναι null.

1011
01:18:51,670 --> 01:18:56,890
Και στη συνέχεια, βάζουμε δύο πράγματα πίσω στο, έτσι τώρα λίστα μας είναι το μέγεθος 2.

1012
01:18:56,890 --> 01:19:00,030
Στη συνέχεια θα πάμε στο βρόχο πίσω και είμαστε ακριβώς πρόκειται να τραβήξει,

1013
01:19:00,030 --> 01:19:04,250
ας πούμε, το αριστερό δείκτη του ριζικού κόμβου μας.

1014
01:19:04,250 --> 01:19:07,730
Και αυτό ακριβώς θα συνεχίζουν να συμβαίνουν? Θα καταλήξουμε looping πάνω από όλα.

1015
01:19:07,730 --> 01:19:11,280
>> Παρατηρήστε ότι αυτή ήταν σημαντικά πιο περίπλοκη

1016
01:19:11,280 --> 01:19:14,160
στο επαναληπτικό διάλυμα.

1017
01:19:14,160 --> 01:19:17,260
Και έχω πει πολλές φορές

1018
01:19:17,260 --> 01:19:25,120
ότι η αναδρομική λύση έχει συνήθως πολλά κοινά με την επαναληπτική λύση.

1019
01:19:25,120 --> 01:19:30,820
Εδώ αυτό είναι ακριβώς ό, τι η αναδρομική λύση είναι να κάνει.

1020
01:19:30,820 --> 01:19:36,740
Η μόνη μεταβολή είναι ότι αντί της εμμέσως χρησιμοποιώντας τη στοίβα, η στοίβα του προγράμματος,

1021
01:19:36,740 --> 01:19:40,840
ως το δρόμο σας από την παρακολούθηση του τι κόμβους θα πρέπει ακόμα να επισκεφθείτε,

1022
01:19:40,840 --> 01:19:45,430
τώρα θα πρέπει να χρησιμοποιήσετε ρητά μια συνδεδεμένη λίστα.

1023
01:19:45,430 --> 01:19:49,070
Και στις δύο περιπτώσεις που η παρακολούθηση του κόμβου τι χρειάζεται ακόμη να επισκεφθεί.

1024
01:19:49,070 --> 01:19:51,790
Σε περίπτωση επαναληπτικής είναι απλά πιο εύκολο, διότι μια στοίβα

1025
01:19:51,790 --> 01:19:57,100
υλοποιείται για εσάς ως τη στοίβα του προγράμματος.

1026
01:19:57,100 --> 01:19:59,550
Παρατηρήστε ότι αυτή η συνδεδεμένη λίστα, είναι μια στοίβα.

1027
01:19:59,550 --> 01:20:01,580
Ό, τι ακριβώς τοποθετούνται στη στοίβα

1028
01:20:01,580 --> 01:20:09,960
είναι αμέσως τι θα πάμε να τραβήξει από τη στοίβα για να επισκεφθείτε επόμενη.

1029
01:20:09,960 --> 01:20:14,380
Είμαστε έξω από το χρόνο, αλλά κάποιες ερωτήσεις;

1030
01:20:14,380 --> 01:20:23,530
[Φοιτητών, ακατάληπτο]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Ναι. Έτσι, αν έχουμε συνδεδεμένη λίστα μας,

1032
01:20:27,790 --> 01:20:30,150
ρεύμα πρόκειται να επισημάνει αυτόν τον τύπο,

1033
01:20:30,150 --> 01:20:34,690
και τώρα είμαστε μόλις προώθηση συνδεδεμένη λίστα μας για να επικεντρωθεί σε αυτόν τον τύπο.

1034
01:20:34,690 --> 01:20:44,200
Είμαστε διέρχονται πάνω από τη συνδεδεμένη λίστα σε αυτή τη γραμμή.

1035
01:20:44,200 --> 01:20:51,200
Και τότε υποθέτω ότι θα πρέπει να ελευθερώσετε συνδεδεμένη λίστα και τα πράγματα μας

1036
01:20:51,200 --> 01:20:53,880
μία φορά πριν επιστρέψει αληθής ή ψευδής, θα πρέπει να

1037
01:20:53,880 --> 01:20:57,360
επαναλάβει σε συνδεδεμένη λίστα μας και πάντα εδώ κάτω, υποθέτω,

1038
01:20:57,360 --> 01:21:03,900
αν τρέχουσα δικαίωμα δεν είναι ίσο με το προσθέσετε, έτσι και τώρα θέλουμε να ελευθερώσετε

1039
01:21:03,900 --> 01:21:09,600
τρέχουσα επειδή, καλά, δεν μπορούμε να ξεχάσουμε εντελώς την λίστα; Ναι.

1040
01:21:09,600 --> 01:21:12,880
Έτσι, αυτό είναι που θέλουμε να κάνουμε εδώ.

1041
01:21:12,880 --> 01:21:16,730
Πού είναι ο δείκτης;

1042
01:21:16,730 --> 01:21:23,320
Cur ήταν τότε - θέλουμε μια λίστα struct * 10 ισούται με λίστα δίπλα.

1043
01:21:23,320 --> 01:21:29,240
Δωρεάν κατάλογος, κατάλογος = temp.

1044
01:21:29,240 --> 01:21:32,820
Και στην περίπτωση που θα επιστρέψει αλήθεια, χρειαζόμαστε να επαναλάβει

1045
01:21:32,820 --> 01:21:37,050
πάνω από το υπόλοιπο των συνδεδεμένων λίστα μας απελευθερώνοντας τα πράγματα.

1046
01:21:37,050 --> 01:21:39,700
Το θετικό σχετικά με την αναδρομική λύση είναι απελευθερώνοντας τα πράγματα

1047
01:21:39,700 --> 01:21:44,930
ακριβώς σημαίνει βρεθώ factorings από τη στοίβα που θα συμβεί για σας.

1048
01:21:44,930 --> 01:21:50,720
Έτσι, έχουμε περάσει από κάτι που είναι σαν 3 γραμμές είναι δύσκολο να σκεφτούμε-για τον κωδικό

1049
01:21:50,720 --> 01:21:57,520
σε κάτι που είναι σημαντικά πιο πολλά είναι δύσκολο να σκεφτούμε-για τις γραμμές του κώδικα.

1050
01:21:57,520 --> 01:22:00,620
Κάθε άλλες ερωτήσεις;

1051
01:22:00,620 --> 01:22:08,760
Εντάξει. Είμαστε καλά. Αντίο!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]