1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Sezione 7: più confortevole]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[Questo è CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Bene. Così come ho detto nella mia e-mail,

5
00:00:10,110 --> 00:00:14,060
questo sta andando essere un albero binario ad alta intensità di sezione.

6
00:00:14,060 --> 00:00:16,820
Ma non ci sono che molte domande.

7
00:00:16,820 --> 00:00:18,920
Quindi stiamo andando a cercare di tirar fuori ogni domanda

8
00:00:18,920 --> 00:00:25,430
ed entrare nei dettagli dolorosa di tutti i modi migliori di fare le cose.

9
00:00:25,430 --> 00:00:31,200
Quindi, fin dall'inizio, si va attraverso il disegno di campionamento di alberi binari e roba del genere.

10
00:00:31,200 --> 00:00:35,970
Quindi, ecco, "Ricordati che un albero binario con nodi simili a quelle di una lista concatenata,

11
00:00:35,970 --> 00:00:38,150
tranne che invece di un puntatore ce ne sono due: uno per 'bambino' a sinistra

12
00:00:38,150 --> 00:00:41,950
e uno per il diritto di 'bambino' ".

13
00:00:41,950 --> 00:00:45,630
Quindi, un albero binario è come una lista concatenata,

14
00:00:45,630 --> 00:00:47,910
tranne la struttura sta per avere due puntatori.

15
00:00:47,910 --> 00:00:51,390
Ci sono alberi ternario, che stanno per avere tre puntatori,

16
00:00:51,390 --> 00:00:56,540
ci sono N-arie alberi, che appena hanno un puntatore generico

17
00:00:56,540 --> 00:01:00,320
che è quindi necessario malloc essere grande abbastanza per avere

18
00:01:00,320 --> 00:01:04,840
puntatori sufficiente a tutti i bambini possibili.

19
00:01:04,840 --> 00:01:08,200
Così albero binario succede solo per avere un numero costante di due.

20
00:01:08,200 --> 00:01:11,260
Se si vuole, si può dare una lista concatenata come un albero unario,

21
00:01:11,260 --> 00:01:15,360
ma io non credo che nessuno lo chiama così.

22
00:01:15,360 --> 00:01:18,060
"Disegna un box-e-frecce diagramma di un nodo dell'albero binario

23
00:01:18,060 --> 00:01:24,110
contenente il numero preferito di Nate, 7, dove ogni puntatore bambino è nulla. "

24
00:01:24,110 --> 00:01:27,780
Modalità Così iPad.

25
00:01:27,780 --> 00:01:30,280
>> E 'intenzione di essere abbastanza semplice.

26
00:01:30,280 --> 00:01:36,150
Stiamo solo andando ad avere un nodo, io lo disegnare come un quadrato.

27
00:01:36,150 --> 00:01:38,730
E io disegnare i valori qui dentro.

28
00:01:38,730 --> 00:01:41,090
Quindi, il valore andrà in qui,

29
00:01:41,090 --> 00:01:44,770
e poi qui avremo il puntatore sinistra sulla sinistra e destra il puntatore sulla destra.

30
00:01:44,770 --> 00:01:50,430
Ed è molto tanto convenzione di chiamare verso sinistra e destra, il nome del puntatore.

31
00:01:50,430 --> 00:01:52,460
Entrambi stanno per essere nullo.

32
00:01:52,460 --> 00:01:57,870
Questo sarà solo nullo, e che sarà solo essere nullo.

33
00:01:57,870 --> 00:02:03,630
Va bene. Ma torniamo al qui.

34
00:02:03,630 --> 00:02:05,700
"Con una lista concatenata, abbiamo solo dovuto memorizzare un puntatore

35
00:02:05,700 --> 00:02:09,639
al primo nodo della lista, al fine di ricordare l'intera lista collegata, oppure l'intero elenco.

36
00:02:09,639 --> 00:02:11,650
Allo stesso modo, con gli alberi, non ci resta che memorizzare un puntatore

37
00:02:11,650 --> 00:02:13,420
ad un singolo nodo per ricordare tutto l'albero.

38
00:02:13,420 --> 00:02:15,980
Questo nodo è la calle 'radice' dell'albero.

39
00:02:15,980 --> 00:02:18,320
Sviluppare il vostro diagramma da prima o disegnare una nuova

40
00:02:18,320 --> 00:02:21,690
in modo tale che si dispone di un box-e-frecce raffigurazione di un albero binario

41
00:02:21,690 --> 00:02:25,730
con il valore 7, poi 3 a sinistra,

42
00:02:25,730 --> 00:02:32,760
9 poi a destra, e poi 6 sulla destra del 3. "

43
00:02:32,760 --> 00:02:34,810
Vediamo se riesco a ricordare tutto questo nella mia testa.

44
00:02:34,810 --> 00:02:37,670
Quindi questo sarà il nostro principale qui.

45
00:02:37,670 --> 00:02:41,600
Avremo un po 'di puntatore da qualche parte, qualcosa che chiameremo radice,

46
00:02:41,600 --> 00:02:45,140
ed è rivolta a questo ragazzo.

47
00:02:45,140 --> 00:02:48,490
Ora fare un nuovo nodo,

48
00:02:48,490 --> 00:02:52,870
che cosa abbiamo, 3 a sinistra?

49
00:02:52,870 --> 00:02:57,140
Così un nuovo nodo con 3, che punta inizialmente nullo.

50
00:02:57,140 --> 00:02:59,190
Metto N.

51
00:02:59,190 --> 00:03:02,250
Ora vogliamo fare che andare a sinistra di 7.

52
00:03:02,250 --> 00:03:06,840
Quindi cambiamo questo puntatore per puntare ora a questo ragazzo.

53
00:03:06,840 --> 00:03:12,420
E noi facciamo lo stesso. Vogliamo un 9 qui

54
00:03:12,420 --> 00:03:14,620
che inizialmente solo dice nulla.

55
00:03:14,620 --> 00:03:19,600
Stiamo andando a cambiare questo, punto puntatore a 9,

56
00:03:19,600 --> 00:03:23,310
e ora vogliamo mettere 6 a destra di 3.

57
00:03:23,310 --> 00:03:32,170
Così sta andando a - fare un 6.

58
00:03:32,170 --> 00:03:34,310
E quel ragazzo punterà lì.

59
00:03:34,310 --> 00:03:38,320
Va bene. Ecco, questo è tutto quello che ci chiede di fare.

60
00:03:38,320 --> 00:03:42,770
>> Ora andiamo su alcuni termini.

61
00:03:42,770 --> 00:03:46,690
Abbiamo già parlato di come la radice dell'albero è il più in alto nodo nell'albero.

62
00:03:46,690 --> 00:03:54,720
Quella contenente 7. I nodi nella parte inferiore dell'albero sono chiamati le foglie.

63
00:03:54,720 --> 00:04:01,240
Ogni nodo che ha appena null come suoi figli è una foglia.

64
00:04:01,240 --> 00:04:03,680
Così è possibile, se il nostro albero binario è solo un singolo nodo,

65
00:04:03,680 --> 00:04:10,130
che un albero è una foglia, e questo è tutto.

66
00:04:10,130 --> 00:04:12,060
"Il 'height' dell'albero è il numero di salti si deve fare

67
00:04:12,060 --> 00:04:16,620
per ottenere, da cima a una foglia. "

68
00:04:16,620 --> 00:04:18,640
Andremo in, in un secondo, la differenza

69
00:04:18,640 --> 00:04:21,940
tra gli alberi binari bilanciati e sbilanciati,

70
00:04:21,940 --> 00:04:29,470
ma per ora, l'altezza di questo albero

71
00:04:29,470 --> 00:04:34,520
Direi che è 3, anche se si conta il numero di hop

72
00:04:34,520 --> 00:04:39,710
si deve fare per arrivare a 9, allora è davvero solo una altezza di 2.

73
00:04:39,710 --> 00:04:43,340
In questo momento si tratta di un albero binario bilanciato,

74
00:04:43,340 --> 00:04:49,840
ma ci parlato equilibrata quando si arriva a essere rilevante.

75
00:04:49,840 --> 00:04:52,040
Così ora possiamo parlare di nodi in un albero, in termini

76
00:04:52,040 --> 00:04:54,700
rispetto agli altri nodi dell'albero.

77
00:04:54,700 --> 00:04:59,730
Così ora abbiamo genitori, figli, fratelli e sorelle, antenati e discendenti.

78
00:04:59,730 --> 00:05:05,650
Si tratta di senso piuttosto comune, che cosa significano.

79
00:05:05,650 --> 00:05:09,610
Se ci chiediamo - è genitori.

80
00:05:09,610 --> 00:05:12,830
Allora, qual è il genitore di 3?

81
00:05:12,830 --> 00:05:16,090
[Gli studenti] 7. Sì >>. Il genitore è solo andare a essere ciò che fa per voi.

82
00:05:16,090 --> 00:05:20,510
Allora che cosa sono i figli di 7?

83
00:05:20,510 --> 00:05:23,860
[Gli studenti] 3 e 9. Sì >>.

84
00:05:23,860 --> 00:05:26,460
Si noti che "bambini" significa letteralmente figli,

85
00:05:26,460 --> 00:05:31,010
quindi 6 non si applica, perché è come un nipote.

86
00:05:31,010 --> 00:05:35,540
Ma poi se andiamo discendenti, quindi quali sono i discendenti di 7?

87
00:05:35,540 --> 00:05:37,500
[Gli studenti] 3, 6 e 9. Sì >>.

88
00:05:37,500 --> 00:05:42,330
I discendenti del nodo principale sta per essere tutto ciò che nella struttura,

89
00:05:42,330 --> 00:05:47,950
tranne forse il nodo radice in sé, se non si vuole considerare che un discendente.

90
00:05:47,950 --> 00:05:50,750
E, infine, antenati, quindi è la direzione opposta.

91
00:05:50,750 --> 00:05:55,740
Ma quali sono gli antenati di 6?

92
00:05:55,740 --> 00:05:58,920
[Gli studenti] 3 e 7. Sì >>. 9 non è incluso.

93
00:05:58,920 --> 00:06:02,520
E 'solo la parte posteriore discendenza diretta alla radice

94
00:06:02,520 --> 00:06:13,230
sta per essere i vostri antenati.

95
00:06:13,230 --> 00:06:16,300
>> "Noi diciamo che un albero binario è 'ordinato' se per ogni nodo dell'albero,

96
00:06:16,300 --> 00:06:19,530
tutti i suoi discendenti sulla sinistra hanno valori minori

97
00:06:19,530 --> 00:06:22,890
e tutti quelli di destra hanno maggiori valori.

98
00:06:22,890 --> 00:06:27,060
Ad esempio, l'albero sopra è ordinato ma non è possibile solo la disposizione ordinata. "

99
00:06:27,060 --> 00:06:30,180
Prima di arrivare a questo,

100
00:06:30,180 --> 00:06:36,420
un albero binario ordinato è anche conosciuto come un albero di ricerca binaria.

101
00:06:36,420 --> 00:06:38,660
Qui ci capita di essere la chiamata di un albero binario ordinato,

102
00:06:38,660 --> 00:06:41,850
ma non ho mai sentito chiamato un albero binario ordinato prima,

103
00:06:41,850 --> 00:06:46,650
e su un quiz siamo molto più propensi a mettere albero binario di ricerca.

104
00:06:46,650 --> 00:06:49,250
Sono la stessa cosa,

105
00:06:49,250 --> 00:06:54,580
ed è importante riconoscere che la distinzione tra albero binario e ricerca su alberi binari.

106
00:06:54,580 --> 00:06:58,830
Un albero binario è solo un albero che fa riferimento a due cose.

107
00:06:58,830 --> 00:07:02,120
Ogni nodo indica due cose.

108
00:07:02,120 --> 00:07:06,310
Non vi è alcuna motivazione circa i valori a cui punta.

109
00:07:06,310 --> 00:07:11,370
Così come qui, dal momento che si tratta di un albero binario di ricerca,

110
00:07:11,370 --> 00:07:14,030
sappiamo che se andiamo a sinistra di 7,

111
00:07:14,030 --> 00:07:16,670
allora tutti i valori che si può eventualmente raggiungere

112
00:07:16,670 --> 00:07:19,310
andando a sinistra del 7 deve essere inferiore a 7.

113
00:07:19,310 --> 00:07:24,070
Si noti che tutti i valori inferiori a 7 sono 3 e 6.

114
00:07:24,070 --> 00:07:26,040
Queste sono tutte a sinistra del 7.

115
00:07:26,040 --> 00:07:29,020
Se andiamo a destra di 7, tutto deve essere superiore a 7,

116
00:07:29,020 --> 00:07:33,220
9 è così a destra di 7, quindi siamo a posto.

117
00:07:33,220 --> 00:07:36,150
Questo non è il caso di un albero binario,

118
00:07:36,150 --> 00:07:40,020
per un albero binario regolare possiamo solo 3 nella parte superiore, a sinistra 7,

119
00:07:40,020 --> 00:07:47,630
9 a sinistra 7; c'è nessun ordinamento dei valori di sorta.

120
00:07:47,630 --> 00:07:56,140
Ora, noi non effettivamente fare questo perché è noioso e inutile,

121
00:07:56,140 --> 00:07:59,400
ma "cercare di disegnare alberi ordinati in molti come si può pensare di

122
00:07:59,400 --> 00:08:01,900
utilizzando i numeri 7, 3, 9, e 6.

123
00:08:01,900 --> 00:08:06,800
Quanti accordi distinti ci sono? Qual è l'altezza di ciascuno? "

124
00:08:06,800 --> 00:08:10,480
>> Faremo una coppia, ma l'idea principale è,

125
00:08:10,480 --> 00:08:16,530
questo è in alcun modo una rappresentazione unica di un albero binario contenente questi valori.

126
00:08:16,530 --> 00:08:22,760
Tutto quello che serve è un albero binario che contiene il 7, 3, 6, e 9.

127
00:08:22,760 --> 00:08:25,960
Un altro possibile valida sarebbe la radice è 3,

128
00:08:25,960 --> 00:08:30,260
andare a sinistra ed è 6, andare a sinistra ed è 7,

129
00:08:30,260 --> 00:08:32,730
andare a sinistra ed è 9.

130
00:08:32,730 --> 00:08:36,169
Questo è perfettamente valido albero binario di ricerca.

131
00:08:36,169 --> 00:08:39,570
Non è molto utile, perché è proprio come una lista concatenata

132
00:08:39,570 --> 00:08:43,750
e tutti questi puntatori sono solo nullo.

133
00:08:43,750 --> 00:08:48,900
Ma è un albero valido. Si '?

134
00:08:48,900 --> 00:08:51,310
[Studente] Non i valori devono essere maggiori a destra?

135
00:08:51,310 --> 00:08:56,700
O si tratta di -? Questi >> volevo andare nella direzione opposta.

136
00:08:56,700 --> 00:09:00,960
C'è anche - sì, facciamo passare questo.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Bella presa.

138
00:09:07,770 --> 00:09:11,730
Ha ancora obbedire a ciò che un albero binario di ricerca si dovrebbe fare.

139
00:09:11,730 --> 00:09:15,650
Quindi tutto a sinistra deve essere minore rispetto a qualsiasi dato nodo.

140
00:09:15,650 --> 00:09:23,180
Potremmo andare, per esempio, questo 6 e metterlo qui.

141
00:09:23,180 --> 00:09:26,880
No, non possiamo. Perché continuo a farlo?

142
00:09:26,880 --> 00:09:35,350
Facciamo - è qui 6, è qui 7, 6 punti a 3.

143
00:09:35,350 --> 00:09:39,290
Questo è ancora un valido albero binario di ricerca.

144
00:09:39,290 --> 00:09:49,260
Cosa c'è di sbagliato se io - vediamo se riesco a trovare una sistemazione.

145
00:09:49,260 --> 00:09:52,280
Si ', va bene. Allora, cosa c'è di sbagliato in questo albero?

146
00:09:52,280 --> 00:10:08,920
Credo di aver già dato un suggerimento che ci sia qualcosa che non va.

147
00:10:08,920 --> 00:10:14,430
Perché continuo a farlo?

148
00:10:14,430 --> 00:10:18,510
Va bene. Questo sembra ragionevole.

149
00:10:18,510 --> 00:10:22,590
Se guardiamo ad ogni nodo, come il 7, poi a sinistra di 7 è una 3.

150
00:10:22,590 --> 00:10:24,960
Così abbiamo 3, la cosa a destra di 3 è un 6.

151
00:10:24,960 --> 00:10:27,750
E se si guarda alle 6, la cosa a destra di 6 è un 9.

152
00:10:27,750 --> 00:10:30,910
Allora, perché non è questo un valido albero binario di ricerca?

153
00:10:30,910 --> 00:10:36,330
[Studenti] 9 è ancora a sinistra 7. Sì >>.

154
00:10:36,330 --> 00:10:43,710
Deve essere vero che tutti i valori si può eventualmente raggiungere andando a sinistra di 7 sono meno di 7.

155
00:10:43,710 --> 00:10:49,120
Se andiamo a sinistra di 7, si arriva a 3 e si può ancora arrivare a 6,

156
00:10:49,120 --> 00:10:52,520
possiamo ancora arrivare a 9, ma essendo andato inferiore a 7,

157
00:10:52,520 --> 00:10:55,070
non dovremmo essere in grado di arrivare a un numero che è maggiore di 7.

158
00:10:55,070 --> 00:10:59,830
Quindi questo non è un valido albero binario di ricerca.

159
00:10:59,830 --> 00:11:02,330
>> Mio fratello in realtà ha avuto un colloquio di domanda

160
00:11:02,330 --> 00:11:07,760
che era fondamentalmente questo, basta codice qualcosa per convalidare

161
00:11:07,760 --> 00:11:10,500
se un albero è un albero binario di ricerca,

162
00:11:10,500 --> 00:11:13,580
e così la prima cosa che fece fu solo verificare

163
00:11:13,580 --> 00:11:17,020
se la sinistra e la destra sono corretti, quindi scorrere verso il basso lì.

164
00:11:17,020 --> 00:11:19,700
Ma non si può semplicemente fare questo, devi tenere traccia

165
00:11:19,700 --> 00:11:22,550
del fatto che, ora che sono andato a sinistra di 7,

166
00:11:22,550 --> 00:11:26,340
tutto in questa sottostruttura deve essere inferiore a 7.

167
00:11:26,340 --> 00:11:28,430
L'algoritmo corretto deve tenere traccia

168
00:11:28,430 --> 00:11:35,970
dei limiti che i valori possono eventualmente cadranno dentro

169
00:11:35,970 --> 00:11:38,360
Noi non passerà attraverso tutti loro.

170
00:11:38,360 --> 00:11:41,630
C'è una relazione di ricorrenza piacevole,

171
00:11:41,630 --> 00:11:44,810
anche se non siamo ancora arrivati ​​a quelli, altrimenti non si arriva a quelli,

172
00:11:44,810 --> 00:11:47,030
la definizione di quanti ce ne sono in realtà.

173
00:11:47,030 --> 00:11:53,180
Quindi ci sono 14 di loro.

174
00:11:53,180 --> 00:11:56,020
L'idea di come si dovrebbe fare è matematicamente come,

175
00:11:56,020 --> 00:11:59,770
si può scegliere uno solo di essere il nodo radice,

176
00:11:59,770 --> 00:12:03,160
e poi se prendo 7 per essere il nodo radice,

177
00:12:03,160 --> 00:12:08,150
poi ci sono, ad esempio, alcuni numeri che possono andare il mio nodo di sinistra,

178
00:12:08,150 --> 00:12:10,440
e ci sono alcuni numeri che possono essere il mio nodo a destra,

179
00:12:10,440 --> 00:12:15,090
ma se ho n il numero totale, quindi l'importo che può andare a sinistra

180
00:12:15,090 --> 00:12:18,820
più l'importo che può andare a destra è n - 1.

181
00:12:18,820 --> 00:12:26,130
Quindi i numeri rimanenti, devono essere in grado di andare sia a sinistra oa destra.

182
00:12:26,130 --> 00:12:31,580
Sembra difficile che, se ho messo 3, primo poi tutto deve andare a sinistra,

183
00:12:31,580 --> 00:12:35,080
ma se ho messo 7, quindi alcune cose possono andare a sinistra e alcune cose possono andare a destra.

184
00:12:35,080 --> 00:12:39,570
E da '3 'prima volevo dire tutto può andare a destra.

185
00:12:39,570 --> 00:12:42,350
E 'davvero, basta pensare a come,

186
00:12:42,350 --> 00:12:47,980
quante cose possono andare al livello successivo della struttura.

187
00:12:47,980 --> 00:12:50,420
E risulta essere 14; oppure è possibile disegnare tutti,

188
00:12:50,420 --> 00:12:54,650
e poi avrai 14.

189
00:12:54,650 --> 00:13:01,120
>> Tornando qui,

190
00:13:01,120 --> 00:13:03,510
"Alberi ordinati binari sono fresche, perché si può cercare attraverso di loro

191
00:13:03,510 --> 00:13:06,910
in un modo molto simile alla ricerca in un array ordinato.

192
00:13:06,910 --> 00:13:10,120
Per fare ciò, si inizia dalla radice e lavorare il nostro modo l'albero

193
00:13:10,120 --> 00:13:13,440
verso le foglie, il controllo dei valori di ogni nodo con i valori che stiamo cercando.

194
00:13:13,440 --> 00:13:15,810
Se il valore del nodo corrente è inferiore al valore che stiamo cercando,

195
00:13:15,810 --> 00:13:18,050
si va vicino al figlio destro del nodo.

196
00:13:18,050 --> 00:13:20,030
In caso contrario, si va al figlio sinistro del nodo.

197
00:13:20,030 --> 00:13:22,800
Ad un certo punto, potrete sia trovare il valore che stai cercando, o si incorrerà in un null,

198
00:13:22,800 --> 00:13:28,520
indicante il valore non è nella struttura. "

199
00:13:28,520 --> 00:13:32,450
Devo ridisegnare l'albero che avevamo prima, che prendo un secondo.

200
00:13:32,450 --> 00:13:38,280
Ma noi vogliamo cercare se 6, 10, e 1 sono nella struttura.

201
00:13:38,280 --> 00:13:49,180
Così che cosa è stato, 7, 9, 3, 6. Va bene.

202
00:13:49,180 --> 00:13:52,730
I numeri che si desidera cercare, vogliamo guardare in alto 6.

203
00:13:52,730 --> 00:13:55,440
Come funziona questo algoritmo?

204
00:13:55,440 --> 00:14:03,040
Beh, abbiamo anche un po 'di puntatore root per il nostro albero.

205
00:14:03,040 --> 00:14:12,460
E saremmo andati alla radice e dire, è questo valore uguale al valore che stiamo cercando?

206
00:14:12,460 --> 00:14:15,000
Quindi stiamo cercando di 6, quindi non è uguale.

207
00:14:15,000 --> 00:14:20,140
Quindi andare avanti, e ora diciamo, va bene, quindi 6 è inferiore a 7.

208
00:14:20,140 --> 00:14:23,940
Vuol dire che vogliamo andare a sinistra, o vogliamo andare a destra?

209
00:14:23,940 --> 00:14:27,340
[Studente] Sinistra. Sì >>.

210
00:14:27,340 --> 00:14:33,340
E 'molto più semplice, tutto ciò che dovete fare è disegnare un nodo possibile della struttura

211
00:14:33,340 --> 00:14:37,760
e poi Non. - invece di cercare di pensare nella tua testa,

212
00:14:37,760 --> 00:14:40,020
Va bene, se è di meno, devo andare a sinistra o andare diritto,

213
00:14:40,020 --> 00:14:43,030
solo guardando questa foto, è molto chiaro che devo andare a sinistra

214
00:14:43,030 --> 00:14:47,700
se questo nodo è maggiore del valore che sto cercando.

215
00:14:47,700 --> 00:14:52,600
Quindi si va a sinistra, ora sono a 3.

216
00:14:52,600 --> 00:14:57,770
Voglio - 3 è inferiore al valore che sto cercando, che è 6.

217
00:14:57,770 --> 00:15:03,420
Così si va a destra, e ora finisco alle 6,

218
00:15:03,420 --> 00:15:07,380
che è il valore che sto cercando, così mi restituisce true.

219
00:15:07,380 --> 00:15:15,760
Il valore successivo vado a cercare è 10.

220
00:15:15,760 --> 00:15:23,230
Va bene. Quindi 10, ora, sta per - tagliare che - andando a seguire la radice.

221
00:15:23,230 --> 00:15:27,670
Ora, 10 sta per essere superiore a 7, quindi voglio guardare a destra.

222
00:15:27,670 --> 00:15:31,660
Ho intenzione di venire qui, 10 sta per essere superiore a 9,

223
00:15:31,660 --> 00:15:34,520
così ho intenzione di voler guardare a destra.

224
00:15:34,520 --> 00:15:42,100
Io vengo qui, ma qui ora sono a null.

225
00:15:42,100 --> 00:15:44,170
Che cosa devo fare se ho colpito nulla?

226
00:15:44,170 --> 00:15:47,440
[Studente] Ritorna falso? Sì >>. Non ho trovato 10.

227
00:15:47,440 --> 00:15:49,800
1 sta per essere un caso quasi identico,

228
00:15:49,800 --> 00:15:51,950
tranne che sta solo andando a essere capovolte, invece di guardare

229
00:15:51,950 --> 00:15:56,540
lungo il lato destro, ho intenzione di guardare in basso sul lato sinistro.

230
00:15:56,540 --> 00:16:00,430
>> Ora penso che effettivamente arrivare a codice.

231
00:16:00,430 --> 00:16:04,070
Ecco dove - aprire l'apparecchio CS50 e navigare il vostro senso lì,

232
00:16:04,070 --> 00:16:07,010
ma si può farlo anche nello spazio.

233
00:16:07,010 --> 00:16:09,170
E 'probabilmente l'ideale per farlo nello spazio,

234
00:16:09,170 --> 00:16:13,760
perché possiamo lavorare nello spazio.

235
00:16:13,760 --> 00:16:19,170
"In primo luogo abbiamo bisogno di una nuova definizione di tipo per un nodo di albero binario che contiene valori int.

236
00:16:19,170 --> 00:16:21,400
Utilizzando il boilerplate typedef di seguito,

237
00:16:21,400 --> 00:16:24,510
creare una nuova definizione di tipo di un nodo in un albero binario.

238
00:16:24,510 --> 00:16:27,930
Se ti trovi in ​​difficoltà. . . "Bla, bla, bla. Okay.

239
00:16:27,930 --> 00:16:30,380
Quindi cerchiamo di mettere il boilerplate qui,

240
00:16:30,380 --> 00:16:41,630
struct nodo typedef, e il nodo. Si ', va bene.

241
00:16:41,630 --> 00:16:44,270
Ma quali sono i campi che stiamo andando a voler nel nostro nodo?

242
00:16:44,270 --> 00:16:46,520
[Studente] Int e poi due puntatori?

243
00:16:46,520 --> 00:16:49,700
Int >> valore, due puntatori? Come faccio a scrivere i puntatori?

244
00:16:49,700 --> 00:16:58,440
[Studente] Struct. >> Dovrei Immagine Sì, così struct nodo * a sinistra,

245
00:16:58,440 --> 00:17:01,320
e struct nodo * a destra.

246
00:17:01,320 --> 00:17:03,460
E ricordate la discussione dell'ultima volta,

247
00:17:03,460 --> 00:17:15,290
che questo non ha senso, questo non ha senso,

248
00:17:15,290 --> 00:17:18,270
questo non ha senso.

249
00:17:18,270 --> 00:17:25,000
Hai bisogno di tutto quello che c'è per definire questa struttura ricorsiva.

250
00:17:25,000 --> 00:17:27,970
Ok, allora questo è ciò che il nostro albero è andare a guardare come.

251
00:17:27,970 --> 00:17:37,670
Se abbiamo fatto un albero ternario, poi un nodo potrebbe essere simile b1, b2, b3 struct nodo *,

252
00:17:37,670 --> 00:17:43,470
dove b è un ramo - in realtà, l'ho più sentito a sinistra, al centro, a destra, ma qualunque.

253
00:17:43,470 --> 00:17:55,610
Ci interessa solo binario, per cui a destra, a sinistra.

254
00:17:55,610 --> 00:17:59,110
"Ora dichiarare una variabile globale * nodo per la radice dell'albero."

255
00:17:59,110 --> 00:18:01,510
Quindi non abbiamo intenzione di farlo.

256
00:18:01,510 --> 00:18:08,950
Per rendere le cose leggermente più difficile e più generalizzata,

257
00:18:08,950 --> 00:18:11,570
non avremo una variabile globale nodo.

258
00:18:11,570 --> 00:18:16,710
Invece, in main dichiareremo tutte le nostre cose nodi,

259
00:18:16,710 --> 00:18:20,500
e questo significa che al di sotto, quando iniziare a correre

260
00:18:20,500 --> 00:18:23,130
Contiene la nostra funzione e la nostra funzione di inserimento,

261
00:18:23,130 --> 00:18:27,410
al posto dei nostri contiene una funzione semplicemente utilizzando questa variabile globale nodo,

262
00:18:27,410 --> 00:18:34,280
stiamo andando ad avere la prenda come argomento l'albero che vogliamo elaborare.

263
00:18:34,280 --> 00:18:36,650
Avere la variabile globale avrebbe dovuto rendere le cose più facili.

264
00:18:36,650 --> 00:18:42,310
Stiamo andando a fare le cose più difficili.

265
00:18:42,310 --> 00:18:51,210
Ora prendete un minuto o giù di lì di fare proprio questo genere di cose,

266
00:18:51,210 --> 00:18:57,690
dove all'interno del principale che si desidera creare questo albero, e questo è tutto quello che vuoi fare.

267
00:18:57,690 --> 00:19:04,530
Prova a costruire questo albero nella funzione principale.

268
00:19:42,760 --> 00:19:47,610
>> Va bene. Quindi non hanno nemmeno bisogno di aver costruito l'albero per tutta la strada ancora.

269
00:19:47,610 --> 00:19:49,840
Ma qualcuno ha qualcosa che avrei potuto tirare su

270
00:19:49,840 --> 00:20:03,130
per mostrare come si può iniziare a costruire un albero?

271
00:20:03,130 --> 00:20:08,080
[Studente] Qualcuno di colpi, cercando di uscire.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Chiunque agio con la loro costruzione albero?

273
00:20:13,100 --> 00:20:15,520
[Studente] Certo. Non è fatto. Va bene >>. Possiamo solo concludere -

274
00:20:15,520 --> 00:20:26,860
oh, si può salvare? Evviva.

275
00:20:26,860 --> 00:20:32,020
Quindi qui abbiamo - oh, sono leggermente tagliate.

276
00:20:32,020 --> 00:20:34,770
Sto ingrandita?

277
00:20:34,770 --> 00:20:37,730
Per ingrandire, scorrere fuori. >> Ho una domanda. Sì >>?

278
00:20:37,730 --> 00:20:44,410
[Studente] Quando si definisce una struttura, sono cose come inizializzato a qualcosa?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No. >> Ok. Quindi si dovrebbe inizializzare -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No. Quando si definisce, o quando si dichiara una struttura,

281
00:20:50,450 --> 00:20:55,600
non è inizializzato per impostazione predefinita, ma è proprio come se si dichiara un int.

282
00:20:55,600 --> 00:20:59,020
E 'esattamente la stessa cosa. E 'come se ciascuno dei suoi singoli campi

283
00:20:59,020 --> 00:21:04,460
possono avere un valore spazzatura in esso. >> Ed è possibile definire - o di dichiarare una struttura

284
00:21:04,460 --> 00:21:07,740
in un modo che fa inizializzarli?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Sì. Quindi, collegamento sintassi di inizializzazione

286
00:21:13,200 --> 00:21:18,660
è andare a guardare come -

287
00:21:18,660 --> 00:21:22,200
Ci sono due modi in cui possiamo farlo. Penso che dovremmo compilarlo

288
00:21:22,200 --> 00:21:25,840
fare Clang che fa anche questo.

289
00:21:25,840 --> 00:21:28,510
L'ordine degli argomenti che viene nella struttura,

290
00:21:28,510 --> 00:21:32,170
si mette come l'ordine degli argomenti all'interno di queste parentesi graffe.

291
00:21:32,170 --> 00:21:35,690
Quindi, se si desidera inizializzare a 9 e ha lasciato nulla e poi a destra essere nullo,

292
00:21:35,690 --> 00:21:41,570
sarebbe 9, null, null.

293
00:21:41,570 --> 00:21:47,890
L'alternativa è, e l'editor non piace questa sintassi,

294
00:21:47,890 --> 00:21:50,300
e pensa che io voglio un nuovo blocco,

295
00:21:50,300 --> 00:22:01,800
ma l'alternativa è qualcosa di simile -

296
00:22:01,800 --> 00:22:04,190
qui, la metto su una nuova riga.

297
00:22:04,190 --> 00:22:09,140
Si può dire in modo esplicito, non ricordo la sintassi esatta.

298
00:22:09,140 --> 00:22:13,110
Così si può esplicitamente indirizzare il messaggio per nome, e dire:

299
00:22:13,110 --> 00:22:21,570
. C o. Valore = 9. NULL = sinistra.

300
00:22:21,570 --> 00:22:24,540
Sto indovinando questi devono essere virgole.

301
00:22:24,540 --> 00:22:29,110
. Destra = NULL, così in questo modo non si

302
00:22:29,110 --> 00:22:33,780
effettivamente bisogno di conoscere l'ordine della struttura,

303
00:22:33,780 --> 00:22:36,650
e quando stai leggendo questo, è molto più esplicito

304
00:22:36,650 --> 00:22:41,920
su ciò che il valore è in fase di inizializzazione di.

305
00:22:41,920 --> 00:22:44,080
>> Questa sembra essere una delle cose che -

306
00:22:44,080 --> 00:22:49,100
così, per la maggior parte, C + + è un superset di C.

307
00:22:49,100 --> 00:22:54,160
Si può prendere il codice C, spostarlo sulla C + +, e dovrebbe compilare.

308
00:22:54,160 --> 00:22:59,570
Questa è una delle cose che il C + + non supporta, per cui le persone tendono a non farlo.

309
00:22:59,570 --> 00:23:01,850
Non so se questo è l'unico motivo per le persone tendono a non farlo,

310
00:23:01,850 --> 00:23:10,540
ma il caso in cui avevo bisogno di usare di cui aveva bisogno per lavorare con C + + e così non ho potuto usare questo.

311
00:23:10,540 --> 00:23:14,000
Un altro esempio di qualcosa che non funziona con C + + è

312
00:23:14,000 --> 00:23:16,940
come malloc restituisce un "void *," tecnicamente,

313
00:23:16,940 --> 00:23:20,200
ma si può solo dire char * x = qualsiasi malloc,

314
00:23:20,200 --> 00:23:22,840
e che verrà automaticamente il cast a un char *.

315
00:23:22,840 --> 00:23:25,450
Tale fusione automatica non avviene in C + +.

316
00:23:25,450 --> 00:23:28,150
Non sarebbe la compilazione, e si avrebbe bisogno di dire in modo esplicito

317
00:23:28,150 --> 00:23:34,510
char *, malloc, qualsiasi cosa, per il cast di un char *.

318
00:23:34,510 --> 00:23:37,270
Non ci sono molte cose che C e C + + non sono d'accordo su,

319
00:23:37,270 --> 00:23:40,620
ma questi sono due.

320
00:23:40,620 --> 00:23:43,120
Quindi dovremo andare con questa sintassi.

321
00:23:43,120 --> 00:23:46,150
Ma anche se non siamo andati con quella sintassi,

322
00:23:46,150 --> 00:23:49,470
ciò che è - potrebbe essere di sbagliato in questo?

323
00:23:49,470 --> 00:23:52,170
[Studente] Non ho bisogno di dereferenziarlo? Sì >>.

324
00:23:52,170 --> 00:23:55,110
Ricordate che la freccia ha un dereference implicito,

325
00:23:55,110 --> 00:23:58,230
e così quando siamo solo di fronte ad un struct,

326
00:23:58,230 --> 00:24:04,300
vogliamo usare. per arrivare a un campo all'interno della struttura.

327
00:24:04,300 --> 00:24:07,200
E l'unica volta che usiamo freccia è quando vogliamo fare -

328
00:24:07,200 --> 00:24:13,450
bene, freccia è equivalente a -

329
00:24:13,450 --> 00:24:17,020
questo è quello che avrebbe voluto dire se ho usato freccia.

330
00:24:17,020 --> 00:24:24,600
Tutti i mezzi freccia, dereferenziare questo, ora sono in una struttura, e posso ottenere il campo.

331
00:24:24,600 --> 00:24:28,040
O ottenere il campo direttamente o dereference e ottenere il campo -

332
00:24:28,040 --> 00:24:30,380
Credo che questo dovrebbe essere il valore.

333
00:24:30,380 --> 00:24:33,910
Ma qui ho a che fare solo con una struttura, non un puntatore ad una struct,

334
00:24:33,910 --> 00:24:38,780
e quindi non posso utilizzare la freccia.

335
00:24:38,780 --> 00:24:47,510
Ma questo genere di cose che possiamo fare per tutti i nodi.

336
00:24:47,510 --> 00:24:55,790
Oh mio Dio.

337
00:24:55,790 --> 00:25:09,540
Questo è 6, 7, e 3.

338
00:25:09,540 --> 00:25:16,470
Quindi siamo in grado di impostare i rami del nostro albero, possiamo avere 7 -

339
00:25:16,470 --> 00:25:21,650
si può avere, la sua sinistra deve puntare a 3.

340
00:25:21,650 --> 00:25:25,130
Quindi, come possiamo fare?

341
00:25:25,130 --> 00:25:29,320
[Gli studenti, incomprensibile] >> Si '. L'indirizzo di node3,

342
00:25:29,320 --> 00:25:34,170
e se non ha avuto l'indirizzo, allora semplicemente non sarebbe la compilazione.

343
00:25:34,170 --> 00:25:38,190
Ma ricordate che questi sono i puntatori ai nodi successivi.

344
00:25:38,190 --> 00:25:44,930
Il diritto deve puntare a 9,

345
00:25:44,930 --> 00:25:53,330
e 3 deve puntare sul diritto 6.

346
00:25:53,330 --> 00:25:58,480
Credo che questo sia tutto pronto. Eventuali commenti o domande?

347
00:25:58,480 --> 00:26:02,060
[Studente, incomprensibile] La radice sta per essere 7.

348
00:26:02,060 --> 00:26:08,210
Possiamo solo dire nodo * ptr =

349
00:26:08,210 --> 00:26:14,160
o radice, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Per i nostri scopi, stiamo andando a che fare con inserto,

351
00:26:20,730 --> 00:26:25,490
quindi stiamo andando a voler scrivere una funzione per inserire in questo albero binario

352
00:26:25,490 --> 00:26:34,230
e inserto è inevitabile che chiama malloc per creare un nuovo nodo di questo albero.

353
00:26:34,230 --> 00:26:36,590
Quindi, le cose stanno andando per ottenere disordinato con il fatto che alcuni nodi

354
00:26:36,590 --> 00:26:38,590
sono attualmente in pila

355
00:26:38,590 --> 00:26:43,680
e altri nodi stanno andando a finire nel mucchio quando li inserisce.

356
00:26:43,680 --> 00:26:47,640
Ciò è perfettamente valido, ma l'unica ragione

357
00:26:47,640 --> 00:26:49,600
siamo in grado di fare questo in pila

358
00:26:49,600 --> 00:26:51,840
è perché è un esempio forzato che sappiamo

359
00:26:51,840 --> 00:26:56,360
l'albero dovrebbe essere costruito come 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Se non avessimo questo, allora non avrebbe dovuto malloc in primo luogo.

361
00:27:02,970 --> 00:27:06,160
Come vedremo un po 'più tardi, dovremmo essere malloc'ing.

362
00:27:06,160 --> 00:27:08,570
In questo momento è perfettamente ragionevole per mettere in pila,

363
00:27:08,570 --> 00:27:14,750
ma cambiamo ad un implementazione malloc.

364
00:27:14,750 --> 00:27:17,160
Quindi, ciascuna di esse è ora di andare a essere qualcosa di simile

365
00:27:17,160 --> 00:27:24,240
nodo * node9 = malloc (sizeof (nodo)).

366
00:27:24,240 --> 00:27:28,040
E ora andiamo a fare il nostro check.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Non volevo che -

368
00:27:34,010 --> 00:27:40,950
ritorno 1, quindi possiamo fare node9-> perché ora è un puntatore,

369
00:27:40,950 --> 00:27:45,300
valore = 6, node9-> sinistra = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> destra = NULL,

371
00:27:48,930 --> 00:27:51,410
e stiamo andando a fare che per ciascuno di questi nodi.

372
00:27:51,410 --> 00:27:57,490
Così, invece, cerchiamo di metterlo all'interno di una funzione separata.

373
00:27:57,490 --> 00:28:00,620
Chiamiamolo nodo * build_node,

374
00:28:00,620 --> 00:28:09,050
e questo è in qualche modo simile alle API che prevede la codifica di Huffman.

375
00:28:09,050 --> 00:28:12,730
Noi vi diamo le funzioni di inizializzazione per un albero

376
00:28:12,730 --> 00:28:20,520
e decostruttore "funzioni" per quegli alberi e lo stesso per le foreste.

377
00:28:20,520 --> 00:28:22,570
>> Quindi qui si sta andando ad avere una funzione di inizializzazione

378
00:28:22,570 --> 00:28:25,170
di costruire solo un nodo per noi.

379
00:28:25,170 --> 00:28:29,320
E sta andando a guardare più o meno esattamente come questo.

380
00:28:29,320 --> 00:28:32,230
E sto andando anche a essere pigri e non cambiare il nome della variabile,

381
00:28:32,230 --> 00:28:34,380
anche se non ha senso node9 più.

382
00:28:34,380 --> 00:28:38,610
Oh, credo che il valore node9 dovrebbe non sono stati 6.

383
00:28:38,610 --> 00:28:42,800
Ora possiamo ritornare node9.

384
00:28:42,800 --> 00:28:49,550
E qui si deve restituire null.

385
00:28:49,550 --> 00:28:52,690
Tutti d'accordo su questo build-a-nodo della funzione?

386
00:28:52,690 --> 00:28:59,780
Così ora possiamo chiamare che per costruire qualsiasi nodo con un determinato valore e puntatori nulli.

387
00:28:59,780 --> 00:29:09,750
Ora possiamo chiamare, si può fare il nodo * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
E facciamolo. . .

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

390
00:29:33,980 --> 00:29:39,330
E ora vogliamo impostare i puntatori stessi,

391
00:29:39,330 --> 00:29:42,470
solo che adesso tutto è già in termini di puntatori

392
00:29:42,470 --> 00:29:48,480
quindi non è più necessario l'indirizzo di.

393
00:29:48,480 --> 00:29:56,300
Va bene. Allora, qual è l'ultima cosa che voglio fare?

394
00:29:56,300 --> 00:30:03,850
C'è un controllo degli errori che non sto facendo.

395
00:30:03,850 --> 00:30:06,800
Che cosa significa costruire ritorno nodo?

396
00:30:06,800 --> 00:30:11,660
[Studente, incomprensibile] >> Si '. Se non malloc, che restituisca null.

397
00:30:11,660 --> 00:30:16,460
Quindi ho intenzione di pigramente messo giù qui, invece di fare una condizione per ogni.

398
00:30:16,460 --> 00:30:22,320
Se (node9 == NULL, o - ancora più semplice,

399
00:30:22,320 --> 00:30:28,020
questo è pari a poco se non node9.

400
00:30:28,020 --> 00:30:38,310
Quindi, se non node9, o non Node6, o non node3, o non node7, ritorno 1.

401
00:30:38,310 --> 00:30:42,850
Forse dovremmo stampare malloc non riuscito, o qualcosa del genere.

402
00:30:42,850 --> 00:30:46,680
[Studente] E 'falso uguale a null, come bene?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Qualsiasi valore zero è falso.

404
00:30:51,290 --> 00:30:53,920
Quindi nulla è un valore zero.

405
00:30:53,920 --> 00:30:56,780
Zero è un valore zero. Falso è un valore zero.

406
00:30:56,780 --> 00:31:02,130
Qualsiasi - praticamente gli unici due valori zero sono nulli e zero,

407
00:31:02,130 --> 00:31:07,900
falso è solo hash definito come zero.

408
00:31:07,900 --> 00:31:13,030
Ciò vale anche se si dichiara variabile globale.

409
00:31:13,030 --> 00:31:17,890
Se abbiamo avuto * nodo principale qui,

410
00:31:17,890 --> 00:31:24,150
poi - la cosa bella di variabili globali è che hanno sempre un valore iniziale.

411
00:31:24,150 --> 00:31:27,500
Non è vero di funzioni, come all'interno di qui,

412
00:31:27,500 --> 00:31:34,870
se abbiamo, come, * nodo o nodo x.

413
00:31:34,870 --> 00:31:37,380
Non abbiamo idea di cosa x.Value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
o potremmo stampare e potrebbero essere arbitraria.

415
00:31:40,700 --> 00:31:44,980
Non è vero di variabili globali.

416
00:31:44,980 --> 00:31:47,450
Così radice nodo o nodo x.

417
00:31:47,450 --> 00:31:53,410
Per impostazione predefinita, tutto ciò che è globale, se non esplicitamente inizializzato a un valore,

418
00:31:53,410 --> 00:31:57,390
ha un valore zero come valore.

419
00:31:57,390 --> 00:32:01,150
Così qui, radice * nodo, non esplicitamente inizializzato a nulla,

420
00:32:01,150 --> 00:32:06,350
quindi il suo valore di default è null, che è il valore zero di puntatori.

421
00:32:06,350 --> 00:32:11,870
Il valore predefinito di x sta a significare che x.Value è pari a zero,

422
00:32:11,870 --> 00:32:14,260
x.left è nullo, e x.right è null.

423
00:32:14,260 --> 00:32:21,070
Quindi, poiché è una struttura, tutti i campi della struttura saranno i valori zero.

424
00:32:21,070 --> 00:32:24,410
Non abbiamo bisogno di usare che qui, però.

425
00:32:24,410 --> 00:32:27,320
[Studente] Le strutture sono diverse da quelle di altre variabili, e le altre variabili sono

426
00:32:27,320 --> 00:32:31,400
valori di spazzatura, che sono zero?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Altri valori troppo. Quindi, in x, x sarà pari a zero.

428
00:32:36,220 --> 00:32:40,070
Se è in ambito globale, ha un valore iniziale. Va bene >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] In entrambi i casi il valore iniziale che ha dato o zero.

430
00:32:48,950 --> 00:32:53,260
Penso che si prende cura di tutto questo.

431
00:32:53,260 --> 00:32:58,390
>> Va bene. Così la parte successiva della questione si chiede,

432
00:32:58,390 --> 00:33:01,260
"Ora vogliamo scrivere una funzione chiamata contiene

433
00:33:01,260 --> 00:33:04,930
con un prototipo di bool valore int. "

434
00:33:04,930 --> 00:33:08,340
Non abbiamo intenzione di fare bool valore int.

435
00:33:08,340 --> 00:33:15,110
Il nostro prototipo è andare a guardare come

436
00:33:15,110 --> 00:33:22,380
bool (valore int.

437
00:33:22,380 --> 00:33:24,490
E poi stiamo anche andando a passare l'albero

438
00:33:24,490 --> 00:33:28,870
che dovrebbe essere il controllo per vedere se ha quel valore.

439
00:33:28,870 --> 00:33:38,290
Così nodo * albero). Va bene.

440
00:33:38,290 --> 00:33:44,440
E poi si può chiamare con qualcosa di simile,

441
00:33:44,440 --> 00:33:46,090
forse ci vuole printf o qualcosa del genere.

442
00:33:46,090 --> 00:33:51,040
Contiene 6, la nostra radice.

443
00:33:51,040 --> 00:33:54,300
Questo dovrebbe restituire uno, o vero,

444
00:33:54,300 --> 00:33:59,390
che contiene 5 radice deve restituire false.

445
00:33:59,390 --> 00:34:02,690
Quindi prendere un secondo per implementare questo.

446
00:34:02,690 --> 00:34:06,780
Puoi farlo sia iterativo o ricorsivo.

447
00:34:06,780 --> 00:34:09,739
La cosa bella del modo in cui abbiamo impostato le cose è che

448
00:34:09,739 --> 00:34:12,300
si presta alla nostra soluzione ricorsiva molto più facile

449
00:34:12,300 --> 00:34:14,719
rispetto alla variabile globale così ha fatto.

450
00:34:14,719 --> 00:34:19,750
Perché se non ci resta che contiene un valore int, allora non abbiamo modo di recursing giù sottoalberi.

451
00:34:19,750 --> 00:34:24,130
Dovremmo avere una funzione distinta di supporto che ricorsivamente le sottostrutture per noi.

452
00:34:24,130 --> 00:34:29,610
Ma dal momento che abbiamo cambiato a prendere l'albero come argomento,

453
00:34:29,610 --> 00:34:32,760
che deve essere sempre in primo luogo,

454
00:34:32,760 --> 00:34:35,710
ora si può recurse più facilmente.

455
00:34:35,710 --> 00:34:38,960
Così iterativa o ricorsiva, andremo su entrambi,

456
00:34:38,960 --> 00:34:46,139
ma staremo a vedere che finisce con l'essere ricorsive abbastanza facile.

457
00:34:59,140 --> 00:35:02,480
Va bene. Qualcuno ha qualcosa che possiamo lavorare?

458
00:35:02,480 --> 00:35:12,000
>> [Studente] Ho una soluzione iterativa. Va bene >>, iterativo.

459
00:35:12,000 --> 00:35:16,030
Ok, questo sembra buono.

460
00:35:16,030 --> 00:35:18,920
Quindi, vuole camminare con noi attraverso di essa?

461
00:35:18,920 --> 00:35:25,780
[Studente] Certo. Così mi sono messo una variabile temporanea per ottenere il primo nodo della struttura ad albero.

462
00:35:25,780 --> 00:35:28,330
E poi ho collegato in cascata, mentre temperatura non nulla uguale,

463
00:35:28,330 --> 00:35:31,700
così, mentre era ancora nella struttura, credo.

464
00:35:31,700 --> 00:35:35,710
E se il valore è uguale al valore di temperatura che sta puntando,

465
00:35:35,710 --> 00:35:37,640
poi restituisce tale valore.

466
00:35:37,640 --> 00:35:40,210
Altrimenti, si controlla se è sul lato destro o sul lato sinistro.

467
00:35:40,210 --> 00:35:43,400
Se mai una situazione in cui non c'è albero più,

468
00:35:43,400 --> 00:35:47,330
poi lo restituisce - esce il ciclo e restituisce false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Ok. In modo che sembra buono.

470
00:35:52,190 --> 00:35:58,470
Qualcuno ha qualche commento su qualcosa?

471
00:35:58,470 --> 00:36:02,400
Non ho commenti correttezza a tutti.

472
00:36:02,400 --> 00:36:11,020
L'unica cosa che possiamo fare è questo ragazzo.

473
00:36:11,020 --> 00:36:21,660
Oh, sta per andare un po 'lunghetta.

474
00:36:21,660 --> 00:36:33,460
Io che fino sistemare. Va bene.

475
00:36:33,460 --> 00:36:37,150
>> Tutti dovrebbero ricordare come ternario funziona.

476
00:36:37,150 --> 00:36:38,610
Ci sono sicuramente stati quiz in passato

477
00:36:38,610 --> 00:36:41,170
che ti danno una funzione con un operatore ternario,

478
00:36:41,170 --> 00:36:45,750
e dire, tradurre questo, fare qualcosa che non fa uso di ternario.

479
00:36:45,750 --> 00:36:49,140
Quindi questo è un caso molto comune di quando avrei pensato di usare ternario,

480
00:36:49,140 --> 00:36:54,610
dove se una certa condizione impostare una variabile a qualcosa,

481
00:36:54,610 --> 00:36:58,580
altro set che stessa variabile a qualcosa d'altro.

482
00:36:58,580 --> 00:37:03,390
Questo è qualcosa che molto spesso può essere trasformato in questo genere di cose

483
00:37:03,390 --> 00:37:14,420
dove impostare questa variabile a questo - o, beh, è ​​vero? Allora questo, altrimenti questo.

484
00:37:14,420 --> 00:37:18,550
[Studente] La prima è se è vero, giusto?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Si '. Il modo in cui ho sempre letto è, temperatura è uguale al valore maggiore del valore temp,

486
00:37:25,570 --> 00:37:30,680
allora questo, altrimenti questo. E 'una domanda.

487
00:37:30,680 --> 00:37:35,200
E 'più grande? Poi fare la prima cosa. Altrimenti fare la seconda cosa.

488
00:37:35,200 --> 00:37:41,670
Ho quasi sempre - i due punti, ho solo - nella mia testa, ho letto come gli altri.

489
00:37:41,670 --> 00:37:47,180
>> Qualcuno ha una soluzione ricorsiva?

490
00:37:47,180 --> 00:37:49,670
Va bene. Questo che andremo a - potrebbe già essere grande,

491
00:37:49,670 --> 00:37:53,990
ma stiamo andando a fare ancora meglio.

492
00:37:53,990 --> 00:37:58,720
Questo è più o meno la stessa idea esatta.

493
00:37:58,720 --> 00:38:03,060
E 'solo che, beh, vuoi spiegare?

494
00:38:03,060 --> 00:38:08,340
[Studente] Certo. Quindi stiamo facendo in modo che l'albero non è null in primo luogo,

495
00:38:08,340 --> 00:38:13,380
perché se l'albero è null allora sta andando a restituire false, perché non lo abbiamo trovato.

496
00:38:13,380 --> 00:38:19,200
E se c'è ancora un albero, andiamo in - per prima cosa verificare se il valore è il nodo corrente.

497
00:38:19,200 --> 00:38:23,740
Restituisce vero se lo è, e se non ci ricorsione a sinistra oa destra.

498
00:38:23,740 --> 00:38:25,970
Ti sembra appropriato? >> Mm-hmm. (Accordo)

499
00:38:25,970 --> 00:38:33,880
Così notare che questo è quasi - strutturalmente molto simile alla soluzione iterativa.

500
00:38:33,880 --> 00:38:38,200
E 'solo che invece di recursing, abbiamo avuto un ciclo while.

501
00:38:38,200 --> 00:38:40,840
E il caso di base qui, dove albero non nullo pari

502
00:38:40,840 --> 00:38:44,850
era la condizione in cui ci siamo lasciati fuori dal ciclo while.

503
00:38:44,850 --> 00:38:50,200
Sono molto simili. Ma stiamo andando a prendere un passo avanti.

504
00:38:50,200 --> 00:38:54,190
Ora, facciamo la stessa cosa qui.

505
00:38:54,190 --> 00:38:57,680
Si noti che stiamo tornando la stessa cosa in entrambe le linee,

506
00:38:57,680 --> 00:39:00,220
tranne che per un argomento è diverso.

507
00:39:00,220 --> 00:39:07,950
Quindi stiamo andando a fare che in un ternario.

508
00:39:07,950 --> 00:39:13,790
Mi ha colpito qualcosa di opzione, e ha fatto un simbolo. Va bene.

509
00:39:13,790 --> 00:39:21,720
Quindi stiamo andando a tornare che contiene.

510
00:39:21,720 --> 00:39:28,030
Sta per essere più righe, beh, è ​​ingrandita.

511
00:39:28,030 --> 00:39:31,060
Di solito, come una cosa stilistica, non credo che molte persone

512
00:39:31,060 --> 00:39:38,640
inserire uno spazio dopo la freccia, ma credo che se sei coerente, va bene.

513
00:39:38,640 --> 00:39:44,320
Se il valore è inferiore al valore albero, vogliamo ricorsione a sinistra albero,

514
00:39:44,320 --> 00:39:53,890
altro vogliamo ricorsione a destra albero.

515
00:39:53,890 --> 00:39:58,610
Così che era passo quello di rendere questo look più piccoli.

516
00:39:58,610 --> 00:40:02,660
Fase due di rendere questo look più piccoli -

517
00:40:02,660 --> 00:40:09,150
siamo in grado di separare il più righe.

518
00:40:09,150 --> 00:40:16,500
Va bene. Fase due di far sembrare più piccolo è qui,

519
00:40:16,500 --> 00:40:25,860
modo che il valore di ritorno è uguale al valore albero, o contiene altro.

520
00:40:25,860 --> 00:40:28,340
>> Questa è una cosa importante.

521
00:40:28,340 --> 00:40:30,860
Non so se ha detto esplicitamente in classe,

522
00:40:30,860 --> 00:40:34,740
ma si chiama corto circuito di valutazione.

523
00:40:34,740 --> 00:40:41,060
L'idea qui è un valore == valore albero.

524
00:40:41,060 --> 00:40:49,960
Se questo è vero, allora questo è vero, e noi vogliamo 'o' che con tutto ciò che è qui.

525
00:40:49,960 --> 00:40:52,520
Così, senza nemmeno pensare a tutto ciò che è qui,

526
00:40:52,520 --> 00:40:55,070
qual è l'intera espressione intenzione di tornare?

527
00:40:55,070 --> 00:40:59,430
[Studente] Vero? >> Già, perché vero di qualsiasi cosa,

528
00:40:59,430 --> 00:41:04,990
in OR - in OR o vero con qualcosa è necessariamente vero.

529
00:41:04,990 --> 00:41:08,150
Così, non appena si vede il valore di ritorno = valore di albero,

530
00:41:08,150 --> 00:41:10,140
stiamo solo andando a restituire true.

531
00:41:10,140 --> 00:41:15,710
Neanche andando a recurse contiene più in basso la linea.

532
00:41:15,710 --> 00:41:20,980
Siamo in grado di fare un passo ulteriore.

533
00:41:20,980 --> 00:41:29,490
Albero di ritorno non nullo uguale e tutto questo.

534
00:41:29,490 --> 00:41:32,650
Esso ha una funzione inline.

535
00:41:32,650 --> 00:41:36,790
Questo è un esempio di valutazione di corto circuito.

536
00:41:36,790 --> 00:41:40,680
Ma ora è la stessa idea -

537
00:41:40,680 --> 00:41:47,320
invece di - quindi se albero non è uguale a null - o, anche,

538
00:41:47,320 --> 00:41:49,580
se albero fa nulla uguale, che è il caso di cattivo,

539
00:41:49,580 --> 00:41:54,790
se albero è uguale a null, quindi la prima condizione sarà falsa.

540
00:41:54,790 --> 00:42:00,550
Così falsa AND con qualcosa sta per essere ciò?

541
00:42:00,550 --> 00:42:04,640
[Studente] False. Sì >>. Questa è l'altra metà della valutazione di corto circuito,

542
00:42:04,640 --> 00:42:10,710
dove se non nullo albero non è uguale, allora non si ha intenzione di andare anche -

543
00:42:10,710 --> 00:42:14,930
o se albero fa nulla uguale, quindi non abbiamo intenzione di fare un valore == valore albero.

544
00:42:14,930 --> 00:42:17,010
Stiamo solo andando a restituire immediatamente false.

545
00:42:17,010 --> 00:42:20,970
Il che è importante, in quanto se così non fosse corto circuito evaluate,

546
00:42:20,970 --> 00:42:25,860
poi se albero fa nulla uguale, questa seconda condizione sta andando per colpa segmento,

547
00:42:25,860 --> 00:42:32,510
perché tree-> valore dereferenziazione nullo.

548
00:42:32,510 --> 00:42:40,490
Quindi, questo è tutto. Può fare questo - spostare una volta sopra.

549
00:42:40,490 --> 00:42:44,840
Questa è una cosa molto comune anche, non fare questa linea con questo,

550
00:42:44,840 --> 00:42:49,000
ma è una cosa comune in condizioni, forse non proprio qui,

551
00:42:49,000 --> 00:42:59,380
ma se (albero! = NULL, e l'albero-> Valore ==), fare qualsiasi cosa.

552
00:42:59,380 --> 00:43:01,560
Questa è una condizione molto comune, in cui invece di avere

553
00:43:01,560 --> 00:43:06,770
per rompere questo in due se e dove vuoi, è il nulla albero?

554
00:43:06,770 --> 00:43:11,780
Ok, non è nulla, così ora è il valore dell'albero pari al valore? Fate questo.

555
00:43:11,780 --> 00:43:17,300
Invece, questa condizione, questo non potrà mai errore di segmentazione

556
00:43:17,300 --> 00:43:21,220
perché si romperà se questo succede a essere null.

557
00:43:21,220 --> 00:43:24,000
Beh, credo che se il tuo albero è un puntatore completamente invalido, può ancora errore di segmentazione,

558
00:43:24,000 --> 00:43:26,620
ma non può errore di segmentazione se albero è nullo.

559
00:43:26,620 --> 00:43:32,900
Se fosse nullo, sarebbe scoppiata la prima mai dereferenziati il ​​puntatore del mouse, in primo luogo.

560
00:43:32,900 --> 00:43:35,000
[Studente] E `la valutazione chiamato pigro?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] valutazione pigra è una cosa a parte.

562
00:43:40,770 --> 00:43:49,880
Valutazione pigra è più simile a chiedere di un valore,

563
00:43:49,880 --> 00:43:54,270
Vi chiedo di calcolare un valore, un po ', ma tu non ne hai bisogno subito.

564
00:43:54,270 --> 00:43:59,040
Quindi, fino a che realmente ne hanno bisogno, non viene valutato.

565
00:43:59,040 --> 00:44:03,920
Questa non è esattamente la stessa cosa, ma nel pset Huffman,

566
00:44:03,920 --> 00:44:06,520
si dice che noi "pigramente" scrivere.

567
00:44:06,520 --> 00:44:08,670
La ragione per cui lo facciamo è perché ci sta effettivamente buffer di scrittura -

568
00:44:08,670 --> 00:44:11,820
non vogliamo scrivere singoli bit alla volta,

569
00:44:11,820 --> 00:44:15,450
o singoli byte alla volta, noi invece vogliamo ottenere un pezzo di byte.

570
00:44:15,450 --> 00:44:19,270
Poi, una volta che abbiamo un pezzo di byte, quindi noi lo scrivere.

571
00:44:19,270 --> 00:44:22,640
Anche se gli chiedi di scrivere - e fwrite e fread fare la stessa cosa.

572
00:44:22,640 --> 00:44:26,260
Essi tamponare la tua legge e scrive.

573
00:44:26,260 --> 00:44:31,610
Anche se si chiede di scrivere subito, probabilmente non lo farà.

574
00:44:31,610 --> 00:44:34,540
E non si può essere certi che le cose stanno per essere scritto

575
00:44:34,540 --> 00:44:37,540
finché non viene chiamato hfclose o qualunque cosa sia,

576
00:44:37,540 --> 00:44:39,620
che poi dice, va bene, sto chiudendo il mio file,

577
00:44:39,620 --> 00:44:43,450
questo significa che è meglio scrivere tutto quello che non ho scritto ancora.

578
00:44:43,450 --> 00:44:45,770
Non ha bisogno di scrivere tutto fuori

579
00:44:45,770 --> 00:44:49,010
fino a quando si sta chiudendo il file, e quindi ha bisogno di.

580
00:44:49,010 --> 00:44:56,220
Ecco, questo è proprio quello pigro - aspetta fino a quando non deve accadere.

581
00:44:56,220 --> 00:44:59,990
Questo - prendere 51 e andrai in esso in modo più dettagliato,

582
00:44:59,990 --> 00:45:05,470
perché OCaml e tutto in 51, tutto è ricorsione.

583
00:45:05,470 --> 00:45:08,890
Non ci sono soluzioni iterative, in fondo.

584
00:45:08,890 --> 00:45:11,550
Tutto è ricorsione, e la valutazione pigra

585
00:45:11,550 --> 00:45:14,790
sarà importante per molte circostanze

586
00:45:14,790 --> 00:45:19,920
dove, se non si è pigramente valutare, ciò significherebbe -

587
00:45:19,920 --> 00:45:24,760
L'esempio è in streaming, che sono infinitamente lungo.

588
00:45:24,760 --> 00:45:30,990
In teoria, si può pensare dei numeri naturali come un flusso di 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Così le cose vanno bene pigramente valutati.

590
00:45:33,090 --> 00:45:37,210
Se dico che voglio il decimo numero, allora posso valutare fino al decimo numero.

591
00:45:37,210 --> 00:45:40,300
Se voglio il numero centesimo, allora posso valutare fino al numero centesimo.

592
00:45:40,300 --> 00:45:46,290
Senza valutazione pigra, quindi sta andando a cercare di valutare tutti i numeri immediatamente.

593
00:45:46,290 --> 00:45:50,000
Stai valutando i numeri infiniti, e che non è solo possibile.

594
00:45:50,000 --> 00:45:52,080
Quindi ci sono un sacco di casi in cui la valutazione pigra

595
00:45:52,080 --> 00:45:57,840
è solo essenziale per ottenere le cose al lavoro.

596
00:45:57,840 --> 00:46:05,260
>> Ora vogliamo scrivere inserto inserto dove sta per essere

597
00:46:05,260 --> 00:46:08,430
allo stesso modo cambiando nella sua definizione.

598
00:46:08,430 --> 00:46:10,470
Quindi, in questo momento è inserto bool (int valore).

599
00:46:10,470 --> 00:46:23,850
Stiamo andando a cambiare la situazione a inserto bool (valore int, nodo * albero).

600
00:46:23,850 --> 00:46:29,120
Stiamo in realtà sta per cambiare di nuovo in un po ', vedremo il perché.

601
00:46:29,120 --> 00:46:32,210
E cerchiamo di spostare build_node, solo per il gusto di farlo,

602
00:46:32,210 --> 00:46:36,730
sopra inserire in modo da non dover scrivere un prototipo di funzione.

603
00:46:36,730 --> 00:46:42,450
Il che è un suggerimento che si sta andando ad utilizzare build_node in inserimento.

604
00:46:42,450 --> 00:46:49,590
Va bene. Prendi un minuto per questo.

605
00:46:49,590 --> 00:46:52,130
Penso che ho salvato la revisione se si vuole tirare da quella,

606
00:46:52,130 --> 00:47:00,240
o, almeno, l'ho fatto ora.

607
00:47:00,240 --> 00:47:04,190
Volevo un momento di pausa per pensare alla logica di inserimento,

608
00:47:04,190 --> 00:47:08,750
se non si può pensare di esso.

609
00:47:08,750 --> 00:47:12,860
In sostanza, si sarà sempre solo l'inserimento di foglie.

610
00:47:12,860 --> 00:47:18,640
Come, se inserisco 1, poi ho inevitabilmente per essere l'inserimento di 1 -

611
00:47:18,640 --> 00:47:21,820
Mi cambio in nero - I'Ll essere inserendo 1 qui.

612
00:47:21,820 --> 00:47:28,070
Oppure, se inserisco 4, voglio essere l'inserimento di 4 oltre qui.

613
00:47:28,070 --> 00:47:32,180
Quindi, non importa quello che fai, si sta andando ad essere l'inserimento di una foglia.

614
00:47:32,180 --> 00:47:36,130
Tutto quello che dovete fare è scorrere lungo l'albero fino ad arrivare al nodo

615
00:47:36,130 --> 00:47:40,890
che dovrebbe essere padre del nodo, padre del nuovo nodo,

616
00:47:40,890 --> 00:47:44,560
e quindi modificare il suo puntatore a sinistra oa destra, a seconda che

617
00:47:44,560 --> 00:47:47,060
è maggiore o minore del nodo corrente.

618
00:47:47,060 --> 00:47:51,180
Modificare tale puntatore per puntare al nuovo nodo.

619
00:47:51,180 --> 00:48:05,490
Quindi scorrere verso il basso l'albero, fare il punto foglia al nuovo nodo.

620
00:48:05,490 --> 00:48:09,810
Anche riflettere sul perché che vieta il tipo di situazione prima,

621
00:48:09,810 --> 00:48:17,990
dove ho costruito l'albero binario in cui è stato corretto

622
00:48:17,990 --> 00:48:19,920
se solo guardato un singolo nodo,

623
00:48:19,920 --> 00:48:24,830
ma 9 era a sinistra del 7 se iterato giù tutto il senso.

624
00:48:24,830 --> 00:48:29,770
Ecco, questo è impossibile, in questo scenario, in quanto -

625
00:48:29,770 --> 00:48:32,530
pensare di inserire 9 o qualcosa, in corrispondenza del nodo prima,

626
00:48:32,530 --> 00:48:35,350
Io vado a vedere 7 e sto solo intenzione di andare a destra.

627
00:48:35,350 --> 00:48:38,490
Quindi, non importa quello che faccio, se sto andando a inserire una foglia,

628
00:48:38,490 --> 00:48:40,790
e ad una foglia utilizzando l'algoritmo appropriato,

629
00:48:40,790 --> 00:48:43,130
che sarà impossibile per me per inserire 9 a sinistra di 7

630
00:48:43,130 --> 00:48:48,250
perché non appena mi ha colpito sette ho intenzione di andare a destra.

631
00:48:59,740 --> 00:49:02,070
Qualcuno ha qualcosa per iniziare?

632
00:49:02,070 --> 00:49:05,480
[Studente] che faccio. Certo >>.

633
00:49:05,480 --> 00:49:09,200
[Studente, incomprensibile]

634
00:49:09,200 --> 00:49:14,390
[Altro studente, incomprensibile]

635
00:49:14,390 --> 00:49:18,330
[Bowden] E 'apprezzato. Va bene. Vuoi spiegare?

636
00:49:18,330 --> 00:49:20,690
>> [Studente] Poiché sappiamo che siamo stati l'inserimento

637
00:49:20,690 --> 00:49:24,060
nuovi nodi alla fine della struttura,

638
00:49:24,060 --> 00:49:28,070
Ho fatto passare attraverso l'albero iterativamente

639
00:49:28,070 --> 00:49:31,360
fino a quando ho avuto modo di un nodo che puntava a null.

640
00:49:31,360 --> 00:49:34,220
E poi ho deciso di metterlo sia sul lato destro o sul lato sinistro

641
00:49:34,220 --> 00:49:37,420
utilizzando questa variabile diritto, ma mi ha detto dove metterlo.

642
00:49:37,420 --> 00:49:41,850
E poi, in sostanza, ho appena fatto che durano -

643
00:49:41,850 --> 00:49:47,520
che il nodo punto di temperatura per il nuovo nodo che si stava creando,

644
00:49:47,520 --> 00:49:50,770
sia sul lato sinistro o sul lato destro, a seconda che il valore di destra era.

645
00:49:50,770 --> 00:49:56,530
Infine, a impostare il nuovo valore del nodo al valore del suo test.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Va bene, quindi non vedo un problema qui.

647
00:49:59,550 --> 00:50:02,050
Questo è come il 95% del tragitto.

648
00:50:02,050 --> 00:50:07,550
L'unico problema che vedo, beh, fa vedere a nessuno un problema?

649
00:50:07,550 --> 00:50:18,400
Qual è la circostanza in cui si rompono fuori dal giro?

650
00:50:18,400 --> 00:50:22,100
[Studente] Se temp è nullo? Sì >>. Allora, come uscire dal ciclo è se temp è nullo.

651
00:50:22,100 --> 00:50:30,220
Ma cosa faccio qui?

652
00:50:30,220 --> 00:50:35,410
Io temperatura dereference, che è inevitabilmente nullo.

653
00:50:35,410 --> 00:50:39,840
Così l'altra cosa che devi fare non è solo tenere traccia fino a quando temperatura è nullo,

654
00:50:39,840 --> 00:50:45,590
si desidera tenere traccia del genitore in ogni momento.

655
00:50:45,590 --> 00:50:52,190
Vogliamo anche * nodo padre, credo che possiamo continuare che a nulla in un primo momento.

656
00:50:52,190 --> 00:50:55,480
Questo sta per avere un comportamento strano per la radice dell'albero,

657
00:50:55,480 --> 00:50:59,210
ma ci arriveremo.

658
00:50:59,210 --> 00:51:03,950
Se il valore è maggiore di qualsiasi altra cosa, quindi temp = temperatura giusta.

659
00:51:03,950 --> 00:51:07,910
Ma prima di farlo, temp = genitore.

660
00:51:07,910 --> 00:51:14,500
Oppure i genitori sempre andando a temperatura uguale? E 'questo il caso?

661
00:51:14,500 --> 00:51:19,560
Se temp non è nullo, quindi ho intenzione di spostare verso il basso, non importa quale,

662
00:51:19,560 --> 00:51:24,030
ad un nodo per il quale temp è il genitore.

663
00:51:24,030 --> 00:51:27,500
Così genitore sarà temp, e poi mi sposto temperatura verso il basso.

664
00:51:27,500 --> 00:51:32,410
Ora temperatura è nullo, ma i punti padre al padre della cosa che è nullo.

665
00:51:32,410 --> 00:51:39,110
Così qui, non voglio impostare uguale a destra 1.

666
00:51:39,110 --> 00:51:41,300
Così ho spostato a destra, quindi se a destra = 1,

667
00:51:41,300 --> 00:51:45,130
e credo che anche voi volete fare -

668
00:51:45,130 --> 00:51:48,530
se si sposta a sinistra, si desidera impostare diritto uguale a 0.

669
00:51:48,530 --> 00:51:55,950
Oppure se mai sposta a destra.

670
00:51:55,950 --> 00:51:58,590
Quindi a destra = 0. Se il diritto = 1,

671
00:51:58,590 --> 00:52:04,260
ora vogliamo rendere effettivo il diritto newnode puntatore genitore,

672
00:52:04,260 --> 00:52:08,520
altra cosa vuole fare la sinistra newnode puntatore genitore.

673
00:52:08,520 --> 00:52:16,850
Domande su questo?

674
00:52:16,850 --> 00:52:24,880
Va bene. Quindi questo è il nostro modo - beh, in realtà, invece di fare questo,

675
00:52:24,880 --> 00:52:29,630
ci aspettava quasi di utilizzare build_node.

676
00:52:29,630 --> 00:52:40,450
E poi se newnode uguale a null, return false.

677
00:52:40,450 --> 00:52:44,170
Questo è quello. Ora, questo è quello che ci aspettavamo di fare.

678
00:52:44,170 --> 00:52:47,690
>> Questo è ciò che le soluzioni del personale fanno.

679
00:52:47,690 --> 00:52:52,360
Non sono d'accordo con questo come il modo "giusto" di andare su di esso

680
00:52:52,360 --> 00:52:57,820
ma questo è perfettamente bene e funzionerà.

681
00:52:57,820 --> 00:53:02,840
Una cosa che è un po 'strano proprio ora è

682
00:53:02,840 --> 00:53:08,310
se l'albero inizia come nullo, si passa in un albero nullo.

683
00:53:08,310 --> 00:53:12,650
Credo che dipende da come si definisce il comportamento di passare in un albero nullo.

684
00:53:12,650 --> 00:53:15,490
Mi sembra che se si passa in un albero nullo,

685
00:53:15,490 --> 00:53:17,520
quindi inserendo il valore in un albero nullo

686
00:53:17,520 --> 00:53:23,030
deve solo restituire un albero in cui l'unico valore è quello singolo nodo.

687
00:53:23,030 --> 00:53:25,830
Sei persone sono d'accordo con questo? Si potrebbe, se si vuole,

688
00:53:25,830 --> 00:53:28,050
se si passa in un albero nullo

689
00:53:28,050 --> 00:53:31,320
e si desidera inserire un valore in esso, restituire false.

690
00:53:31,320 --> 00:53:33,830
E 'a voi definire tale.

691
00:53:33,830 --> 00:53:38,320
Per fare la prima cosa che ho detto e poi -

692
00:53:38,320 --> 00:53:40,720
bene, si sta andando ad avere problemi di farlo, perché

693
00:53:40,720 --> 00:53:44,090
sarebbe più facile se avessimo un puntatore globale alla cosa,

694
00:53:44,090 --> 00:53:48,570
ma non, quindi se albero è nulla, non c'è niente che possiamo fare al riguardo.

695
00:53:48,570 --> 00:53:50,960
Possiamo solo restituire false.

696
00:53:50,960 --> 00:53:52,840
Quindi ho intenzione di cambiare inserto.

697
00:53:52,840 --> 00:53:56,540
Siamo tecnicamente potrebbe semplicemente cambiare questo qui,

698
00:53:56,540 --> 00:53:58,400
come è l'iterazione di cose,

699
00:53:58,400 --> 00:54:04,530
ma ho intenzione di cambiare inserto di fare un nodo della struttura **.

700
00:54:04,530 --> 00:54:07,510
Puntatori doppi.

701
00:54:07,510 --> 00:54:09,710
Che cosa significa?

702
00:54:09,710 --> 00:54:12,330
Invece di trattare con puntatori a nodi,

703
00:54:12,330 --> 00:54:16,690
la cosa che mi vado a manipolare questo puntatore.

704
00:54:16,690 --> 00:54:18,790
Io vado a manipolare questo puntatore.

705
00:54:18,790 --> 00:54:21,770
Ho intenzione di essere manipolare puntatori direttamente.

706
00:54:21,770 --> 00:54:25,760
Questo ha senso dal momento che, pensate in basso -

707
00:54:25,760 --> 00:54:33,340
bene, in questo momento questo punti a null.

708
00:54:33,340 --> 00:54:38,130
Quello che voglio fare è manipolare questo puntatore per puntare a null non.

709
00:54:38,130 --> 00:54:40,970
Voglio che per puntare al mio nuovo nodo.

710
00:54:40,970 --> 00:54:44,870
Se ho appena tenere traccia dei puntatori ai miei puntatori,

711
00:54:44,870 --> 00:54:47,840
allora non c'è bisogno di tenere traccia di un puntatore genitore.

712
00:54:47,840 --> 00:54:52,640
Posso solo tenere traccia per vedere se il puntatore punta a null,

713
00:54:52,640 --> 00:54:54,580
e se il puntatore punta a null,

714
00:54:54,580 --> 00:54:57,370
cambiare per puntare al nodo che voglio.

715
00:54:57,370 --> 00:55:00,070
E posso cambiarlo perchè ho un puntatore al puntatore.

716
00:55:00,070 --> 00:55:02,040
Vediamo un po 'adesso.

717
00:55:02,040 --> 00:55:05,470
Si può effettivamente fare in modo ricorsivo abbastanza facilmente.

718
00:55:05,470 --> 00:55:08,080
Vogliamo farlo?

719
00:55:08,080 --> 00:55:10,980
Sì, lo facciamo.

720
00:55:10,980 --> 00:55:16,790
>> Vediamolo in modo ricorsivo.

721
00:55:16,790 --> 00:55:24,070
In primo luogo, ciò che è il nostro scenario di base sarà?

722
00:55:24,070 --> 00:55:29,140
Quasi sempre il nostro scenario di base, ma in realtà, questo è una specie di complicato.

723
00:55:29,140 --> 00:55:34,370
Per prima cosa, se (albero == NULL)

724
00:55:34,370 --> 00:55:37,550
Credo che stiamo solo andando a restituire false.

725
00:55:37,550 --> 00:55:40,460
Questo è diverso dal vostro albero di essere nullo.

726
00:55:40,460 --> 00:55:44,510
Questo è il puntatore al puntatore nullo privilegi di root

727
00:55:44,510 --> 00:55:48,360
il che significa che il puntatore radice non esiste.

728
00:55:48,360 --> 00:55:52,390
Così qui, se faccio

729
00:55:52,390 --> 00:55:55,760
* nodo - facciamo solo riutilizzare questo.

730
00:55:55,760 --> 00:55:58,960
Nodo * root = NULL,

731
00:55:58,960 --> 00:56:00,730
e poi ho intenzione di chiamare inserto facendo qualcosa di simile,

732
00:56:00,730 --> 00:56:04,540
inserire 4 in & root.

733
00:56:04,540 --> 00:56:06,560
Quindi & root, se root è un nodo *

734
00:56:06,560 --> 00:56:11,170
allora e radice sta per essere un nodo **.

735
00:56:11,170 --> 00:56:15,120
Questo è valido. In questo caso, albero, qui,

736
00:56:15,120 --> 00:56:20,120
albero non è nulla - o inserto.

737
00:56:20,120 --> 00:56:24,630
Qui. Albero non è null; albero * è nulla, che va bene

738
00:56:24,630 --> 00:56:26,680
perché se albero * è nullo, allora posso manipolare

739
00:56:26,680 --> 00:56:29,210
per puntare ora a quello che voglio puntare a.

740
00:56:29,210 --> 00:56:34,750
Ma se albero è nullo, significa che ho appena venuto qui e ha detto nulla.

741
00:56:34,750 --> 00:56:42,710
Questo non ha senso. Io non posso fare niente con questo.

742
00:56:42,710 --> 00:56:45,540
Se albero è null, return false.

743
00:56:45,540 --> 00:56:48,220
Così ho già detto in pratica ciò che il nostro scenario di base reale.

744
00:56:48,220 --> 00:56:50,580
E che cosa è che sta per essere?

745
00:56:50,580 --> 00:56:55,030
[Studente, incomprensibile]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Sì. Quindi, se (* albero == NULL).

747
00:57:00,000 --> 00:57:04,520
Questo si riferisce al caso qui

748
00:57:04,520 --> 00:57:09,640
dove se il mio puntatore è il puntatore sono concentrato su,

749
00:57:09,640 --> 00:57:12,960
così come mi sono concentrato su questo puntatore, ora mi sono concentrato su questo puntatore.

750
00:57:12,960 --> 00:57:15,150
Ora sono concentrato su questo puntatore.

751
00:57:15,150 --> 00:57:18,160
Quindi, se il mio puntatore rosso, che è il mio ** nodo,

752
00:57:18,160 --> 00:57:22,880
è sempre - se *, il mio puntatore rosso, è sempre nullo,

753
00:57:22,880 --> 00:57:28,470
ciò significa che io sono al caso in cui mi sto concentrando su un puntatore che punti -

754
00:57:28,470 --> 00:57:32,530
questo è un puntatore che appartiene ad una foglia.

755
00:57:32,530 --> 00:57:41,090
Voglio cambiare questo puntatore per puntare al mio nuovo nodo.

756
00:57:41,090 --> 00:57:45,230
Torna qui.

757
00:57:45,230 --> 00:57:56,490
Il mio newnode sarà solo nodo * n = build_node (valore)

758
00:57:56,490 --> 00:58:07,300
allora n, se n = NULL, restituisce false.

759
00:58:07,300 --> 00:58:12,600
Altrimenti vogliamo cambiare ciò che il puntatore sta puntando attualmente

760
00:58:12,600 --> 00:58:17,830
per puntare ora al nostro nodo di recente costruzione.

761
00:58:17,830 --> 00:58:20,280
Siamo in grado di darsi da fare qui.

762
00:58:20,280 --> 00:58:30,660
Invece di dire n, diciamo * albero = se albero *.

763
00:58:30,660 --> 00:58:35,450
Capire a tutti che? Che da trattare con puntatori a puntatori,

764
00:58:35,450 --> 00:58:40,750
siamo in grado di cambiare i puntatori nulli per puntare a cose che vogliamo loro di puntare.

765
00:58:40,750 --> 00:58:42,820
Questo è il nostro scenario di base.

766
00:58:42,820 --> 00:58:45,740
>> Ora la nostra ricorrenza, o il nostro ricorsione,

767
00:58:45,740 --> 00:58:51,430
sta per essere molto simile a tutte le altre ricorsioni che abbiamo fatto.

768
00:58:51,430 --> 00:58:55,830
Stiamo andando a voler inserire il valore,

769
00:58:55,830 --> 00:58:59,040
e ora ho intenzione di usare di nuovo ternario, ma ciò che è la nostra condizione sarà?

770
00:58:59,040 --> 00:59:05,180
Che cosa si prova che stiamo cercando di decidere se vogliamo andare a destra oa sinistra?

771
00:59:05,180 --> 00:59:07,760
Facciamolo in fasi separate.

772
00:59:07,760 --> 00:59:18,850
Se (valore <) cosa?

773
00:59:18,850 --> 00:59:23,200
[Studente] Il valore dell'albero?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Quindi ricorda che sono attualmente -

775
00:59:27,490 --> 00:59:31,260
[Gli studenti, incomprensibili]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Si ', quindi proprio qui, diciamo che la freccia verde

777
00:59:34,140 --> 00:59:39,050
è un esempio di quale albero è attualmente, è un puntatore a questo puntatore.

778
00:59:39,050 --> 00:59:46,610
Questo significa che io sono un puntatore a un puntatore a 3.

779
00:59:46,610 --> 00:59:48,800
Il dereference due volte suonava bene.

780
00:59:48,800 --> 00:59:51,010
Cosa devo - come faccio a farlo?

781
00:59:51,010 --> 00:59:53,210
[Studente] risoluzione del riferimento di una volta, e poi fare freccia in quel modo?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Così (albero *) è il dereference una volta, -> valore

783
00:59:58,420 --> 01:00:05,960
sta per darmi il valore del nodo che sto indicando indirettamente.

784
01:00:05,960 --> 01:00:11,980
Quindi posso anche scriverlo ** tree.value se preferite.

785
01:00:11,980 --> 01:00:18,490
In entrambi i casi funziona.

786
01:00:18,490 --> 01:00:26,190
Se questo è il caso, allora voglio chiamare inserire con valore.

787
01:00:26,190 --> 01:00:32,590
E che cosa è il mio nodo aggiornato ** sarà?

788
01:00:32,590 --> 01:00:39,440
Voglio andare a sinistra, in modo da tree.left ** sarà mia sinistra.

789
01:00:39,440 --> 01:00:41,900
E voglio che il puntatore a quella cosa

790
01:00:41,900 --> 01:00:44,930
in modo che se la sinistra finisce per essere il puntatore nullo,

791
01:00:44,930 --> 01:00:48,360
Posso modificare per puntare al mio nuovo nodo.

792
01:00:48,360 --> 01:00:51,460
>> E l'altro caso può essere molto simile.

793
01:00:51,460 --> 01:00:55,600
Facciamo effettivamente fare che il mio ternario in questo momento.

794
01:00:55,600 --> 01:01:04,480
Inserire il valore se il valore <(albero **). Valore.

795
01:01:04,480 --> 01:01:11,040
Poi vogliamo aggiornare i nostri ** a sinistra,

796
01:01:11,040 --> 01:01:17,030
altra cosa desidera aggiornare i nostri ** a destra.

797
01:01:17,030 --> 01:01:22,540
[Studente] Ritiene che ottenere il puntatore al puntatore?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Si ricorda che - ** tree.right è una stella nodo.

799
01:01:30,940 --> 01:01:35,040
[Studente, incomprensibile] >> Si '.

800
01:01:35,040 --> 01:01:41,140
** Tree.right è così puntatore o qualcosa del genere.

801
01:01:41,140 --> 01:01:45,140
Quindi prendendo un puntatore a tale, che mi dà quello che voglio

802
01:01:45,140 --> 01:01:50,090
del puntatore a quel ragazzo.

803
01:01:50,090 --> 01:01:54,260
[Studente] Possiamo andare più volte perché stiamo usando i due puntatori?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Si '. So - no, è possibile, e che la soluzione prima di

805
01:01:58,220 --> 01:02:04,540
era un modo di farlo senza fare due puntatori.

806
01:02:04,540 --> 01:02:08,740
È necessario essere in grado di comprendere con due puntatori,

807
01:02:08,740 --> 01:02:11,660
e questa è una soluzione detergente.

808
01:02:11,660 --> 01:02:16,090
Si noti inoltre che, cosa succede se il mio albero -

809
01:02:16,090 --> 01:02:24,480
cosa succede se la mia radice era nullo? Cosa succede se faccio questo caso proprio qui?

810
01:02:24,480 --> 01:02:30,540
Quindi il nodo * root = NULL, inserire 4 in & root.

811
01:02:30,540 --> 01:02:35,110
Ciò che è radice sarà dopo questo?

812
01:02:35,110 --> 01:02:37,470
[Studente, incomprensibile] >> Si '.

813
01:02:37,470 --> 01:02:41,710
Valore di riferimento sarà 4.

814
01:02:41,710 --> 01:02:45,510
Root sinistra sta per essere nullo, giusto radice sta per essere nullo.

815
01:02:45,510 --> 01:02:49,490
Nel caso in cui non abbiamo passato radice per indirizzo,

816
01:02:49,490 --> 01:02:52,490
non siamo riusciti a modificare la root.

817
01:02:52,490 --> 01:02:56,020
Nel caso in cui l'albero - dove root è stato nullo,

818
01:02:56,020 --> 01:02:58,410
abbiamo dovuto restituire false. Non c'è niente che potessimo fare.

819
01:02:58,410 --> 01:03:01,520
Non si può inserire un nodo in un albero vuoto.

820
01:03:01,520 --> 01:03:06,810
Ma ora possiamo, dobbiamo solo fare un albero vuoto in un unico nodo della struttura.

821
01:03:06,810 --> 01:03:13,400
Qual è di solito il modo atteso che si suppone di lavorare.

822
01:03:13,400 --> 01:03:21,610
>> Inoltre, questo è notevolmente più corta

823
01:03:21,610 --> 01:03:26,240
anche tenere traccia del genitore, e così non si scorre verso il basso tutto il senso.

824
01:03:26,240 --> 01:03:30,140
Ora ho dei miei genitori, e io ho il mio puntatore del diritto dei genitori a qualsiasi altra cosa.

825
01:03:30,140 --> 01:03:35,640
Invece, se abbiamo fatto questo modo iterativo, sarebbe la stessa idea con un ciclo while.

826
01:03:35,640 --> 01:03:38,100
Ma invece di avere a che fare con il mio puntatore del genitore,

827
01:03:38,100 --> 01:03:40,600
invece il mio puntatore attuale sarebbe la cosa

828
01:03:40,600 --> 01:03:43,790
che sto modificando direttamente per puntare al mio nuovo nodo.

829
01:03:43,790 --> 01:03:46,090
Non avere a che fare con il fatto che è rivolta a sinistra.

830
01:03:46,090 --> 01:03:48,810
Non avere a che fare con il fatto che è rivolta verso destra.

831
01:03:48,810 --> 01:04:00,860
E 'solo ciò che questo puntatore è, ho intenzione di impostare in modo che punti al mio nuovo nodo.

832
01:04:00,860 --> 01:04:05,740
Tutti capire come funziona?

833
01:04:05,740 --> 01:04:09,460
Se no, perché vogliamo fare in questo modo,

834
01:04:09,460 --> 01:04:14,920
ma almeno che questo funziona come soluzione?

835
01:04:14,920 --> 01:04:17,110
[Studente] Dove ci restituisce true?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Questo è probabilmente proprio qui.

837
01:04:21,550 --> 01:04:26,690
Se correttamente inserito, restituisce true.

838
01:04:26,690 --> 01:04:32,010
Altrimenti, qui stiamo andando a voler restituire qualunque Insert Returns.

839
01:04:32,010 --> 01:04:35,950
>> E cosa c'è di speciale in questa funzione ricorsiva?

840
01:04:35,950 --> 01:04:43,010
E 'la coda ricorsiva, così fino a quando si compila con qualche ottimizzazione,

841
01:04:43,010 --> 01:04:48,060
si riconoscerà questo e non troverete mai un overflow dello stack da questo,

842
01:04:48,060 --> 01:04:53,230
anche se il nostro albero ha un'altezza di 10.000 o 10 milioni.

843
01:04:53,230 --> 01:04:55,630
[Studente, incomprensibile]

844
01:04:55,630 --> 01:05:00,310
[Bowden] penso che lo fa a Dash - o quale livello di ottimizzazione

845
01:05:00,310 --> 01:05:03,820
è richiesto per una ricorsione tail essere riconosciuto.

846
01:05:03,820 --> 01:05:09,350
Penso che riconosce - GCC e Clang

847
01:05:09,350 --> 01:05:12,610
inoltre hanno significati diversi per i loro livelli di ottimizzazione.

848
01:05:12,610 --> 01:05:17,870
Voglio dire che è Dasho 2, con certezza che riconoscerà ricorsione in coda.

849
01:05:17,870 --> 01:05:27,880
Ma noi - si potrebbe costruire come un esempio Fibonocci o qualcosa del genere.

850
01:05:27,880 --> 01:05:30,030
Non è facile per testare con questo, perché è difficile costruire

851
01:05:30,030 --> 01:05:32,600
un albero binario che è così grande.

852
01:05:32,600 --> 01:05:37,140
Ma sì, penso che sia Dasho 2, che

853
01:05:37,140 --> 01:05:40,580
se si compila con Dasho 2, cercherà ricorsione in coda

854
01:05:40,580 --> 01:05:54,030
e ottimizzare che fuori.

855
01:05:54,030 --> 01:05:58,190
Torniamo a - inserire è letteralmente l'ultima cosa di cui ha bisogno.

856
01:05:58,190 --> 01:06:04,900
Torniamo all'inserto qui

857
01:06:04,900 --> 01:06:07,840
dove stiamo andando a fare la stessa idea.

858
01:06:07,840 --> 01:06:14,340
Sarà ancora il difetto di non essere in grado di gestire tutto

859
01:06:14,340 --> 01:06:17,940
quando la radice stessa è nullo, o la voce passato è null,

860
01:06:17,940 --> 01:06:20,060
ma invece di trattare con un puntatore genitore,

861
01:06:20,060 --> 01:06:27,430
cerchiamo di applicare la stessa logica di puntatori mantenere ai puntatori.

862
01:06:27,430 --> 01:06:35,580
Se qui mantenere il nostro nodo ** corr,

863
01:06:35,580 --> 01:06:37,860
e non abbiamo bisogno di tenere traccia di destra più,

864
01:06:37,860 --> 01:06:47,190
ma il nodo ** corr = & albero.

865
01:06:47,190 --> 01:06:54,800
E ora il nostro ciclo while sarà mentre cur * non nullo uguale.

866
01:06:54,800 --> 01:07:00,270
Non hanno bisogno di tenere traccia dei genitori più.

867
01:07:00,270 --> 01:07:04,180
Non hanno bisogno di tenere traccia di destra e sinistra.

868
01:07:04,180 --> 01:07:10,190
E io lo chiamo temperatura, perché stiamo già utilizzando temp.

869
01:07:10,190 --> 01:07:17,200
Va bene. Quindi, se (valore> * temp),

870
01:07:17,200 --> 01:07:24,010
allora e (* temp) -> a destra

871
01:07:24,010 --> 01:07:29,250
else temp = & (* temp) -> a sinistra.

872
01:07:29,250 --> 01:07:32,730
E ora, a questo punto, dopo questo ciclo while,

873
01:07:32,730 --> 01:07:36,380
Lo faccio solo perché forse è più facile pensare che iterativamente in modo ricorsivo,

874
01:07:36,380 --> 01:07:39,010
ma dopo questo ciclo while,

875
01:07:39,010 --> 01:07:43,820
* Temp è il puntatore che vogliamo cambiare.

876
01:07:43,820 --> 01:07:48,960
>> Prima abbiamo avuto genitori, e abbiamo deciso di cambiare o sinistra genitore o genitore a destra,

877
01:07:48,960 --> 01:07:51,310
ma se vogliamo cambiare proprio genitore,

878
01:07:51,310 --> 01:07:54,550
allora è giusto temperatura * genitore, e possiamo cambiare direttamente.

879
01:07:54,550 --> 01:08:05,860
Così qui, si può fare * temp = newnode, e questo è tutto.

880
01:08:05,860 --> 01:08:09,540
Quindi avviso, tutto quello che è stato fatto in questo estrarre righe di codice.

881
01:08:09,540 --> 01:08:14,770
Al fine di tenere traccia del genitore in tutto ciò che è sforzo supplementare.

882
01:08:14,770 --> 01:08:18,689
Qui, se solo tenere traccia del puntatore al puntatore,

883
01:08:18,689 --> 01:08:22,990
e anche se abbiamo deciso di sbarazzarsi di tutte queste parentesi graffe ora,

884
01:08:22,990 --> 01:08:27,170
farlo sembrare più breve.

885
01:08:27,170 --> 01:08:32,529
Questa è oggi la soluzione esattamente lo stesso,

886
01:08:32,529 --> 01:08:38,210
ma meno righe di codice.

887
01:08:38,210 --> 01:08:41,229
Una volta che si avvia il riconoscimento di questa come una soluzione valida,

888
01:08:41,229 --> 01:08:43,529
è anche più facile ragionare su che come, va bene,

889
01:08:43,529 --> 01:08:45,779
perché ho questa bandiera a destra int?

890
01:08:45,779 --> 01:08:49,290
Che cosa vuol dire? Oh, sta a significare che

891
01:08:49,290 --> 01:08:51,370
ogni volta che vado a destra, ho bisogno di impostare,

892
01:08:51,370 --> 01:08:53,819
altrimenti se vado a sinistra ho bisogno di impostare a zero.

893
01:08:53,819 --> 01:09:04,060
Qui, non c'è bisogno di ragionare su quello, è solo più facile da pensare.

894
01:09:04,060 --> 01:09:06,710
Domande?

895
01:09:06,710 --> 01:09:16,290
[Studente, incomprensibile] >> Si '.

896
01:09:16,290 --> 01:09:23,359
Ok, quindi in ultimo bit -

897
01:09:23,359 --> 01:09:28,080
Credo che una funzione semplice e veloce che possiamo fare è,

898
01:09:28,080 --> 01:09:34,910
let's - insieme, credo, cercare di scrivere una funzione contiene

899
01:09:34,910 --> 01:09:38,899
che non importa se si tratta di un albero binario di ricerca.

900
01:09:38,899 --> 01:09:43,770
Questo contiene la funzione deve restituire true

901
01:09:43,770 --> 01:09:58,330
se da qualche parte in questo albero binario generale è il valore che stiamo cercando.

902
01:09:58,330 --> 01:10:02,520
Quindi, si deve prima fare in modo ricorsivo e poi lo faremo iterativamente.

903
01:10:02,520 --> 01:10:07,300
Possiamo in realtà solo farlo insieme, perché questo sarà davvero breve.

904
01:10:07,300 --> 01:10:11,510
>> Qual è il mio scenario di base sarà?

905
01:10:11,510 --> 01:10:13,890
[Studente, incomprensibile]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Quindi, se (albero == NULL), e poi?

907
01:10:18,230 --> 01:10:22,740
[Studente] Return false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, beh, non ho bisogno del resto.

909
01:10:26,160 --> 01:10:30,250
Se era il mio caso altra base.

910
01:10:30,250 --> 01:10:32,450
Valore [studente] Tree? Sì >>.

911
01:10:32,450 --> 01:10:36,430
Quindi, se (albero-> Valore ==.

912
01:10:36,430 --> 01:10:39,920
Si noti che siamo tornati a * nodo non, nodo ** s?

913
01:10:39,920 --> 01:10:42,990
Contiene non avrà mai bisogno di utilizzare un nodo **,

914
01:10:42,990 --> 01:10:45,480
dal momento che non sta modificando i puntatori.

915
01:10:45,480 --> 01:10:50,540
Stiamo solo loro movimento.

916
01:10:50,540 --> 01:10:53,830
Se ciò accade, allora vogliamo restituire true.

917
01:10:53,830 --> 01:10:58,270
Altrimenti vogliamo attraversare i bambini.

918
01:10:58,270 --> 01:11:02,620
Quindi non possiamo ragionare sul fatto che tutto ciò che a sinistra è meno

919
01:11:02,620 --> 01:11:05,390
e tutto a destra è maggiore.

920
01:11:05,390 --> 01:11:09,590
Così che cosa è la nostra condizione sta per essere qui - o, cosa dobbiamo fare?

921
01:11:09,590 --> 01:11:11,840
[Studente, incomprensibile] >> Si '.

922
01:11:11,840 --> 01:11:17,400
Di ritorno contiene (valore, albero-> sinistra)

923
01:11:17,400 --> 01:11:26,860
o contiene (valore, albero-> destra). E questo è tutto.

924
01:11:26,860 --> 01:11:29,080
E notate c'è qualche corto circuito di valutazione,

925
01:11:29,080 --> 01:11:32,520
dove se capita di trovare il valore nella struttura a sinistra,

926
01:11:32,520 --> 01:11:36,820
non abbiamo mai bisogno di guardare l'albero giusto.

927
01:11:36,820 --> 01:11:40,430
Questa è l'intera funzione.

928
01:11:40,430 --> 01:11:43,690
Ora facciamolo in modo iterativo,

929
01:11:43,690 --> 01:11:48,060
che sta per essere meno bello.

930
01:11:48,060 --> 01:11:54,750
Prendiamo l'inizio abituale di nodo * cur = albero.

931
01:11:54,750 --> 01:12:03,250
Mentre (corr! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rapidamente andare a vedere un problema.

933
01:12:08,600 --> 01:12:12,250
Se cur - qui, se mai uscire da questo,

934
01:12:12,250 --> 01:12:16,020
allora abbiamo a corto di cose da guardare, in modo da tornare false.

935
01:12:16,020 --> 01:12:24,810
Se (corr-> Valore ==), restituisce true.

936
01:12:24,810 --> 01:12:32,910
Così ora, siamo in un luogo -

937
01:12:32,910 --> 01:12:36,250
non sappiamo se si vuole andare a sinistra oa destra.

938
01:12:36,250 --> 01:12:44,590
Così arbitrariamente, facciamo solo andare a sinistra.

939
01:12:44,590 --> 01:12:47,910
Ovviamente ho incontrato un problema in cui ho completamente abbandonato tutto -

940
01:12:47,910 --> 01:12:50,760
Io sempre e solo controllare il lato sinistro di un albero.

941
01:12:50,760 --> 01:12:56,050
Non potrò mai controllare tutto ciò che è un figlio destro di nulla.

942
01:12:56,050 --> 01:13:00,910
Come posso risolvere questo problema?

943
01:13:00,910 --> 01:13:05,260
[Studente] È necessario tenere traccia di sinistra e di destra in una pila.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Si '. Quindi cerchiamo di rendere più

945
01:13:13,710 --> 01:13:32,360
struct lista, nodo * n, e quindi il nodo ** prossimo?

946
01:13:32,360 --> 01:13:40,240
Penso che funziona bene.

947
01:13:40,240 --> 01:13:45,940
Vogliamo andare oltre la sinistra, o let's - qui.

948
01:13:45,940 --> 01:13:54,350
Struct = lista lista, si inizierà

949
01:13:54,350 --> 01:13:58,170
presso questa lista struct.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. In modo che sarà la nostra lista concatenata

951
01:14:04,040 --> 01:14:08,430
di sottostrutture che abbiamo saltato.

952
01:14:08,430 --> 01:14:13,800
Stiamo per attraversare a sinistra ora,

953
01:14:13,800 --> 01:14:17,870
ma dal momento che abbiamo inevitabilmente bisogno di tornare a destra,

954
01:14:17,870 --> 01:14:26,140
Abbiamo intenzione di mantenere il diritto all'interno della nostra lista struct.

955
01:14:26,140 --> 01:14:32,620
Poi avremo new_list o di una struttura,

956
01:14:32,620 --> 01:14:41,080
struct lista *, new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Ho intenzione di ignorare il controllo degli errori, ma si dovrebbe controllare per vedere se è null.

958
01:14:44,920 --> 01:14:50,540
New_list il nodo che sta per puntare a -

959
01:14:50,540 --> 01:14:56,890
oh, è per questo che ho voluto qui. E 'intenzione di puntare a una lista di struct secondo.

960
01:14:56,890 --> 01:15:02,380
Questo è solo il modo collegato lavoro liste.

961
01:15:02,380 --> 01:15:04,810
Questa è la stessa di una lista collegata int

962
01:15:04,810 --> 01:15:06,960
tranne stiamo solo sostituendo int con * nodo.

963
01:15:06,960 --> 01:15:11,040
E 'esattamente lo stesso.

964
01:15:11,040 --> 01:15:15,100
Così new_list, il valore della nostra nodo new_list,

965
01:15:15,100 --> 01:15:19,120
sta per essere cur-> destra.

966
01:15:19,120 --> 01:15:24,280
Il valore della nostra new_list-> prossimo sarà la nostra lista originale,

967
01:15:24,280 --> 01:15:30,760
e poi abbiamo intenzione di aggiornare la nostra lista per puntare a new_list.

968
01:15:30,760 --> 01:15:33,650
>> Ora abbiamo bisogno di una sorta di modo di tirare le cose,

969
01:15:33,650 --> 01:15:37,020
come abbiamo attraversato l'intero sotto-albero di sinistra.

970
01:15:37,020 --> 01:15:40,480
Ora abbiamo bisogno di tirare roba fuori di esso,

971
01:15:40,480 --> 01:15:43,850
come la corrente è nulla, noi non vogliamo tornare semplicemente false.

972
01:15:43,850 --> 01:15:50,370
Vogliamo tirare fuori adesso il nostro nuovo elenco.

973
01:15:50,370 --> 01:15:53,690
Un modo conveniente di fare questo - beh, in realtà, ci sono diversi modi per farlo.

974
01:15:53,690 --> 01:15:56,680
Qualcuno ha un suggerimento?

975
01:15:56,680 --> 01:15:58,790
Dove devo fare questo o come dovrei fare?

976
01:15:58,790 --> 01:16:08,010
Abbiamo solo un paio di minuti, ma qualche suggerimento?

977
01:16:08,010 --> 01:16:14,750
Invece di - un modo, invece di essere durante la nostra condizione,

978
01:16:14,750 --> 01:16:17,090
quello che stiamo attualmente esaminando non è null,

979
01:16:17,090 --> 01:16:22,340
invece abbiamo intenzione di continuare ad andare fino a quando la nostra lista stessa è nullo.

980
01:16:22,340 --> 01:16:25,680
Quindi, se la nostra lista finisce per essere nullo,

981
01:16:25,680 --> 01:16:30,680
allora abbiamo a corto di cose da cercare, per cercare oltre.

982
01:16:30,680 --> 01:16:39,860
Ma questo significa che la prima cosa nella nostra lista è solo andare a essere il primo nodo.

983
01:16:39,860 --> 01:16:49,730
La prima cosa sarà - non abbiamo più bisogno di vedere che.

984
01:16:49,730 --> 01:16:58,710
Così list-> n sarà il nostro albero.

985
01:16:58,710 --> 01:17:02,860
lista-> next sta per essere nullo.

986
01:17:02,860 --> 01:17:07,580
E ora, mentre lista non fa nulla uguale.

987
01:17:07,580 --> 01:17:11,610
Cur sta per tirare qualcosa dalla nostra lista.

988
01:17:11,610 --> 01:17:13,500
Così cur sta per pari list-> n.

989
01:17:13,500 --> 01:17:20,850
E poi lista sta per pari list-> n, o una lista-> next.

990
01:17:20,850 --> 01:17:23,480
Quindi, se il valore corrente è uguale al valore.

991
01:17:23,480 --> 01:17:28,790
Ora possiamo aggiungere sia il nostro puntatore a destra e la nostra sinistra puntatore

992
01:17:28,790 --> 01:17:32,900
fino a quando non sono nulla.

993
01:17:32,900 --> 01:17:36,390
Quaggiù, credo che avrei dovuto farlo, in primo luogo.

994
01:17:36,390 --> 01:17:44,080
Se (corr-> destra! = NULL)

995
01:17:44,080 --> 01:17:56,380
poi abbiamo intenzione di inserire tale nodo al nostro elenco.

996
01:17:56,380 --> 01:17:59,290
Se (corr-> sinistra), questo è un po 'di lavoro in più, ma va bene.

997
01:17:59,290 --> 01:18:02,690
Se (corr-> sinistra! = NULL),

998
01:18:02,690 --> 01:18:14,310
e abbiamo intenzione di inserire la sinistra nella nostra lista concatenata,

999
01:18:14,310 --> 01:18:19,700
e che dovrebbe essere.

1000
01:18:19,700 --> 01:18:22,670
Noi iterare - fintanto che qualcosa nella nostra lista,

1001
01:18:22,670 --> 01:18:26,640
abbiamo un altro nodo da guardare.

1002
01:18:26,640 --> 01:18:28,920
Quindi guardiamo a quel nodo,

1003
01:18:28,920 --> 01:18:31,390
avanziamo la nostra lista a quello successivo.

1004
01:18:31,390 --> 01:18:34,060
Se questo nodo è il valore che stiamo cercando, siamo in grado di restituire true.

1005
01:18:34,060 --> 01:18:37,640
Altrimenti inserire entrambi i nostri sottoalberi sinistro e destro,

1006
01:18:37,640 --> 01:18:40,510
fino a quando non sono nulla, nella nostra lista

1007
01:18:40,510 --> 01:18:43,120
in modo che inevitabilmente andare su di loro.

1008
01:18:43,120 --> 01:18:45,160
Quindi, se non erano nulla,

1009
01:18:45,160 --> 01:18:47,950
se il nostro puntatore radice ha evidenziato due cose,

1010
01:18:47,950 --> 01:18:51,670
poi in un primo momento abbiamo tirato fuori qualcosa così la nostra lista finisce per essere null.

1011
01:18:51,670 --> 01:18:56,890
E poi abbiamo messo due le cose, in modo ora la nostra lista è di dimensione 2.

1012
01:18:56,890 --> 01:19:00,030
Poi andremo a filo dietro e stiamo solo andando a tirare,

1013
01:19:00,030 --> 01:19:04,250
diciamo, il puntatore del mouse a sinistra del nostro nodo principale.

1014
01:19:04,250 --> 01:19:07,730
E che ti basta tenere accadendo; finiremo loop su tutto.

1015
01:19:07,730 --> 01:19:11,280
>> Si noti che questo era significativamente più complicato

1016
01:19:11,280 --> 01:19:14,160
nella soluzione ricorsiva.

1017
01:19:14,160 --> 01:19:17,260
E ho detto più volte

1018
01:19:17,260 --> 01:19:25,120
che la soluzione ricorsiva di solito ha molto in comune con la soluzione iterativa.

1019
01:19:25,120 --> 01:19:30,820
Ecco questo è esattamente ciò che la soluzione ricorsiva sta facendo.

1020
01:19:30,820 --> 01:19:36,740
L'unica modifica è che invece di implicitamente utilizzando lo stack, stack di programma,

1021
01:19:36,740 --> 01:19:40,840
come il tuo modo di tenere traccia di quello che i nodi che ancora bisogno di visitare,

1022
01:19:40,840 --> 01:19:45,430
ora è necessario utilizzare in modo esplicito una lista concatenata.

1023
01:19:45,430 --> 01:19:49,070
In entrambi i casi si sta tenendo traccia di quale nodo ha ancora bisogno di essere visitato.

1024
01:19:49,070 --> 01:19:51,790
Nel caso ricorsivo è solo più facile perché una pila

1025
01:19:51,790 --> 01:19:57,100
viene implementato per voi come lo stack del programma.

1026
01:19:57,100 --> 01:19:59,550
Si noti che questo elenco collegato, è uno stack.

1027
01:19:59,550 --> 01:20:01,580
Qualunque cosa abbiamo appena messo in pila

1028
01:20:01,580 --> 01:20:09,960
è immediatamente quello che stiamo andando a tirare fuori la pila per visitare successivo.

1029
01:20:09,960 --> 01:20:14,380
Siamo fuori tempo, ma tutte le domande?

1030
01:20:14,380 --> 01:20:23,530
[Studente, incomprensibile]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Si '. Quindi, se abbiamo la nostra lista concatenata,

1032
01:20:27,790 --> 01:20:30,150
corrente sta per puntare a questo ragazzo,

1033
01:20:30,150 --> 01:20:34,690
e ora stiamo solo l'approfondimento delle lista collegata a concentrarsi su questo ragazzo.

1034
01:20:34,690 --> 01:20:44,200
Stiamo attraversando sulla lista concatenata in quella linea.

1035
01:20:44,200 --> 01:20:51,200
E poi credo che dovremmo liberare la nostra lista concatenata e roba

1036
01:20:51,200 --> 01:20:53,880
una volta prima di ritornare vero o falso, abbiamo bisogno di

1037
01:20:53,880 --> 01:20:57,360
scorrere la nostra lista collegata e sempre qui, credo,

1038
01:20:57,360 --> 01:21:03,900
se corr diritto non è uguale a, aggiungere, quindi ora vogliamo liberare

1039
01:21:03,900 --> 01:21:09,600
corr perché, beh, abbiamo fatto completamente dimenticare la lista? Gia '.

1040
01:21:09,600 --> 01:21:12,880
Ecco, questo è quello che vogliamo fare qui.

1041
01:21:12,880 --> 01:21:16,730
Dov'e 'il puntatore?

1042
01:21:16,730 --> 01:21:23,320
Cur era allora - vogliamo una lista struct * 10 pari elenco successivo.

1043
01:21:23,320 --> 01:21:29,240
Elenco gratuito, elenco = temp.

1044
01:21:29,240 --> 01:21:32,820
E nel caso in cui si ritorna vero, abbiamo bisogno di iterare

1045
01:21:32,820 --> 01:21:37,050
per il resto della nostra lista concatenata liberando le cose.

1046
01:21:37,050 --> 01:21:39,700
La cosa bella la soluzione ricorsiva è liberare le cose

1047
01:21:39,700 --> 01:21:44,930
significa solo factorings popping dalla pila che avverrà per voi.

1048
01:21:44,930 --> 01:21:50,720
Così siamo passati da qualcosa che è come 3 linee di hard-to-think-sul codice

1049
01:21:50,720 --> 01:21:57,520
a qualcosa che è molto più difficile da molti-pensare-di righe di codice.

1050
01:21:57,520 --> 01:22:00,620
Altre domande?

1051
01:22:00,620 --> 01:22:08,760
Bene. Siamo a posto. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]