1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Seção 7] [menos confortável]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[Esta é CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Bem-vindo à secção 7.

5
00:00:09,080 --> 00:00:11,330
Graças ao furacão Sandy,

6
00:00:11,330 --> 00:00:13,440
em vez de ter uma secção normal esta semana,

7
00:00:13,440 --> 00:00:17,650
estamos fazendo este passo a passo, através da seção de perguntas.

8
00:00:17,650 --> 00:00:22,830
Eu vou estar a seguir, juntamente com o conjunto de problemas 6 Especificação,

9
00:00:22,830 --> 00:00:25,650
e passando por todas as perguntas do

10
00:00:25,650 --> 00:00:27,770
A Seção de secção de Perguntas.

11
00:00:27,770 --> 00:00:30,940
Se houver alguma dúvida,

12
00:00:30,940 --> 00:00:32,960
por favor postar estes em CS50 discutir.

13
00:00:32,960 --> 00:00:35,480
>> Tudo bem. Vamos começar.

14
00:00:35,480 --> 00:00:40,780
Agora eu estou olhando para a página 3 da Especificação conjunto de problemas.

15
00:00:40,780 --> 00:00:44,110
Nós vamos primeiro começar a falar sobre árvores binárias

16
00:00:44,110 --> 00:00:47,850
uma vez que estes têm muita relevância para o conjunto desta semana - problema

17
00:00:47,850 --> 00:00:49,950
a codificação árvore Huffman.

18
00:00:49,950 --> 00:00:55,000
Uma das estruturas de dados primeiras falamos sobre CS50 foi a matriz.

19
00:00:55,000 --> 00:01:00,170
Lembre-se que uma matriz é uma seqüência de elementos -

20
00:01:00,170 --> 00:01:04,019
todos do mesmo tipo, - armazenados ao lado uns dos outros na memória.

21
00:01:04,019 --> 00:01:14,420
Se eu tiver uma matriz de inteiros que eu possa desenhar usando este estilo de caixas-números-inteiros -

22
00:01:14,420 --> 00:01:20,290
Vamos dizer que eu tenho 5 na primeira caixa, eu tenho sete no segundo,

23
00:01:20,290 --> 00:01:27,760
então tenho 8, 10, e 20 na caixa final.

24
00:01:27,760 --> 00:01:33,000
Coisas Lembre-se, os dois realmente boas sobre essa matriz

25
00:01:33,000 --> 00:01:38,800
são de que temos esse acesso e de tempo constante para qualquer elemento específico

26
00:01:38,800 --> 00:01:40,500
 na matriz, se sabemos seu índice.

27
00:01:40,500 --> 00:01:44,670
Por exemplo, se eu quiser pegar o terceiro elemento na matriz -

28
00:01:44,670 --> 00:01:47,870
no índice 2, usando o nosso sistema de indexação baseado em zero -

29
00:01:47,870 --> 00:01:52,220
Eu literalmente só tem que fazer um simples cálculo matemático,

30
00:01:52,220 --> 00:01:56,170
hop para essa posição na matriz,

31
00:01:56,170 --> 00:01:57,840
puxe o 8 que está armazenado lá,

32
00:01:57,840 --> 00:01:59,260
e eu sou bom para ir.

33
00:01:59,260 --> 00:02:03,350
>> Uma das coisas ruins sobre essa matriz - que falou sobre

34
00:02:03,350 --> 00:02:05,010
quando discutimos listas ligadas -

35
00:02:05,010 --> 00:02:09,120
é que se eu quiser inserir um elemento para essa matriz,

36
00:02:09,120 --> 00:02:11,090
Eu vou ter que fazer alguma mudança por aí.

37
00:02:11,090 --> 00:02:12,940
Por exemplo, a matriz isso aqui

38
00:02:12,940 --> 00:02:16,850
é na ordem de classificação - classificados em ordem crescente -

39
00:02:16,850 --> 00:02:19,440
5, em seguida, 7, 8, em seguida, em seguida, 10, e depois 20 -

40
00:02:19,440 --> 00:02:23,100
mas se eu quiser inserir o número 9 para esta matriz,

41
00:02:23,100 --> 00:02:27,460
Eu vou ter que mudar alguns dos elementos a fim de tornar o espaço.

42
00:02:27,460 --> 00:02:30,440
Podemos chamar isso aqui.

43
00:02:30,440 --> 00:02:35,650
Vou ter que mover a 5, a 7 e, em seguida, a 8;

44
00:02:35,650 --> 00:02:38,720
criar um espaço onde posso colocar o 9,

45
00:02:38,720 --> 00:02:45,910
e, em seguida, a 10 e a 20 pode ir para a direita do 9.

46
00:02:45,910 --> 00:02:49,450
Este é um tipo de dor, porque no pior cenário -

47
00:02:49,450 --> 00:02:54,350
quando estamos tendo que inserir ou no início ou no final

48
00:02:54,350 --> 00:02:56,040
da matriz, dependendo de como estamos mudando -

49
00:02:56,040 --> 00:02:58,850
podemos acabar tendo que mudar todos os elementos

50
00:02:58,850 --> 00:03:00,750
que estamos actualmente a armazenar na matriz.

51
00:03:00,750 --> 00:03:03,810
>> Então, o que era a maneira de contornar isso?

52
00:03:03,810 --> 00:03:09,260
A maneira de contornar isso era para ir para o nosso método de lista encadeada, onde -

53
00:03:09,260 --> 00:03:19,820
em vez de armazenar os elementos 5, 7, 8, 10, e 20 todas próximas umas das outras na memória -

54
00:03:19,820 --> 00:03:25,630
o que, em vez fez foi armazená-los tipo de onde nos queria para armazená-los

55
00:03:25,630 --> 00:03:32,470
nestes nós Linked-lista que eu estou desenhando aqui, tipo de ad hoc.

56
00:03:32,470 --> 00:03:42,060
E, então, conectado-los em conjunto, utilizando estes ponteiros próximos.

57
00:03:42,060 --> 00:03:44,370
I pode ter um ponteiro a partir de 5 a 7,

58
00:03:44,370 --> 00:03:46,420
um ponteiro a partir da 7 à 8,

59
00:03:46,420 --> 00:03:47,770
um ponteiro a partir da 8 à 10,

60
00:03:47,770 --> 00:03:51,220
e, finalmente, um ponteiro da 10 à 20,

61
00:03:51,220 --> 00:03:54,880
e, em seguida, um ponteiro nulo no 20, indicando que não há nada de esquerda.

62
00:03:54,880 --> 00:03:59,690
O trade-off que temos aqui

63
00:03:59,690 --> 00:04:05,360
é que agora se pretende inserir o número 9 em nossa lista ordenada,

64
00:04:05,360 --> 00:04:08,270
tudo o que temos a fazer é criar um novo nó com 9,

65
00:04:08,270 --> 00:04:12,290
fio-lo para apontar para o local apropriado,

66
00:04:12,290 --> 00:04:20,630
e, em seguida, re-ligação do 8 a apontar para baixo para o 9.

67
00:04:20,630 --> 00:04:25,660
Isso é muito rápido, assumir que sabemos exatamente onde queremos inserir o 9.

68
00:04:25,660 --> 00:04:32,610
Mas o trade-off em troca para isso é que temos agora perdeu o acesso de tempo constante

69
00:04:32,610 --> 00:04:36,230
para qualquer elemento particular na nossa estrutura de dados.

70
00:04:36,230 --> 00:04:40,950
Por exemplo, se eu quero encontrar o quarto elemento nesta lista ligada,

71
00:04:40,950 --> 00:04:43,510
Eu vou ter que começar bem no início da lista

72
00:04:43,510 --> 00:04:48,930
e trabalhar o meu caminho através da contagem nó a nó até encontrar o quarto.

73
00:04:48,930 --> 00:04:55,870
>> A fim de obter um desempenho melhor acesso do que uma lista ligada -

74
00:04:55,870 --> 00:04:59,360
mas também manter alguns dos benefícios que tivemos

75
00:04:59,360 --> 00:05:01,800
em termos de tempo de inserção a partir de uma lista ligada -

76
00:05:01,800 --> 00:05:05,750
uma árvore binária está indo a necessidade de usar a memória um pouco mais.

77
00:05:05,750 --> 00:05:11,460
Em particular, em vez de ter apenas um ponteiro em um nó de árvore binária -

78
00:05:11,460 --> 00:05:13,350
como a lista ligada nó faz -

79
00:05:13,350 --> 00:05:16,950
vamos adicionar um segundo ponteiro para o nó de árvore binária.

80
00:05:16,950 --> 00:05:19,950
Em vez de ter apenas um ponteiro para o próximo elemento,

81
00:05:19,950 --> 00:05:24,420
vamos ter um ponteiro para uma criança esquerdo e um direito da criança.

82
00:05:24,420 --> 00:05:26,560
>> Vamos tirar uma foto para ver o que realmente parece.

83
00:05:26,560 --> 00:05:31,350
Mais uma vez, eu vou usar essas caixas e flechas.

84
00:05:31,350 --> 00:05:37,150
Um nó da árvore binária vai começar com apenas uma caixa simples.

85
00:05:37,150 --> 00:05:40,940
Vai ter um espaço para o valor,

86
00:05:40,940 --> 00:05:47,280
e depois também vai ter um espaço para a criança esquerda e direita da criança.

87
00:05:47,280 --> 00:05:49,280
Eu estou indo para classificá-los aqui.

88
00:05:49,280 --> 00:05:57,560
Nós vamos ter o filho esquerdo, e então nós vamos ter o filho direito.

89
00:05:57,560 --> 00:05:59,920
Há muitas maneiras diferentes de fazer isso.

90
00:05:59,920 --> 00:06:02,050
Às vezes para o espaço e conveniência,

91
00:06:02,050 --> 00:06:06,460
Eu, na verdade, desenhá-lo como eu estou fazendo aqui em baixo

92
00:06:06,460 --> 00:06:10,910
onde eu vou ter o valor no topo,

93
00:06:10,910 --> 00:06:14,060
e depois o filho da direita no canto inferior direito,

94
00:06:14,060 --> 00:06:16,060
e criança a esquerda no canto inferior esquerdo.

95
00:06:16,060 --> 00:06:20,250
Voltando a este diagrama superior,

96
00:06:20,250 --> 00:06:22,560
temos o valor no topo,

97
00:06:22,560 --> 00:06:25,560
então temos o ponteiro esquerdo criança, e depois temos o ponteiro criança direito.

98
00:06:25,560 --> 00:06:30,110
>> Na Especificação conjunto de problemas,

99
00:06:30,110 --> 00:06:33,110
falamos de desenhar um nó que tem um valor de 7,

100
00:06:33,110 --> 00:06:39,750
e um ponteiro-esquerdo criança que é nulo, e um ponteiro direito da criança, que é nulo.

101
00:06:39,750 --> 00:06:46,040
Nós pode escrever NULL capital no espaço de

102
00:06:46,040 --> 00:06:51,610
tanto a criança quanto a esquerda e direita da criança, ou podemos chamar esta barra diagonal

103
00:06:51,610 --> 00:06:53,750
através de cada uma das caixas, para indicar que é nula.

104
00:06:53,750 --> 00:06:57,560
Eu vou fazer isso só porque é mais simples.

105
00:06:57,560 --> 00:07:03,700
O que você vê aqui são duas formas de diagramação de um nó de árvore muito simples binário

106
00:07:03,700 --> 00:07:07,960
onde temos o valor 7 e ponteiros criança nulos.

107
00:07:07,960 --> 00:07:15,220
>> A segunda parte fala sobre como nossos especificação com listas ligadas -

108
00:07:15,220 --> 00:07:18,270
Lembre-se, temos apenas a segurar o primeiro elemento de uma lista

109
00:07:18,270 --> 00:07:20,270
para lembrar toda a lista -

110
00:07:20,270 --> 00:07:26,140
e da mesma forma, com uma árvore binária, só temos que segurar um ponteiro para a árvore

111
00:07:26,140 --> 00:07:31,120
, a fim de manter o controlo sobre a estrutura de dados inteira.

112
00:07:31,120 --> 00:07:36,150
Este elemento especial da árvore é chamado nó raiz da árvore.

113
00:07:36,150 --> 00:07:43,360
Por exemplo, se esse nó um - este nó que contém o valor 7

114
00:07:43,360 --> 00:07:45,500
com ponteiros nulos lados esquerdo e direito da criança -

115
00:07:45,500 --> 00:07:47,360
eram o único valor em nossa árvore,

116
00:07:47,360 --> 00:07:50,390
então este seria o nosso nó raiz.

117
00:07:50,390 --> 00:07:52,240
É o início da nossa árvore.

118
00:07:52,240 --> 00:07:58,530
Podemos ver isso um pouco mais claramente, uma vez que comece a adicionar mais nós nossa árvore.

119
00:07:58,530 --> 00:08:01,510
Deixa-me tirar-se uma nova página.

120
00:08:01,510 --> 00:08:05,000
>> Agora vamos desenhar uma árvore que tem 7 na raiz,

121
00:08:05,000 --> 00:08:10,920
e 3 dentro da criança à esquerda, e 9 no interior da criança direita.

122
00:08:10,920 --> 00:08:13,500
Novamente, isso é muito simples.

123
00:08:13,500 --> 00:08:26,510
Temos 7, desenhe um nó para o 3, um nó para 9,

124
00:08:26,510 --> 00:08:32,150
e eu estou indo para definir o ponteiro esquerdo criança de 7 a apontar para o nó contendo 3,

125
00:08:32,150 --> 00:08:37,850
e o ponteiro direito do filho do nó contendo 7 para o nó que contém 9.

126
00:08:37,850 --> 00:08:42,419
Agora, desde 3 e 9 não tem filhos,

127
00:08:42,419 --> 00:08:48,500
vamos definir todos os seus ponteiros filho para ser nulo.

128
00:08:48,500 --> 00:08:56,060
Aqui, a raiz da nossa árvore corresponde ao nó que contém o número 7.

129
00:08:56,060 --> 00:09:02,440
Você pode ver que, se tudo o que temos é um ponteiro para o nó raiz,

130
00:09:02,440 --> 00:09:07,330
então podemos caminhar através da nossa árvore e acessar nós tanto a criança -

131
00:09:07,330 --> 00:09:10,630
ambos os 3 e 9.

132
00:09:10,630 --> 00:09:14,820
Não há necessidade de manter ponteiros para cada nó na árvore.

133
00:09:14,820 --> 00:09:22,080
Tudo bem. Agora vamos adicionar um outro nó a este diagrama.

134
00:09:22,080 --> 00:09:25,370
Estamos indo para adicionar um nó contendo 6,

135
00:09:25,370 --> 00:09:34,140
e nós estamos indo para adicionar este como o filho direito do nó contendo 3.

136
00:09:34,140 --> 00:09:41,850
Para fazer isso, eu vou apagar esse ponteiro nulo no 3-nó

137
00:09:41,850 --> 00:09:47,750
e conectá-lo para apontar para o nó contendo 6. Tudo bem.

138
00:09:47,750 --> 00:09:53,800
>> Neste ponto, vamos falar sobre um pouco de terminologia.

139
00:09:53,800 --> 00:09:58,230
Para começar, a razão pela qual isso é chamado de uma árvore binária em particular

140
00:09:58,230 --> 00:10:00,460
é que tem dois ponteiros de crianças.

141
00:10:00,460 --> 00:10:06,020
Existem outros tipos de árvores que têm mais apontadores criança.

142
00:10:06,020 --> 00:10:10,930
Em particular, você fez um 'try' no Conjunto Problema 5.

143
00:10:10,930 --> 00:10:19,310
Você vai perceber que naquele tentativa, você teve 27 indicações diferentes para diferentes crianças -

144
00:10:19,310 --> 00:10:22,410
um para cada uma das 26 letras do alfabeto Inglês,

145
00:10:22,410 --> 00:10:25,410
e depois a 27 para o apóstrofo -

146
00:10:25,410 --> 00:10:28,900
assim, que é semelhante a um tipo de árvore.

147
00:10:28,900 --> 00:10:34,070
Mas aqui, já que é binário, só temos dois ponteiros da criança.

148
00:10:34,070 --> 00:10:37,880
>> Além deste nó raiz que falamos,

149
00:10:37,880 --> 00:10:41,470
Nós também estamos jogando em torno deste termo "criança".

150
00:10:41,470 --> 00:10:44,470
O que significa para um nó a ser um filho de outro nó?

151
00:10:44,470 --> 00:10:54,060
É, literalmente, significa que um nó filho é um filho de outro nó

152
00:10:54,060 --> 00:10:58,760
se que outro nó tem uma das suas crianças ponteiros definidas para apontar para esse nó.

153
00:10:58,760 --> 00:11:01,230
Para colocar isso em termos mais concretos,

154
00:11:01,230 --> 00:11:11,170
se 3 é apontada por um dos ponteiros criança de 7, em seguida, 3 é uma criança de 7.

155
00:11:11,170 --> 00:11:14,510
Se tivéssemos de descobrir o que os filhos de 7 são -

156
00:11:14,510 --> 00:11:18,510
bem, vemos que 7 tem um ponteiro para 3 e um ponteiro a 9,

157
00:11:18,510 --> 00:11:22,190
para 9 e 3 são as crianças de 7.

158
00:11:22,190 --> 00:11:26,650
Nove não tem filhos porque ponteiros seus filhos são nulos,

159
00:11:26,650 --> 00:11:30,940
e 3 tem apenas um filho, 6.

160
00:11:30,940 --> 00:11:37,430
Seis também não tem filhos, porque ambos os seus ponteiros são nulos, o que nós vamos chamar agora.

161
00:11:37,430 --> 00:11:45,010
>> Além disso, também falamos sobre os pais de um nó,

162
00:11:45,010 --> 00:11:51,100
e este é, como seria de esperar, o reverso desta descrição criança.

163
00:11:51,100 --> 00:11:58,620
Cada nó tem apenas um pai - em vez de dois, como você poderia esperar com os humanos.

164
00:11:58,620 --> 00:12:03,390
Por exemplo, a matriz de 3 a 7.

165
00:12:03,390 --> 00:12:10,800
O pai de 9 também é 7, o pai e de 6 a 3. Não há muito a ele.

166
00:12:10,800 --> 00:12:15,720
Nós também temos condições de falar sobre avós e netos,

167
00:12:15,720 --> 00:12:18,210
e, mais geralmente falamos sobre os antepassados

168
00:12:18,210 --> 00:12:20,960
e descendentes de um nó específico.

169
00:12:20,960 --> 00:12:25,710
O ancestral de um nó - ou antepassados, sim, de um nó -

170
00:12:25,710 --> 00:12:32,730
são todos os nós que estão no caminho da raiz para esse nó.

171
00:12:32,730 --> 00:12:36,640
Por exemplo, se eu estou olhando para o 6 nó,

172
00:12:36,640 --> 00:12:46,430
em seguida, os antepassados ​​vão ser o 3 eo 7.

173
00:12:46,430 --> 00:12:55,310
Os ancestrais de 9, por exemplo, são - se eu estou olhando para o nó 9 -

174
00:12:55,310 --> 00:12:59,990
em seguida, o antepassado de 9 é apenas 7.

175
00:12:59,990 --> 00:13:01,940
E descendentes são exatamente o contrário.

176
00:13:01,940 --> 00:13:05,430
Se eu quero olhar para todos os descendentes de 7,

177
00:13:05,430 --> 00:13:11,020
então eu tenho que olhar para todos os nós abaixo dela.

178
00:13:11,020 --> 00:13:16,950
Então, eu tenho 3, 9 e 6 todos como descendentes de 7.

179
00:13:16,950 --> 00:13:24,170
>> O prazo final que vamos falar é esta noção de ser um irmão.

180
00:13:24,170 --> 00:13:27,980
Irmãos - tipo de seguir junto com esses termos familiares -

181
00:13:27,980 --> 00:13:33,150
são nós que estão ao mesmo nível da árvore.

182
00:13:33,150 --> 00:13:42,230
Então, 3 e 9 são irmãos porque são ao mesmo nível na árvore.

183
00:13:42,230 --> 00:13:46,190
Ambos têm o mesmo pai, 7.

184
00:13:46,190 --> 00:13:51,400
O 6 não tem irmãos, porque 9 não têm filhos.

185
00:13:51,400 --> 00:13:55,540
E 7 não tem irmãos, porque é a raiz da nossa árvore,

186
00:13:55,540 --> 00:13:59,010
e há sempre apenas uma raiz.

187
00:13:59,010 --> 00:14:02,260
Para 7 ter irmãos não teria de ser um nó acima de 7.

188
00:14:02,260 --> 00:14:07,480
Teria de ser um pai de 7, caso em que 7 já não seria a raiz da árvore.

189
00:14:07,480 --> 00:14:10,480
Então que o pai novo, de 7 também teria de ter um filho,

190
00:14:10,480 --> 00:14:16,480
e que a criança seria, então, o irmão de 7.

191
00:14:16,480 --> 00:14:21,040
>> Tudo bem. Seguindo em frente.

192
00:14:21,040 --> 00:14:24,930
Quando começamos nossa discussão sobre árvores binárias,

193
00:14:24,930 --> 00:14:28,790
nós falamos sobre como nós íamos usá-los para

194
00:14:28,790 --> 00:14:32,800
ganhar uma vantagem sobre as duas matrizes e listas ligadas.

195
00:14:32,800 --> 00:14:37,220
E a maneira como vamos fazer isso é com esta propriedade encomenda.

196
00:14:37,220 --> 00:14:41,080
Dizemos que uma árvore binária é ordenada, de acordo com a especificação,

197
00:14:41,080 --> 00:14:45,740
se, para cada nó na nossa árvore, todos os seus descendentes à esquerda -

198
00:14:45,740 --> 00:14:48,670
a criança esquerda e todos os descendentes do filho esquerdo de -

199
00:14:48,670 --> 00:14:54,510
têm valores menores, e todos os nós da direita -

200
00:14:54,510 --> 00:14:57,770
o direito da criança e todos os descendentes de direito da criança de -

201
00:14:57,770 --> 00:15:02,800
ter nós mais do que o valor do nó atual que estamos olhando.

202
00:15:02,800 --> 00:15:07,850
Só para simplificar, vamos assumir que não há nós duplicados na nossa árvore.

203
00:15:07,850 --> 00:15:11,180
Por exemplo, nesta árvore que não estamos indo para lidar com o caso

204
00:15:11,180 --> 00:15:13,680
onde temos o valor 7 na raiz

205
00:15:13,680 --> 00:15:16,720
 e depois também temos o valor 7 em outras partes da árvore.

206
00:15:16,720 --> 00:15:24,390
Neste caso, você vai perceber que esta árvore é de fato ordenado.

207
00:15:24,390 --> 00:15:26,510
Temos o valor 7 na raiz.

208
00:15:26,510 --> 00:15:29,720
Tudo para a esquerda, de 7 -

209
00:15:29,720 --> 00:15:35,310
se eu desfazer todas essas pequenas marcas aqui -

210
00:15:35,310 --> 00:15:40,450
tudo para a esquerda, de 7 - a 3 e a 6 -

211
00:15:40,450 --> 00:15:49,410
esses valores estão a menos de 7, e tudo para a direita - o que é exatamente isso 9 -

212
00:15:49,410 --> 00:15:53,450
é maior do que 7.

213
00:15:53,450 --> 00:15:58,650
>> Esta não é a única árvore ordenados contendo estes valores,

214
00:15:58,650 --> 00:16:03,120
mas vamos desenhar um pouco mais deles.

215
00:16:03,120 --> 00:16:05,030
Há realmente um monte de maneiras que podemos fazer isso.

216
00:16:05,030 --> 00:16:09,380
Eu vou usar um atalho só para manter as coisas simples, onde -

217
00:16:09,380 --> 00:16:11,520
em vez de desenhar a todo caixas-e-flechas -

218
00:16:11,520 --> 00:16:14,220
Eu só vou para desenhar os números e adicionar setas conectando-los.

219
00:16:14,220 --> 00:16:22,920
Para começar, vamos escrever a nossa árvore original de novo, onde tivemos 7, e depois um 3,

220
00:16:22,920 --> 00:16:25,590
e depois 3 apontou para o direito à 6,

221
00:16:25,590 --> 00:16:30,890
e 7 teve um filho direito que tinha 9 anos.

222
00:16:30,890 --> 00:16:33,860
Tudo bem. O que é outra forma que podemos escrever esta árvore?

223
00:16:33,860 --> 00:16:38,800
Em vez de ter 3 ser o filho esquerdo de 7,

224
00:16:38,800 --> 00:16:41,360
também poderíamos ter a 6 ser o filho esquerdo de 7,

225
00:16:41,360 --> 00:16:44,470
e depois 3 ser o filho esquerdo do 6.

226
00:16:44,470 --> 00:16:48,520
Que seria parecido com esta árvore aqui onde eu tenho 7,

227
00:16:48,520 --> 00:16:57,860
depois 6, depois 3, e um 9 do lado direito.

228
00:16:57,860 --> 00:17:01,490
Nós também não temos que ter 7 como nosso nó raiz.

229
00:17:01,490 --> 00:17:03,860
Nós também poderíamos ter 6 como o nosso nó raiz.

230
00:17:03,860 --> 00:17:06,470
O que isso parece?

231
00:17:06,470 --> 00:17:09,230
Se vamos manter esta propriedade ordenada,

232
00:17:09,230 --> 00:17:12,970
tudo para a esquerda do 6 tem que ser menos do que isso.

233
00:17:12,970 --> 00:17:16,540
Há apenas uma possibilidade, e isso é 3.

234
00:17:16,540 --> 00:17:19,869
Mas, então, como o direito da criança de 6, temos duas possibilidades.

235
00:17:19,869 --> 00:17:25,380
Primeiro, pode-se ter a 7 e, em seguida, o 9,

236
00:17:25,380 --> 00:17:28,850
ou poderíamos chamar isso - como eu estou prestes a fazer aqui -

237
00:17:28,850 --> 00:17:34,790
onde temos o 9 como o direito da criança do 6,

238
00:17:34,790 --> 00:17:39,050
e em seguida a 7 como o filho esquerdo do 9.

239
00:17:39,050 --> 00:17:44,240
>> Agora, 7 e 6 não são os únicos valores possíveis para a raiz.

240
00:17:44,240 --> 00:17:50,200
Nós também poderíamos ter 3 estar na raiz.

241
00:17:50,200 --> 00:17:52,240
O que acontece se 3 é a raiz?

242
00:17:52,240 --> 00:17:54,390
Aqui, as coisas ficam um pouco mais interessante.

243
00:17:54,390 --> 00:17:58,440
Três não possui valores que são menos do que isto,

244
00:17:58,440 --> 00:18:02,070
modo que o lado esquerdo inteiro da árvore é apenas vai ser nulo.

245
00:18:02,070 --> 00:18:03,230
Não vai ser nada lá.

246
00:18:03,230 --> 00:18:07,220
Para a direita, podemos listar as coisas em ordem crescente.

247
00:18:07,220 --> 00:18:15,530
Poderíamos ter 3, e depois 6, depois 7, em seguida, 9.

248
00:18:15,530 --> 00:18:26,710
Ou, poderíamos fazer 3, depois 6, depois 9, depois 7.

249
00:18:26,710 --> 00:18:35,020
Ou, poderíamos fazer 3, depois 7, depois 6, depois 9.

250
00:18:35,020 --> 00:18:40,950
Ou, 3, 7 - na verdade, não, não podemos fazer um 7 mais.

251
00:18:40,950 --> 00:18:43,330
Essa é a nossa única coisa lá.

252
00:18:43,330 --> 00:18:54,710
Podemos fazer 9, e depois a partir do 9 podemos fazer 6 e 7.

253
00:18:54,710 --> 00:19:06,980
Ou, pode-se fazê-3, e depois 9, em seguida, 7, e, em seguida, 6.

254
00:19:06,980 --> 00:19:12,490
>> Uma coisa de chamar a atenção aqui é

255
00:19:12,490 --> 00:19:14,510
que estas árvores são um pouco esquisito.

256
00:19:14,510 --> 00:19:17,840
Em particular, se olharmos para as quatro árvores no lado direito -

257
00:19:17,840 --> 00:19:20,930
Vou circular-los, aqui -

258
00:19:20,930 --> 00:19:28,410
estas árvores parecem quase exatamente como uma lista ligada.

259
00:19:28,410 --> 00:19:32,670
Cada nó tem apenas um filho,

260
00:19:32,670 --> 00:19:38,950
e assim não temos nada disso estrutura de árvore que vemos, por exemplo,

261
00:19:38,950 --> 00:19:44,720
 nesta árvore um solitário aqui na parte inferior esquerda.

262
00:19:44,720 --> 00:19:52,490
Estas árvores são chamadas realmente degenerada árvores binárias,

263
00:19:52,490 --> 00:19:54,170
e nós vamos falar sobre estes mais no futuro -

264
00:19:54,170 --> 00:19:56,730
especialmente se você continuar a fazer cursos de ciências outros computadores.

265
00:19:56,730 --> 00:19:59,670
Estas árvores são degenerados.

266
00:19:59,670 --> 00:20:03,780
Eles não são muito úteis, pois, de fato, essa estrutura se presta

267
00:20:03,780 --> 00:20:08,060
 a pesquisa de vezes semelhantes aos de uma lista ligada.

268
00:20:08,060 --> 00:20:13,050
Nós não temos de aproveitar a memória extra - este ponteiro extra -

269
00:20:13,050 --> 00:20:18,840
por causa da nossa estrutura ser ruim assim.

270
00:20:18,840 --> 00:20:24,700
Ao invés de ir e tirar as árvores binárias que têm nove na raiz,

271
00:20:24,700 --> 00:20:27,220
que é o caso final que teria,

272
00:20:27,220 --> 00:20:32,380
estamos em vez disso, neste momento, vou falar um pouco sobre esse outro termo

273
00:20:32,380 --> 00:20:36,150
que usamos ao falar sobre as árvores, que é chamado a altura.

274
00:20:36,150 --> 00:20:45,460
>> A altura de uma árvore é a distância a partir da raiz para o nó de mais distante,

275
00:20:45,460 --> 00:20:48,370
ou melhor, o número de saltos que você teria que fazer a fim de

276
00:20:48,370 --> 00:20:53,750
começar a partir da raiz e depois acabam no nó mais distante na árvore.

277
00:20:53,750 --> 00:20:57,330
Se olharmos para algumas dessas árvores que temos desenhado aqui,

278
00:20:57,330 --> 00:21:07,870
podemos ver que, se tomarmos esta árvore no canto superior esquerdo e começamos a 3,

279
00:21:07,870 --> 00:21:14,510
então nós temos que fazer um salto para chegar ao 6, um segundo salto para chegar ao 7,

280
00:21:14,510 --> 00:21:20,560
e um terceiro hop para chegar ao 9.

281
00:21:20,560 --> 00:21:26,120
Então, a altura da árvore é de 3.

282
00:21:26,120 --> 00:21:30,640
Nós podemos fazer o mesmo exercício para as outras árvores descritas com este verde,

283
00:21:30,640 --> 00:21:40,100
e podemos ver que a altura de todas estas árvores é também verdade 3.

284
00:21:40,100 --> 00:21:45,230
Isso é parte do que os torna degenerada -

285
00:21:45,230 --> 00:21:53,750
que a sua altura é apenas um a menos que o número de nós em toda a árvore.

286
00:21:53,750 --> 00:21:58,400
Se olharmos para esta outra árvore que é cercada com vermelho, por outro lado,

287
00:21:58,400 --> 00:22:03,920
vemos que os nós mais distantes da folha são o 6 eo 9 -

288
00:22:03,920 --> 00:22:06,940
o deixa de ser os nós que não têm filhos.

289
00:22:06,940 --> 00:22:11,760
Assim, a fim de obter a partir do nó de raiz, quer a 6 ou a 9,

290
00:22:11,760 --> 00:22:17,840
temos que fazer um salto para chegar ao 7 e, em seguida, um segundo salto para chegar ao 9,

291
00:22:17,840 --> 00:22:21,240
e do mesmo modo, apenas o salto de um segundo a partir do 7 para obter a 6.

292
00:22:21,240 --> 00:22:29,080
Assim, a altura desta árvore aqui é apenas 2.

293
00:22:29,080 --> 00:22:35,330
Você pode voltar e fazer isso para todas as outras árvores que previamente discutido

294
00:22:35,330 --> 00:22:37,380
começando com o 7 e a 6,

295
00:22:37,480 --> 00:22:42,500
e você verá que a altura de todas as árvores também é 2.

296
00:22:42,500 --> 00:22:46,320
>> A razão pela qual temos falado sobre ordenou árvores binárias

297
00:22:46,320 --> 00:22:50,250
e por que eles são legais porque você pode procurar por elas em

298
00:22:50,250 --> 00:22:53,810
uma forma muito semelhante à procura de um array ordenado.

299
00:22:53,810 --> 00:22:58,720
Este é o lugar onde se fala de conseguir que o tempo de pesquisa melhorada

300
00:22:58,720 --> 00:23:02,730
sobre a lista ligada simples.

301
00:23:02,730 --> 00:23:05,010
Com uma lista ligada - se você quiser encontrar um elemento particular -

302
00:23:05,010 --> 00:23:07,470
você está no melhor vai fazer algum tipo de busca linear

303
00:23:07,470 --> 00:23:10,920
onde você começa no início de uma lista de e-hop um-por-um -

304
00:23:10,920 --> 00:23:12,620
um nó, um nó -

305
00:23:12,620 --> 00:23:16,060
toda a lista até encontrar o que você está procurando.

306
00:23:16,060 --> 00:23:19,440
Considerando que, se você tem uma árvore binária que está armazenado neste formato agradável,

307
00:23:19,440 --> 00:23:23,300
você pode realmente ficar mais de uma busca binária acontecendo

308
00:23:23,300 --> 00:23:25,160
onde você dividir e conquistar

309
00:23:25,160 --> 00:23:29,490
e pesquisa através da metade apropriada da árvore de cada etapa.

310
00:23:29,490 --> 00:23:32,840
Vamos ver como isso funciona.

311
00:23:32,840 --> 00:23:38,850
>> Se temos - de novo, voltando a nossa árvore original -

312
00:23:38,850 --> 00:23:46,710
começamos a 7, que têm 3, à esquerda, à direita 9,

313
00:23:46,710 --> 00:23:51,740
e sob a 3 temos a 6.

314
00:23:51,740 --> 00:24:01,880
Se quisermos buscar o número 6 na árvore, nós iniciar na raiz.

315
00:24:01,880 --> 00:24:08,910
Nós comparar o valor que estamos procurando, digamos 6,

316
00:24:08,910 --> 00:24:12,320
para o valor armazenado no nó que nós estamos procurando, aos 7,

317
00:24:12,320 --> 00:24:21,200
descobrir que 6 é de fato menor que 7, então nós mover para a esquerda.

318
00:24:21,200 --> 00:24:25,530
Se o valor de 6 tinha sido superior a 7, que teria lugar movido para a direita.

319
00:24:25,530 --> 00:24:29,770
Como sabemos que - devido à estrutura da nossa árvore binária ordenada -

320
00:24:29,770 --> 00:24:33,910
todos os valores de menos do que 7 vão ser armazenadas para a esquerda, de 7,

321
00:24:33,910 --> 00:24:40,520
não há necessidade de incomodar mesmo olhando pelo lado direito da árvore.

322
00:24:40,520 --> 00:24:43,780
Uma vez que se mover para a esquerda e agora estamos no nó contendo 3,

323
00:24:43,780 --> 00:24:48,110
nós podemos fazer isso de novo mesma comparação, onde se compara o 3 eo 6.

324
00:24:48,110 --> 00:24:52,430
E descobrimos que, enquanto 6 - o valor que estamos procurando - é maior do que 3,

325
00:24:52,430 --> 00:24:58,580
que pode ir para o lado direito do nó contendo 3.

326
00:24:58,580 --> 00:25:02,670
Não há lado esquerdo aqui, portanto, poderia ter ignorado isso.

327
00:25:02,670 --> 00:25:06,510
Mas só sabemos que porque nós estamos olhando para a própria árvore,

328
00:25:06,510 --> 00:25:08,660
e podemos ver que a árvore não tem filhos.

329
00:25:08,660 --> 00:25:13,640
>> Também é muito fácil olhar para cima 6 nesta árvore se estamos fazendo a nós mesmos como seres humanos,

330
00:25:13,640 --> 00:25:16,890
mas vamos acompanhar esse processo mecanicamente como um computador faria

331
00:25:16,890 --> 00:25:18,620
para realmente entender o algoritmo.

332
00:25:18,620 --> 00:25:26,200
Neste ponto, estamos agora olhando para um nó que contém 6,

333
00:25:26,200 --> 00:25:29,180
e nós estamos olhando para o valor 6,

334
00:25:29,180 --> 00:25:31,740
assim, na verdade, nós encontramos o nó apropriado.

335
00:25:31,740 --> 00:25:35,070
Encontramos o valor 6 em nossa árvore, e nós podemos parar a nossa busca.

336
00:25:35,070 --> 00:25:37,330
Neste ponto, dependendo do que está acontecendo,

337
00:25:37,330 --> 00:25:41,870
podemos dizer, sim, nós encontramos o valor 6, que existe na nossa árvore.

338
00:25:41,870 --> 00:25:47,640
Ou, se estamos planejando para inserir um nó ou fazer algo, nós podemos fazer isso neste momento.

339
00:25:47,640 --> 00:25:53,010
>> Vamos fazer pesquisas mais algumas só para ver como isso funciona.

340
00:25:53,010 --> 00:25:59,390
Vejamos o que acontece se fôssemos tentar e olhar para cima o valor 10.

341
00:25:59,390 --> 00:26:02,970
Se estivéssemos a olhar para cima o valor 10, que iria começar na raiz.

342
00:26:02,970 --> 00:26:07,070
Nós vemos que 10 é maior que 7, assim que nós mover para a direita.

343
00:26:07,070 --> 00:26:13,640
Teríamos a 9 e comparar 9 ao 10 e veja que 9 é realmente inferior a 10.

344
00:26:13,640 --> 00:26:16,210
Então, novamente, que ia tentar se mover para a direita.

345
00:26:16,210 --> 00:26:20,350
Mas, neste ponto, a gente percebe que estamos em um nó nulo.

346
00:26:20,350 --> 00:26:23,080
Não há nada lá. Não há nada que o 10 deve ser.

347
00:26:23,080 --> 00:26:29,360
Este é o lugar onde nós podemos relatar falha - que na verdade não há 10 na árvore.

348
00:26:29,360 --> 00:26:35,420
E, finalmente, vamos percorrer o caso em que estamos a tentar procurar uma na árvore.

349
00:26:35,420 --> 00:26:38,790
Isto é semelhante ao que acontece quando olhamos para cima 10, exceto em vez de ir para a direita,

350
00:26:38,790 --> 00:26:41,260
estamos indo para ir para a esquerda.

351
00:26:41,260 --> 00:26:46,170
Nós começamos no 7 e ver que uma é inferior a 7, de modo que se mover para a esquerda.

352
00:26:46,170 --> 00:26:51,750
Chegamos ao 3 e ver que 1 é menor do que 3, portanto, mais uma vez, tentar mover para a esquerda.

353
00:26:51,750 --> 00:26:59,080
Neste ponto temos um nó nulo, então, novamente, podemos denunciar o fracasso.

354
00:26:59,080 --> 00:27:10,260
>> Se você quer aprender mais sobre árvores binárias,

355
00:27:10,260 --> 00:27:14,420
há um monte de diversão pequenos problemas que você pode fazer com eles.

356
00:27:14,420 --> 00:27:19,450
Eu sugiro praticar o desenho de estes diagramas um-por-um

357
00:27:19,450 --> 00:27:21,910
e depois através de todos os passos diferentes,

358
00:27:21,910 --> 00:27:25,060
porque isso virá a super-acessível

359
00:27:25,060 --> 00:27:27,480
não apenas quando você está fazendo a Huffman conjunto de problemas de codificação

360
00:27:27,480 --> 00:27:29,390
mas também em cursos futuros -

361
00:27:29,390 --> 00:27:32,220
apenas aprender a tirar essas estruturas de dados e pensar os problemas

362
00:27:32,220 --> 00:27:38,000
com caneta e papel, ou, neste caso do iPad, e caneta.

363
00:27:38,000 --> 00:27:41,000
>> Neste ponto, porém, vamos passar a fazer alguma prática de codificação

364
00:27:41,000 --> 00:27:44,870
e realmente jogar com essas árvores binárias e ver.

365
00:27:44,870 --> 00:27:52,150
Vou voltar para o meu computador.

366
00:27:52,150 --> 00:27:58,480
Para esta parte da seção, em vez de usar CS50 CS50 Executar ou espaços,

367
00:27:58,480 --> 00:28:01,500
Eu vou usar o aparelho.

368
00:28:01,500 --> 00:28:04,950
>> Após juntamente com a especificação do conjunto de problemas,

369
00:28:04,950 --> 00:28:07,740
Eu vejo que eu tenho que abrir o aparelho,

370
00:28:07,740 --> 00:28:11,020
ir para a minha pasta Dropbox, crie uma pasta chamada Seção 7,

371
00:28:11,020 --> 00:28:15,730
e, então, criar um arquivo chamado binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Aqui vamos nós. Eu tenho o aparelho já está aberta.

373
00:28:22,050 --> 00:28:25,910
Eu vou puxar um terminal.

374
00:28:25,910 --> 00:28:38,250
Eu estou indo para ir para a pasta Dropbox, crie um diretório chamado Seção 7,

375
00:28:38,250 --> 00:28:42,230
e ver que é totalmente vazio.

376
00:28:42,230 --> 00:28:48,860
Agora vou abrir binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Tudo bem. Aqui vamos nós - arquivo vazio.

378
00:28:51,750 --> 00:28:54,330
>> Vamos voltar com a especificação.

379
00:28:54,330 --> 00:28:59,850
A especificação pede para criar uma nova definição de tipo

380
00:28:59,850 --> 00:29:03,080
para um nó de árvore binária contendo valores int -

381
00:29:03,080 --> 00:29:07,110
assim como os valores que tirou em nossa diagramação antes.

382
00:29:07,110 --> 00:29:11,740
Nós vamos usar esse clichê typedef que fizemos aqui

383
00:29:11,740 --> 00:29:14,420
que você deve reconhecer de Conjunto de Problemas 5 -

384
00:29:14,420 --> 00:29:19,190
se você fez o caminho tabela hash do programa conquistando o speller.

385
00:29:19,190 --> 00:29:22,540
Você também deve reconhecê-lo da seção da semana passada

386
00:29:22,540 --> 00:29:23,890
onde falamos sobre listas ligadas.

387
00:29:23,890 --> 00:29:27,870
Temos este typedef de um nó de estrutura,

388
00:29:27,870 --> 00:29:34,430
e demos a este nó struct este nome de nó struct previamente

389
00:29:34,430 --> 00:29:39,350
para que possamos, em seguida se referem a ele, uma vez que vai querer ter ponteiros nó struct

390
00:29:39,350 --> 00:29:45,740
como parte de nossa estrutura, mas nós então cercaram isso -

391
00:29:45,740 --> 00:29:47,700
ou antes, esta fechada - em um typedef

392
00:29:47,700 --> 00:29:54,600
de modo que, no final do código, que pode se referir a essa estrutura como apenas um nó em vez de um nó de estrutura.

393
00:29:54,600 --> 00:30:03,120
>> Isso vai ser muito semelhante à definição de lista individualmente-vinculado que vimos na semana passada.

394
00:30:03,120 --> 00:30:20,070
Para fazer isso, vamos começar por escrever o clichê.

395
00:30:20,070 --> 00:30:23,840
Nós sabemos que temos que ter um valor inteiro,

396
00:30:23,840 --> 00:30:32,170
então vamos pôr em valor int, e depois, em vez de ter apenas um ponteiro para o próximo elemento -

397
00:30:32,170 --> 00:30:33,970
como fizemos com isoladamente ligados listas -

398
00:30:33,970 --> 00:30:38,110
vamos ter ponteiros criança esquerdo e direito.

399
00:30:38,110 --> 00:30:42,880
Isso é muito simples também - struct filho do nó * esquerda;

400
00:30:42,880 --> 00:30:51,190
e struct nó filho direito *;. Cool.

401
00:30:51,190 --> 00:30:54,740
Isso parece um bom começo.

402
00:30:54,740 --> 00:30:58,530
Vamos voltar com a especificação.

403
00:30:58,530 --> 00:31:05,030
>> Agora precisamos declarar uma variável * mundial nó para a raiz de uma árvore.

404
00:31:05,030 --> 00:31:10,590
Nós vamos fazer este global como fizemos ponteiro primeiro em nossa lista ligada também global.

405
00:31:10,590 --> 00:31:12,690
Este foi, de modo que nas funções que escrevem

406
00:31:12,690 --> 00:31:16,180
não temos de manter esta passando em torno de raiz -

407
00:31:16,180 --> 00:31:19,620
mas vamos ver que se você quer escrever estas funções de forma recursiva,

408
00:31:19,620 --> 00:31:22,830
talvez seja melhor não mesmo passá-lo em torno de como uma empresa global, em primeiro lugar

409
00:31:22,830 --> 00:31:28,090
e, em vez inicializá-lo localmente na sua função principal.

410
00:31:28,090 --> 00:31:31,960
Mas, vamos fazê-lo globalmente para começar.

411
00:31:31,960 --> 00:31:39,920
Mais uma vez, vamos dar um par de espaços, e eu vou declarar uma raiz * nó.

412
00:31:39,920 --> 00:31:46,770
Só para ter certeza que eu não deixe este não inicializado, eu estou indo para defini-la igual a null.

413
00:31:46,770 --> 00:31:52,210
Agora, na função principal - o que vamos escrever muito rapidamente aqui -

414
00:31:52,210 --> 00:32:00,450
int main (int argc, const char * argv []) -

415
00:32:00,450 --> 00:32:10,640
e eu vou começar declarando minha matriz argv como const só assim que eu sei

416
00:32:10,640 --> 00:32:14,550
que esses argumentos são argumentos que eu provavelmente não querem modificar.

417
00:32:14,550 --> 00:32:18,390
Se eu quiser modificá-los eu provavelmente deveria estar fazendo cópias deles.

418
00:32:18,390 --> 00:32:21,740
Você vai ver muito isso no código.

419
00:32:21,740 --> 00:32:25,440
É bom de qualquer maneira. É bom deixá-lo como - omitir a const se você gostaria.

420
00:32:25,440 --> 00:32:28,630
Eu normalmente colocá-lo em apenas para que eu me lembrar

421
00:32:28,630 --> 00:32:33,650
 que eu provavelmente não querem modificar esses argumentos.

422
00:32:33,650 --> 00:32:39,240
>> Como sempre, eu estou indo para incluir este retorno 0 no final do principal.

423
00:32:39,240 --> 00:32:45,730
Aqui, vou iniciar o meu nó de raiz.

424
00:32:45,730 --> 00:32:48,900
Tal como está agora, eu tenho um ponteiro que está definido como nulo,

425
00:32:48,900 --> 00:32:52,970
por isso está apontando para o nada.

426
00:32:52,970 --> 00:32:57,480
A fim de realmente começar a construir o nó,

427
00:32:57,480 --> 00:32:59,250
Eu primeiro preciso alocar memória para ele.

428
00:32:59,250 --> 00:33:05,910
Eu vou fazer isso, fazendo memória na pilha usando malloc.

429
00:33:05,910 --> 00:33:10,660
Eu estou indo para definir raiz igual ao resultado de malloc,

430
00:33:10,660 --> 00:33:19,550
e eu vou usar o operador sizeof para calcular o tamanho de um nó.

431
00:33:19,550 --> 00:33:24,990
A razão que eu uso nó sizeof ao contrário de, digamos,

432
00:33:24,990 --> 00:33:37,020
fazer algo assim - malloc (4 + 4 +4) ou malloc 12 -

433
00:33:37,020 --> 00:33:40,820
é porque eu quero o meu código para ser o mais compatível possível.

434
00:33:40,820 --> 00:33:44,540
Eu quero ser capaz de tomar isso. Arquivo c, compilá-lo no aparelho,

435
00:33:44,540 --> 00:33:48,820
e depois compilá-lo no meu 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
ou sobre uma arquitectura completamente diferente -

437
00:33:52,040 --> 00:33:54,640
e eu quero isso tudo para o mesmo trabalho.

438
00:33:54,640 --> 00:33:59,510
>> Se eu estou fazendo suposições sobre o tamanho de variáveis ​​-

439
00:33:59,510 --> 00:34:02,070
o tamanho de um int ou o tamanho de um ponteiro -

440
00:34:02,070 --> 00:34:06,070
então eu também estou fazendo suposições sobre os tipos de arquiteturas

441
00:34:06,070 --> 00:34:10,440
em que o meu código pode compilar com êxito quando for executado.

442
00:34:10,440 --> 00:34:15,030
Sempre use sizeof ao contrário manualmente soma dos campos de estruturas.

443
00:34:15,030 --> 00:34:20,500
A outra razão é que também pode haver preenchimento que o compilador coloca na estrutura.

444
00:34:20,500 --> 00:34:26,570
Mesmo apenas somar os campos individuais não é algo que você normalmente quer fazer,

445
00:34:26,570 --> 00:34:30,340
assim, apagar a linha.

446
00:34:30,340 --> 00:34:33,090
Agora, para realmente inicializar este nó raiz,

447
00:34:33,090 --> 00:34:36,489
Eu vou ter de ligar os valores para cada um dos seus diferentes campos.

448
00:34:36,489 --> 00:34:41,400
Por exemplo, para o valor que eu sei que eu quero para inicializar a 7,

449
00:34:41,400 --> 00:34:46,920
e agora eu estou indo para definir o filho esquerdo de ser nulo

450
00:34:46,920 --> 00:34:55,820
e do direito da criança a ser também nulo. Ótimo!

451
00:34:55,820 --> 00:35:02,670
Nós fizemos isso parte da especificação.

452
00:35:02,670 --> 00:35:07,390
>> A especificação para baixo na parte inferior da página 3 me pede para criar três mais nós -

453
00:35:07,390 --> 00:35:10,600
um contendo 3, um contendo 6, e um com 9 -

454
00:35:10,600 --> 00:35:14,210
e, em seguida, conectá-los de modo que parece exatamente como o nosso diagrama de árvore

455
00:35:14,210 --> 00:35:17,120
que estávamos falando anteriormente.

456
00:35:17,120 --> 00:35:20,450
Vamos fazer isso bem rápido aqui.

457
00:35:20,450 --> 00:35:26,270
Você vai ver muito rapidamente que eu vou começar a escrever um monte de código duplicado.

458
00:35:26,270 --> 00:35:32,100
Eu estou indo para criar um nó * e eu vou chamá-lo de três.

459
00:35:32,100 --> 00:35:36,000
Eu estou indo para defini-la igual a malloc (sizeof (nó)).

460
00:35:36,000 --> 00:35:41,070
Eu estou indo para definir três-> valor = 3.

461
00:35:41,070 --> 00:35:54,780
Três -> left_child = NULL; três -> direito _child = NULL; também.

462
00:35:54,780 --> 00:36:01,150
Isso parece bastante semelhante ao inicializar a raiz, e isso é exatamente o que

463
00:36:01,150 --> 00:36:05,760
Eu vou ter que fazer se eu começar a inicializar 6 e 9 também.

464
00:36:05,760 --> 00:36:20,720
Eu vou fazer isso muito rapidamente aqui - na verdade, eu vou fazer uma cópia pouco e colar,

465
00:36:20,720 --> 00:36:46,140
e certifique-se de que eu - tudo bem.

466
00:36:46,470 --> 00:37:09,900
 Agora, eu tenho que copiar e eu posso ir em frente e definir esta igual a 6.

467
00:37:09,900 --> 00:37:14,670
Você pode ver que isso leva algum tempo e não é super-eficiente.

468
00:37:14,670 --> 00:37:22,610
Em apenas um pouco, vamos escrever uma função que vai fazer isso por nós.

469
00:37:22,610 --> 00:37:32,890
Quero substituir isso com um 9, substitua que, com um 6.

470
00:37:32,890 --> 00:37:37,360
>> Agora temos todos os nossos nós criado e inicializado.

471
00:37:37,360 --> 00:37:41,200
Temos nossa raiz definido igual a 7, ou que contém o valor 7,

472
00:37:41,200 --> 00:37:46,510
nossa nó contendo 3, nosso nó que contém 6, e contendo o nó 9.

473
00:37:46,510 --> 00:37:50,390
Neste ponto, tudo o que temos a fazer é tudo o fio para cima.

474
00:37:50,390 --> 00:37:53,020
A razão de eu inicializado todos os ponteiros como nulo é apenas para que eu ter certeza de que

475
00:37:53,020 --> 00:37:56,260
Eu não tenho os ponteiros não inicializados lá por acidente.

476
00:37:56,260 --> 00:38:02,290
E também porque, neste momento, eu só tenho que realmente conectar os nós para o outro -

477
00:38:02,290 --> 00:38:04,750
para os que estão realmente ligadas a - Eu não tenho que passar e fazer

478
00:38:04,750 --> 00:38:08,240
certeza de que todos os nulos estão lá nos lugares apropriados.

479
00:38:08,240 --> 00:38:15,630
>> A partir da raiz, eu sei que filho esquerdo da raiz é 3.

480
00:38:15,630 --> 00:38:21,250
Eu sei que filho direito da raiz é 9.

481
00:38:21,250 --> 00:38:24,880
Depois disso, o filho único outro que me resta para se preocupar

482
00:38:24,880 --> 00:38:39,080
É direito da criança 3, que é 6.

483
00:38:39,080 --> 00:38:44,670
Neste ponto, tudo parece muito bom.

484
00:38:44,670 --> 00:38:54,210
Nós vamos excluir algumas dessas linhas.

485
00:38:54,210 --> 00:38:59,540
Agora tudo parece muito bom.

486
00:38:59,540 --> 00:39:04,240
Vamos voltar para a nossa especificação e ver o que nós temos que fazer a seguir.

487
00:39:04,240 --> 00:39:07,610
>> Neste ponto, temos de escrever uma função chamada "contém"

488
00:39:07,610 --> 00:39:14,150
com um protótipo de 'contém bool (valor inteiro).

489
00:39:14,150 --> 00:39:17,060
E este contém função vai retornar true

490
00:39:17,060 --> 00:39:21,200
 se a árvore apontada por nossa variável raiz global

491
00:39:21,200 --> 00:39:26,950
 contém o valor passado para a função e falso caso contrário.

492
00:39:26,950 --> 00:39:29,000
Vamos em frente e fazer isso.

493
00:39:29,000 --> 00:39:35,380
Este vai ser exatamente como a pesquisa que fizemos com a mão no iPad um pouco atrás.

494
00:39:35,380 --> 00:39:40,130
Vamos zoom em um pouco e vá para cima.

495
00:39:40,130 --> 00:39:43,130
Nós vamos colocar esta função logo acima a nossa função principal

496
00:39:43,130 --> 00:39:48,990
de modo que não temos que fazer qualquer tipo de prototipagem.

497
00:39:48,990 --> 00:39:55,960
Então, bool contém (valor inteiro).

498
00:39:55,960 --> 00:40:00,330
Lá vamos nós. Não é a nossa declaração clichê.

499
00:40:00,330 --> 00:40:02,900
Só para ter certeza que isso vai compilar,

500
00:40:02,900 --> 00:40:06,820
Eu estou indo para ir em frente e configurá-lo igual a retornar falso.

501
00:40:06,820 --> 00:40:09,980
Neste momento esta função só não vai fazer nada e sempre relatam que

502
00:40:09,980 --> 00:40:14,010
o valor que estamos procurando não está na árvore.

503
00:40:14,010 --> 00:40:16,280
>> Neste ponto, é provavelmente uma boa idéia -

504
00:40:16,280 --> 00:40:19,600
desde que escrevi um monte de código e não temos sequer tentou testá-lo ainda -

505
00:40:19,600 --> 00:40:22,590
para se certificar de que tudo compila.

506
00:40:22,590 --> 00:40:27,460
Há um par de coisas que temos que fazer para ter certeza de que isso realmente vai compilar.

507
00:40:27,460 --> 00:40:33,530
Primeiro, veja se estamos usando todas as funções em qualquer biblioteca que ainda não foram incluídas.

508
00:40:33,530 --> 00:40:37,940
As funções que usamos até agora são malloc,

509
00:40:37,940 --> 00:40:43,310
e então nós também vindo a utilizar este tipo - este tipo fora do padrão chamado 'bool' -

510
00:40:43,310 --> 00:40:45,750
que está incluído no arquivo de cabeçalho padrão bool.

511
00:40:45,750 --> 00:40:53,250
Nós definitivamente queremos incluir bool.h padrão para o tipo bool,

512
00:40:53,250 --> 00:40:59,230
e nós também queremos # include lib.h padrão para as bibliotecas padrão

513
00:40:59,230 --> 00:41:03,530
que incluem malloc, e livre, e tudo isso.

514
00:41:03,530 --> 00:41:08,660
Então, zoom out, vamos parar de fumar.

515
00:41:08,660 --> 00:41:14,190
Vamos tentar e ter certeza de que isso realmente fez a compilação.

516
00:41:14,190 --> 00:41:18,150
Vemos que ele faz, então estamos no caminho certo.

517
00:41:18,150 --> 00:41:22,990
>> Vamos abrir binary_tree.c novamente.

518
00:41:22,990 --> 00:41:34,530
Ele compila. Vamos descer e ter certeza de que vamos inserir algumas chamadas para nossa função contém -

519
00:41:34,530 --> 00:41:40,130
só para ter certeza que isso é tudo muito bem.

520
00:41:40,130 --> 00:41:43,170
Por exemplo, quando fizemos algumas pesquisas em nossa árvore mais cedo,

521
00:41:43,170 --> 00:41:48,500
tentamos procurar os 6 valores em 10, e 1, e nós sabíamos que era 6 na árvore,

522
00:41:48,500 --> 00:41:52,220
10 não estava na árvore, e 1 não estava na árvore ou.

523
00:41:52,220 --> 00:41:57,230
Vamos usar as chamadas de amostras, como forma de descobrir se ou não

524
00:41:57,230 --> 00:41:59,880
nossa função contém está funcionando.

525
00:41:59,880 --> 00:42:05,210
A fim de fazer isso, eu vou usar a função printf,

526
00:42:05,210 --> 00:42:10,280
e nós estamos indo para imprimir o resultado da chamada para contém.

527
00:42:10,280 --> 00:42:13,280
Eu vou colocar em uma string "contém (% d) = porque

528
00:42:13,280 --> 00:42:20,470
 vamos ligar o valor que vamos procurar,

529
00:42:20,470 --> 00:42:27,130
e =% s \ n "e usar isso como nossa seqüência de formato.

530
00:42:27,130 --> 00:42:30,720
Nós só vamos ver - literalmente imprimir na tela -

531
00:42:30,720 --> 00:42:32,060
o que parece ser uma chamada de função.

532
00:42:32,060 --> 00:42:33,580
Isto não é realmente a chamada de função.

533
00:42:33,580 --> 00:42:36,760
 Esta é apenas uma seqüência projetado para parecer com uma chamada de função.

534
00:42:36,760 --> 00:42:41,140
>> Agora, vamos ligar os valores.

535
00:42:41,140 --> 00:42:43,580
Nós vamos tentar contém em 6,

536
00:42:43,580 --> 00:42:48,340
e então o que vamos fazer aqui é usar o operador ternário.

537
00:42:48,340 --> 00:42:56,340
Vamos ver - contém 6 - assim, agora eu continha 6 e se contém 6 é verdadeira,

538
00:42:56,340 --> 00:43:01,850
a string que vamos enviar para o caráter de formato% s

539
00:43:01,850 --> 00:43:04,850
vai ser a string "true".

540
00:43:04,850 --> 00:43:07,690
Vamos rolar mais um pouco.

541
00:43:07,690 --> 00:43:16,210
Caso contrário, queremos enviar a string "false" se contém seis retornos falsos.

542
00:43:16,210 --> 00:43:19,730
Isto é um pouco pateta bonito, mas eu acho que eu poderia muito bem ilustrar

543
00:43:19,730 --> 00:43:23,780
o que o operador ternário parece, uma vez que não vi ele por algum tempo.

544
00:43:23,780 --> 00:43:27,670
Esta será uma forma agradável, útil para descobrir se a nossa função contém está funcionando.

545
00:43:27,670 --> 00:43:30,040
Eu estou indo para rolar de volta para a esquerda,

546
00:43:30,040 --> 00:43:39,900
e eu vou copiar e colar essa linha algumas vezes.

547
00:43:39,900 --> 00:43:44,910
Ele mudou alguns desses valores ao redor,

548
00:43:44,910 --> 00:43:59,380
por isso este vai ser um, e isso vai ser 10.

549
00:43:59,380 --> 00:44:02,480
>> Neste ponto, temos uma função contém agradável.

550
00:44:02,480 --> 00:44:06,080
Nós temos alguns testes, e vamos ver se esta tudo funciona.

551
00:44:06,080 --> 00:44:08,120
Neste ponto, tenho escrito alguns códigos mais.

552
00:44:08,120 --> 00:44:13,160
Tempo para sair fora e certifique-se de que tudo ainda compila.

553
00:44:13,160 --> 00:44:20,360
Saia fora, e agora vamos tentar fazer árvore binária novamente.

554
00:44:20,360 --> 00:44:22,260
Bem, parece que temos um erro,

555
00:44:22,260 --> 00:44:26,930
E nós temos esta declarar explicitamente a função de biblioteca printf.

556
00:44:26,930 --> 00:44:39,350
Parece que temos que ir e # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
E, com isso, tudo deve compilar. Estamos todos bem.

558
00:44:45,350 --> 00:44:50,420
Agora vamos tentar correr árvore binária e ver o que acontece.

559
00:44:50,420 --> 00:44:53,520
Aqui estamos nós,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
e vemos que, como se esperava -

561
00:44:55,190 --> 00:44:56,910
porque não têm implementado contém ainda,

562
00:44:56,910 --> 00:44:59,800
ou melhor, acabamos de colocar no return false -

563
00:44:59,800 --> 00:45:03,300
vemos que ele está apenas retornando falso para todos eles,

564
00:45:03,300 --> 00:45:06,180
Então isso é tudo trabalho para a maior parte bastante bem.

565
00:45:06,180 --> 00:45:11,860
>> Vamos voltar e realmente implementar contém neste momento.

566
00:45:11,860 --> 00:45:17,490
Eu estou indo para rolar para baixo, aumentar o zoom, e -

567
00:45:17,490 --> 00:45:22,330
lembre-se, o algoritmo que usamos foi que começou no nó raiz

568
00:45:22,330 --> 00:45:28,010
e em cada nó que encontramos, fazemos uma comparação,

569
00:45:28,010 --> 00:45:32,380
e com base em que a comparação que quer passar para o filho esquerdo ou direito para a criança.

570
00:45:32,380 --> 00:45:39,670
Isso vai parecer muito semelhante ao código de busca binária que escrevemos no início do prazo.

571
00:45:39,670 --> 00:45:47,810
Quando começamos, nós sabemos que queremos segurar o nó atual

572
00:45:47,810 --> 00:45:54,050
que estamos olhando, eo nó atual vai ser inicializado para o nó raiz.

573
00:45:54,050 --> 00:45:56,260
E agora, vamos continuar com a árvore,

574
00:45:56,260 --> 00:45:58,140
e lembre-se que a nossa condição de parar -

575
00:45:58,140 --> 00:46:01,870
 quando efectivamente trabalhadas através do exemplo à mão -

576
00:46:01,870 --> 00:46:03,960
foi quando encontrou um nó nulo,

577
00:46:03,960 --> 00:46:05,480
não quando olhamos para uma criança nulo,

578
00:46:05,480 --> 00:46:09,620
mas quando nós realmente mudou-se para um nó na árvore

579
00:46:09,620 --> 00:46:12,640
e descobriu que estamos em um nó nulo.

580
00:46:12,640 --> 00:46:20,720
Nós estamos indo para iterar até atu não é igual a nulo.

581
00:46:20,720 --> 00:46:22,920
E o que é que vamos fazer?

582
00:46:22,920 --> 00:46:31,610
Nós vamos testar se (cur -> valor valor ==),

583
00:46:31,610 --> 00:46:35,160
então sabemos que temos na verdade, o nó que estamos procurando.

584
00:46:35,160 --> 00:46:40,450
Então, aqui, nós podemos retornar true.

585
00:46:40,450 --> 00:46:49,830
Caso contrário, queremos para ver se ou não o valor é menor que o valor.

586
00:46:49,830 --> 00:46:53,850
Se o valor do nó atual é menor do que o valor que está procurando,

587
00:46:53,850 --> 00:46:57,280
vamos passar para a direita.

588
00:46:57,280 --> 00:47:10,600
Então, cur = atual -> right_child, e caso contrário, nós estamos indo para mover para a esquerda.

589
00:47:10,600 --> 00:47:17,480
atu atu = -> left_child;. Muito simples.

590
00:47:17,480 --> 00:47:22,830
>> Você provavelmente reconhece o laço que se parece muito semelhante a este de

591
00:47:22,830 --> 00:47:27,580
busca binária no início do prazo, exceto em seguida estávamos lidando com baixa, média e alta.

592
00:47:27,580 --> 00:47:30,000
Aqui, só temos de olhar para um valor atual,

593
00:47:30,000 --> 00:47:31,930
por isso é bom e simples.

594
00:47:31,930 --> 00:47:34,960
Vamos ter certeza que esse código está funcionando.

595
00:47:34,960 --> 00:47:42,780
Primeiro, certifique-se que compila. Parece que ele faz.

596
00:47:42,780 --> 00:47:47,920
Vamos tentar executá-lo.

597
00:47:47,920 --> 00:47:50,160
E, de fato, ela mostra tudo o que esperávamos.

598
00:47:50,160 --> 00:47:54,320
Ele encontra 6 na árvore, não encontra 10, porque 10 não está na árvore,

599
00:47:54,320 --> 00:47:57,740
e não se encontrar uma ou porque não é uma também na árvore.

600
00:47:57,740 --> 00:48:01,420
Coisas legais.

601
00:48:01,420 --> 00:48:04,470
>> Tudo bem. Vamos voltar para a nossa especificação e ver o que está próximo.

602
00:48:04,470 --> 00:48:07,990
Agora, ele quer adicionar nós mais alguns para a nossa árvore.

603
00:48:07,990 --> 00:48:11,690
Ele quer adicionar 5, 2 e 8, e certifique-se de que a nossa contém código

604
00:48:11,690 --> 00:48:13,570
ainda funciona como o esperado.

605
00:48:13,570 --> 00:48:14,900
Vamos fazer isso.

606
00:48:14,900 --> 00:48:19,430
Neste ponto, ao invés de fazer a cópia irritante e colar novamente,

607
00:48:19,430 --> 00:48:23,770
vamos escrever uma função para realmente criar um nó.

608
00:48:23,770 --> 00:48:27,740
Se rolar todo o caminho para o principal, vemos que temos vindo a fazer esta

609
00:48:27,740 --> 00:48:31,210
código muito semelhante e outra vez cada vez que queremos criar um nó.

610
00:48:31,210 --> 00:48:39,540
>> Vamos escrever uma função que realmente construir um nó para nós e para devolvê-lo.

611
00:48:39,540 --> 00:48:41,960
Eu vou chamá-lo build_node.

612
00:48:41,960 --> 00:48:45,130
Eu vou construir um nó com um valor específico.

613
00:48:45,130 --> 00:48:51,040
Zoom aqui.

614
00:48:51,040 --> 00:48:56,600
A primeira coisa que vou fazer é, na verdade, criar espaço para o nó na pilha.

615
00:48:56,600 --> 00:49:05,400
Assim, o nó * n = malloc (sizeof (nó)); n - valor> = valor;

616
00:49:05,400 --> 00:49:14,960
e depois aqui, eu estou indo só para inicializar todos os campos para valores apropriados.

617
00:49:14,960 --> 00:49:22,500
E no final, vamos voltar nossa nó.

618
00:49:22,500 --> 00:49:28,690
Tudo bem. Uma coisa a notar é que esta função aqui

619
00:49:28,690 --> 00:49:34,320
vai retornar um ponteiro para a memória que foi alocada montão.

620
00:49:34,320 --> 00:49:38,880
O que é legal sobre isso é que este nó agora -

621
00:49:38,880 --> 00:49:42,420
temos que declará-lo na pilha porque, se declarou na pilha

622
00:49:42,420 --> 00:49:45,050
não seria capaz de fazê-lo nesta função como esta.

623
00:49:45,050 --> 00:49:47,690
Que a memória iria fora do escopo

624
00:49:47,690 --> 00:49:51,590
e seria inválido se tentamos acessá-lo mais tarde.

625
00:49:51,590 --> 00:49:53,500
Uma vez que estamos declarando pilha alocada de memória,

626
00:49:53,500 --> 00:49:55,830
vamos ter que cuidar de libertar-lo mais tarde

627
00:49:55,830 --> 00:49:58,530
para o nosso programa para não vazar qualquer memória.

628
00:49:58,530 --> 00:50:01,270
Fomos punting em que para qualquer outra coisa no código

629
00:50:01,270 --> 00:50:02,880
apenas por causa da simplicidade na época,

630
00:50:02,880 --> 00:50:05,610
mas se você já escrever uma função parecida com esta

631
00:50:05,610 --> 00:50:10,370
onde você tem - alguns chamam de um malloc ou realloc dentro -

632
00:50:10,370 --> 00:50:14,330
você quer ter certeza de que você colocar algum tipo de comentário por aqui que diz:

633
00:50:14,330 --> 00:50:29,970
ei, você sabe, retorna um nó pilha alocada inicializado com o valor passado-in.

634
00:50:29,970 --> 00:50:33,600
E então você quer ter certeza de que você colocar em algum tipo de nota que diz

635
00:50:33,600 --> 00:50:41,720
o chamador deve liberar a memória voltou.

636
00:50:41,720 --> 00:50:45,450
Dessa forma, se alguém nunca vai e usa essa função,

637
00:50:45,450 --> 00:50:48,150
eles sabem que o que recebem de volta do que a função

638
00:50:48,150 --> 00:50:50,870
em algum ponto terá de ser libertado.

639
00:50:50,870 --> 00:50:53,940
>> Assumindo que tudo está bem e bom aqui,

640
00:50:53,940 --> 00:51:02,300
podemos ir para baixo em nosso código e substituir todas estas linhas aqui

641
00:51:02,300 --> 00:51:05,410
com chamadas para nossa função nó de construção.

642
00:51:05,410 --> 00:51:08,170
Vamos fazer isso muito rapidamente.

643
00:51:08,170 --> 00:51:15,840
A única parte que não estamos indo para substituir é essa parte aqui

644
00:51:15,840 --> 00:51:18,520
na parte inferior onde realmente conectar os nós para apontar para o outro,

645
00:51:18,520 --> 00:51:21,030
porque que não podemos fazer em nossa função.

646
00:51:21,030 --> 00:51:37,400
Mas, vamos fazer raiz = build_node (7); nó * três = build_node (3);

647
00:51:37,400 --> 00:51:47,980
nó * seis = build_node (6); nó * nove = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
E agora, nós também queria adicionar nós para -

649
00:51:52,590 --> 00:52:03,530
nó * cinco = build_node (5); nó * oito = build_node (8);

650
00:52:03,530 --> 00:52:09,760
e qual foi o outro nó? Vamos ver aqui. Queríamos também adicionar um 2 -

651
00:52:09,760 --> 00:52:20,280
nó * dois = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Tudo bem. Neste ponto, sabemos que temos o 7, o 3, o 9, e os 6

653
00:52:26,850 --> 00:52:30,320
todo ligado de forma adequada, mas que sobre o 5, o 8, eo 2?

654
00:52:30,320 --> 00:52:33,550
Para manter tudo em ordem apropriada,

655
00:52:33,550 --> 00:52:39,230
sabemos que criança direita três é 6.

656
00:52:39,230 --> 00:52:40,890
Então, se nós vamos adicionar a 5,

657
00:52:40,890 --> 00:52:46,670
a 5 também pertence ao lado direito da árvore dos quais 3 é a raiz,

658
00:52:46,670 --> 00:52:50,440
assim como 5 pertence a criança esquerda de 6.

659
00:52:50,440 --> 00:52:58,650
Nós podemos fazer isto por dizer, seis -> left_child = cinco;

660
00:52:58,650 --> 00:53:10,790
e, em seguida, a 8 pertence como o filho esquerdo de 9, de modo nove -> left_child = oito;

661
00:53:10,790 --> 00:53:22,190
e 2 é o filho esquerdo de três, para que possamos fazer isso aqui - te -> left_child = dois;.

662
00:53:22,190 --> 00:53:27,730
Se você não chegou a acompanhar, juntamente com isso, eu sugiro que você retirá-la sozinho.

663
00:53:27,730 --> 00:53:35,660
>> Tudo bem. Vamos salvar este. Vamos sair e se certificar de que compila,

664
00:53:35,660 --> 00:53:40,760
e então nós podemos adicionar em nossas chamadas contém.

665
00:53:40,760 --> 00:53:44,120
Parece que tudo ainda compila.

666
00:53:44,120 --> 00:53:51,790
Vamos entrar e adicionar em algumas contém chamadas.

667
00:53:51,790 --> 00:53:59,640
Mais uma vez, eu vou fazer um pouco de copiar e colar.

668
00:53:59,640 --> 00:54:15,860
Agora vamos procurar 5, 8 e 2. Tudo bem.

669
00:54:15,860 --> 00:54:28,330
Vamos ter certeza de que tudo isso parece ser bom ainda. Ótimo! Salvar e sair.

670
00:54:28,330 --> 00:54:33,220
Agora vamos fazer, compilar, e agora vamos executar.

671
00:54:33,220 --> 00:54:37,540
A partir dos resultados, parece que tudo está funcionando muito agradável e bem.

672
00:54:37,540 --> 00:54:41,780
Ótimo! Então, agora nós temos nossos contém função escrito.

673
00:54:41,780 --> 00:54:46,160
Vamos seguir em frente e começar a trabalhar em como inserir nós na árvore

674
00:54:46,160 --> 00:54:50,000
uma vez que, como estamos fazendo agora, as coisas não são muito bonitas.

675
00:54:50,000 --> 00:54:52,280
>> Se voltarmos para a especificação,

676
00:54:52,280 --> 00:55:00,540
que nos pede para escrever uma função chamada inserir - novamente, retornando um bool

677
00:55:00,540 --> 00:55:04,400
para se ou não poderíamos inserir o nó na árvore -

678
00:55:04,400 --> 00:55:07,710
e, em seguida, o valor para inserir na árvore é especificado como

679
00:55:07,710 --> 00:55:11,060
o único argumento para a nossa função de inserção.

680
00:55:11,060 --> 00:55:18,180
Voltaremos verdade se poderia de fato inserir o valor do nó contendo na árvore,

681
00:55:18,180 --> 00:55:20,930
o que significa que, um, tinha memória suficiente,

682
00:55:20,930 --> 00:55:24,840
e dois, que o nó já não existe na árvore desde então -

683
00:55:24,840 --> 00:55:32,170
Lembre-se, nós não vamos ter valores duplicados na árvore, só para fazer as coisas simples.

684
00:55:32,170 --> 00:55:35,590
Tudo bem. De volta para o código.

685
00:55:35,590 --> 00:55:44,240
Abra-se. Zoom em um pouco, em seguida, vá para baixo.

686
00:55:44,240 --> 00:55:47,220
Vamos colocar a função de inserção logo acima os contém.

687
00:55:47,220 --> 00:55:56,360
Mais uma vez, ele vai ser chamado de inserção bool (valor inteiro).

688
00:55:56,360 --> 00:56:01,840
Dê-lhe um pouco mais espaço, e então, como um padrão,

689
00:56:01,840 --> 00:56:08,870
vamos colocar em return false no final.

690
00:56:08,870 --> 00:56:22,620
Agora, na parte inferior, vamos em frente e em vez de construir manualmente os nós

691
00:56:22,620 --> 00:56:27,900
na principal nós mesmos e fiação-los para apontar para o outro como nós estamos fazendo,

692
00:56:27,900 --> 00:56:30,600
vamos confiar na nossa função de inserção para fazer isso.

693
00:56:30,600 --> 00:56:35,510
Nós não vamos contar com nossa função de inserção para construir a árvore inteira a partir do zero ainda,

694
00:56:35,510 --> 00:56:39,970
mas nós vamos nos livrar dessas linhas - vamos comentar as linhas -

695
00:56:39,970 --> 00:56:43,430
que construir os 5 nós, 8 e 2.

696
00:56:43,430 --> 00:56:55,740
E em vez disso, vamos inserir chamadas para nossa função de inserção

697
00:56:55,740 --> 00:57:01,280
para ter certeza de que isso realmente funciona.

698
00:57:01,280 --> 00:57:05,840
Aqui vamos nós.

699
00:57:05,840 --> 00:57:09,300
>> Agora que já comentou estas linhas.

700
00:57:09,300 --> 00:57:13,700
Nós só temos 7, 3, 9 e 6 em nossa árvore neste momento.

701
00:57:13,700 --> 00:57:18,870
Para se certificar de que tudo está funcionando,

702
00:57:18,870 --> 00:57:25,050
podemos diminuir o zoom, fazer a nossa árvore binária,

703
00:57:25,050 --> 00:57:30,750
executá-lo, e podemos ver que contém agora está nos dizendo que está totalmente certo -

704
00:57:30,750 --> 00:57:33,110
5, 8, e 2 já não se na árvore.

705
00:57:33,110 --> 00:57:37,960
Volte para o código,

706
00:57:37,960 --> 00:57:41,070
e como é que vamos inserir?

707
00:57:41,070 --> 00:57:46,290
Lembre-se o que fizemos quando estávamos realmente a inserção de 5, 8 e 2 anteriormente.

708
00:57:46,290 --> 00:57:50,100
Nós jogamos esse jogo Plinko onde começamos na raiz,

709
00:57:50,100 --> 00:57:52,780
desceu a uma árvore por um por um

710
00:57:52,780 --> 00:57:54,980
até encontrarmos a brecha adequado,

711
00:57:54,980 --> 00:57:57,570
e, então, com fio no nó no local apropriado.

712
00:57:57,570 --> 00:57:59,480
Nós vamos fazer a mesma coisa.

713
00:57:59,480 --> 00:58:04,070
Isto é basicamente como escrever o código que usamos no contém função

714
00:58:04,070 --> 00:58:05,910
para encontrar o local onde o nó deve ser,

715
00:58:05,910 --> 00:58:10,560
e então nós apenas estamos indo para inserir o nó ali mesmo.

716
00:58:10,560 --> 00:58:17,000
Vamos começar a fazer isso.

717
00:58:17,000 --> 00:58:24,200
>> Portanto, temos um nó * cur = raiz; nós apenas estamos indo para acompanhar o contém código

718
00:58:24,200 --> 00:58:26,850
até descobrir que ele não funciona muito bem para nós.

719
00:58:26,850 --> 00:58:32,390
Nós vamos passar pela árvore, enquanto o elemento atual não é nulo,

720
00:58:32,390 --> 00:58:45,280
e se encontrar o valor que atu é igual ao valor que estamos tentando inserir -

721
00:58:45,280 --> 00:58:49,600
bem, este é um dos casos em que não poderia realmente inserir o nó

722
00:58:49,600 --> 00:58:52,730
para a árvore, porque isso significa que temos um valor duplicado.

723
00:58:52,730 --> 00:58:59,010
Aqui nós estamos indo realmente para retornar falso.

724
00:58:59,010 --> 00:59:08,440
Agora outra coisa, se o valor atu é menor do que o valor,

725
00:59:08,440 --> 00:59:10,930
agora sabemos que vamos passar para a direita

726
00:59:10,930 --> 00:59:17,190
 porque o valor pertence a metade direita da árvore cur.

727
00:59:17,190 --> 00:59:30,110
Caso contrário, nós estamos indo para mover para a esquerda.

728
00:59:30,110 --> 00:59:37,980
Isso é basicamente nossos contém função ali.

729
00:59:37,980 --> 00:59:41,820
>> Neste ponto, uma vez que tenhamos concluído esta loop while,

730
00:59:41,820 --> 00:59:47,350
nosso ponteiro atu vai estar apontando para null

731
00:59:47,350 --> 00:59:51,540
se a função não tenha retornado.

732
00:59:51,540 --> 00:59:58,710
Estamos, portanto, ter cur no local onde deseja inserir o novo nó.

733
00:59:58,710 --> 01:00:05,210
O que resta a ser feito é realmente construir o novo nó,

734
01:00:05,210 --> 01:00:08,480
o que podemos fazer muito facilmente.

735
01:00:08,480 --> 01:00:14,930
Podemos usar o nosso super-acessível função do nó de construção,

736
01:00:14,930 --> 01:00:17,210
e algo que não fizemos antes -

737
01:00:17,210 --> 01:00:21,400
que apenas um tipo de levou para concedido, mas agora vamos fazer só para ter certeza -

738
01:00:21,400 --> 01:00:27,130
vamos testar para ter certeza de que o valor retornado pelo novo nó foi realmente

739
01:00:27,130 --> 01:00:33,410
não nulo, porque nós não queremos começar a acessar a memória se ele é nulo.

740
01:00:33,410 --> 01:00:39,910
Nós podemos testar para ter certeza de que novo nó não é igual a nulo.

741
01:00:39,910 --> 01:00:42,910
Ou em vez disso, podemos apenas ver se ele realmente é nulo,

742
01:00:42,910 --> 01:00:52,120
e se é nulo, então podemos simplesmente retornar falso cedo.

743
01:00:52,120 --> 01:00:59,090
>> Neste ponto, é preciso ligar novo nó no seu local adequado na árvore.

744
01:00:59,090 --> 01:01:03,510
Se olharmos para trás, principal e onde estávamos realmente fiação em valores antes,

745
01:01:03,510 --> 01:01:08,470
vemos que a forma como nós estávamos fazendo isso quando queria colocar 3 na árvore

746
01:01:08,470 --> 01:01:11,750
foi acessamos o filho esquerdo de raiz.

747
01:01:11,750 --> 01:01:14,920
Quando colocamos nove na árvore, nós tivemos que acessar o filho direito da raiz.

748
01:01:14,920 --> 01:01:21,030
Tínhamos que ter um ponteiro para o pai, a fim de colocar um novo valor para a árvore.

749
01:01:21,030 --> 01:01:24,430
Rolando de volta para inserir, que não vai muito trabalhar aqui

750
01:01:24,430 --> 01:01:27,550
porque não temos um ponteiro pai.

751
01:01:27,550 --> 01:01:31,650
O que se quer ser capaz de fazer é, neste ponto,

752
01:01:31,650 --> 01:01:37,080
verificar o valor do pai e ver - bem, caramba,

753
01:01:37,080 --> 01:01:41,990
se o valor do pai é menor do que o valor atual,

754
01:01:41,990 --> 01:01:54,440
então a criança o direito dos pais deve ser o novo nó;

755
01:01:54,440 --> 01:02:07,280
caso contrário, filho esquerdo do pai deve ser o novo nó.

756
01:02:07,280 --> 01:02:10,290
Mas, não temos este ponteiro pai ainda.

757
01:02:10,290 --> 01:02:15,010
>> A fim de obtê-lo, nós vamos mesmo ter que segui-lo como nós atravessamos a árvore

758
01:02:15,010 --> 01:02:18,440
e encontrar o local apropriado no nosso loop acima.

759
01:02:18,440 --> 01:02:26,840
Podemos fazer isso por rolagem de volta até o topo da nossa função de inserção

760
01:02:26,840 --> 01:02:32,350
e acompanhamento de outra variável ponteiro chamado de pai.

761
01:02:32,350 --> 01:02:39,340
Nós vamos defini-lo igual a nulo, inicialmente,

762
01:02:39,340 --> 01:02:43,640
e então cada vez que passar pela árvore,

763
01:02:43,640 --> 01:02:51,540
vamos definir o ponteiro pai para coincidir com o ponteiro atual.

764
01:02:51,540 --> 01:02:59,140
Definir pai igual a cur.

765
01:02:59,140 --> 01:03:02,260
Desta forma, cada vez que passar,

766
01:03:02,260 --> 01:03:05,550
vamos garantir que, como o ponteiro atual é incrementado

767
01:03:05,550 --> 01:03:12,640
o ponteiro pai segue - apenas um nível mais elevado do que o ponteiro atual na árvore.

768
01:03:12,640 --> 01:03:17,370
Isso tudo parece muito bom.

769
01:03:17,370 --> 01:03:22,380
>> Eu acho que a única coisa que vamos querer ajustar é esta compilação nulo nó de retorno.

770
01:03:22,380 --> 01:03:25,380
A fim de obter construir nó realmente com sucesso retornar nulo,

771
01:03:25,380 --> 01:03:31,060
nós vamos ter que modificar esse código,

772
01:03:31,060 --> 01:03:37,270
porque aqui, nós nunca testados para garantir que malloc retornou um ponteiro válido.

773
01:03:37,270 --> 01:03:53,390
Assim, se (n = NULL!), Em seguida, -

774
01:03:53,390 --> 01:03:55,250
se malloc retornou um ponteiro válido, então vamos inicializá-lo;

775
01:03:55,250 --> 01:04:02,540
caso contrário, vamos retornar e que vai acabar retornando nulo para nós.

776
01:04:02,540 --> 01:04:13,050
Agora tudo parece muito bom. Vamos ter certeza que isso realmente compila.

777
01:04:13,050 --> 01:04:22,240
Fazer árvore binária, e oh, nós temos algumas coisas acontecendo aqui.

778
01:04:22,240 --> 01:04:29,230
>> Nós temos uma declaração implícita da função construir nó.

779
01:04:29,230 --> 01:04:31,950
Novamente, com estes compiladores, vamos começar no topo.

780
01:04:31,950 --> 01:04:36,380
O que tem de dizer é que eu estou chamando construir nó antes de eu realmente declarado.

781
01:04:36,380 --> 01:04:37,730
Vamos voltar ao código muito rapidamente.

782
01:04:37,730 --> 01:04:43,510
Rolar para baixo, e com certeza, a minha função de inserção é declarado

783
01:04:43,510 --> 01:04:47,400
acima da função do nó de construção,

784
01:04:47,400 --> 01:04:50,070
mas eu estou tentando usar construir nó dentro de inserção.

785
01:04:50,070 --> 01:05:06,610
Eu vou entrar e cópia - e depois cole o caminho de construção função do nó aqui no topo.

786
01:05:06,610 --> 01:05:11,750
Dessa forma, espero que funcione. Vamos dar este outro ir.

787
01:05:11,750 --> 01:05:18,920
Agora tudo compila. Tudo é bom.

788
01:05:18,920 --> 01:05:21,640
>> Mas neste momento, não temos realmente chamou a função de inserção.

789
01:05:21,640 --> 01:05:26,510
Nós só sabemos que ele compila, então vamos entrar e colocar algumas chamadas dentro

790
01:05:26,510 --> 01:05:28,240
Vamos fazer isso em nossa função principal.

791
01:05:28,240 --> 01:05:32,390
Aqui, nós comentada 5, 8 e 2,

792
01:05:32,390 --> 01:05:36,680
e, depois, não conectá-los aqui.

793
01:05:36,680 --> 01:05:41,640
Vamos fazer algumas chamadas para inserir,

794
01:05:41,640 --> 01:05:46,440
e vamos também usar o mesmo tipo de material que usamos

795
01:05:46,440 --> 01:05:52,810
quando fizemos essas chamadas printf para ter certeza de que tudo que se inserir corretamente.

796
01:05:52,810 --> 01:06:00,550
Vou copiar e colar,

797
01:06:00,550 --> 01:06:12,450
e em vez de contém vamos fazer de inserção.

798
01:06:12,450 --> 01:06:30,140
E, em vez de 6, 10 e 1, vamos usar 5, 8 e 2.

799
01:06:30,140 --> 01:06:37,320
Isto deve esperançosamente inserir 5, 8, e dois para a árvore.

800
01:06:37,320 --> 01:06:44,050
Compilar. Tudo é bom. Agora vamos rodar o nosso programa.

801
01:06:44,050 --> 01:06:47,330
>> Tudo voltou falso.

802
01:06:47,330 --> 01:06:53,830
Então, 5, 8 e 2 não foi, e parece que contém não achou nenhuma delas.

803
01:06:53,830 --> 01:06:58,890
O que está acontecendo? Vamos diminuir o zoom.

804
01:06:58,890 --> 01:07:02,160
O primeiro problema foi que inserir parecia retornar falso,

805
01:07:02,160 --> 01:07:08,750
e parece que isso é porque saímos na nossa chamada de retorno falso,

806
01:07:08,750 --> 01:07:14,590
e nós nunca realmente retornou verdadeiro.

807
01:07:14,590 --> 01:07:17,880
Podemos configurar isso.

808
01:07:17,880 --> 01:07:25,290
O segundo problema é que, agora mesmo que fazer - salvar este, parar isso,

809
01:07:25,290 --> 01:07:34,530
executar o make novamente, tê-lo compilar, em seguida, executá-lo -

810
01:07:34,530 --> 01:07:37,670
vemos que algo mais aconteceu aqui.

811
01:07:37,670 --> 01:07:42,980
O 5, 8, e 2 foram ainda nunca encontrada na árvore.

812
01:07:42,980 --> 01:07:44,350
Então, o que está acontecendo?

813
01:07:44,350 --> 01:07:45,700
>> Vamos dar uma olhada nisso no código.

814
01:07:45,700 --> 01:07:49,790
Vamos ver se podemos descobrir isso.

815
01:07:49,790 --> 01:07:57,940
Começamos com o pai não ser nulo.

816
01:07:57,940 --> 01:07:59,510
Nós ajustamos o ponteiro atual igual ao ponteiro raiz,

817
01:07:59,510 --> 01:08:04,280
e nós vamos trabalhar o nosso caminho através da árvore.

818
01:08:04,280 --> 01:08:08,650
Se o nó atual não é nulo, então sabemos que podemos mover um pouco para baixo.

819
01:08:08,650 --> 01:08:12,330
Montamos nosso ponteiro pai para ser igual ao atual do ponteiro,

820
01:08:12,330 --> 01:08:15,420
verificou o valor - se os valores são os mesmos que retornou falso.

821
01:08:15,420 --> 01:08:17,540
Se os valores são menos nos mudamos para a direita;

822
01:08:17,540 --> 01:08:20,399
caso contrário, mudou-se para a esquerda.

823
01:08:20,399 --> 01:08:24,220
Então, vamos construir um nó. Eu vou ampliar um pouco.

824
01:08:24,220 --> 01:08:31,410
E aqui, nós vamos tentar conectar os valores a ser o mesmo.

825
01:08:31,410 --> 01:08:37,250
O que está acontecendo? Vamos ver se possivelmente Valgrind pode nos dar uma dica.

826
01:08:37,250 --> 01:08:43,910
>> Eu gosto de usar Valgrind só porque Valgrind muito rapidamente executado

827
01:08:43,910 --> 01:08:46,729
e diz-lhe se existem erros de memória.

828
01:08:46,729 --> 01:08:48,300
Quando corremos Valgrind no código,

829
01:08:48,300 --> 01:08:55,859
como você pode ver hit here--Valgrind./binary_tree--and direito entrar.

830
01:08:55,859 --> 01:09:03,640
Você vê que não tem nenhum erro de memória, por isso parece que está tudo bem até agora.

831
01:09:03,640 --> 01:09:07,529
Temos alguns vazamentos de memória, que sabemos, porque não somos

832
01:09:07,529 --> 01:09:08,910
acontecendo para libertar qualquer um dos nossos nós.

833
01:09:08,910 --> 01:09:13,050
Vamos tentar executar GDB para ver o que está realmente acontecendo.

834
01:09:13,050 --> 01:09:20,010
Nós vamos fazer gdb. / Binary_tree. Ele iniciou-se muito bem.

835
01:09:20,010 --> 01:09:23,670
Vamos definir um ponto de ruptura na inserção.

836
01:09:23,670 --> 01:09:28,600
Vamos correr.

837
01:09:28,600 --> 01:09:31,200
Parece que nós nunca realmente chamado de inserção.

838
01:09:31,200 --> 01:09:39,410
Parece que o problema era só que quando eu mudei para cá em principal -

839
01:09:39,410 --> 01:09:44,279
todas essas chamadas de printf contém -

840
01:09:44,279 --> 01:09:56,430
Eu nunca realmente mudou destes para chamar de inserção.

841
01:09:56,430 --> 01:10:01,660
Agora vamos dar uma chance. Vamos compilar.

842
01:10:01,660 --> 01:10:09,130
Tudo parece bom lá. Agora vamos tentar executá-lo, ver o que acontece.

843
01:10:09,130 --> 01:10:13,320
Tudo bem! Tudo parece muito bom lá.

844
01:10:13,320 --> 01:10:18,130
>> A última coisa a se pensar é, existem casos de ponta a esta inserção?

845
01:10:18,130 --> 01:10:23,170
E acontece que, bem, o caso de borda que é sempre interessante para pensar sobre

846
01:10:23,170 --> 01:10:26,250
é, o que acontece se a sua árvore está vazia e você chamar essa função de inserção?

847
01:10:26,250 --> 01:10:30,330
Será que vai funcionar? Bem, vamos dar uma chance.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
A maneira que nós vamos testar este é, estamos indo para ir até a nossa função principal,

850
01:10:35,810 --> 01:10:41,690
e ao invés de fiação esses nós se assim,

851
01:10:41,690 --> 01:10:56,730
nós apenas estamos indo para comentar a coisa toda,

852
01:10:56,730 --> 01:11:02,620
e em vez de fiação até os nós de nós mesmos,

853
01:11:02,620 --> 01:11:09,400
nós podemos realmente ir em frente e apagar tudo isso.

854
01:11:09,400 --> 01:11:17,560
Nós vamos fazer tudo o que uma chamada para inserir.

855
01:11:17,560 --> 01:11:49,020
Então, vamos fazer - em vez de 5, 8 e 2, vamos inserir 7, 3 e 9.

856
01:11:49,020 --> 01:11:58,440
E então nós também deseja inserir 6 também.

857
01:11:58,440 --> 01:12:05,190
Salvar. Sair. Fazer árvore binária.

858
01:12:05,190 --> 01:12:08,540
Tudo compila.

859
01:12:08,540 --> 01:12:10,320
Nós podemos apenas executá-lo como está e ver o que acontece,

860
01:12:10,320 --> 01:12:12,770
mas também vai ser muito importante para se certificar de que

861
01:12:12,770 --> 01:12:14,740
não temos quaisquer erros de memória,

862
01:12:14,740 --> 01:12:16,840
uma vez que este é um dos nossos casos de ponta que nós conhecemos.

863
01:12:16,840 --> 01:12:20,150
>> Vamos ter certeza de que ele funciona bem sob Valgrind,

864
01:12:20,150 --> 01:12:28,310
o que faremos simplesmente executando Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Parece que, de facto, um erro de um contexto -

866
01:12:31,110 --> 01:12:33,790
temos essa falha de segmentação.

867
01:12:33,790 --> 01:12:36,690
O que aconteceu?

868
01:12:36,690 --> 01:12:41,650
Valgrind realmente nos diz onde está.

869
01:12:41,650 --> 01:12:43,050
Zoom para fora um pouco.

870
01:12:43,050 --> 01:12:46,040
Parece que está acontecendo em nossa função de inserção,

871
01:12:46,040 --> 01:12:53,420
onde temos uma leitura inválido de tamanho 4 a inserção, linha 60.

872
01:12:53,420 --> 01:13:03,590
Vamos voltar e ver o que está acontecendo aqui.

873
01:13:03,590 --> 01:13:05,350
Diminuir o zoom muito rápido.

874
01:13:05,350 --> 01:13:14,230
Eu quero ter certeza de que ele não vai para a borda da tela, para que possamos ver tudo.

875
01:13:14,230 --> 01:13:18,760
Puxe que em um pouco. Tudo bem.

876
01:13:18,760 --> 01:13:35,030
Rolar para baixo, e que o problema está aqui.

877
01:13:35,030 --> 01:13:40,120
O que acontece se nós descermos e nosso nó atual já é nulo,

878
01:13:40,120 --> 01:13:44,010
nosso nó pai é nulo, por isso, se olhamos para o topo, aqui -

879
01:13:44,010 --> 01:13:47,340
se isso nunca loop while realmente executa

880
01:13:47,340 --> 01:13:52,330
porque o nosso valor atual é nulo - a nossa raiz é nula para atu é nulo -

881
01:13:52,330 --> 01:13:57,810
então nunca nosso pai é configurado para atu ou para um valor válido,

882
01:13:57,810 --> 01:14:00,580
assim, o pai também será nulo.

883
01:14:00,580 --> 01:14:03,700
Precisamos lembrar para verificar que

884
01:14:03,700 --> 01:14:08,750
no momento em que chegar aqui, e começar a acessar valor do pai.

885
01:14:08,750 --> 01:14:13,190
Então, o que acontece? Bem, se o pai é nulo -

886
01:14:13,190 --> 01:14:17,990
if (pai == NULL) -, então nós sabemos que

887
01:14:17,990 --> 01:14:19,530
não deve haver qualquer coisa na árvore.

888
01:14:19,530 --> 01:14:22,030
Devemos estar tentando inseri-lo na raiz.

889
01:14:22,030 --> 01:14:32,570
Podemos fazer isso definindo apenas a raiz igual ao novo nó.

890
01:14:32,570 --> 01:14:40,010
Então, neste ponto, nós realmente não quero passar por essas outras coisas.

891
01:14:40,010 --> 01:14:44,780
Em vez disso, aqui, nós podemos fazer uma ou outra coisa-se-else,

892
01:14:44,780 --> 01:14:47,610
ou podemos combinar tudo aqui em uma outra pessoa,

893
01:14:47,610 --> 01:14:56,300
mas aqui vamos usar mais e fazê-lo dessa maneira.

894
01:14:56,300 --> 01:14:59,030
Agora, vamos testar para ter certeza de que o nosso pai não é nulo

895
01:14:59,030 --> 01:15:02,160
antes, então realmente tentando acessar seus campos.

896
01:15:02,160 --> 01:15:05,330
Isso vai nos ajudar a evitar a falha de segmentação.

897
01:15:05,330 --> 01:15:14,740
Então, nós paramos, zoom out, compilar, executar.

898
01:15:14,740 --> 01:15:18,130
>> Sem erros, mas ainda temos um monte de vazamentos de memória

899
01:15:18,130 --> 01:15:20,650
porque não libertar qualquer um dos nossos nós.

900
01:15:20,650 --> 01:15:24,350
Mas, se formos até aqui e vá para a impressão,

901
01:15:24,350 --> 01:15:30,880
vemos que, bem, parece que todos os nossos inserções foram retornando verdadeiro, o que é bom.

902
01:15:30,880 --> 01:15:33,050
As pastilhas são todas verdadeiras,

903
01:15:33,050 --> 01:15:36,670
e depois as chamadas apropriadas contém também são verdadeiras.

904
01:15:36,670 --> 01:15:41,510
>> Bom trabalho! Parece que temos escrito com sucesso inserção.

905
01:15:41,510 --> 01:15:47,430
Isso é tudo o que temos para esta semana Especificação conjunto de problemas.

906
01:15:47,430 --> 01:15:51,720
Um desafio divertido de pensar é como você realmente ir em

907
01:15:51,720 --> 01:15:55,340
e livre de todos os nós desta árvore.

908
01:15:55,340 --> 01:15:58,830
Podemos fazer um certo número de maneiras diferentes,

909
01:15:58,830 --> 01:16:01,930
mas vou deixar isso para você experimentar,

910
01:16:01,930 --> 01:16:06,080
e como um desafio divertido, tentar e ter certeza de que você pode ter certeza

911
01:16:06,080 --> 01:16:09,490
que este relatório Valgrind retorna sem erros e sem vazamentos.

912
01:16:09,490 --> 01:16:12,880
>> Boa sorte no jogo desta semana problema Huffman,

913
01:16:12,880 --> 01:16:14,380
e vamos ver semana que vem!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]