1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Sezione 7] [meno confortevole]

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

3
00:00:04,890 --> 00:00:07,000
[Questo è CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Benvenuti alla Sezione 7.

5
00:00:09,080 --> 00:00:11,330
Grazie a Sandy uragano,

6
00:00:11,330 --> 00:00:13,440
invece di avere una sezione normale di questa settimana,

7
00:00:13,440 --> 00:00:17,650
lo stiamo facendo walk-through, attraverso la sezione di domande.

8
00:00:17,650 --> 00:00:22,830
Ho intenzione di seguire in particolare il problema Set 6 Specification,

9
00:00:22,830 --> 00:00:25,650
e passando attraverso tutte le domande del

10
00:00:25,650 --> 00:00:27,770
Una sezione della sezione Domande.

11
00:00:27,770 --> 00:00:30,940
Se ci sono delle domande,

12
00:00:30,940 --> 00:00:32,960
si prega di inviare questi su CS50 discutere.

13
00:00:32,960 --> 00:00:35,480
>> Va bene. Cominciamo.

14
00:00:35,480 --> 00:00:40,780
In questo momento sto guardando la pagina 3 della Specifica Set problema.

15
00:00:40,780 --> 00:00:44,110
Stiamo per iniziare prima a parlare di alberi binari

16
00:00:44,110 --> 00:00:47,850
in quanto tali hanno un sacco di rilevanza per set problema di questa settimana -

17
00:00:47,850 --> 00:00:49,950
la codifica di Huffman.

18
00:00:49,950 --> 00:00:55,000
Una delle strutture di dati molto prima abbiamo parlato sul CS50 era la matrice.

19
00:00:55,000 --> 00:01:00,170
Ricordate che un array è una sequenza di elementi -

20
00:01:00,170 --> 00:01:04,019
tutte dello stesso tipo - memorizzato accanto all'altro in memoria.

21
00:01:04,019 --> 00:01:14,420
Se ho un array di interi che posso disegnare con questo scatole-numeri-interi stile -

22
00:01:14,420 --> 00:01:20,290
Diciamo che ho 5 nella prima casella, ho 7 nel secondo,

23
00:01:20,290 --> 00:01:27,760
poi ho 8, 10, e 20 nella casella finale.

24
00:01:27,760 --> 00:01:33,000
Ricordate le cose, le due realtà positive di questa matrice

25
00:01:33,000 --> 00:01:38,800
è che abbiamo questo tempo costante accesso a qualsiasi elemento particolare

26
00:01:38,800 --> 00:01:40,500
 nella matrice se sappiamo suo indice.

27
00:01:40,500 --> 00:01:44,670
Per esempio, se voglio prendere il terzo elemento della matrice -

28
00:01:44,670 --> 00:01:47,870
2 dell'indice usando il nostro a base zero sistema di indicizzazione -

29
00:01:47,870 --> 00:01:52,220
Ho letteralmente solo fare un semplice calcolo matematico,

30
00:01:52,220 --> 00:01:56,170
hop a quella posizione nella matrice,

31
00:01:56,170 --> 00:01:57,840
estrarre la 8 che è memorizzato,

32
00:01:57,840 --> 00:01:59,260
e io sono a posto.

33
00:01:59,260 --> 00:02:03,350
>> Una delle cose brutte su questo array - di cui abbiamo parlato

34
00:02:03,350 --> 00:02:05,010
quando abbiamo discusso liste concatenate -

35
00:02:05,010 --> 00:02:09,120
è che se voglio inserire un elemento in questa matrice,

36
00:02:09,120 --> 00:02:11,090
Ho intenzione di fare un po 'a vacillare.

37
00:02:11,090 --> 00:02:12,940
Ad esempio, questa matrice qui

38
00:02:12,940 --> 00:02:16,850
è in modo ordinato - in ordine crescente -

39
00:02:16,850 --> 00:02:19,440
5, poi 7, poi 8, poi 10, poi 20 -

40
00:02:19,440 --> 00:02:23,100
ma se voglio inserire il numero 9 in questa matrice,

41
00:02:23,100 --> 00:02:27,460
Sto andando a spostare alcuni degli elementi, al fine di fare spazio.

42
00:02:27,460 --> 00:02:30,440
Siamo in grado di disegnare questo qui.

43
00:02:30,440 --> 00:02:35,650
Sto andando a spostare il 5, il 7, e poi la 8;

44
00:02:35,650 --> 00:02:38,720
creare uno spazio dove posso mettere il 9,

45
00:02:38,720 --> 00:02:45,910
e poi il 10 e il 20 può andare alla destra del 9.

46
00:02:45,910 --> 00:02:49,450
Si tratta di una specie di dolore perché nel peggiore dei casi -

47
00:02:49,450 --> 00:02:54,350
quando siamo dover inserire o all'inizio o alla fine

48
00:02:54,350 --> 00:02:56,040
della matrice, a seconda di come ci stiamo spostando -

49
00:02:56,040 --> 00:02:58,850
potremmo finire per dover spostare tutti gli elementi

50
00:02:58,850 --> 00:03:00,750
che stiamo attualmente memorizzando nella matrice.

51
00:03:00,750 --> 00:03:03,810
>> Allora, che cosa è stato il modo per aggirare questo?

52
00:03:03,810 --> 00:03:09,260
Il modo per aggirare questo è stato quello di andare alla nostra lista concatenata metodo in cui -

53
00:03:09,260 --> 00:03:19,820
invece di memorizzare gli elementi 5, 7, 8, 10 e 20 tutti adiacenti in memoria -

54
00:03:19,820 --> 00:03:25,630
quello che abbiamo fatto è stato invece conservarli tipo di ovunque volessimo per memorizzarli

55
00:03:25,630 --> 00:03:32,470
in queste liste collegate nodi che sto disegnando qui, un po 'ad hoc.

56
00:03:32,470 --> 00:03:42,060
E poi li abbiamo collegati tra loro con questi puntatori successivi.

57
00:03:42,060 --> 00:03:44,370
Posso avere un puntatore dalla 5 alla 7,

58
00:03:44,370 --> 00:03:46,420
un puntatore dalla 7 alla 8,

59
00:03:46,420 --> 00:03:47,770
un puntatore dalla 8 alla 10,

60
00:03:47,770 --> 00:03:51,220
e, infine, un puntatore dalla 10 alla 20,

61
00:03:51,220 --> 00:03:54,880
e poi un puntatore nullo al 20 che indica che non c'è niente di sinistra.

62
00:03:54,880 --> 00:03:59,690
Il trade-off che abbiamo qui

63
00:03:59,690 --> 00:04:05,360
è che ora se vogliamo inserire il numero 9 nella nostra lista ordinata,

64
00:04:05,360 --> 00:04:08,270
tutto quello che dobbiamo fare è creare un nuovo nodo con 9,

65
00:04:08,270 --> 00:04:12,290
collegarlo fino al punto fino al luogo appropriato,

66
00:04:12,290 --> 00:04:20,630
e poi ri-legare l'8 a puntare verso il basso al 9.

67
00:04:20,630 --> 00:04:25,660
E 'abbastanza veloce, assumendo sappiamo esattamente dove si vuole inserire il 9.

68
00:04:25,660 --> 00:04:32,610
Ma il trade-off in cambio di questo è che ora abbiamo perso la costante tempo di accesso

69
00:04:32,610 --> 00:04:36,230
a qualsiasi elemento particolare nella nostra struttura dati.

70
00:04:36,230 --> 00:04:40,950
Per esempio, se voglio trovare il quarto elemento in questa lista collegata,

71
00:04:40,950 --> 00:04:43,510
Ho intenzione di ricominciare proprio all'inizio della lista

72
00:04:43,510 --> 00:04:48,930
e lavorare la mia strada attraverso il conteggio nodo per nodo fino a trovare il quarto.

73
00:04:48,930 --> 00:04:55,870
>> Al fine di ottenere prestazioni di accesso meglio di una lista concatenata -

74
00:04:55,870 --> 00:04:59,360
ma anche mantenere alcuni dei vantaggi che abbiamo avuto

75
00:04:59,360 --> 00:05:01,800
in termini di inserimento a tempo da una lista concatenata -

76
00:05:01,800 --> 00:05:05,750
un albero binario sta andando ad avere bisogno di utilizzare la memoria un po 'di più.

77
00:05:05,750 --> 00:05:11,460
In particolare, invece di avere un puntatore a un nodo di albero binario -

78
00:05:11,460 --> 00:05:13,350
come la lista concatenata nodo fa -

79
00:05:13,350 --> 00:05:16,950
abbiamo intenzione di aggiungere un secondo puntatore al nodo albero binario.

80
00:05:16,950 --> 00:05:19,950
Piuttosto che avere un puntatore all'elemento successivo,

81
00:05:19,950 --> 00:05:24,420
stiamo andando ad avere un puntatore a un figlio sinistro e figlio destro.

82
00:05:24,420 --> 00:05:26,560
>> Facciamo un disegno per vedere ciò che in realtà sembra.

83
00:05:26,560 --> 00:05:31,350
Ancora una volta, ho intenzione di utilizzare queste scatole e frecce.

84
00:05:31,350 --> 00:05:37,150
Un nodo di albero binario partirà con solo una semplice scatola.

85
00:05:37,150 --> 00:05:40,940
E 'intenzione di avere uno spazio per il valore,

86
00:05:40,940 --> 00:05:47,280
e poi è anche intenzione di avere uno spazio per il figlio sinistro e figlio destro.

87
00:05:47,280 --> 00:05:49,280
Ho intenzione di etichettarli qui.

88
00:05:49,280 --> 00:05:57,560
Stiamo per avere il bambino a sinistra, e poi abbiamo intenzione di avere il figlio destro.

89
00:05:57,560 --> 00:05:59,920
Ci sono molti modi diversi di fare questo.

90
00:05:59,920 --> 00:06:02,050
A volte, per lo spazio e la comodità,

91
00:06:02,050 --> 00:06:06,460
Io in realtà disegnare come sto facendo qui in basso

92
00:06:06,460 --> 00:06:10,910
dove ho intenzione di avere il valore in alto,

93
00:06:10,910 --> 00:06:14,060
e poi il bambino a destra in basso a destra,

94
00:06:14,060 --> 00:06:16,060
e il figlio sinistro in basso a sinistra.

95
00:06:16,060 --> 00:06:20,250
Tornando a questo diagramma in alto,

96
00:06:20,250 --> 00:06:22,560
abbiamo il valore in cima,

97
00:06:22,560 --> 00:06:25,560
poi abbiamo la sinistra-bambino puntatore e quindi abbiamo il diritto-bambino puntatore.

98
00:06:25,560 --> 00:06:30,110
>> Nella specifica Set problema,

99
00:06:30,110 --> 00:06:33,110
si parla di disegnare un nodo che ha un valore di 7,

100
00:06:33,110 --> 00:06:39,750
e poi a sinistra-figlio puntatore che è nullo, e un diritto-figlio puntatore che è nullo.

101
00:06:39,750 --> 00:06:46,040
Possiamo scrivere NULL capitale nello spazio per

102
00:06:46,040 --> 00:06:51,610
sia il figlio sinistro e il figlio destro, o siamo in grado di disegnare questa barra diagonale

103
00:06:51,610 --> 00:06:53,750
attraverso ciascuna delle caselle per indicare che è nullo.

104
00:06:53,750 --> 00:06:57,560
Ho intenzione di farlo solo perché è più semplice.

105
00:06:57,560 --> 00:07:03,700
Quello che vedete qui sono due modi di diagrammi molto semplice nodo di albero binario

106
00:07:03,700 --> 00:07:07,960
dove abbiamo il valore 7 e puntatori nulli bambino.

107
00:07:07,960 --> 00:07:15,220
>> La seconda parte delle nostre discussioni specifiche su come con le liste collegate -

108
00:07:15,220 --> 00:07:18,270
ricordate, abbiamo avuto solo a mantenere il primo elemento di una lista

109
00:07:18,270 --> 00:07:20,270
per ricordare l'intero elenco -

110
00:07:20,270 --> 00:07:26,140
e allo stesso modo, con un albero binario, non ci resta che aggrapparsi a un puntatore alla struttura ad albero

111
00:07:26,140 --> 00:07:31,120
al fine di mantenere il controllo sulla struttura dati intera.

112
00:07:31,120 --> 00:07:36,150
Questo elemento particolare della struttura ad albero si chiama il nodo radice dell'albero.

113
00:07:36,150 --> 00:07:43,360
Ad esempio, se questo nodo - il nodo contenente il valore 7

114
00:07:43,360 --> 00:07:45,500
con puntatori nulli a destra ea sinistra del figlio -

115
00:07:45,500 --> 00:07:47,360
erano il valore solo nel nostro albero,

116
00:07:47,360 --> 00:07:50,390
allora questo sarebbe il nostro nodo principale.

117
00:07:50,390 --> 00:07:52,240
E 'proprio all'inizio del nostro albero.

118
00:07:52,240 --> 00:07:58,530
Possiamo vedere questo un po 'più chiaro una volta che iniziare ad aggiungere ulteriori nodi al nostro albero.

119
00:07:58,530 --> 00:08:01,510
Permettetemi di tirare su una nuova pagina.

120
00:08:01,510 --> 00:08:05,000
>> Ora stiamo andando a disegnare un albero che ha 7 alla radice,

121
00:08:05,000 --> 00:08:10,920
e 3 all'interno del figlio sinistro, e 9 all'interno del figlio destro.

122
00:08:10,920 --> 00:08:13,500
Ancora una volta, questo è abbastanza semplice.

123
00:08:13,500 --> 00:08:26,510
Abbiamo 7, disegnare un nodo per la 3, un nodo per 9,

124
00:08:26,510 --> 00:08:32,150
e ho intenzione di impostare il puntatore a sinistra bambino di 7 punti al nodo contenente 3,

125
00:08:32,150 --> 00:08:37,850
e il diritto-bambino puntatore del nodo contenente 7 al nodo contenente 9.

126
00:08:37,850 --> 00:08:42,419
Ora, dal momento che 3 e 9 non ha figli,

127
00:08:42,419 --> 00:08:48,500
stiamo andando a impostare tutti i loro puntatori figlio per essere nullo.

128
00:08:48,500 --> 00:08:56,060
Qui, la radice del nostro albero corrisponde al nodo contenente il numero 7.

129
00:08:56,060 --> 00:09:02,440
Si può vedere che se tutto quello che abbiamo è un puntatore a quel nodo radice,

130
00:09:02,440 --> 00:09:07,330
possiamo poi a piedi attraverso il nostro albero e accedere a entrambi i nodi figlio -

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

132
00:09:10,630 --> 00:09:14,820
Non c'è bisogno di mantenere i puntatori ad ogni singolo nodo sull'albero.

133
00:09:14,820 --> 00:09:22,080
Va bene. Ora stiamo andando ad aggiungere un altro nodo a questo schema.

134
00:09:22,080 --> 00:09:25,370
Stiamo per aggiungere un nodo contenente 6,

135
00:09:25,370 --> 00:09:34,140
e abbiamo intenzione di aggiungere questo come il figlio destro del nodo contenente 3.

136
00:09:34,140 --> 00:09:41,850
Per fare questo, ho intenzione di cancellare quel puntatore nullo nel 3-nodo

137
00:09:41,850 --> 00:09:47,750
e cavo fino a puntare al nodo contenente 6. Va bene.

138
00:09:47,750 --> 00:09:53,800
>> A questo punto, andiamo su un po 'di terminologia.

139
00:09:53,800 --> 00:09:58,230
Per iniziare, la ragione per cui si parla di un albero binario, in particolare,

140
00:09:58,230 --> 00:10:00,460
è che ha due puntatori figlio.

141
00:10:00,460 --> 00:10:06,020
Ci sono altri tipi di alberi che hanno più puntatori bambino.

142
00:10:06,020 --> 00:10:10,930
In particolare, hai fatto un 'try' nel set Problema 5.

143
00:10:10,930 --> 00:10:19,310
Si noterà che in quella prova, voi aveva 27 diversi puntatori ai bambini diverse -

144
00:10:19,310 --> 00:10:22,410
uno per ciascuna delle 26 lettere dell'alfabeto inglese,

145
00:10:22,410 --> 00:10:25,410
e poi il 27 per l'apostrofo -

146
00:10:25,410 --> 00:10:28,900
così, che è simile a un tipo di albero.

147
00:10:28,900 --> 00:10:34,070
Ma qui, dal momento che è binaria, abbiamo solo due puntatori figlio.

148
00:10:34,070 --> 00:10:37,880
>> Oltre a questo nodo principale di cui abbiamo parlato,

149
00:10:37,880 --> 00:10:41,470
abbiamo anche buttato intorno a questo termine 'bambino.'

150
00:10:41,470 --> 00:10:44,470
Che cosa significa per un nodo di essere figlio di un altro nodo?

151
00:10:44,470 --> 00:10:54,060
Letteralmente significa che un nodo figlio è un figlio di un altro nodo

152
00:10:54,060 --> 00:10:58,760
se tale nodo ha uno dei suoi figli puntatori impostata per puntare a quel nodo.

153
00:10:58,760 --> 00:11:01,230
Per mettere questo in termini più concreti,

154
00:11:01,230 --> 00:11:11,170
se 3 è puntato da uno dei puntatori figlio di 7, quindi 3 è un bambino di 7.

155
00:11:11,170 --> 00:11:14,510
Se dovessimo capire che cosa i figli di 7 sono -

156
00:11:14,510 --> 00:11:18,510
bene, vediamo che 7 ha un puntatore a 3 e un puntatore a 9,

157
00:11:18,510 --> 00:11:22,190
così 9 e 3 sono i figli di 7.

158
00:11:22,190 --> 00:11:26,650
Nove non ha figli perché i suoi figli puntatori sono nulli,

159
00:11:26,650 --> 00:11:30,940
e 3 ha un solo figlio, 6.

160
00:11:30,940 --> 00:11:37,430
Sei inoltre non ha figli perché entrambi i suoi puntatori sono nulli, che tireremo in questo momento.

161
00:11:37,430 --> 00:11:45,010
>> Inoltre, parliamo anche i genitori di un nodo particolare,

162
00:11:45,010 --> 00:11:51,100
e questo è, come ci si aspetterebbe, il contrario di questa descrizione bambino.

163
00:11:51,100 --> 00:11:58,620
Ogni nodo ha un solo genitore - invece di due, come ci si potrebbe aspettare con gli esseri umani.

164
00:11:58,620 --> 00:12:03,390
Per esempio, il genitore di 3 è 7.

165
00:12:03,390 --> 00:12:10,800
Il padre di 9 è anche 7, e la madre di 6 è 3. Non c'è molto da esso.

166
00:12:10,800 --> 00:12:15,720
Abbiamo anche termini per parlare di nonni e nipoti,

167
00:12:15,720 --> 00:12:18,210
e più in generale si parla di antenati

168
00:12:18,210 --> 00:12:20,960
e discendenti di un nodo particolare.

169
00:12:20,960 --> 00:12:25,710
L'antenato di un nodo - o antenati, piuttosto, di un nodo -

170
00:12:25,710 --> 00:12:32,730
sono tutti i nodi che si trovano sul percorso dalla radice a quel nodo.

171
00:12:32,730 --> 00:12:36,640
Per esempio, se sto guardando il nodo 6,

172
00:12:36,640 --> 00:12:46,430
poi gli antenati stanno per essere sia 3 e 7.

173
00:12:46,430 --> 00:12:55,310
Gli antenati di 9, per esempio, sono - se sto guardando il nodo 9 -

174
00:12:55,310 --> 00:12:59,990
poi l'antenato del 9 è solo 7.

175
00:12:59,990 --> 00:13:01,940
E discendenti sono esattamente il contrario.

176
00:13:01,940 --> 00:13:05,430
Se voglio vedere tutti i discendenti del 7,

177
00:13:05,430 --> 00:13:11,020
allora devo guardare tutti i nodi sotto di esso.

178
00:13:11,020 --> 00:13:16,950
Così, ho 3, 9, e 6 tutti come discendenti di 7.

179
00:13:16,950 --> 00:13:24,170
>> Il termine finale che parleremo di questo concetto di essere un fratello.

180
00:13:24,170 --> 00:13:27,980
Siblings - tipo di seguito lungo in questi termini famiglie -

181
00:13:27,980 --> 00:13:33,150
sono nodi che sono allo stesso livello nell'albero.

182
00:13:33,150 --> 00:13:42,230
Quindi, 3 e 9 sono fratelli perché sono allo stesso livello nell'albero.

183
00:13:42,230 --> 00:13:46,190
Entrambi hanno lo stesso padre, 7.

184
00:13:46,190 --> 00:13:51,400
Il 6 non ha fratelli, perché 9 non ha figli.

185
00:13:51,400 --> 00:13:55,540
E 7 non ha fratelli o sorelle, perché è la radice del nostro albero,

186
00:13:55,540 --> 00:13:59,010
e c'è sempre e solo 1 root.

187
00:13:59,010 --> 00:14:02,260
Per 7 di avere fratelli ci dovrebbe essere un nodo superiore a 7.

188
00:14:02,260 --> 00:14:07,480
Ci dovrebbe essere un genitore di 7, nel qual caso 7 non sarebbe più la radice dell'albero.

189
00:14:07,480 --> 00:14:10,480
Poi quel nuovo genitore del 7 dovrebbe anche avere un figlio,

190
00:14:10,480 --> 00:14:16,480
e quel bambino sarebbe poi il fratello di 7.

191
00:14:16,480 --> 00:14:21,040
>> Va bene. Passando.

192
00:14:21,040 --> 00:14:24,930
Quando abbiamo iniziato la nostra discussione di alberi binari,

193
00:14:24,930 --> 00:14:28,790
abbiamo parlato di come avremmo usarli per

194
00:14:28,790 --> 00:14:32,800
ottenere un vantaggio su entrambi gli array e liste concatenate.

195
00:14:32,800 --> 00:14:37,220
E il modo in cui abbiamo intenzione di farlo è con questa proprietà di ordinazione.

196
00:14:37,220 --> 00:14:41,080
Diciamo che un albero binario è ordinato, secondo la specifica,

197
00:14:41,080 --> 00:14:45,740
se per ogni nodo nell'albero, tutti i suoi discendenti a sinistra -

198
00:14:45,740 --> 00:14:48,670
il figlio sinistro e tutti i discendenti del bambino di sinistra -

199
00:14:48,670 --> 00:14:54,510
hanno meno valori, e tutti i nodi a destra -

200
00:14:54,510 --> 00:14:57,770
il bambino a destra e tutti i discendenti del bambino di destra -

201
00:14:57,770 --> 00:15:02,800
avere nodi superiori al valore del nodo corrente che stiamo guardando.

202
00:15:02,800 --> 00:15:07,850
Solo per semplicità, abbiamo intenzione di assumere che non ci sono i nodi duplicati nel nostro albero.

203
00:15:07,850 --> 00:15:11,180
Ad esempio, in questo albero non stiamo andando a trattare il caso

204
00:15:11,180 --> 00:15:13,680
dove abbiamo il valore 7 alla radice

205
00:15:13,680 --> 00:15:16,720
 e poi abbiamo anche il valore 7 altrove nella struttura ad albero.

206
00:15:16,720 --> 00:15:24,390
In questo caso, si noterà che questo albero è davvero ordinata.

207
00:15:24,390 --> 00:15:26,510
Abbiamo il valore 7 alla radice.

208
00:15:26,510 --> 00:15:29,720
Tutto a sinistra di 7 -

209
00:15:29,720 --> 00:15:35,310
se io sciolgo tutti questi piccoli segni qui -

210
00:15:35,310 --> 00:15:40,450
tutto a sinistra di 7 - il 3 e il 6 -

211
00:15:40,450 --> 00:15:49,410
questi valori sono entrambi meno di 7, e tutto a destra - che è proprio questo 9 -

212
00:15:49,410 --> 00:15:53,450
è maggiore di 7.

213
00:15:53,450 --> 00:15:58,650
>> Questo non è l'unico albero ordinato contenente questi valori,

214
00:15:58,650 --> 00:16:03,120
ma cerchiamo di disegnare un paio di più di loro.

215
00:16:03,120 --> 00:16:05,030
Vi è in realtà un sacco di modi in cui possiamo fare questo.

216
00:16:05,030 --> 00:16:09,380
Ho intenzione di utilizzare una scorciatoia solo per mantenere le cose semplici in cui -

217
00:16:09,380 --> 00:16:11,520
anziché disegnare l'intera scatole-e-frecce -

218
00:16:11,520 --> 00:16:14,220
Sto solo andando a disegnare i numeri e aggiungere frecce che li collegano.

219
00:16:14,220 --> 00:16:22,920
Per iniziare, ci limiteremo a scrivere il nostro albero originale di nuovo dove abbiamo avuto 7, e poi un 3,

220
00:16:22,920 --> 00:16:25,590
e poi 3 indicò a destra per il 6,

221
00:16:25,590 --> 00:16:30,890
e 7 aveva un figlio destro che era 9.

222
00:16:30,890 --> 00:16:33,860
Va bene. Che è un altro modo in cui si potrebbe scrivere questo albero?

223
00:16:33,860 --> 00:16:38,800
Invece di avere 3 Sii il figlio sinistro di 7,

224
00:16:38,800 --> 00:16:41,360
si potrebbe anche avere il 6 essere il figlio sinistro di 7,

225
00:16:41,360 --> 00:16:44,470
3 e quindi essere il figlio sinistro del 6.

226
00:16:44,470 --> 00:16:48,520
Questo sarebbe simile a questo albero proprio qui dove ho 7,

227
00:16:48,520 --> 00:16:57,860
poi 6, poi 3, e 9 sulla destra.

228
00:16:57,860 --> 00:17:01,490
Inoltre, non c'è bisogno di avere 7 come il nostro nodo principale.

229
00:17:01,490 --> 00:17:03,860
Potremmo anche avere 6 come il nostro nodo principale.

230
00:17:03,860 --> 00:17:06,470
Cosa che sembrano?

231
00:17:06,470 --> 00:17:09,230
Se abbiamo intenzione di mantenere questa struttura ordinata,

232
00:17:09,230 --> 00:17:12,970
tutto a sinistra del 6 deve essere inferiore a esso.

233
00:17:12,970 --> 00:17:16,540
C'è solo una possibilità, e questo è 3.

234
00:17:16,540 --> 00:17:19,869
Ma poi come il figlio destro di 6, abbiamo due possibilità.

235
00:17:19,869 --> 00:17:25,380
In primo luogo, si potrebbe avere il 7 e poi il 9,

236
00:17:25,380 --> 00:17:28,850
o potremmo trarre - come se fossi sul punto di fare qui -

237
00:17:28,850 --> 00:17:34,790
dove abbiamo la 9 come figlio destro del 6,

238
00:17:34,790 --> 00:17:39,050
e poi il 7 come figlio sinistro del 9.

239
00:17:39,050 --> 00:17:44,240
>> Ora, 7 e 6 non sono gli unici valori possibili per la radice.

240
00:17:44,240 --> 00:17:50,200
Possiamo anche avere tre essere alla radice.

241
00:17:50,200 --> 00:17:52,240
Cosa succede se 3 è alla radice?

242
00:17:52,240 --> 00:17:54,390
Qui, le cose si fanno un po 'interessante.

243
00:17:54,390 --> 00:17:58,440
Tre non ha valori che sono meno di esso,

244
00:17:58,440 --> 00:18:02,070
in modo che l'intero lato sinistro della struttura è solo andare a essere nullo.

245
00:18:02,070 --> 00:18:03,230
Non ci sarà nulla.

246
00:18:03,230 --> 00:18:07,220
A destra, potremmo elencare le cose in ordine crescente.

247
00:18:07,220 --> 00:18:15,530
Potremmo avere 3, poi 6, poi 7, poi 9.

248
00:18:15,530 --> 00:18:26,710
Oppure, potremmo fare 3, poi 6, poi 9, poi 7.

249
00:18:26,710 --> 00:18:35,020
Oppure, potremmo fare 3, poi 7, poi 6, poi 9.

250
00:18:35,020 --> 00:18:40,950
In alternativa, 3, 7 - in realtà no, non si può fare un 7 più.

251
00:18:40,950 --> 00:18:43,330
Questa è la nostra unica cosa lì.

252
00:18:43,330 --> 00:18:54,710
Possiamo fare 9 e quindi dal 9 possiamo fare 6 e poi 7.

253
00:18:54,710 --> 00:19:06,980
In alternativa, si può fare 3, poi 9, poi 7, e poi 6.

254
00:19:06,980 --> 00:19:12,490
>> Una cosa da attirare la vostra attenzione qui è

255
00:19:12,490 --> 00:19:14,510
che questi alberi sono un po 'strano aspetto.

256
00:19:14,510 --> 00:19:17,840
In particolare, se guardiamo i 4 alberi sul lato destro -

257
00:19:17,840 --> 00:19:20,930
Li cerchio, qui -

258
00:19:20,930 --> 00:19:28,410
questi alberi sembrano quasi esattamente come una lista concatenata.

259
00:19:28,410 --> 00:19:32,670
Ogni nodo ha un solo figlio,

260
00:19:32,670 --> 00:19:38,950
e quindi non abbiamo nulla di tutto questo albero come la struttura che si vede, per esempio,

261
00:19:38,950 --> 00:19:44,720
 in questo albero solitario uno qui in basso a sinistra.

262
00:19:44,720 --> 00:19:52,490
Questi alberi sono in realtà chiamati degeneri alberi binari,

263
00:19:52,490 --> 00:19:54,170
e parleremo di questi più in futuro -

264
00:19:54,170 --> 00:19:56,730
soprattutto se si va a prendere altri corsi di informatica.

265
00:19:56,730 --> 00:19:59,670
Questi alberi sono degeneri.

266
00:19:59,670 --> 00:20:03,780
Non sono molto utili perché, in effetti, questa struttura si presta

267
00:20:03,780 --> 00:20:08,060
 di ricercare i tempi simili a quello di una lista collegata.

268
00:20:08,060 --> 00:20:13,050
Noi non riusciamo a sfruttare la memoria aggiuntiva - questo puntatore extra -

269
00:20:13,050 --> 00:20:18,840
a causa della nostra struttura di essere male in questo modo.

270
00:20:18,840 --> 00:20:24,700
Piuttosto che andare avanti e tirare fuori gli alberi binari che hanno 9 alla radice,

271
00:20:24,700 --> 00:20:27,220
che è il caso finale che avremmo,

272
00:20:27,220 --> 00:20:32,380
siamo invece, a questo punto, di andare a parlare un po 'su questo altro termine

273
00:20:32,380 --> 00:20:36,150
che usiamo quando parliamo di alberi, che si chiama l'altezza.

274
00:20:36,150 --> 00:20:45,460
>> L'altezza di un albero è la distanza dalla radice al nodo più lontano,

275
00:20:45,460 --> 00:20:48,370
o meglio il numero di salti che si dovrebbe fare in modo da

276
00:20:48,370 --> 00:20:53,750
inizia dalla radice e poi finire al più lontano nodo nell'albero.

277
00:20:53,750 --> 00:20:57,330
Se guardiamo ad alcuni di questi alberi che abbiamo disegnato proprio qui,

278
00:20:57,330 --> 00:21:07,870
possiamo vedere che se prendiamo questo albero in alto a sinistra e iniziamo a 3,

279
00:21:07,870 --> 00:21:14,510
allora dobbiamo fare 1 salto per arrivare al 6, un secondo nodo per arrivare al 7,

280
00:21:14,510 --> 00:21:20,560
e un terzo hop per arrivare al 9.

281
00:21:20,560 --> 00:21:26,120
Quindi, l'altezza di questo albero è 3.

282
00:21:26,120 --> 00:21:30,640
Possiamo fare lo stesso esercizio per gli altri alberi descritti con questo verde,

283
00:21:30,640 --> 00:21:40,100
e vediamo che l'altezza di tutti questi alberi è effettivamente 3.

284
00:21:40,100 --> 00:21:45,230
Questo è parte di ciò che li rende degenere -

285
00:21:45,230 --> 00:21:53,750
che la loro altezza è solo uno meno del numero di nodi in tutto l'albero.

286
00:21:53,750 --> 00:21:58,400
Se osserviamo questo altro albero che è circondata di rosso, invece,

287
00:21:58,400 --> 00:22:03,920
vediamo che i più distanti nodi foglia sono il 6 e il 9 -

288
00:22:03,920 --> 00:22:06,940
le foglie essendo quei nodi che non hanno figli.

289
00:22:06,940 --> 00:22:11,760
Quindi, al fine di ottenere dal nodo radice né al 6 o al 9,

290
00:22:11,760 --> 00:22:17,840
dobbiamo fare un salto per arrivare al 7 e poi un secondo hop per arrivare al 9,

291
00:22:17,840 --> 00:22:21,240
e allo stesso modo, solo un secondo hop dal 7 per arrivare al 6.

292
00:22:21,240 --> 00:22:29,080
Quindi, l'altezza di questo albero qui è solo 2.

293
00:22:29,080 --> 00:22:35,330
Si può tornare indietro e farlo per tutti gli altri alberi che abbiamo discusso in precedenza

294
00:22:35,330 --> 00:22:37,380
cominciando con il 7 e il 6,

295
00:22:37,480 --> 00:22:42,500
e troverete che l'altezza di tutti questi alberi è anche 2.

296
00:22:42,500 --> 00:22:46,320
>> Il motivo per cui abbiamo parlato ordinata alberi binari

297
00:22:46,320 --> 00:22:50,250
e perché sono cool è perché è possibile cercare attraverso di loro in

298
00:22:50,250 --> 00:22:53,810
un modo molto simile alla ricerca in un array ordinato.

299
00:22:53,810 --> 00:22:58,720
Questo è dove si parla di ottenere che il tempo migliore ricerca

300
00:22:58,720 --> 00:23:02,730
il semplice elenco collegato.

301
00:23:02,730 --> 00:23:05,010
Con una lista concatenata - se si vuole trovare un particolare elemento -

302
00:23:05,010 --> 00:23:07,470
sei nella migliore delle ipotesi di andare a fare una sorta di ricerca lineare

303
00:23:07,470 --> 00:23:10,920
dove si inizia all'inizio di un elenco e hop one-by-one -

304
00:23:10,920 --> 00:23:12,620
un nodo da un nodo -

305
00:23:12,620 --> 00:23:16,060
attraverso l'intero elenco fino a trovare quello che stai cercando.

306
00:23:16,060 --> 00:23:19,440
Considerando che, se si dispone di un albero binario che è memorizzato in questo formato bello,

307
00:23:19,440 --> 00:23:23,300
si può effettivamente ottenere più di una ricerca binaria in corso

308
00:23:23,300 --> 00:23:25,160
dove si divide et impera

309
00:23:25,160 --> 00:23:29,490
e di ricerca attraverso la metà appropriata della struttura ad ogni passo.

310
00:23:29,490 --> 00:23:32,840
Vediamo come funziona.

311
00:23:32,840 --> 00:23:38,850
>> Se abbiamo - di nuovo, tornando al nostro albero originale -

312
00:23:38,850 --> 00:23:46,710
si inizia alle 7, abbiamo 3 a sinistra, a destra 9,

313
00:23:46,710 --> 00:23:51,740
e sotto il 3 abbiamo la 6.

314
00:23:51,740 --> 00:24:01,880
Se vogliamo cercare il numero 6 in questo albero, ci piacerebbe iniziare alla radice.

315
00:24:01,880 --> 00:24:08,910
Vorremmo confrontare il valore che stiamo cercando, per esempio 6,

316
00:24:08,910 --> 00:24:12,320
al valore memorizzato nel nodo che stiamo attualmente esaminando, 7,

317
00:24:12,320 --> 00:24:21,200
trova che 6 è effettivamente inferiore a 7, quindi ci sposta verso sinistra.

318
00:24:21,200 --> 00:24:25,530
Se il valore di 6 era maggiore di 7, avremmo invece spostato verso destra.

319
00:24:25,530 --> 00:24:29,770
Poiché sappiamo che - a causa della struttura del nostro albero binario ordinato -

320
00:24:29,770 --> 00:24:33,910
tutti i valori inferiori a 7 saranno immagazzinati a sinistra 7,

321
00:24:33,910 --> 00:24:40,520
non c'è bisogno di preoccuparsi, anche guardando attraverso il lato destro dell'albero.

322
00:24:40,520 --> 00:24:43,780
Una volta che ci si sposta verso sinistra e siamo ora al nodo che contiene 3,

323
00:24:43,780 --> 00:24:48,110
possiamo farlo di nuovo lo stesso confronto in cui si confronta il 3 e il 6.

324
00:24:48,110 --> 00:24:52,430
E troviamo che mentre il 6 - il valore che stiamo cercando - è maggiore di 3,

325
00:24:52,430 --> 00:24:58,580
possiamo andare al lato destro del nodo contenente 3.

326
00:24:58,580 --> 00:25:02,670
Non c'è sinistra qui, così avremmo potuto ignorare questo.

327
00:25:02,670 --> 00:25:06,510
Ma si sa solo che, perché stiamo guardando lo stesso albero,

328
00:25:06,510 --> 00:25:08,660
e possiamo vedere che l'albero non ha figli.

329
00:25:08,660 --> 00:25:13,640
>> E 'anche abbastanza facile da consultare 6 in questo albero, se lo stiamo facendo noi stessi come esseri umani,

330
00:25:13,640 --> 00:25:16,890
ma cerchiamo di seguire questo processo meccanico come un computer farebbe

331
00:25:16,890 --> 00:25:18,620
per capire veramente l'algoritmo.

332
00:25:18,620 --> 00:25:26,200
A questo punto, stiamo ora cercando un nodo che contiene 6,

333
00:25:26,200 --> 00:25:29,180
e stiamo cercando il valore 6,

334
00:25:29,180 --> 00:25:31,740
così, infatti, abbiamo trovato il nodo appropriato.

335
00:25:31,740 --> 00:25:35,070
Abbiamo trovato il valore 6 nel nostro albero, e siamo in grado di fermare la nostra ricerca.

336
00:25:35,070 --> 00:25:37,330
A questo punto, a seconda di quello che sta succedendo,

337
00:25:37,330 --> 00:25:41,870
si può dire, sì, abbiamo trovato il valore 6, che esiste nel nostro albero.

338
00:25:41,870 --> 00:25:47,640
Oppure, se stiamo pensando di inserire un nodo o fare qualcosa, possiamo farlo a questo punto.

339
00:25:47,640 --> 00:25:53,010
>> Facciamo un altro paio di ricerche solo per vedere come funziona.

340
00:25:53,010 --> 00:25:59,390
Diamo un'occhiata a cosa succede se dovessimo provare a cercare il valore 10.

341
00:25:59,390 --> 00:26:02,970
Se dovessimo cercare il valore 10, avremmo iniziato alla radice.

342
00:26:02,970 --> 00:26:07,070
Ci piacerebbe vedere che 10 è maggiore di 7, quindi ci si sposta verso destra.

343
00:26:07,070 --> 00:26:13,640
Ci piacerebbe arrivare al 9 e confrontare 9 al 10 e vedere che 9 è meno del 10.

344
00:26:13,640 --> 00:26:16,210
Quindi, di nuovo, ci piacerebbe provare a spostare a destra.

345
00:26:16,210 --> 00:26:20,350
Ma a questo punto, avevamo notato che siamo in un nodo nullo.

346
00:26:20,350 --> 00:26:23,080
Non c'e 'niente. Non c'è niente di cui il 10 dovrebbe essere.

347
00:26:23,080 --> 00:26:29,360
Questo è dove si segnala il fallimento - che non vi è infatti no 10 nella struttura.

348
00:26:29,360 --> 00:26:35,420
E, infine, andiamo attraverso il caso in cui stiamo cercando di guardare up 1 nella struttura.

349
00:26:35,420 --> 00:26:38,790
Questo è simile a quello che succede se guardiamo il 10, solo che invece di andare a destra,

350
00:26:38,790 --> 00:26:41,260
stiamo per andare a sinistra.

351
00:26:41,260 --> 00:26:46,170
Si comincia al 7 e vedere che 1 è inferiore a 7, in modo da spostare a sinistra.

352
00:26:46,170 --> 00:26:51,750
Arriviamo al 3 e vedere che 1 è inferiore a 3, quindi ancora una volta si tenta di spostare a sinistra.

353
00:26:51,750 --> 00:26:59,080
A questo punto abbiamo un nodo nullo, per cui ancora una volta siamo in grado di segnalare il guasto.

354
00:26:59,080 --> 00:27:10,260
>> Se si desidera saperne di più su alberi binari,

355
00:27:10,260 --> 00:27:14,420
ci sono un sacco di divertimento piccoli problemi che si possono fare con loro.

356
00:27:14,420 --> 00:27:19,450
Vi suggerisco di praticare il disegno di questi diagrammi one-by-one

357
00:27:19,450 --> 00:27:21,910
e in seguito attraverso tutte le diverse fasi,

358
00:27:21,910 --> 00:27:25,060
perché questo verrà in super-pratico

359
00:27:25,060 --> 00:27:27,480
non solo quando si sta facendo la codifica del set di Huffman problema

360
00:27:27,480 --> 00:27:29,390
ma anche in corsi successivi -

361
00:27:29,390 --> 00:27:32,220
solo imparando a tirare fuori queste strutture dati e pensare attraverso i problemi

362
00:27:32,220 --> 00:27:38,000
con carta e penna o, in questo caso, iPad e stilo.

363
00:27:38,000 --> 00:27:41,000
>> A questo punto, però, abbiamo intenzione di passare a fare un pò di pratica di codifica

364
00:27:41,000 --> 00:27:44,870
e proprio di giocare con questi alberi binari e vedere.

365
00:27:44,870 --> 00:27:52,150
Ho intenzione di tornare al mio computer.

366
00:27:52,150 --> 00:27:58,480
Per questa parte della sezione, invece di utilizzare Run CS50 o CS50 spazi,

367
00:27:58,480 --> 00:28:01,500
Ho intenzione di utilizzare l'apparecchio.

368
00:28:01,500 --> 00:28:04,950
>> Proseguendo lungo con la specifica Set problema,

369
00:28:04,950 --> 00:28:07,740
Vedo che dovrei aprire l'apparecchio,

370
00:28:07,740 --> 00:28:11,020
vai alla mia cartella Dropbox, creare una cartella denominata Sezione 7,

371
00:28:11,020 --> 00:28:15,730
e quindi creare un file chiamato binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Ci siamo. Ho l'apparecchio già aperto.

373
00:28:22,050 --> 00:28:25,910
Vado tirare su un terminale.

374
00:28:25,910 --> 00:28:38,250
Ho intenzione di passare alla cartella Dropbox, una directory chiamata sezione 7,

375
00:28:38,250 --> 00:28:42,230
e vedere che è completamente vuoto.

376
00:28:42,230 --> 00:28:48,860
Ora ho intenzione di aprire binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Va bene. Ci siamo - file vuoto.

378
00:28:51,750 --> 00:28:54,330
>> Torniamo alla specifica.

379
00:28:54,330 --> 00:28:59,850
La specifica chiede di creare una nuova definizione di tipo

380
00:28:59,850 --> 00:29:03,080
per un nodo di albero binario che contiene i valori int -

381
00:29:03,080 --> 00:29:07,110
proprio come i valori che ci ha richiamato nella nostra diagrammi prima.

382
00:29:07,110 --> 00:29:11,740
Stiamo andando a utilizzare questo boilerplate typedef che abbiamo fatto proprio qui

383
00:29:11,740 --> 00:29:14,420
che si dovrebbe riconoscere dal Set Problema 5 -

384
00:29:14,420 --> 00:29:19,190
se avete fatto la strada tabella hash di conquistare il programma speller.

385
00:29:19,190 --> 00:29:22,540
Si dovrebbe anche riconoscerlo da parte della scorsa settimana

386
00:29:22,540 --> 00:29:23,890
in cui abbiamo parlato di liste concatenate.

387
00:29:23,890 --> 00:29:27,870
Abbiamo ottenuto questo typedef di un nodo struct,

388
00:29:27,870 --> 00:29:34,430
e abbiamo dato questo nodo struct il nome del nodo struct in anticipo

389
00:29:34,430 --> 00:29:39,350
in modo da poter poi fare riferimento ad esso dal momento che vorrà avere puntatori struct nodo

390
00:29:39,350 --> 00:29:45,740
come parte della nostra struttura, ma abbiamo poi circondato questo -

391
00:29:45,740 --> 00:29:47,700
o meglio, racchiuso questo - in un typedef

392
00:29:47,700 --> 00:29:54,600
in modo che, più avanti nel codice, si può fare riferimento a questa struttura solo come un nodo al posto di un nodo struct.

393
00:29:54,600 --> 00:30:03,120
>> Questo sarà molto simile al singolarmente-linked definizione di elenco che abbiamo visto la scorsa settimana.

394
00:30:03,120 --> 00:30:20,070
Per fare questo, facciamo solo iniziare a scrivere il boilerplate.

395
00:30:20,070 --> 00:30:23,840
Sappiamo che dobbiamo avere un valore intero,

396
00:30:23,840 --> 00:30:32,170
quindi dovremo mettere in valore int, e quindi invece di avere solo un puntatore all'elemento successivo -

397
00:30:32,170 --> 00:30:33,970
come abbiamo fatto con singolarmente legati liste -

398
00:30:33,970 --> 00:30:38,110
stiamo andando ad avere puntatori figlio sinistro e destro.

399
00:30:38,110 --> 00:30:42,880
E 'abbastanza semplice, troppo - struct nodo figlio * sinistra;

400
00:30:42,880 --> 00:30:51,190
e struct nodo * diritto minorile;. Cool.

401
00:30:51,190 --> 00:30:54,740
Che sembra un buon inizio.

402
00:30:54,740 --> 00:30:58,530
Torniamo alla specifica.

403
00:30:58,530 --> 00:31:05,030
>> Ora abbiamo bisogno di dichiarare una variabile globale * nodo per la radice di un albero.

404
00:31:05,030 --> 00:31:10,590
Stiamo andando a fare questo mondiale, proprio come abbiamo fatto nel nostro primo puntatore lista collegata anche globale.

405
00:31:10,590 --> 00:31:12,690
Questo è stato in modo che le funzioni che scrivono

406
00:31:12,690 --> 00:31:16,180
non c'è bisogno di continuare passa intorno questa radice -

407
00:31:16,180 --> 00:31:19,620
anche se vedremo che se si vuole scrivere queste funzioni in modo ricorsivo,

408
00:31:19,620 --> 00:31:22,830
potrebbe essere meglio nemmeno passarlo in giro come un mondiale, in primo luogo

409
00:31:22,830 --> 00:31:28,090
e invece l'inizializzazione locale nella funzione principale.

410
00:31:28,090 --> 00:31:31,960
Ma, lo faremo a livello globale per iniziare.

411
00:31:31,960 --> 00:31:39,920
Anche in questo caso, daremo un paio di spazi, e ho intenzione di dichiarare una radice nodo *.

412
00:31:39,920 --> 00:31:46,770
Giusto per fare in modo che non mi lasciare questo non inizializzato, ho intenzione di impostarlo uguale a null.

413
00:31:46,770 --> 00:31:52,210
Ora, la funzione principale - di cui parleremo scrivere molto velocemente proprio qui -

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

415
00:32:00,450 --> 00:32:10,640
e ho intenzione di iniziare a dichiarare il mio array argv come const solo in modo che io so

416
00:32:10,640 --> 00:32:14,550
che tali argomenti sono argomenti che probabilmente non si desidera modificare.

417
00:32:14,550 --> 00:32:18,390
Se voglio modificarli forse dovrei essere l'esecuzione di copie di essi.

418
00:32:18,390 --> 00:32:21,740
Vedrete questo molto in codice.

419
00:32:21,740 --> 00:32:25,440
Va bene in entrambi i modi. Va bene lasciare come - omettere il const se lo desideri.

420
00:32:25,440 --> 00:32:28,630
Io di solito messo in proprio in modo che ricordo a me stesso

421
00:32:28,630 --> 00:32:33,650
 che probabilmente non si desidera modificare tali argomenti.

422
00:32:33,650 --> 00:32:39,240
>> Come sempre, ho intenzione di includere questo 0 tubazione di ritorno alla fine del principale.

423
00:32:39,240 --> 00:32:45,730
Ecco, io inizializzare il mio nodo principale.

424
00:32:45,730 --> 00:32:48,900
Così com'è adesso, ho un puntatore che è impostato su null,

425
00:32:48,900 --> 00:32:52,970
quindi è che punta a nulla.

426
00:32:52,970 --> 00:32:57,480
Al fine di iniziare a realizzare il nodo,

427
00:32:57,480 --> 00:32:59,250
Ho bisogno di allocare memoria per esso.

428
00:32:59,250 --> 00:33:05,910
Ho intenzione di farlo facendo memoria heap usando malloc.

429
00:33:05,910 --> 00:33:10,660
Ho intenzione di impostare radice uguale al risultato di malloc,

430
00:33:10,660 --> 00:33:19,550
e ho intenzione di usare l'operatore sizeof per calcolare la dimensione di un nodo.

431
00:33:19,550 --> 00:33:24,990
La ragione per cui io uso il nodo sizeof a differenza, per esempio,

432
00:33:24,990 --> 00:33:37,020
facendo qualcosa di simile - malloc (4 + 4 +4) o malloc 12 -

433
00:33:37,020 --> 00:33:40,820
è perché io voglio che il mio codice sia il più compatibile possibile.

434
00:33:40,820 --> 00:33:44,540
Voglio essere in grado di prendere questo file. C, compilarlo sull'apparecchio,

435
00:33:44,540 --> 00:33:48,820
e quindi compilarlo sul mio a 64-bit per Mac -

436
00:33:48,820 --> 00:33:52,040
o su un'architettura completamente diversa -

437
00:33:52,040 --> 00:33:54,640
e voglio che questo tutti funzionano allo stesso modo.

438
00:33:54,640 --> 00:33:59,510
>> Se sto facendo ipotesi circa le dimensioni di variabili -

439
00:33:59,510 --> 00:34:02,070
la dimensione di un int o la dimensione di un puntatore -

440
00:34:02,070 --> 00:34:06,070
poi mi sono anche fare ipotesi sul tipo di architetture

441
00:34:06,070 --> 00:34:10,440
su cui il mio codice può compilare correttamente quando viene eseguito.

442
00:34:10,440 --> 00:34:15,030
Usare sempre sizeof in contrasto manualmente sommando i campi struct.

443
00:34:15,030 --> 00:34:20,500
L'altra ragione è che ci potrebbe anche essere imbottitura che il compilatore inserisce nella struttura.

444
00:34:20,500 --> 00:34:26,570
Anche solo sommando i singoli campi non è una cosa che in genere si desidera fare,

445
00:34:26,570 --> 00:34:30,340
, cancellare quella linea.

446
00:34:30,340 --> 00:34:33,090
Ora, per inizializzare davvero questo nodo radice,

447
00:34:33,090 --> 00:34:36,489
Sto andando a inserire i valori per ciascuno dei suoi diversi settori.

448
00:34:36,489 --> 00:34:41,400
Ad esempio, per il valore so che voglio inizializzare a 7,

449
00:34:41,400 --> 00:34:46,920
e per ora ho intenzione di impostare il figlio sinistro di essere nullo

450
00:34:46,920 --> 00:34:55,820
e il bambino il diritto di essere anche nullo. Fantastico!

451
00:34:55,820 --> 00:35:02,670
Abbiamo fatto parte della specifica.

452
00:35:02,670 --> 00:35:07,390
>> La specifica verso il basso nella parte inferiore della pagina 3 mi chiede per creare più tre nodi -

453
00:35:07,390 --> 00:35:10,600
uno contenente 3, uno contenente 6, e uno con 9 -

454
00:35:10,600 --> 00:35:14,210
e poi cablare in modo che appaia esattamente come il nostro diagramma ad albero

455
00:35:14,210 --> 00:35:17,120
che parlavamo in precedenza.

456
00:35:17,120 --> 00:35:20,450
Facciamo che piuttosto velocemente qui.

457
00:35:20,450 --> 00:35:26,270
Vedrete molto in fretta che ho intenzione di iniziare a scrivere un mucchio di codice duplicato.

458
00:35:26,270 --> 00:35:32,100
Ho intenzione di creare un * nodo e ho intenzione di chiamare tre.

459
00:35:32,100 --> 00:35:36,000
Ho intenzione di impostarlo uguale a malloc (sizeof (nodo)).

460
00:35:36,000 --> 00:35:41,070
Ho intenzione di impostare tre-> valore = 3.

461
00:35:41,070 --> 00:35:54,780
Tre -> left_child = NULL; tre -> destra _child = NULL; pure.

462
00:35:54,780 --> 00:36:01,150
Che sembra piuttosto simile a inizializzare la radice, e questo è esattamente ciò che

463
00:36:01,150 --> 00:36:05,760
Ho intenzione di fare se mi metto l'inizializzazione 6 e 9 come bene.

464
00:36:05,760 --> 00:36:20,720
Lo farò molto velocemente qui - in realtà, ho intenzione di fare un po 'di copia e incolla,

465
00:36:20,720 --> 00:36:46,140
e fare in modo che io - va bene.

466
00:36:46,470 --> 00:37:09,900
 Ora, ho copiato e posso andare avanti e impostare questo uguale a 6.

467
00:37:09,900 --> 00:37:14,670
Si può vedere che questo richiede un po 'e non è super-efficiente.

468
00:37:14,670 --> 00:37:22,610
In appena un po ', ci scrivere una funzione che lo farà per noi.

469
00:37:22,610 --> 00:37:32,890
Voglio sostituire questo con un 9, sostituire che con un 6.

470
00:37:32,890 --> 00:37:37,360
>> Ora abbiamo tutti i nostri nodi creato e inizializzato.

471
00:37:37,360 --> 00:37:41,200
Abbiamo impostato la nostra radice uguale a 7, o contenenti il ​​valore 7,

472
00:37:41,200 --> 00:37:46,510
il nostro nodo contenente 3, il nostro nodo contenente 6, e il nostro nodo contenente 9.

473
00:37:46,510 --> 00:37:50,390
A questo punto, tutto quello che dobbiamo fare è tutto filo fino.

474
00:37:50,390 --> 00:37:53,020
Il motivo per cui ho inizializzato tutti i puntatori a null è proprio così che io faccio in modo che

475
00:37:53,020 --> 00:37:56,260
Non ho tutti i puntatori non inizializzati in là per caso.

476
00:37:56,260 --> 00:38:02,290
E anche perché, a questo punto, devo solo connettere effettivamente i nodi tra di loro -

477
00:38:02,290 --> 00:38:04,750
a quelli che sono in realtà collegati - che non c'è bisogno di passare attraverso e fare

478
00:38:04,750 --> 00:38:08,240
Assicurarsi che tutti i valori null sono lì nei luoghi appropriati.

479
00:38:08,240 --> 00:38:15,630
>> A partire dalla radice, so che figlio sinistro della radice è 3.

480
00:38:15,630 --> 00:38:21,250
So che figlio destro della radice è 9.

481
00:38:21,250 --> 00:38:24,880
Dopo di che, l'unico altro bambino che ho lasciato di cui preoccuparsi

482
00:38:24,880 --> 00:38:39,080
è il figlio destro 3, che è 6.

483
00:38:39,080 --> 00:38:44,670
A questo punto, tutto sembra abbastanza buono.

484
00:38:44,670 --> 00:38:54,210
Ci eliminare alcune di queste linee.

485
00:38:54,210 --> 00:38:59,540
Ora tutto sembra piuttosto buono.

486
00:38:59,540 --> 00:39:04,240
Torniamo alle nostre specifiche e vedere quello che dobbiamo fare.

487
00:39:04,240 --> 00:39:07,610
>> A questo punto, dobbiamo scrivere una funzione chiamata 'contiene'

488
00:39:07,610 --> 00:39:14,150
con un prototipo di 'contiene bool (int valore).

489
00:39:14,150 --> 00:39:17,060
E questo contiene la funzione sta per restituire true

490
00:39:17,060 --> 00:39:21,200
 se l'albero a cui punta la variabile root globale

491
00:39:21,200 --> 00:39:26,950
 contiene il valore passato alla funzione e false in caso contrario.

492
00:39:26,950 --> 00:39:29,000
Andiamo avanti e farlo.

493
00:39:29,000 --> 00:39:35,380
Questo sta per essere esattamente come la ricerca che abbiamo fatto a mano su iPad solo un po 'di tempo fa.

494
00:39:35,380 --> 00:39:40,130
Facciamo ingrandire di nuovo un po 'e scorrere verso l'alto.

495
00:39:40,130 --> 00:39:43,130
Stiamo per mettere questa funzione proprio sopra la nostra funzione principale

496
00:39:43,130 --> 00:39:48,990
in modo da non dover fare alcun tipo di prototipazione.

497
00:39:48,990 --> 00:39:55,960
Quindi, bool (int valore).

498
00:39:55,960 --> 00:40:00,330
Ecco fatto. C'è la nostra dichiarazione boilerplate.

499
00:40:00,330 --> 00:40:02,900
Giusto per fare in modo che questo compilerà,

500
00:40:02,900 --> 00:40:06,820
Ho intenzione di andare avanti e basta porla uguale a restituire false.

501
00:40:06,820 --> 00:40:09,980
Al momento questa funzione è sufficiente non fare nulla e sempre riportano che

502
00:40:09,980 --> 00:40:14,010
il valore che stiamo cercando non è nella struttura.

503
00:40:14,010 --> 00:40:16,280
>> A questo punto, è probabilmente una buona idea -

504
00:40:16,280 --> 00:40:19,600
da quando abbiamo scritto un sacco di codice e non abbiamo nemmeno provato provarla ancora -

505
00:40:19,600 --> 00:40:22,590
per assicurarsi che raccoglie tutte.

506
00:40:22,590 --> 00:40:27,460
Ci sono un paio di cose che dobbiamo fare per fare in modo che questo sarà effettivamente compilato.

507
00:40:27,460 --> 00:40:33,530
In primo luogo, verificare se abbiamo usato le funzioni in tutte le librerie che non abbiamo ancora inclusi.

508
00:40:33,530 --> 00:40:37,940
Le funzioni che abbiamo usato finora sono malloc,

509
00:40:37,940 --> 00:40:43,310
e poi abbiamo anche usato questo tipo - questo tipo non standard chiamato 'bool' -

510
00:40:43,310 --> 00:40:45,750
che è incluso nel file di intestazione standard bool.

511
00:40:45,750 --> 00:40:53,250
Abbiamo sicuramente desidera includere bool.h standard per il tipo bool,

512
00:40:53,250 --> 00:40:59,230
e vogliamo anche includere # lib.h standard per le librerie standard

513
00:40:59,230 --> 00:41:03,530
che includono malloc, e libero, e tutto il resto.

514
00:41:03,530 --> 00:41:08,660
Quindi, eseguire lo zoom indietro, stiamo andando a smettere.

515
00:41:08,660 --> 00:41:14,190
Cerchiamo di fare in modo che questa realtà ha fatto di compilazione.

516
00:41:14,190 --> 00:41:18,150
Si vede che lo fa, quindi siamo sulla strada giusta.

517
00:41:18,150 --> 00:41:22,990
>> Apriamo il binary_tree.c nuovo.

518
00:41:22,990 --> 00:41:34,530
Si compila. Andiamo verso il basso e fare in modo di inserire alcune chiamate alla nostra funzione contiene -

519
00:41:34,530 --> 00:41:40,130
solo per assicurarsi che questo è cosa buona e giusta.

520
00:41:40,130 --> 00:41:43,170
Per esempio, quando abbiamo fatto alcune ricerche nel nostro albero in precedenza,

521
00:41:43,170 --> 00:41:48,500
abbiamo provato a cercare i valori 6, 10, e 1, e sapevamo che 6 era nella struttura,

522
00:41:48,500 --> 00:41:52,220
10 non era nella struttura, e 1 non era nella struttura sia.

523
00:41:52,220 --> 00:41:57,230
Usiamo queste chiamate di esempio come un modo per capire se

524
00:41:57,230 --> 00:41:59,880
la nostra funzione contiene funziona.

525
00:41:59,880 --> 00:42:05,210
Per fare questo, ho intenzione di utilizzare la funzione printf,

526
00:42:05,210 --> 00:42:10,280
e stiamo andando a stampare il risultato della chiamata a contiene.

527
00:42:10,280 --> 00:42:13,280
Ho intenzione di mettere in una stringa "contiene (% d) = perché

528
00:42:13,280 --> 00:42:20,470
 stiamo andando a inserire il valore che stiamo andando a cercare,

529
00:42:20,470 --> 00:42:27,130
e =% s \ n "e l'uso che la nostra stringa di formato.

530
00:42:27,130 --> 00:42:30,720
Stiamo solo andando a vedere - letteralmente stampare sullo schermo -

531
00:42:30,720 --> 00:42:32,060
quella che appare come una chiamata di funzione.

532
00:42:32,060 --> 00:42:33,580
Questo non è in realtà la chiamata di funzione.

533
00:42:33,580 --> 00:42:36,760
 Questa è solo una stringa progettato per apparire come una chiamata di funzione.

534
00:42:36,760 --> 00:42:41,140
>> Ora, andiamo a collegare i valori.

535
00:42:41,140 --> 00:42:43,580
Stiamo andando a cercare contiene il 6,

536
00:42:43,580 --> 00:42:48,340
e poi quello che andremo a fare è utilizzare tale operatore ternario.

537
00:42:48,340 --> 00:42:56,340
Vediamo un po '- contiene 6 - così, ora ho conteneva 6 e se contiene 6 è vero,

538
00:42:56,340 --> 00:43:01,850
la stringa che stiamo per inviare al carattere di formato% s

539
00:43:01,850 --> 00:43:04,850
sarà la stringa "true".

540
00:43:04,850 --> 00:43:07,690
Facciamo scorrere sopra un po '.

541
00:43:07,690 --> 00:43:16,210
In caso contrario, si desidera inviare la stringa "false" se contiene 6 restituisce false.

542
00:43:16,210 --> 00:43:19,730
Questo è un po 'goffo di aspetto, ma ho capito che potrebbe anche illustrare

543
00:43:19,730 --> 00:43:23,780
ciò che l'operatore ternario sembra che dal momento che non l'ho visto per un po '.

544
00:43:23,780 --> 00:43:27,670
Questo sarà un modo semplice e comodo per capire se la nostra funzione contiene funziona.

545
00:43:27,670 --> 00:43:30,040
Io vado a scorrere indietro verso sinistra,

546
00:43:30,040 --> 00:43:39,900
e ho intenzione di copiare e incollare questa linea un paio di volte.

547
00:43:39,900 --> 00:43:44,910
Ha cambiato alcuni di questi valori in giro,

548
00:43:44,910 --> 00:43:59,380
quindi questo sarà 1, e questo sta per essere 10.

549
00:43:59,380 --> 00:44:02,480
>> A questo punto abbiamo una funzione di Nizza contiene.

550
00:44:02,480 --> 00:44:06,080
Abbiamo alcuni test, e vedremo se tutto questo funziona.

551
00:44:06,080 --> 00:44:08,120
A questo punto abbiamo scritto il codice un po 'di più.

552
00:44:08,120 --> 00:44:13,160
È ora di uscire fuori e fare in modo che tutto ciò che compila ancora.

553
00:44:13,160 --> 00:44:20,360
Esci fuori, e ora proviamo a fare albero binario di nuovo.

554
00:44:20,360 --> 00:44:22,260
Beh, sembra che abbiamo un errore,

555
00:44:22,260 --> 00:44:26,930
e abbiamo ottenuto questo dichiarare in modo esplicito la funzione di libreria printf.

556
00:44:26,930 --> 00:44:39,350
Sembra che abbiamo bisogno di andare in e # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
E con questo, tutto dovrebbe compilare. Siamo tutti buoni.

558
00:44:45,350 --> 00:44:50,420
Ora proviamo in esecuzione albero binario e vedere cosa succede.

559
00:44:50,420 --> 00:44:53,520
Eccoci qui,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
e vediamo che, come ci aspettavamo -

561
00:44:55,190 --> 00:44:56,910
perché non abbiamo ancora implementato contiene,

562
00:44:56,910 --> 00:44:59,800
o meglio, abbiamo appena messo in return false -

563
00:44:59,800 --> 00:45:03,300
si vede che è solo restituire false per tutti loro,

564
00:45:03,300 --> 00:45:06,180
così che è tutto funziona per la maggior parte abbastanza bene.

565
00:45:06,180 --> 00:45:11,860
>> Torniamo indietro e di attuare effettivamente contiene, a questo punto.

566
00:45:11,860 --> 00:45:17,490
Io vado a scorrere verso il basso, lo zoom, e -

567
00:45:17,490 --> 00:45:22,330
ricordate, l'algoritmo che abbiamo usato è che abbiamo iniziato in corrispondenza del nodo radice

568
00:45:22,330 --> 00:45:28,010
e poi ad ogni nodo che incontriamo, facciamo un confronto,

569
00:45:28,010 --> 00:45:32,380
e sulla base di tale confronto ci sia passare al figlio sinistro o per il figlio destro.

570
00:45:32,380 --> 00:45:39,670
Questo sta a guardare molto simile al codice binario di ricerca che abbiamo scritto in precedenza nel periodo.

571
00:45:39,670 --> 00:45:47,810
Quando iniziare, sappiamo che vogliamo mantenere il nodo corrente

572
00:45:47,810 --> 00:45:54,050
che stiamo guardando, e il nodo corrente sta per essere inizializzato al nodo radice.

573
00:45:54,050 --> 00:45:56,260
E ora, andiamo ad andare avanti attraverso l'albero,

574
00:45:56,260 --> 00:45:58,140
e ricordare che la nostra condizione di arresto -

575
00:45:58,140 --> 00:46:01,870
 quando abbiamo effettivamente lavorato con l'esempio a mano -

576
00:46:01,870 --> 00:46:03,960
è stato quando abbiamo incontrato un nodo nullo,

577
00:46:03,960 --> 00:46:05,480
non quando abbiamo guardato un bambino nullo,

578
00:46:05,480 --> 00:46:09,620
ma quando abbiamo effettivamente trasferiti in un nodo dell'albero

579
00:46:09,620 --> 00:46:12,640
e ha scoperto che siamo in un nodo nullo.

580
00:46:12,640 --> 00:46:20,720
Stiamo andando a scorrere fino a cur non è uguale a null.

581
00:46:20,720 --> 00:46:22,920
E che cosa abbiamo intenzione di fare?

582
00:46:22,920 --> 00:46:31,610
Stiamo andando a verificare se (corr -> Valore ==),

583
00:46:31,610 --> 00:46:35,160
allora sappiamo che abbiamo effettivamente trovato il nodo che stiamo cercando.

584
00:46:35,160 --> 00:46:40,450
Così qui, siamo in grado di restituire true.

585
00:46:40,450 --> 00:46:49,830
Altrimenti, vogliamo vedere se il valore è inferiore al valore.

586
00:46:49,830 --> 00:46:53,850
Se il valore del nodo corrente è inferiore al valore che stiamo cercando,

587
00:46:53,850 --> 00:46:57,280
stiamo andando a spostarsi verso destra.

588
00:46:57,280 --> 00:47:10,600
Quindi, cur cur = -> right_child, e in caso contrario, abbiamo intenzione di spostarsi a sinistra.

589
00:47:10,600 --> 00:47:17,480
cur = cur -> left_child;. Abbastanza semplice.

590
00:47:17,480 --> 00:47:22,830
>> Probabilmente riconoscere il ciclo che sembra molto simile a questo da

591
00:47:22,830 --> 00:47:27,580
ricerca binaria in precedenza nel termine, salvo poi abbiamo a che fare con basse, medie e alte.

592
00:47:27,580 --> 00:47:30,000
Qui, non ci resta che guardare un valore corrente,

593
00:47:30,000 --> 00:47:31,930
quindi è bello e semplice.

594
00:47:31,930 --> 00:47:34,960
Facciamo in modo che questo codice funziona.

595
00:47:34,960 --> 00:47:42,780
Per prima cosa, assicurarsi che compila. Sembra che lo fa.

596
00:47:42,780 --> 00:47:47,920
Proviamo eseguirlo.

597
00:47:47,920 --> 00:47:50,160
E in effetti, esso stampa tutto quello che ci aspettavamo.

598
00:47:50,160 --> 00:47:54,320
Essa trova 6 nella struttura, non trova 10 perché 10 non è nella struttura,

599
00:47:54,320 --> 00:47:57,740
e non riesce a trovare uno o perché uno non è anche nella struttura.

600
00:47:57,740 --> 00:48:01,420
Cool stuff.

601
00:48:01,420 --> 00:48:04,470
>> Va bene. Torniamo alle nostre specifiche e vedere cosa c'è dopo.

602
00:48:04,470 --> 00:48:07,990
Ora, vuole aggiungere un po 'di nodi in più per il nostro albero.

603
00:48:07,990 --> 00:48:11,690
Vuole aggiungere 5, 2, e 8, e fare in modo che il nostro contiene il codice

604
00:48:11,690 --> 00:48:13,570
funziona ancora come previsto.

605
00:48:13,570 --> 00:48:14,900
Andiamo a farlo.

606
00:48:14,900 --> 00:48:19,430
A questo punto, piuttosto che fare quella copia fastidioso e incolla di nuovo,

607
00:48:19,430 --> 00:48:23,770
cerchiamo di scrivere una funzione per creare effettivamente un nodo.

608
00:48:23,770 --> 00:48:27,740
Se scorrere verso il basso fino alla principale, si vede che abbiamo fatto questo

609
00:48:27,740 --> 00:48:31,210
codice molto simile più e più volte ogni volta che vogliamo creare un nodo.

610
00:48:31,210 --> 00:48:39,540
>> Facciamo scrivere una funzione che effettivamente creare un nodo per noi e restituirlo.

611
00:48:39,540 --> 00:48:41,960
Io vado a chiamare build_node.

612
00:48:41,960 --> 00:48:45,130
Ho intenzione di costruire un nodo con un valore particolare.

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

614
00:48:51,040 --> 00:48:56,600
La prima cosa che ho intenzione di fare è in realtà creare spazio per il nodo sul mucchio.

615
00:48:56,600 --> 00:49:05,400
Quindi, il nodo * n = malloc (sizeof (nodo)); n -> Valore = valore;

616
00:49:05,400 --> 00:49:14,960
e poi qui, sto solo andando per inizializzare tutti i campi da valori appropriati.

617
00:49:14,960 --> 00:49:22,500
E alla fine, torneremo il nostro nodo.

618
00:49:22,500 --> 00:49:28,690
Va bene. Una cosa da notare è che questa funzione proprio qui

619
00:49:28,690 --> 00:49:34,320
sta per tornare un puntatore alla memoria che è stato heap allocata.

620
00:49:34,320 --> 00:49:38,880
Il bello di questo è che ora questo nodo -

621
00:49:38,880 --> 00:49:42,420
dobbiamo dichiarare sul mucchio perché se ha dichiarato in pila

622
00:49:42,420 --> 00:49:45,050
non sarebbe in grado di farlo in questa funzione come questa.

623
00:49:45,050 --> 00:49:47,690
Quel ricordo usciva di portata

624
00:49:47,690 --> 00:49:51,590
e sarebbe valida se abbiamo tentato di accedere in seguito.

625
00:49:51,590 --> 00:49:53,500
Dal momento che stiamo dichiarando heap allocata la memoria,

626
00:49:53,500 --> 00:49:55,830
stiamo andando a prendersi cura di liberare in un secondo momento

627
00:49:55,830 --> 00:49:58,530
per il nostro programma di non perdere la memoria.

628
00:49:58,530 --> 00:50:01,270
Abbiamo andare in barca sul che per tutto il resto del codice

629
00:50:01,270 --> 00:50:02,880
solo per semplicità, al momento,

630
00:50:02,880 --> 00:50:05,610
ma se mai scrivere una funzione che assomiglia a questo

631
00:50:05,610 --> 00:50:10,370
dove hai - alcuni lo chiamano una malloc o realloc all'interno -

632
00:50:10,370 --> 00:50:14,330
si vuole fare in modo che si mette una sorta di commento qui che dice,

633
00:50:14,330 --> 00:50:29,970
hey, sai, restituisce un heap-allocato nodo inizializzato con il valore passato.

634
00:50:29,970 --> 00:50:33,600
E poi si vuole fare in modo che si inserisce in una sorta di nota che dice:

635
00:50:33,600 --> 00:50:41,720
il chiamante deve liberare la memoria restituita.

636
00:50:41,720 --> 00:50:45,450
In questo modo, se qualcuno va mai e utilizza tale funzione,

637
00:50:45,450 --> 00:50:48,150
sanno che tutto ciò che tornare da quella funzione

638
00:50:48,150 --> 00:50:50,870
ad un certo punto dovrà essere liberato.

639
00:50:50,870 --> 00:50:53,940
>> Partendo dal presupposto che tutto va bene e bene qui,

640
00:50:53,940 --> 00:51:02,300
si può scendere nel nostro codice e sostituire tutte queste linee qui

641
00:51:02,300 --> 00:51:05,410
alle chiamate verso la nostra funzione di nodo di compilazione.

642
00:51:05,410 --> 00:51:08,170
Facciamo davvero in fretta.

643
00:51:08,170 --> 00:51:15,840
L'unica parte che non stiamo andando a sostituire questa parte qui

644
00:51:15,840 --> 00:51:18,520
nella parte inferiore dove abbiamo effettivamente cablaggio degli nodi per puntare a vicenda,

645
00:51:18,520 --> 00:51:21,030
perché non possiamo fare nella nostra funzione.

646
00:51:21,030 --> 00:51:37,400
Ma, facciamo root = build_node (7); nodo * tre = build_node (3);

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

648
00:51:47,980 --> 00:51:52,590
E ora, abbiamo anche voluto aggiungere nodi per -

649
00:51:52,590 --> 00:52:03,530
nodo * = build_node cinque (5); nodo * = build_node otto (8);

650
00:52:03,530 --> 00:52:09,760
e quello che era l'altro nodo? Vediamo qui. Abbiamo voluto aggiungere anche un 2 -

651
00:52:09,760 --> 00:52:20,280
nodo * due = build_node (2),.

652
00:52:20,280 --> 00:52:26,850
Va bene. A questo punto, sappiamo che abbiamo il 7, il 3, il 9 e il 6

653
00:52:26,850 --> 00:52:30,320
tutti collegati in modo appropriato, ma per quanto riguarda il 5, l'8 e il 2?

654
00:52:30,320 --> 00:52:33,550
Per tenere tutto nel corretto ordine,

655
00:52:33,550 --> 00:52:39,230
sappiamo che tre figlio destro è pari a 6.

656
00:52:39,230 --> 00:52:40,890
Quindi, se abbiamo intenzione di aggiungere il 5,

657
00:52:40,890 --> 00:52:46,670
il 5 appartiene anche nel lato destro dell'albero di cui 3 è la radice,

658
00:52:46,670 --> 00:52:50,440
quindi 5 appartiene come il figlio sinistro di 6.

659
00:52:50,440 --> 00:52:58,650
Possiamo farlo dicendo, sei -> left_child = cinque;

660
00:52:58,650 --> 00:53:10,790
e poi l'8 appartiene come il figlio sinistro di 9, in modo da nove -> left_child = otto;

661
00:53:10,790 --> 00:53:22,190
e poi 2 è il figlio sinistro di 3, in modo che possiamo farlo qui - te -> left_child = due;.

662
00:53:22,190 --> 00:53:27,730
Se non riusciva a seguire con questo, ti consiglio di disegnare voi stessi.

663
00:53:27,730 --> 00:53:35,660
>> Va bene. Salviamo questo. Usciamo e assicurarsi che compila,

664
00:53:35,660 --> 00:53:40,760
e poi possiamo aggiungere nelle nostre chiamate contiene.

665
00:53:40,760 --> 00:53:44,120
Sembra che tutto ciò che compila ancora.

666
00:53:44,120 --> 00:53:51,790
Entriamo e aggiungere in qualche contiene chiamate.

667
00:53:51,790 --> 00:53:59,640
Ancora una volta, ho intenzione di fare un po 'di copia e incolla.

668
00:53:59,640 --> 00:54:15,860
Ora la ricerca di 5, 8, e 2. Va bene.

669
00:54:15,860 --> 00:54:28,330
Facciamo in modo che tutto questo sembra buono ancora. Fantastico! Salvare e uscire.

670
00:54:28,330 --> 00:54:33,220
Ora facciamo, compilare, e ora corriamo.

671
00:54:33,220 --> 00:54:37,540
Dai risultati, sembra che tutto funziona solo bello e bene.

672
00:54:37,540 --> 00:54:41,780
Fantastico! Così ora abbiamo le nostre contiene una funzione scritta.

673
00:54:41,780 --> 00:54:46,160
Andiamo avanti e iniziare a lavorare su come inserire i nodi nella struttura

674
00:54:46,160 --> 00:54:50,000
in quanto, come lo stiamo facendo in questo momento, le cose non sono molto belle.

675
00:54:50,000 --> 00:54:52,280
>> Se torniamo alle specifiche,

676
00:54:52,280 --> 00:55:00,540
ci chiede di scrivere una funzione chiamata inserire - ancora una volta, la restituzione di un bool

677
00:55:00,540 --> 00:55:04,400
per se o non si potesse davvero inserire il nodo nella struttura -

678
00:55:04,400 --> 00:55:07,710
e quindi il valore da inserire l'albero viene specificato come

679
00:55:07,710 --> 00:55:11,060
l'unico argomento per la nostra funzione di inserimento.

680
00:55:11,060 --> 00:55:18,180
Torneremo vero se potremmo davvero inserire il valore del nodo che contiene nella struttura,

681
00:55:18,180 --> 00:55:20,930
il che significa che, uno, aveva memoria sufficiente,

682
00:55:20,930 --> 00:55:24,840
e poi due, quel nodo non è già presente nella struttura in quanto -

683
00:55:24,840 --> 00:55:32,170
ricordate, non stiamo andando ad avere valori duplicati nella struttura, giusto per rendere le cose semplici.

684
00:55:32,170 --> 00:55:35,590
Va bene. Eseguire il codice.

685
00:55:35,590 --> 00:55:44,240
Aprirlo. Zoom in un po ', quindi scorrere verso il basso.

686
00:55:44,240 --> 00:55:47,220
Mettiamo la funzione di inserimento a destra sopra le contains.

687
00:55:47,220 --> 00:55:56,360
Anche in questo caso, sta andando essere chiamato inserto bool (int valore).

688
00:55:56,360 --> 00:56:01,840
Dategli un po 'più di spazio, e poi, come impostazione predefinita,

689
00:56:01,840 --> 00:56:08,870
mettiamo in return false alla fine.

690
00:56:08,870 --> 00:56:22,620
Ora, giù in fondo, andiamo avanti e invece di costruzione manuale dei nodi

691
00:56:22,620 --> 00:56:27,900
in noi stessi e il cablaggio principale loro fino al punto l'un l'altro come stiamo facendo,

692
00:56:27,900 --> 00:56:30,600
faremo affidamento sulla nostra funzione di inserimento di farlo.

693
00:56:30,600 --> 00:56:35,510
Non si affidano alla nostra funzione di inserimento di costruire l'intero albero da zero appena ancora,

694
00:56:35,510 --> 00:56:39,970
ma ci sbarazzarsi di queste linee - we'll commentare queste righe -

695
00:56:39,970 --> 00:56:43,430
che costruire i nodi 5, 8, e 2.

696
00:56:43,430 --> 00:56:55,740
E invece, dovremo inserire le chiamate alla nostra funzione di insert

697
00:56:55,740 --> 00:57:01,280
fare in modo che che funziona realmente.

698
00:57:01,280 --> 00:57:05,840
Ci siamo.

699
00:57:05,840 --> 00:57:09,300
>> Ora abbiamo commentato queste righe.

700
00:57:09,300 --> 00:57:13,700
Abbiamo solo 7, 3, 9, e 6 nel nostro albero a questo punto.

701
00:57:13,700 --> 00:57:18,870
Per assicurarsi che tutto questo è lavoro,

702
00:57:18,870 --> 00:57:25,050
siamo in grado di eseguire lo zoom indietro, fare il nostro albero binario,

703
00:57:25,050 --> 00:57:30,750
eseguirlo, e possiamo vedere che contiene ora ci dice che siamo totalmente di destra -

704
00:57:30,750 --> 00:57:33,110
5, 8, e 2 non sono più nella struttura.

705
00:57:33,110 --> 00:57:37,960
Torna nel codice,

706
00:57:37,960 --> 00:57:41,070
e come facciamo a inserire?

707
00:57:41,070 --> 00:57:46,290
Ricordate quello che abbiamo fatto quando eravamo in realtà l'inserimento di 5, 8, e 2 in precedenza.

708
00:57:46,290 --> 00:57:50,100
Abbiamo giocato quel gioco Plinko dove siamo partiti alla radice,

709
00:57:50,100 --> 00:57:52,780
è andato giù quello albero uno per uno

710
00:57:52,780 --> 00:57:54,980
finché non abbiamo trovato la distanza appropriata,

711
00:57:54,980 --> 00:57:57,570
e poi cablato nel nodo nel punto appropriato.

712
00:57:57,570 --> 00:57:59,480
Stiamo andando a fare la stessa cosa.

713
00:57:59,480 --> 00:58:04,070
Questo è fondamentalmente come scrivere il codice che abbiamo usato nella funzione contiene

714
00:58:04,070 --> 00:58:05,910
per trovare il punto in cui il nodo dovrebbe essere,

715
00:58:05,910 --> 00:58:10,560
e poi stiamo solo andando a inserire il nodo proprio lì.

716
00:58:10,560 --> 00:58:17,000
Cominciamo a farlo.

717
00:58:17,000 --> 00:58:24,200
>> Così abbiamo un nodo * cur = root, stiamo solo andando a seguire la contiene il codice

718
00:58:24,200 --> 00:58:26,850
fino a trovare che non va a buon fine per noi.

719
00:58:26,850 --> 00:58:32,390
Stiamo per passare attraverso l'albero, mentre l'elemento corrente non è null,

720
00:58:32,390 --> 00:58:45,280
e se troviamo valore corrente è uguale al valore che stiamo cercando di inserire -

721
00:58:45,280 --> 00:58:49,600
bene, questo è uno dei casi in cui non potrebbe effettivamente inserire il nodo

722
00:58:49,600 --> 00:58:52,730
nell'albero, perché questo significa che abbiamo un valore duplicato.

723
00:58:52,730 --> 00:58:59,010
Qui stiamo effettivamente andando a restituire false.

724
00:58:59,010 --> 00:59:08,440
Ora il resto, se il valore corrente è inferiore al valore,

725
00:59:08,440 --> 00:59:10,930
ora sappiamo che ci si sposta verso destra

726
00:59:10,930 --> 00:59:17,190
 perché il valore appartiene nella metà destra della struttura corrente.

727
00:59:17,190 --> 00:59:30,110
In caso contrario, andremo a spostarsi a sinistra.

728
00:59:30,110 --> 00:59:37,980
Questo è fondamentalmente nostri Funzione contains proprio lì.

729
00:59:37,980 --> 00:59:41,820
>> A questo punto, una volta che abbiamo completato questo ciclo while,

730
00:59:41,820 --> 00:59:47,350
il nostro puntatore corrente sta per puntare a null

731
00:59:47,350 --> 00:59:51,540
se la funzione non è già tornato.

732
00:59:51,540 --> 00:59:58,710
Stiamo quindi con corr nel punto in cui si vuole inserire il nuovo nodo.

733
00:59:58,710 --> 01:00:05,210
Che cosa resta da fare è quello di costruire in realtà il nuovo nodo,

734
01:00:05,210 --> 01:00:08,480
che si può fare abbastanza facilmente.

735
01:00:08,480 --> 01:00:14,930
Possiamo usare il nostro super-comoda la funzione del nodo di generazione,

736
01:00:14,930 --> 01:00:17,210
e qualcosa che non abbiamo fatto in precedenza -

737
01:00:17,210 --> 01:00:21,400
abbiamo solo tipo di dato per scontato, ma ora faremo solo per assicurarsi -

738
01:00:21,400 --> 01:00:27,130
ci prova per assicurarsi che il valore restituito da nuovo nodo era in realtà

739
01:00:27,130 --> 01:00:33,410
non nullo, perché non si vuole avviare l'accesso che la memoria se è null.

740
01:00:33,410 --> 01:00:39,910
Possiamo provare a fare in modo che il nuovo nodo non è uguale a null.

741
01:00:39,910 --> 01:00:42,910
O invece, possiamo solo vedere se è effettivamente nullo,

742
01:00:42,910 --> 01:00:52,120
e se è nullo, allora possiamo semplicemente restituire false presto.

743
01:00:52,120 --> 01:00:59,090
>> A questo punto, dobbiamo cablare nuovo nodo nella sua posizione appropriata nella struttura.

744
01:00:59,090 --> 01:01:03,510
Se guardiamo indietro a principale e dove eravamo in realtà cablaggio in valori prima,

745
01:01:03,510 --> 01:01:08,470
vediamo che il modo in cui lo stavamo facendo quando abbiamo voluto mettere 3 nella struttura ad albero

746
01:01:08,470 --> 01:01:11,750
è stato abbiamo accesso al figlio sinistro della radice.

747
01:01:11,750 --> 01:01:14,920
Quando abbiamo messo 9 nella struttura, abbiamo dovuto accedere al figlio destro della radice.

748
01:01:14,920 --> 01:01:21,030
Abbiamo dovuto avere un puntatore al genitore, al fine di mettere un nuovo valore nella struttura.

749
01:01:21,030 --> 01:01:24,430
Scorrendo il backup da inserire, che non sta andando a lavorare abbastanza qui

750
01:01:24,430 --> 01:01:27,550
perché non si dispone di un puntatore genitore.

751
01:01:27,550 --> 01:01:31,650
Quello che vogliamo essere in grado di fare è, a questo punto,

752
01:01:31,650 --> 01:01:37,080
controllare il valore del genitore e vedere - beh, cavolo,

753
01:01:37,080 --> 01:01:41,990
se il valore del genitore è inferiore al valore corrente,

754
01:01:41,990 --> 01:01:54,440
poi figlio destro del genitore dovrebbe essere il nuovo nodo;

755
01:01:54,440 --> 01:02:07,280
in caso contrario, figlio sinistro del genitore dovrebbe essere il nuovo nodo.

756
01:02:07,280 --> 01:02:10,290
Ma, non abbiamo questo puntatore genitore ancora abbastanza.

757
01:02:10,290 --> 01:02:15,010
>> Per farlo, in realtà stiamo andando ad avere per tenerne traccia come andiamo attraverso l'albero

758
01:02:15,010 --> 01:02:18,440
e trovare il punto appropriato nel nostro ciclo precedente.

759
01:02:18,440 --> 01:02:26,840
Possiamo farlo scorrendo indietro fino alla cima della nostra funzione di insert

760
01:02:26,840 --> 01:02:32,350
e il monitoraggio di un altro variabile puntatore chiamato il padre.

761
01:02:32,350 --> 01:02:39,340
Stiamo per impostarlo uguale a null inizialmente,

762
01:02:39,340 --> 01:02:43,640
e poi ogni volta che andiamo attraverso l'albero,

763
01:02:43,640 --> 01:02:51,540
stiamo andando a impostare il puntatore del genitore in base al corrente del puntatore.

764
01:02:51,540 --> 01:02:59,140
Imposta raccolta principale pari a cur.

765
01:02:59,140 --> 01:03:02,260
In questo modo, ogni volta che passare attraverso,

766
01:03:02,260 --> 01:03:05,550
stiamo andando a garantire che la corrente del puntatore viene incrementato

767
01:03:05,550 --> 01:03:12,640
il puntatore genitore segue - solo un livello superiore rispetto al puntatore corrente nella struttura.

768
01:03:12,640 --> 01:03:17,370
Che tutto sembra piuttosto buono.

769
01:03:17,370 --> 01:03:22,380
>> Penso che l'unica cosa che dobbiamo provare a modificare questa build è nullo nodo di ritorno.

770
01:03:22,380 --> 01:03:25,380
Al fine di ottenere costruire nodo realmente successo restituire null,

771
01:03:25,380 --> 01:03:31,060
dovremo modificare il codice,

772
01:03:31,060 --> 01:03:37,270
perché qui, non abbiamo mai provato a fare in modo che malloc ha restituito un puntatore valido.

773
01:03:37,270 --> 01:03:53,390
Quindi, se (n = NULL!), Poi -

774
01:03:53,390 --> 01:03:55,250
se malloc ha restituito un puntatore valido, poi ci inizializzarlo;

775
01:03:55,250 --> 01:04:02,540
in caso contrario, ci limiteremo a tornare e che finirà per tornare nulla per noi.

776
01:04:02,540 --> 01:04:13,050
Ora tutto sembra piuttosto buono. Facciamo in modo che questo compila in realtà.

777
01:04:13,050 --> 01:04:22,240
Fai albero binario, e oh, abbiamo un po 'di roba in corso qui.

778
01:04:22,240 --> 01:04:29,230
>> Abbiamo una dichiarazione implicita di funzione di costruzione del nodo.

779
01:04:29,230 --> 01:04:31,950
Anche in questo caso, con questi compilatori, stiamo per iniziare al top.

780
01:04:31,950 --> 01:04:36,380
Cosa che deve dire è che sto chiamando costruire nodo prima di aver effettivamente dichiarato.

781
01:04:36,380 --> 01:04:37,730
Torniamo al codice molto velocemente.

782
01:04:37,730 --> 01:04:43,510
Scorrere verso il basso, e abbastanza sicuro, la mia funzione di insert è dichiarata

783
01:04:43,510 --> 01:04:47,400
al di sopra della funzione del nodo di generazione,

784
01:04:47,400 --> 01:04:50,070
ma sto cercando di usare costruire nodo all'interno dell'inserto.

785
01:04:50,070 --> 01:05:06,610
Ho intenzione di andare a copia - e quindi incollare il modo in cui la funzione del nodo di generazione qui in alto.

786
01:05:06,610 --> 01:05:11,750
In questo modo, si spera che funzioni. Diamo questo un altro andare.

787
01:05:11,750 --> 01:05:18,920
Ora compila tutto. Tutto è buono.

788
01:05:18,920 --> 01:05:21,640
>> Ma a questo punto, non abbiamo effettivamente chiamato la nostra funzione di inserimento.

789
01:05:21,640 --> 01:05:26,510
Sappiamo solo che si compila, quindi cerchiamo di andare a mettere un po 'le chiamate trovi

790
01:05:26,510 --> 01:05:28,240
Facciamo che nella nostra funzione principale.

791
01:05:28,240 --> 01:05:32,390
Qui, ha commentato su 5, 8, e 2,

792
01:05:32,390 --> 01:05:36,680
e poi non li cablare qui.

793
01:05:36,680 --> 01:05:41,640
Facciamo alcune chiamate di inserire,

794
01:05:41,640 --> 01:05:46,440
e cerchiamo di utilizzare lo stesso tipo di cose che abbiamo usato

795
01:05:46,440 --> 01:05:52,810
quando abbiamo fatto queste chiamate printf per fare in modo che tutto ciò che si ha inserito correttamente.

796
01:05:52,810 --> 01:06:00,550
Ho intenzione di copiare e incollare,

797
01:06:00,550 --> 01:06:12,450
e invece di contiene andremo a fare inserire.

798
01:06:12,450 --> 01:06:30,140
E invece di 6, 10, e 1, che andremo a usare 5, 8, e 2.

799
01:06:30,140 --> 01:06:37,320
Questo dovrebbe auspicabilmente inserire 5, 8, e 2 nella struttura.

800
01:06:37,320 --> 01:06:44,050
Compilare. Tutto è buono. Ora ci troveremo a eseguire il nostro programma.

801
01:06:44,050 --> 01:06:47,330
>> Tutto ciò che ha restituito false.

802
01:06:47,330 --> 01:06:53,830
Quindi, 5, 8, e 2 non è andato, e sembra che contiene non li ha trovato né.

803
01:06:53,830 --> 01:06:58,890
Cosa sta succedendo? Andiamo diminuire.

804
01:06:58,890 --> 01:07:02,160
Il primo problema era che sembrava inserto per restituire false,

805
01:07:02,160 --> 01:07:08,750
e sembra che è perché abbiamo lasciato nella nostra chiamata return false,

806
01:07:08,750 --> 01:07:14,590
e non abbiamo mai restituito true.

807
01:07:14,590 --> 01:07:17,880
Siamo in grado di configurare il monitoraggio.

808
01:07:17,880 --> 01:07:25,290
Il secondo problema è, ora, anche se lo facciamo - salvare questo, uscire da questa,

809
01:07:25,290 --> 01:07:34,530
eseguire make, farlo compilare, quindi eseguirlo -

810
01:07:34,530 --> 01:07:37,670
vediamo che qualcosa è successo qui.

811
01:07:37,670 --> 01:07:42,980
Il 5, 8, e 2 non sono mai stati ancora trovati nella struttura.

812
01:07:42,980 --> 01:07:44,350
Allora, che cosa sta succedendo?

813
01:07:44,350 --> 01:07:45,700
>> Diamo uno sguardo a questo nel codice.

814
01:07:45,700 --> 01:07:49,790
Vediamo se siamo in grado di capirlo.

815
01:07:49,790 --> 01:07:57,940
Si comincia con il genitore non essere nulla.

816
01:07:57,940 --> 01:07:59,510
Abbiamo impostato il puntatore corrente pari al puntatore radice,

817
01:07:59,510 --> 01:08:04,280
e stiamo andando a lavorare il nostro percorso attraverso l'albero.

818
01:08:04,280 --> 01:08:08,650
Se il nodo corrente non è nullo, allora sappiamo che siamo in grado di spostare verso il basso un po '.

819
01:08:08,650 --> 01:08:12,330
Abbiamo impostato il nostro puntatore del genitore di essere uguale alla corrente del puntatore,

820
01:08:12,330 --> 01:08:15,420
controllato il valore - se i valori sono gli stessi che ha restituito false.

821
01:08:15,420 --> 01:08:17,540
Se i valori sono meno ci siamo spostati a destra;

822
01:08:17,540 --> 01:08:20,399
in caso contrario, ci siamo spostati a sinistra.

823
01:08:20,399 --> 01:08:24,220
Poi costruire un nodo. Io lo zoom un po '.

824
01:08:24,220 --> 01:08:31,410
E qui, stiamo andando a cercare di collegare i valori sia la stessa.

825
01:08:31,410 --> 01:08:37,250
Cosa sta succedendo? Vediamo se forse Valgrind ci può dare un suggerimento.

826
01:08:37,250 --> 01:08:43,910
>> Mi piace usare Valgrind Valgrind solo perché corre molto in fretta

827
01:08:43,910 --> 01:08:46,729
e ti dice se ci sono errori di memoria.

828
01:08:46,729 --> 01:08:48,300
Quando corriamo Valgrind sul codice,

829
01:08:48,300 --> 01:08:55,859
come si può vedere colpo here--Valgrind./binary_tree--and destra entrare.

830
01:08:55,859 --> 01:09:03,640
Si vede che non abbiamo avuto alcun errore di memoria, in modo che sembra che tutto va bene fino ad ora.

831
01:09:03,640 --> 01:09:07,529
Abbiamo alcuni problemi di memoria, che sappiamo, perché non siamo

832
01:09:07,529 --> 01:09:08,910
accadendo per liberare tutti i nostri nodi.

833
01:09:08,910 --> 01:09:13,050
Proviamo esecuzione GDB per vedere cosa sta realmente succedendo.

834
01:09:13,050 --> 01:09:20,010
Faremo gdb. / Binary_tree. E 'avviato bene.

835
01:09:20,010 --> 01:09:23,670
Mettiamo da un punto di interruzione su inserto.

836
01:09:23,670 --> 01:09:28,600
Corriamo.

837
01:09:28,600 --> 01:09:31,200
Sembra che non abbiamo mai chiamato inserto.

838
01:09:31,200 --> 01:09:39,410
Sembra che il problema era solo che quando ho cambiato qui in main -

839
01:09:39,410 --> 01:09:44,279
tutte queste chiamate da printf contiene -

840
01:09:44,279 --> 01:09:56,430
Non ho mai veramente cambiato questi chiamare inserto.

841
01:09:56,430 --> 01:10:01,660
Ora cerchiamo di fare un tentativo. Facciamo compilare.

842
01:10:01,660 --> 01:10:09,130
Tutto sembra buono lì. Ora provare a eseguirlo, vedere cosa succede.

843
01:10:09,130 --> 01:10:13,320
Va bene! Tutto sembra piuttosto buona.

844
01:10:13,320 --> 01:10:18,130
>> L'ultima cosa da pensare è, ci sono dei casi limite a questo foglietto?

845
01:10:18,130 --> 01:10:23,170
E si scopre che, beh, quello caso limite che è sempre interessante a cui pensare

846
01:10:23,170 --> 01:10:26,250
è, che cosa succede se il vostro albero è vuoto e si chiama questa funzione insert?

847
01:10:26,250 --> 01:10:30,330
Funzionerà? Bene, vediamo di fare un tentativo.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Il modo in cui andremo a testare questa è, stiamo per andare in fondo alla nostra funzione principale,

850
01:10:35,810 --> 01:10:41,690
e piuttosto che il cablaggio questi nodi in questo modo,

851
01:10:41,690 --> 01:10:56,730
stiamo solo andando a commentare l'intera cosa,

852
01:10:56,730 --> 01:11:02,620
e invece di cablaggio dei nodi di noi stessi,

853
01:11:02,620 --> 01:11:09,400
possiamo in realtà solo andare avanti e cancellare tutto questo.

854
01:11:09,400 --> 01:11:17,560
Stiamo andando a fare tutto ciò che una chiamata a inserire.

855
01:11:17,560 --> 01:11:49,020
Quindi, cerchiamo di fare - invece di 5, 8, e 2, abbiamo intenzione di inserire 7, 3, e 9.

856
01:11:49,020 --> 01:11:58,440
E poi ci vogliono anche inserire 6 pure.

857
01:11:58,440 --> 01:12:05,190
Salva. Quit. Crea albero binario.

858
01:12:05,190 --> 01:12:08,540
Si compila tutti.

859
01:12:08,540 --> 01:12:10,320
Noi possiamo solo correre è come e vedere cosa succede,

860
01:12:10,320 --> 01:12:12,770
ma è anche sarà molto importante per fare in modo che

861
01:12:12,770 --> 01:12:14,740
Non ci sono errori di memoria,

862
01:12:14,740 --> 01:12:16,840
dal momento che questo è uno dei nostri casi limite che siamo a conoscenza.

863
01:12:16,840 --> 01:12:20,150
>> Facciamo in modo che funzioni bene sotto Valgrind,

864
01:12:20,150 --> 01:12:28,310
che faremo lanciando solamente Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Sembra che in effetti hanno un errore da un contesto -

866
01:12:31,110 --> 01:12:33,790
abbiamo questa segmentation fault.

867
01:12:33,790 --> 01:12:36,690
Che cosa è successo?

868
01:12:36,690 --> 01:12:41,650
Valgrind realtà ci dice dove si trova.

869
01:12:41,650 --> 01:12:43,050
Zoom indietro un po '.

870
01:12:43,050 --> 01:12:46,040
Sembra che sta accadendo nella nostra funzione di inserimento,

871
01:12:46,040 --> 01:12:53,420
dove abbiamo una lettura valida di dimensione 4 a inserto, linea 60.

872
01:12:53,420 --> 01:13:03,590
Torniamo indietro e vedere cosa sta succedendo qui.

873
01:13:03,590 --> 01:13:05,350
Zoom indietro molto veloce.

874
01:13:05,350 --> 01:13:14,230
Voglio fare in modo che non va al bordo dello schermo, in modo che possiamo vedere tutto.

875
01:13:14,230 --> 01:13:18,760
Tirare che tra un po '. Va bene.

876
01:13:18,760 --> 01:13:35,030
Scorrere verso il basso, e il problema è proprio qui.

877
01:13:35,030 --> 01:13:40,120
Cosa succede se ci mettiamo e il nostro nodo corrente è già nullo,

878
01:13:40,120 --> 01:13:44,010
il nostro nodo padre è nullo, quindi se guardiamo in alto, proprio qui -

879
01:13:44,010 --> 01:13:47,340
se mai questo ciclo while viene eseguito in realtà

880
01:13:47,340 --> 01:13:52,330
perché il nostro valore corrente è nullo - la nostra radice è null in modo corrente è nullo -

881
01:13:52,330 --> 01:13:57,810
poi mai la nostra casa madre viene impostata al corrente o su un valore valido,

882
01:13:57,810 --> 01:14:00,580
così, genitore anche essere nullo.

883
01:14:00,580 --> 01:14:03,700
Abbiamo bisogno di ricordare per verificare che

884
01:14:03,700 --> 01:14:08,750
per il momento abbiamo venire qui, e iniziamo l'accesso valore del livello superiore.

885
01:14:08,750 --> 01:14:13,190
Allora, che cosa succede? Beh, se il genitore è nullo -

886
01:14:13,190 --> 01:14:17,990
if (NULL == genitore) - allora sappiamo che

887
01:14:17,990 --> 01:14:19,530
non ci deve essere nulla nella struttura.

888
01:14:19,530 --> 01:14:22,030
Dobbiamo cercare di inserirlo alla radice.

889
01:14:22,030 --> 01:14:32,570
Possiamo farlo semplicemente impostando la radice pari al nuovo nodo.

890
01:14:32,570 --> 01:14:40,010
Quindi a questo punto, in realtà non vogliono passare attraverso queste altre cose.

891
01:14:40,010 --> 01:14:44,780
Invece, proprio qui, si può fare sia un else-if-else,

892
01:14:44,780 --> 01:14:47,610
o potremmo combinare tutto qui in un altro,

893
01:14:47,610 --> 01:14:56,300
ma qui ci limiteremo a usare altro e farlo in quel modo.

894
01:14:56,300 --> 01:14:59,030
Ora, stiamo andando a test per assicurarsi che il nostro genitore non è nullo

895
01:14:59,030 --> 01:15:02,160
prima di allora in realtà cercando di accedere ai suoi campi.

896
01:15:02,160 --> 01:15:05,330
Questo ci aiuterà a evitare l'errore di segmentazione.

897
01:15:05,330 --> 01:15:14,740
Così, abbiamo smesso, zoom out, compilare, eseguire.

898
01:15:14,740 --> 01:15:18,130
>> Nessun errore, ma abbiamo ancora un sacco di perdite di memoria

899
01:15:18,130 --> 01:15:20,650
perché non liberare tutti i nostri nodi.

900
01:15:20,650 --> 01:15:24,350
Ma, se andiamo qui e guardiamo la nostra stampa,

901
01:15:24,350 --> 01:15:30,880
vediamo che, beh, sembra che tutti i nostri inserti stavano tornando vero, che è buono.

902
01:15:30,880 --> 01:15:33,050
Gli inserti sono tutte vere,

903
01:15:33,050 --> 01:15:36,670
e poi le chiamate alle contiene anche vero.

904
01:15:36,670 --> 01:15:41,510
>> Buon lavoro! Sembra che abbiamo scritto correttamente inserto.

905
01:15:41,510 --> 01:15:47,430
Questo è tutto quello che abbiamo per la specifica problema di questa settimana Set.

906
01:15:47,430 --> 01:15:51,720
Una sfida divertente a cui pensare è come si dovrebbe effettivamente andare in

907
01:15:51,720 --> 01:15:55,340
e libera tutti i nodi di questo albero.

908
01:15:55,340 --> 01:15:58,830
Possiamo farlo un certo numero di modi diversi,

909
01:15:58,830 --> 01:16:01,930
ma lascio a voi di sperimentare,

910
01:16:01,930 --> 01:16:06,080
e come una sfida divertente, cercare di fare in modo che si può fare in modo

911
01:16:06,080 --> 01:16:09,490
che tale relazione Valgrind non ha prodotto alcun errore e senza perdite.

912
01:16:09,490 --> 01:16:12,880
>> Buona fortuna per il problema di questa settimana insieme codifica di Huffman,

913
01:16:12,880 --> 01:16:14,380
e ci vediamo la prossima settimana!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]