1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Seção 7: Mais Confortável]

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
Tudo bem. Então, como eu disse no meu e-mail,

5
00:00:10,110 --> 00:00:14,060
isso vai ser uma seção binário-tree-intensivo.

6
00:00:14,060 --> 00:00:16,820
Mas não há que muitas questões.

7
00:00:16,820 --> 00:00:18,920
Então, nós estamos indo para tentar extrair de cada pergunta

8
00:00:18,920 --> 00:00:25,430
e entrar em detalhes dolorosa de todas as melhores maneiras de fazer as coisas.

9
00:00:25,430 --> 00:00:31,200
Assim, logo no início, passamos por desenhos de amostragem de árvores binárias e outras coisas.

10
00:00:31,200 --> 00:00:35,970
Então, aqui, "Lembre-se que uma árvore binária tem nós semelhantes aos de uma lista ligada,

11
00:00:35,970 --> 00:00:38,150
exceto em vez de um ponteiro, há duas: uma para "criança" à esquerda

12
00:00:38,150 --> 00:00:41,950
e um para a "criança" certo ".

13
00:00:41,950 --> 00:00:45,630
Assim, uma árvore binária é como uma lista ligada,

14
00:00:45,630 --> 00:00:47,910
exceto a estrutura vai ter dois ponteiros.

15
00:00:47,910 --> 00:00:51,390
Há árvores trinário, que vão ter três ponteiros,

16
00:00:51,390 --> 00:00:56,540
existem N-ary árvores, que só tem um ponteiro genérico

17
00:00:56,540 --> 00:01:00,320
que então você tem que malloc para ser grande o suficiente para ter

18
00:01:00,320 --> 00:01:04,840
ponteiros suficientes para todas as crianças possíveis.

19
00:01:04,840 --> 00:01:08,200
Então árvore binária só acontece de ter um número constante de dois.

20
00:01:08,200 --> 00:01:11,260
Se você quiser, você pode dar uma lista encadeada como uma árvore unário,

21
00:01:11,260 --> 00:01:15,360
mas eu não acho que ninguém chama isso.

22
00:01:15,360 --> 00:01:18,060
"Desenhe um diagrama de caixas-e-flechas de um nó de árvore binária

23
00:01:18,060 --> 00:01:24,110
contendo o número favorito de Nate, 7, em que cada ponteiro criança é nulo. "

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

25
00:01:27,780 --> 00:01:30,280
>> Vai ser bastante simples.

26
00:01:30,280 --> 00:01:36,150
Nós só vamos ter um nó, eu vou desenhá-lo como um quadrado.

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

28
00:01:38,730 --> 00:01:41,090
Portanto, o valor deverá ser aqui,

29
00:01:41,090 --> 00:01:44,770
e aqui nós vamos ter o ponteiro para a esquerda à esquerda e à direita o ponteiro à direita.

30
00:01:44,770 --> 00:01:50,430
E é muito assim convenção para chamá-lo de esquerda e direita, os nomes de ponteiro.

31
00:01:50,430 --> 00:01:52,460
Ambos vão ser nulo.

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

33
00:01:57,870 --> 00:02:03,630
Okay. Então, de volta para aqui.

34
00:02:03,630 --> 00:02:05,700
"Com uma lista ligada, tínhamos apenas para armazenar um ponteiro

35
00:02:05,700 --> 00:02:09,639
para o primeiro nó na lista para lembrar toda a lista ligada, ou toda a lista.

36
00:02:09,639 --> 00:02:11,650
Da mesma forma, com árvores, só temos que armazenar um ponteiro

37
00:02:11,650 --> 00:02:13,420
a um único nó, a fim de lembrar a árvore inteira.

38
00:02:13,420 --> 00:02:15,980
Este nodo é o calle "raiz" da árvore.

39
00:02:15,980 --> 00:02:18,320
Construir sobre o seu diagrama de antes ou desenhar um novo

40
00:02:18,320 --> 00:02:21,690
de tal forma que você tem uma representação caixas-e-flechas de uma árvore binária

41
00:02:21,690 --> 00:02:25,730
com o valor 7, em seguida, 3 no lado esquerdo,

42
00:02:25,730 --> 00:02:32,760
e depois 9, à direita, e em seguida 6, à direita da extremidade 3 ".

43
00:02:32,760 --> 00:02:34,810
Vamos ver se eu consigo me lembrar de tudo isso na minha cabeça.

44
00:02:34,810 --> 00:02:37,670
Portanto, esta vai ser a nossa raiz aqui.

45
00:02:37,670 --> 00:02:41,600
Nós vamos ter algum ponteiro em algum lugar, algo que chamaremos de raiz,

46
00:02:41,600 --> 00:02:45,140
e ele está apontando para esse cara.

47
00:02:45,140 --> 00:02:48,490
Agora, para fazer um novo nó,

48
00:02:48,490 --> 00:02:52,870
o que temos, três à esquerda?

49
00:02:52,870 --> 00:02:57,140
Assim, um novo nó com 3, e aponta inicialmente nula.

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

51
00:02:59,190 --> 00:03:02,250
Agora nós queremos fazer com que vá para a esquerda, de 7.

52
00:03:02,250 --> 00:03:06,840
Então nós mudar este ponteiro para apontar agora para esse cara.

53
00:03:06,840 --> 00:03:12,420
E nós fazemos o mesmo. Queremos um 9 aqui

54
00:03:12,420 --> 00:03:14,620
que, inicialmente, apenas diz nulo.

55
00:03:14,620 --> 00:03:19,600
Nós vamos mudar este ponteiro ponto, a 9,

56
00:03:19,600 --> 00:03:23,310
e agora queremos colocar 6 à direita de 3.

57
00:03:23,310 --> 00:03:32,170
Então, ele vai - fazer um 6.

58
00:03:32,170 --> 00:03:34,310
E esse cara vai apontar lá.

59
00:03:34,310 --> 00:03:38,320
Okay. Então, isso é tudo o que nos pede para fazer.

60
00:03:38,320 --> 00:03:42,770
>> Agora vamos passar por cima de alguma terminologia.

61
00:03:42,770 --> 00:03:46,690
Nós já falamos sobre como a raiz da árvore é o nó mais alto da árvore.

62
00:03:46,690 --> 00:03:54,720
A uma contendo 7. Os nós na parte inferior da árvore são chamados as folhas.

63
00:03:54,720 --> 00:04:01,240
Qualquer nó que só tem nulo como seus filhos é uma folha.

64
00:04:01,240 --> 00:04:03,680
Por isso, é possível, se a nossa árvore binária é apenas um único nó,

65
00:04:03,680 --> 00:04:10,130
que uma árvore é uma folha, e é isso.

66
00:04:10,130 --> 00:04:12,060
"O 'altura' da árvore é o número de saltos que você tem que fazer

67
00:04:12,060 --> 00:04:16,620
para obter a partir do topo de uma folha. "

68
00:04:16,620 --> 00:04:18,640
Nós vamos entrar, em um segundo, a diferença

69
00:04:18,640 --> 00:04:21,940
entre árvores binárias balanceadas e não balanceadas,

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

71
00:04:29,470 --> 00:04:34,520
Eu diria que é 3, embora, se você contar o número de saltos

72
00:04:34,520 --> 00:04:39,710
você tem que fazer a fim de obter a 9, então é realmente apenas uma altura de 2.

73
00:04:39,710 --> 00:04:43,340
Agora esta é uma árvore binária não balanceada,

74
00:04:43,340 --> 00:04:49,840
mas nós conversamos sobre equilibrada quando se chega a ser relevante.

75
00:04:49,840 --> 00:04:52,040
Então agora podemos falar sobre nós em uma árvore, em termos

76
00:04:52,040 --> 00:04:54,700
em relação aos outros nós na árvore.

77
00:04:54,700 --> 00:04:59,730
Portanto, agora temos os pais, filhos, irmãos, antepassados ​​e descendentes.

78
00:04:59,730 --> 00:05:05,650
São sentido bastante comum, o que eles significam.

79
00:05:05,650 --> 00:05:09,610
Se perguntarmos - É pais.

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

81
00:05:12,830 --> 00:05:16,090
[Os alunos] 7. Sim >>. O pai está indo só para ser o que aponta para você.

82
00:05:16,090 --> 00:05:20,510
Então, o que são as crianças de 7?

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

84
00:05:23,860 --> 00:05:26,460
Observe que "crianças" significa literalmente filhos,

85
00:05:26,460 --> 00:05:31,010
para 6 não se aplica, porque é como um neto.

86
00:05:31,010 --> 00:05:35,540
Mas, então, se formos descendentes, então o que são os descendentes de 7?

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

88
00:05:37,500 --> 00:05:42,330
Os descendentes do nó raiz vai ser tudo na árvore,

89
00:05:42,330 --> 00:05:47,950
exceto, talvez, o nó de raiz em si, se você não quer considerar que um descendente.

90
00:05:47,950 --> 00:05:50,750
E, finalmente, os ancestrais, por isso é a direção oposta.

91
00:05:50,750 --> 00:05:55,740
Então, quais são os ancestrais de 6?

92
00:05:55,740 --> 00:05:58,920
[Os alunos] 3 e 7. Sim >>. 9 não está incluído.

93
00:05:58,920 --> 00:06:02,520
É apenas a linhagem direta de volta à raiz

94
00:06:02,520 --> 00:06:13,230
vai ser seus antepassados.

95
00:06:13,230 --> 00:06:16,300
>> "Dizemos que uma árvore binária é" ordenada ", se para cada nó na árvore,

96
00:06:16,300 --> 00:06:19,530
todos os seus descendentes no lado esquerdo têm valores menores

97
00:06:19,530 --> 00:06:22,890
e todos os da direita têm valores maiores.

98
00:06:22,890 --> 00:06:27,060
Por exemplo, a árvore acima é ordenada, mas não é o único arranjo possível ordenada. "

99
00:06:27,060 --> 00:06:30,180
Antes de chegarmos a isso,

100
00:06:30,180 --> 00:06:36,420
uma árvore binária ordenada é também conhecido como uma árvore de pesquisa binária.

101
00:06:36,420 --> 00:06:38,660
Aqui nós acontecer de ser chamando de uma árvore binária ordenada,

102
00:06:38,660 --> 00:06:41,850
mas eu nunca ouvi-lo chamado de uma árvore binária ordenada antes,

103
00:06:41,850 --> 00:06:46,650
e em um quiz que são muito mais propensos a colocar árvore de busca binária.

104
00:06:46,650 --> 00:06:49,250
Eles são uma ea mesma coisa,

105
00:06:49,250 --> 00:06:54,580
e é importante que você reconhece a distinção entre árvore binária e árvore de busca binária.

106
00:06:54,580 --> 00:06:58,830
Uma árvore binária é apenas uma árvore que aponta para duas coisas.

107
00:06:58,830 --> 00:07:02,120
Cada nó aponta para duas coisas.

108
00:07:02,120 --> 00:07:06,310
Não há raciocínio sobre os valores que ele aponta para.

109
00:07:06,310 --> 00:07:11,370
Assim como aqui, já que é uma árvore de busca binária,

110
00:07:11,370 --> 00:07:14,030
nós sabemos que se vá para a esquerda, de 7,

111
00:07:14,030 --> 00:07:16,670
em seguida, todos os valores que podem possivelmente alcançar

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

113
00:07:19,310 --> 00:07:24,070
Note-se que todos os valores menores do que 7 são 3 e 6.

114
00:07:24,070 --> 00:07:26,040
Essas são todas para a esquerda, de 7.

115
00:07:26,040 --> 00:07:29,020
Se formos para a direita, de 7, tudo tem que ser maior do que 7,

116
00:07:29,020 --> 00:07:33,220
para 9 é para a direita, de 7, por isso estamos bem.

117
00:07:33,220 --> 00:07:36,150
Este não é o caso de uma árvore binária,

118
00:07:36,150 --> 00:07:40,020
para uma árvore binária regulares, podemos ter apenas três no topo, 7 para a esquerda,

119
00:07:40,020 --> 00:07:47,630
9 para a esquerda, de 7, não há nenhuma ordenação de valores, em absoluto.

120
00:07:47,630 --> 00:07:56,140
Agora, nós realmente não vai fazer isso porque é tedioso e desnecessário,

121
00:07:56,140 --> 00:07:59,400
mas "tentar desenhar como muitas árvores ordenadas como você 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
Quantos arranjos distintos existem? O que é a altura de cada um? "

124
00:08:06,800 --> 00:08:10,480
>> Nós vamos fazer um casal, mas a idéia principal é,

125
00:08:10,480 --> 00:08:16,530
isto é, de modo algum uma representação singular de uma árvore binária contendo esses valores.

126
00:08:16,530 --> 00:08:22,760
Tudo o que precisamos é de uma árvore binária que contém 7, 3, 6 e 9.

127
00:08:22,760 --> 00:08:25,960
Outra possível válida seria a raiz é 3,

128
00:08:25,960 --> 00:08:30,260
vá para a esquerda e é 6, vá para a esquerda e é 7,

129
00:08:30,260 --> 00:08:32,730
para a esquerda e é 9.

130
00:08:32,730 --> 00:08:36,169
Que é uma árvore de pesquisa binária perfeitamente válida.

131
00:08:36,169 --> 00:08:39,570
Não é muito útil, porque é como uma lista ligada

132
00:08:39,570 --> 00:08:43,750
e todos esses ponteiros são apenas nulo.

133
00:08:43,750 --> 00:08:48,900
Mas é uma árvore válido. Sim?

134
00:08:48,900 --> 00:08:51,310
[Estudante] Não os valores têm que ser maior do lado direito?

135
00:08:51,310 --> 00:08:56,700
Ou isso é -? Estes >> eu quis ir por outro caminho.

136
00:08:56,700 --> 00:09:00,960
Há também - sim, vamos mudar isso.

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

138
00:09:07,770 --> 00:09:11,730
Ele ainda tem que obedecer o que uma árvore de busca binária é suposto fazer.

139
00:09:11,730 --> 00:09:15,650
Assim, tudo o que o lado esquerdo tem de ser menor que qualquer dado nó.

140
00:09:15,650 --> 00:09:23,180
Nós poderíamos apenas mudar, por exemplo, este 6 e colocá-lo aqui.

141
00:09:23,180 --> 00:09:26,880
Não, não podemos. Por que eu continuo fazendo isso?

142
00:09:26,880 --> 00:09:35,350
Vamos fazer - aqui é 6, aqui é 7, 6 pontos a 3.

143
00:09:35,350 --> 00:09:39,290
Esta ainda é uma árvore de busca binária válido.

144
00:09:39,290 --> 00:09:49,260
O que é errado se eu - vamos ver se consigo chegar a um acordo.

145
00:09:49,260 --> 00:09:52,280
Sim, está bem. Então, o que está errado com esta árvore?

146
00:09:52,280 --> 00:10:08,920
Eu acho que eu já lhe deu uma dica de que há algo de errado com ele.

147
00:10:08,920 --> 00:10:14,430
Por que eu continuo fazendo isso?

148
00:10:14,430 --> 00:10:18,510
Okay. Isso parece razoável.

149
00:10:18,510 --> 00:10:22,590
Se olharmos para cada nó, como o 7, em seguida, para a esquerda da Fig. 7 é uma 3.

150
00:10:22,590 --> 00:10:24,960
Portanto, temos três, a única coisa para a direita de 3 é um 6.

151
00:10:24,960 --> 00:10:27,750
E se você olhar para 6, a coisa à direita do 6 é um 9.

152
00:10:27,750 --> 00:10:30,910
Então, por que isso não é uma árvore de busca binária válida?

153
00:10:30,910 --> 00:10:36,330
[Os alunos] 9 é ainda para a esquerda, de 7. Sim >>.

154
00:10:36,330 --> 00:10:43,710
Deve ser verdade que todos os valores que podem ser possivelmente alcançar, indo para a esquerda, de 7 estão a menos de 7.

155
00:10:43,710 --> 00:10:49,120
Se ir para a esquerda, de 7, temos a 3 e ainda podemos chegar a 6,

156
00:10:49,120 --> 00:10:52,520
ainda podemos chegar a 9, mas por ter passado menos de 7,

157
00:10:52,520 --> 00:10:55,070
não deve ser capaz de chegar a um número que é maior do que 7.

158
00:10:55,070 --> 00:10:59,830
Então isso não é uma árvore de busca binária válido.

159
00:10:59,830 --> 00:11:02,330
>> Meu irmão realmente tinha uma pergunta da entrevista

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

161
00:11:07,760 --> 00:11:10,500
se uma árvore é uma árvore de busca binária,

162
00:11:10,500 --> 00:11:13,580
e então a primeira coisa que ele fez foi apenas verificar para ver

163
00:11:13,580 --> 00:11:17,020
se a esquerda e direita estão corretas, e depois repetir lá em baixo.

164
00:11:17,020 --> 00:11:19,700
Mas você não pode simplesmente fazer isso, você tem que manter o controle

165
00:11:19,700 --> 00:11:22,550
do fato de que, agora que eu fui deixado de 7,

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

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

168
00:11:28,430 --> 00:11:35,970
dos limites que os valores podem eventualmente caem dentro

169
00:11:35,970 --> 00:11:38,360
Nós não vamos passar por todos eles.

170
00:11:38,360 --> 00:11:41,630
Há uma relação de recorrência agradável,

171
00:11:41,630 --> 00:11:44,810
embora não se tenha chegado a esses, ou não vamos chegar a esses,

172
00:11:44,810 --> 00:11:47,030
definir quantos realmente são.

173
00:11:47,030 --> 00:11:53,180
Portanto, há 14 deles.

174
00:11:53,180 --> 00:11:56,020
A idéia de como você faria isso matematicamente é como,

175
00:11:56,020 --> 00:11:59,770
você pode escolher qualquer um única de ser o nó raiz,

176
00:11:59,770 --> 00:12:03,160
e então se eu pegar de 7 a ser o nó raiz,

177
00:12:03,160 --> 00:12:08,150
em seguida, há, por exemplo, alguns números que podem ir ser meu nó esquerdo,

178
00:12:08,150 --> 00:12:10,440
e há alguns números que pode ser meu nó direito,

179
00:12:10,440 --> 00:12:15,090
mas se eu tiver n números totais, o montante que pode ir para a esquerda

180
00:12:15,090 --> 00:12:18,820
mais o montante que pode ir para a direita é n - 1.

181
00:12:18,820 --> 00:12:26,130
Assim, os números restantes, eles têm que ser capazes de ir, quer para a esquerda ou para a direita.

182
00:12:26,130 --> 00:12:31,580
Parece difícil que, se eu colocar 3 primeiro, então tudo tem que ir para a esquerda,

183
00:12:31,580 --> 00:12:35,080
mas se eu colocar 7, então algumas coisas podem ir a esquerda e algumas coisas podem ir para a direita.

184
00:12:35,080 --> 00:12:39,570
E por '3 'primeiro eu queria dizer tudo pode ir para a direita.

185
00:12:39,570 --> 00:12:42,350
É realmente, você só tem que pensar nisso como,

186
00:12:42,350 --> 00:12:47,980
quantas coisas podem ir no próximo nível da árvore.

187
00:12:47,980 --> 00:12:50,420
E vem a ser 14, ou você pode desenhar todos eles,

188
00:12:50,420 --> 00:12:54,650
e então você vai ter 14.

189
00:12:54,650 --> 00:13:01,120
>> Voltando aqui,

190
00:13:01,120 --> 00:13:03,510
"Ordenou árvores binárias são legais porque podemos procurar por eles

191
00:13:03,510 --> 00:13:06,910
de uma forma muito semelhante à procura de um array ordenado.

192
00:13:06,910 --> 00:13:10,120
Para isso, vamos começar na raiz e trabalhar nossa maneira para baixo da árvore

193
00:13:10,120 --> 00:13:13,440
para folhas, verificando os valores de cada nó contra os valores que estamos procurando.

194
00:13:13,440 --> 00:13:15,810
Se o valor do nó atual é menor do que o valor que está procurando,

195
00:13:15,810 --> 00:13:18,050
você vai ao lado direito da criança do nó.

196
00:13:18,050 --> 00:13:20,030
Caso contrário, você vai para o filho esquerdo do nó.

197
00:13:20,030 --> 00:13:22,800
Em algum momento, você quer encontrar o valor que você está procurando, ou você vai correr em um nulo,

198
00:13:22,800 --> 00:13:28,520
indicando o valor não está na árvore. "

199
00:13:28,520 --> 00:13:32,450
Eu tenho que redesenhar a árvore que tínhamos antes, que vai levar um segundo.

200
00:13:32,450 --> 00:13:38,280
Mas queremos olhar para cima se 6, 10, e um está na árvore.

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

202
00:13:49,180 --> 00:13:52,730
Os números que você quer olhar para cima, queremos olhar para cima 6.

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

204
00:13:55,440 --> 00:14:03,040
Bem, também temos alguns ponteiro raiz para a nossa árvore.

205
00:14:03,040 --> 00:14:12,460
E nós ir à raiz e dizer, é este valor igual ao valor que estamos procurando?

206
00:14:12,460 --> 00:14:15,000
Então, nós estamos olhando para 6, por isso não é igual.

207
00:14:15,000 --> 00:14:20,140
Então, continue indo, e agora podemos dizer, ok, então 6 é inferior a 7.

208
00:14:20,140 --> 00:14:23,940
Isso quer dizer que nós queremos ir para a esquerda, ou queremos ir para a direita?

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

210
00:14:27,340 --> 00:14:33,340
É muito mais fácil, tudo que você tem a fazer é tirar um nó possível da árvore

211
00:14:33,340 --> 00:14:37,760
e então você não - em vez de tentar pensar em sua cabeça,

212
00:14:37,760 --> 00:14:40,020
Tudo bem, se é menos, eu vou para a esquerda ou para ir à direita,

213
00:14:40,020 --> 00:14:43,030
só de olhar para esta foto, é muito claro que eu tenho que ir para a esquerda

214
00:14:43,030 --> 00:14:47,700
se este nó é maior do que o valor que eu estou procurando.

215
00:14:47,700 --> 00:14:52,600
Então você vai para a esquerda, agora estou no 3.

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

217
00:14:57,770 --> 00:15:03,420
Então, vá para a direita, e agora eu acabar no 6,

218
00:15:03,420 --> 00:15:07,380
que é o valor que eu estou procurando, assim que eu retornar true.

219
00:15:07,380 --> 00:15:15,760
O valor que vem eu vou procurar é 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Então, 10, agora, vai - corte que - vai seguir a raiz.

221
00:15:23,230 --> 00:15:27,670
Agora, 10 vai ser maior do que 7, então eu quero olhar para a direita.

222
00:15:27,670 --> 00:15:31,660
Eu vou vir para cá, 10, vai ser maior do que 9,

223
00:15:31,660 --> 00:15:34,520
então eu vou querer olhar para a direita.

224
00:15:34,520 --> 00:15:42,100
Eu venho aqui, mas aqui agora estou em nulo.

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

226
00:15:44,170 --> 00:15:47,440
[Estudante] Retornar falso? Sim >>. Eu não encontrei 10.

227
00:15:47,440 --> 00:15:49,800
1 vai ser um caso quase idêntico,

228
00:15:49,800 --> 00:15:51,950
exceto que ele só vai ser invertida, em vez de olhar

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

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

231
00:16:00,430 --> 00:16:04,070
Aqui é onde - abra o aparelho CS50 e navegar no seu caminho,

232
00:16:04,070 --> 00:16:07,010
mas você pode também fazê-lo apenas no espaço.

233
00:16:07,010 --> 00:16:09,170
Provavelmente é ideal para fazê-lo no espaço,

234
00:16:09,170 --> 00:16:13,760
porque podemos trabalhar no espaço.

235
00:16:13,760 --> 00:16:19,170
"Primeiro vamos precisar de uma nova definição de tipo para um nó de árvore binário contendo 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
criar uma nova definição de tipo para um nó em uma árvore binária.

238
00:16:24,510 --> 00:16:27,930
Se você ficar preso. . . "Blá, blá, blá. Okay.

239
00:16:27,930 --> 00:16:30,380
Então, vamos colocar o clichê aqui,

240
00:16:30,380 --> 00:16:41,630
nó typedef struct, e nó. Sim, está bem.

241
00:16:41,630 --> 00:16:44,270
Então, quais são os campos que vamos querer em nosso nó?

242
00:16:44,270 --> 00:16:46,520
[Estudante] Int e depois dois ponteiros?

243
00:16:46,520 --> 00:16:49,700
>> Valor Int, dois ponteiros? Como faço para escrever os ponteiros?

244
00:16:49,700 --> 00:16:58,440
[Estudante] Struct. >> Eu deveria fazer zoom in Sim, então nó struct * esquerda,

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

246
00:17:01,320 --> 00:17:03,460
E lembre-se a discussão da última vez,

247
00:17:03,460 --> 00:17:15,290
que isso não faz sentido, isso não faz sentido,

248
00:17:15,290 --> 00:17:18,270
isso não faz sentido.

249
00:17:18,270 --> 00:17:25,000
Você precisa de tudo o que há para definir essa estrutura recursiva.

250
00:17:25,000 --> 00:17:27,970
Ok, então é isso que nossa árvore vai ficar.

251
00:17:27,970 --> 00:17:37,670
Se fizéssemos uma árvore trinário, em seguida, um nó pode parecer b1, b2, struct node * b3,

252
00:17:37,670 --> 00:17:43,470
onde b é um ramo - na verdade, eu tenho mais ouvido à esquerda, meio, à direita, o que quer mas.

253
00:17:43,470 --> 00:17:55,610
Nós só se preocupam com binário, para direita, esquerda.

254
00:17:55,610 --> 00:17:59,110
"Agora declarar uma variável * mundial nó para a raiz da árvore."

255
00:17:59,110 --> 00:18:01,510
Então, nós não vamos fazer isso.

256
00:18:01,510 --> 00:18:08,950
A fim de tornar as coisas um pouco mais difícil e mais generalizado,

257
00:18:08,950 --> 00:18:11,570
não teremos uma variável nó global.

258
00:18:11,570 --> 00:18:16,710
Em vez disso, no principal que irá declarar todas as nossas coisas de nós,

259
00:18:16,710 --> 00:18:20,500
e isso significa que a seguir, quando começar a correr

260
00:18:20,500 --> 00:18:23,130
nossa função contém e nossa função de inserção,

261
00:18:23,130 --> 00:18:27,410
em vez de nossos contém função apenas usando essa variável nó global,

262
00:18:27,410 --> 00:18:34,280
nós vamos ter que tomar como um argumento a árvore que nós queremos que ele processar.

263
00:18:34,280 --> 00:18:36,650
Tendo a variável global era para facilitar as coisas.

264
00:18:36,650 --> 00:18:42,310
Nós vamos fazer as coisas mais difíceis.

265
00:18:42,310 --> 00:18:51,210
Agora pegue um minuto apenas para fazer esse tipo de coisa,

266
00:18:51,210 --> 00:18:57,690
onde dentro de principal que pretende criar esta árvore, e isso é tudo que você quer fazer.

267
00:18:57,690 --> 00:19:04,530
Tentar construir esta árvore em sua função principal.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Assim, você não precisa nem ter construído a árvore de todo o caminho ainda.

269
00:19:47,610 --> 00:19:49,840
Mas alguém tem algo que eu poderia puxar para cima

270
00:19:49,840 --> 00:20:03,130
para mostrar como se poderia começar a construir essa árvore?

271
00:20:03,130 --> 00:20:08,080
[Estudante] bater de alguém, tentando sair.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Qualquer confortável com a sua construção da árvore?

273
00:20:13,100 --> 00:20:15,520
[Estudante] Claro. Ele não é feito. >> Está tudo bem. Nós podemos apenas terminar -

274
00:20:15,520 --> 00:20:26,860
Oh, você pode salvá-lo? Hooray.

275
00:20:26,860 --> 00:20:32,020
Portanto, temos aqui - oh, eu estou um 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 fora. >> Eu tenho uma pergunta. >> Sim?

278
00:20:37,730 --> 00:20:44,410
[Estudante] Quando você define estrutura, são coisas como inicializado para alguma coisa?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Não. >> Okay. Então você teria que inicializar -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Não. Quando você definir, ou quando você declarar uma estrutura,

281
00:20:50,450 --> 00:20:55,600
não é inicializado por padrão, que é exatamente como se você declarar um int.

282
00:20:55,600 --> 00:20:59,020
É exatamente a mesma coisa. É como se cada um dos seus campos individuais

283
00:20:59,020 --> 00:21:04,460
pode ter um valor de lixo na mesma. >> E é possível definir - ou declarar uma struct

284
00:21:04,460 --> 00:21:07,740
de uma forma que ele não inicializa-la?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Sim. Então, sintaxe de inicialização atalho

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

287
00:21:18,660 --> 00:21:22,200
Há duas maneiras de fazer isso. Acho que devemos compilá-lo

288
00:21:22,200 --> 00:21:25,840
para fazer Clang certeza também faz isso.

289
00:21:25,840 --> 00:21:28,510
A ordem de argumentos que vem na estrutura,

290
00:21:28,510 --> 00:21:32,170
você colocou como a ordem dos argumentos dentro destas chaves.

291
00:21:32,170 --> 00:21:35,690
Então, se você quiser inicializar a 9 e deixou ser nulo e depois à direita ser nulo,

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

293
00:21:41,570 --> 00:21:47,890
A alternativa é, eo editor não gosta esta sintaxe,

294
00:21:47,890 --> 00:21:50,300
e ele pensa que eu quero um novo bloco,

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

296
00:22:01,800 --> 00:22:04,190
aqui, eu vou colocá-lo em uma nova linha.

297
00:22:04,190 --> 00:22:09,140
Você pode dizer explicitamente, eu esquecer a sintaxe exata.

298
00:22:09,140 --> 00:22:13,110
Assim, você pode abordar explicitamente os pelo nome, e dizer:

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

300
00:22:21,570 --> 00:22:24,540
Eu estou supondo que estes precisam ser vírgulas.

301
00:22:24,540 --> 00:22:29,110
. Direito = NULL, assim desta forma você não

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

303
00:22:33,780 --> 00:22:36,650
e quando você estiver lendo isto, é muito mais explícito

304
00:22:36,650 --> 00:22:41,920
sobre o que o valor está sendo inicializado para.

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

306
00:22:44,080 --> 00:22:49,100
assim, para a maior parte, C + + é um superconjunto de C.

307
00:22:49,100 --> 00:22:54,160
Você pode pegar o código C, movê-lo para C + +, e deve compilar.

308
00:22:54,160 --> 00:22:59,570
Esta é uma das coisas que o C + + não suporta, para que as pessoas tendem a não fazê-lo.

309
00:22:59,570 --> 00:23:01,850
Eu não sei se essa é a única razão pela qual as pessoas tendem a não fazê-lo,

310
00:23:01,850 --> 00:23:10,540
mas o caso em que eu precisava usá-lo necessário para trabalhar com C + + e assim eu não poderia usar isso.

311
00:23:10,540 --> 00:23:14,000
Outro exemplo de algo que não funciona com o C + + é

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

313
00:23:16,940 --> 00:23:20,200
mas você pode apenas dizer o que quer que char * x = malloc,

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

315
00:23:22,840 --> 00:23:25,450
Esse elenco automático não acontece em C + +.

316
00:23:25,450 --> 00:23:28,150
Isso não seria compilar, e você precisa dizer explicitamente

317
00:23:28,150 --> 00:23:34,510
char *, malloc, qualquer que seja, para lançá-lo para um char *.

318
00:23:34,510 --> 00:23:37,270
Não há muitas coisas que C e C + + discordam,

319
00:23:37,270 --> 00:23:40,620
mas esses são dois.

320
00:23:40,620 --> 00:23:43,120
Então vamos com esta sintaxe.

321
00:23:43,120 --> 00:23:46,150
Mas mesmo que não fosse com essa sintaxe,

322
00:23:46,150 --> 00:23:49,470
o que é - pode estar errado com isso?

323
00:23:49,470 --> 00:23:52,170
[Estudante] Eu não preciso excluir a referência é? Sim >>.

324
00:23:52,170 --> 00:23:55,110
Lembre-se de que a seta tem uma dereference implícito,

325
00:23:55,110 --> 00:23:58,230
e assim, quando estamos lidando apenas com uma estrutura,

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

327
00:24:04,300 --> 00:24:07,200
E a única vez que use a seta é quando nós queremos fazer -

328
00:24:07,200 --> 00:24:13,450
bem, a seta é equivalente à -

329
00:24:13,450 --> 00:24:17,020
isso é o que teria significado se eu usasse seta.

330
00:24:17,020 --> 00:24:24,600
Todos os meios de seta é, dereference isso, agora estou em uma estrutura, e eu posso obter o campo.

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

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

333
00:24:30,380 --> 00:24:33,910
Mas aqui eu estou lidando com apenas uma estrutura, não um ponteiro para uma estrutura,

334
00:24:33,910 --> 00:24:38,780
e por isso não pode usar a seta.

335
00:24:38,780 --> 00:24:47,510
Mas esse tipo de coisa que podemos fazer 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ão, podemos definir os ramos em nossa árvore, podemos ter 7 -

339
00:25:16,470 --> 00:25:21,650
Podemos ter, a sua esquerda deve apontar a 3.

340
00:25:21,650 --> 00:25:25,130
Então, como vamos fazer isso?

341
00:25:25,130 --> 00:25:29,320
[Estudantes, ininteligível] >> sim. O endereço do node3,

342
00:25:29,320 --> 00:25:34,170
e se você não tem endereço, então ele só não seria compilar.

343
00:25:34,170 --> 00:25:38,190
Mas lembre-se que estes são os ponteiros para os nós próximos.

344
00:25:38,190 --> 00:25:44,930
O direito deve apontar a 9,

345
00:25:44,930 --> 00:25:53,330
e 3 deve apontar sobre o direito à 6.

346
00:25:53,330 --> 00:25:58,480
Acho que isso é tudo pronto. Quaisquer comentários ou perguntas?

347
00:25:58,480 --> 00:26:02,060
[Estudante, ininteligível] A raiz vai ser 7.

348
00:26:02,060 --> 00:26:08,210
Podemos apenas dizer nó * ptr =

349
00:26:08,210 --> 00:26:14,160
ou raiz, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Para nossos propósitos, vamos estar lidando com a inserção,

351
00:26:20,730 --> 00:26:25,490
então vamos querer escrever uma função para inserir esta árvore binária

352
00:26:25,490 --> 00:26:34,230
e inserção é, inevitavelmente, vai chamar malloc para criar um novo nó para esta árvore.

353
00:26:34,230 --> 00:26:36,590
Assim, as coisas vão ficar confuso com o fato de que alguns nós

354
00:26:36,590 --> 00:26:38,590
Estão actualmente na pilha

355
00:26:38,590 --> 00:26:43,680
e outros nós vamos acabar na pilha quando inseri-los.

356
00:26:43,680 --> 00:26:47,640
Isso é perfeitamente válido, mas a única razão

357
00:26:47,640 --> 00:26:49,600
nós somos capazes de fazer isso na pilha

358
00:26:49,600 --> 00:26:51,840
é porque é um exemplo tão artificial que sabemos

359
00:26:51,840 --> 00:26:56,360
a árvore é suposto ser construído como 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Se não tem isso, então não teríamos a malloc em primeiro lugar.

361
00:27:02,970 --> 00:27:06,160
Como veremos um pouco mais tarde, devemos ser malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Agora é perfeitamente razoável para colocar na pilha,

363
00:27:08,570 --> 00:27:14,750
mas vamos mudar isso para uma implementação de malloc.

364
00:27:14,750 --> 00:27:17,160
Então, cada um deles agora vai ser algo como

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

366
00:27:24,240 --> 00:27:28,040
E agora nós vamos ter que fazer a nossa seleção.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Eu não queria que isso -

368
00:27:34,010 --> 00:27:40,950
retornar 1, e então nós podemos fazer node9-> porque agora é um ponteiro,

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

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

371
00:27:48,930 --> 00:27:51,410
e nós vamos ter que fazer isso para cada um desses nós.

372
00:27:51,410 --> 00:27:57,490
Então, em vez disso, vamos colocá-lo dentro de uma função separada.

373
00:27:57,490 --> 00:28:00,620
Vamos chamá-lo de nó * build_node,

374
00:28:00,620 --> 00:28:09,050
e isso é um pouco semelhante ao APIs nós fornecemos para codificação de Huffman.

375
00:28:09,050 --> 00:28:12,730
Nós damos-lhe funções inicializador para uma árvore

376
00:28:12,730 --> 00:28:20,520
e desconstrutor "funções" para as árvores e os mesmos para as florestas.

377
00:28:20,520 --> 00:28:22,570
>> Então aqui nós vamos ter uma função de inicialização

378
00:28:22,570 --> 00:28:25,170
apenas construir um nó para nós.

379
00:28:25,170 --> 00:28:29,320
E vai ficar muito bonito exatamente como este.

380
00:28:29,320 --> 00:28:32,230
E eu estou indo para ser preguiçoso e não mudar o nome da variável,

381
00:28:32,230 --> 00:28:34,380
embora node9 não faz mais sentido.

382
00:28:34,380 --> 00:28:38,610
Ah, eu acho que o valor do node9 não deveria ter sido 6.

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

384
00:28:42,800 --> 00:28:49,550
E aqui nós deve retornar nulo.

385
00:28:49,550 --> 00:28:52,690
Todos concordam em que a função build-a-nó?

386
00:28:52,690 --> 00:28:59,780
Então agora podemos chamar de que a construção de qualquer nó com um dado valor e ponteiros nulos.

387
00:28:59,780 --> 00:29:09,750
Agora nós podemos chamar isso, podemos fazer nó * node9 = build_node (9).

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

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 ponteiros mesmos,

391
00:29:39,330 --> 00:29:42,470
só que agora tudo está já em termos de ponteiros

392
00:29:42,470 --> 00:29:48,480
então não precisa mais o endereço do.

393
00:29:48,480 --> 00:29:56,300
Okay. Então, qual é a última coisa que eu quero fazer?

394
00:29:56,300 --> 00:30:03,850
Há um erro de verificação de que eu não estou fazendo.

395
00:30:03,850 --> 00:30:06,800
O que significa construir retorno nó?

396
00:30:06,800 --> 00:30:11,660
[Estudante, ininteligível] >> Yeah. Se malloc falhou, ele vai retornar nulo.

397
00:30:11,660 --> 00:30:16,460
Então, eu estou indo para preguiçosamente colocá-la aqui, em vez de fazer uma condição para cada um.

398
00:30:16,460 --> 00:30:22,320
Se (node9 == null, ou - ainda mais simples,

399
00:30:22,320 --> 00:30:28,020
isto é equivalente a apenas se não node9.

400
00:30:28,020 --> 00:30:38,310
Então, se não node9, ou não node6, ou não node3, ou não node7, retornar 1.

401
00:30:38,310 --> 00:30:42,850
Talvez devêssemos imprimir malloc falhou, ou algo assim.

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

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

404
00:30:51,290 --> 00:30:53,920
Assim nulo é um valor zero.

405
00:30:53,920 --> 00:30:56,780
Zero é um valor de zero. Falso é um valor zero.

406
00:30:56,780 --> 00:31:02,130
Qualquer - praticamente os únicos dois valores zero são nulas e zero,

407
00:31:02,130 --> 00:31:07,900
falsa é apenas de hash definido como zero.

408
00:31:07,900 --> 00:31:13,030
Isso também se aplica se nós declarar variável global.

409
00:31:13,030 --> 00:31:17,890
Se tinha raiz * nó aqui,

410
00:31:17,890 --> 00:31:24,150
então - a coisa agradável sobre variáveis ​​globais é que eles sempre têm um valor inicial.

411
00:31:24,150 --> 00:31:27,500
Isso não é verdade de funções, como aqui dentro,

412
00:31:27,500 --> 00:31:34,870
se temos, *, como nó ou nodo.

413
00:31:34,870 --> 00:31:37,380
Nós não temos idéia do que x.Value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
ou poderíamos imprimi-los e eles poderiam ser arbitrária.

415
00:31:40,700 --> 00:31:44,980
Isso não é verdade de variáveis ​​globais.

416
00:31:44,980 --> 00:31:47,450
Raiz para nó ou nodo.

417
00:31:47,450 --> 00:31:53,410
Por padrão, tudo o que é global, se não explicitamente inicializada com algum valor,

418
00:31:53,410 --> 00:31:57,390
tem um valor de zero, como o seu valor.

419
00:31:57,390 --> 00:32:01,150
Então, aqui, o nó raiz *, não explicitamente inicializá-lo a nada,

420
00:32:01,150 --> 00:32:06,350
portanto, seu valor padrão será nulo, que é o valor zero de ponteiros.

421
00:32:06,350 --> 00:32:11,870
O valor padrão de x vai significar que x.Value é zero,

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ão, uma vez que é uma estrutura, de todos os campos da estrutura serão os valores zero.

424
00:32:21,070 --> 00:32:24,410
Nós não precisamos usar isso aqui, no entanto.

425
00:32:24,410 --> 00:32:27,320
[Aluno] As estruturas são diferentes do que outras variáveis, e as outras variáveis ​​são

426
00:32:27,320 --> 00:32:31,400
valores de lixo, que são zeros?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Outros valores também. Assim, em x, x será zero.

428
00:32:36,220 --> 00:32:40,070
Se é no escopo global, que tem um valor inicial. Ok >>.

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

430
00:32:48,950 --> 00:32:53,260
Eu acho que cuida de tudo isso.

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

432
00:32:58,390 --> 00:33:01,260
"Agora queremos escrever uma função chamada contém

433
00:33:01,260 --> 00:33:04,930
com um protótipo de bool contém valor int. "

434
00:33:04,930 --> 00:33:08,340
Nós não vamos fazer bool contém valor int.

435
00:33:08,340 --> 00:33:15,110
Nosso protótipo está indo olhar como

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

437
00:33:22,380 --> 00:33:24,490
E então nós também vamos passar a árvore

438
00:33:24,490 --> 00:33:28,870
que deve ser a verificação para ver se ele tem esse valor.

439
00:33:28,870 --> 00:33:38,290
Então nó * árvore). Okay.

440
00:33:38,290 --> 00:33:44,440
E então podemos chamá-lo com algo como,

441
00:33:44,440 --> 00:33:46,090
talvez a gente vai querer printf ou algo assim.

442
00:33:46,090 --> 00:33:51,040
Contém 6, nossa raiz.

443
00:33:51,040 --> 00:33:54,300
Que deve retornar uma, ou verdadeiro,

444
00:33:54,300 --> 00:33:59,390
enquanto contém 5 raiz deve retornar falso.

445
00:33:59,390 --> 00:34:02,690
Então, tome um segundo para implementar isso.

446
00:34:02,690 --> 00:34:06,780
Você pode fazer isso de qualquer forma iterativa ou recursivamente.

447
00:34:06,780 --> 00:34:09,739
A coisa agradável sobre a maneira que nós definir as coisas é que

448
00:34:09,739 --> 00:34:12,300
presta-se a nossa solução recursiva muito mais fácil

449
00:34:12,300 --> 00:34:14,719
do que a forma global variável fez.

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

451
00:34:19,750 --> 00:34:24,130
Nós teríamos que ter uma função auxiliar separado que recurses as subárvores para nós.

452
00:34:24,130 --> 00:34:29,610
Mas desde que mudei-o a tomar a árvore como um argumento,

453
00:34:29,610 --> 00:34:32,760
que deveria ter sido sempre, em primeiro lugar,

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

455
00:34:35,710 --> 00:34:38,960
Então iterativo ou recursivo, nós vamos passar por cima de ambos,

456
00:34:38,960 --> 00:34:46,139
mas vamos ver que termina recursivas por ser bastante fácil.

457
00:34:59,140 --> 00:35:02,480
Okay. Alguém tem algo que podemos trabalhar?

458
00:35:02,480 --> 00:35:12,000
>> [Estudante] Eu tenho uma solução iterativa. >> Tudo bem, iterativo.

459
00:35:12,000 --> 00:35:16,030
Ok, isso parece bom.

460
00:35:16,030 --> 00:35:18,920
Então, quero andar nos com ele?

461
00:35:18,920 --> 00:35:25,780
[Estudante] Claro. Então eu definir uma variável temp para obter o primeiro nó da árvore.

462
00:35:25,780 --> 00:35:28,330
E então eu só em loop enquanto temp não nula igual,

463
00:35:28,330 --> 00:35:31,700
por isso, enquanto ainda estava na árvore, eu acho.

464
00:35:31,700 --> 00:35:35,710
E se o valor for igual ao valor de temperatura que está a apontar para,

465
00:35:35,710 --> 00:35:37,640
em seguida, ele retorna esse valor.

466
00:35:37,640 --> 00:35:40,210
Caso contrário, ele verifica se ele está do lado direito ou do lado esquerdo.

467
00:35:40,210 --> 00:35:43,400
Se você já teve uma situação em que não há mais árvores,

468
00:35:43,400 --> 00:35:47,330
em seguida, ele retorna - ele sai do loop e retorna falso.

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

470
00:35:52,190 --> 00:35:58,470
Alguém tem algum comentário sobre qualquer coisa?

471
00:35:58,470 --> 00:36:02,400
Eu não tenho comentários correção em tudo.

472
00:36:02,400 --> 00:36:11,020
A única coisa que podemos fazer é esse cara.

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

474
00:36:21,660 --> 00:36:33,460
Eu vou corrigir isso. Okay.

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

476
00:36:37,150 --> 00:36:38,610
Há, certamente testes no passado

477
00:36:38,610 --> 00:36:41,170
que dar-lhe uma função com um operador ternário,

478
00:36:41,170 --> 00:36:45,750
e dizer, traduzir isso, fazer alguma coisa que não usa ternário.

479
00:36:45,750 --> 00:36:49,140
Portanto, este é um caso muito comum de quando eu iria pensar em usar ternário,

480
00:36:49,140 --> 00:36:54,610
onde se alguma condição definir uma variável para alguma coisa,

481
00:36:54,610 --> 00:36:58,580
mais definido que a mesma variável para outra coisa.

482
00:36:58,580 --> 00:37:03,390
Isso é algo que muito freqüentemente pode ser transformado em esse tipo de coisa

483
00:37:03,390 --> 00:37:14,420
onde definir essa variável para isso - ou, bem, isso é verdade? Então este, senão isso.

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

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

486
00:37:25,570 --> 00:37:30,680
então isto, mais isto. É uma pergunta.

487
00:37:30,680 --> 00:37:35,200
É maior? Em seguida, faça a primeira coisa. Mais fazer o segundo.

488
00:37:35,200 --> 00:37:41,670
Eu quase sempre - o cólon, eu só - na minha cabeça, eu leio como pessoa.

489
00:37:41,670 --> 00:37:47,180
>> Alguém tem uma solução recursiva?

490
00:37:47,180 --> 00:37:49,670
Okay. Este vamos - que poderia já ser grande,

491
00:37:49,670 --> 00:37:53,990
mas estamos indo para torná-lo ainda melhor.

492
00:37:53,990 --> 00:37:58,720
Esta é praticamente a mesma idéia exata.

493
00:37:58,720 --> 00:38:03,060
É só que, bem, você quer explicar?

494
00:38:03,060 --> 00:38:08,340
[Estudante] Claro. Então, estamos certificando-se de que a árvore não é nulo em primeiro lugar,

495
00:38:08,340 --> 00:38:13,380
porque se a árvore é nula, então ele vai retornar falso, porque não tê-lo encontrado.

496
00:38:13,380 --> 00:38:19,200
E se ainda há uma árvore, vamos para - nós primeiro verificar se o valor é o nó atual.

497
00:38:19,200 --> 00:38:23,740
Return true se for, e se não recurse nós à esquerda ou à direita.

498
00:38:23,740 --> 00:38:25,970
Diz que o som apropriado? >> Mm-hmm. (Acordo)

499
00:38:25,970 --> 00:38:33,880
Assim, notar que esta é quase - estruturalmente muito semelhante à solução iterativa.

500
00:38:33,880 --> 00:38:38,200
É só que, em vez de recursão, tivemos um loop while.

501
00:38:38,200 --> 00:38:40,840
E o caso base aqui onde árvore não faz nula igual

502
00:38:40,840 --> 00:38:44,850
foi a condição sob a qual saiu do loop while.

503
00:38:44,850 --> 00:38:50,200
Eles são muito semelhantes. Mas vamos dar um passo adiante.

504
00:38:50,200 --> 00:38:54,190
Agora, nós fazemos a mesma coisa aqui.

505
00:38:54,190 --> 00:38:57,680
Note que estamos retornando a mesma coisa em ambas as linhas,

506
00:38:57,680 --> 00:39:00,220
com exceção de um argumento é diferente.

507
00:39:00,220 --> 00:39:07,950
Então, nós vamos fazer isso em um ternário.

508
00:39:07,950 --> 00:39:13,790
Eu bati algo opção, e fez um símbolo. Okay.

509
00:39:13,790 --> 00:39:21,720
Então vamos voltar contém isso.

510
00:39:21,720 --> 00:39:28,030
Isso está começando a ser várias linhas, bem, o zoom é.

511
00:39:28,030 --> 00:39:31,060
Geralmente, como uma coisa de estilo, eu não acho que muitas pessoas

512
00:39:31,060 --> 00:39:38,640
colocar um espaço após a seta, mas eu acho que se você for consistente, está tudo bem.

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

514
00:39:44,320 --> 00:39:53,890
outra coisa que queremos recurse em direito árvore.

515
00:39:53,890 --> 00:39:58,610
Então isso foi um passo de fazer este olhar menor.

516
00:39:58,610 --> 00:40:02,660
Passo dois de fazer este olhar menor -

517
00:40:02,660 --> 00:40:09,150
podemos separar isso para várias linhas.

518
00:40:09,150 --> 00:40:16,500
Okay. Passo dois de fazê-lo parecer menor está aqui,

519
00:40:16,500 --> 00:40:25,860
então o valor de retorno é igual ao valor de árvore, ou o que quer que contém.

520
00:40:25,860 --> 00:40:28,340
>> Isso é uma coisa importante.

521
00:40:28,340 --> 00:40:30,860
Eu não tenho certeza se ele disse isso explicitamente em sala de aula,

522
00:40:30,860 --> 00:40:34,740
mas é chamado de curto-circuito avaliação.

523
00:40:34,740 --> 00:40:41,060
A idéia aqui é valor == valor árvore.

524
00:40:41,060 --> 00:40:49,960
Se isso é verdade, então isso é verdade, e nós queremos "ou" aquilo com o que está aqui.

525
00:40:49,960 --> 00:40:52,520
Assim, sem sequer pensar sobre o que está aqui,

526
00:40:52,520 --> 00:40:55,070
o que é a expressão inteira vai voltar?

527
00:40:55,070 --> 00:40:59,430
[Estudante] True? >> Sim, porque verdadeiro de qualquer coisa,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd ou verdadeiro com qualquer coisa é necessariamente verdade.

529
00:41:04,990 --> 00:41:08,150
Assim, logo que vemos valor de retorno = valor árvore,

530
00:41:08,150 --> 00:41:10,140
nós apenas estamos indo para retornar verdadeiro.

531
00:41:10,140 --> 00:41:15,710
Nem mesmo vai recurse contém ainda abaixo da linha.

532
00:41:15,710 --> 00:41:20,980
Podemos dar um passo adiante.

533
00:41:20,980 --> 00:41:29,490
Árvore de retorno não nulo igual e tudo isso.

534
00:41:29,490 --> 00:41:32,650
Ele fez uma função de uma linha.

535
00:41:32,650 --> 00:41:36,790
Este é também um exemplo de avaliação curto-circuito.

536
00:41:36,790 --> 00:41:40,680
Mas agora é a mesma idéia -

537
00:41:40,680 --> 00:41:47,320
em vez de - por isso, se não nulo árvore faz igual - ou, bem,

538
00:41:47,320 --> 00:41:49,580
se faz árvore nula igual, o que é o caso de má,

539
00:41:49,580 --> 00:41:54,790
se a árvore é igual a nulo, então a primeira condição vai ser falso.

540
00:41:54,790 --> 00:42:00,550
Tão falso anded com qualquer coisa vai ser o que?

541
00:42:00,550 --> 00:42:04,640
[Estudante] False. Sim >>. Esta é a outra metade do curto-circuito de avaliação,

542
00:42:04,640 --> 00:42:10,710
onde se a árvore não nulo não igual, então não estamos indo mesmo ir -

543
00:42:10,710 --> 00:42:14,930
ou se faz árvore nula igual, então não vamos fazer valor == valor árvore.

544
00:42:14,930 --> 00:42:17,010
Nós apenas estamos indo para retornar imediatamente falso.

545
00:42:17,010 --> 00:42:20,970
O que é importante, pois, se não o fez curto-circuito avaliar,

546
00:42:20,970 --> 00:42:25,860
em seguida, se árvore faz nulo igual, esta segunda condição vai culpa seg,

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

548
00:42:32,510 --> 00:42:40,490
Então é isso. Pode fazer isso - mudar uma vez mais.

549
00:42:40,490 --> 00:42:44,840
Isso é uma coisa muito comum também, não fazer esta linha um com isso,

550
00:42:44,840 --> 00:42:49,000
mas é uma coisa comum em condições, talvez não aqui,

551
00:42:49,000 --> 00:42:59,380
mas se (árvore! = NULL, e árvore-> valor valor ==), fazer o que.

552
00:42:59,380 --> 00:43:01,560
Esta é uma condição muito comum, em que em vez de ter

553
00:43:01,560 --> 00:43:06,770
para quebrar isso em dois ifs, onde, como, é o nulo árvore?

554
00:43:06,770 --> 00:43:11,780
Ok, não é nula, então agora é o valor igual ao valor de árvore? Fazer isso.

555
00:43:11,780 --> 00:43:17,300
Em vez disso, essa condição, isso nunca vai seg culpa

556
00:43:17,300 --> 00:43:21,220
porque ele vai sair se isso acontecer a ser nulo.

557
00:43:21,220 --> 00:43:24,000
Bem, eu acho que se a árvore é um ponteiro completamente inválido, ele ainda pode seg culpa,

558
00:43:24,000 --> 00:43:26,620
mas não pode seg culpa se a árvore é nula.

559
00:43:26,620 --> 00:43:32,900
Se fosse nulo, ele iria sair antes de você dereferenced o ponteiro em primeiro lugar.

560
00:43:32,900 --> 00:43:35,000
[Estudante] É esta avaliação chamado preguiçoso?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Avaliação preguiçoso é uma coisa separada.

562
00:43:40,770 --> 00:43:49,880
Avaliação preguiçosa é mais como você perguntar para um valor,

563
00:43:49,880 --> 00:43:54,270
você perguntar para calcular um valor, tipo, mas você não precisa dele imediatamente.

564
00:43:54,270 --> 00:43:59,040
Então, até que você realmente precisa dele, ele não é avaliada.

565
00:43:59,040 --> 00:44:03,920
Esta não é exatamente a mesma coisa, mas no pset Huffman,

566
00:44:03,920 --> 00:44:06,520
ele diz que "preguiçosamente", escrevem.

567
00:44:06,520 --> 00:44:08,670
A razão para fazermos isso é porque na verdade estamos buffer a escrita -

568
00:44:08,670 --> 00:44:11,820
não quero escrever bits individuais de cada vez,

569
00:44:11,820 --> 00:44:15,450
ou bytes individuais de uma vez, que em vez querem ter um pedaço de bytes.

570
00:44:15,450 --> 00:44:19,270
Em seguida, uma vez que temos um pedaço de bytes, então vamos escrever isso.

571
00:44:19,270 --> 00:44:22,640
Mesmo que você pedir para ele escrever - e fwrite e fread fazer o mesmo tipo de coisa.

572
00:44:22,640 --> 00:44:26,260
Elas suavizam o lê e escreve.

573
00:44:26,260 --> 00:44:31,610
Mesmo que você pedir para ele escrever de imediato, provavelmente não.

574
00:44:31,610 --> 00:44:34,540
E você não pode ter certeza de que as coisas vão ser escrito

575
00:44:34,540 --> 00:44:37,540
até que você chamar hfclose ou o que seja,

576
00:44:37,540 --> 00:44:39,620
que, então, diz, está bem, eu estou fechando meu arquivo,

577
00:44:39,620 --> 00:44:43,450
isso significa que é melhor eu escrever tudo o que eu ainda não escreveu.

578
00:44:43,450 --> 00:44:45,770
Ele não tem necessidade de escrever tudo fora

579
00:44:45,770 --> 00:44:49,010
até que você está fechando o arquivo, e então ele precisa.

580
00:44:49,010 --> 00:44:56,220
Então, isso é apenas o que preguiçoso - ele espera até que isso tem que acontecer.

581
00:44:56,220 --> 00:44:59,990
Este - ter 51 e você vai entrar em mais detalhes,

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

583
00:45:05,470 --> 00:45:08,890
Não existem soluções iterativo, basicamente.

584
00:45:08,890 --> 00:45:11,550
Tudo é recursividade, e avaliação preguiçosa

585
00:45:11,550 --> 00:45:14,790
vai ser importante para uma série de circunstâncias

586
00:45:14,790 --> 00:45:19,920
onde, se você não avaliar preguiçosamente, isso significaria -

587
00:45:19,920 --> 00:45:24,760
O exemplo é correntes, que são infinitamente longo.

588
00:45:24,760 --> 00:45:30,990
Em teoria, você pode pensar que os números naturais como um fluxo de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Coisas tão preguiçosamente avaliados estão bem.

590
00:45:33,090 --> 00:45:37,210
Se eu disser que quero o número dez, então eu posso avaliar, até o número dez.

591
00:45:37,210 --> 00:45:40,300
Se eu quiser que o número centésimo, então eu posso avaliar, até o número centésimo.

592
00:45:40,300 --> 00:45:46,290
Sem avaliação preguiçosa, então ele vai tentar avaliar todos os números imediatamente.

593
00:45:46,290 --> 00:45:50,000
Você está avaliando números infinitos, e isso não é apenas possível.

594
00:45:50,000 --> 00:45:52,080
Então, há uma série de circunstâncias em que a avaliação preguiçoso

595
00:45:52,080 --> 00:45:57,840
é apenas essencial para a obtenção de coisas para trabalhar.

596
00:45:57,840 --> 00:46:05,260
>> Agora queremos escrever inserção onde inserção vai ser

597
00:46:05,260 --> 00:46:08,430
similarmente mudança na sua definição.

598
00:46:08,430 --> 00:46:10,470
Então agora é inserir bool (valor inteiro).

599
00:46:10,470 --> 00:46:23,850
Vamos mudar isso para inserção bool (int valor, nó da árvore *).

600
00:46:23,850 --> 00:46:29,120
Estamos, na verdade, vai mudar de novo daqui a pouco, vamos ver por que.

601
00:46:29,120 --> 00:46:32,210
E vamos passar build_node, apenas para os pedaços dele,

602
00:46:32,210 --> 00:46:36,730
acima de inserir de modo que não tem que escrever um protótipo de função.

603
00:46:36,730 --> 00:46:42,450
Que é um indício de que você está indo estar usando build_node na inserção.

604
00:46:42,450 --> 00:46:49,590
Okay. Tome um minuto para isso.

605
00:46:49,590 --> 00:46:52,130
Eu acho que eu salvo a revisão se você quiser puxar de que,

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

607
00:47:00,240 --> 00:47:04,190
Eu queria uma ligeira quebra para pensar sobre a lógica de inserção,

608
00:47:04,190 --> 00:47:08,750
se você não pode pensar nisso.

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

610
00:47:12,860 --> 00:47:18,640
Como, se eu inserir um, então eu estou, inevitavelmente, vai ser uma inserção -

611
00:47:18,640 --> 00:47:21,820
Eu vou mudar para o preto - eu ser a inserção de um por aqui.

612
00:47:21,820 --> 00:47:28,070
Ou se eu inserir 4, eu quero ser a inserção de quatro aqui.

613
00:47:28,070 --> 00:47:32,180
Portanto, não importa o que você faça, você vai ser a inserção de uma folha.

614
00:47:32,180 --> 00:47:36,130
Tudo que você tem a fazer é repetir a árvore até chegar ao nó

615
00:47:36,130 --> 00:47:40,890
que deve ser pai do nó, o pai do novo nó,

616
00:47:40,890 --> 00:47:44,560
e depois alterar o ponteiro para a esquerda ou direita, dependendo do facto

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

618
00:47:47,060 --> 00:47:51,180
Alterar esse ponteiro para apontar para o novo nó.

619
00:47:51,180 --> 00:48:05,490
Então iterar a árvore, fazer o ponto da folha para o novo nó.

620
00:48:05,490 --> 00:48:09,810
Também pensar sobre o motivo que proíbe o tipo de situação antes,

621
00:48:09,810 --> 00:48:17,990
onde construiu a árvore binária onde estava correto

622
00:48:17,990 --> 00:48:19,920
se você só olhou para um único nó,

623
00:48:19,920 --> 00:48:24,830
mas 9 foi para a esquerda, de 7, se você iterado para baixo todo o caminho.

624
00:48:24,830 --> 00:48:29,770
Então, isso é impossível, neste cenário, uma vez que -

625
00:48:29,770 --> 00:48:32,530
pensa sobre a inserção 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 para ir para a direita.

627
00:48:35,350 --> 00:48:38,490
Portanto, não importa o que eu faço, se eu estou indo para a inserção de uma folha,

628
00:48:38,490 --> 00:48:40,790
e para uma folha utilizando o algoritmo adequado,

629
00:48:40,790 --> 00:48:43,130
que vai ser impossível para mim para inserir 9 para a esquerda, de 7 de

630
00:48:43,130 --> 00:48:48,250
porque assim que eu bater 7 Eu estou indo para ir para a direita.

631
00:48:59,740 --> 00:49:02,070
Alguém tem alguma coisa para começar?

632
00:49:02,070 --> 00:49:05,480
[Estudante] eu faço. >> Claro.

633
00:49:05,480 --> 00:49:09,200
[Estudante, ininteligível]

634
00:49:09,200 --> 00:49:14,390
[Outro aluno, ininteligível]

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

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

637
00:49:20,690 --> 00:49:24,060
novos nós na extremidade da árvore,

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

639
00:49:28,070 --> 00:49:31,360
até que cheguei a um nó que apontou como nulo.

640
00:49:31,360 --> 00:49:34,220
E então eu decidi colocá-lo tanto no lado direito ou no lado esquerdo

641
00:49:34,220 --> 00:49:37,420
usando essa variável direito, que me disse onde colocá-lo.

642
00:49:37,420 --> 00:49:41,850
E então, essencialmente, eu fiz apenas que a última -

643
00:49:41,850 --> 00:49:47,520
Nesse ponto nó temp para o novo nó que estava criando,

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

645
00:49:50,770 --> 00:49:56,530
Finalmente, defina o valor novo nó com o valor de seus testes.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Ok, então eu vejo um problema aqui.

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

648
00:50:02,050 --> 00:50:07,550
O problema que eu vejo, bem, se alguém ver um problema?

649
00:50:07,550 --> 00:50:18,400
Qual é a circunstância em que eles quebram fora do circuito?

650
00:50:18,400 --> 00:50:22,100
[Estudante] Se temp é nulo? Sim >>. Então, como você sair do loop é se temp é nulo.

651
00:50:22,100 --> 00:50:30,220
Mas o que eu faço aqui?

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

653
00:50:35,410 --> 00:50:39,840
Então, a outra coisa que você precisa fazer não é apenas acompanhar até temp é nulo,

654
00:50:39,840 --> 00:50:45,590
você quer acompanhar o pai em todos os momentos.

655
00:50:45,590 --> 00:50:52,190
Queremos também pai * nó, acho que podemos manter isso em nulo no primeiro.

656
00:50:52,190 --> 00:50:55,480
Isso vai ter um comportamento estranho para a raiz da árvore,

657
00:50:55,480 --> 00:50:59,210
mas nós vamos chegar a isso.

658
00:50:59,210 --> 00:51:03,950
Se o valor é maior do que qualquer outra coisa, então temperatura certa temp =.

659
00:51:03,950 --> 00:51:07,910
Mas antes de fazer esse pai, temp =.

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

661
00:51:14,500 --> 00:51:19,560
Se temp não é nulo, então eu vou mover para baixo, não importa o que,

662
00:51:19,560 --> 00:51:24,030
a um nó para o qual temp é o pai.

663
00:51:24,030 --> 00:51:27,500
Então pai vai ser temporário, e depois eu passo temporário para baixo.

664
00:51:27,500 --> 00:51:32,410
Agora temporário é nulo, mas pontos pai para o pai da coisa que é nulo.

665
00:51:32,410 --> 00:51:39,110
Então, aqui, eu não quero para definir direito igual a 1.

666
00:51:39,110 --> 00:51:41,300
Então eu me mudei para a direita, por isso, se a direita = 1,

667
00:51:41,300 --> 00:51:45,130
e eu acho que você também quer fazer -

668
00:51:45,130 --> 00:51:48,530
se você se mover para a esquerda, que pretende definir direito igual a 0.

669
00:51:48,530 --> 00:51:55,950
Ou então, se você nunca se mover para a direita.

670
00:51:55,950 --> 00:51:58,590
Então direita = 0. Se o direito = 1,

671
00:51:58,590 --> 00:52:04,260
agora queremos fazer o pai newNode ponteiro direito,

672
00:52:04,260 --> 00:52:08,520
outra coisa que quero fazer o pai newNode ponteiro esquerdo.

673
00:52:08,520 --> 00:52:16,850
Perguntas sobre isso?

674
00:52:16,850 --> 00:52:24,880
Okay. Portanto, esta é a maneira que nós - bem, na verdade, em vez de fazer isso,

675
00:52:24,880 --> 00:52:29,630
Nós meio que esperava que você use build_node.

676
00:52:29,630 --> 00:52:40,450
E então se newNode igual nulo, retorna false.

677
00:52:40,450 --> 00:52:44,170
É isso. Agora, isso é o que espera que você faça.

678
00:52:44,170 --> 00:52:47,690
>> Isto é o que as soluções pessoal fazer.

679
00:52:47,690 --> 00:52:52,360
Não concordo com isso como o jeito "certo" de fazer isso

680
00:52:52,360 --> 00:52:57,820
mas isso é perfeitamente bem e ele vai funcionar.

681
00:52:57,820 --> 00:53:02,840
Uma coisa que está um pouco estranho agora é

682
00:53:02,840 --> 00:53:08,310
se a árvore começa como nula, passamos em uma árvore nula.

683
00:53:08,310 --> 00:53:12,650
Acho que depende de como você define o comportamento de passar em uma árvore nula.

684
00:53:12,650 --> 00:53:15,490
Eu acho que se você passar em uma árvore nula,

685
00:53:15,490 --> 00:53:17,520
em seguida, inserir o valor para uma árvore nula

686
00:53:17,520 --> 00:53:23,030
deve retornar apenas uma árvore, onde o único valor que é único nó.

687
00:53:23,030 --> 00:53:25,830
As pessoas concordam com isso? Você poderia, se quisesse,

688
00:53:25,830 --> 00:53:28,050
se você passar em uma árvore nula

689
00:53:28,050 --> 00:53:31,320
e você quer inserir um valor para ele, retornar falso.

690
00:53:31,320 --> 00:53:33,830
É até você para definir isso.

691
00:53:33,830 --> 00:53:38,320
Para fazer a primeira coisa que eu disse e depois -

692
00:53:38,320 --> 00:53:40,720
bem, você vai ter problemas para fazer isso, porque

693
00:53:40,720 --> 00:53:44,090
seria mais fácil se tivéssemos um ponteiro global para a coisa,

694
00:53:44,090 --> 00:53:48,570
mas nós não, então se a árvore é nulo, não há nada que possamos fazer sobre isso.

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

696
00:53:50,960 --> 00:53:52,840
Então, eu vou mudar de inserção.

697
00:53:52,840 --> 00:53:56,540
Nós tecnicamente poderia mudar isso aqui,

698
00:53:56,540 --> 00:53:58,400
como ele está interagindo sobre as coisas,

699
00:53:58,400 --> 00:54:04,530
mas eu vou mudar de inserção para tomar um nó de árvore. **

700
00:54:04,530 --> 00:54:07,510
Ponteiros duplos.

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

702
00:54:09,710 --> 00:54:12,330
Em vez de lidar com ponteiros para nós,

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

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

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

706
00:54:21,770 --> 00:54:25,760
Isso faz sentido, uma vez que, pensar para baixo -

707
00:54:25,760 --> 00:54:33,340
bem, agora isso aponta para nulo.

708
00:54:33,340 --> 00:54:38,130
O que eu quero fazer é manipular este ponteiro para apontar para não nulo.

709
00:54:38,130 --> 00:54:40,970
Eu quero que ele aponte para o meu novo nó.

710
00:54:40,970 --> 00:54:44,870
Se eu apenas manter o controle de ponteiros para os meus ponteiros,

711
00:54:44,870 --> 00:54:47,840
então não precisa manter o controle de um ponteiro pai.

712
00:54:47,840 --> 00:54:52,640
Eu posso apenas acompanhar para ver se o ponteiro está apontando para nulo,

713
00:54:52,640 --> 00:54:54,580
e se o ponteiro está apontando para nulo,

714
00:54:54,580 --> 00:54:57,370
mudá-lo para apontar para o nó que eu quero.

715
00:54:57,370 --> 00:55:00,070
E eu posso mudá-lo desde que eu tenho um ponteiro para o ponteiro.

716
00:55:00,070 --> 00:55:02,040
Vamos ver isso agora.

717
00:55:02,040 --> 00:55:05,470
Você pode realmente fazê-lo recursivamente muito facilmente.

718
00:55:05,470 --> 00:55:08,080
Não queremos fazer isso?

719
00:55:08,080 --> 00:55:10,980
Sim, nós fazemos.

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

721
00:55:16,790 --> 00:55:24,070
Primeiro, o que é o nosso caso base vai ser?

722
00:55:24,070 --> 00:55:29,140
Quase sempre o nosso caso base, mas, na verdade, isso é meio complicado.

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

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

725
00:55:37,550 --> 00:55:40,460
Isto é diferente de seu nulo árvore estar.

726
00:55:40,460 --> 00:55:44,510
Este é o ponteiro para o ponteiro raiz sendo nula

727
00:55:44,510 --> 00:55:48,360
o que significa que o ponteiro raiz não existe.

728
00:55:48,360 --> 00:55:52,390
Então, aqui, se eu fizer

729
00:55:52,390 --> 00:55:55,760
* nó - vamos reutilizar esse.

730
00:55:55,760 --> 00:55:58,960
* Nó raiz = NULL,

731
00:55:58,960 --> 00:56:00,730
e então eu vou chamar de inserção, fazendo algo parecido,

732
00:56:00,730 --> 00:56:04,540
inserir em 4 e raiz.

733
00:56:04,540 --> 00:56:06,560
Assim, e de raiz, se a raiz é um nó *

734
00:56:06,560 --> 00:56:11,170
depois & raiz vai ser um ** nó.

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

736
00:56:15,120 --> 00:56:20,120
árvore não é nula - ou inserção.

737
00:56:20,120 --> 00:56:24,630
Aqui. Árvore não é nulo; árvore * é nulo, o que é bom

738
00:56:24,630 --> 00:56:26,680
porque se a árvore * é nulo, então eu posso manipulá-lo

739
00:56:26,680 --> 00:56:29,210
até agora apontam para o que eu quero que ele apontar.

740
00:56:29,210 --> 00:56:34,750
Mas se a árvore for nula, isso significa que eu só vim aqui e disse nulo.

741
00:56:34,750 --> 00:56:42,710
Isso não faz sentido. Eu não posso fazer nada com isso.

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

743
00:56:45,540 --> 00:56:48,220
Então eu basicamente já disse o que o nosso caso base real.

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

745
00:56:50,580 --> 00:56:55,030
[Estudante, ininteligível]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Sim. Então, se (* árvore == NULL).

747
00:57:00,000 --> 00:57:04,520
Isso se relaciona com o caso aqui

748
00:57:04,520 --> 00:57:09,640
onde se meu ponteiro vermelho é o ponteiro Estou focado,

749
00:57:09,640 --> 00:57:12,960
assim como eu estou focado neste ponteiro, agora eu estou focado neste ponteiro.

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

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

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

753
00:57:22,880 --> 00:57:28,470
isso significa que eu estou no caso em que eu estou focando um ponteiro que aponta -

754
00:57:28,470 --> 00:57:32,530
este é um ponteiro que pertence a uma folha.

755
00:57:32,530 --> 00:57:41,090
Eu quero mudar este ponteiro para apontar para o meu novo nó.

756
00:57:41,090 --> 00:57:45,230
Volte aqui.

757
00:57:45,230 --> 00:57:56,490
Meu newNode será apenas nó * n = build_node (valor)

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

759
00:58:07,300 --> 00:58:12,600
Outra coisa que quero mudar o que o ponteiro está apontando para

760
00:58:12,600 --> 00:58:17,830
agora a apontar para o nosso nó recém-construído.

761
00:58:17,830 --> 00:58:20,280
Nós podemos realmente fazer isso aqui.

762
00:58:20,280 --> 00:58:30,660
Em vez de dizer n, dizemos * = árvore se a árvore *.

763
00:58:30,660 --> 00:58:35,450
Todo mundo entende isso? Que, por lidar com ponteiros para ponteiros,

764
00:58:35,450 --> 00:58:40,750
nós podemos mudar ponteiros nulos para apontar para coisas que queremos que eles apontam.

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

766
00:58:42,820 --> 00:58:45,740
>> Agora recorrência nosso, ou o nosso recursão,

767
00:58:45,740 --> 00:58:51,430
vai ser muito semelhante a todos os outros recursões temos vindo a fazer.

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

769
00:58:55,830 --> 00:58:59,040
e agora eu vou usar ternário de novo, mas o que é a nossa condição vai ser?

770
00:58:59,040 --> 00:59:05,180
O que é que estamos à procura de decidir se queremos ir para a esquerda ou direita?

771
00:59:05,180 --> 00:59:07,760
Vamos fazê-lo em etapas separadas.

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

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

774
00:59:23,200 --> 00:59:27,490
[Bowden] Então lembre-se que eu estou atualmente -

775
00:59:27,490 --> 00:59:31,260
[Estudantes, ininteligível]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Sim, isso aqui, vamos dizer que esta seta verde

777
00:59:34,140 --> 00:59:39,050
é um exemplo de que árvore é atualmente, é um ponteiro para este ponteiro.

778
00:59:39,050 --> 00:59:46,610
Então isso significa que eu sou um ponteiro para um ponteiro para 3.

779
00:59:46,610 --> 00:59:48,800
O dereference duas vezes soava bem.

780
00:59:48,800 --> 00:59:51,010
O que eu - como eu faço isso?

781
00:59:51,010 --> 00:59:53,210
[Estudante] Referência no uma vez, e em seguida, fazer seta que maneira?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Então (árvore *) é o dereference uma vez, - valor>

783
00:59:58,420 --> 01:00:05,960
vai dar-me o valor do nó que eu estou indiretamente apontando.

784
01:00:05,960 --> 01:00:11,980
Então, eu também posso escrever ** tree.value se você preferir.

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

786
01:00:18,490 --> 01:00:26,190
Se for esse o caso, então eu quero chamar inserir com valor.

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

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

789
01:00:39,440 --> 01:00:41,900
E eu quero que o ponteiro para essa coisa

790
01:00:41,900 --> 01:00:44,930
de modo que se a esquerda acaba sendo o ponteiro nulo,

791
01:00:44,930 --> 01:00:48,360
Eu posso modificá-lo para apontar para o meu novo nó.

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

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

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

795
01:01:04,480 --> 01:01:11,040
Então nós queremos atualizar nossos ** para a esquerda,

796
01:01:11,040 --> 01:01:17,030
mais queremos atualizar nossos ** para a direita.

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

798
01:01:22,540 --> 01:01:30,940
[Bowden] Lembre-se que - ** tree.right é uma estrela nó.

799
01:01:30,940 --> 01:01:35,040
[Estudante, ininteligível] >> Yeah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right é assim ponteiro ou algo assim.

801
01:01:41,140 --> 01:01:45,140
Assim, tomando um ponteiro para isso, que me dá o que eu quero

802
01:01:45,140 --> 01:01:50,090
do ponteiro para esse cara.

803
01:01:50,090 --> 01:01:54,260
[Estudante] Podemos ir mais uma vez por que estamos usando os dois ponteiros?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Então - não, você pode, e que a solução antes

805
01:01:58,220 --> 01:02:04,540
Era uma maneira de fazê-lo sem fazer dois ponteiros.

806
01:02:04,540 --> 01:02:08,740
Você precisa ser capaz de entender usando dois ponteiros,

807
01:02:08,740 --> 01:02:11,660
e esta é uma solução de limpeza.

808
01:02:11,660 --> 01:02:16,090
Além disso, observe que, o que acontece se a minha árvore -

809
01:02:16,090 --> 01:02:24,480
o que acontece se minha raiz era nulo? O que acontece se eu fazer isso caso aqui?

810
01:02:24,480 --> 01:02:30,540
Então nó raiz * = NULL, insira 4 em e raiz.

811
01:02:30,540 --> 01:02:35,110
O que é raiz vai ser depois disto?

812
01:02:35,110 --> 01:02:37,470
[Estudante, ininteligível] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Valor da raiz vai ser 4.

814
01:02:41,710 --> 01:02:45,510
Esquerdo de raiz vai ser nulo, certo raiz vai ser nulo.

815
01:02:45,510 --> 01:02:49,490
No caso em que não passe de raiz por endereço,

816
01:02:49,490 --> 01:02:52,490
não foi possível modificar raiz.

817
01:02:52,490 --> 01:02:56,020
No caso em que a árvore - onde raiz era nulo,

818
01:02:56,020 --> 01:02:58,410
nós apenas tivemos que retornar falso. Não há nada que possamos fazer.

819
01:02:58,410 --> 01:03:01,520
Nós não podemos inserir um nó em uma árvore vazia.

820
01:03:01,520 --> 01:03:06,810
Mas agora nós podemos, nós apenas fazer uma árvore vazia em uma árvore de um nó.

821
01:03:06,810 --> 01:03:13,400
Que normalmente é a maneira esperada que é suposto para trabalhar.

822
01:03:13,400 --> 01:03:21,610
>> Além disso, esta é significativamente mais curto do que

823
01:03:21,610 --> 01:03:26,240
também manter o controle do pai, e assim você percorrer todo o caminho para baixo.

824
01:03:26,240 --> 01:03:30,140
Agora eu tenho o meu pai, e eu só tenho o meu ponteiro direito pai para o que seja.

825
01:03:30,140 --> 01:03:35,640
Em vez disso, se fizermos isso de forma iterativa, que seria a mesma idéia com um loop while.

826
01:03:35,640 --> 01:03:38,100
Mas, em vez de ter que lidar com o meu ponteiro pai,

827
01:03:38,100 --> 01:03:40,600
em vez meu ponteiro atual seria a coisa

828
01:03:40,600 --> 01:03:43,790
que eu estou modificando diretamente para apontar para o meu novo nó.

829
01:03:43,790 --> 01:03:46,090
Eu não tenho que lidar com o fato de que ele está apontando para a esquerda.

830
01:03:46,090 --> 01:03:48,810
Eu não tenho que lidar com o fato de que ele está apontando para a direita.

831
01:03:48,810 --> 01:04:00,860
É só o que esse ponteiro é, eu estou indo para configurá-lo para apontar para o meu novo nó.

832
01:04:00,860 --> 01:04:05,740
Todo mundo entende como funciona?

833
01:04:05,740 --> 01:04:09,460
Se não, por que queremos fazê-lo desta forma,

834
01:04:09,460 --> 01:04:14,920
mas que, pelo menos, esta funciona como uma solução?

835
01:04:14,920 --> 01:04:17,110
[Estudante] Onde é que vamos voltar verdade?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Isso é provavelmente aqui.

837
01:04:21,550 --> 01:04:26,690
Se corretamente inseri-lo, retornar true.

838
01:04:26,690 --> 01:04:32,010
Outra coisa, aqui nós vamos querer voltar retornos independentemente de inserção.

839
01:04:32,010 --> 01:04:35,950
>> E o que há de especial sobre esta função recursiva?

840
01:04:35,950 --> 01:04:43,010
É cauda recursiva, por isso, enquanto nós compilar com alguma otimização,

841
01:04:43,010 --> 01:04:48,060
ele vai reconhecer isso e você nunca vai ter um estouro de pilha a partir deste,

842
01:04:48,060 --> 01:04:53,230
mesmo se a nossa árvore tem uma altura de 10 mil ou 10 milhões.

843
01:04:53,230 --> 01:04:55,630
[Estudante, ininteligível]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Eu acho que ele faz isso em Dash - ou o que nível de otimização

845
01:05:00,310 --> 01:05:03,820
é necessário para uma recursão de cauda para ser reconhecida.

846
01:05:03,820 --> 01:05:09,350
Eu acho que ele reconhece - GCC e Clang

847
01:05:09,350 --> 01:05:12,610
também têm significados diferentes para os seus níveis de otimização.

848
01:05:12,610 --> 01:05:17,870
Eu quero dizer que é DashO 2, a certeza de que ele vai reconhecer recursão de cauda.

849
01:05:17,870 --> 01:05:27,880
Mas nós - você pode construir como um exemplo Fibonocci ou algo assim.

850
01:05:27,880 --> 01:05:30,030
Não é fácil fazer o teste com isso, porque é difícil construir

851
01:05:30,030 --> 01:05:32,600
uma árvore binária que é tão grande.

852
01:05:32,600 --> 01:05:37,140
Mas sim, eu acho que é DashO 2, que

853
01:05:37,140 --> 01:05:40,580
se você compilar com DashO 2, ele irá procurar por recursão

854
01:05:40,580 --> 01:05:54,030
e otimizar isso.

855
01:05:54,030 --> 01:05:58,190
Vamos voltar - inserir, literalmente, a última coisa que ele precisa.

856
01:05:58,190 --> 01:06:04,900
Vamos voltar para a inserção aqui

857
01:06:04,900 --> 01:06:07,840
onde nós estamos indo fazer a mesma idéia.

858
01:06:07,840 --> 01:06:14,340
Ele ainda vai ter a falha de não ser capaz de lidar com todo

859
01:06:14,340 --> 01:06:17,940
quando a raiz em si é nulo, ou a entrada de passado é nulo,

860
01:06:17,940 --> 01:06:20,060
mas, em vez de lidar com um ponteiro pai,

861
01:06:20,060 --> 01:06:27,430
vamos aplicar a mesma lógica dos ponteiros mantendo a ponteiros.

862
01:06:27,430 --> 01:06:35,580
Se aqui nós manter nosso nó **, cur

863
01:06:35,580 --> 01:06:37,860
e não precisa manter o controle de mais certo,

864
01:06:37,860 --> 01:06:47,190
mas nó ** cur = & árvore.

865
01:06:47,190 --> 01:06:54,800
E agora o nosso loop while vai ser enquanto cur * não nula igual.

866
01:06:54,800 --> 01:07:00,270
Não precisa manter o controle de pais mais.

867
01:07:00,270 --> 01:07:04,180
Não precisa manter o controle de esquerda e direita.

868
01:07:04,180 --> 01:07:10,190
E eu vou chamá-lo de temp, porque nós já estamos usando temp.

869
01:07:10,190 --> 01:07:17,200
Okay. Então, se (valor> * temp),

870
01:07:17,200 --> 01:07:24,010
em seguida, & (* temp) - direito>

871
01:07:24,010 --> 01:07:29,250
mais temp = & (* temp) -> esquerda.

872
01:07:29,250 --> 01:07:32,730
E agora, neste momento, após este loop while,

873
01:07:32,730 --> 01:07:36,380
Eu só faço isso porque talvez seja mais fácil pensar iterativamente de forma recursiva,

874
01:07:36,380 --> 01:07:39,010
mas depois deste loop while,

875
01:07:39,010 --> 01:07:43,820
* Temp é o ponteiro que deseja alterar.

876
01:07:43,820 --> 01:07:48,960
>> Antes tínhamos pai, e queríamos mudar qualquer pai ou mãe esquerda para a direita,

877
01:07:48,960 --> 01:07:51,310
mas se queremos mudar direito dos pais,

878
01:07:51,310 --> 01:07:54,550
então temp * é direito dos pais, e nós podemos mudá-lo diretamente.

879
01:07:54,550 --> 01:08:05,860
Então, aqui, nós podemos fazer * temp = newNode, e é isso.

880
01:08:05,860 --> 01:08:09,540
Então aviso, tudo o que fizemos nesta era tirar linhas de código.

881
01:08:09,540 --> 01:08:14,770
A fim de acompanhar o pai em tudo o que é o esforço adicional.

882
01:08:14,770 --> 01:08:18,689
Aqui, se nós apenas acompanhar o ponteiro para o ponteiro,

883
01:08:18,689 --> 01:08:22,990
e mesmo que queria se livrar de todas essas chaves agora,

884
01:08:22,990 --> 01:08:27,170
torná-la mais curta.

885
01:08:27,170 --> 01:08:32,529
Esta agora é a solução exatamente o mesmo,

886
01:08:32,529 --> 01:08:38,210
mas menos linhas de código.

887
01:08:38,210 --> 01:08:41,229
Uma vez que você começar a reconhecer isso como uma solução válida,

888
01:08:41,229 --> 01:08:43,529
também é mais fácil do que raciocinar sobre como, ok,

889
01:08:43,529 --> 01:08:45,779
por que eu tenho esta bandeira à direita int?

890
01:08:45,779 --> 01:08:49,290
O que significa isso? Oh, está significando que

891
01:08:49,290 --> 01:08:51,370
cada vez que eu vá para a direita, eu preciso defini-lo,

892
01:08:51,370 --> 01:08:53,819
outra coisa, se eu for embora, eu preciso configurá-lo para zero.

893
01:08:53,819 --> 01:09:04,060
Aqui, eu não tenho a razão sobre isso, é apenas mais fácil de pensar.

894
01:09:04,060 --> 01:09:06,710
Perguntas?

895
01:09:06,710 --> 01:09:16,290
[Estudante, ininteligível] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Ok, então no último bit -

897
01:09:23,359 --> 01:09:28,080
Eu acho que uma função fácil e rápida que podemos fazer é,

898
01:09:28,080 --> 01:09:34,910
Vamos - juntos, eu acho, e tentar escrever um contém função

899
01:09:34,910 --> 01:09:38,899
que não se importa se é uma árvore de busca binária.

900
01:09:38,899 --> 01:09:43,770
Este contém função deve retornar true

901
01:09:43,770 --> 01:09:58,330
se em qualquer lugar nesta árvore binária geral é o valor que estamos procurando.

902
01:09:58,330 --> 01:10:02,520
Então, vamos primeiro fazer isso recursivamente e depois nós vamos fazê-lo de forma iterativa.

903
01:10:02,520 --> 01:10:07,300
Nós realmente podemos apenas fazê-lo juntos, porque isso vai ser muito 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, ininteligível]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Então, se (árvore == NULL), então o que?

907
01:10:18,230 --> 01:10:22,740
[Estudante] Retornar falso.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, bem, eu não preciso do 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] árvore? Sim >>.

911
01:10:32,450 --> 01:10:36,430
Então, se (árvore-> valor valor. ==

912
01:10:36,430 --> 01:10:39,920
Observe que estamos de volta ao * nó não, nó ** s?

913
01:10:39,920 --> 01:10:42,990
Contém nunca vai precisar usar um ** nó,

914
01:10:42,990 --> 01:10:45,480
uma vez que não está modificando de ponteiros.

915
01:10:45,480 --> 01:10:50,540
Nós apenas estamos atravessando eles.

916
01:10:50,540 --> 01:10:53,830
Se isso acontecer, então nós queremos retornar true.

917
01:10:53,830 --> 01:10:58,270
Outra coisa que quiser percorrer as crianças.

918
01:10:58,270 --> 01:11:02,620
Portanto, não podemos raciocinar sobre se tudo para a esquerda é menos

919
01:11:02,620 --> 01:11:05,390
e tudo para a direita é maior.

920
01:11:05,390 --> 01:11:09,590
Então o que está a nossa condição vai ser aqui - ou, o que é que vamos fazer?

921
01:11:09,590 --> 01:11:11,840
[Estudante, ininteligível] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Retorno contém (valor, árvore-> esquerda)

923
01:11:17,400 --> 01:11:26,860
ou contém (valor, árvore-> direita). E é isso.

924
01:11:26,860 --> 01:11:29,080
E notar que há algum tipo de avaliação de curto-circuito,

925
01:11:29,080 --> 01:11:32,520
onde se acontecer de encontrar o valor na árvore esquerda,

926
01:11:32,520 --> 01:11:36,820
nós nunca precisamos olhar para a árvore certa.

927
01:11:36,820 --> 01:11:40,430
Essa é a função inteira.

928
01:11:40,430 --> 01:11:43,690
Agora vamos fazê-lo de forma iterativa,

929
01:11:43,690 --> 01:11:48,060
que vai ser menos agradável.

930
01:11:48,060 --> 01:11:54,750
Vamos levar o começo habitual do nó atu * = árvore.

931
01:11:54,750 --> 01:12:03,250
Enquanto (act! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rapidamente vai ver um problema.

933
01:12:08,600 --> 01:12:12,250
Se atual - aqui, se alguma vez sair dessa,

934
01:12:12,250 --> 01:12:16,020
então, temos acabar de coisas para olhar, então retorne falso.

935
01:12:16,020 --> 01:12:24,810
If (atual-> valor valor ==), retorna true.

936
01:12:24,810 --> 01:12:32,910
Então, agora, nós estamos em um lugar -

937
01:12:32,910 --> 01:12:36,250
não sabemos se queremos ir para a esquerda ou direita.

938
01:12:36,250 --> 01:12:44,590
Então, arbitrariamente, vamos ir para a esquerda.

939
01:12:44,590 --> 01:12:47,910
Eu, obviamente, executar em um problema onde eu completamente abandonado tudo -

940
01:12:47,910 --> 01:12:50,760
Eu sempre apenas verificar do lado esquerdo de uma árvore.

941
01:12:50,760 --> 01:12:56,050
Eu nunca vou verificar tudo o que é um direito da criança de qualquer coisa.

942
01:12:56,050 --> 01:13:00,910
Como faço para corrigir isso?

943
01:13:00,910 --> 01:13:05,260
[Estudante] Você tem que manter o controle da esquerda e da direita em uma pilha.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Então, vamos torná-lo

945
01:13:13,710 --> 01:13:32,360
struct lista, nó * n, e depois nó ** próximo?

946
01:13:32,360 --> 01:13:40,240
Eu acho que funciona bem.

947
01:13:40,240 --> 01:13:45,940
Queremos ir mais à esquerda, ou vamos - até aqui.

948
01:13:45,940 --> 01:13:54,350
Struct = lista da lista, ele vai começar

949
01:13:54,350 --> 01:13:58,170
fora nesta lista struct.

950
01:13:58,170 --> 01:14:04,040
* Lista = NULL. Assim que vai ser a nossa lista encadeada

951
01:14:04,040 --> 01:14:08,430
de sub-árvores que nós pulamos.

952
01:14:08,430 --> 01:14:13,800
Nós vamos atravessar resta agora,

953
01:14:13,800 --> 01:14:17,870
mas desde que inevitavelmente precisa voltar para a direita,

954
01:14:17,870 --> 01:14:26,140
Nós vamos manter o lado direito dentro da nossa lista struct.

955
01:14:26,140 --> 01:14:32,620
Então nós vamos 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
Eu vou ignorar verificação de erros que, mas você deve verificar para ver se é nulo.

958
01:14:44,920 --> 01:14:50,540
New_list o nó que vai apontar -

959
01:14:50,540 --> 01:14:56,890
oh, é por isso que eu queria aqui. Vai apontar para uma lista struct segundo.

960
01:14:56,890 --> 01:15:02,380
É assim que ligado listas trabalho.

961
01:15:02,380 --> 01:15:04,810
Este é o mesmo como uma lista ligada int

962
01:15:04,810 --> 01:15:06,960
exceto estamos apenas substituindo int com * nó.

963
01:15:06,960 --> 01:15:11,040
É exatamente o mesmo.

964
01:15:11,040 --> 01:15:15,100
Então new_list, o valor do nosso nó new_list,

965
01:15:15,100 --> 01:15:19,120
vai ser atu-> direita.

966
01:15:19,120 --> 01:15:24,280
O valor da nossa new_list-> próxima vai ser a nossa lista original,

967
01:15:24,280 --> 01:15:30,760
e depois vamos atualizar nossa lista para apontar para new_list.

968
01:15:30,760 --> 01:15:33,650
>> Agora precisamos de algum tipo de forma de puxar as coisas,

969
01:15:33,650 --> 01:15:37,020
como temos atravessado toda a subárvore esquerda.

970
01:15:37,020 --> 01:15:40,480
Agora precisamos tirar algo de fora,

971
01:15:40,480 --> 01:15:43,850
como atu é nulo, nós não queremos apenas retornar falso.

972
01:15:43,850 --> 01:15:50,370
Queremos agora puxar fora a nossa nova lista.

973
01:15:50,370 --> 01:15:53,690
Uma maneira conveniente de fazer isso - bem, na verdade, há várias maneiras de fazer isso.

974
01:15:53,690 --> 01:15:56,680
Alguém tem uma sugestão?

975
01:15:56,680 --> 01:15:58,790
Onde eu deveria fazer isso ou como eu deveria fazer isso?

976
01:15:58,790 --> 01:16:08,010
Nós só temos um par de minutos, mas alguma sugestão?

977
01:16:08,010 --> 01:16:14,750
Em vez de - uma forma, ao invés de nossa condição de ser ao mesmo tempo,

978
01:16:14,750 --> 01:16:17,090
o que estamos actualmente a analisar não é nulo,

979
01:16:17,090 --> 01:16:22,340
em vez disso, vamos continuar a ir até a nossa própria lista é nulo.

980
01:16:22,340 --> 01:16:25,680
Então, se a nossa lista acaba sendo nula,

981
01:16:25,680 --> 01:16:30,680
então nós temos mais coisas para procurar, pesquisar.

982
01:16:30,680 --> 01:16:39,860
Mas isso significa que a primeira coisa na nossa lista está indo só para ser o primeiro nó.

983
01:16:39,860 --> 01:16:49,730
A primeira coisa que vai ser - já não precisa ver isso.

984
01:16:49,730 --> 01:16:58,710
Então, lista-> n será nossa árvore.

985
01:16:58,710 --> 01:17:02,860
lista-> próxima vai ser nulo.

986
01:17:02,860 --> 01:17:07,580
E agora, enquanto a lista não nula igual.

987
01:17:07,580 --> 01:17:11,610
Cur vai puxar algo da nossa lista.

988
01:17:11,610 --> 01:17:13,500
Então atu vai igual lista-> n.

989
01:17:13,500 --> 01:17:20,850
E então lista vai igual lista-> n, ou lista-> seguinte.

990
01:17:20,850 --> 01:17:23,480
Assim se o valor é igual ao valor atu.

991
01:17:23,480 --> 01:17:28,790
Agora podemos acrescentar tanto o ponteiro nosso direito e nosso ponteiro esquerdo

992
01:17:28,790 --> 01:17:32,900
contanto que eles não são nulos.

993
01:17:32,900 --> 01:17:36,390
Até aqui, acho que deveria ter feito isso em primeiro lugar.

994
01:17:36,390 --> 01:17:44,080
Se (cur-> certo! = NULL)

995
01:17:44,080 --> 01:17:56,380
depois vamos inserir o nó em nossa lista.

996
01:17:56,380 --> 01:17:59,290
Se (cur-> esquerda), isso é um pouco de trabalho extra, mas está tudo bem.

997
01:17:59,290 --> 01:18:02,690
Se (cur-> esquerda! = NULL),

998
01:18:02,690 --> 01:18:14,310
e vamos inserir a esquerda em nossa lista ligada,

999
01:18:14,310 --> 01:18:19,700
e que deve ser isso.

1000
01:18:19,700 --> 01:18:22,670
Repetimos - enquanto temos algo em nossa lista,

1001
01:18:22,670 --> 01:18:26,640
temos outro nó para olhar.

1002
01:18:26,640 --> 01:18:28,920
Então, olhamos para esse nó,

1003
01:18:28,920 --> 01:18:31,390
nós avançamos nossa lista para a próxima.

1004
01:18:31,390 --> 01:18:34,060
Se esse nó é o valor que estamos procurando, nós podemos retornar true.

1005
01:18:34,060 --> 01:18:37,640
Else inserir ambas as subárvores nossa esquerda e à direita,

1006
01:18:37,640 --> 01:18:40,510
enquanto eles não são nulos, em nossa lista

1007
01:18:40,510 --> 01:18:43,120
de modo que, inevitavelmente, passar por cima deles.

1008
01:18:43,120 --> 01:18:45,160
Então, se eles não foram nulos,

1009
01:18:45,160 --> 01:18:47,950
se a nossa raiz ponteiro apontava para duas coisas,

1010
01:18:47,950 --> 01:18:51,670
em seguida, no primeiro, tirou algo para fora de modo a nossa lista acaba sendo nulo.

1011
01:18:51,670 --> 01:18:56,890
E, então, colocar duas coisas de volta, agora nossa lista é de tamanho 2.

1012
01:18:56,890 --> 01:19:00,030
Então nós vamos fazer um loop de volta e nós apenas estamos indo para puxar,

1013
01:19:00,030 --> 01:19:04,250
vamos dizer, o ponteiro esquerdo do nosso nó raiz.

1014
01:19:04,250 --> 01:19:07,730
E isso só vai continuar acontecendo, nós vamos acabar looping sobre tudo.

1015
01:19:07,730 --> 01:19:11,280
>> Note-se que esta era significativamente mais complicado

1016
01:19:11,280 --> 01:19:14,160
na solução recursiva.

1017
01:19:14,160 --> 01:19:17,260
E eu já disse várias vezes

1018
01:19:17,260 --> 01:19:25,120
que a solução recursiva tem normalmente muito mais em comum com a solução iterativa.

1019
01:19:25,120 --> 01:19:30,820
Aqui é exatamente isso que a solução recursiva é fazendo.

1020
01:19:30,820 --> 01:19:36,740
A única alteração é a de que em vez de implicitamente utilizando a pilha, a pilha de programa,

1021
01:19:36,740 --> 01:19:40,840
como a sua forma de manter o controle do que nós ainda precisa visitar,

1022
01:19:40,840 --> 01:19:45,430
agora você tem que explicitamente usar uma lista ligada.

1023
01:19:45,430 --> 01:19:49,070
Em ambos os casos você está mantendo a par do que ainda precisa de nó a ser visitado.

1024
01:19:49,070 --> 01:19:51,790
No caso recursivo é apenas mais fácil, porque uma pilha

1025
01:19:51,790 --> 01:19:57,100
é implementado para você como a pilha do programa.

1026
01:19:57,100 --> 01:19:59,550
Note-se que esta lista ligada, é uma pilha.

1027
01:19:59,550 --> 01:20:01,580
Tudo o que basta colocar na pilha

1028
01:20:01,580 --> 01:20:09,960
é imediatamente o que nós vamos retirar a pilha para próxima visita.

1029
01:20:09,960 --> 01:20:14,380
Estamos fora do tempo, mas alguma dúvida?

1030
01:20:14,380 --> 01:20:23,530
[Estudante, ininteligível]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Então, se temos a nossa lista ligada,

1032
01:20:27,790 --> 01:20:30,150
atual está indo para apontar para esse cara,

1033
01:20:30,150 --> 01:20:34,690
e agora nós estamos apenas avançar nossa lista ligada a concentrar-se sobre esse cara.

1034
01:20:34,690 --> 01:20:44,200
Estamos atravessando sobre a lista ligada nessa linha.

1035
01:20:44,200 --> 01:20:51,200
E então eu acho que devemos libertar a nossa lista encadeada e outras coisas

1036
01:20:51,200 --> 01:20:53,880
uma vez antes de retornar verdadeiro ou falso, precisamos

1037
01:20:53,880 --> 01:20:57,360
iterar sobre a nossa lista ligada e sempre aqui, eu acho,

1038
01:20:57,360 --> 01:21:03,900
se atu direito não é igual, adicioná-lo, então agora nós queremos libertar

1039
01:21:03,900 --> 01:21:09,600
atu porque, bem, que nós esquecemos completamente sobre a lista? Sim.

1040
01:21:09,600 --> 01:21:12,880
Então é isso que nós queremos fazer aqui.

1041
01:21:12,880 --> 01:21:16,730
Onde está o ponteiro?

1042
01:21:16,730 --> 01:21:23,320
Cur era então - nós queremos uma lista struct * 10 é igual a próxima lista.

1043
01:21:23,320 --> 01:21:29,240
Lista livre, list = temp.

1044
01:21:29,240 --> 01:21:32,820
E, no caso em que retornar verdadeiro, precisamos iterar

1045
01:21:32,820 --> 01:21:37,050
sobre o restante de nossa lista ligada liberando coisas.

1046
01:21:37,050 --> 01:21:39,700
A coisa agradável sobre a solução recursiva é libertar as coisas

1047
01:21:39,700 --> 01:21:44,930
significa apenas factorings popping fora da pilha que vai acontecer para você.

1048
01:21:44,930 --> 01:21:50,720
Então, nós fomos de algo que é como 3 linhas de difícil de pensar sobre o código-

1049
01:21:50,720 --> 01:21:57,520
a algo que é significativamente mais muitos de difícil pensar-sobre linhas de código.

1050
01:21:57,520 --> 01:22:00,620
Mais alguma pergunta?

1051
01:22:00,620 --> 01:22:08,760
Tudo bem. Nós somos bons. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]