1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Secció 7: més còmode]

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

3
00:00:05,090 --> 00:00:07,930
[Aquesta és CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Està bé. Així que, com vaig dir en el meu correu electrònic,

5
00:00:10,110 --> 00:00:14,060
això serà una secció de l'arbre binari d'obra.

6
00:00:14,060 --> 00:00:16,820
Però no cal moltes preguntes.

7
00:00:16,820 --> 00:00:18,920
Així que anem a tractar de treure cada pregunta

8
00:00:18,920 --> 00:00:25,430
i entrar en detalls dolorosos de les millors maneres de fer les coses.

9
00:00:25,430 --> 00:00:31,200
Així que des del principi, anem a través dels dibuixos de la mostra d'arbres binaris i aquestes coses.

10
00:00:31,200 --> 00:00:35,970
Així que aquí, "Recorda que un arbre binari té nodes similars als d'una llista enllaçada,

11
00:00:35,970 --> 00:00:38,150
però en lloc d'un punter hi ha dos: un per "nen" a l'esquerra

12
00:00:38,150 --> 00:00:41,950
i un altre per la dreta "nen". "

13
00:00:41,950 --> 00:00:45,630
Així que un arbre binari és igual que una llista enllaçada,

14
00:00:45,630 --> 00:00:47,910
excepte l'estructura tindrà dos punters.

15
00:00:47,910 --> 00:00:51,390
Hi ha arbres trinaris, que van a tenir tres punters,

16
00:00:51,390 --> 00:00:56,540
hi ha N-àries arbres, que només tenen un punter genèric

17
00:00:56,540 --> 00:01:00,320
que vostè llavors ha de malloc ser prou gran per tenir

18
00:01:00,320 --> 00:01:04,840
indicadors suficients per a tots els nens possibles.

19
00:01:04,840 --> 00:01:08,200
Així arbre binari només passa a tenir un nombre constant de dues.

20
00:01:08,200 --> 00:01:11,260
Si ho desitja, pot donar una llista enllaçada com un arbre unari,

21
00:01:11,260 --> 00:01:15,360
però jo no crec que ningú ho crida això.

22
00:01:15,360 --> 00:01:18,060
"Dibuixar un diagrama de caixes i fletxes d'un node de l'arbre binari

23
00:01:18,060 --> 00:01:24,110
que conté el nombre preferit de Nate, 7, on cada punter nen és nul. "

24
00:01:24,110 --> 00:01:27,780
Així que la manera d'iPad.

25
00:01:27,780 --> 00:01:30,280
>> Serà bastant senzill.

26
00:01:30,280 --> 00:01:36,150
Només tindrem un node, ho vaig a dibuixar un quadrat.

27
00:01:36,150 --> 00:01:38,730
I vaig a treure els valors d'aquí.

28
00:01:38,730 --> 00:01:41,090
Així, el valor passarà d'aquí,

29
00:01:41,090 --> 00:01:44,770
i llavors aquí tindrem el punter a l'esquerra de l'esquerra i el punter a la dreta a la dreta.

30
00:01:44,770 --> 00:01:50,430
I és molt el que la convenció de cridar a l'esquerra i la dreta, els noms de punter.

31
00:01:50,430 --> 00:01:52,460
Tots dos seran nul.

32
00:01:52,460 --> 00:01:57,870
Això només serà nul, i que només serà nul.

33
00:01:57,870 --> 00:02:03,630
Bé. Així que de tornada a aquí.

34
00:02:03,630 --> 00:02:05,700
"Amb una llista enllaçada, només havíem de emmagatzemar un punter

35
00:02:05,700 --> 00:02:09,639
al primer node de la llista per recordar tota la llista vinculada, o tota la llista.

36
00:02:09,639 --> 00:02:11,650
De la mateixa manera, amb els arbres, només ha d'emmagatzemar un punter

37
00:02:11,650 --> 00:02:13,420
a un únic node amb la finalitat de recordar a tot l'arbre.

38
00:02:13,420 --> 00:02:15,980
Aquest node és el carrer "arrel" de l'arbre.

39
00:02:15,980 --> 00:02:18,320
Basar-se en el diagrama d'abans o dibuixar un de nou

40
00:02:18,320 --> 00:02:21,690
de manera que té una representació caixes i fletxes d'un arbre binari

41
00:02:21,690 --> 00:02:25,730
amb el valor de 7, a continuació, 3 a l'esquerra,

42
00:02:25,730 --> 00:02:32,760
a continuació, 9 a la dreta, i després 6 a la dreta de la 3. "

43
00:02:32,760 --> 00:02:34,810
A veure si puc recordar tot això en el meu cap.

44
00:02:34,810 --> 00:02:37,670
Així que això serà la nostra arrel fins aquí.

45
00:02:37,670 --> 00:02:41,600
Tindrem una mica de punter en algun lloc, alguna cosa que anomenarem arrel,

46
00:02:41,600 --> 00:02:45,140
i que apunta a aquest tipus.

47
00:02:45,140 --> 00:02:48,490
Ara per fer un nou node,

48
00:02:48,490 --> 00:02:52,870
¿Què és el que tenim, 3 a l'esquerra?

49
00:02:52,870 --> 00:02:57,140
Així que un nou node amb 3, i que assenyala inicialment nul.

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

51
00:02:59,190 --> 00:03:02,250
Ara volem fer que anar a l'esquerra 7.

52
00:03:02,250 --> 00:03:06,840
Així que canviem aquest punter per apuntar ara a aquest tipus.

53
00:03:06,840 --> 00:03:12,420
I fem el mateix. Volem un 9 per aquí

54
00:03:12,420 --> 00:03:14,620
que al principi només diu nul.

55
00:03:14,620 --> 00:03:19,600
Anem a canviar aquest punter, assenyali a 9,

56
00:03:19,600 --> 00:03:23,310
i ara volem posar 6 a la dreta de 3.

57
00:03:23,310 --> 00:03:32,170
Així que va a - fer un 6.

58
00:03:32,170 --> 00:03:34,310
I aquest noi va a apuntar allà.

59
00:03:34,310 --> 00:03:38,320
Bé. Així que això és tot el que se'ns demana que fem.

60
00:03:38,320 --> 00:03:42,770
>> Ara anem a repassar alguns termes.

61
00:03:42,770 --> 00:03:46,690
Ja hem parlat de com l'arrel de l'arbre és el node de més amunt en l'arbre.

62
00:03:46,690 --> 00:03:54,720
L'un que conté 7. Els nodes en la part inferior de l'arbre es diuen les fulles.

63
00:03:54,720 --> 00:04:01,240
Qualsevol node que només té nul com els seus fills és un full.

64
00:04:01,240 --> 00:04:03,680
Així és possible, si el nostre arbre binari és només un únic node,

65
00:04:03,680 --> 00:04:10,130
que un arbre és un full, i això és tot.

66
00:04:10,130 --> 00:04:12,060
"El 'height' l'arbre és el nombre de salts que ha de fer

67
00:04:12,060 --> 00:04:16,620
per arribar des de la part superior a un full. "

68
00:04:16,620 --> 00:04:18,640
Entrarem, en un segon, la diferència

69
00:04:18,640 --> 00:04:21,940
entre els arbres binaris balancejats i no balancejats,

70
00:04:21,940 --> 00:04:29,470
però per ara, l'altura total d'aquest arbre

71
00:04:29,470 --> 00:04:34,520
Jo diria que és 3, encara que si es compta el nombre de salts

72
00:04:34,520 --> 00:04:39,710
el que has de fer per arribar a 9, llavors és realment només una alçada de 2.

73
00:04:39,710 --> 00:04:43,340
En aquest moment es tracta d'un arbre binari desequilibrat,

74
00:04:43,340 --> 00:04:49,840
però anem a parlar sobre equilibrat quan arriba negatiu.

75
00:04:49,840 --> 00:04:52,040
Així que ara podem parlar dels nodes d'un arbre en termes

76
00:04:52,040 --> 00:04:54,700
pel que fa als altres nodes en l'arbre.

77
00:04:54,700 --> 00:04:59,730
Així que ara tenim pares, fills, germans, ascendents i descendents.

78
00:04:59,730 --> 00:05:05,650
Són bastant sentit comú, el que signifiquen.

79
00:05:05,650 --> 00:05:09,610
Si ens preguntem - són els pares.

80
00:05:09,610 --> 00:05:12,830
Llavors, què és el pare de 3?

81
00:05:12,830 --> 00:05:16,090
[Els estudiants] 7. Sí >>. El pare és només serà el assenyala a vostè.

82
00:05:16,090 --> 00:05:20,510
Llavors, què són els nens de 7?

83
00:05:20,510 --> 00:05:23,860
[Els estudiants] 3 i 9. Sí >>.

84
00:05:23,860 --> 00:05:26,460
Tingueu en compte que els "nens" significa literalment fills,

85
00:05:26,460 --> 00:05:31,010
així que 6 no s'aplicaria, perquè és com un nét.

86
00:05:31,010 --> 00:05:35,540
Però si anem descendents, així que el que són els descendents de 7?

87
00:05:35,540 --> 00:05:37,500
[Els estudiants] 3, 6 i 9. Sí >>.

88
00:05:37,500 --> 00:05:42,330
Els descendents del node arrel serà tot en l'arbre,

89
00:05:42,330 --> 00:05:47,950
excepte potser el node arrel en si, si no vols tenir en compte que un descendent.

90
00:05:47,950 --> 00:05:50,750
I finalment, els ancestres, pel que és la direcció oposada.

91
00:05:50,750 --> 00:05:55,740
Quins són els avantpassats de 6?

92
00:05:55,740 --> 00:05:58,920
[Els estudiants] 3 i 7. Sí >>. 9 no està inclòs.

93
00:05:58,920 --> 00:06:02,520
És només la part de darrere llinatge directe a l'arrel

94
00:06:02,520 --> 00:06:13,230
Serà seus avantpassats.

95
00:06:13,230 --> 00:06:16,300
>> "Diem que un arbre binari és" ordenat "si per a cada node a l'arbre,

96
00:06:16,300 --> 00:06:19,530
tots els seus descendents de l'esquerra tenen valors menors

97
00:06:19,530 --> 00:06:22,890
i tots els de la dreta tenen valors majors.

98
00:06:22,890 --> 00:06:27,060
Per exemple, l'arbre de dalt està ordenat, però no és l'única possible ordenat ".

99
00:06:27,060 --> 00:06:30,180
Abans d'arribar a això,

100
00:06:30,180 --> 00:06:36,420
un arbre binari ordenat també es coneix com un arbre binari de cerca.

101
00:06:36,420 --> 00:06:38,660
Aquí succeeix que se'n diu un arbre binari ordenat,

102
00:06:38,660 --> 00:06:41,850
però mai he sentit anomenar un arbre binari ordenat abans,

103
00:06:41,850 --> 00:06:46,650
i en una prova que són molt més propensos a posar arbre de cerca binària.

104
00:06:46,650 --> 00:06:49,250
Són un i el mateix,

105
00:06:49,250 --> 00:06:54,580
i és important que vostè reconegui la distinció entre arbre i arbre binari de cerca binària.

106
00:06:54,580 --> 00:06:58,830
Un arbre binari és un arbre que apunta a dues coses.

107
00:06:58,830 --> 00:07:02,120
Cada node apunta dues coses.

108
00:07:02,120 --> 00:07:06,310
No hi ha raonament sobre els valors que s'apunta.

109
00:07:06,310 --> 00:07:11,370
Així com aquí, ja que és un arbre de cerca binària,

110
00:07:11,370 --> 00:07:14,030
sabem que si anem a l'esquerra de 7,

111
00:07:14,030 --> 00:07:16,670
llavors tots els valors que ens sigui possible assolir

112
00:07:16,670 --> 00:07:19,310
anant a l'esquerra de 7 ha de ser menor que 7.

113
00:07:19,310 --> 00:07:24,070
Tingueu en compte que tots els valors menys que 7 són 3 i 6.

114
00:07:24,070 --> 00:07:26,040
Aquests són tots a l'esquerra de 7.

115
00:07:26,040 --> 00:07:29,020
Si ens anem a la dreta de 7, tot ha de ser superior a 7,

116
00:07:29,020 --> 00:07:33,220
9 és tan a la dreta de 7, així que estem bé.

117
00:07:33,220 --> 00:07:36,150
Aquest no és el cas d'un arbre binari,

118
00:07:36,150 --> 00:07:40,020
per a un arbre binari regular que es pot tenir en la part superior 3, 7 a l'esquerra,

119
00:07:40,020 --> 00:07:47,630
9 a l'esquerra de 7, no hi ha ordre de valors qualssevol.

120
00:07:47,630 --> 00:07:56,140
Ara, no farem això perquè és tediós i innecessari,

121
00:07:56,140 --> 00:07:59,400
sinó "intentar extreure arbres ordenats com molts com vostè pot pensar en

122
00:07:59,400 --> 00:08:01,900
usant els números 7, 3, 9, i 6.

123
00:08:01,900 --> 00:08:06,800
Quants arranjaments diferents hi ha? Quina és l'altura de cada un? "

124
00:08:06,800 --> 00:08:10,480
>> Farem una parella, però és la idea principal,

125
00:08:10,480 --> 00:08:16,530
això no és de cap manera una representació única d'un arbre binari que conté aquests valors.

126
00:08:16,530 --> 00:08:22,760
Tot el que necessitem és un arbre binari que conté 7, 3, 6 i 9.

127
00:08:22,760 --> 00:08:25,960
Una altra possibilitat seria vàlida l'arrel és 3,

128
00:08:25,960 --> 00:08:30,260
anar a l'esquerra i és 6, aneu a l'esquerra i és 7,

129
00:08:30,260 --> 00:08:32,730
anar a l'esquerra i és 9.

130
00:08:32,730 --> 00:08:36,169
Que és un arbre binari de recerca perfectament vàlid.

131
00:08:36,169 --> 00:08:39,570
No és molt útil, ja que és com una llista enllaçada

132
00:08:39,570 --> 00:08:43,750
i tots aquests punters són null.

133
00:08:43,750 --> 00:08:48,900
Però és un arbre vàlida. Sí?

134
00:08:48,900 --> 00:08:51,310
[Estudiant] És que els valors han de ser majors de la dreta?

135
00:08:51,310 --> 00:08:56,700
O és això -? Aquests >> vaig voler anar a un altre costat.

136
00:08:56,700 --> 00:09:00,960
Hi ha també - si, canviarem això.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Bona captura.

138
00:09:07,770 --> 00:09:11,730
Encara ha d'obeir el que és un arbre de cerca binària se suposa que ha de fer.

139
00:09:11,730 --> 00:09:15,650
Així tot a l'esquerra ha de ser menor que qualsevol node donat.

140
00:09:15,650 --> 00:09:23,180
Només podia moure, per exemple, el 6 i el va posar aquí.

141
00:09:23,180 --> 00:09:26,880
No, no podem. Per què segueixo fent això?

142
00:09:26,880 --> 00:09:35,350
Anem a fer-ho - aquí és 6, aquí és 7, 6 punts a 3.

143
00:09:35,350 --> 00:09:39,290
Això segueix sent un arbre binari de recerca vàlida.

144
00:09:39,290 --> 00:09:49,260
Què passa si jo - anem a veure si puc arribar a un acord.

145
00:09:49,260 --> 00:09:52,280
Sí, està bé. Llavors, què està malament amb aquest arbre?

146
00:09:52,280 --> 00:10:08,920
Suposo que ja t'he donat un indici que hi ha una cosa dolenta en això.

147
00:10:08,920 --> 00:10:14,430
Per què segueixo fent això?

148
00:10:14,430 --> 00:10:18,510
Bé. Això sembla raonable.

149
00:10:18,510 --> 00:10:22,590
Si ens fixem en cada node, com 7, després a l'esquerra de 7 és un 3.

150
00:10:22,590 --> 00:10:24,960
Així que tenim 3, la cosa a la dreta de 3 és un 6.

151
00:10:24,960 --> 00:10:27,750
I si mires als 6, la cosa a la dreta de 6 és un 9.

152
00:10:27,750 --> 00:10:30,910
Per què no és aquest un arbre binari de cerca vàlid?

153
00:10:30,910 --> 00:10:36,330
[Els estudiants] 9 és encara a l'esquerra de 7. Sí >>.

154
00:10:36,330 --> 00:10:43,710
Ha de ser cert que tots els valors que possiblement pot arribar per anar a l'esquerra de 7 són menys de 7.

155
00:10:43,710 --> 00:10:49,120
Si es va a l'esquerra, de 7, s'arriba a 3 i encara podem arribar a 6,

156
00:10:49,120 --> 00:10:52,520
encara podem arribar a 9, però per haver passat menys de 7,

157
00:10:52,520 --> 00:10:55,070
no cal ser capaç d'arribar a un nombre que és més gran que 7.

158
00:10:55,070 --> 00:10:59,830
Així que això no és un arbre binari de recerca vàlida.

159
00:10:59,830 --> 00:11:02,330
>> El meu germà tenia realment una pregunta de l'entrevista

160
00:11:02,330 --> 00:11:07,760
que era bàsicament això, només una mica de codi per validar

161
00:11:07,760 --> 00:11:10,500
si un arbre és un arbre de cerca binària,

162
00:11:10,500 --> 00:11:13,580
i així que el primer que va fer va ser simplement comprovi

163
00:11:13,580 --> 00:11:17,020
si l'esquerra i la dreta són correctes, i després iterar per allà.

164
00:11:17,020 --> 00:11:19,700
Però no es pot fer això, cal seguir la pista

165
00:11:19,700 --> 00:11:22,550
el fet que ara que m'he anat a l'esquerra de 7,

166
00:11:22,550 --> 00:11:26,340
tot en aquest subarbre ha de ser menor que 7.

167
00:11:26,340 --> 00:11:28,430
L'algorisme correcte necessita seguir la pista

168
00:11:28,430 --> 00:11:35,970
dels límits dels valors que possiblement poden caure polz

169
00:11:35,970 --> 00:11:38,360
No anirem a través de tots ells.

170
00:11:38,360 --> 00:11:41,630
Hi ha una relació de recurrència agradable,

171
00:11:41,630 --> 00:11:44,810
encara que no hem arribat a ells, o no arribarem a ells,

172
00:11:44,810 --> 00:11:47,030
definir quants són en realitat.

173
00:11:47,030 --> 00:11:53,180
Així que hi ha 14 d'ells.

174
00:11:53,180 --> 00:11:56,020
La idea de la manera com ho faria matemàticament és com,

175
00:11:56,020 --> 00:11:59,770
vostè pot escollir un de sol per ser el node arrel,

176
00:11:59,770 --> 00:12:03,160
i llavors si prenc 7 a ser el node arrel,

177
00:12:03,160 --> 00:12:08,150
després hi, per exemple, alguns números que poden anar a ser el meu node esquerre,

178
00:12:08,150 --> 00:12:10,440
i hi ha alguns números que poden ser el meu node de la dreta,

179
00:12:10,440 --> 00:12:15,090
però si té n xifres totals, la quantitat que pot anar a l'esquerra

180
00:12:15,090 --> 00:12:18,820
més la quantitat que pot anar a la dreta és n - 1.

181
00:12:18,820 --> 00:12:26,130
Així dels nombres restants, han de ser capaços d'anar cap a l'esquerra o la dreta.

182
00:12:26,130 --> 00:12:31,580
Sembla difícil que, si poso 3 primer i després tot el que ha d'anar a l'esquerra,

183
00:12:31,580 --> 00:12:35,080
però si poso 7, a continuació, algunes coses poden anar a l'esquerra i algunes coses poden anar a la dreta.

184
00:12:35,080 --> 00:12:39,570
I per '3 'primer que vaig voler dir tot pot anar a la dreta.

185
00:12:39,570 --> 00:12:42,350
En realitat, només cal pensar-hi com,

186
00:12:42,350 --> 00:12:47,980
quantes coses poden passar al següent nivell de l'arbre.

187
00:12:47,980 --> 00:12:50,420
I ve a ser 14, o pot dibuixar tots ells,

188
00:12:50,420 --> 00:12:54,650
i llavors vostè aconseguirà 14.

189
00:12:54,650 --> 00:13:01,120
>> Tornant aquí,

190
00:13:01,120 --> 00:13:03,510
"Va ordenar arbres binaris són frescos ja que podem buscar a través d'ells

191
00:13:03,510 --> 00:13:06,910
d'una manera molt similar a la recerca a través d'una matriu ordenada.

192
00:13:06,910 --> 00:13:10,120
Per això, partim de l'arrel i anem per l'arbre

193
00:13:10,120 --> 00:13:13,440
cap a les fulles, comprovant els valors de cada node amb els valors que estem buscant.

194
00:13:13,440 --> 00:13:15,810
Si el valor del node actual és menor que el valor que busquem,

195
00:13:15,810 --> 00:13:18,050
acostar-te a fill dret del node.

196
00:13:18,050 --> 00:13:20,030
En cas contrari, aneu al fill esquerre del node.

197
00:13:20,030 --> 00:13:22,800
En algun moment, trobareu el valor que vostè està buscant, o et trobaràs amb un valor nul,

198
00:13:22,800 --> 00:13:28,520
el que indica que el valor no està en l'arbre. "

199
00:13:28,520 --> 00:13:32,450
He de tornar a dibuixar l'arbre que teníem abans, que prendrà un segon.

200
00:13:32,450 --> 00:13:38,280
Però volem mirar cap amunt si 6, 10 i 1 estan en l'arbre.

201
00:13:38,280 --> 00:13:49,180
Així que el que era, 7, 9, 3, 6. Bé.

202
00:13:49,180 --> 00:13:52,730
Els números que voleu cercar, volem mirar cap amunt 6.

203
00:13:52,730 --> 00:13:55,440
Com funciona aquest algorisme?

204
00:13:55,440 --> 00:14:03,040
Bé, també tenim alguns punter arrel del nostre arbre.

205
00:14:03,040 --> 00:14:12,460
I ens tornaríem a anar a l'arrel i dir, aquest valor és igual al valor que estem buscant?

206
00:14:12,460 --> 00:14:15,000
Així que estem buscant per a 6, així que no és igual.

207
00:14:15,000 --> 00:14:20,140
Per tant, seguir endavant, i ara es diu, està bé, així que 6 és menor que 7.

208
00:14:20,140 --> 00:14:23,940
Significa això que volem anar cap a l'esquerra, o volem anar a la dreta?

209
00:14:23,940 --> 00:14:27,340
[Estudiant] Esquerra. Sí >>.

210
00:14:27,340 --> 00:14:33,340
És molt més fàcil, l'únic que has de fer és treure un node de l'arbre és possible

211
00:14:33,340 --> 00:14:37,760
i llavors no - en lloc de tractar de pensar en el teu cap,

212
00:14:37,760 --> 00:14:40,020
bé, si és menys, he d'anar a l'esquerra o anar a la dreta,

213
00:14:40,020 --> 00:14:43,030
només mirar aquesta imatge, és molt clar que he d'anar a l'esquerra

214
00:14:43,030 --> 00:14:47,700
si aquest node és major que el valor que jo estic buscant.

215
00:14:47,700 --> 00:14:52,600
Així que anar a l'esquerra, ara estic en 3.

216
00:14:52,600 --> 00:14:57,770
Vull - 3 és menor que el valor que estic buscant, que és de 6.

217
00:14:57,770 --> 00:15:03,420
Així que ens anem a la dreta, i ara acabo a les 6,

218
00:15:03,420 --> 00:15:07,380
que és el valor que estic buscant, així que em torni true.

219
00:15:07,380 --> 00:15:15,760
El següent valor que vaig a buscar és 10.

220
00:15:15,760 --> 00:15:23,230
Bé. Així que 10, ara, va a - tallar això - seguirà l'arrel.

221
00:15:23,230 --> 00:15:27,670
Ara, el 10 serà superior a 7, així que vull mirar a la dreta.

222
00:15:27,670 --> 00:15:31,660
Vaig a venir per aquí, 10 serà més gran que 9,

223
00:15:31,660 --> 00:15:34,520
així que vaig a voler mirar a la dreta.

224
00:15:34,520 --> 00:15:42,100
Jo vinc per aquí, però aquí ara estic a null.

225
00:15:42,100 --> 00:15:44,170
Què faig si em va colpejar nul?

226
00:15:44,170 --> 00:15:47,440
[Estudiant] Tornar fals? Sí >>. No vaig trobar 10.

227
00:15:47,440 --> 00:15:49,800
1 va a ser un cas gairebé idèntic,

228
00:15:49,800 --> 00:15:51,950
excepte que només donarà la volta, en lloc de buscar

229
00:15:51,950 --> 00:15:56,540
pel costat dret, vaig a mirar cap avall al 'esquerra.

230
00:15:56,540 --> 00:16:00,430
>> Ara crec que en realitat obtenir el codi.

231
00:16:00,430 --> 00:16:04,070
Aquí és on - obrir l'aparell CS50 i navegar pel seu camí,

232
00:16:04,070 --> 00:16:07,010
però vostè pot també fer-ho en l'espai.

233
00:16:07,010 --> 00:16:09,170
És probable que sigui ideal per fer-ho en l'espai,

234
00:16:09,170 --> 00:16:13,760
perquè podem treballar en l'espai.

235
00:16:13,760 --> 00:16:19,170
"Primer anem a necessitar una definició de tipus nou per a un node de l'arbre binari que conté valors int.

236
00:16:19,170 --> 00:16:21,400
Usant la repetitiva typedef continuació,

237
00:16:21,400 --> 00:16:24,510
crear una definició de nou tipus per a un node en un arbre binari.

238
00:16:24,510 --> 00:16:27,930
Si et quedes encallat. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
Així que anem a posar aquí el text model,

240
00:16:30,380 --> 00:16:41,630
typedef struct node i node. Sí, està bé.

241
00:16:41,630 --> 00:16:44,270
Llavors, què són els camps que anem a voler al nostre node?

242
00:16:44,270 --> 00:16:46,520
[Estudiant] Int i després dos punters?

243
00:16:46,520 --> 00:16:49,700
Int >> valor, dos punters? Com puc escriure els punters?

244
00:16:49,700 --> 00:16:58,440
[Estudiant] struct. >> Em zoom in Sí, així struct node * a l'esquerra,

245
00:16:58,440 --> 00:17:01,320
i struct node * dreta.

246
00:17:01,320 --> 00:17:03,460
I recorda que el debat de l'última vegada,

247
00:17:03,460 --> 00:17:15,290
que això no té sentit, això no té sentit,

248
00:17:15,290 --> 00:17:18,270
això no té sentit.

249
00:17:18,270 --> 00:17:25,000
Necessites tot el que hi ha per definir aquesta estructura recursiva.

250
00:17:25,000 --> 00:17:27,970
Molt bé, així que això és el que el nostre arbre semblarà.

251
00:17:27,970 --> 00:17:37,670
Si féssim un arbre ternari, a continuació, un node pot ser com b1, b2, b3 struct node *,

252
00:17:37,670 --> 00:17:43,470
on b és una branca - en realitat, he sentit més a l'esquerra, centre, dreta, però el que sigui.

253
00:17:43,470 --> 00:17:55,610
Només ens importa binari, per dreta, esquerra.

254
00:17:55,610 --> 00:17:59,110
"Ara declarem una variable global per al node * l'arrel de l'arbre."

255
00:17:59,110 --> 00:18:01,510
Així que no farem això.

256
00:18:01,510 --> 00:18:08,950
Per fer les coses una mica més difícil i més generalitzada,

257
00:18:08,950 --> 00:18:11,570
no tindrem una variable de node global.

258
00:18:11,570 --> 00:18:16,710
En canvi, en principal per la qual ens declararà totes les nostres coses de nodes,

259
00:18:16,710 --> 00:18:20,500
i això vol dir que més endavant, quan vam començar a córrer

260
00:18:20,500 --> 00:18:23,130
nostra funció contains i la nostra funció d'inserció,

261
00:18:23,130 --> 00:18:27,410
en lloc de les nostres conté la funció de només utilitzar aquesta variable node global,

262
00:18:27,410 --> 00:18:34,280
haurem de prendre com a argument l'arbre que volem que siguin processats.

263
00:18:34,280 --> 00:18:36,650
Tenir la variable global es suposa que fa les coses més fàcils.

264
00:18:36,650 --> 00:18:42,310
Farem les coses més difícils.

265
00:18:42,310 --> 00:18:51,210
Ara prengui un minut per només fer aquest tipus de coses,

266
00:18:51,210 --> 00:18:57,690
on dins de la principal que voleu crear aquest arbre, i això és tot el que vull fer.

267
00:18:57,690 --> 00:19:04,530
Intenta construir aquest arbre en la seva funció principal.

268
00:19:42,760 --> 00:19:47,610
>> Bé. Així que no tenen ni tan sols haver construït l'arbre durant tot el camí encara.

269
00:19:47,610 --> 00:19:49,840
Però algú té alguna cosa que pogués aixecar

270
00:19:49,840 --> 00:20:03,130
per mostrar com es pot començar a construir un arbre?

271
00:20:03,130 --> 00:20:08,080
[Estudiant] Algú està colpejant, tractant de sortir.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Qualsevol persona còmodes amb la seva construcció de l'arbre?

273
00:20:13,100 --> 00:20:15,520
[Estudiant] Clar. No es fa. >> Està bé. Només podem acabar -

274
00:20:15,520 --> 00:20:26,860
oh, podeu estalviar? Visca.

275
00:20:26,860 --> 00:20:32,020
Així que aquí tenim - oh, estic una mica tallat.

276
00:20:32,020 --> 00:20:34,770
Estic zoom?

277
00:20:34,770 --> 00:20:37,730
Zoom cap a dins, desplaceu-vos cap a fora. >> Tinc una pregunta. >> Sí?

278
00:20:37,730 --> 00:20:44,410
[Estudiant] Quan es defineix una estructura, són coses com inicialitzat a alguna cosa?

279
00:20:44,410 --> 00:20:47,160
[Bowden] >> No Està bé. Així que hauria de inicialitzar -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Quan es defineix, o quan es declara una struct,

281
00:20:50,450 --> 00:20:55,600
no s'inicialitza per defecte, és com si es declara un int.

282
00:20:55,600 --> 00:20:59,020
És exactament el mateix. És com si cada un dels seus camps individuals

283
00:20:59,020 --> 00:21:04,460
pot tenir un valor escombraries-hi. >> I és possible definir - o declarar una estructura

284
00:21:04,460 --> 00:21:07,740
d'una manera que ho fa inicialitzar ells?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Sí Per tant, l'accés directe sintaxi d'inicialització

286
00:21:13,200 --> 00:21:18,660
es veurà com -

287
00:21:18,660 --> 00:21:22,200
Hi ha dues formes en que podem fer això. Crec que hem de compilar

288
00:21:22,200 --> 00:21:25,840
per fer Clang segur també ho fa.

289
00:21:25,840 --> 00:21:28,510
L'ordre dels arguments que ve en l'estructura,

290
00:21:28,510 --> 00:21:32,170
vostè posa l'ordre dels arguments dins d'aquestes claus.

291
00:21:32,170 --> 00:21:35,690
Així que si vol inicialitzar a 9 i es queda nul i després a la dreta ser nul,

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

293
00:21:41,570 --> 00:21:47,890
L'alternativa és, i l'editor no li agrada aquesta sintaxi,

294
00:21:47,890 --> 00:21:50,300
i es creu que vull un nou bloc,

295
00:21:50,300 --> 00:22:01,800
però l'alternativa és com -

296
00:22:01,800 --> 00:22:04,190
aquí, ho vaig a posar en una nova línia.

297
00:22:04,190 --> 00:22:09,140
Vostè pot explícitament dir, no recordo la sintaxi exacta.

298
00:22:09,140 --> 00:22:13,110
Així que vostè pot abordar explícitament pel seu nom, i dir:

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

300
00:22:21,570 --> 00:22:24,540
Suposo que aquests han de ser comes.

301
00:22:24,540 --> 00:22:29,110
. Dreta = NULL, de manera que aquest camí no ho fa

302
00:22:29,110 --> 00:22:33,780
realment necessita saber l'ordre de l'estructura,

303
00:22:33,780 --> 00:22:36,650
i quan vostè està llegint això, és molt més explícita

304
00:22:36,650 --> 00:22:41,920
sobre quin és el valor que s'està inicialitzat a.

305
00:22:41,920 --> 00:22:44,080
>> Això passa a ser una de les coses que -

306
00:22:44,080 --> 00:22:49,100
així, en la seva major part, C + + és un superconjunt de C.

307
00:22:49,100 --> 00:22:54,160
Vostè pot obtenir les C, moure a C + +, i s'ha de compilar.

308
00:22:54,160 --> 00:22:59,570
Aquesta és una de les coses que C + + no admet, de manera que la gent tendeix a no fer-ho.

309
00:22:59,570 --> 00:23:01,850
No sé si aquesta és l'única raó per la gent tendeix a no fer-ho,

310
00:23:01,850 --> 00:23:10,540
però el cas on havia de fer-lo servir necessari per treballar amb C + + i el que no podia usar.

311
00:23:10,540 --> 00:23:14,000
Un altre exemple d'alguna cosa que no funciona en C + + és

312
00:23:14,000 --> 00:23:16,940
com malloc retorna un "void *," tècnicament,

313
00:23:16,940 --> 00:23:20,200
però podeu dir char * x = qualsevol malloc,

314
00:23:20,200 --> 00:23:22,840
i automàticament es converteix en un char *.

315
00:23:22,840 --> 00:23:25,450
Aquest repartiment automàtic no passa en C + +.

316
00:23:25,450 --> 00:23:28,150
Això no va a construir i de manera explícita hauria de dir

317
00:23:28,150 --> 00:23:34,510
char *, malloc, el que sigui, per llançar-lo a un char *.

318
00:23:34,510 --> 00:23:37,270
No hi ha moltes coses que C i C + + no estan d'acord en,

319
00:23:37,270 --> 00:23:40,620
però aquests són dos.

320
00:23:40,620 --> 00:23:43,120
Així que anirem amb aquesta sintaxi.

321
00:23:43,120 --> 00:23:46,150
Però encara que no va ser amb aquesta sintaxi,

322
00:23:46,150 --> 00:23:49,470
el que és - podria ser dolent en això?

323
00:23:49,470 --> 00:23:52,170
[Estudiant] No cal eliminar la referència veritat? Sí >>.

324
00:23:52,170 --> 00:23:55,110
Recordeu que la fletxa té un dereference implícita,

325
00:23:55,110 --> 00:23:58,230
i així, quan només estem tractant amb una estructura,

326
00:23:58,230 --> 00:24:04,300
que voleu utilitzar. per arribar a un camp a l'interior de l'estructura.

327
00:24:04,300 --> 00:24:07,200
I l'única vegada que utilitzi la fletxa és quan volem fer -

328
00:24:07,200 --> 00:24:13,450
així, la fletxa és equivalent a -

329
00:24:13,450 --> 00:24:17,020
això és el que hauria significat si he fet servir fletxa.

330
00:24:17,020 --> 00:24:24,600
Tots els mitjans fletxa és a dir, eliminar la referència això, ara estic en una estructura, i puc aconseguir el terreny.

331
00:24:24,600 --> 00:24:28,040
Qualsevol d'obtenir el camp o directament eliminar la referència i obtenir el camp -

332
00:24:28,040 --> 00:24:30,380
Suposo que això ha de ser el valor.

333
00:24:30,380 --> 00:24:33,910
Però aquí estic tractant amb només una estructura, no és un punter a una estructura,

334
00:24:33,910 --> 00:24:38,780
i per tant no puc utilitzar la fletxa.

335
00:24:38,780 --> 00:24:47,510
Però aquest tipus de coses que podem fer per a tots els nodes.

336
00:24:47,510 --> 00:24:55,790
Oh meu Déu.

337
00:24:55,790 --> 00:25:09,540
Això és 6, 7, i 3.

338
00:25:09,540 --> 00:25:16,470
Llavors podem establir les sucursals al nostre arbre, podem tenir 7 -

339
00:25:16,470 --> 00:25:21,650
Podem tenir, a la seva esquerra ha d'apuntar a 3.

340
00:25:21,650 --> 00:25:25,130
Llavors, com fer això?

341
00:25:25,130 --> 00:25:29,320
[Els estudiants, inintel · ligible] >> Yeah. La direcció de node3,

342
00:25:29,320 --> 00:25:34,170
i si no tenia la direcció, llavors simplement no es compilarà.

343
00:25:34,170 --> 00:25:38,190
Però recordeu que aquests són punters als nodes propers.

344
00:25:38,190 --> 00:25:44,930
El dret ha d'apuntar a 9,

345
00:25:44,930 --> 00:25:53,330
i 3 han d'emprendre la dreta a 6.

346
00:25:53,330 --> 00:25:58,480
Crec que això és tot a punt. Qualsevol comentari o pregunta?

347
00:25:58,480 --> 00:26:02,060
[Estudiant, inintel · ligible] L'arrel serà 7.

348
00:26:02,060 --> 00:26:08,210
Només podem dir node * ptr =

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

350
00:26:14,160 --> 00:26:20,730
>> Per als nostres propòsits, estarem tractant amb insert,

351
00:26:20,730 --> 00:26:25,490
així que anem a voler escriure una funció per inserir en aquest arbre binari

352
00:26:25,490 --> 00:26:34,230
i l'insert està inevitablement va a trucar a malloc per crear un nou node d'aquest arbre.

353
00:26:34,230 --> 00:26:36,590
Així que les coses van a causar problemes amb el fet que alguns nodes

354
00:26:36,590 --> 00:26:38,590
són actualment a la pila

355
00:26:38,590 --> 00:26:43,680
i altres nodes acabaran a la pila quan les inseriu.

356
00:26:43,680 --> 00:26:47,640
Això és perfectament vàlid, però l'única raó

357
00:26:47,640 --> 00:26:49,600
som capaços de fer això a la pila

358
00:26:49,600 --> 00:26:51,840
és pel fet que és un exemple artificial que sabem

359
00:26:51,840 --> 00:26:56,360
l'arbre se suposa que es construeix com 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Si no té això, llavors no hauria de malloc en el primer lloc.

361
00:27:02,970 --> 00:27:06,160
Com veurem una mica més endavant, hem d'estar malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Ara mateix és perfectament raonable per posar a la pila,

363
00:27:08,570 --> 00:27:14,750
però anem a canviar això a una implementació de malloc.

364
00:27:14,750 --> 00:27:17,160
Així que cada un d'ells ara serà una cosa així com

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

366
00:27:24,240 --> 00:27:28,040
I ara haurem de fer el procés de registre.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - No volia que -

368
00:27:34,010 --> 00:27:40,950
retorna 1, i després podem fer node9-> perquè ara és un punter,

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

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

371
00:27:48,930 --> 00:27:51,410
i haurem de fer això per a cada un dels nodes.

372
00:27:51,410 --> 00:27:57,490
Així que en comptes, posarem dins d'una funció separada.

373
00:27:57,490 --> 00:28:00,620
Diguem que és el node * build_node,

374
00:28:00,620 --> 00:28:09,050
i això és una cosa semblant a l'API de proporcionar per a la codificació de Huffman.

375
00:28:09,050 --> 00:28:12,730
Li donem les funcions inicializador per un arbre

376
00:28:12,730 --> 00:28:20,520
i deconstructor "funcions" dels arbres i el mateix per als boscos.

377
00:28:20,520 --> 00:28:22,570
>> Així que aquí tindrem una funció d'inicialització

378
00:28:22,570 --> 00:28:25,170
a només construir un node per a nosaltres.

379
00:28:25,170 --> 00:28:29,320
I veurà gairebé exactament així.

380
00:28:29,320 --> 00:28:32,230
I estic encara serà mandrós i no canviar el nom de la variable,

381
00:28:32,230 --> 00:28:34,380
encara node9 no té sentit ja.

382
00:28:34,380 --> 00:28:38,610
Oh, suposo valor node9 no hauria d'haver estat 6.

383
00:28:38,610 --> 00:28:42,800
Ara podem tornar node9.

384
00:28:42,800 --> 00:28:49,550
I aquí hem de tornar nul.

385
00:28:49,550 --> 00:28:52,690
Tothom està d'acord que la funció build-a-node?

386
00:28:52,690 --> 00:28:59,780
Així que ara només podem dir així a construir un node amb un valor determinat i punters nuls.

387
00:28:59,780 --> 00:29:09,750
Ara podem dir així, que podem fer node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
I farem. . .

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

390
00:29:33,980 --> 00:29:39,330
I ara volem establir els punters mateixos,

391
00:29:39,330 --> 00:29:42,470
excepte que ara tot està ja en termes d'indicadors

392
00:29:42,470 --> 00:29:48,480
així que ja no necessita la direcció d'.

393
00:29:48,480 --> 00:29:56,300
Bé. Llavors, què és l'últim que vull fer?

394
00:29:56,300 --> 00:30:03,850
Hi ha un error de comprovació de que no estic fent.

395
00:30:03,850 --> 00:30:06,800
Què significa construir retorn node?

396
00:30:06,800 --> 00:30:11,660
[Estudiant, inintel · ligible] >> Si. Si malloc no, tornarà null.

397
00:30:11,660 --> 00:30:16,460
Així que vaig a mandrosament deixar de llegir-lo aquí en comptes de fer una condició per a cada un.

398
00:30:16,460 --> 00:30:22,320
Si (node9 == NULL, - o encara més simple,

399
00:30:22,320 --> 00:30:28,020
això és equivalent a poc si no node9.

400
00:30:28,020 --> 00:30:38,310
Així que si no node9, o no node6, o no node3, o no node7, tornarà 1.

401
00:30:38,310 --> 00:30:42,850
Potser hauríem imprimir malloc fracassat, o alguna cosa així.

402
00:30:42,850 --> 00:30:46,680
[Estudiant] És fals igual a null també?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Qualsevol valor zero és fals.

404
00:30:51,290 --> 00:30:53,920
Així nul és un valor zero.

405
00:30:53,920 --> 00:30:56,780
Zero és un valor de zero. False és un valor de zero.

406
00:30:56,780 --> 00:31:02,130
Qualsevol - pràcticament els únics 2 valors zero són nuls i zero,

407
00:31:02,130 --> 00:31:07,900
fals és només haixix definit com zero.

408
00:31:07,900 --> 00:31:13,030
Això també s'aplica si es declaren variable global.

409
00:31:13,030 --> 00:31:17,890
Si tinguéssim node arrel * fins aquí,

410
00:31:17,890 --> 00:31:24,150
llavors - el bo de variables globals és que sempre tenen un valor inicial.

411
00:31:24,150 --> 00:31:27,500
Això no és cert de funcions, com l'interior d'aquí,

412
00:31:27,500 --> 00:31:34,870
si tenim, com *, node o node x.

413
00:31:34,870 --> 00:31:37,380
No tenim idea del que x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
o podríem imprimir-los i que podria resultar arbitrari.

415
00:31:40,700 --> 00:31:44,980
Això no és cert de les variables globals.

416
00:31:44,980 --> 00:31:47,450
Així node arrel o un node x.

417
00:31:47,450 --> 00:31:53,410
Per defecte, tot el que és global, sinó explícitament inicialitzada a un valor,

418
00:31:53,410 --> 00:31:57,390
té un valor de zero com el seu valor.

419
00:31:57,390 --> 00:32:01,150
Així que aquí, l'arrel node *, no explícitament inicialitzar a qualsevol cosa,

420
00:32:01,150 --> 00:32:06,350
pel que el seu valor per defecte serà nul, que és el valor zero de punters.

421
00:32:06,350 --> 00:32:11,870
El valor per omissió de x voldrà dir que x.value és zero,

422
00:32:11,870 --> 00:32:14,260
x.left és nul, i x.right és nul.

423
00:32:14,260 --> 00:32:21,070
Per tant, ja que és una estructura, tots els camps de l'estructura serà el valor zero.

424
00:32:21,070 --> 00:32:24,410
No cal utilitzar que aquí, però.

425
00:32:24,410 --> 00:32:27,320
[Estudiant] Les estructures són diferents de les altres variables, i són les altres variables

426
00:32:27,320 --> 00:32:31,400
valors d'escombraries, que són zeros?

427
00:32:31,400 --> 00:32:36,220
Bowden [] Altres valors també. Així, en x, x serà zero.

428
00:32:36,220 --> 00:32:40,070
Si és en l'àmbit global, té un valor inicial. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] O el valor inicial que va donar o zero.

430
00:32:48,950 --> 00:32:53,260
Crec que s'encarrega de tot això.

431
00:32:53,260 --> 00:32:58,390
>> Bé. Així que la següent part de la pregunta es refereix,

432
00:32:58,390 --> 00:33:01,260
"Ara volem escriure una funció anomenada conté

433
00:33:01,260 --> 00:33:04,930
amb un prototip d'bool conté un valor int. "

434
00:33:04,930 --> 00:33:08,340
No farem bool conté un valor int.

435
00:33:08,340 --> 00:33:15,110
El nostre prototip s'assemblarà

436
00:33:15,110 --> 00:33:22,380
bool conté (valor int.

437
00:33:22,380 --> 00:33:24,490
I també passarem l'arbre

438
00:33:24,490 --> 00:33:28,870
que s'ha de comprovar per veure si té aquest valor.

439
00:33:28,870 --> 00:33:38,290
Així node * arbre). Bé.

440
00:33:38,290 --> 00:33:44,440
I llavors podem anomenar amb alguna cosa així com:

441
00:33:44,440 --> 00:33:46,090
potser voldrà printf o alguna cosa així.

442
00:33:46,090 --> 00:33:51,040
Conté 6, la nostra arrel.

443
00:33:51,040 --> 00:33:54,300
Això hauria de tornar un o veritable,

444
00:33:54,300 --> 00:33:59,390
mentre que l'arrel conté 5 ha de tornar false.

445
00:33:59,390 --> 00:34:02,690
Així que pren un segon per implementar això.

446
00:34:02,690 --> 00:34:06,780
Pot fer-ho ja sigui iterativament o recursivament.

447
00:34:06,780 --> 00:34:09,739
El millor de la manera com hem establert és que les coses

448
00:34:09,739 --> 00:34:12,300
es presta a la nostra solució recursiva molt més fàcil

449
00:34:12,300 --> 00:34:14,719
de manera global la variable fet.

450
00:34:14,719 --> 00:34:19,750
Perquè si només tenim conté un valor int, llavors no tenim forma de manera recursiva per subarbres.

451
00:34:19,750 --> 00:34:24,130
Hauríem de tenir una funció auxiliar independent que recursivament pels subarbres per a nosaltres.

452
00:34:24,130 --> 00:34:29,610
Però ja que hem canviat a prendre l'arbre com un argument,

453
00:34:29,610 --> 00:34:32,760
que hauria d'haver estat sempre, en primer lloc,

454
00:34:32,760 --> 00:34:35,710
ara podem recurse amb més facilitat.

455
00:34:35,710 --> 00:34:38,960
Així iteratiu o recursiu, anem a repassar tots dos,

456
00:34:38,960 --> 00:34:46,139
però veurem que els extrems recursives sent bastant fàcil.

457
00:34:59,140 --> 00:35:02,480
Bé. Algú té alguna cosa que puguem treballar?

458
00:35:02,480 --> 00:35:12,000
>> [Estudiant] Tinc una solució iterativa. >> Molt bé, iteratiu.

459
00:35:12,000 --> 00:35:16,030
Bé, això es veu bé.

460
00:35:16,030 --> 00:35:18,920
Per tant, ens volen caminar a través d'ell?

461
00:35:18,920 --> 00:35:25,780
[Estudiant] Clar. Així que em vaig posar una variable temporal per obtenir el primer node de l'arbre.

462
00:35:25,780 --> 00:35:28,330
I llavors només en bucle mentre que la temperatura no nul · la de igualtat,

463
00:35:28,330 --> 00:35:31,700
així que mentre es trobava encara a l'arbre, suposo.

464
00:35:31,700 --> 00:35:35,710
I si el valor és igual al valor que està apuntant a temp,

465
00:35:35,710 --> 00:35:37,640
a continuació, es torna aquest valor.

466
00:35:37,640 --> 00:35:40,210
En cas contrari, es comprova si és al costat dret o el costat esquerre.

467
00:35:40,210 --> 00:35:43,400
Si mai tens una situació en què no hi ha més arbres,

468
00:35:43,400 --> 00:35:47,330
després torna - surt del bucle i torna false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Bé. Així que sembla bo.

470
00:35:52,190 --> 00:35:58,470
Qualsevol persona té algun comentari sobre qualsevol cosa?

471
00:35:58,470 --> 00:36:02,400
No tinc comentaris correcció en absolut.

472
00:36:02,400 --> 00:36:11,020
L'únic que podem fer és aquest tipus.

473
00:36:11,020 --> 00:36:21,660
Oh, anirà una mica allargada.

474
00:36:21,660 --> 00:36:33,460
Vaig a arreglar això. Bé.

475
00:36:33,460 --> 00:36:37,150
>> Tothom hauria de recordar com funciona ternari.

476
00:36:37,150 --> 00:36:38,610
No ha estat, sens dubte proves en el passat

477
00:36:38,610 --> 00:36:41,170
que li donen una funció amb un operador ternari,

478
00:36:41,170 --> 00:36:45,750
i dir, traduir això, fer una cosa que no utilitza ternari.

479
00:36:45,750 --> 00:36:49,140
Així que aquest és un cas molt comú de quan se li ocorreria utilitzar ternari,

480
00:36:49,140 --> 00:36:54,610
on si alguna condició establir una variable a alguna cosa,

481
00:36:54,610 --> 00:36:58,580
altra indicació que la mateixa variable a una altra cosa.

482
00:36:58,580 --> 00:37:03,390
Això és una cosa que molt sovint es pot transformar en aquest tipus de coses

483
00:37:03,390 --> 00:37:14,420
on assignar a aquesta variable aquesta - o, bé, ¿és això cert? Després d'això, més això.

484
00:37:14,420 --> 00:37:18,550
[Estudiant] La primera és si és cert, oi?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. La manera com sempre ho llegit és, la temperatura és igual al valor més gran que el valor temporal,

486
00:37:25,570 --> 00:37:30,680
llavors això, més d'això. Està fent una pregunta.

487
00:37:30,680 --> 00:37:35,200
És gran? Després fer el primer. Altres fer el segon.

488
00:37:35,200 --> 00:37:41,670
Jo gairebé sempre - els dos punts, jo només - en el meu cap, he llegit com una altra cosa.

489
00:37:41,670 --> 00:37:47,180
>> Algú té una solució recursiva?

490
00:37:47,180 --> 00:37:49,670
Bé. Aquest anem a - que ja podia ser gran,

491
00:37:49,670 --> 00:37:53,990
però ho farem encara millor.

492
00:37:53,990 --> 00:37:58,720
Això és més o menys la idea exactament el mateix.

493
00:37:58,720 --> 00:38:03,060
És només que, bé, és el que vols explicar?

494
00:38:03,060 --> 00:38:08,340
[Estudiant] Clar. Així ens assegurem que l'arbre no és nul en primer lloc,

495
00:38:08,340 --> 00:38:13,380
perquè si l'arbre és nul llavors tornarà fals, perquè no l'hem trobat.

496
00:38:13,380 --> 00:38:19,200
I si encara hi ha un arbre, entrem en - en primer lloc comprovar si el valor és el node actual.

497
00:38:19,200 --> 00:38:23,740
Retorna vertader si ho és, i si no recurse a l'esquerra oa la dreta.

498
00:38:23,740 --> 00:38:25,970
Li sembla adequat? >> Mm-hmm. (Acord)

499
00:38:25,970 --> 00:38:33,880
Així adonar que això és gairebé - estructuralment molt semblant a la solució iterativa.

500
00:38:33,880 --> 00:38:38,200
És només que en lloc de recursivitat, vam tenir un bucle while.

501
00:38:38,200 --> 00:38:40,840
I el cas base aquí on arbre no fa nul igual

502
00:38:40,840 --> 00:38:44,850
era la condició sota la qual va trencar el bucle while.

503
00:38:44,850 --> 00:38:50,200
Són molt similars. Però anem a fer un pas més enllà.

504
00:38:50,200 --> 00:38:54,190
Ara, fem el mateix aquí.

505
00:38:54,190 --> 00:38:57,680
Tingueu en compte que estem tornant el mateix en ambdues línies,

506
00:38:57,680 --> 00:39:00,220
a excepció d'un argument és diferent.

507
00:39:00,220 --> 00:39:07,950
Així que farem això en un ternari.

508
00:39:07,950 --> 00:39:13,790
Vaig picar alguna cosa opció, i va fer un símbol. Bé.

509
00:39:13,790 --> 00:39:21,720
Així que anem a tornar que conté.

510
00:39:21,720 --> 00:39:28,030
Això s'està convertint en diverses línies, bé, el zoom és.

511
00:39:28,030 --> 00:39:31,060
En general, com una cosa d'estil, no crec que molta gent

512
00:39:31,060 --> 00:39:38,640
posar un espai després de la fletxa, però suposo que si ets consistent, està bé.

513
00:39:38,640 --> 00:39:44,320
Si el valor és inferior al valor de l'arbre, volem recurse a l'esquerra de l'arbre,

514
00:39:44,320 --> 00:39:53,890
més volem recurse a la dreta de l'arbre.

515
00:39:53,890 --> 00:39:58,610
Així que aquest va ser el primer pas de fer aquesta mirada més petit.

516
00:39:58,610 --> 00:40:02,660
Segon pas de fer aquesta mirada més petit -

517
00:40:02,660 --> 00:40:09,150
podem separar aquesta a diverses línies.

518
00:40:09,150 --> 00:40:16,500
Bé. El segon pas de fer que es vegi més petita és aquí,

519
00:40:16,500 --> 00:40:25,860
així valor de retorn és igual al valor de l'arbre, o conté el que sigui.

520
00:40:25,860 --> 00:40:28,340
>> Això és una cosa important.

521
00:40:28,340 --> 00:40:30,860
No estic segur de si ho va dir explícitament en la classe,

522
00:40:30,860 --> 00:40:34,740
però es diu l'avaluació de curtcircuit.

523
00:40:34,740 --> 00:40:41,060
La idea és value == valor arbre.

524
00:40:41,060 --> 00:40:49,960
Si això és veritat, llavors això és cert, i volem »o« això amb el que estigui per aquí.

525
00:40:49,960 --> 00:40:52,520
Així, sense ni tan sols pensar en el que està per aquí,

526
00:40:52,520 --> 00:40:55,070
Quina és l'expressió sencera va a tornar?

527
00:40:55,070 --> 00:40:59,430
[Estudiant] Cert? >> Sí, perquè cert de res,

528
00:40:59,430 --> 00:41:04,990
operació lògica OR - operació lògica OR o veritable amb tot és necessàriament cert.

529
00:41:04,990 --> 00:41:08,150
Així que tan aviat com veiem valor de retorn = valor d'arbre,

530
00:41:08,150 --> 00:41:10,140
només tornarem realitat.

531
00:41:10,140 --> 00:41:15,710
Ni tan sols va a recurse conté més de la línia.

532
00:41:15,710 --> 00:41:20,980
Podem fer un pas més enllà.

533
00:41:20,980 --> 00:41:29,490
Arbre retorn no nul igual i tot això.

534
00:41:29,490 --> 00:41:32,650
Ho va fer en funció d'una línia.

535
00:41:32,650 --> 00:41:36,790
Aquest és també un exemple de l'avaluació de curtcircuit.

536
00:41:36,790 --> 00:41:40,680
Però ara és la mateixa idea -

537
00:41:40,680 --> 00:41:47,320
en lloc de - pel que si l'arbre no nul igual - o, bé,

538
00:41:47,320 --> 00:41:49,580
si arbre fa nul · la d'igualtat, que és el cas dolent,

539
00:41:49,580 --> 00:41:54,790
si l'arbre és igual a NULL, la primera condició és falsa.

540
00:41:54,790 --> 00:42:00,550
Així fals AND amb qualsevol cosa serà què?

541
00:42:00,550 --> 00:42:04,640
[Estudiant] Fals. Sí >>. Aquesta és l'altra meitat de l'avaluació de curtcircuit,

542
00:42:04,640 --> 00:42:10,710
on si l'arbre és nul no és igual, llavors no aniran encara més -

543
00:42:10,710 --> 00:42:14,930
o si ho fa nul arbre igual, llavors no farem value == valor arbre.

544
00:42:14,930 --> 00:42:17,010
Només anem a tornar immediatament falsa.

545
00:42:17,010 --> 00:42:20,970
La qual cosa és important, ja que si no ho fa curtcircuit evaluate,

546
00:42:20,970 --> 00:42:25,860
llavors si l'arbre fa nul igual, aquesta segona condició es va a culpa seg,

547
00:42:25,860 --> 00:42:32,510
perquè arbre-> valor desreferencia nul · la.

548
00:42:32,510 --> 00:42:40,490
Així que això és tot. Pot fer això - canviar un cop més.

549
00:42:40,490 --> 00:42:44,840
Això és una cosa molt comuna també, no fer aquesta línia amb això,

550
00:42:44,840 --> 00:42:49,000
però és una cosa comuna en condicions, potser no aquí,

551
00:42:49,000 --> 00:42:59,380
però si (árbol! = NULL, i l'arbre-> valor value ==), fer el que sigui.

552
00:42:59,380 --> 00:43:01,560
Aquesta és una condició molt comú, on en lloc de tenir

553
00:43:01,560 --> 00:43:06,770
a trencar això en dues IFS, on vulgui, és la nul · arbre?

554
00:43:06,770 --> 00:43:11,780
Bé, no és nul, de manera que ara és el valor equivalent al valor de l'arbre? Feu això.

555
00:43:11,780 --> 00:43:17,300
En el seu lloc, aquesta condició, això mai falla seg

556
00:43:17,300 --> 00:43:21,220
perquè sortirà si això passa a ser nul.

557
00:43:21,220 --> 00:43:24,000
Bé, suposo que si l'arbre és un punter nul completament, encara pot seg culpa,

558
00:43:24,000 --> 00:43:26,620
però no pot seg error si l'arbre és nul.

559
00:43:26,620 --> 00:43:32,900
Si fos nul, anava a esclatar abans que desreferencia el punter al primer lloc.

560
00:43:32,900 --> 00:43:35,000
[Estudiant] Aquest avaluació mandrosa anomenada?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] L'avaluació diferida és una cosa a part.

562
00:43:40,770 --> 00:43:49,880
L'avaluació diferida és més com vostè demana un valor,

563
00:43:49,880 --> 00:43:54,270
demanar-li que calculi un valor, tipus d', però vostè no ho necessita immediatament.

564
00:43:54,270 --> 00:43:59,040
Així que fins que realment ho necessiten, no s'avalua.

565
00:43:59,040 --> 00:44:03,920
Això no és exactament el mateix, però, en el conjunt de processadors Huffman

566
00:44:03,920 --> 00:44:06,520
que diu que "mandrosa", escriuen.

567
00:44:06,520 --> 00:44:08,670
La raó per la qual fem això és perquè en realitat estem amortiment de l'escriptura -

568
00:44:08,670 --> 00:44:11,820
no vull escriure bits individuals alhora,

569
00:44:11,820 --> 00:44:15,450
o bytes individuals alhora, en lloc vol aconseguir un tros de bytes.

570
00:44:15,450 --> 00:44:19,270
Després, una vegada que tenim un fragment de bytes, llavors anem a escriure.

571
00:44:19,270 --> 00:44:22,640
Tot i que es demani a escriure - i fwrite i fread fer el mateix tipus de coses.

572
00:44:22,640 --> 00:44:26,260
Ells esmorteir la seva lectura i escriptura.

573
00:44:26,260 --> 00:44:31,610
Tot i que es demani a escriure immediatament, probablement no ho farà.

574
00:44:31,610 --> 00:44:34,540
I no es pot estar segur que les coses seran escrits

575
00:44:34,540 --> 00:44:37,540
fins que es diu hfclose o el que sigui,

576
00:44:37,540 --> 00:44:39,620
que després es diu, està bé, vaig a tancar el meu arxiu,

577
00:44:39,620 --> 00:44:43,450
això vol dir que serà millor que escriure tot el que no he escrit encara.

578
00:44:43,450 --> 00:44:45,770
No ha d'escriure tot el que fos

579
00:44:45,770 --> 00:44:49,010
fins que es tanqui l'arxiu i faci el necessari.

580
00:44:49,010 --> 00:44:56,220
Així que això és just el vague - que espera fins que ha de succeir.

581
00:44:56,220 --> 00:44:59,990
Això - prendre 51 i podràs entrar-hi amb més detall,

582
00:44:59,990 --> 00:45:05,470
perquè Ocaml i tot el que en el 51, tot és repetició.

583
00:45:05,470 --> 00:45:08,890
No hi ha solucions iteratives, bàsicament.

584
00:45:08,890 --> 00:45:11,550
Tot és repetició, i l'avaluació mandrosa

585
00:45:11,550 --> 00:45:14,790
serà important per a un munt de circumstàncies

586
00:45:14,790 --> 00:45:19,920
on, si no mandrosament avaluar, això significaria -

587
00:45:19,920 --> 00:45:24,760
L'exemple és corrents, que són infinitament llarg.

588
00:45:24,760 --> 00:45:30,990
En teoria, es pot pensar en els nombres naturals com un corrent de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Així que les coses estan ben avaluats mandrosament.

590
00:45:33,090 --> 00:45:37,210
Si dic que vull que el desè número, llavors puc avaluar fins al número deu.

591
00:45:37,210 --> 00:45:40,300
Si voleu que el número cent, llavors puc avaluar fins al número cent.

592
00:45:40,300 --> 00:45:46,290
Sense l'avaluació mandrosa, llavors intentarà avaluar tots els números immediatament.

593
00:45:46,290 --> 00:45:50,000
S'està avaluant un nombre infinit de nombres, i això no és possible.

594
00:45:50,000 --> 00:45:52,080
Així que hi ha un munt de circumstàncies en les que l'avaluació mandrosa

595
00:45:52,080 --> 00:45:57,840
és essencial per aconseguir que les coses funcionin.

596
00:45:57,840 --> 00:46:05,260
>> Ara volem escriure inserció insert on serà

597
00:46:05,260 --> 00:46:08,430
de manera similar canviant en la seva definició.

598
00:46:08,430 --> 00:46:10,470
Així que ara mateix està inserit bool (int value).

599
00:46:10,470 --> 00:46:23,850
Canviarem això per inserir bool (int value, node d'arbre *).

600
00:46:23,850 --> 00:46:29,120
Estem realment canviarà de nou una mica, ja veurem per què.

601
00:46:29,120 --> 00:46:32,210
I passarem build_node, només pel gust de fer-ho,

602
00:46:32,210 --> 00:46:36,730
per sobre d'inserir de manera que no ha d'escriure un prototip de funció.

603
00:46:36,730 --> 00:46:42,450
La qual cosa és un indici que s'utilitzarà en build_node inserció.

604
00:46:42,450 --> 00:46:49,590
Bé. Tome un minut per això.

605
00:46:49,590 --> 00:46:52,130
Crec que em va salvar la revisió si vols tirar d'això,

606
00:46:52,130 --> 00:47:00,240
o, si més no, ho vaig fer ara.

607
00:47:00,240 --> 00:47:04,190
Jo volia un lleuger a pensar en la lògica de la inserció,

608
00:47:04,190 --> 00:47:08,750
si vostè no pot pensar-hi.

609
00:47:08,750 --> 00:47:12,860
Bàsicament, només alguna vegada s'insereix en les fulles.

610
00:47:12,860 --> 00:47:18,640
Igual que, si inserit 1, llavors estic inevitablement va a inserir 1 -

611
00:47:18,640 --> 00:47:21,820
Vaig a canviar a negre - Estaré inserir una per aquí.

612
00:47:21,820 --> 00:47:28,070
O si puc inserir 4, vull ser la inserció de 4 per aquí.

613
00:47:28,070 --> 00:47:32,180
Així que no importa el que facis, vas a inserir en un full.

614
00:47:32,180 --> 00:47:36,130
Tot el que has de fer és recórrer l'arbre fins arribar al node

615
00:47:36,130 --> 00:47:40,890
que ha de ser el pare del node, el pare del nou node,

616
00:47:40,890 --> 00:47:44,560
i després canviar el punter d'esquerra o dreta, depenent de si

617
00:47:44,560 --> 00:47:47,060
és major o menor que el node actual.

618
00:47:47,060 --> 00:47:51,180
Canviar aquest punter per apuntar al seu nou node.

619
00:47:51,180 --> 00:48:05,490
Així iterar cap avall de l'arbre, fan que el punt del full al nou node.

620
00:48:05,490 --> 00:48:09,810
També pensi per què prohibeix el tipus de situació abans,

621
00:48:09,810 --> 00:48:17,990
on va construir l'arbre binari on estava correcta

622
00:48:17,990 --> 00:48:19,920
si només mirar a un sol node,

623
00:48:19,920 --> 00:48:24,830
però el 9 estava a l'esquerra de 7 si reiterat per tot el camí.

624
00:48:24,830 --> 00:48:29,770
Així que és impossible en aquesta situació, ja que -

625
00:48:29,770 --> 00:48:32,530
pensar en la inserció de 9 o alguna cosa, en el primer node,

626
00:48:32,530 --> 00:48:35,350
Vaig a veure 7 i em vaig a anar a la dreta.

627
00:48:35,350 --> 00:48:38,490
Així que no importa el que faci, si estic anant a la inserció d'un full,

628
00:48:38,490 --> 00:48:40,790
i a un full utilitzant l'algorisme apropiat,

629
00:48:40,790 --> 00:48:43,130
que serà impossible per a mi per inserir 9 a l'esquerra, de 7 de

630
00:48:43,130 --> 00:48:48,250
perquè així que em va colpejar 7 Jo vaig a anar a la dreta.

631
00:48:59,740 --> 00:49:02,070
Algú té alguna cosa per començar?

632
00:49:02,070 --> 00:49:05,480
[Estudiant] que faig. >> Clar.

633
00:49:05,480 --> 00:49:09,200
[Estudiant, inintel · ligible]

634
00:49:09,200 --> 00:49:14,390
[Un altre estudiant, inintel · ligible]

635
00:49:14,390 --> 00:49:18,330
[Bowden] S'aprecia. Bé. Vols explicar?

636
00:49:18,330 --> 00:49:20,690
>> [Estudiant] Ja que sabem que estàvem inserint

637
00:49:20,690 --> 00:49:24,060
nous nodes a l'extrem de l'arbre,

638
00:49:24,060 --> 00:49:28,070
M'envien a través de l'arbre de manera iterativa

639
00:49:28,070 --> 00:49:31,360
fins que vaig arribar a un node que apuntava a null.

640
00:49:31,360 --> 00:49:34,220
I llavors em vaig decidir a posar ja sigui en el costat dret o el costat esquerre

641
00:49:34,220 --> 00:49:37,420
utilitzant aquesta variable correcte, sinó que em va dir on posar.

642
00:49:37,420 --> 00:49:41,850
I llavors, en essència, que acabo de fer que el passat -

643
00:49:41,850 --> 00:49:47,520
aquest punt temp node al nou node que s'estava creant,

644
00:49:47,520 --> 00:49:50,770
ja sigui en el costat esquerre o al costat dret, depenent del que el valor de la dreta era.

645
00:49:50,770 --> 00:49:56,530
Finalment, estableix el valor nou node amb el valor de la seva prova.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Està bé, així que no veig un problema aquí.

647
00:49:59,550 --> 00:50:02,050
Això és com el 95% del camí.

648
00:50:02,050 --> 00:50:07,550
L'únic problema que veig, bé, algú més veu un problema?

649
00:50:07,550 --> 00:50:18,400
Quina és la circumstància en què trencar el llaç?

650
00:50:18,400 --> 00:50:22,100
[Estudiant] Si la temperatura és nul? Sí >>. Llavors, com sortir del bucle és si la temperatura és nul.

651
00:50:22,100 --> 00:50:30,220
Però, què faig aquí?

652
00:50:30,220 --> 00:50:35,410
Jo dereference temperatura, que és inevitablement nul.

653
00:50:35,410 --> 00:50:39,840
Així que el que vostè ha de fer no és només un seguiment fins que la temperatura és nul,

654
00:50:39,840 --> 00:50:45,590
vostè vol estar al dia dels pares en tot moment.

655
00:50:45,590 --> 00:50:52,190
També volem que els pares node *, crec que podem mantenir en nul al principi.

656
00:50:52,190 --> 00:50:55,480
Això tindrà un comportament estrany en l'arrel de l'arbre,

657
00:50:55,480 --> 00:50:59,210
però ja arribarem a això.

658
00:50:59,210 --> 00:51:03,950
Si el valor és més gran del que sigui, llavors temp = temp dreta.

659
00:51:03,950 --> 00:51:07,910
Però abans de fer això, pare temp =.

660
00:51:07,910 --> 00:51:14,500
O els pares sempre van a temp iguals? És aquest el cas?

661
00:51:14,500 --> 00:51:19,560
Si la temperatura no és nul, llavors jo vaig a baixar, tant i fa,

662
00:51:19,560 --> 00:51:24,030
a un node per al qual la temperatura és el pare.

663
00:51:24,030 --> 00:51:27,500
Així que els pares serà temporal, i després em moc per temp.

664
00:51:27,500 --> 00:51:32,410
Ara la temperatura és nul, però assenyala als pares dels pares del que és nul.

665
00:51:32,410 --> 00:51:39,110
Així que aquí, no vull establir dreta és igual a 1.

666
00:51:39,110 --> 00:51:41,300
Així que em vaig mudar a la dreta, de manera que si la dreta = 1,

667
00:51:41,300 --> 00:51:45,130
i suposo que també volen fer -

668
00:51:45,130 --> 00:51:48,530
si es mou cap a l'esquerra, que vol establir el dret igual a 0.

669
00:51:48,530 --> 00:51:55,950
O bé, si mai es mouen cap a la dreta.

670
00:51:55,950 --> 00:51:58,590
Així dreta = 0. Si la dreta = 1,

671
00:51:58,590 --> 00:52:04,260
ara volem que el pare nodo_nuevo punter dret,

672
00:52:04,260 --> 00:52:08,520
altra cosa que vol fer el pare nodo_nuevo punter esquerre.

673
00:52:08,520 --> 00:52:16,850
Les preguntes sobre això?

674
00:52:16,850 --> 00:52:24,880
Bé. Així que aquesta és la forma en què - bé, en realitat, en lloc de fer això,

675
00:52:24,880 --> 00:52:29,630
Gairebé esperava que utilitzeu build_node.

676
00:52:29,630 --> 00:52:40,450
I després, si és igual nodo_nuevo nul, retorna fals.

677
00:52:40,450 --> 00:52:44,170
Això és tot. Ara bé, això és el que esperàvem que fes.

678
00:52:44,170 --> 00:52:47,690
>> Això és el que les solucions de personal fer.

679
00:52:47,690 --> 00:52:52,360
No estic d'acord amb això com la manera "correcta" de fer les coses

680
00:52:52,360 --> 00:52:57,820
però això està perfectament bé i va a funcionar.

681
00:52:57,820 --> 00:53:02,840
Una cosa que és un dret mica estrany ara és

682
00:53:02,840 --> 00:53:08,310
si l'arbre comença com nul, es passa a un arbre nul.

683
00:53:08,310 --> 00:53:12,650
Suposo que depèn de com es defineixi el comportament del passatger en un arbre nul.

684
00:53:12,650 --> 00:53:15,490
M'agradaria pensar que si es passa un arbre nul,

685
00:53:15,490 --> 00:53:17,520
a continuació, inserir el valor NULL en un arbre

686
00:53:17,520 --> 00:53:23,030
només ha de retornar un arbre en el qual l'únic valor és que només node.

687
00:53:23,030 --> 00:53:25,830
Les persones estan d'acord amb això? Vostè pot, si vol,

688
00:53:25,830 --> 00:53:28,050
si es passa un arbre nul

689
00:53:28,050 --> 00:53:31,320
i desitja inserir un valor en ell, retorna fals.

690
00:53:31,320 --> 00:53:33,830
Depèn de vostè per definir això.

691
00:53:33,830 --> 00:53:38,320
Per això el primer que em va dir i després -

692
00:53:38,320 --> 00:53:40,720
així, tindràs problemes per fer això, perquè

693
00:53:40,720 --> 00:53:44,090
seria més fàcil si tinguéssim un punter global a la cosa,

694
00:53:44,090 --> 00:53:48,570
però no, de manera que si l'arbre és nul, no hi ha res que puguem fer al respecte.

695
00:53:48,570 --> 00:53:50,960
Només pot tornar false.

696
00:53:50,960 --> 00:53:52,840
Així que em canviaré d'inserció.

697
00:53:52,840 --> 00:53:56,540
Ens tècnicament podria canviar això d'aquí,

698
00:53:56,540 --> 00:53:58,400
com es itera sobre les coses,

699
00:53:58,400 --> 00:54:04,530
però jo canviaré d'inserció per prendre un node d'arbre. **

700
00:54:04,530 --> 00:54:07,510
Punters dobles.

701
00:54:07,510 --> 00:54:09,710
Què vol dir això?

702
00:54:09,710 --> 00:54:12,330
En lloc de tractar amb punters a nodes,

703
00:54:12,330 --> 00:54:16,690
el que vaig a estar manipulant és aquest punter.

704
00:54:16,690 --> 00:54:18,790
Vaig a estar manipulant aquest punter.

705
00:54:18,790 --> 00:54:21,770
Vaig a estar manipulant directament els punters.

706
00:54:21,770 --> 00:54:25,760
Això té sentit ja que, pensar cap avall -

707
00:54:25,760 --> 00:54:33,340
Bé, ara això apunta null.

708
00:54:33,340 --> 00:54:38,130
El que vull fer és manipular aquest punter per apuntar a no nul.

709
00:54:38,130 --> 00:54:40,970
Vull que apunti al meu nou node.

710
00:54:40,970 --> 00:54:44,870
Si tan sols fer un seguiment dels punters als meus consells,

711
00:54:44,870 --> 00:54:47,840
llavors no és necessari fer un seguiment d'un punter pares.

712
00:54:47,840 --> 00:54:52,640
Acabo de fer un seguiment per veure si el punter apunta a null,

713
00:54:52,640 --> 00:54:54,580
i si el punter apunta a null,

714
00:54:54,580 --> 00:54:57,370
canviar perquè apunti al node que vull.

715
00:54:57,370 --> 00:55:00,070
I puc canviar ja que tinc un punter al punter.

716
00:55:00,070 --> 00:55:02,040
Anem a veure això ara mateix.

717
00:55:02,040 --> 00:55:05,470
En realitat es pot fer de forma recursiva amb força facilitat.

718
00:55:05,470 --> 00:55:08,080
Volem fer-ho?

719
00:55:08,080 --> 00:55:10,980
Sí, ho fem.

720
00:55:10,980 --> 00:55:16,790
>> Anem a veure de forma recursiva.

721
00:55:16,790 --> 00:55:24,070
En primer lloc, quin és el nostre cas base serà?

722
00:55:24,070 --> 00:55:29,140
Gairebé sempre el nostre cas base, però en realitat, això és una mica complicat.

723
00:55:29,140 --> 00:55:34,370
El primer és el primer, si (arbre == NULL)

724
00:55:34,370 --> 00:55:37,550
Suposo que només tornarà false.

725
00:55:37,550 --> 00:55:40,460
Això és diferent de la seva nul · arbre benestar.

726
00:55:40,460 --> 00:55:44,510
Aquest és el punter al punter arrel sent nul

727
00:55:44,510 --> 00:55:48,360
el que significa que el punter de la seva arrel no existeix.

728
00:55:48,360 --> 00:55:52,390
Així que aquí, si ho faig

729
00:55:52,390 --> 00:55:55,760
* Node - tornarem a fer servir això.

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

731
00:55:58,960 --> 00:56:00,730
i després em vaig a trucar a inserir fent alguna cosa com:

732
00:56:00,730 --> 00:56:04,540
inserir i 4 a l'arrel.

733
00:56:04,540 --> 00:56:06,560
Així i arrel, si l'arrel és un node *

734
00:56:06,560 --> 00:56:11,170
i llavors l'arrel serà un ** node.

735
00:56:11,170 --> 00:56:15,120
Això és vàlid. En aquest cas, l'arbre, fins aquí,

736
00:56:15,120 --> 00:56:20,120
arbre no és nul - o inserció.

737
00:56:20,120 --> 00:56:24,630
Aquí. Tree no és nul; arbre * és nul, la qual cosa està bé

738
00:56:24,630 --> 00:56:26,680
perquè si l'arbre * és nul, llavors puc manipular

739
00:56:26,680 --> 00:56:29,210
apuntar ara al que jo vull apuntar.

740
00:56:29,210 --> 00:56:34,750
Però si l'arbre és nul, això vol dir que només vaig venir aquí i em va dir nul.

741
00:56:34,750 --> 00:56:42,710
Això no té sentit. No puc fer res amb això.

742
00:56:42,710 --> 00:56:45,540
Si l'arbre és nul, retorna fals.

743
00:56:45,540 --> 00:56:48,220
Així que, bàsicament, el que ja ha dit el nostre cas base real.

744
00:56:48,220 --> 00:56:50,580
I el que és que serà?

745
00:56:50,580 --> 00:56:55,030
[Estudiant, inintel · ligible]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Sí Així que si (* arbre == NULL).

747
00:57:00,000 --> 00:57:04,520
Això es relaciona amb el cas aquí

748
00:57:04,520 --> 00:57:09,640
on si el meu punter vermell és el punter que estic enfocat,

749
00:57:09,640 --> 00:57:12,960
així que estic centrat en aquest indicador, ara estic centrat en aquest indicador.

750
00:57:12,960 --> 00:57:15,150
Ara estic centrat en aquest indicador.

751
00:57:15,150 --> 00:57:18,160
Així que si el meu punter vermell, que és el meu ** nodes,

752
00:57:18,160 --> 00:57:22,880
és cada vegada - si *, la meva punter vermell, és sempre nul,

753
00:57:22,880 --> 00:57:28,470
això vol dir que estic en el cas que em centraré en un punter que apunta -

754
00:57:28,470 --> 00:57:32,530
aquest és un punter que pertany a un full.

755
00:57:32,530 --> 00:57:41,090
Vull canviar aquest punter per apuntar al meu nou node.

756
00:57:41,090 --> 00:57:45,230
Torna per aquí.

757
00:57:45,230 --> 00:57:56,490
La meva nodo_nuevo només serà node * n = build_node (valor)

758
00:57:56,490 --> 00:58:07,300
llavors n, si n = NULL, retorna fals.

759
00:58:07,300 --> 00:58:12,600
Altres vendes que volem canviar el que el punter apunta actualment

760
00:58:12,600 --> 00:58:17,830
apuntar ara al nostre node de nova construcció.

761
00:58:17,830 --> 00:58:20,280
De fet, podem fer això aquí.

762
00:58:20,280 --> 00:58:30,660
En lloc de dir n, diem arbre * = si l'arbre *.

763
00:58:30,660 --> 00:58:35,450
Tothom entén això? Això negociant amb punters a punters,

764
00:58:35,450 --> 00:58:40,750
podem canviar punters nuls per apuntar a les coses que volem apuntar.

765
00:58:40,750 --> 00:58:42,820
Aquest és el nostre cas base.

766
00:58:42,820 --> 00:58:45,740
>> Ara el nostre recurrència, o la nostra recursivitat,

767
00:58:45,740 --> 00:58:51,430
serà molt similar a tots els altres recurrències que hem estat fent.

768
00:58:51,430 --> 00:58:55,830
Anem a voler inserir un valor,

769
00:58:55,830 --> 00:58:59,040
i ara jo vaig a usar de nou ternari, però el que és la nostra condició serà?

770
00:58:59,040 --> 00:59:05,180
Què és el que estem buscant per decidir si volem anar a l'esquerra oa la dreta?

771
00:59:05,180 --> 00:59:07,760
Anem a fer-ho en passos separats.

772
00:59:07,760 --> 00:59:18,850
Si (valor <) què?

773
00:59:18,850 --> 00:59:23,200
[Estudiant] El valor de l'arbre?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Així que recordi que sóc en l'actualitat -

775
00:59:27,490 --> 00:59:31,260
[Els estudiants], inintel · ligibles

776
00:59:31,260 --> 00:59:34,140
[Bowden] Sí, tan bé aquí, direm que aquesta fletxa verda

777
00:59:34,140 --> 00:59:39,050
és un exemple del que actualment és arbre, és un punter al punter.

778
00:59:39,050 --> 00:59:46,610
Així que això significa que sóc un punter a un punter a 3.

779
00:59:46,610 --> 00:59:48,800
El dereference dues vegades sonava bé.

780
00:59:48,800 --> 00:59:51,010
Què - com puc fer això?

781
00:59:51,010 --> 00:59:53,210
[Estudiant] eliminar la referència una vegada, i després fer fletxa d'aquesta manera?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Llavors (arbre *) és l'eliminació de referències una vegada, -> valor

783
00:59:58,420 --> 01:00:05,960
em donarà el valor del node que estic assenyalant indirectament.

784
01:00:05,960 --> 01:00:11,980
Així que també es pot escriure ** tree.value si ho prefereix això.

785
01:00:11,980 --> 01:00:18,490
Qualsevol de les obres.

786
01:00:18,490 --> 01:00:26,190
Si aquest és el cas, llavors vull trucar a inserir amb valor.

787
01:00:26,190 --> 01:00:32,590
I el que és meu node actualitzat ** serà?

788
01:00:32,590 --> 01:00:39,440
Jo vull anar a l'esquerra, de manera que arbol.izquierdo ** serà la meva esquerra.

789
01:00:39,440 --> 01:00:41,900
I vull que el punter a aquesta cosa

790
01:00:41,900 --> 01:00:44,930
de manera que si l'esquerra acaba sent el punter nul,

791
01:00:44,930 --> 01:00:48,360
Puc modificar per apuntar al meu nou node.

792
01:00:48,360 --> 01:00:51,460
>> I l'altre cas pot ser molt similar.

793
01:00:51,460 --> 01:00:55,600
Farem que la meva realitat ternari en aquests moments.

794
01:00:55,600 --> 01:01:04,480
Inseriu valor si el valor <(arbre **). Valor.

795
01:01:04,480 --> 01:01:11,040
Llavors volem actualitzar els nostres ** a l'esquerra,

796
01:01:11,040 --> 01:01:17,030
més volem actualitzar els nostres ** a la dreta.

797
01:01:17,030 --> 01:01:22,540
[Estudiant] Això obtenir el punter al punter?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Recordeu que - ** arbol.derecho és un estel node.

799
01:01:30,940 --> 01:01:35,040
[Estudiant, inintel · ligible] >> Si.

800
01:01:35,040 --> 01:01:41,140
** Arbol.derecho és com aquest punter o alguna cosa així.

801
01:01:41,140 --> 01:01:45,140
Així, prenent un punter a això, que em dóna el que vull

802
01:01:45,140 --> 01:01:50,090
del punter a aquest tipus.

803
01:01:50,090 --> 01:01:54,260
[Estudiant] Podríem anar una altra vegada per què estem utilitzant els dos punters?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Per tant - no, vostè pot, i la solució que abans

805
01:01:58,220 --> 01:02:04,540
Era una manera de fer-ho sense haver de fer dos punters.

806
01:02:04,540 --> 01:02:08,740
Ha de ser capaç d'entendre l'ús de dos punters,

807
01:02:08,740 --> 01:02:11,660
i aquesta és una solució més neta.

808
01:02:11,660 --> 01:02:16,090
A més, observi que, què passa si el meu arbre -

809
01:02:16,090 --> 01:02:24,480
Què passa si el meu arrel era nul? Què passa si no faig aquest cas aquí?

810
01:02:24,480 --> 01:02:30,540
Així node * root = NULL, inserir i 4 a l'arrel.

811
01:02:30,540 --> 01:02:35,110
Què és l'arrel serà després d'això?

812
01:02:35,110 --> 01:02:37,470
[Estudiant, inintel · ligible] >> Si.

813
01:02:37,470 --> 01:02:41,710
Valor de l'arrel serà 4.

814
01:02:41,710 --> 01:02:45,510
Arrel esquerra serà nul, dret fonamental serà nul.

815
01:02:45,510 --> 01:02:49,490
En el cas en què no va passar arran de direcció,

816
01:02:49,490 --> 01:02:52,490
no podíem modificar arrel.

817
01:02:52,490 --> 01:02:56,020
En el cas que l'arbre - on l'arrel era nul,

818
01:02:56,020 --> 01:02:58,410
ens vam haver tornar false. No hi ha res que poguéssim fer.

819
01:02:58,410 --> 01:03:01,520
No es pot inserir un node en un arbre buit.

820
01:03:01,520 --> 01:03:06,810
Però ara sí, acabem de fer un arbre buit en un arbre d'un node.

821
01:03:06,810 --> 01:03:13,400
La qual cosa és generalment la manera esperada que se suposa que ha de funcionar.

822
01:03:13,400 --> 01:03:21,610
>> A més, aquest és significativament més curt que

823
01:03:21,610 --> 01:03:26,240
també fer el seguiment dels pares, i pel que iterar cap avall tot el camí.

824
01:03:26,240 --> 01:03:30,140
Ara tinc al meu pare, i jo només tinc la meva punter dret del pare al que sigui.

825
01:03:30,140 --> 01:03:35,640
En canvi, si fem això iterativa, que seria la mateixa idea amb un bucle while.

826
01:03:35,640 --> 01:03:38,100
Però en lloc d'haver de bregar amb el meu pare punter,

827
01:03:38,100 --> 01:03:40,600
meu lloc actual del punter seria el

828
01:03:40,600 --> 01:03:43,790
que estic modificant directament per apuntar al meu nou node.

829
01:03:43,790 --> 01:03:46,090
Jo no he de bregar amb el fet que apunta cap a l'esquerra.

830
01:03:46,090 --> 01:03:48,810
Jo no he de bregar amb el fet que apunta cap a la dreta.

831
01:03:48,810 --> 01:04:00,860
És només el que aquest indicador és que em vaig a fixar perquè apunti al meu nou node.

832
01:04:00,860 --> 01:04:05,740
Tothom entén com funciona?

833
01:04:05,740 --> 01:04:09,460
Si no és així, per què volem fer-ho d'aquesta manera,

834
01:04:09,460 --> 01:04:14,920
però almenys que això funciona com una solució?

835
01:04:14,920 --> 01:04:17,110
[Estudiant] On return true?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Això és probablement just aquí.

837
01:04:21,550 --> 01:04:26,690
Si s'insereix correctament, retorna true.

838
01:04:26,690 --> 01:04:32,010
Si no, aquí anem a voler tornar al que sigui retorns d'inserció.

839
01:04:32,010 --> 01:04:35,950
>> I què té d'especial aquesta funció recursiva?

840
01:04:35,950 --> 01:04:43,010
És la cua recursiva, de manera que mentre es compila amb una mica d'optimització,

841
01:04:43,010 --> 01:04:48,060
reconeixerà i que mai es té un desbordament de pila d'això,

842
01:04:48,060 --> 01:04:53,230
fins i tot si el nostre arbre té una alçada de 10.000 milions o 10.

843
01:04:53,230 --> 01:04:55,630
[Estudiant, inintel · ligible]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Crec que ho fa a Dash - o quin nivell d'optimització

845
01:05:00,310 --> 01:05:03,820
es requereix per a una recursió de cua per ser reconegut.

846
01:05:03,820 --> 01:05:09,350
Crec que el reconeix - GCC i Clang

847
01:05:09,350 --> 01:05:12,610
També tenen diferents significats per als seus nivells d'optimització.

848
01:05:12,610 --> 01:05:17,870
Vull dir que és DashO 2, per assegurar-se que es reconegui la recursió de cua.

849
01:05:17,870 --> 01:05:27,880
Però - es pot construir com un exemple Fibonocci o alguna cosa així.

850
01:05:27,880 --> 01:05:30,030
No és fàcil de provar amb això, perquè és difícil construir

851
01:05:30,030 --> 01:05:32,600
un arbre binari que és tan gran.

852
01:05:32,600 --> 01:05:37,140
Però sí, crec que és DashO 2, que

853
01:05:37,140 --> 01:05:40,580
si es compila amb DashO 2, es buscarà la recursió de cua

854
01:05:40,580 --> 01:05:54,030
i optimitzar això.

855
01:05:54,030 --> 01:05:58,190
Tornem a - inserir, literalment, l'última cosa que necessita.

856
01:05:58,190 --> 01:06:04,900
Tornem a la inserció d'aquí

857
01:06:04,900 --> 01:06:07,840
on farem la mateixa idea.

858
01:06:07,840 --> 01:06:14,340
Encara tindrem el defecte de no ser capaç de manejar tot

859
01:06:14,340 --> 01:06:17,940
quan la mateixa arrel és nul, o el passat entrada és nul,

860
01:06:17,940 --> 01:06:20,060
però en lloc de tractar amb un punter pare,

861
01:06:20,060 --> 01:06:27,430
anem a aplicar la mateixa lògica dels punters a punters de manteniment.

862
01:06:27,430 --> 01:06:35,580
Si aquí seguim el nostre node ** cursos,

863
01:06:35,580 --> 01:06:37,860
i no és necessari fer un seguiment de la dreta més,

864
01:06:37,860 --> 01:06:47,190
però node ** act = & arbre.

865
01:06:47,190 --> 01:06:54,800
I ara el nostre bucle while serà mentre act * no nul · la de igualtat.

866
01:06:54,800 --> 01:07:00,270
No cal fer un seguiment dels pares més.

867
01:07:00,270 --> 01:07:04,180
No cal fer un seguiment d'esquerra i dreta.

868
01:07:04,180 --> 01:07:10,190
I ho vaig a trucar a la temperatura, perquè ja estem fent servir temp.

869
01:07:10,190 --> 01:07:17,200
Bé. Així que si (valor> * temp),

870
01:07:17,200 --> 01:07:24,010
i llavors (* temp) -> dreta

871
01:07:24,010 --> 01:07:29,250
més temp = & (* temp) -> a l'esquerra.

872
01:07:29,250 --> 01:07:32,730
I ara, en aquest punt, després d'aquest bucle while,

873
01:07:32,730 --> 01:07:36,380
Jo només faig això perquè potser és més fàcil pensar en forma iterativa de forma recursiva,

874
01:07:36,380 --> 01:07:39,010
però després d'aquest bucle while,

875
01:07:39,010 --> 01:07:43,820
* Temp és el punter que desitja canviar.

876
01:07:43,820 --> 01:07:48,960
>> Abans de tenir pares, i volíem canviar cap a l'esquerra pare o pares dreta,

877
01:07:48,960 --> 01:07:51,310
però si volem canviar drets dels pares,

878
01:07:51,310 --> 01:07:54,550
llavors és correcte * temp pare, i podem canviar directament.

879
01:07:54,550 --> 01:08:05,860
Així que aquí, podem fer * temp = nodo_nuevo, i això és tot.

880
01:08:05,860 --> 01:08:09,540
Així que avís, tot el que vam fer en aquesta era treure línies de codi.

881
01:08:09,540 --> 01:08:14,770
Per tal de seguir la pista de la matriu en tot el que és esforç addicional.

882
01:08:14,770 --> 01:08:18,689
En aquest cas, si tan sols no perdre de vista el punter al punter,

883
01:08:18,689 --> 01:08:22,990
i fins i tot si volia desfer-se de totes aquestes claus ara,

884
01:08:22,990 --> 01:08:27,170
fer que es vegi més curt.

885
01:08:27,170 --> 01:08:32,529
Aquesta és la mateixa solució exacta,

886
01:08:32,529 --> 01:08:38,210
però menys línies de codi.

887
01:08:38,210 --> 01:08:41,229
Un cop de començar a reconèixer això com una solució vàlida,

888
01:08:41,229 --> 01:08:43,529
també és més fàcil de raonar sobre que com, bé,

889
01:08:43,529 --> 01:08:45,779
Per què tinc aquesta bandera a la dreta int?

890
01:08:45,779 --> 01:08:49,290
Què significa això? Oh, està significant que

891
01:08:49,290 --> 01:08:51,370
cada vegada que vagi a la dreta, he de posar,

892
01:08:51,370 --> 01:08:53,819
else if I a l'esquerra he de posar-lo a zero.

893
01:08:53,819 --> 01:09:04,060
En aquest cas, no tinc la raó en això, és més fàcil que pensar.

894
01:09:04,060 --> 01:09:06,710
Preguntes?

895
01:09:06,710 --> 01:09:16,290
[Estudiant, inintel · ligible] >> Si.

896
01:09:16,290 --> 01:09:23,359
Està bé, així que en l'últim -

897
01:09:23,359 --> 01:09:28,080
Suposo que una funció ràpida i fàcil que podem fer és,

898
01:09:28,080 --> 01:09:34,910
let 's - junt, crec, tractar d'escriure una funció contains

899
01:09:34,910 --> 01:09:38,899
que no li importa si es tracta d'un arbre de cerca binària.

900
01:09:38,899 --> 01:09:43,770
Conté funció ha de retornar true

901
01:09:43,770 --> 01:09:58,330
si qualsevol part d'aquest arbre binari general és el valor que està buscant.

902
01:09:58,330 --> 01:10:02,520
Així que primer anem a fer-ho de forma recursiva i després ho farem iterativa.

903
01:10:02,520 --> 01:10:07,300
De fet, podem simplement fer-ho junts, perquè això serà molt curta.

904
01:10:07,300 --> 01:10:11,510
>> Quina és la meva hipòtesi de base serà?

905
01:10:11,510 --> 01:10:13,890
[Estudiant, inintel · ligible]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Així que si (arbre == NULL), llavors què?

907
01:10:18,230 --> 01:10:22,740
[Estudiant] Tornar fals.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Si no, bé, jo no necessito l'altre.

909
01:10:26,160 --> 01:10:30,250
Si va ser el meu cas una altra base.

910
01:10:30,250 --> 01:10:32,450
Valor [Estudiant] Tree? Sí >>.

911
01:10:32,450 --> 01:10:36,430
Així que si (arbre-> value value ==.

912
01:10:36,430 --> 01:10:39,920
Tingueu en compte que estem de tornada a * node no, node ** s?

913
01:10:39,920 --> 01:10:42,990
Conté no haurà de fer servir un ** nodes,

914
01:10:42,990 --> 01:10:45,480
ja que no estem modificant punters.

915
01:10:45,480 --> 01:10:50,540
Estem travessant ells.

916
01:10:50,540 --> 01:10:53,830
Si això succeeix, llavors volem tornar realitat.

917
01:10:53,830 --> 01:10:58,270
Altres vendes que volem recórrer els nens.

918
01:10:58,270 --> 01:11:02,620
Així que no podem raonar sobre si tot a l'esquerra és menor

919
01:11:02,620 --> 01:11:05,390
i tot a la dreta és major.

920
01:11:05,390 --> 01:11:09,590
Llavors, quin és el nostre estat estarà aquí - o, què farem?

921
01:11:09,590 --> 01:11:11,840
[Estudiant, inintel · ligible] >> Si.

922
01:11:11,840 --> 01:11:17,400
Tornar conté (valor, arbre-> esquerre)

923
01:11:17,400 --> 01:11:26,860
o conté (valor, arbre-> dreta). I això és tot.

924
01:11:26,860 --> 01:11:29,080
I compte que hi ha algun tipus d'avaluació de curt circuit,

925
01:11:29,080 --> 01:11:32,520
on si ens toca trobar el valor en l'arbre de l'esquerra,

926
01:11:32,520 --> 01:11:36,820
que mai necessitem mirar l'arbre de la dreta.

927
01:11:36,820 --> 01:11:40,430
Aquesta és la funció sencera.

928
01:11:40,430 --> 01:11:43,690
Ara farem iterativament,

929
01:11:43,690 --> 01:11:48,060
que serà menys agradable.

930
01:11:48,060 --> 01:11:54,750
Anem a prendre la sortida habitual de node * act = arbre.

931
01:11:54,750 --> 01:12:03,250
Mentre (act! = NULL).

932
01:12:03,250 --> 01:12:08,600
Ràpidament veurem un problema.

933
01:12:08,600 --> 01:12:12,250
Si act - aquí, si mai sortir d'això,

934
01:12:12,250 --> 01:12:16,020
llavors ens hem quedat sense coses a veure, pel que retorna fals.

935
01:12:16,020 --> 01:12:24,810
Si (act-> valor value ==), retorna true.

936
01:12:24,810 --> 01:12:32,910
Així que ara, estem en un lloc -

937
01:12:32,910 --> 01:12:36,250
no sabem si volem anar a l'esquerra oa la dreta.

938
01:12:36,250 --> 01:12:44,590
Per tant arbitràriament, anirem a l'esquerra.

939
01:12:44,590 --> 01:12:47,910
Òbviament he topat amb un problema en el qual m'he abandonat del tot tot -

940
01:12:47,910 --> 01:12:50,760
Només vaig a comprovar sempre el costat esquerre d'un arbre.

941
01:12:50,760 --> 01:12:56,050
Mai es comprovi tot el que és un fill dret a res.

942
01:12:56,050 --> 01:13:00,910
Com puc solucionar aquest problema?

943
01:13:00,910 --> 01:13:05,260
[Estudiant] Cal seguir la pista de l'esquerra i la dreta en una pila.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Així que anem a fer-ho

945
01:13:13,710 --> 01:13:32,360
struct llista node * n, i després node ** següent?

946
01:13:32,360 --> 01:13:40,240
Jo crec que funciona bé.

947
01:13:40,240 --> 01:13:45,940
Volem anar per l'esquerra o let 's - fins aquí.

948
01:13:45,940 --> 01:13:54,350
Struct = llista de la llista, que començarà

949
01:13:54,350 --> 01:13:58,170
a terme en aquesta llista struct.

950
01:13:58,170 --> 01:14:04,040
* Llista = NULL. Així que serà la nostra llista enllaçada

951
01:14:04,040 --> 01:14:08,430
de subarbres que hem saltat.

952
01:14:08,430 --> 01:14:13,800
Anem a travessar l'esquerra ara,

953
01:14:13,800 --> 01:14:17,870
però és inevitable que hagi de tornar a la dreta,

954
01:14:17,870 --> 01:14:26,140
Anem a mantenir el costat dret dins la nostra llista d'estructura.

955
01:14:26,140 --> 01:14:32,620
Llavors tindrem new_list o estructura,

956
01:14:32,620 --> 01:14:41,080
struct llista *, new_list = malloc (sizeof (llista)).

957
01:14:41,080 --> 01:14:44,920
Vaig a passar per alt la comprovació d'errors, però vostè ha de comprovar per veure si és nul.

958
01:14:44,920 --> 01:14:50,540
New_list el node que va a apuntar a -

959
01:14:50,540 --> 01:14:56,890
oh, és per això que ho volia aquí. Es va a apuntar a una llista struct segon.

960
01:14:56,890 --> 01:15:02,380
Així és com el treball vinculat llistes.

961
01:15:02,380 --> 01:15:04,810
Aquest és el mateix com una llista vinculada int

962
01:15:04,810 --> 01:15:06,960
excepte només estem reemplaçant amb int * node.

963
01:15:06,960 --> 01:15:11,040
És exactament el mateix.

964
01:15:11,040 --> 01:15:15,100
Així new_list, el valor del nostre node new_list,

965
01:15:15,100 --> 01:15:19,120
serà actualment> dreta.

966
01:15:19,120 --> 01:15:24,280
El valor de la nostra new_list-> següent serà la nostra llista original,

967
01:15:24,280 --> 01:15:30,760
i després anem a actualitzar la nostra llista per apuntar a new_list.

968
01:15:30,760 --> 01:15:33,650
>> Ara necessitem algun tipus de forma de les coses que tiren,

969
01:15:33,650 --> 01:15:37,020
com hem travessat el subarbre esquerre sencer.

970
01:15:37,020 --> 01:15:40,480
Ara hem de tirar coses fora,

971
01:15:40,480 --> 01:15:43,850
com act és nul, no volem tornar simplement fals.

972
01:15:43,850 --> 01:15:50,370
Volem tirar ara fora de la nostra nova llista.

973
01:15:50,370 --> 01:15:53,690
Una manera convenient de fer això - bé, en realitat, hi ha diverses maneres de fer això.

974
01:15:53,690 --> 01:15:56,680
Algú té algun suggeriment?

975
01:15:56,680 --> 01:15:58,790
On he de fer això o com ho he de fer?

976
01:15:58,790 --> 01:16:08,010
Només tenim un parell de minuts, però qualsevol suggeriment?

977
01:16:08,010 --> 01:16:14,750
En lloc de - d'una manera, en comptes de la nostra condició de ser temps,

978
01:16:14,750 --> 01:16:17,090
el que estem mirant no és nul,

979
01:16:17,090 --> 01:16:22,340
en lloc d'això continuarem per anar fins a la nostra llista en si és nul.

980
01:16:22,340 --> 01:16:25,680
Així que si la nostra llista acaba sent nul,

981
01:16:25,680 --> 01:16:30,680
llavors ens hem quedat sense coses que ha de buscar, a buscar un altre.

982
01:16:30,680 --> 01:16:39,860
Però això vol dir que el primer a la nostra llista és només serà el primer node.

983
01:16:39,860 --> 01:16:49,730
El primer serà - ja no hem de veure això.

984
01:16:49,730 --> 01:16:58,710
Així llista-> n serà el nostre arbre.

985
01:16:58,710 --> 01:17:02,860
llista-> següent serà nul.

986
01:17:02,860 --> 01:17:07,580
I ara, mentre que la llista no nul · la de igualtat.

987
01:17:07,580 --> 01:17:11,610
Cur traurà alguna cosa de la nostra llista.

988
01:17:11,610 --> 01:17:13,500
Així act serà igual list-> núm.

989
01:17:13,500 --> 01:17:20,850
I llavors llista serà igual list-> n, o llista-> següent.

990
01:17:20,850 --> 01:17:23,480
Així que si el valor és igual al valor actual.

991
01:17:23,480 --> 01:17:28,790
Ara podem afegir tant els nostres com punter dret i el nostre punter esquerre

992
01:17:28,790 --> 01:17:32,900
sempre que no és nul.

993
01:17:32,900 --> 01:17:36,390
Aquí baix, suposo que hauríem d'haver fet això en primer lloc.

994
01:17:36,390 --> 01:17:44,080
Si (act-> bé! = NULL)

995
01:17:44,080 --> 01:17:56,380
llavors anem a inserir el node a la llista.

996
01:17:56,380 --> 01:17:59,290
Si (act-> esquerra), es tracta d'una mica de treball extra, però està bé.

997
01:17:59,290 --> 01:18:02,690
Si (act-> esquerra! = NULL),

998
01:18:02,690 --> 01:18:14,310
i anem a inserir a l'esquerra a la nostra llista enllaçada,

999
01:18:14,310 --> 01:18:19,700
i que hauria de ser.

1000
01:18:19,700 --> 01:18:22,670
Ens iterar - sempre que tenim alguna cosa a la nostra llista,

1001
01:18:22,670 --> 01:18:26,640
tenim un altre node a la vista.

1002
01:18:26,640 --> 01:18:28,920
Així que ens fixem en aquest node,

1003
01:18:28,920 --> 01:18:31,390
avancem la nostra llista per a la següent.

1004
01:18:31,390 --> 01:18:34,060
Si el node és el valor que busquem, podem tornar realitat.

1005
01:18:34,060 --> 01:18:37,640
Altres vendes inserir dos subarbres nostra esquerra i la dreta,

1006
01:18:37,640 --> 01:18:40,510
sempre que no siguin nuls, a la llista

1007
01:18:40,510 --> 01:18:43,120
de manera que és inevitable anar-hi.

1008
01:18:43,120 --> 01:18:45,160
Així que si no eren nul · les,

1009
01:18:45,160 --> 01:18:47,950
si el nostre punter arrel assenyalar dues coses,

1010
01:18:47,950 --> 01:18:51,670
a continuació, al principi ens va treure alguna cosa de manera que la nostra llista acaba sent nul.

1011
01:18:51,670 --> 01:18:56,890
I després posem dues coses de nou, de manera que ara la nostra llista és de mida 2.

1012
01:18:56,890 --> 01:19:00,030
A continuació, anem a teixir per enrere i només tirarem,

1013
01:19:00,030 --> 01:19:04,250
diguem, el punter esquerre del nostre node arrel.

1014
01:19:04,250 --> 01:19:07,730
I això seguirà passant, anem a acabar recórrer tot.

1015
01:19:07,730 --> 01:19:11,280
>> Observi que això era significativament més complicat

1016
01:19:11,280 --> 01:19:14,160
en la solució recursiva.

1017
01:19:14,160 --> 01:19:17,260
I ja he dit diverses vegades

1018
01:19:17,260 --> 01:19:25,120
que la solució recursiva en general té molt en comú amb la solució iterativa.

1019
01:19:25,120 --> 01:19:30,820
Aquí és exactament el que la solució recursiva està fent.

1020
01:19:30,820 --> 01:19:36,740
L'únic canvi és que en lloc d'utilitzar implícitament la pila, la pila del programa,

1021
01:19:36,740 --> 01:19:40,840
com la seva forma de fer el seguiment de què nodes vostè encara ha de visitar,

1022
01:19:40,840 --> 01:19:45,430
Ara vostè ha d'utilitzar explícitament una llista enllaçada.

1023
01:19:45,430 --> 01:19:49,070
En ambdós casos, vostè està guardant un registre del node encara ha de ser visitat.

1024
01:19:49,070 --> 01:19:51,790
En el cas recursiu és més fàcil perquè una pila

1025
01:19:51,790 --> 01:19:57,100
que s'apliqui a vostè com la pila del programa.

1026
01:19:57,100 --> 01:19:59,550
Observi que aquesta llista enllaçada, és una pila.

1027
01:19:59,550 --> 01:20:01,580
Independentment del que acaba de posar a la pila

1028
01:20:01,580 --> 01:20:09,960
és immediatament el que anem a treure la pila per la propera visita.

1029
01:20:09,960 --> 01:20:14,380
Estem fora de temps, però alguna pregunta?

1030
01:20:14,380 --> 01:20:23,530
[Estudiant, inintel · ligible]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Així que si tenim la nostra llista enllaçada,

1032
01:20:27,790 --> 01:20:30,150
actual es va a apuntar a aquest noi,

1033
01:20:30,150 --> 01:20:34,690
i ara estem avançant al llistat enllaçada per centrar-se en aquest tipus.

1034
01:20:34,690 --> 01:20:44,200
Estem travessant per la llista enllaçada en aquesta línia.

1035
01:20:44,200 --> 01:20:51,200
I llavors crec que hem de alliberar la nostra llista enllaçada i aquestes coses

1036
01:20:51,200 --> 01:20:53,880
una vegada abans de tornar veritable o falsa, hem de

1037
01:20:53,880 --> 01:20:57,360
iterar a través de la nostra llista enllaçada i sempre aquí baix, suposo,

1038
01:20:57,360 --> 01:21:03,900
si act dret no és igual que afegir, de manera que ara volem alliberar

1039
01:21:03,900 --> 01:21:09,600
act perquè, bé, què ens oblidem per complet de la llista? Si.

1040
01:21:09,600 --> 01:21:12,880
Així que això és el que volem fer aquí.

1041
01:21:12,880 --> 01:21:16,730
On és el punter?

1042
01:21:16,730 --> 01:21:23,320
Cur era llavors - volem una llista struct * 10 és igual a la llista següent.

1043
01:21:23,320 --> 01:21:29,240
Llista lliure, list = temp.

1044
01:21:29,240 --> 01:21:32,820
I en el cas que ens retorni true, necessitem iterar

1045
01:21:32,820 --> 01:21:37,050
durant la resta de la nostra llista enllaçada alliberar coses.

1046
01:21:37,050 --> 01:21:39,700
El millor de la solució recursiva és alliberar les coses

1047
01:21:39,700 --> 01:21:44,930
Només significa factorings apareixent de la pila que passarà per vostè.

1048
01:21:44,930 --> 01:21:50,720
Així que hem passat d'una cosa que és com 3 línies de dur-a-pensar-sobre el codi

1049
01:21:50,720 --> 01:21:57,520
a alguna cosa que és significativament molts més difícils de pensament sobre les línies de codi.

1050
01:21:57,520 --> 01:22:00,620
Una mica més preguntes?

1051
01:22:00,620 --> 01:22:08,760
Està bé. Estem bé. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]