1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Sección 7: máis cómodo]

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

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

4
00:00:07,930 --> 00:00:10,110
Todo ben. Entón, como eu dixen no meu correo electrónico,

5
00:00:10,110 --> 00:00:14,060
iso vai ser unha sección binario-tree-intensivo.

6
00:00:14,060 --> 00:00:16,820
Pero non hai que moitas cuestións.

7
00:00:16,820 --> 00:00:18,920
Entón, nós estamos indo a probar extraer de cada pregunta

8
00:00:18,920 --> 00:00:25,430
e entrar en detalles Dolores de todas as mellores formas de facer as cousas.

9
00:00:25,430 --> 00:00:31,200
Así, ao comezo, pasamos por deseños de mostraxe de árbores binarias e outras cousas.

10
00:00:31,200 --> 00:00:35,970
Entón, aquí, "Lembre que unha árbore binaria ten nos semellantes aos dunha lista ligada,

11
00:00:35,970 --> 00:00:38,150
excepto en vez de un punteiro, hai dúas: unha para "neno" á esquerda

12
00:00:38,150 --> 00:00:41,950
e un para a "neno" correcto ".

13
00:00:41,950 --> 00:00:45,630
Así, unha árbore binaria é como unha lista ligada,

14
00:00:45,630 --> 00:00:47,910
excepto a estrutura terá dous punteiros.

15
00:00:47,910 --> 00:00:51,390
Hai árbores trinário, que van ter tres punteiros,

16
00:00:51,390 --> 00:00:56,540
hai N-Ary árbores, que só ten un punteiro xenérico

17
00:00:56,540 --> 00:01:00,320
que entón tes que malloc para ser grande abondo para ter

18
00:01:00,320 --> 00:01:04,840
punteiros suficientes para todos os nenos posibles.

19
00:01:04,840 --> 00:01:08,200
Entón árbore binaria só acontece de ter un número constante de dous.

20
00:01:08,200 --> 00:01:11,260
Se queres, podes dar unha lista encadeada como unha árbore unário,

21
00:01:11,260 --> 00:01:15,360
pero eu non creo que ninguén chama iso.

22
00:01:15,360 --> 00:01:18,060
"Debuxe un diagrama de caixas-e-flechas dun nodo árbore binaria

23
00:01:18,060 --> 00:01:24,110
contén o número favorito de Nate, 7, en que cada punteiro neno é nulo. "

24
00:01:24,110 --> 00:01:27,780
Modo para iPad.

25
00:01:27,780 --> 00:01:30,280
>> Vai ser moi sinxelo.

26
00:01:30,280 --> 00:01:36,150
Nós só imos ter un nó, eu vou deseña-lo como un cadrado.

27
00:01:36,150 --> 00:01:38,730
E eu vou chamar os valores aquí.

28
00:01:38,730 --> 00:01:41,090
Polo tanto, o valor debe ser aquí,

29
00:01:41,090 --> 00:01:44,770
e aquí nós imos ter o punteiro para a esquerda á esquerda e á dereita o punteiro á dereita.

30
00:01:44,770 --> 00:01:50,430
E é moi así convenio para chamalo de esquerda e dereita, os nomes de punteiro.

31
00:01:50,430 --> 00:01:52,460
Ambos van ser nulo.

32
00:01:52,460 --> 00:01:57,870
Isto só vai ser nulo, e que só vai ser nulo.

33
00:01:57,870 --> 00:02:03,630
Okay. Entón, de volta para aquí.

34
00:02:03,630 --> 00:02:05,700
"Con unha lista ligada, tiñamos só para almacenar un punteiro

35
00:02:05,700 --> 00:02:09,639
para o primeiro nodo da lista para lembrar a listaxe ligada, ou toda a lista.

36
00:02:09,639 --> 00:02:11,650
Do mesmo xeito, con árbores, só temos que gardar un punteiro

37
00:02:11,650 --> 00:02:13,420
a un único nodo, a fin de acordar a árbore enteira.

38
00:02:13,420 --> 00:02:15,980
Este nodo é o calle "raíz" da árbore.

39
00:02:15,980 --> 00:02:18,320
Construír sobre o seu diagrama de antes ou deseñar un novo

40
00:02:18,320 --> 00:02:21,690
de tal forma que ten unha representación caixas-e-flechas dunha árbore binaria

41
00:02:21,690 --> 00:02:25,730
co valor 7, a continuación, 3 na parte esquerda,

42
00:02:25,730 --> 00:02:32,760
e despois 9, á dereita, e logo 6, á dereita da extremo 3 ".

43
00:02:32,760 --> 00:02:34,810
Imos ver se eu lembro de todo isto na miña cabeza.

44
00:02:34,810 --> 00:02:37,670
Polo tanto, esta vai ser a nosa raíz aquí.

45
00:02:37,670 --> 00:02:41,600
Nós imos ter un punteiro en algún lugar, algo que chamaremos de raíz,

46
00:02:41,600 --> 00:02:45,140
e está apuntando para este cara.

47
00:02:45,140 --> 00:02:48,490
Agora, para facer un novo nodo,

48
00:02:48,490 --> 00:02:52,870
o que temos, tres á esquerda?

49
00:02:52,870 --> 00:02:57,140
Así, un novo nodo con 3, e apunta inicialmente nula.

50
00:02:57,140 --> 00:02:59,190
Vou poñer N.

51
00:02:59,190 --> 00:03:02,250
Agora queremos facer que vaia á esquerda, de 7.

52
00:03:02,250 --> 00:03:06,840
Entón nós cambiar este punteiro para apuntar agora para este cara.

53
00:03:06,840 --> 00:03:12,420
E nós facemos o mesmo. Queremos un 9 aquí

54
00:03:12,420 --> 00:03:14,620
que, inicialmente, só di nulo.

55
00:03:14,620 --> 00:03:19,600
Nós imos cambiar este punteiro punto, a 9,

56
00:03:19,600 --> 00:03:23,310
e agora queren pór 6 á dereita de 3.

57
00:03:23,310 --> 00:03:32,170
Entón, vai - facer un 6.

58
00:03:32,170 --> 00:03:34,310
E este cara vai apuntar alí.

59
00:03:34,310 --> 00:03:38,320
Okay. Entón, iso é todo o que nos pide para facelo.

60
00:03:38,320 --> 00:03:42,770
>> Agora imos pasar por riba de algunha terminoloxía.

61
00:03:42,770 --> 00:03:46,690
Nós xa falamos sobre como a raíz da árbore é o nó máis alto da árbore.

62
00:03:46,690 --> 00:03:54,720
A unha contendo 7. Os nós na parte inferior da árbore son chamados as follas.

63
00:03:54,720 --> 00:04:01,240
Calquera nodo que só ten nulo como os seus fillos é unha folla.

64
00:04:01,240 --> 00:04:03,680
Por iso, é posible, a nosa árbore binaria é só un único nodo,

65
00:04:03,680 --> 00:04:10,130
que unha árbore é unha folla, e é iso.

66
00:04:10,130 --> 00:04:12,060
"O 'altura' da árbore é o número de saltos que ten que facer

67
00:04:12,060 --> 00:04:16,620
para dende o principio de unha folla. "

68
00:04:16,620 --> 00:04:18,640
Nós imos entrar en un segundo, a diferenza

69
00:04:18,640 --> 00:04:21,940
entre árbores binarias saldadas e non saldadas,

70
00:04:21,940 --> 00:04:29,470
pero, por agora, a altura total da árbore

71
00:04:29,470 --> 00:04:34,520
Eu diría que é 3, aínda que, se contar o número de saltos

72
00:04:34,520 --> 00:04:39,710
tes que facer para obter a 9, entón é realmente só unha altura de 2.

73
00:04:39,710 --> 00:04:43,340
Agora esta é unha árbore binaria non balanceada,

74
00:04:43,340 --> 00:04:49,840
pero nós falamos sobre equilibrada cando se chega a ser relevante.

75
00:04:49,840 --> 00:04:52,040
Entón agora podemos falar sobre nós nunha árbore, en termos

76
00:04:52,040 --> 00:04:54,700
en relación aos outros nós na árbore.

77
00:04:54,700 --> 00:04:59,730
Polo tanto, agora temos os pais, fillos, irmáns, pais e descendentes.

78
00:04:59,730 --> 00:05:05,650
San sentido moi común, o que significan.

79
00:05:05,650 --> 00:05:09,610
Se preguntarmos - e pais.

80
00:05:09,610 --> 00:05:12,830
Entón, o que é o pai de 3?

81
00:05:12,830 --> 00:05:16,090
[Os alumnos] 7. Si >>. O pai vai só para ser o que apunta para ti.

82
00:05:16,090 --> 00:05:20,510
Entón, o que son os nenos de 7?

83
00:05:20,510 --> 00:05:23,860
[Os alumnos] 3 e 9. Si >>.

84
00:05:23,860 --> 00:05:26,460
Teña en conta que "nenos" significa literalmente fillos,

85
00:05:26,460 --> 00:05:31,010
para 6 non se aplica, porque é como un neto.

86
00:05:31,010 --> 00:05:35,540
Pero, entón, se somos descendentes, entón o que son os descendentes de 7?

87
00:05:35,540 --> 00:05:37,500
[Os alumnos] 3, 6 e 9. Si >>.

88
00:05:37,500 --> 00:05:42,330
Os descendentes do nodo raíz vai ser todo na árbore,

89
00:05:42,330 --> 00:05:47,950
excepto, talvez, o nó de raíz en si, se non quere considerar que un descendente.

90
00:05:47,950 --> 00:05:50,750
E, finalmente, os devanceiros, polo que é a dirección oposta.

91
00:05:50,750 --> 00:05:55,740
Entón, cales son os devanceiros de 6?

92
00:05:55,740 --> 00:05:58,920
[Os alumnos] 3 e 7. Si >>. 9 non está incluído.

93
00:05:58,920 --> 00:06:02,520
É só a liñaxe directa de volta á raíz

94
00:06:02,520 --> 00:06:13,230
Vai ser os seus antepasados.

95
00:06:13,230 --> 00:06:16,300
>> "Dicimos que unha árbore binaria é" listada ", para cada nó na árbore,

96
00:06:16,300 --> 00:06:19,530
todos os seus descendentes no lado esquerdo teñen valores menores

97
00:06:19,530 --> 00:06:22,890
e todos os da dereita teñen valores maiores.

98
00:06:22,890 --> 00:06:27,060
Por exemplo, a árbore enriba é ordenada, pero non é o único arranxo posible ordenada. "

99
00:06:27,060 --> 00:06:30,180
Antes de chegar a iso,

100
00:06:30,180 --> 00:06:36,420
unha árbore binaria ordenada é tamén coñecido como unha árbore de busca binaria.

101
00:06:36,420 --> 00:06:38,660
Aquí ocorrer de ser chamado dunha árbore binaria ordenada,

102
00:06:38,660 --> 00:06:41,850
pero eu nunca oín-lo chamado dunha árbore binaria ordenada antes,

103
00:06:41,850 --> 00:06:46,650
e nun quiz que son moito máis propensos a poñer árbore de busca binaria.

104
00:06:46,650 --> 00:06:49,250
Son unha ea mesma cousa,

105
00:06:49,250 --> 00:06:54,580
e é importante que recoñece a distinción entre árbore binaria e árbore de busca binaria.

106
00:06:54,580 --> 00:06:58,830
Unha árbore binaria é só unha árbore que apunta a dúas cousas.

107
00:06:58,830 --> 00:07:02,120
Cada nodo apunta a dúas cousas.

108
00:07:02,120 --> 00:07:06,310
Non hai razoamento sobre os valores que apunta a.

109
00:07:06,310 --> 00:07:11,370
Así como aquí, xa que é unha árbore de busca binaria,

110
00:07:11,370 --> 00:07:14,030
sabemos que se vai cara á esquerda, de 7,

111
00:07:14,030 --> 00:07:16,670
a continuación, todos os valores que poden posiblemente alcanzar

112
00:07:16,670 --> 00:07:19,310
indo deixou de 7 ten que ser inferior a 7.

113
00:07:19,310 --> 00:07:24,070
Nótese que todos os valores menores que 7 son 3 e 6.

114
00:07:24,070 --> 00:07:26,040
Estas son todas á esquerda, de 7.

115
00:07:26,040 --> 00:07:29,020
Ou tamén para a dereita, de 7, todo ten que ser maior que 7,

116
00:07:29,020 --> 00:07:33,220
para 9 é para a dereita, de 7, por iso estamos ben.

117
00:07:33,220 --> 00:07:36,150
Este non é o caso dunha árbore binaria,

118
00:07:36,150 --> 00:07:40,020
para unha árbore binaria estándar, podemos ter só tres no cume, 7 á esquerda,

119
00:07:40,020 --> 00:07:47,630
9 á esquerda, de 7, non hai ningunha ordenación de valores, en absoluto.

120
00:07:47,630 --> 00:07:56,140
Agora, nós realmente non vai facer iso porque é tedioso e innecesario,

121
00:07:56,140 --> 00:07:59,400
pero "tentar deseñar como moitas árbores ordenada como pode pensar

122
00:07:59,400 --> 00:08:01,900
utilizando os números 7, 3, 9 e 6.

123
00:08:01,900 --> 00:08:06,800
Cantos arranxos distintos existen? O que é a altura de cada un? "

124
00:08:06,800 --> 00:08:10,480
>> Nós imos facer unha parella, pero a idea principal é,

125
00:08:10,480 --> 00:08:16,530
é dicir, de ningún xeito unha representación singular dunha árbore binaria conteñen eses valores.

126
00:08:16,530 --> 00:08:22,760
Todo o que necesitamos é unha árbore binaria que contén 7, 3, 6 e 9.

127
00:08:22,760 --> 00:08:25,960
Outra posible válida sería a raíz é 3,

128
00:08:25,960 --> 00:08:30,260
vaia á esquerda e 6, vaia á esquerda e 7,

129
00:08:30,260 --> 00:08:32,730
cara á esquerda e está 9.

130
00:08:32,730 --> 00:08:36,169
Que é unha árbore de busca binaria perfectamente válida.

131
00:08:36,169 --> 00:08:39,570
Non é moi útil, porque é como unha lista ligada

132
00:08:39,570 --> 00:08:43,750
e todos eses punteiros son só nulo.

133
00:08:43,750 --> 00:08:48,900
Pero é unha árbore válido. Si?

134
00:08:48,900 --> 00:08:51,310
[Estudante] Non valores teñen que ser maior do lado dereito?

135
00:08:51,310 --> 00:08:56,700
Ou iso é -? Estes >> eu quixen ir por outro camiño.

136
00:08:56,700 --> 00:09:00,960
Hai tamén - Si, imos cambiar isto.

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

138
00:09:07,770 --> 00:09:11,730
El aínda ten que cumprir o que unha árbore de busca binaria é suposta facer.

139
00:09:11,730 --> 00:09:15,650
Así, todo o que o lado esquerdo debe ser menor que calquera dato nodo.

140
00:09:15,650 --> 00:09:23,180
Nós poderiamos só cambiar, por exemplo, este 6 e poñelas aquí.

141
00:09:23,180 --> 00:09:26,880
Non, non podemos. Por que eu sigo facendo isto?

142
00:09:26,880 --> 00:09:35,350
Imos facer - aquí é 6, aquí é 7, 6 puntos 3.

143
00:09:35,350 --> 00:09:39,290
Esta aínda é unha árbore de busca binaria válido.

144
00:09:39,290 --> 00:09:49,260
O que é malo se eu - imos ver se podo chegar a un acordo.

145
00:09:49,260 --> 00:09:52,280
Si, está ben. Entón, o que está mal con esta árbore?

146
00:09:52,280 --> 00:10:08,920
Eu creo que eu xa lle deu unha información de que hai algo de malo con el.

147
00:10:08,920 --> 00:10:14,430
Por que eu sigo facendo isto?

148
00:10:14,430 --> 00:10:18,510
Okay. Isto parece razoable.

149
00:10:18,510 --> 00:10:22,590
Se olharmos para cada nodo, coma o 7, a continuación, á esquerda da Fig 7 é unha 3.

150
00:10:22,590 --> 00:10:24,960
Polo tanto, temos tres, o único cara á dereita do 3 é un 6.

151
00:10:24,960 --> 00:10:27,750
E se ollar para 6, a cousa á dereita do 6 é un 9.

152
00:10:27,750 --> 00:10:30,910
Entón, por que iso non é unha árbore de busca binaria válida?

153
00:10:30,910 --> 00:10:36,330
[Os alumnos] 9 é aínda a esquerda, de 7. Si >>.

154
00:10:36,330 --> 00:10:43,710
Debe ser certo que todos os valores que poden ser posiblemente alcanzar, indo cara á esquerda, de 7 están a menos de 7.

155
00:10:43,710 --> 00:10:49,120
Ir á esquerda, de 7, temos a 3 e aínda podemos chegar a 6,

156
00:10:49,120 --> 00:10:52,520
aínda podemos chegar a 9, mais por ter pasado menos de 7,

157
00:10:52,520 --> 00:10:55,070
non debe ser capaz de chegar a un número que é maior que 7.

158
00:10:55,070 --> 00:10:59,830
Entón iso non é unha árbore de busca binaria válido.

159
00:10:59,830 --> 00:11:02,330
>> Meu irmán realmente tiña unha pregunta da entrevista

160
00:11:02,330 --> 00:11:07,760
que era basicamente iso, código só algo para validar

161
00:11:07,760 --> 00:11:10,500
unha árbore é unha árbore de busca binaria,

162
00:11:10,500 --> 00:11:13,580
e entón a primeira cousa que fixo foi só comprobar a ver

163
00:11:13,580 --> 00:11:17,020
a esquerda e dereita son correctos, e despois repetir alí en baixo.

164
00:11:17,020 --> 00:11:19,700
Pero non pode simplemente facelo, ten que manter o control

165
00:11:19,700 --> 00:11:22,550
do feito de que, agora que eu fun deixar de 7,

166
00:11:22,550 --> 00:11:26,340
todo neste sub debe ser inferior a 7.

167
00:11:26,340 --> 00:11:28,430
O algoritmo correcto precisa manter o control

168
00:11:28,430 --> 00:11:35,970
dos límites que os valores poden eventualmente caen dentro

169
00:11:35,970 --> 00:11:38,360
Non imos pasar por todos eles.

170
00:11:38,360 --> 00:11:41,630
Hai unha relación de recorrencia agradable,

171
00:11:41,630 --> 00:11:44,810
aínda que non se chegase a eses, ou non imos chegar a estes,

172
00:11:44,810 --> 00:11:47,030
definir cantos realmente son.

173
00:11:47,030 --> 00:11:53,180
Polo tanto, hai 14 deles.

174
00:11:53,180 --> 00:11:56,020
A idea de como faría iso matematicamente é como,

175
00:11:56,020 --> 00:11:59,770
pode escoller calquera única de ser o nodo raíz,

176
00:11:59,770 --> 00:12:03,160
e entón se eu incorporarse de 7 a ser o nodo raíz,

177
00:12:03,160 --> 00:12:08,150
a continuación, hai, por exemplo, algúns números que poden ir ser o meu nó esquerdo,

178
00:12:08,150 --> 00:12:10,440
e hai algúns números que pode ser o meu no dereito,

179
00:12:10,440 --> 00:12:15,090
pero se eu tivera n números totais, o importe que pode ir á esquerda

180
00:12:15,090 --> 00:12:18,820
máis o importe que pode ir á dereita e n - 1.

181
00:12:18,820 --> 00:12:26,130
Así, os números restantes, eles teñen que ser capaces de ir, tanto á esquerda ou cara á dereita.

182
00:12:26,130 --> 00:12:31,580
Parece difícil que, se eu poñer 3 primeiro, entón todo ten que ir á esquerda,

183
00:12:31,580 --> 00:12:35,080
pero se eu poñer 7, entón algunhas cousas poden ir á esquerda e algunhas cousas poden ir cara á dereita.

184
00:12:35,080 --> 00:12:39,570
E por '3 'primeiro eu quería dicir todo pode ir cara á dereita.

185
00:12:39,570 --> 00:12:42,350
É realmente, só tes que pensar niso como,

186
00:12:42,350 --> 00:12:47,980
cantas cousas poden ir no seguinte nivel da árbore.

187
00:12:47,980 --> 00:12:50,420
E vén a ser 14, ou pode debuxar todos eles,

188
00:12:50,420 --> 00:12:54,650
e entón vai ter 14.

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

190
00:13:01,120 --> 00:13:03,510
"Ordenou árbores binarias son legais porque podemos buscar por eles

191
00:13:03,510 --> 00:13:06,910
dunha forma moi semellante á procura dun array ordenado.

192
00:13:06,910 --> 00:13:10,120
Para iso, imos comezar na raíz e traballar nosa maneira para abaixo da árbore

193
00:13:10,120 --> 00:13:13,440
para follas, comprobando os valores de cada nodo contra os valores que estamos a buscar.

194
00:13:13,440 --> 00:13:15,810
Se o valor do nodo actual é menor que o valor que está a buscar,

195
00:13:15,810 --> 00:13:18,050
vai ao lado dereito do neno do nodo.

196
00:13:18,050 --> 00:13:20,030
Se non, vai para o fillo esquerdo do nodo.

197
00:13:20,030 --> 00:13:22,800
Nalgún momento, quere atopar o valor que está a buscar, ou vai executar nun nulo,

198
00:13:22,800 --> 00:13:28,520
indicando o valor non está na árbore. "

199
00:13:28,520 --> 00:13:32,450
Eu teño que redeseñar a árbore que tiña antes, que vai levar un segundo.

200
00:13:32,450 --> 00:13:38,280
Pero queremos mirar para arriba 6, 10, e un está na árbore.

201
00:13:38,280 --> 00:13:49,180
Entón o que era, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Os números que quere ollar para arriba, queremos mirar para arriba 6.

203
00:13:52,730 --> 00:13:55,440
Como funciona este algoritmo?

204
00:13:55,440 --> 00:14:03,040
Ben, tamén temos algúns punteiro raíz para a nosa árbore.

205
00:14:03,040 --> 00:14:12,460
E ir á raíz e dicir, é este valor igual ao valor que estamos buscando?

206
00:14:12,460 --> 00:14:15,000
Entón, nós estamos mirando para 6, polo que non é igual.

207
00:14:15,000 --> 00:14:20,140
Entón, siga indo, e agora podemos dicir, ok, entón 6 é inferior a 7.

208
00:14:20,140 --> 00:14:23,940
Iso quere dicir que queremos ir á esquerda, ou queremos ir para a dereita?

209
00:14:23,940 --> 00:14:27,340
[Estudante] Esquerda. Si >>.

210
00:14:27,340 --> 00:14:33,340
É moito máis doado, todo o que tes que facer é tomar un nó posible da árbore

211
00:14:33,340 --> 00:14:37,760
e entón non - en vez de tratar de pensar na súa cabeza,

212
00:14:37,760 --> 00:14:40,020
Todo ben, se é menos, eu vou para a esquerda ou para ir á dereita,

213
00:14:40,020 --> 00:14:43,030
só de ollar para esta foto, é moi claro que eu teño que ir á esquerda

214
00:14:43,030 --> 00:14:47,700
este nodo é maior que o valor que eu estou buscando.

215
00:14:47,700 --> 00:14:52,600
Entón vai cara á esquerda, agora estou no 3.

216
00:14:52,600 --> 00:14:57,770
Eu quero - 3 é menor que o valor que eu estou a buscar, que é 6.

217
00:14:57,770 --> 00:15:03,420
Entón, vai para a dereita, e agora eu rematar o 6,

218
00:15:03,420 --> 00:15:07,380
que é o valor que eu estou buscando, así que eu voltar true.

219
00:15:07,380 --> 00:15:15,760
O valor que vén eu vou buscar é 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Entón, 10, agora, vai - corte que - vai seguir a raíz.

221
00:15:23,230 --> 00:15:27,670
Agora, 10 vai ser maior que 7, entón eu quero ollar para a dereita.

222
00:15:27,670 --> 00:15:31,660
Vou vir para aquí, 10, vai ser maior que 9,

223
00:15:31,660 --> 00:15:34,520
entón eu vou querer ollar para a dereita.

224
00:15:34,520 --> 00:15:42,100
Eu veño aquí, pero aquí agora estou en nulo.

225
00:15:42,100 --> 00:15:44,170
O que fago se eu acertar nulo?

226
00:15:44,170 --> 00:15:47,440
[Estudante] Voltar falso? Si >>. Eu non atopei 10.

227
00:15:47,440 --> 00:15:49,800
1 vai ser un caso case idéntico,

228
00:15:49,800 --> 00:15:51,950
excepto que el só vai ser invertida, en vez de ollar

229
00:15:51,950 --> 00:15:56,540
para o lado dereito, eu vou mirar para o lado esquerdo.

230
00:15:56,540 --> 00:16:00,430
>> Agora eu creo que nós realmente chegar ao código.

231
00:16:00,430 --> 00:16:04,070
Aquí é onde - abra o aparello CS50 e navegar no seu camiño,

232
00:16:04,070 --> 00:16:07,010
pero pode tamén facelo só no espazo.

233
00:16:07,010 --> 00:16:09,170
Probablemente é ideal para facelo no espazo,

234
00:16:09,170 --> 00:16:13,760
porque podemos traballar no espazo.

235
00:16:13,760 --> 00:16:19,170
"Primeiro imos ter unha nova definición de tipo para un nodo árbore binario que contén valores int.

236
00:16:19,170 --> 00:16:21,400
Usando o boilerplate typedef abaixo,

237
00:16:21,400 --> 00:16:24,510
crear unha nova definición de tipo para un nodo nunha árbore binaria.

238
00:16:24,510 --> 00:16:27,930
Se queda preso. . . "Bla, bla, bla. Okay.

239
00:16:27,930 --> 00:16:30,380
Entón, imos poñer o cliché aquí,

240
00:16:30,380 --> 00:16:41,630
nó typedef struct, e no. Si, está ben.

241
00:16:41,630 --> 00:16:44,270
Entón, cales son os campos que imos querer no noso nodo?

242
00:16:44,270 --> 00:16:46,520
[Estudante] Int e despois dous punteiros?

243
00:16:46,520 --> 00:16:49,700
>> Valor Int, dous punteiros? ¿Como escribir os punteiros?

244
00:16:49,700 --> 00:16:58,440
[Estudante] struct. >> Eu debería facer zoom in Si, entón no struct * esquerda,

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

246
00:17:01,320 --> 00:17:03,460
E lembre-se a discusión da última vez,

247
00:17:03,460 --> 00:17:15,290
que iso non ten sentido, iso non ten sentido,

248
00:17:15,290 --> 00:17:18,270
iso non ten sentido.

249
00:17:18,270 --> 00:17:25,000
Debe de todo o que hai para definir esa estrutura recursiva.

250
00:17:25,000 --> 00:17:27,970
Ok, entón é iso que a nosa árbore vai quedar.

251
00:17:27,970 --> 00:17:37,670
Se fixésemos unha árbore trinário, a continuación, un nó pode parecer B1, B2, struct node * B3,

252
00:17:37,670 --> 00:17:43,470
onde b é unha rama - na verdade, eu teño máis oído á esquerda, medio, á dereita, o que quere pero.

253
00:17:43,470 --> 00:17:55,610
Nós só se preocupan binario, cara a dereita, esquerda.

254
00:17:55,610 --> 00:17:59,110
"Agora declarar unha variable * mundial no a raíz da árbore."

255
00:17:59,110 --> 00:18:01,510
Entón, nós non imos facelo.

256
00:18:01,510 --> 00:18:08,950
Co fin de facer as cousas un pouco máis difícil e máis xeneralizado,

257
00:18:08,950 --> 00:18:11,570
non teremos unha variable no global.

258
00:18:11,570 --> 00:18:16,710
En vez diso, o principal que pode declarar todas as nosas cousas de nós,

259
00:18:16,710 --> 00:18:20,500
e iso significa que a continuación, cando comezar a correr

260
00:18:20,500 --> 00:18:23,130
nosa función contén ea nosa función de inserción,

261
00:18:23,130 --> 00:18:27,410
en vez dos nosos contén función só usando esa variable no global,

262
00:18:27,410 --> 00:18:34,280
Nós imos ter que tomar como un argumento a árbore que queremos que procesar.

263
00:18:34,280 --> 00:18:36,650
Tendo a variable global era para facilitar as cousas.

264
00:18:36,650 --> 00:18:42,310
Nós imos facer as cousas máis difíciles.

265
00:18:42,310 --> 00:18:51,210
Agora tome un minuto só para facer este tipo de cousas,

266
00:18:51,210 --> 00:18:57,690
onde dentro principal que pretende crear esta árbore, e iso é todo o que quere facer.

267
00:18:57,690 --> 00:19:04,530
Tentar construír esta árbore na súa función principal.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Así, non é preciso nin ter construído a árbore de todo o camiño aínda.

269
00:19:47,610 --> 00:19:49,840
Pero alguén ten algo que eu podería tirar para arriba

270
00:19:49,840 --> 00:20:03,130
para mostrar como se podería comezar a construír esa árbore?

271
00:20:03,130 --> 00:20:08,080
[Estudante] bater de alguén, tentando saír.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Calquera cómodo coa súa construción a árbore?

273
00:20:13,100 --> 00:20:15,520
[Estudante] Claro. Non está feito. >> Está todo ben. Podemos só rematar -

274
00:20:15,520 --> 00:20:26,860
Oh, vostede pode garda-lo? Hooray.

275
00:20:26,860 --> 00:20:32,020
Polo tanto, temos aquí - Oh, eu estou un pouco cortados.

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

277
00:20:34,770 --> 00:20:37,730
Aumentar o zoom, rolar para fóra. >> Eu teño unha pregunta. >> Si?

278
00:20:37,730 --> 00:20:44,410
[Estudante] Cando define estrutura, son cousas como inicializar a algo?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Non >> Okay. Entón tería que iniciar -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Non Cando definir, ou cando declarar unha estrutura,

281
00:20:50,450 --> 00:20:55,600
non é inicializar por defecto, que é exactamente como se declarar un int.

282
00:20:55,600 --> 00:20:59,020
É exactamente a mesma cousa. É coma se cada un dos seus campos individuais

283
00:20:59,020 --> 00:21:04,460
pode ter un valor de lixo na mesma. >> E é posible definir - ou declarar unha struct

284
00:21:04,460 --> 00:21:07,740
de forma que non arrinque-la?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Si Entón, sintaxe de inicio atallo

286
00:21:13,200 --> 00:21:18,660
vai parecer -

287
00:21:18,660 --> 00:21:22,200
Hai dúas formas de facelo. Creo que debemos recompila-lo

288
00:21:22,200 --> 00:21:25,840
para facer Clang seguro tamén fai iso.

289
00:21:25,840 --> 00:21:28,510
A orde de argumentos que vén na estrutura,

290
00:21:28,510 --> 00:21:32,170
puxo como a orde dos argumentos dentro destas claves.

291
00:21:32,170 --> 00:21:35,690
Entón, se quere iniciar a 9 e deixou ser nulo e despois á dereita ser nulo,

292
00:21:35,690 --> 00:21:41,570
sería 9, null, null.

293
00:21:41,570 --> 00:21:47,890
A alternativa é, eo editor non lle gusta esta sintaxe,

294
00:21:47,890 --> 00:21:50,300
e el pensa que quero un novo bloque,

295
00:21:50,300 --> 00:22:01,800
pero a alternativa é algo así como -

296
00:22:01,800 --> 00:22:04,190
aquí, eu vou poñelas nunha nova liña.

297
00:22:04,190 --> 00:22:09,140
Pode dicir explicitamente, eu esquezo a sintaxe exacta.

298
00:22:09,140 --> 00:22:13,110
Así, pode abordar explícitamente os polo nome, e dicir:

299
00:22:13,110 --> 00:22:21,570
. Valor c ou. = 9. = NULL esquerda.

300
00:22:21,570 --> 00:22:24,540
Estou supoñendo que estes precisan ser comas.

301
00:22:24,540 --> 00:22:29,110
. Dereito = NULL, así desta forma non

302
00:22:29,110 --> 00:22:33,780
realmente precisa saber a orde da estrutura,

303
00:22:33,780 --> 00:22:36,650
e cando está lendo isto, é moito máis explícito

304
00:22:36,650 --> 00:22:41,920
sobre o que o valor está inicializar a.

305
00:22:41,920 --> 00:22:44,080
>> Isto acontece por ser unha das cousas que -

306
00:22:44,080 --> 00:22:49,100
así, a maior parte, C + + é un superconjunto de C.

307
00:22:49,100 --> 00:22:54,160
Pode incorporarse o código C, mover para C + +, e debe compilar.

308
00:22:54,160 --> 00:22:59,570
Esta é unha das cousas que o C + + non soporta, para que as persoas tenden a non facelo.

309
00:22:59,570 --> 00:23:01,850
Eu non sei se esa é a única razón pola que as persoas tenden a non facelo,

310
00:23:01,850 --> 00:23:10,540
pero o caso en que eu precisaba usalo necesario para traballar con C + + e así eu non podería usar isto.

311
00:23:10,540 --> 00:23:14,000
Outro exemplo de algo que non funciona co C + + é

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

313
00:23:16,940 --> 00:23:20,200
pero pode só dicir o que quere que char * x = malloc,

314
00:23:20,200 --> 00:23:22,840
e será convertido automaticamente para un char *.

315
00:23:22,840 --> 00:23:25,450
Ese reparto automático non acontece en C + +.

316
00:23:25,450 --> 00:23:28,150
Isto non sería compilar, e cómpre dicir explicitamente

317
00:23:28,150 --> 00:23:34,510
char *, malloc, calquera que sexa, para lanza-lo para un char *.

318
00:23:34,510 --> 00:23:37,270
Non hai moitas cousas que C e C + + discordan,

319
00:23:37,270 --> 00:23:40,620
pero estes son dous.

320
00:23:40,620 --> 00:23:43,120
Entón imos con esta sintaxe.

321
00:23:43,120 --> 00:23:46,150
Pero aínda que non fose con esa sintaxe,

322
00:23:46,150 --> 00:23:49,470
o que é - pode estar mal con iso?

323
00:23:49,470 --> 00:23:52,170
[Estudante] Eu non teño eliminar a referencia é? Si >>.

324
00:23:52,170 --> 00:23:55,110
Lembre-se de que a frecha ten unha dereference implícito,

325
00:23:55,110 --> 00:23:58,230
e así, cando estamos lidando só con unha estrutura,

326
00:23:58,230 --> 00:24:04,300
queremos usar. para chegar a unha dentro do campo da estrutura.

327
00:24:04,300 --> 00:24:07,200
E a única vez que use a frecha é cando queremos facer -

328
00:24:07,200 --> 00:24:13,450
ben, a frecha é equivalente á -

329
00:24:13,450 --> 00:24:17,020
iso é o que significaría se eu usase frecha.

330
00:24:17,020 --> 00:24:24,600
Todos os medios de frecha e, dereference iso, agora estou nunha estrutura, e podo obter o campo.

331
00:24:24,600 --> 00:24:28,040
Ou obter o campo directamente ou dereference e obter o campo -

332
00:24:28,040 --> 00:24:30,380
Eu creo que este debe ser o valor.

333
00:24:30,380 --> 00:24:33,910
Pero aquí estou lidando con só unha estrutura, non un punteiro para unha estrutura,

334
00:24:33,910 --> 00:24:38,780
e por iso non pode usar a frecha.

335
00:24:38,780 --> 00:24:47,510
Pero este tipo de cousas que podemos facer para todos nós.

336
00:24:47,510 --> 00:24:55,790
Oh, meu Deus.

337
00:24:55,790 --> 00:25:09,540
Isto é de 6, 7 e 3.

338
00:25:09,540 --> 00:25:16,470
Entón, podemos definir os ramos na nosa árbore, podemos ter 7 -

339
00:25:16,470 --> 00:25:21,650
Podemos ter a súa esquerda debe apuntar a 3.

340
00:25:21,650 --> 00:25:25,130
Entón, como imos facer iso?

341
00:25:25,130 --> 00:25:29,320
[Estudantes, inintelixible] >> si. O enderezo do node3,

342
00:25:29,320 --> 00:25:34,170
e se non ten enderezo, el só non sería compilar.

343
00:25:34,170 --> 00:25:38,190
Pero lembre que estes son os punteiros para os nos próximos.

344
00:25:38,190 --> 00:25:44,930
O dereito debe apuntar a 9,

345
00:25:44,930 --> 00:25:53,330
e 3 debe apuntar sobre o dereito á 6.

346
00:25:53,330 --> 00:25:58,480
Creo que iso é todo listo. Calquera comentarios ou preguntas?

347
00:25:58,480 --> 00:26:02,060
[Estudante, inintelixible] A raíz vai ser 7.

348
00:26:02,060 --> 00:26:08,210
Podemos só dicir no * PTR =

349
00:26:08,210 --> 00:26:14,160
ou raíz, = node7.

350
00:26:14,160 --> 00:26:20,730
>> Para os nosos propósitos, imos estar lidando coa inserción,

351
00:26:20,730 --> 00:26:25,490
entón imos querer escribir unha función para introducir esta árbore binaria

352
00:26:25,490 --> 00:26:34,230
e inserción é, inevitablemente, vai chamar malloc para crear un novo nodo a esta árbore.

353
00:26:34,230 --> 00:26:36,590
Así, as cousas van estar confuso co feito de que algúns nós

354
00:26:36,590 --> 00:26:38,590
Están na pila

355
00:26:38,590 --> 00:26:43,680
e outros imos acabar na pila cando inserir-los.

356
00:26:43,680 --> 00:26:47,640
Isto é perfectamente válido, pero a única razón

357
00:26:47,640 --> 00:26:49,600
Nós somos capaces de facelo na pila

358
00:26:49,600 --> 00:26:51,840
é porque é un exemplo tan artificial que sabemos

359
00:26:51,840 --> 00:26:56,360
A árbore é suposta ser construído como 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Se non ten iso, entón non teriamos a malloc en primeiro lugar.

361
00:27:02,970 --> 00:27:06,160
Como veremos un pouco máis tarde, debemos ser malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Agora é perfectamente razoable para poñer na pila,

363
00:27:08,570 --> 00:27:14,750
pero imos cambiar isto para unha aplicación de malloc.

364
00:27:14,750 --> 00:27:17,160
Entón, cada un deles agora vai ser algo así como

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

366
00:27:24,240 --> 00:27:28,040
E agora imos ter que facer a nosa selección.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Eu non quería que iso -

368
00:27:34,010 --> 00:27:40,950
voltar 1, e entón podemos facer node9-> porque agora é un punteiro,

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

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

371
00:27:48,930 --> 00:27:51,410
e nós imos ter que facer isto para cada un deses nós.

372
00:27:51,410 --> 00:27:57,490
Entón, en vez diso, imos poñelas dentro dunha función separada.

373
00:27:57,490 --> 00:28:00,620
Imos chamalo de nodo * build_node,

374
00:28:00,620 --> 00:28:09,050
e iso é un pouco semellante ao APIs nós fornecen para codificación de Huffman.

375
00:28:09,050 --> 00:28:12,730
Nós dámoslle funcións inicializador para unha árbore

376
00:28:12,730 --> 00:28:20,520
e desconstrutor "funcións" para as árbores e os mesmos para os bosques.

377
00:28:20,520 --> 00:28:22,570
>> Entón aquí imos ter unha función de arranque

378
00:28:22,570 --> 00:28:25,170
só construír un nó para nós.

379
00:28:25,170 --> 00:28:29,320
E vai ser moi bonito exactamente como este.

380
00:28:29,320 --> 00:28:32,230
E eu estou indo a ser preguiceiro e non cambiar o nome da variable,

381
00:28:32,230 --> 00:28:34,380
aínda node9 non fai máis sentido.

382
00:28:34,380 --> 00:28:38,610
Ah, eu creo que o valor do node9 non debería ser 6.

383
00:28:38,610 --> 00:28:42,800
Agora podemos volver node9.

384
00:28:42,800 --> 00:28:49,550
E aquí nós debe retornar nulo.

385
00:28:49,550 --> 00:28:52,690
Todos coinciden en que a función build-a-no?

386
00:28:52,690 --> 00:28:59,780
Entón agora podemos chamar de que a construción de calquera nodo cun dato valor e punteiros nulos.

387
00:28:59,780 --> 00:29:09,750
Agora podemos chamar iso, podemos facer no * node9 = build_node (9).

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

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 agora queremos definir os punteiros mesmos,

391
00:29:39,330 --> 00:29:42,470
só que agora todo está xa en termos de punteiros

392
00:29:42,470 --> 00:29:48,480
entón non necesita máis o enderezo do.

393
00:29:48,480 --> 00:29:56,300
Okay. Entón, cal é a última cousa que quero facer?

394
00:29:56,300 --> 00:30:03,850
Hai un erro de verificación de que eu non estou facendo.

395
00:30:03,850 --> 00:30:06,800
O que significa construír retorno no?

396
00:30:06,800 --> 00:30:11,660
[Estudante, inintelixible] >> Yeah. Se malloc fallou, el vai voltar nulo.

397
00:30:11,660 --> 00:30:16,460
Entón, eu estou indo a preguizosamente poñela aquí, en vez de facer unha condición para cada un.

398
00:30:16,460 --> 00:30:22,320
Se (node9 == null, ou - aínda máis simple,

399
00:30:22,320 --> 00:30:28,020
isto é equivalente a só se non node9.

400
00:30:28,020 --> 00:30:38,310
Entón, se non node9, ou non node6, ou non node3, ou non node7, voltar 1.

401
00:30:38,310 --> 00:30:42,850
Quizais devêssemos imprimir malloc fallou, ou algo así.

402
00:30:42,850 --> 00:30:46,680
[Estudante] é falso igual a nulo, así como?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Calquera valor cero é falso.

404
00:30:51,290 --> 00:30:53,920
Así nulo é un valor cero.

405
00:30:53,920 --> 00:30:56,780
Cero é un valor de cero. Falso é un valor cero.

406
00:30:56,780 --> 00:31:02,130
Calquera - practicamente os únicos dous valores cero son nulas e cero,

407
00:31:02,130 --> 00:31:07,900
falsa é só de hash definido como cero.

408
00:31:07,900 --> 00:31:13,030
Isto tamén se aplica se nós declarar variable global.

409
00:31:13,030 --> 00:31:17,890
Se raíz * ó aquí,

410
00:31:17,890 --> 00:31:24,150
entón - a cousa agradable sobre variables globais é que sempre teñen un valor inicial.

411
00:31:24,150 --> 00:31:27,500
Iso non é verdade de funcións, como aquí dentro,

412
00:31:27,500 --> 00:31:34,870
si temos, *, como no ou nodo.

413
00:31:34,870 --> 00:31:37,380
Nós non temos idea do que x.Value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
ou poderiamos imprimir-los e eles poderían ser arbitraria.

415
00:31:40,700 --> 00:31:44,980
Iso non é verdade de variables globais.

416
00:31:44,980 --> 00:31:47,450
Raíz nodo ou nó.

417
00:31:47,450 --> 00:31:53,410
Por defecto, todo o que é global, non explícitamente inicializada con algún valor,

418
00:31:53,410 --> 00:31:57,390
ten un valor de cero, como o seu valor.

419
00:31:57,390 --> 00:32:01,150
Entón, aquí, o nodo raíz *, non explícitamente inicia-lo a nada,

420
00:32:01,150 --> 00:32:06,350
polo tanto, o seu valor por defecto será nulo, que é o valor cero de punteiros.

421
00:32:06,350 --> 00:32:11,870
O valor por defecto de x vai significar que x.Value é cero,

422
00:32:11,870 --> 00:32:14,260
x.left é nulo, e x.right é nulo.

423
00:32:14,260 --> 00:32:21,070
Entón, unha vez que é unha estrutura, de todos os campos da estrutura serán os valores cero.

424
00:32:21,070 --> 00:32:24,410
Nós non precisamos usar isto aquí, con todo.

425
00:32:24,410 --> 00:32:27,320
[Alumno] As estruturas son diferentes do que outras variables, e as outras variables son

426
00:32:27,320 --> 00:32:31,400
valores de lixo, que son ceros?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Outros valores tamén. Así, en x, x será cero.

428
00:32:36,220 --> 00:32:40,070
Se é no ámbito global, que ten un valor inicial. Ok >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Ou o valor inicial que deu ou cero.

430
00:32:48,950 --> 00:32:53,260
Eu creo que coida de todo isto.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Así, a próxima parte da pregunta é,

432
00:32:58,390 --> 00:33:01,260
"Agora queremos escribir unha función chamada contén

433
00:33:01,260 --> 00:33:04,930
cun prototipo de bool contén valor int. "

434
00:33:04,930 --> 00:33:08,340
Non imos facer bool contén valor int.

435
00:33:08,340 --> 00:33:15,110
O noso prototipo está indo ollar como

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

437
00:33:22,380 --> 00:33:24,490
E entón nós tamén imos pasar a árbore

438
00:33:24,490 --> 00:33:28,870
que debe ser a comprobación para ver se ten ese valor.

439
00:33:28,870 --> 00:33:38,290
Entón no * árbore). Okay.

440
00:33:38,290 --> 00:33:44,440
E entón podemos chamalo con algo,

441
00:33:44,440 --> 00:33:46,090
quizais a xente vai querer printf ou algo así.

442
00:33:46,090 --> 00:33:51,040
Contén 6, a nosa raíz.

443
00:33:51,040 --> 00:33:54,300
Que debe regresar dunha ou verdadeiro,

444
00:33:54,300 --> 00:33:59,390
mentres contén 5 raíz debe retornar falso.

445
00:33:59,390 --> 00:34:02,690
Entón, tome un segundo para aplicar isto.

446
00:34:02,690 --> 00:34:06,780
Podes facelo de calquera forma iterativa ou recursivamente.

447
00:34:06,780 --> 00:34:09,739
O agradable sobre a forma que definir as cousas que

448
00:34:09,739 --> 00:34:12,300
préstase a nosa solución recursiva moito máis fácil

449
00:34:12,300 --> 00:34:14,719
que a forma global variable fixo.

450
00:34:14,719 --> 00:34:19,750
Porque só temos contén valor int, entón non temos forma de recursão para abaixo subárvores.

451
00:34:19,750 --> 00:34:24,130
Nós teriamos que ter unha función auxiliar separado que recurses as subárvores para nós.

452
00:34:24,130 --> 00:34:29,610
Pero desde que cambiei o a tomar a árbore como un argumento,

453
00:34:29,610 --> 00:34:32,760
que debería ser sempre, en primeiro lugar,

454
00:34:32,760 --> 00:34:35,710
agora podemos recurse máis facilmente.

455
00:34:35,710 --> 00:34:38,960
Entón iterativo ou recursivo, nós imos pasar por riba de ambos,

456
00:34:38,960 --> 00:34:46,139
pero imos ver que remata recursivas por ser moi fácil.

457
00:34:59,140 --> 00:35:02,480
Okay. Alguén ten algo que podemos traballar?

458
00:35:02,480 --> 00:35:12,000
>> [Estudante] Eu teño unha solución iterativa. >> Todo ben, iterativo.

459
00:35:12,000 --> 00:35:16,030
Ok, iso parece bo.

460
00:35:16,030 --> 00:35:18,920
Entón, quero andar nos con el?

461
00:35:18,920 --> 00:35:25,780
[Estudante] Claro. Entón eu definir unha variable tempo para obter o primeiro nó da árbore.

462
00:35:25,780 --> 00:35:28,330
E entón eu só loop mentres tempo non nula igual,

463
00:35:28,330 --> 00:35:31,700
por iso, mentres aínda estaba na árbore, eu creo.

464
00:35:31,700 --> 00:35:35,710
E se o valor é igual ao valor de temperatura que está a apuntar cara,

465
00:35:35,710 --> 00:35:37,640
a continuación, el retorna ese valor.

466
00:35:37,640 --> 00:35:40,210
Se non, el verifica se está do lado dereito ou do lado esquerdo.

467
00:35:40,210 --> 00:35:43,400
Se xa tivo unha situación na que non hai máis árbores,

468
00:35:43,400 --> 00:35:47,330
a continuación, el retorna - sae do loop e retorna falso.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. De xeito que parece bo.

470
00:35:52,190 --> 00:35:58,470
Alguén ten algún comentario sobre calquera cousa?

471
00:35:58,470 --> 00:36:02,400
Eu non teño comentarios corrección en todo.

472
00:36:02,400 --> 00:36:11,020
O único que podemos facer é este cara.

473
00:36:11,020 --> 00:36:21,660
Oh, que vai percorrer un pouco longo.

474
00:36:21,660 --> 00:36:33,460
Vou corrixir isto. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Todos deben lembrar de como ternário funciona.

476
00:36:37,150 --> 00:36:38,610
Hai, por suposto probas no pasado

477
00:36:38,610 --> 00:36:41,170
que darlle unha función con un operador ternário,

478
00:36:41,170 --> 00:36:45,750
e dicir, traducir iso, facer algo que non usa ternário.

479
00:36:45,750 --> 00:36:49,140
Polo tanto, este é un caso moi común cando eu ía pensar en usar ternário,

480
00:36:49,140 --> 00:36:54,610
onde se algunha condición definir unha variable para algo,

481
00:36:54,610 --> 00:36:58,580
máis definido que a mesma variable para outra cousa.

482
00:36:58,580 --> 00:37:03,390
Iso é algo que moi frecuentemente se pode converter este tipo de cousas

483
00:37:03,390 --> 00:37:14,420
onde establecer esa variable para iso - ou, ben, iso é verdade? Entón este, senón isto.

484
00:37:14,420 --> 00:37:18,550
[Estudante] O primeiro é se verdade, non?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. O xeito que eu sempre ler é, temperatura igual valor maior que o valor da temperatura,

486
00:37:25,570 --> 00:37:30,680
entón isto, máis isto. É unha pregunta.

487
00:37:30,680 --> 00:37:35,200
É maior? A continuación, faga o primeiro. Máis facer o segundo.

488
00:37:35,200 --> 00:37:41,670
Eu case sempre - o colon, eu só - na miña cabeza, eu leo ​​como persoa.

489
00:37:41,670 --> 00:37:47,180
>> Alguén ten unha solución recursiva?

490
00:37:47,180 --> 00:37:49,670
Okay. Este imos - que podería xa ser grande,

491
00:37:49,670 --> 00:37:53,990
pero estamos indo a facelo aínda mellor.

492
00:37:53,990 --> 00:37:58,720
Esta é practicamente a mesma idea exacta.

493
00:37:58,720 --> 00:38:03,060
É só que, así, quere explicar?

494
00:38:03,060 --> 00:38:08,340
[Estudante] Claro. Entón, estamos asegurarse de que a árbore non é nulo, en primeiro lugar,

495
00:38:08,340 --> 00:38:13,380
porque a árbore é nula, entón el vai voltar falso, porque non telo atopado.

496
00:38:13,380 --> 00:38:19,200
E aínda hai unha árbore, imos para - nós primeiro comprobar que o valor é o nó actual.

497
00:38:19,200 --> 00:38:23,740
Return true se se, e se non recurse nós á esquerda ou á dereita.

498
00:38:23,740 --> 00:38:25,970
Di que o son perfecto? >> MM-hmm. (Acordo)

499
00:38:25,970 --> 00:38:33,880
Así, conta que esta é case - estruturalmente moi semellante á solución iterativa.

500
00:38:33,880 --> 00:38:38,200
É só que, no canto de recursão, tivemos un loop while.

501
00:38:38,200 --> 00:38:40,840
É o caso base aquí onde árbore non fai nula igual

502
00:38:40,840 --> 00:38:44,850
foi a condición baixo a cal saíu do loop while.

503
00:38:44,850 --> 00:38:50,200
Son moi semellantes. Pero imos dar un paso adiante.

504
00:38:50,200 --> 00:38:54,190
Agora, nós facemos o mesmo aquí.

505
00:38:54,190 --> 00:38:57,680
Teña en conta que estamos volvendo o mesmo en ambas as liñas,

506
00:38:57,680 --> 00:39:00,220
con excepción de un argumento é diferente.

507
00:39:00,220 --> 00:39:07,950
Entón, nós imos facelo nun ternário.

508
00:39:07,950 --> 00:39:13,790
Eu bati algo opción, e fixo un símbolo. Okay.

509
00:39:13,790 --> 00:39:21,720
Entón imos voltar contén isto.

510
00:39:21,720 --> 00:39:28,030
Isto está empezando a ser varias liñas, así, o zoom é.

511
00:39:28,030 --> 00:39:31,060
Xeralmente, como unha cousa de estilo, eu non creo que moitas persoas

512
00:39:31,060 --> 00:39:38,640
poñer un espazo despois da frecha, pero eu creo que se vostede é consistente, está todo ben.

513
00:39:38,640 --> 00:39:44,320
Se o valor é menor que o valor de árbore, queremos recurse na esquerda árbore,

514
00:39:44,320 --> 00:39:53,890
outra cousa que queremos recurse en dereito árbore.

515
00:39:53,890 --> 00:39:58,610
Entón iso foi un paso de facer este ollar menor.

516
00:39:58,610 --> 00:40:02,660
Paso dous de facer este ollar menor -

517
00:40:02,660 --> 00:40:09,150
podemos separar isto para varias liñas.

518
00:40:09,150 --> 00:40:16,500
Okay. Paso dous de facelo parecer menor está aquí,

519
00:40:16,500 --> 00:40:25,860
entón o valor de retorno é igual ao valor de árbore, ou o que quere que contén.

520
00:40:25,860 --> 00:40:28,340
>> Iso é unha cousa importante.

521
00:40:28,340 --> 00:40:30,860
Eu non estou seguro se el dixo iso explicitamente en clase,

522
00:40:30,860 --> 00:40:34,740
pero chámase curtocircuíto avaliación.

523
00:40:34,740 --> 00:40:41,060
A idea aquí é valor == valor árbore.

524
00:40:41,060 --> 00:40:49,960
Se iso é verdade, entón iso é verdade, e queremos "ou" o co que está aquí.

525
00:40:49,960 --> 00:40:52,520
Así, sen sequera pensar sobre o que está aquí,

526
00:40:52,520 --> 00:40:55,070
o que é a expresión enteira vai volver?

527
00:40:55,070 --> 00:40:59,430
[Estudante] True? >> Si, porque certo de calquera cousa,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd ou certo con calquera cousa é necesariamente verdade.

529
00:41:04,990 --> 00:41:08,150
Así, logo que vemos valor de retorno = valor árbore,

530
00:41:08,150 --> 00:41:10,140
Nós só estamos indo para voltar certo.

531
00:41:10,140 --> 00:41:15,710
Nin sequera vai recurse contén aínda por baixo da liña.

532
00:41:15,710 --> 00:41:20,980
Podemos dar un paso adiante.

533
00:41:20,980 --> 00:41:29,490
Árbore de retorno non nulo igual e todo iso.

534
00:41:29,490 --> 00:41:32,650
El fixo unha función dunha liña.

535
00:41:32,650 --> 00:41:36,790
Este é tamén un exemplo de avaliación curtocircuíto.

536
00:41:36,790 --> 00:41:40,680
Pero agora é a mesma idea -

537
00:41:40,680 --> 00:41:47,320
en vez de - por iso, se non nulo árbore fai igual - ou, ben,

538
00:41:47,320 --> 00:41:49,580
se fai árbore nula igual, o que é o caso de mala,

539
00:41:49,580 --> 00:41:54,790
a árbore é igual a nulo, entón a primeira condición vai ser falso.

540
00:41:54,790 --> 00:42:00,550
Tan falso anded con calquera cousa vai ser o que?

541
00:42:00,550 --> 00:42:04,640
[Estudante] False. Si >>. Esta é a outra metade do curtocircuíto de avaliación,

542
00:42:04,640 --> 00:42:10,710
onde a árbore non nulo non igual, non estamos indo mesmo ir -

543
00:42:10,710 --> 00:42:14,930
ou se fai árbore nula igual, non imos facer valor == valor árbore.

544
00:42:14,930 --> 00:42:17,010
Nós só estamos indo para voltar inmediatamente falso.

545
00:42:17,010 --> 00:42:20,970
O que é importante, pois, se non o fixo curtocircuíto avaliar,

546
00:42:20,970 --> 00:42:25,860
a continuación, se árbore fai nulo igual, esta segunda condición vai culpa seg,

547
00:42:25,860 --> 00:42:32,510
porque árbore-> valor dereferencing nulo.

548
00:42:32,510 --> 00:42:40,490
Entón é iso. Pode facelo - cambiar unha vez máis.

549
00:42:40,490 --> 00:42:44,840
Iso é unha cousa moi común tamén, non facer esta liña un con iso,

550
00:42:44,840 --> 00:42:49,000
pero é algo común en condicións, é posible que non aquí,

551
00:42:49,000 --> 00:42:59,380
pero (árvore! = NULL, e árbore-> valor valor ==), facer o que.

552
00:42:59,380 --> 00:43:01,560
Esta é unha condición moi común, en que en vez de ter

553
00:43:01,560 --> 00:43:06,770
para romper iso en dous IFS, onde, como é o nulo árbore?

554
00:43:06,770 --> 00:43:11,780
Ok, non é nula, entón agora é o valor igual ao valor de árbore? Facelo.

555
00:43:11,780 --> 00:43:17,300
En vez diso, esa condición, iso non vai seg culpa

556
00:43:17,300 --> 00:43:21,220
porque vai saír se isto acontecer a ser nulo.

557
00:43:21,220 --> 00:43:24,000
Ben, eu creo que a árbore é un punteiro completamente válido, aínda pode seg culpa,

558
00:43:24,000 --> 00:43:26,620
pero non pode seg culpa a árbore é nula.

559
00:43:26,620 --> 00:43:32,900
Se fose nulo, ía saír antes de lle dereferenced o punteiro en primeiro lugar.

560
00:43:32,900 --> 00:43:35,000
[Estudante] É esta avaliación chamado preguiceiro?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Valoración preguiceiro é unha cousa separada.

562
00:43:40,770 --> 00:43:49,880
Avaliación preguiceira é máis como lle preguntar a un valor,

563
00:43:49,880 --> 00:43:54,270
preguntar para calcular un valor, tipo, pero non precisa del inmediatamente.

564
00:43:54,270 --> 00:43:59,040
Entón, ata que realmente precisa del, non é valorada.

565
00:43:59,040 --> 00:44:03,920
Esta non é exactamente a mesma cousa, pero no pset Huffman,

566
00:44:03,920 --> 00:44:06,520
el di que "preguizosamente", escriben.

567
00:44:06,520 --> 00:44:08,670
A razón para facermos iso é porque en realidade estamos buffer escrita -

568
00:44:08,670 --> 00:44:11,820
non quero escribir bits individuais de cada vez,

569
00:44:11,820 --> 00:44:15,450
ou máis individuais de unha vez, que en vez queren ter un pedazo de bytes.

570
00:44:15,450 --> 00:44:19,270
A continuación, unha vez que temos un anaco de máis, entón imos escribir isto.

571
00:44:19,270 --> 00:44:22,640
Aínda que pedir para el escribir - e fwrite e fread facer o mesmo tipo de cousas.

572
00:44:22,640 --> 00:44:26,260
Elas suavizan o le e escribe.

573
00:44:26,260 --> 00:44:31,610
Aínda que pedir para el escribir de inmediato, probablemente non.

574
00:44:31,610 --> 00:44:34,540
E non pode estar seguro de que as cousas van ser escrito

575
00:44:34,540 --> 00:44:37,540
ata que chamar hfclose ou o que sexa,

576
00:44:37,540 --> 00:44:39,620
que, entón, di, está ben, eu estou pechando meu arquivo,

577
00:44:39,620 --> 00:44:43,450
Isto significa que é mellor eu escribir todo o que eu non escribiu.

578
00:44:43,450 --> 00:44:45,770
El non ten necesidade de escribir todo fóra

579
00:44:45,770 --> 00:44:49,010
ata que está pechando o ficheiro, e entón el necesita.

580
00:44:49,010 --> 00:44:56,220
Entón, iso é só o que preguiceiro - espera ata que iso ten que acontecer.

581
00:44:56,220 --> 00:44:59,990
Este - ter 51 e vai entrar en máis detalles,

582
00:44:59,990 --> 00:45:05,470
porque OCaml e todo en 51, todo é recursão.

583
00:45:05,470 --> 00:45:08,890
Non existen solucións iterativo, basicamente.

584
00:45:08,890 --> 00:45:11,550
Todo é recursividade, e avaliación preguiceira

585
00:45:11,550 --> 00:45:14,790
vai ser importante para unha serie de circunstancias

586
00:45:14,790 --> 00:45:19,920
onde, se non avaliar preguizosamente, iso significaría -

587
00:45:19,920 --> 00:45:24,760
O exemplo é cadeas, que son infinitamente longo.

588
00:45:24,760 --> 00:45:30,990
En teoría, pode pensar que os números naturais como un fluxo de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Cousas tan preguizosamente avaliados están ben.

590
00:45:33,090 --> 00:45:37,210
Se eu dixer que quero o número dez, entón eu podo avaliar, ata o número dez.

591
00:45:37,210 --> 00:45:40,300
Se quere que o número centésimo, entón eu podo avaliar, ata o número centésimo.

592
00:45:40,300 --> 00:45:46,290
Sen avaliación preguiceira, el vai avaliar todos os números inmediatamente.

593
00:45:46,290 --> 00:45:50,000
Vostede está avaliando números infinitos, e iso non é só posible.

594
00:45:50,000 --> 00:45:52,080
Entón, hai unha serie de circunstancias en que a avaliación preguiceiro

595
00:45:52,080 --> 00:45:57,840
é só esencial para a obtención de cousas para traballar.

596
00:45:57,840 --> 00:46:05,260
>> Agora queremos escribir inserción onde inserción será

597
00:46:05,260 --> 00:46:08,430
Similarmente cambio na súa definición.

598
00:46:08,430 --> 00:46:10,470
Entón agora é introducir bool (valor enteiro).

599
00:46:10,470 --> 00:46:23,850
Imos cambiar isto para inserción bool (int valor, no da árbore *).

600
00:46:23,850 --> 00:46:29,120
Estamos, en realidade, vai cambiar de novo aquí a pouco, imos ver por que.

601
00:46:29,120 --> 00:46:32,210
E imos pasar build_node, só para os anacos del,

602
00:46:32,210 --> 00:46:36,730
por riba de introducir de xeito que non ten que escribir un prototipo de función.

603
00:46:36,730 --> 00:46:42,450
Que é un indicio de que está indo estar usando build_node na inserción.

604
00:46:42,450 --> 00:46:49,590
Okay. Tomé un minuto para iso.

605
00:46:49,590 --> 00:46:52,130
Eu creo que eu salvo a revisión se quere tirar de que,

606
00:46:52,130 --> 00:47:00,240
ou, polo menos, eu fixen agora.

607
00:47:00,240 --> 00:47:04,190
Eu quería unha lixeira quebra a pensar sobre a lóxica de inserción,

608
00:47:04,190 --> 00:47:08,750
se non pode pensar niso.

609
00:47:08,750 --> 00:47:12,860
Basicamente, só vai ser inserir nas follas.

610
00:47:12,860 --> 00:47:18,640
Como, se eu introducir un, entón eu estou, inevitablemente, vai ser unha inserción -

611
00:47:18,640 --> 00:47:21,820
Vou cambiar a negro - eu ser a inserción dun por aquí.

612
00:47:21,820 --> 00:47:28,070
Ou se eu inserir 4, quero ser a inserción de catro aquí.

613
00:47:28,070 --> 00:47:32,180
Polo tanto, non importa o que fai, vai ser a inserción de unha folla.

614
00:47:32,180 --> 00:47:36,130
Todo o que tes que facer é repetir a árbore ata chegar ao nodo

615
00:47:36,130 --> 00:47:40,890
que debe ser pai do nodo, o pai do novo nodo,

616
00:47:40,890 --> 00:47:44,560
e despois cambiar o punteiro cara á esquerda ou dereita, dependendo do feito

617
00:47:44,560 --> 00:47:47,060
que é maior que ou menor que o nodo actual.

618
00:47:47,060 --> 00:47:51,180
Cambiar ese punteiro para apuntar para o novo nodo.

619
00:47:51,180 --> 00:48:05,490
Entón iterar a árbore, facer o punto da folla para o novo nodo.

620
00:48:05,490 --> 00:48:09,810
Tamén pensar sobre o motivo que prohibe o tipo de situación antes,

621
00:48:09,810 --> 00:48:17,990
onde construíu a árbore binaria onde estaba correcto

622
00:48:17,990 --> 00:48:19,920
se só ollou para un único nodo,

623
00:48:19,920 --> 00:48:24,830
pero 9 foi á esquerda, de 7, se iterado para abaixo todo o camiño.

624
00:48:24,830 --> 00:48:29,770
Entón, iso é imposible, neste escenario, xa que -

625
00:48:29,770 --> 00:48:32,530
pensa sobre a inserción de 9 ou algo; no nó de primeira,

626
00:48:32,530 --> 00:48:35,350
Vou ver 7 e eu só estou indo a ir á dereita.

627
00:48:35,350 --> 00:48:38,490
Polo tanto, non importa o que fago, se eu estou indo para a inserción de unha folla,

628
00:48:38,490 --> 00:48:40,790
e para unha folla utilizando o algoritmo axeitado,

629
00:48:40,790 --> 00:48:43,130
que vai ser imposible para min para introducir 9 a esquerda, do 7 de

630
00:48:43,130 --> 00:48:48,250
porque así que eu bater 7 Eu estou indo a ir á dereita.

631
00:48:59,740 --> 00:49:02,070
Alguén ten algunha cousa para comezar?

632
00:49:02,070 --> 00:49:05,480
[Estudante] fago. >> Suposto.

633
00:49:05,480 --> 00:49:09,200
[Estudante, inintelixible]

634
00:49:09,200 --> 00:49:14,390
[Outro alumno, inintelixible]

635
00:49:14,390 --> 00:49:18,330
[Bowden] É apreciado. Okay. Queres explicar?

636
00:49:18,330 --> 00:49:20,690
>> [Estudante] Unha vez que sabemos que fomos inserindo

637
00:49:20,690 --> 00:49:24,060
novos nós no extremo da árbore,

638
00:49:24,060 --> 00:49:28,070
Eu loop través da árbore iterativamente

639
00:49:28,070 --> 00:49:31,360
ata que cheguei a un nodo que apuntou como nulo.

640
00:49:31,360 --> 00:49:34,220
E entón eu decidir colocar-lo tanto no lado dereito ou do lado esquerdo

641
00:49:34,220 --> 00:49:37,420
usando esa variable dereito, que me dixo onde poñelas.

642
00:49:37,420 --> 00:49:41,850
E entón, esencialmente, eu fixen só que a última -

643
00:49:41,850 --> 00:49:47,520
Nese punto no tempo para o novo nodo que estaba creando,

644
00:49:47,520 --> 00:49:50,770
ou no lado esquerdo ou no lado dereito, de acordo co que o valor era certo.

645
00:49:50,770 --> 00:49:56,530
Finalmente, defina o valor novo no co valor dos seus probas.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Ok, entón eu vexo un problema aquí.

647
00:49:59,550 --> 00:50:02,050
Isto é como o 95% do camiño.

648
00:50:02,050 --> 00:50:07,550
O problema que eu vexo, así, se alguén ve un problema?

649
00:50:07,550 --> 00:50:18,400
Cal é a circunstancia en que quebran fóra do circuíto?

650
00:50:18,400 --> 00:50:22,100
[Estudante] Si tempo é nulo? Si >>. Entón, como saír do loop é se tempo é nulo.

651
00:50:22,100 --> 00:50:30,220
Pero o que fago aquí?

652
00:50:30,220 --> 00:50:35,410
Eu temperatura dereference, que é inevitablemente nula.

653
00:50:35,410 --> 00:50:39,840
Entón, a outra cousa que ten que facer non é só seguir ata tempo é nulo,

654
00:50:39,840 --> 00:50:45,590
quere seguir o pai en todos os momentos.

655
00:50:45,590 --> 00:50:52,190
Queremos tamén pai * no, creo que podemos manter isto nulo no primeiro.

656
00:50:52,190 --> 00:50:55,480
Isto vai ter un comportamento estraño para a raíz da árbore,

657
00:50:55,480 --> 00:50:59,210
pero nós imos chegar a iso.

658
00:50:59,210 --> 00:51:03,950
Se o valor é maior do que calquera outra cousa, entón temperatura correcta tempo =.

659
00:51:03,950 --> 00:51:07,910
Pero antes de facer ese pai, tempo =.

660
00:51:07,910 --> 00:51:14,500
Ou os pais sempre vai temperatura igual? É ese o caso?

661
00:51:14,500 --> 00:51:19,560
Se tempo non é nulo, entón eu vou mover para abaixo, non importa o que,

662
00:51:19,560 --> 00:51:24,030
a un nodo para o cal tempo é o pai.

663
00:51:24,030 --> 00:51:27,500
Entón pai vai ser temporal, e despois eu paso temporal inferior.

664
00:51:27,500 --> 00:51:32,410
Agora temporal é nulo, pero puntos pai para o pai da cousa que é nulo.

665
00:51:32,410 --> 00:51:39,110
Entón, aquí, eu non quero para definir dereito igual a 1.

666
00:51:39,110 --> 00:51:41,300
Entón eu me mudei para a dereita, por iso, a dereita = 1,

667
00:51:41,300 --> 00:51:45,130
e eu creo que tamén quere facer -

668
00:51:45,130 --> 00:51:48,530
se se mover á esquerda, que pretende definir dereito igual a 0.

669
00:51:48,530 --> 00:51:55,950
Ou ben, se non se mover á dereita.

670
00:51:55,950 --> 00:51:58,590
Entón dereita = 0. O dereito = 1,

671
00:51:58,590 --> 00:52:04,260
agora queremos facer o pai newNode punteiro dereito,

672
00:52:04,260 --> 00:52:08,520
outra cousa que quero facer o pai newNode punteiro esquerdo.

673
00:52:08,520 --> 00:52:16,850
Preguntas sobre iso?

674
00:52:16,850 --> 00:52:24,880
Okay. Polo tanto, esta é a forma que - ben, en realidade, no canto de facelo,

675
00:52:24,880 --> 00:52:29,630
Nós medio que esperaba que use build_node.

676
00:52:29,630 --> 00:52:40,450
E entón newNode igual nulo, retorna false.

677
00:52:40,450 --> 00:52:44,170
É iso. Agora, iso é o que espera que faga.

678
00:52:44,170 --> 00:52:47,690
>> Isto é o que as solucións persoal facer.

679
00:52:47,690 --> 00:52:52,360
Non estou de acordo con iso como o xeito "correcto" de facelo

680
00:52:52,360 --> 00:52:57,820
pero iso é perfectamente ben e el vai funcionar.

681
00:52:57,820 --> 00:53:02,840
Unha cousa que está un pouco raro agora

682
00:53:02,840 --> 00:53:08,310
a árbore comeza como nula, pasamos a unha árbore nula.

683
00:53:08,310 --> 00:53:12,650
Creo que depende de como define o comportamento pasar dunha árbore nula.

684
00:53:12,650 --> 00:53:15,490
Eu creo que se pasar dunha árbore nula,

685
00:53:15,490 --> 00:53:17,520
a continuación, engadir o valor para unha árbore nula

686
00:53:17,520 --> 00:53:23,030
debe retornar só unha árbore, onde o único valor que é único no.

687
00:53:23,030 --> 00:53:25,830
As persoas de acordo con iso? Vostede podería, se quixese,

688
00:53:25,830 --> 00:53:28,050
se pasar dunha árbore nula

689
00:53:28,050 --> 00:53:31,320
e quere inserir un valor para el, voltar falso.

690
00:53:31,320 --> 00:53:33,830
É ata a definir iso.

691
00:53:33,830 --> 00:53:38,320
Para facer a primeira cousa que eu dixen e despois -

692
00:53:38,320 --> 00:53:40,720
así, vai ter problemas para facer iso, porque

693
00:53:40,720 --> 00:53:44,090
sería máis doado se tivésemos un punteiro global para a cousa,

694
00:53:44,090 --> 00:53:48,570
pero non, entón a árbore é nulo, non hai nada que poidamos facer sobre iso.

695
00:53:48,570 --> 00:53:50,960
Podemos só retornar falso.

696
00:53:50,960 --> 00:53:52,840
Entón, eu vou cambiar de inserción.

697
00:53:52,840 --> 00:53:56,540
Nós tecnicamente podería cambiar isto aquí,

698
00:53:56,540 --> 00:53:58,400
como está interactuando sobre as cousas,

699
00:53:58,400 --> 00:54:04,530
pero eu vou cambiar de inserción para tomar un nodo árbore. **

700
00:54:04,530 --> 00:54:07,510
Punteiros dobres.

701
00:54:07,510 --> 00:54:09,710
O que significa isto?

702
00:54:09,710 --> 00:54:12,330
En vez de xestionar punteiros para nós,

703
00:54:12,330 --> 00:54:16,690
a cousa que eu vou estar manipulando é este punteiro.

704
00:54:16,690 --> 00:54:18,790
Eu vou estar manipulando este punteiro.

705
00:54:18,790 --> 00:54:21,770
Eu vou estar manipulando punteiros directamente.

706
00:54:21,770 --> 00:54:25,760
Isto ten sentido, xa que, pensando cara abaixo -

707
00:54:25,760 --> 00:54:33,340
Ben, agora que apunta a nulo.

708
00:54:33,340 --> 00:54:38,130
O que quero facer é manipular este punteiro para apuntar para non nulo.

709
00:54:38,130 --> 00:54:40,970
Eu quero que apunte cara ao meu novo nodo.

710
00:54:40,970 --> 00:54:44,870
Se eu só manter o control de punteiros para os meus punteiros,

711
00:54:44,870 --> 00:54:47,840
entón non necesita manter o control dun punteiro pai.

712
00:54:47,840 --> 00:54:52,640
Eu podo só seguir a ver se o punteiro está a apuntar cara nulo,

713
00:54:52,640 --> 00:54:54,580
e se o punteiro está a apuntar cara nulo,

714
00:54:54,580 --> 00:54:57,370
muda-lo para apuntar para o nodo que quero.

715
00:54:57,370 --> 00:55:00,070
E podo mudalo desde que eu teño un punteiro para o punteiro.

716
00:55:00,070 --> 00:55:02,040
Imos ver iso agora.

717
00:55:02,040 --> 00:55:05,470
Pode realmente facelo recursivamente moi facilmente.

718
00:55:05,470 --> 00:55:08,080
Non queremos facer iso?

719
00:55:08,080 --> 00:55:10,980
Si, nós facemos.

720
00:55:10,980 --> 00:55:16,790
>> Imos ver iso de forma recursiva.

721
00:55:16,790 --> 00:55:24,070
En primeiro lugar, o que é o noso caso base vai ser?

722
00:55:24,070 --> 00:55:29,140
Case sempre o noso caso base, pero, en realidade, iso é medio complicado.

723
00:55:29,140 --> 00:55:34,370
Primeiro de todo, se (árbore == NULL)

724
00:55:34,370 --> 00:55:37,550
Eu creo que nós só estamos indo para voltar falso.

725
00:55:37,550 --> 00:55:40,460
Isto é distinto do seu nulo árbore estar.

726
00:55:40,460 --> 00:55:44,510
Este é o punteiro para o punteiro raíz sendo nula

727
00:55:44,510 --> 00:55:48,360
o que significa que o punteiro raíz non existe.

728
00:55:48,360 --> 00:55:52,390
Entón, aquí, se eu fai

729
00:55:52,390 --> 00:55:55,760
* No - imos reutilizar ese.

730
00:55:55,760 --> 00:55:58,960
* No raíz = NULL,

731
00:55:58,960 --> 00:56:00,730
e entón eu vou chamar de inserción, facendo algo parecido,

732
00:56:00,730 --> 00:56:04,540
inserir o 4 e raíz.

733
00:56:04,540 --> 00:56:06,560
Así, e de raíz, a raíz é un nó *

734
00:56:06,560 --> 00:56:11,170
despois & raíz vai ser un ** nodo.

735
00:56:11,170 --> 00:56:15,120
Isto é válido. Neste caso, árbore, até aquí,

736
00:56:15,120 --> 00:56:20,120
árbore non é nula - ou inserción.

737
00:56:20,120 --> 00:56:24,630
Aquí. Árbore non é nulo; árbore * é nulo, o que é bo

738
00:56:24,630 --> 00:56:26,680
porque a árbore * é nulo, entón eu podo manipulala lo

739
00:56:26,680 --> 00:56:29,210
ata agora apuntan o que quero que apuntar.

740
00:56:29,210 --> 00:56:34,750
Pero se a árbore é nula, isto significa que eu só vin aquí e dixo nulo.

741
00:56:34,750 --> 00:56:42,710
Isto non ten sentido. Eu non podo facer nada con iso.

742
00:56:42,710 --> 00:56:45,540
Se a árbore é nulo, retorna false.

743
00:56:45,540 --> 00:56:48,220
Entón eu basicamente xa dixen que o noso caso base real.

744
00:56:48,220 --> 00:56:50,580
E que é o que vai ser?

745
00:56:50,580 --> 00:56:55,030
[Estudante, inintelixible]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Si Entón, se (* árbore == NULL).

747
00:57:00,000 --> 00:57:04,520
Isto relaciónase co caso aquí

748
00:57:04,520 --> 00:57:09,640
onde se meu punteiro vermello é o punteiro Estou centrado,

749
00:57:09,640 --> 00:57:12,960
así como eu estou focado neste punteiro, agora eu estou focado neste punteiro.

750
00:57:12,960 --> 00:57:15,150
Agora estou focado neste punteiro.

751
00:57:15,150 --> 00:57:18,160
Entón, se o meu punteiro vermello, que é ** meu nó,

752
00:57:18,160 --> 00:57:22,880
é nunca - se *, meu punteiro vermello, sempre nula,

753
00:57:22,880 --> 00:57:28,470
iso significa que eu estou no caso en que eu estou focando un punteiro que apunta -

754
00:57:28,470 --> 00:57:32,530
este é un punteiro que pertence a unha folla.

755
00:57:32,530 --> 00:57:41,090
Eu quero cambiar este punteiro para apuntar para o meu novo nodo.

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

757
00:57:45,230 --> 00:57:56,490
O meu newNode será só no * n = build_node (valor)

758
00:57:56,490 --> 00:58:07,300
entón n, se n = NULL, retorna false.

759
00:58:07,300 --> 00:58:12,600
Outra cousa que quero cambiar o que o punteiro está a apuntar cara

760
00:58:12,600 --> 00:58:17,830
agora a apuntar para o noso nodo recén construído.

761
00:58:17,830 --> 00:58:20,280
Podemos realmente facer iso aquí.

762
00:58:20,280 --> 00:58:30,660
En vez de dicir n, dicimos * = árbore a árbore *.

763
00:58:30,660 --> 00:58:35,450
Todo o mundo entende isto? Que, por xestione punteiros para punteiro,

764
00:58:35,450 --> 00:58:40,750
podemos cambiar punteiros nulos para apuntar para cousas que queremos que ligan.

765
00:58:40,750 --> 00:58:42,820
Ese é o noso caso base.

766
00:58:42,820 --> 00:58:45,740
>> Agora recorrencia noso, ou o noso recursão,

767
00:58:45,740 --> 00:58:51,430
vai ser moi semellante a todos os outros recursões temos está a facer.

768
00:58:51,430 --> 00:58:55,830
Nós imos querer inserir valor,

769
00:58:55,830 --> 00:58:59,040
e agora eu vou usar ternário de novo, pero o que é a nosa condición será?

770
00:58:59,040 --> 00:59:05,180
Que estamos á procura de decidir se queremos ir á esquerda ou dereita?

771
00:59:05,180 --> 00:59:07,760
Imos facelo en etapas separadas.

772
00:59:07,760 --> 00:59:18,850
If (valor <) o que?

773
00:59:18,850 --> 00:59:23,200
[Alumno] O valor árbore?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Entón lembre que eu estou actualmente -

775
00:59:27,490 --> 00:59:31,260
[Estudantes, inintelixible]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Si, iso aquí, imos dicir que esta frecha verde

777
00:59:34,140 --> 00:59:39,050
é un exemplo do que é actualmente a árbore é un punteiro para este punteiro.

778
00:59:39,050 --> 00:59:46,610
Entón iso significa que eu son un punteiro para un punteiro para 3.

779
00:59:46,610 --> 00:59:48,800
O dereference dúas veces soaba ben.

780
00:59:48,800 --> 00:59:51,010
O que eu - como fago isto?

781
00:59:51,010 --> 00:59:53,210
[Estudante] Referencia no unha vez, e en seguida, facer frecha que xeito?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Entón (árbore *) é o dereference unha vez máis, - valor>

783
00:59:58,420 --> 01:00:05,960
vai dar-me o valor do nodo que eu estou indirectamente apuntando.

784
01:00:05,960 --> 01:00:11,980
Entón, eu tamén podo escribir ** tree.value se prefire.

785
01:00:11,980 --> 01:00:18,490
Ou funciona.

786
01:00:18,490 --> 01:00:26,190
Se é ese o caso, entón eu quero chamar inserir con valor.

787
01:00:26,190 --> 01:00:32,590
E o que é o meu nó actualizados ** vai ser?

788
01:00:32,590 --> 01:00:39,440
Eu quero ir para a esquerda, para tree.left ** vai ser miña esquerda.

789
01:00:39,440 --> 01:00:41,900
E quero que o punteiro para esa cousa

790
01:00:41,900 --> 01:00:44,930
de xeito que a esquerda acaba sendo o punteiro nulo,

791
01:00:44,930 --> 01:00:48,360
Eu podo modificalo lo para apuntar para o meu novo nodo.

792
01:00:48,360 --> 01:00:51,460
>> E outro caso pode ser moi similar.

793
01:00:51,460 --> 01:00:55,600
Imos realmente facer que o meu ternário agora.

794
01:00:55,600 --> 01:01:04,480
Insire valor se valor <(árbore **). Valor.

795
01:01:04,480 --> 01:01:11,040
Entón queremos actualizar os nosos ** a esquerda,

796
01:01:11,040 --> 01:01:17,030
mais queremos actualizar os nosos ** a dereita.

797
01:01:17,030 --> 01:01:22,540
[Estudante] Será que obter o punteiro para o punteiro?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Lembre que - ** tree.right é unha estrela no.

799
01:01:30,940 --> 01:01:35,040
[Estudante, inintelixible] >> Yeah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right é así punteiro ou algo así.

801
01:01:41,140 --> 01:01:45,140
Así, tomando un punteiro para iso, que me dá o que quero

802
01:01:45,140 --> 01:01:50,090
do punteiro para este cara.

803
01:01:50,090 --> 01:01:54,260
[Estudante] Podemos ir unha vez máis por que estamos usando os dous punteiros?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Entón - non, pode, e que a solución antes

805
01:01:58,220 --> 01:02:04,540
Era unha forma de facelo sen facer dous punteiros.

806
01:02:04,540 --> 01:02:08,740
Debe ser capaz de comprender a usar dous punteiros,

807
01:02:08,740 --> 01:02:11,660
e esta é unha solución de limpeza.

808
01:02:11,660 --> 01:02:16,090
Ademais, observe que, o que pasa se a miña árbore -

809
01:02:16,090 --> 01:02:24,480
Qué acontece se miña raíz era nulo? Qué acontece se eu facer iso caso aquí?

810
01:02:24,480 --> 01:02:30,540
Entón nodo raíz * = NULL, insira 4 en e raíz.

811
01:02:30,540 --> 01:02:35,110
O que é raíz vai ser despois disto?

812
01:02:35,110 --> 01:02:37,470
[Estudante, inintelixible] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Valor da raíz vai ser 4.

814
01:02:41,710 --> 01:02:45,510
Esquerdo de raíz vai ser nulo, seguro raíz vai ser nulo.

815
01:02:45,510 --> 01:02:49,490
No caso de que non pase de raíz por enderezo

816
01:02:49,490 --> 01:02:52,490
non se pode modificar raíz.

817
01:02:52,490 --> 01:02:56,020
No caso de que a árbore - onde raíz era nulo,

818
01:02:56,020 --> 01:02:58,410
Nós só tivemos que voltar falso. Non hai nada que poidamos facer.

819
01:02:58,410 --> 01:03:01,520
Non podemos inserir un nodo nunha árbore baleira.

820
01:03:01,520 --> 01:03:06,810
Pero agora podemos, nós só facer unha árbore baleira nunha árbore dun nodo.

821
01:03:06,810 --> 01:03:13,400
Que normalmente é a forma esperada que suporía para traballar.

822
01:03:13,400 --> 01:03:21,610
>> Ademais, esta é significativamente máis curto do que

823
01:03:21,610 --> 01:03:26,240
tamén manter o control do seu pai, e así percorrer todo o camiño cara a abaixo.

824
01:03:26,240 --> 01:03:30,140
Agora eu teño o meu pai, e eu só teño o meu punteiro dereito pai para o que sexa.

825
01:03:30,140 --> 01:03:35,640
En vez diso, se facemos iso de forma iterativa, que sería a mesma idea con un loop while.

826
01:03:35,640 --> 01:03:38,100
Pero, en vez de ter que xestione o meu punteiro pai,

827
01:03:38,100 --> 01:03:40,600
en vez o meu punteiro actual sería a cousa

828
01:03:40,600 --> 01:03:43,790
que eu estou modificando directamente para apuntar para o meu novo nodo.

829
01:03:43,790 --> 01:03:46,090
Eu non teño que xestione o feito de que está a apuntar cara á esquerda.

830
01:03:46,090 --> 01:03:48,810
Eu non teño que xestione o feito de que está a apuntar cara a dereita.

831
01:03:48,810 --> 01:04:00,860
É só o que ese punteiro é, eu estou indo a configuralo para apuntar para o meu novo nodo.

832
01:04:00,860 --> 01:04:05,740
Todo o mundo entende como funciona?

833
01:04:05,740 --> 01:04:09,460
Se non, por que queremos facelo desta forma,

834
01:04:09,460 --> 01:04:14,920
pero que, polo menos, esta funciona como unha solución?

835
01:04:14,920 --> 01:04:17,110
[Estudante] Onde é que imos volver verdade?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Isto é probablemente aquí.

837
01:04:21,550 --> 01:04:26,690
Se correctamente inserir-lo, voltar true.

838
01:04:26,690 --> 01:04:32,010
Outra cousa, aquí imos querer volver retorno independentemente de inserción.

839
01:04:32,010 --> 01:04:35,950
>> E o que hai de especial sobre esta función recursiva?

840
01:04:35,950 --> 01:04:43,010
É cola recursiva, por iso, mentres nós compilar con algunha optimización,

841
01:04:43,010 --> 01:04:48,060
vai recoñecer iso e nunca vai ter un estourido de pila a partir deste,

842
01:04:48,060 --> 01:04:53,230
mesmo se a nosa árbore ten unha altura de 10 mil ou 10 millóns.

843
01:04:53,230 --> 01:04:55,630
[Estudante, inintelixible]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Coido que fai iso en Dash - ou o que nivel de optimización

845
01:05:00,310 --> 01:05:03,820
é necesario para unha recursão de cola para ser recoñecida.

846
01:05:03,820 --> 01:05:09,350
Coido que recoñece - GCC e Clang

847
01:05:09,350 --> 01:05:12,610
tamén teñen significados diferentes para os seus niveis de optimización.

848
01:05:12,610 --> 01:05:17,870
Eu quero dicir que é DashO 2, a certeza de que vai recoñecer recursão de cola.

849
01:05:17,870 --> 01:05:27,880
Pero nós - pode construír como un exemplo Fibonocci ou algo así.

850
01:05:27,880 --> 01:05:30,030
Non é doado facer a proba con iso, porque é difícil construír

851
01:05:30,030 --> 01:05:32,600
unha árbore binaria que é tan grande.

852
01:05:32,600 --> 01:05:37,140
Pero si, eu creo que é DashO 2, que

853
01:05:37,140 --> 01:05:40,580
Se compilar con DashO 2, el ha buscar recursão

854
01:05:40,580 --> 01:05:54,030
e optimizar iso.

855
01:05:54,030 --> 01:05:58,190
Imos volver - inserir, literalmente, a última cousa que precisa.

856
01:05:58,190 --> 01:06:04,900
Imos volver para a inserción aquí

857
01:06:04,900 --> 01:06:07,840
onde nós estamos indo facer a mesma idea.

858
01:06:07,840 --> 01:06:14,340
Aínda vai ter o fallo de non ser capaz de tratar con todo

859
01:06:14,340 --> 01:06:17,940
cando a raíz en si é nulo, ou a entrada de pasado é nulo,

860
01:06:17,940 --> 01:06:20,060
pero, en vez de tratar con un punteiro pai,

861
01:06:20,060 --> 01:06:27,430
imos aplicar a mesma lóxica dos punteiros mantendo a punteiros.

862
01:06:27,430 --> 01:06:35,580
Aquí nós manter o noso nodo **, cur

863
01:06:35,580 --> 01:06:37,860
e non precisa manter o control de máis correcto,

864
01:06:37,860 --> 01:06:47,190
pero nó ** cur = árbore.

865
01:06:47,190 --> 01:06:54,800
E agora o noso loop while será mentres cur * non nula igual.

866
01:06:54,800 --> 01:07:00,270
Non é preciso manter o control de pais máis.

867
01:07:00,270 --> 01:07:04,180
Non é preciso manter o control de esquerda e dereita.

868
01:07:04,180 --> 01:07:10,190
E eu vou chamalo de tempo, porque xa estamos usando tempo.

869
01:07:10,190 --> 01:07:17,200
Okay. Entón, se (valor> * tempo),

870
01:07:17,200 --> 01:07:24,010
a continuación, e (* tempo) - dereito>

871
01:07:24,010 --> 01:07:29,250
máis tempo = (* tempo) -> esquerda.

872
01:07:29,250 --> 01:07:32,730
E agora, neste momento, tras este loop while,

873
01:07:32,730 --> 01:07:36,380
Eu só fago iso porque quizais sexa máis fácil pensar iterativamente de forma recursiva,

874
01:07:36,380 --> 01:07:39,010
pero despois deste loop while,

875
01:07:39,010 --> 01:07:43,820
* Temp é o punteiro que desexa cambiar.

876
01:07:43,820 --> 01:07:48,960
>> Antes tiñamos pai, e queriamos cambiar calquera pai ou nai esquerda a dereita,

877
01:07:48,960 --> 01:07:51,310
pero se queremos cambiar dereito dos pais,

878
01:07:51,310 --> 01:07:54,550
entón tempo * é dereito dos pais, e podemos mudalo directamente.

879
01:07:54,550 --> 01:08:05,860
Entón, aquí, podemos facer * temp = newNode, e é iso.

880
01:08:05,860 --> 01:08:09,540
Entón aviso, todo o que fixemos nesta era sacar liñas de código.

881
01:08:09,540 --> 01:08:14,770
Co fin de seguir o pai en todo o que é o esforzo adicional.

882
01:08:14,770 --> 01:08:18,689
Aquí, se nós só seguir o punteiro para o punteiro,

883
01:08:18,689 --> 01:08:22,990
e mesmo que quería se librar de todas estas claves agora,

884
01:08:22,990 --> 01:08:27,170
facela máis curta.

885
01:08:27,170 --> 01:08:32,529
Agora é a solución exactamente o mesmo,

886
01:08:32,529 --> 01:08:38,210
pero menos liñas de código.

887
01:08:38,210 --> 01:08:41,229
Unha vez que comezar a recoñecer isto como unha solución válida,

888
01:08:41,229 --> 01:08:43,529
tamén é máis fácil do que razoar sobre como, ok,

889
01:08:43,529 --> 01:08:45,779
por que eu teño esta bandeira á dereita int?

890
01:08:45,779 --> 01:08:49,290
O que significa isto? Oh, está significando que

891
01:08:49,290 --> 01:08:51,370
Cada vez que vou ben, eu teño configure-lo,

892
01:08:51,370 --> 01:08:53,819
outra cousa, se for aínda que, eu teño configuralo para cero.

893
01:08:53,819 --> 01:09:04,060
Aquí, eu non teño a razón sobre iso, é só máis fácil de pensar.

894
01:09:04,060 --> 01:09:06,710
Preguntas?

895
01:09:06,710 --> 01:09:16,290
[Estudante, inintelixible] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Ok, entón o último bit -

897
01:09:23,359 --> 01:09:28,080
Eu creo que unha función sinxela e rápida que podemos facer é,

898
01:09:28,080 --> 01:09:34,910
Imos - xuntos, eu creo, e tentar escribir un contén función

899
01:09:34,910 --> 01:09:38,899
que non lle importa se é unha árbore de busca binaria.

900
01:09:38,899 --> 01:09:43,770
Este contén función debe devolver True

901
01:09:43,770 --> 01:09:58,330
en calquera lugar nesta árbore binaria xeral é o valor que estamos a buscar.

902
01:09:58,330 --> 01:10:02,520
Entón, imos primeiro facer iso recursivamente e logo nós imos facelo de forma iterativa.

903
01:10:02,520 --> 01:10:07,300
Nós realmente podemos só facelo xuntos, porque iso vai ser moi curto.

904
01:10:07,300 --> 01:10:11,510
>> O que é o meu caso base vai ser?

905
01:10:11,510 --> 01:10:13,890
[Estudante, inintelixible]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Entón, se (árbore == NULL), entón o que?

907
01:10:18,230 --> 01:10:22,740
[Estudante] Voltar falso.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, así, eu non teño outro.

909
01:10:26,160 --> 01:10:30,250
Se foi o meu caso outra base.

910
01:10:30,250 --> 01:10:32,450
Valor [do estudante] árbore? Si >>.

911
01:10:32,450 --> 01:10:36,430
Entón, se (árbore-> valor valor. ==

912
01:10:36,430 --> 01:10:39,920
Teña en conta que estamos de volta ao * No non, no ** s?

913
01:10:39,920 --> 01:10:42,990
Contén nunca vai ter usar un ** nodo,

914
01:10:42,990 --> 01:10:45,480
unha vez que non está modificando de punteiros.

915
01:10:45,480 --> 01:10:50,540
Nós só estamos atravesando eles.

916
01:10:50,540 --> 01:10:53,830
Se isto acontecer, entón nós queremos voltar true.

917
01:10:53,830 --> 01:10:58,270
Outra cousa que quere percorrer os nenos.

918
01:10:58,270 --> 01:11:02,620
Polo tanto, non podemos razoar sobre todo para a esquerda é menos

919
01:11:02,620 --> 01:11:05,390
e todo para a dereita e maior.

920
01:11:05,390 --> 01:11:09,590
Entón o que está a nosa condición será aquí - ou, o que é que imos facer?

921
01:11:09,590 --> 01:11:11,840
[Estudante, inintelixible] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Retorno contén (valor, árbore-> esquerda)

923
01:11:17,400 --> 01:11:26,860
ou contén (valor, árbore-> dereita). E é iso.

924
01:11:26,860 --> 01:11:29,080
E en conta que hai algún tipo de avaliación de cortocircuíto,

925
01:11:29,080 --> 01:11:32,520
onde se ocorrer de atopar o valor na árbore esquerda,

926
01:11:32,520 --> 01:11:36,820
nunca necesitamos mirar para a árbore correcta.

927
01:11:36,820 --> 01:11:40,430
Esa é a función enteira.

928
01:11:40,430 --> 01:11:43,690
Agora imos facelo de forma iterativa,

929
01:11:43,690 --> 01:11:48,060
que vai ser menos agradable.

930
01:11:48,060 --> 01:11:54,750
Imos levar o comezo habitual do nodo actual * = árbore.

931
01:11:54,750 --> 01:12:03,250
Mentres (act! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rapidamente vai ver un problema.

933
01:12:08,600 --> 01:12:12,250
Se actual - aquí, se algunha vez saír desa,

934
01:12:12,250 --> 01:12:16,020
entón, temos acabar de cousas para mirar, entón volva falso.

935
01:12:16,020 --> 01:12:24,810
If (actual-> valor valor ==), retorna true.

936
01:12:24,810 --> 01:12:32,910
Entón, agora, estamos nun lugar -

937
01:12:32,910 --> 01:12:36,250
non sabemos se queremos ir á esquerda ou á dereita.

938
01:12:36,250 --> 01:12:44,590
Entón, arbitrariamente, imos ir á esquerda.

939
01:12:44,590 --> 01:12:47,910
Eu, obviamente, executar un problema onde eu completamente abandonado todo -

940
01:12:47,910 --> 01:12:50,760
Eu sempre só comprobar no lado esquerdo dunha árbore.

941
01:12:50,760 --> 01:12:56,050
Eu nunca vou comprobar todo o que é un dereito do neno de calquera cousa.

942
01:12:56,050 --> 01:13:00,910
¿Como corrixir isto?

943
01:13:00,910 --> 01:13:05,260
[Estudante] Ten que manter o control da esquerda e da dereita en unha pila.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Entón, imos facelo

945
01:13:13,710 --> 01:13:32,360
struct lista, no * n, e despois no ** próximo?

946
01:13:32,360 --> 01:13:40,240
Eu creo que funciona ben.

947
01:13:40,240 --> 01:13:45,940
Queremos ir máis á esquerda, ou imos - ata aquí.

948
01:13:45,940 --> 01:13:54,350
Struct = Lista da lista, que vai comezar

949
01:13:54,350 --> 01:13:58,170
fóra desta lista struct.

950
01:13:58,170 --> 01:14:04,040
* Lista = NULL. Así que vai ser a nosa lista encadeada

951
01:14:04,040 --> 01:14:08,430
de sub-árbores que pulamos.

952
01:14:08,430 --> 01:14:13,800
Nós imos atravesar queda agora

953
01:14:13,800 --> 01:14:17,870
pero desde que inevitablemente ten que volver para a dereita,

954
01:14:17,870 --> 01:14:26,140
Nós imos manter o lado dereito dentro da nosa lista struct.

955
01:14:26,140 --> 01:14:32,620
Entón nós imos ter new_list ou estrutura,

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
Vou ignorar verificación de erros que, pero ten que comprobar a ver se é nulo.

958
01:14:44,920 --> 01:14:50,540
New_list o no que vai apuntar -

959
01:14:50,540 --> 01:14:56,890
oh, é por iso que eu quería aquí. Vai apuntar unha lista struct segundo.

960
01:14:56,890 --> 01:15:02,380
É así que conectado listas traballo.

961
01:15:02,380 --> 01:15:04,810
Este é o mesmo como unha lista ligada int

962
01:15:04,810 --> 01:15:06,960
excepto estamos só substituíndo int con * nodo.

963
01:15:06,960 --> 01:15:11,040
É exactamente o mesmo.

964
01:15:11,040 --> 01:15:15,100
Entón new_list, o valor do noso nodo new_list,

965
01:15:15,100 --> 01:15:19,120
vai ser actual-> dereita.

966
01:15:19,120 --> 01:15:24,280
O valor da nosa new_list-> seguinte vai ser a nosa lista orixinal,

967
01:15:24,280 --> 01:15:30,760
e despois imos actualizar a nosa lista para apuntar para new_list.

968
01:15:30,760 --> 01:15:33,650
>> Agora necesitamos algún tipo de forma de cousas tirando,

969
01:15:33,650 --> 01:15:37,020
como temos atravesado toda a subárvore esquerda.

970
01:15:37,020 --> 01:15:40,480
Agora necesitamos sacar algo de fóra,

971
01:15:40,480 --> 01:15:43,850
como actual é nulo, nós non queremos só retornar falso.

972
01:15:43,850 --> 01:15:50,370
Queremos agora tirar fóra a nosa nova lista.

973
01:15:50,370 --> 01:15:53,690
Un xeito cómodo de facelo - Ben, en realidade, hai moitas maneiras de facelo.

974
01:15:53,690 --> 01:15:56,680
Alguén ten algunha suxestión?

975
01:15:56,680 --> 01:15:58,790
Onde eu debería facelo ou como eu debería facelo?

976
01:15:58,790 --> 01:16:08,010
Nós só temos un par de minutos, pero algunha suxestión?

977
01:16:08,010 --> 01:16:14,750
En vez de - unha forma, ao contrario da nosa condición de ser ao mesmo tempo,

978
01:16:14,750 --> 01:16:17,090
o que estamos actualmente a analizar non é nulo,

979
01:16:17,090 --> 01:16:22,340
en vez diso, imos continuar a ir ata a nosa propia lista é nulo.

980
01:16:22,340 --> 01:16:25,680
Entón, se a nosa lista acaba sendo nula,

981
01:16:25,680 --> 01:16:30,680
entón temos máis cousas para buscar, investigar.

982
01:16:30,680 --> 01:16:39,860
Pero isto significa que a primeira cousa na nosa lista vai só para ser o primeiro en.

983
01:16:39,860 --> 01:16:49,730
A primeira cousa que vai ser - non precisa ver iso.

984
01:16:49,730 --> 01:16:58,710
Entón, lista-> n será a nosa árbore.

985
01:16:58,710 --> 01:17:02,860
Lista-> seguinte vai ser nulo.

986
01:17:02,860 --> 01:17:07,580
E agora, mentres que a lista non nula igual.

987
01:17:07,580 --> 01:17:11,610
Cur vai tirar algo da nosa lista.

988
01:17:11,610 --> 01:17:13,500
Entón actual vai igual lista-> n.

989
01:17:13,500 --> 01:17:20,850
E entón lista vai igual lista-> n, ou lista-> seguinte.

990
01:17:20,850 --> 01:17:23,480
Así se o valor é igual ao valor actual.

991
01:17:23,480 --> 01:17:28,790
Agora podemos engadir tanto o punteiro noso dereito eo noso punteiro esquerdo

992
01:17:28,790 --> 01:17:32,900
sempre que non é nulo.

993
01:17:32,900 --> 01:17:36,390
Ata aquí, creo que debería ter feito isto en primeiro lugar.

994
01:17:36,390 --> 01:17:44,080
Se (cur-> seguro! = NULL)

995
01:17:44,080 --> 01:17:56,380
despois imos introducir o nó na nosa lista.

996
01:17:56,380 --> 01:17:59,290
Se (cur-> esquerda), que é un pouco de traballo extra, pero está todo ben.

997
01:17:59,290 --> 01:18:02,690
Se (cur-> esquerda! = NULL),

998
01:18:02,690 --> 01:18:14,310
e imos introducir á esquerda na nosa lista ligada,

999
01:18:14,310 --> 01:18:19,700
e que debe ser iso.

1000
01:18:19,700 --> 01:18:22,670
Repetimos - mentres temos algo na nosa lista,

1001
01:18:22,670 --> 01:18:26,640
temos outro no para ollar.

1002
01:18:26,640 --> 01:18:28,920
Entón, miramos para este nodo,

1003
01:18:28,920 --> 01:18:31,390
nós avanzamos nosa lista para a próxima.

1004
01:18:31,390 --> 01:18:34,060
Se ese nodo é o valor que estamos a buscar, podemos volver true.

1005
01:18:34,060 --> 01:18:37,640
Else introducir dúas subárvores nosa esquerda e á dereita,

1006
01:18:37,640 --> 01:18:40,510
sempre que non é nulo, na nosa lista

1007
01:18:40,510 --> 01:18:43,120
de xeito que, inevitablemente, pasar por riba deles.

1008
01:18:43,120 --> 01:18:45,160
Entón, se eles non foron nulos,

1009
01:18:45,160 --> 01:18:47,950
a nosa raíz punteiro apuntaba para dúas cousas,

1010
01:18:47,950 --> 01:18:51,670
a continuación, o primeiro, tirou algo para fóra para a nosa lista acaba sendo nulo.

1011
01:18:51,670 --> 01:18:56,890
E, entón, poñer dúas cousas de volta, agora a nosa lista de tamaño 2.

1012
01:18:56,890 --> 01:19:00,030
Entón imos facer un loop de volta e nós só estamos indo a tirar,

1013
01:19:00,030 --> 01:19:04,250
imos dicir, o punteiro esquerdo do noso nodo raíz.

1014
01:19:04,250 --> 01:19:07,730
E iso só vai continuar a suceder, nós imos acabar looping sobre todo.

1015
01:19:07,730 --> 01:19:11,280
>> Nótese que esta era significativamente máis complicado

1016
01:19:11,280 --> 01:19:14,160
na solución recursiva.

1017
01:19:14,160 --> 01:19:17,260
E eu xa dixen varias veces

1018
01:19:17,260 --> 01:19:25,120
que a solución recursiva ten normalmente moito máis en común coa solución iterativa.

1019
01:19:25,120 --> 01:19:30,820
Aquí é exactamente iso que a solución recursiva é facendo.

1020
01:19:30,820 --> 01:19:36,740
A única modificación é que en vez de implicitamente mediante a pila, a pila de programa,

1021
01:19:36,740 --> 01:19:40,840
como a súa forma de manter o control do que aínda precisa visitar,

1022
01:19:40,840 --> 01:19:45,430
agora ten que explicitamente usar unha lista ligada.

1023
01:19:45,430 --> 01:19:49,070
En ambos os casos está mantendo a par do que aínda precisa de a ser visitado.

1024
01:19:49,070 --> 01:19:51,790
No caso recursivo é só máis fácil, porque unha pila

1025
01:19:51,790 --> 01:19:57,100
é aplicado para ti como a pila do programa.

1026
01:19:57,100 --> 01:19:59,550
Nótese que esta lista ligada, é unha pila.

1027
01:19:59,550 --> 01:20:01,580
Todo o que pode poñer na pila

1028
01:20:01,580 --> 01:20:09,960
é inmediatamente o que nós imos retirar a pila para próxima visita.

1029
01:20:09,960 --> 01:20:14,380
Estamos fóra do tempo, pero algunha dúbida?

1030
01:20:14,380 --> 01:20:23,530
[Estudante, inintelixible]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Entón, se temos a nosa lista ligada,

1032
01:20:27,790 --> 01:20:30,150
actual está indo a apuntar para este cara,

1033
01:20:30,150 --> 01:20:34,690
e agora nós estamos só avanzar nosa lista ligada a concentrar-se sobre este cara.

1034
01:20:34,690 --> 01:20:44,200
Estamos atravesando sobre a lista ligada nesa liña.

1035
01:20:44,200 --> 01:20:51,200
E entón eu creo que debemos liberar a nosa lista encadeada e outras cousas

1036
01:20:51,200 --> 01:20:53,880
unha vez antes de regresar verdadeiro ou falso, necesitamos

1037
01:20:53,880 --> 01:20:57,360
iterar sobre a nosa lista conexionada e sempre aquí, eu creo,

1038
01:20:57,360 --> 01:21:03,900
se actual dereito non é igual, engadir lo, entón agora queremos liberar

1039
01:21:03,900 --> 01:21:09,600
actual porque, así, que nos esquecemos completamente sobre a lista? Si

1040
01:21:09,600 --> 01:21:12,880
Entón é iso que queremos facer aquí.

1041
01:21:12,880 --> 01:21:16,730
Onde está o punteiro?

1042
01:21:16,730 --> 01:21:23,320
Cur era entón - queremos unha lista struct * 10 é igual a próxima lista.

1043
01:21:23,320 --> 01:21:29,240
Lista libre, list = tempo.

1044
01:21:29,240 --> 01:21:32,820
E no caso de que volvemos realidade, necesitamos iterar

1045
01:21:32,820 --> 01:21:37,050
sobre o resto da nosa lista ligada liberando cousas.

1046
01:21:37,050 --> 01:21:39,700
O agradable sobre a solución recursiva é liberar as cousas

1047
01:21:39,700 --> 01:21:44,930
significa só factorings popping fóra da pila que vai ocorrer para ti.

1048
01:21:44,930 --> 01:21:50,720
Entón, nós fomos algo que é como 3 liñas de difícil pensar sobre o código

1049
01:21:50,720 --> 01:21:57,520
a algo que é significativamente máis moitos de difícil pensar-sobre liñas de código.

1050
01:21:57,520 --> 01:22:00,620
Algunha pregunta?

1051
01:22:00,620 --> 01:22:08,760
Todo ben. Somos bos. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]