1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Sekcio 7] [Less Komfortaj]

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

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

4
00:00:07,000 --> 00:00:09,080
>> Bonvenon Sekcio 7.

5
00:00:09,080 --> 00:00:11,330
Danke al uragano Sandy,

6
00:00:11,330 --> 00:00:13,440
anstataŭ havi normalan sekcio ĉi semajno,

7
00:00:13,440 --> 00:00:17,650
ni faras ĉi promeno-tra, tra la sekcio de demandoj.

8
00:00:17,650 --> 00:00:22,830
Mi tuj iros post kune kun la problemo Ŝanĝu 6 Specification,

9
00:00:22,830 --> 00:00:25,650
kaj irante tra ĉiuj el la demandoj en la

10
00:00:25,650 --> 00:00:27,770
Al Sekcio de Demandoj sekcio.

11
00:00:27,770 --> 00:00:30,940
Se vi renkontas demandoj,

12
00:00:30,940 --> 00:00:32,960
bonvolu afiŝi tiuj sur CS50 diskuti.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Ni komenci.

14
00:00:35,480 --> 00:00:40,780
Ĝuste nun mi rigardas paĝo 3 de la Problemo Ara Specification.

15
00:00:40,780 --> 00:00:44,110
Ni iras al unua komenci paroli pri duumaj arboj

16
00:00:44,110 --> 00:00:47,850
pro tio ke tiuj havas multe da graveco al ĉi tiu semajno problemo aro -

17
00:00:47,850 --> 00:00:49,950
la Huffman Arbo kodigo.

18
00:00:49,950 --> 00:00:55,000
Unu el la tre unua datumstrukturoj ni parolis pri la CS50 estis la tabelo.

19
00:00:55,000 --> 00:01:00,170
Memoru ke tabelo estas vico de eroj -

20
00:01:00,170 --> 00:01:04,019
ĉiuj de la sama tipo - stokita dekstra flanko de la alia en memoro.

21
00:01:04,019 --> 00:01:14,420
Se mi havas entjero tabelo, ke mi povas desegni uzante ĉi skatoloj-numerojn-entjeroj stilo -

22
00:01:14,420 --> 00:01:20,290
Diru Mi havas 5 en la unua skatolo, mi havas 7 en la dua,

23
00:01:20,290 --> 00:01:27,760
tiam mi havas 8, 10, kaj 20 en la fina skatolo.

24
00:01:27,760 --> 00:01:33,000
Memoru, la du vere bona aferojn pri ĉi tiu tabelo

25
00:01:33,000 --> 00:01:38,800
estas ke ni havas ĉi konstanta tempo aliron al iu aparta elemento

26
00:01:38,800 --> 00:01:40,500
 en la tabelo se ni scias lian indekso.

27
00:01:40,500 --> 00:01:44,670
Ekzemple, se mi volas kapti la tria elemento en la tabelo -

28
00:01:44,670 --> 00:01:47,870
ĉe indekso 2 uzante nian nulo-bazita indeksado sistemo -

29
00:01:47,870 --> 00:01:52,220
Mi laŭvorte nur devas fari simplan matematikan kalkulo,

30
00:01:52,220 --> 00:01:56,170
hop por tiu posteno en la tabelo,

31
00:01:56,170 --> 00:01:57,840
eltiri la 8 kiu stokas tie,

32
00:01:57,840 --> 00:01:59,260
kaj mi estas bona por iri.

33
00:01:59,260 --> 00:02:03,350
>> Unu el la malbonaj aferoj pri tiu tabelo - ke ni parolis pri

34
00:02:03,350 --> 00:02:05,010
kiam ni diskutis ligitaj listoj -

35
00:02:05,010 --> 00:02:09,120
estas ke se mi volas enmeti ero en ĉi tiun tabelo,

36
00:02:09,120 --> 00:02:11,090
Mi tuj devos fari iu movo ĉirkaŭe.

37
00:02:11,090 --> 00:02:12,940
Ekzemple, ĉi tabelo ĉi tie

38
00:02:12,940 --> 00:02:16,850
estas en ordo ordo - ordo en suprenira ordo -

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

40
00:02:19,440 --> 00:02:23,100
sed se mi volas enmeti la numero 9 en tiun tabelo,

41
00:02:23,100 --> 00:02:27,460
Mi tuj devos ŝanĝi kelkajn el la elementoj por fari spacon.

42
00:02:27,460 --> 00:02:30,440
Ni povas desegni tiun ĉi tie.

43
00:02:30,440 --> 00:02:35,650
Mi tuj devos kopii la 5, la 7, kaj tiam la 8;

44
00:02:35,650 --> 00:02:38,720
krei truon, kie mi povas meti la 9,

45
00:02:38,720 --> 00:02:45,910
kaj tiam la 10an kaj la 20an povas iri al la rajto de la 9.

46
00:02:45,910 --> 00:02:49,450
Tio estas speco de doloro ĉar en la plej malbona-kazo scenaro -

47
00:02:49,450 --> 00:02:54,350
kiam ni havi por enmeti aŭ komence aŭ fine

48
00:02:54,350 --> 00:02:56,040
de la tabelo, depende de kiom ni movo -

49
00:02:56,040 --> 00:02:58,850
ni povus fini devi ŝanĝi ĉiujn elementojn

50
00:02:58,850 --> 00:03:00,750
ke ni nuntempe stokante en la tabelo.

51
00:03:00,750 --> 00:03:03,810
>> Do, kio estis la maniero ĉirkaŭ ĉi?

52
00:03:03,810 --> 00:03:09,260
La vojo ĉirkaŭ ĉi estis iri al nia kunligita-listo metodo kie -

53
00:03:09,260 --> 00:03:19,820
anstataŭ konservi la elementoj 5, 7, 8, 10, kaj 20 ĉiuj apud la alia en memoro -

54
00:03:19,820 --> 00:03:25,630
kion ni anstataŭ tio estis stoki ilin ia ajn ni volis konservi ilin

55
00:03:25,630 --> 00:03:32,470
en ĉi tiuj ligitaj-listo nodoj kiuj mi desegnon el tie, ia ad hoc.

56
00:03:32,470 --> 00:03:42,060
Kaj tiam ni konektis ilin kune uzante tiujn sekva punteros.

57
00:03:42,060 --> 00:03:44,370
Mi povas havi puntero de 5 al la 7,

58
00:03:44,370 --> 00:03:46,420
puntero de la 7 al la 8,

59
00:03:46,420 --> 00:03:47,770
puntero de la 8 ĝis la 10,

60
00:03:47,770 --> 00:03:51,220
kaj fine, puntero de la 10 al la 20,

61
00:03:51,220 --> 00:03:54,880
kaj tiam nula puntero je la 20 indikante ke ekzistas nenio maldekstren.

62
00:03:54,880 --> 00:03:59,690
La komerco-off, ke ni havas ĉi tie

63
00:03:59,690 --> 00:04:05,360
estas ke nun, se ni volas enmeti la numero 9 en niajn ordo listo,

64
00:04:05,360 --> 00:04:08,270
ĉiuj ni devas fari estas krei novan nodon kun 9,

65
00:04:08,270 --> 00:04:12,290
telegramon gxin rekte al la adekvata loko,

66
00:04:12,290 --> 00:04:20,630
kaj tiam re-drato la 8 atentigi malsupren al la 9.

67
00:04:20,630 --> 00:04:25,660
Tio estas bela rapida, supozante ni scias precize kie ni volas enmeti la 9.

68
00:04:25,660 --> 00:04:32,610
Sed la komerco-off kontraŭ ĉi tiu estas ke ni nun perdis la konstanta tempo aliro

69
00:04:32,610 --> 00:04:36,230
al iu aparta ero en nia datumstrukturo.

70
00:04:36,230 --> 00:04:40,950
Ekzemple, se mi volas trovi la kvara elemento en ĉi ligillisto,

71
00:04:40,950 --> 00:04:43,510
Mi tuj devos starti je la komenco de la listo

72
00:04:43,510 --> 00:04:48,930
kaj labori mian vojon tra rakonti nodo-per-nodo ĝis mi trovos la kvaran oni.

73
00:04:48,930 --> 00:04:55,870
>> Por akiri pli bonan aliron agado ol ligitaj listo -

74
00:04:55,870 --> 00:04:59,360
sed ankaŭ konservas iujn de la profitoj kiujn ni havis

75
00:04:59,360 --> 00:05:01,800
en terminoj de inserción-tempo de ligitaj listo -

76
00:05:01,800 --> 00:05:05,750
duuma arbo tuj bezonas uzi iom pli memoro.

77
00:05:05,750 --> 00:05:11,460
En aparta, anstataŭ nur havi unu puntero en duuma arbo nodo -

78
00:05:11,460 --> 00:05:13,350
kiel la kunligita-listo nodo faras -

79
00:05:13,350 --> 00:05:16,950
nin tuj aldoni duan sagon al la duuma arbo nodo.

80
00:05:16,950 --> 00:05:19,950
Anstataŭ nur havi sagon al la sekva elemento,

81
00:05:19,950 --> 00:05:24,420
ni tuj havos puntero al maldekstra infano kaj dekstra infano.

82
00:05:24,420 --> 00:05:26,560
>> Ni desegni bildon por vidi kion tio efektive aspektas.

83
00:05:26,560 --> 00:05:31,350
Denove, mi tuj uzos tiujn skatolojn kaj sagojn.

84
00:05:31,350 --> 00:05:37,150
A duuma arbo nodo dividos kun nur simpla skatolo.

85
00:05:37,150 --> 00:05:40,940
Oni tuj havos spacon por la valoro,

86
00:05:40,940 --> 00:05:47,280
kaj tiam ĝi estas ankaŭ havos spacon por la maldekstra infano kaj la dekstra infano.

87
00:05:47,280 --> 00:05:49,280
Mi tuj etikedi ilin ĉi tie.

88
00:05:49,280 --> 00:05:57,560
Ni havos la maldekstra infano, kaj poste ni iras al rajtas infano.

89
00:05:57,560 --> 00:05:59,920
Estas multaj malsamaj manieroj de fari tion.

90
00:05:59,920 --> 00:06:02,050
Kelkfoje por spaco kaj komforto,

91
00:06:02,050 --> 00:06:06,460
Mi vere desegni ĝin kiel mi faras tie ĉi sur la fundo

92
00:06:06,460 --> 00:06:10,910
kie mi havos la valoron ĉe la supro,

93
00:06:10,910 --> 00:06:14,060
kaj tiam la dekstra infano sur la fundon-dekstra,

94
00:06:14,060 --> 00:06:16,060
kaj la maldekstra infano sur la fundon-maldekstren.

95
00:06:16,060 --> 00:06:20,250
Reiros al ĉi supro diagramo,

96
00:06:20,250 --> 00:06:22,560
ni havas la valoron je la plejsupro,

97
00:06:22,560 --> 00:06:25,560
tiam ni havas la maldekstra infano pointer, kaj poste ni rajtas-infano puntero.

98
00:06:25,560 --> 00:06:30,110
>> En la Problemo Ara Specification,

99
00:06:30,110 --> 00:06:33,110
ni parolas pri desegni nodo kiu havas valoro 7,

100
00:06:33,110 --> 00:06:39,750
kaj tiam maldekstra infano puntero kiu estas nula, kaj dekstra infano puntero kiu estas nula.

101
00:06:39,750 --> 00:06:46,040
Ni povas ĉu verki ĉefurbo NULL en la spaco por

102
00:06:46,040 --> 00:06:51,610
ambaŭ la maldekstra infano kaj la dekstra infano, aŭ ni povas desegni ĉi diagonalo oblikvo

103
00:06:51,610 --> 00:06:53,750
tra ĉiu el la skatoloj por indiki, ke estas nula.

104
00:06:53,750 --> 00:06:57,560
Mi faros tion nur ĉar tio estas pli simpla.

105
00:06:57,560 --> 00:07:03,700
Kion vi vidas ĉi tie estas du vojoj de diagramming tre simpla duuma arbo nodo

106
00:07:03,700 --> 00:07:07,960
kie ni havas la valoron 7 kaj nula infano punteros.

107
00:07:07,960 --> 00:07:15,220
>> La dua parto de nia specifo prelegoj pri kiel kun ligitaj listoj -

108
00:07:15,220 --> 00:07:18,270
memoru, ni nur devis tenadi la unua ero en listo

109
00:07:18,270 --> 00:07:20,270
memori la tutan liston -

110
00:07:20,270 --> 00:07:26,140
kaj tiel same, kun duargumenta arbo, ni nur devas tenadi unu sagon al la arbo

111
00:07:26,140 --> 00:07:31,120
por subteni kontrolo super la tuta datumstrukturo.

112
00:07:31,120 --> 00:07:36,150
Ĉi tiu speciala elemento de la arbo oni nomas la radika vertico de la arbo.

113
00:07:36,150 --> 00:07:43,360
Ekzemple, se ĉi tiu nodo - ĉi nodo enhavanta la valoron 7

114
00:07:43,360 --> 00:07:45,500
kun nula maldekstra kaj dekstra infano punteros -

115
00:07:45,500 --> 00:07:47,360
estis la sola valoro de nia arbo,

116
00:07:47,360 --> 00:07:50,390
tiam ĉi tio estus nia radika nodo.

117
00:07:50,390 --> 00:07:52,240
Ĝi estas la komenco de nia arbo.

118
00:07:52,240 --> 00:07:58,530
Ni povas vidi ĉi iom pli klare iam ni eku aldoni pli nodoj al nia arbo.

119
00:07:58,530 --> 00:08:01,510
Lasu min eltiri novan paĝon.

120
00:08:01,510 --> 00:08:05,000
>> Nun ni iras por desegni arbon kiu havas 7, je la radika,

121
00:08:05,000 --> 00:08:10,920
kaj 3 ene de la maldekstra infano kaj 9 ene de la dekstra infano.

122
00:08:10,920 --> 00:08:13,500
Denove, tio estas bela simpla.

123
00:08:13,500 --> 00:08:26,510
Ni havas 7, desegni nodo por la 3, nodo por 9,

124
00:08:26,510 --> 00:08:32,150
kaj mi tuj metis la maldekstra infano puntero de 7 al punkto al la nodo enhavanta 3,

125
00:08:32,150 --> 00:08:37,850
kaj la dekstra infano puntero de la nodo enhavanta 7 al la nodo enhavanta 9.

126
00:08:37,850 --> 00:08:42,419
Nun, ekde 3 kaj 9 ne havas infanojn,

127
00:08:42,419 --> 00:08:48,500
nin tuj metis ĉiujn siajn infano punteros esti nula.

128
00:08:48,500 --> 00:08:56,060
Ĉi tie, la radiko de nia arbo korespondas al la nodo enhavanta la numero 7.

129
00:08:56,060 --> 00:09:02,440
Vi povas vidi ke se ĉiuj ni havas estas puntero al tiu radiko nodo,

130
00:09:02,440 --> 00:09:07,330
ni povas tiam marŝi tra niaj arbo kaj konsenti ambaŭ infanaj verticoj -

131
00:09:07,330 --> 00:09:10,630
ambaŭ 3 kaj 9.

132
00:09:10,630 --> 00:09:14,820
Neniu bezonas subteni punteros al ĉiu unuopa nodo en la arbo.

133
00:09:14,820 --> 00:09:22,080
Alright. Nun ni iras aldoni alian nodon al ĉi tiu figuro.

134
00:09:22,080 --> 00:09:25,370
Ni tuj aldonos nodo enhavanta 6,

135
00:09:25,370 --> 00:09:34,140
kaj ni tuj aldonu tion kiel la dekstra filo de la nodo enhavanta 3.

136
00:09:34,140 --> 00:09:41,850
Por fari tion, mi tuj viŝi ke nula puntero en la 3-nodon

137
00:09:41,850 --> 00:09:47,750
kaj telegramon gxin rekte al la nodo enhavanta 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Je ĉi tiu punkto, ni transiru iomete da terminologio.

139
00:09:53,800 --> 00:09:58,230
Por komenci, la kialo ke ĉi nomiĝas binara arbo en aparta

140
00:09:58,230 --> 00:10:00,460
estas ke ĝi havas du infano punteros.

141
00:10:00,460 --> 00:10:06,020
Estas aliaj specoj de arboj kiu havas pli infano punteros.

142
00:10:06,020 --> 00:10:10,930
En aparta, vi faris 'provi' en Problemo Serio 5.

143
00:10:10,930 --> 00:10:19,310
Vi rimarkos ke en tiu try, vi havis 27 malsamajn punteros al malsamaj infanoj -

144
00:10:19,310 --> 00:10:22,410
unu por ĉiu el la 26 literoj en la angla alfabeto,

145
00:10:22,410 --> 00:10:25,410
kaj tiam la 27a por la apostrofo -

146
00:10:25,410 --> 00:10:28,900
do, jen simila al tipo de arbo.

147
00:10:28,900 --> 00:10:34,070
Sed ĉi tie, pro tio la duuma, ni nur havas du infano punteros.

148
00:10:34,070 --> 00:10:37,880
>> Aldone al ĉi tiu nodo radiko, ke ni raportis,

149
00:10:37,880 --> 00:10:41,470
ni ankaŭ ĵetis ĉirkaŭ ĉi termino 'infano'.

150
00:10:41,470 --> 00:10:44,470
Kion ĝi signifas por unu nodo esti knabo de alia nodo?

151
00:10:44,470 --> 00:10:54,060
Ĝi laŭvorte signifas ke infano nodo estas infano de alia nodo

152
00:10:54,060 --> 00:10:58,760
se tiu alia nodo havas unu el liaj infano punteros starigis al punkto al tiu nodo.

153
00:10:58,760 --> 00:11:01,230
Meti ĉi tion en pli konkreta terminoj,

154
00:11:01,230 --> 00:11:11,170
se 3 estas montradis per unu el la infano punteros de 7, tiam 3 estas infano de 7.

155
00:11:11,170 --> 00:11:14,510
Se ni devis eltrovi kio estas la filoj de 7 estas -

156
00:11:14,510 --> 00:11:18,510
bone, ni vidas ke 7 havas puntero al 3 kaj puntero al 9,

157
00:11:18,510 --> 00:11:22,190
tiel 9 kaj 3 estas la filoj de 7.

158
00:11:22,190 --> 00:11:26,650
Naŭ ne havas infanojn pro lia infano punteros estas nulaj,

159
00:11:26,650 --> 00:11:30,940
kaj 3 havas nur unu infanon, 6.

160
00:11:30,940 --> 00:11:37,430
Ses ankaŭ ne havas infanojn ĉar ambaŭ de liaj indikoj estas nulaj, kiun ni devos desegni nun.

161
00:11:37,430 --> 00:11:45,010
>> Aldone, ni ankaŭ parolas pri la gepatroj de aparta nodo,

162
00:11:45,010 --> 00:11:51,100
kaj ĉi tio estas, kiel vi atendus, la dorsflanko de tiu infano priskribo.

163
00:11:51,100 --> 00:11:58,620
Ĉiu vertico havas nur unu patro - anstataŭ du kiel vi eble atendas kun homoj.

164
00:11:58,620 --> 00:12:03,390
Ekzemple, la patro de 3 estas 7.

165
00:12:03,390 --> 00:12:10,800
La patro de 9 estas ankaŭ 7, kaj la patro de 6 estas 3. Ne multe por tio.

166
00:12:10,800 --> 00:12:15,720
Ni ankaŭ havas terminojn por raporti geavoj kaj genepoj,

167
00:12:15,720 --> 00:12:18,210
kaj pli ĝenerale parolas pri la prauloj

168
00:12:18,210 --> 00:12:20,960
kaj posteuloj de aparta nodo.

169
00:12:20,960 --> 00:12:25,710
La praulo de vertico - aŭ prapatroj, pli ĝuste, de nodo -

170
00:12:25,710 --> 00:12:32,730
estas ĉiuj de la nodoj, kiuj staras en la vojo de la radiko al tiu nodo.

171
00:12:32,730 --> 00:12:36,640
Ekzemple, se mi rigardas la nodo 6,

172
00:12:36,640 --> 00:12:46,430
tiam la prapatroj tuj esti ambaŭ 3 kaj 7.

173
00:12:46,430 --> 00:12:55,310
La prapatroj de 9, ekzemple, estas - se mi rigardas la nodo 9 -

174
00:12:55,310 --> 00:12:59,990
tiam la patro de 9 estas nur 7.

175
00:12:59,990 --> 00:13:01,940
Kaj posteuloj estas akurate la reverso.

176
00:13:01,940 --> 00:13:05,430
Se mi volas rigardi ĉiujn posteulojn de 7,

177
00:13:05,430 --> 00:13:11,020
tiam mi devas rigardi ĉiujn nodoj sub ĝi.

178
00:13:11,020 --> 00:13:16,950
Do, mi havas 3, 9, kaj 6 ĉiuj kiel posteuloj de 7.

179
00:13:16,950 --> 00:13:24,170
>> La fina termino kiu ni parolos pri estas ĉi nocio de estante frato.

180
00:13:24,170 --> 00:13:27,980
Gefratoj - speco de post kune sur tiuj familio terminoj -

181
00:13:27,980 --> 00:13:33,150
estas nodoj kiuj estas je la sama nivelo en la arbo.

182
00:13:33,150 --> 00:13:42,230
Do, 3 kaj 9 estas gefratoj, ĉar ili estas je la sama nivelo en la arbo.

183
00:13:42,230 --> 00:13:46,190
Ili ambaŭ havas la saman patro, 7.

184
00:13:46,190 --> 00:13:51,400
La 6 ne havas fratojn ĉar 9 ne havas infanojn.

185
00:13:51,400 --> 00:13:55,540
Kaj 7 ne havas neniun gefratoj ĉar ĝi estas la radiko de nia arbo,

186
00:13:55,540 --> 00:13:59,010
kaj tie estas nur iam 1 radiko.

187
00:13:59,010 --> 00:14:02,260
Dum 7 havi gefratoj tie devus esti nodo supre 7.

188
00:14:02,260 --> 00:14:07,480
Tie devus esti patro de 7, en kies kazo 7 kaj kiu ne estus la radiko de la arbo.

189
00:14:07,480 --> 00:14:10,480
Tiam tiu nova patro de 7 ankaŭ devus havi infanon,

190
00:14:10,480 --> 00:14:16,480
kaj ke infano devus tiam esti la frato de 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Movante plu.

192
00:14:21,040 --> 00:14:24,930
Kiam ni komencis nian diskuton de duumaj arboj,

193
00:14:24,930 --> 00:14:28,790
ni parolis pri kiel ni tuj uzi ilin por

194
00:14:28,790 --> 00:14:32,800
gajni avantaĝon super ambaŭ tabeloj kaj kunligita listoj.

195
00:14:32,800 --> 00:14:37,220
Kaj la vojon ni tuj faros kiu estas kun ĉi ordigante proprieto.

196
00:14:37,220 --> 00:14:41,080
Ni diru ke duuma arbo estas ordigita laŭ la specifo,

197
00:14:41,080 --> 00:14:45,740
se por ĉiu nodo en nia arbo, ĉiu el liaj posteuloj maldekstre -

198
00:14:45,740 --> 00:14:48,670
la maldekstra infano kaj ĉiuj de la maldekstra infano posteuloj -

199
00:14:48,670 --> 00:14:54,510
havas malpli valoroj, kaj ĉiuj de la nodoj ĉe la dekstra -

200
00:14:54,510 --> 00:14:57,770
Dekstre infano kaj ĉiuj la rajton infano posteuloj -

201
00:14:57,770 --> 00:15:02,800
havi nodoj granda ol la valoro de la nuna nodo ke ni rigardas.

202
00:15:02,800 --> 00:15:07,850
Nur por simpleco, ni tuj supozi ke estas nenia duplikatajn nodoj en nia arbo.

203
00:15:07,850 --> 00:15:11,180
Ekzemple, en ĉi tiu arbo ni ne tuj pritrakti la kazon

204
00:15:11,180 --> 00:15:13,680
kie ni havas la valoron 7, je la radika

205
00:15:13,680 --> 00:15:16,720
 kaj tiam ni ankaŭ havas la valoron 7 aliloke en la arbo.

206
00:15:16,720 --> 00:15:24,390
En ĉi tiu kazo, vi rimarkos ke la arbo estas fakte ordigita.

207
00:15:24,390 --> 00:15:26,510
Ni havas la valoron 7, je la radiko.

208
00:15:26,510 --> 00:15:29,720
Ĉiu al la maldekstra de 7 -

209
00:15:29,720 --> 00:15:35,310
se mi malfari ĉiuj el ĉi tiuj malgranduloj markoj tie -

210
00:15:35,310 --> 00:15:40,450
ĉiun al la maldekstra de 7 - la 3 kaj la 6 -

211
00:15:40,450 --> 00:15:49,410
tiuj valoroj estas tiel malpli ol 7, kaj ĉiu al la dekstra - kiu estas ĝuste ĉi tiu 9 -

212
00:15:49,410 --> 00:15:53,450
estas pli granda ol 7.

213
00:15:53,450 --> 00:15:58,650
>> Tiu ne estas la sola ordigis arbo kiu enhavas tiujn valorojn,

214
00:15:58,650 --> 00:16:03,120
sed ni desegni kelkajn pli el ili.

215
00:16:03,120 --> 00:16:05,030
Estas vere tutan faskon da manieroj kiujn ni povas fari ĉi tion.

216
00:16:05,030 --> 00:16:09,380
Mi tuj uzos stenografio nur por subteni la aĵojn simpla kie -

217
00:16:09,380 --> 00:16:11,520
anstataŭ desegni ekster la tuta skatoloj-kaj-sagojn -

218
00:16:11,520 --> 00:16:14,220
Mi nur tuj desegni la numeroj kaj aldonu sagojn konektante ilin.

219
00:16:14,220 --> 00:16:22,920
Por komenci, ni simple skribu nian originalan arbo, kie ni havis 7, kaj tiam 3,

220
00:16:22,920 --> 00:16:25,590
kaj tiam 3 pinta reen al la rajto al la 6,

221
00:16:25,590 --> 00:16:30,890
kaj 7 havis rajton infano kiu estis 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Kio estas alia maniero por ke ni povus skribi ĉi arbo?

223
00:16:33,860 --> 00:16:38,800
Anstataŭ havi 3 esti la maldekstra infano de 7,

224
00:16:38,800 --> 00:16:41,360
ni povus havi ankaŭ la 6 esti la maldekstra infano de 7,

225
00:16:41,360 --> 00:16:44,470
kaj tiam 3 esti la maldekstra infano de la 6.

226
00:16:44,470 --> 00:16:48,520
Tio aspektas kiel tiu arbo ĉi tie kie mi havas 7,

227
00:16:48,520 --> 00:16:57,860
tiam 6, tiam 3, kaj 9 dekstre.

228
00:16:57,860 --> 00:17:01,490
Ni ankaŭ ne devas havi 7 kiel nia radika nodo.

229
00:17:01,490 --> 00:17:03,860
Ni povus ankaŭ havi 6 kiel nia radika nodo.

230
00:17:03,860 --> 00:17:06,470
Kion tio aspektas?

231
00:17:06,470 --> 00:17:09,230
Se ni iras al subteni ĉi ordigis proprieto,

232
00:17:09,230 --> 00:17:12,970
ĉiun al la maldekstra de la 6 devas esti malpli ol tio.

233
00:17:12,970 --> 00:17:16,540
Estas nur unu eblo, kaj tio estas 3.

234
00:17:16,540 --> 00:17:19,869
Sed tiam kiel la dekstra filo de 6, ni havas du eblecojn.

235
00:17:19,869 --> 00:17:25,380
Unue, ni povus havi la 7 kaj poste la 9,

236
00:17:25,380 --> 00:17:28,850
aŭ ni povus desegni ĝin - kiel mi estas faronta tie -

237
00:17:28,850 --> 00:17:34,790
kie ni havas la 9 kiel la rajto infano de la 6,

238
00:17:34,790 --> 00:17:39,050
kaj tiam la 7 kiel la maldekstra infano de la 9.

239
00:17:39,050 --> 00:17:44,240
>> Nun, 7 kaj 6 ne estas la solaj eblaj valoroj por la radiko.

240
00:17:44,240 --> 00:17:50,200
Ni povus ankaŭ havi 3 esti je la radiko.

241
00:17:50,200 --> 00:17:52,240
Kio okazas se 3 estas ĉe la radiko?

242
00:17:52,240 --> 00:17:54,390
Ĉi tie, aĵoj iom interesa.

243
00:17:54,390 --> 00:17:58,440
Tri ne havas neniun valoroj kiuj estas malpli ol ĝi,

244
00:17:58,440 --> 00:18:02,070
por ke tuta maldekstra flanko de la arbo estas simple tuj estos nula.

245
00:18:02,070 --> 00:18:03,230
Tie ne iras al esti io tie.

246
00:18:03,230 --> 00:18:07,220
Dekstre, ni povus listigi aĵojn en suprenira ordo.

247
00:18:07,220 --> 00:18:15,530
Ni povus havi 3, tiam 6, tiam 7, tiam 9.

248
00:18:15,530 --> 00:18:26,710
Aŭ, ni povis fari 3, tiam 6, tiam 9, tiam 7.

249
00:18:26,710 --> 00:18:35,020
Aŭ, ni povis fari 3, tiam 7, tiam 6, tiam 9.

250
00:18:35,020 --> 00:18:40,950
Aŭ, 3, 7 - fakte ne, ni ne povas fari ĉirkaŭ 7 plu.

251
00:18:40,950 --> 00:18:43,330
Tio estas nia unu afero tie.

252
00:18:43,330 --> 00:18:54,710
Ni povas fari 9, kaj tiam el la 9 ni povas fari 6 kaj poste 7.

253
00:18:54,710 --> 00:19:06,980
Aŭ, ni povas fari 3, tiam 9, tiam 7, kaj tiam 6.

254
00:19:06,980 --> 00:19:12,490
>> Unu afero atentigi vin tie estas

255
00:19:12,490 --> 00:19:14,510
ke tiuj arboj estas iom stranga aspekto.

256
00:19:14,510 --> 00:19:17,840
En aparta, se ni rigardas la 4 arboj sur la dekstra flanko -

257
00:19:17,840 --> 00:19:20,930
Mi ĉirkaŭiri ilin, tie -

258
00:19:20,930 --> 00:19:28,410
tiuj arboj aspektas preskaŭ ekzakte kiel ligitaj listo.

259
00:19:28,410 --> 00:19:32,670
Ĉiu vertico havas nur unu infanon,

260
00:19:32,670 --> 00:19:38,950
kaj tiel ni ne havas iu ajn el ĉi tiu arbo-simila strukturo kiu ni vidas, ekzemple,

261
00:19:38,950 --> 00:19:44,720
 en ĉi tiu sola arbo super tie sur la fundo maldekstren.

262
00:19:44,720 --> 00:19:52,490
Tiuj arboj estas reale nomita degeneri duumaj arboj,

263
00:19:52,490 --> 00:19:54,170
kaj ni parolos pri tiuj pli en la estonteco -

264
00:19:54,170 --> 00:19:56,730
precipe se vi iras preni aliaj komputikaj kursoj.

265
00:19:56,730 --> 00:19:59,670
Tiuj arboj estas degenera.

266
00:19:59,670 --> 00:20:03,780
Ili ne estas tre utilaj ĉar, ja, tiu strukturo pruntas

267
00:20:03,780 --> 00:20:08,060
 al lookup fojoj simila al tiu de ligitaj listo.

268
00:20:08,060 --> 00:20:13,050
Ni ne komprenas utiligi la ekstra memoro - tiu ekstra puntero -

269
00:20:13,050 --> 00:20:18,840
pro nia strukturo esti malbona en tio.

270
00:20:18,840 --> 00:20:24,700
Anstataŭ daŭrigi kaj nudigos la duuma arboj kiuj havas 9, je la radika,

271
00:20:24,700 --> 00:20:27,220
kiu estas la lasta kazo, ke ni devus,

272
00:20:27,220 --> 00:20:32,380
ni estas loko, en ĉi tiu punkto, tuj parolos iomete pri tiu alia termino

273
00:20:32,380 --> 00:20:36,150
ke ni uzas kiam parolas pri arboj, kiu estas nomata la alteco.

274
00:20:36,150 --> 00:20:45,460
>> La alteco de arbo estas la distanco de la radiko ĝis la plej malproksima-nodo,

275
00:20:45,460 --> 00:20:48,370
aŭ pli ĝuste la nombro de lupolo, ke vi devus fari por

276
00:20:48,370 --> 00:20:53,750
komencos de la radiko kaj tiam finas ĉe la plej malproksima vertico en la arbo.

277
00:20:53,750 --> 00:20:57,330
Se ni rigardas iujn el tiuj arboj, kiujn ni desegnis ĉi tie,

278
00:20:57,330 --> 00:21:07,870
ni povas vidi ke se ni prenos ĉi arbo en la supra maldekstra angulo kaj ni starti je la 3,

279
00:21:07,870 --> 00:21:14,510
tiam ni devas fari 1 lupolo por atingi la 6, dua lupolo por atingi la 7,

280
00:21:14,510 --> 00:21:20,560
kaj triono lupolo por atingi la 9.

281
00:21:20,560 --> 00:21:26,120
Do, la alteco de ĉi tiu arbo estas 3.

282
00:21:26,120 --> 00:21:30,640
Ni povas fari la saman taskon pri la aliaj arboj konturita kun ĉi verda,

283
00:21:30,640 --> 00:21:40,100
kaj ni vidos, ke la alteco de ĉiuj el tiuj arboj estas ankaŭ ja 3.

284
00:21:40,100 --> 00:21:45,230
Tio estas parto de tio, kio igas ilin degeneri -

285
00:21:45,230 --> 00:21:53,750
ke ilia alteco estas nur unu malpli ol la nombro de nodoj en la tuta arbo.

286
00:21:53,750 --> 00:21:58,400
Se ni rigardas tiun aliaj arbo jen ĉirkaŭitaj per ruĝaj, aliflanke,

287
00:21:58,400 --> 00:22:03,920
ni vidas ke la plej malproksima folio nodoj estas la 6 kaj la 9 -

288
00:22:03,920 --> 00:22:06,940
la folioj estas tiuj nodoj, kiuj ne havas infanojn.

289
00:22:06,940 --> 00:22:11,760
Do, por preni de la radika vertico al ĉu la 6 aŭ 9,

290
00:22:11,760 --> 00:22:17,840
ni devas fari unu lupolo por atingi la 7 kaj poste duan lupolo por atingi la 9,

291
00:22:17,840 --> 00:22:21,240
kaj simile, nur dua hop de la 7 al atingi la 6.

292
00:22:21,240 --> 00:22:29,080
Do, la alteco de ĉi tiu arbo super tie estas nur 2.

293
00:22:29,080 --> 00:22:35,330
Vi povas reiri kaj fari tion por ĉiuj el la aliaj arboj, ke ni antaŭe diskutis

294
00:22:35,330 --> 00:22:37,380
komencante kun la 7 kaj la 6,

295
00:22:37,480 --> 00:22:42,500
kaj vi trovos ke la alteco de ĉiuj el tiuj arboj estas ankaŭ 2.

296
00:22:42,500 --> 00:22:46,320
>> La kialo ni parolis pri ordigitaj duumaj arboj

297
00:22:46,320 --> 00:22:50,250
kaj kial ili estas malvarmaj estas ĉar vi povas serĉi per ili en

298
00:22:50,250 --> 00:22:53,810
tre simila maniero serĉado super ordo tabelo.

299
00:22:53,810 --> 00:22:58,720
Tie estas kie ni parolas pri atingi ke plibonigitaj lookup tempo

300
00:22:58,720 --> 00:23:02,730
super la simpla ligitaj listo.

301
00:23:02,730 --> 00:23:05,010
Kun ligitaj listo - se vi volas trovi apartan elementon -

302
00:23:05,010 --> 00:23:07,470
vi estas en la plej bona faros ian lineara serĉo

303
00:23:07,470 --> 00:23:10,920
kie oni komencas komence de lerta kaj lupolo unu-por-unu -

304
00:23:10,920 --> 00:23:12,620
unu nodo de unu nodo -

305
00:23:12,620 --> 00:23:16,060
tra la tutan liston ĝis vi trovos kion ajn vi sercxas.

306
00:23:16,060 --> 00:23:19,440
Dum, se vi havas duuma arbo ke tio stokitaj en ĉi bela formato,

307
00:23:19,440 --> 00:23:23,300
vi povas reale preni pli ol duuma serĉo okazas

308
00:23:23,300 --> 00:23:25,160
kie vi dividu kaj venkos

309
00:23:25,160 --> 00:23:29,490
kaj serĉo tra la taŭga duono de la arbo je ĉiu paŝo.

310
00:23:29,490 --> 00:23:32,840
Ni vidu kiel tiu verkoj.

311
00:23:32,840 --> 00:23:38,850
>> Se ni havas - denove, tuj reen al nia originala arbo -

312
00:23:38,850 --> 00:23:46,710
ni starti je 7, ni havas 3 maldekstre, 9 dekstre,

313
00:23:46,710 --> 00:23:51,740
kaj sub la 3 havas la 6.

314
00:23:51,740 --> 00:24:01,880
Se ni volas serĉi la nombro 6 en tiu arbo, ni volas komenci je la radiko.

315
00:24:01,880 --> 00:24:08,910
Ni devus kompari la valoron ni serĉas, diru 6,

316
00:24:08,910 --> 00:24:12,320
al la valoro stokita en la nodo ke ni nuntempe rigardante, 7,

317
00:24:12,320 --> 00:24:21,200
trovi ke 6 estas ja malpli ol 7, do ni volas movi al la maldekstra.

318
00:24:21,200 --> 00:24:25,530
Se la valoro de 6 estis pli granda ol 7, ni estus en loko kopiis al dekstre.

319
00:24:25,530 --> 00:24:29,770
Ĉar ni scias, ke - pro la strukturo de nia ordigitaj duumaj arbo -

320
00:24:29,770 --> 00:24:33,910
ĉiuj valoroj malpli ol 7 estas tuj estos stokitaj la maldekstra de 7,

321
00:24:33,910 --> 00:24:40,520
ne necesas eĉ tedas rigardi tra la dekstra flanko de la arbo.

322
00:24:40,520 --> 00:24:43,780
Iam ni movi al la maldekstra kaj ni estas nun en la nodo enhavanta 3,

323
00:24:43,780 --> 00:24:48,110
ni povas fari tion saman komparon denove kie oni komparas la 3 kaj la 6.

324
00:24:48,110 --> 00:24:52,430
Kaj ni trovos ke dum 6 - la valoron ni serĉas - estas pli granda ol 3,

325
00:24:52,430 --> 00:24:58,580
ni povas iri al la dekstra flanko de la nodo enhavanta 3.

326
00:24:58,580 --> 00:25:02,670
Ne maldekstra flanko tie, do ni povus esti ignorata tio.

327
00:25:02,670 --> 00:25:06,510
Sed ni nur scias ke ĉar ni rigardas la arbo mem,

328
00:25:06,510 --> 00:25:08,660
kaj ni povas vidi ke la arbo ne havas infanoj.

329
00:25:08,660 --> 00:25:13,640
>> Estas ankaŭ bela facile serĉi 6 en ĉi tiu arbo se ni faras ĝin mem kiel homoj,

330
00:25:13,640 --> 00:25:16,890
sed ni sekvi tiu procezo mekanike kiel komputilo estus fari

331
00:25:16,890 --> 00:25:18,620
por vere kompreni la algoritmo.

332
00:25:18,620 --> 00:25:26,200
Je ĉi tiu punkto, ni nun rigardas nodo kiu enhavas 6,

333
00:25:26,200 --> 00:25:29,180
kaj ni serĉas la valoro 6,

334
00:25:29,180 --> 00:25:31,740
do, ja, ni trovis la taŭgan nodo.

335
00:25:31,740 --> 00:25:35,070
Ni trovis la valoron 6 en nia arbo, kaj ni povas halti nian serĉo.

336
00:25:35,070 --> 00:25:37,330
Je ĉi tiu punkto, depende de tio, kio okazas,

337
00:25:37,330 --> 00:25:41,870
ni povas diri, jes, ni trovis la valoron 6, ekzistas en nia arbo.

338
00:25:41,870 --> 00:25:47,640
Aŭ, se ni planas enmeti nodo aŭ fari ion, ni povas fari ĉe ĉi tiu punkto.

339
00:25:47,640 --> 00:25:53,010
>> Ni faru paro pli serĉoj nur por vidi kiel tio funkcias.

340
00:25:53,010 --> 00:25:59,390
Ni rigardu kio okazas se ni devis provi kaj serĉi la valoron 10.

341
00:25:59,390 --> 00:26:02,970
Se ni devis serĉi la valoron 10, ni devus komenci je la radiko.

342
00:26:02,970 --> 00:26:07,070
Ni ŝatus vidi ke 10 estas pli granda ol 7, do ni volas movi al dekstre.

343
00:26:07,070 --> 00:26:13,640
Ni ŝatus alveni al la 9 kaj kompari 9 al la 10 kaj vidi ke 9 estas ja malpli ol 10.

344
00:26:13,640 --> 00:26:16,210
Do denove, ni volas provi kopii al dekstre.

345
00:26:16,210 --> 00:26:20,350
Sed en ĉi tiu punkto, ni volas rimarki ke ni estas en nula nodo.

346
00:26:20,350 --> 00:26:23,080
Nenio tie. Nenio kie la 10 devus esti.

347
00:26:23,080 --> 00:26:29,360
Tie estas kie ni povas raporti fiasko - tio estas ja ne 10 en la arbo.

348
00:26:29,360 --> 00:26:35,420
Kaj fine, ni iru tra la kazo kie ni provas serĉi 1 en la arbo.

349
00:26:35,420 --> 00:26:38,790
Ĉi tio estas simila al kio okazas se ni rigardas supren 10, krom anstataŭ iri al la dekstra,

350
00:26:38,790 --> 00:26:41,260
ni tuj iros al la maldekstra.

351
00:26:41,260 --> 00:26:46,170
Ni starti je la 7 kaj vidas ke 1 estas malpli ol 7, do ni movi al la maldekstra.

352
00:26:46,170 --> 00:26:51,750
Ni atingos la 3 kaj vidas ke 1 estas malpli ol 3, do ni denove provas movi al la maldekstra.

353
00:26:51,750 --> 00:26:59,080
Je ĉi tiu punkto ni havas nula nodo, do ni denove povas raporti fiasko.

354
00:26:59,080 --> 00:27:10,260
>> Se vi volas lerni pli pri duumaj arboj,

355
00:27:10,260 --> 00:27:14,420
ekzistas tuta amaso de amuzo iom problemoj kiujn vi povas fari kun ili.

356
00:27:14,420 --> 00:27:19,450
Mi sugestas praktiki la desegno el tiuj diagramoj unu-por-unu

357
00:27:19,450 --> 00:27:21,910
kaj post tra ĉiuj malsamaj ŝtupoj,

358
00:27:21,910 --> 00:27:25,060
ĉar ĉi venos en super-oportuna

359
00:27:25,060 --> 00:27:27,480
ne nur kiam vi faras la Huffman kodigo problemo aro

360
00:27:27,480 --> 00:27:29,390
sed ankaŭ en estonteco kursoj -

361
00:27:29,390 --> 00:27:32,220
nur lerni kiel nudigos tiuj datumstrukturoj kaj pensi per la problemoj

362
00:27:32,220 --> 00:27:38,000
kun plumo kaj papero aŭ, en ĉi tiu kazo, iPad kaj grifelo.

363
00:27:38,000 --> 00:27:41,000
>> Je ĉi tiu punkto tamen, ni iras al movi sur fari iu kodigo praktiko

364
00:27:41,000 --> 00:27:44,870
kaj reale ludi kun tiuj binaraj arboj kaj vidi.

365
00:27:44,870 --> 00:27:52,150
Mi tuj ŝanĝi reen super al mia komputilo.

366
00:27:52,150 --> 00:27:58,480
Por ĉi tiu parto de la sekcio, anstataŭ uzi CS50 Run aŭ CS50 Spacoj,

367
00:27:58,480 --> 00:28:01,500
Mi tuj uzos la aparaton.

368
00:28:01,500 --> 00:28:04,950
>> Post kune kun la problemo Ara specifo,

369
00:28:04,950 --> 00:28:07,740
Mi vidas ke mi devus malfermi la aparaton,

370
00:28:07,740 --> 00:28:11,020
iri al mia Dropbox dosierujo, krei dosierujo nomita Sekcio 7,

371
00:28:11,020 --> 00:28:15,730
kaj poste krei dosieron nomatan binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Ĉi tie ni iru. Mi havas la aparaton jam malfermitaj.

373
00:28:22,050 --> 00:28:25,910
Mi iros elsxiros fina.

374
00:28:25,910 --> 00:28:38,250
Mi tuj iros al la Dropbox dosierujo, faru dosierujo nomita section7,

375
00:28:38,250 --> 00:28:42,230
kaj vidi estas tute malplena.

376
00:28:42,230 --> 00:28:48,860
Nun mi iros por malfermi binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Ĉi tie ni iru - malplena dosiero.

378
00:28:51,750 --> 00:28:54,330
>> Ni reiru al la specifo.

379
00:28:54,330 --> 00:28:59,850
La specifo petas krei novan tipon difino

380
00:28:59,850 --> 00:29:03,080
por duuma arbo nodo enhavanta int valoroj -

381
00:29:03,080 --> 00:29:07,110
same kiel la valoroj kiujn ni eltiris en nia diagramming antaŭe.

382
00:29:07,110 --> 00:29:11,740
Ni tuj uzos ĉi Boilerplate typedef ke ni faris ĉi tie

383
00:29:11,740 --> 00:29:14,420
ke vi rekonas el Problemo Serio 5 -

384
00:29:14,420 --> 00:29:19,190
se vi faris la hash tablo vojo de konkerantoj la Speller programo.

385
00:29:19,190 --> 00:29:22,540
Vi devus ankaŭ rekonas ĝin de la pasinta semajno sekcio

386
00:29:22,540 --> 00:29:23,890
kie ni parolis pri ligitaj listoj.

387
00:29:23,890 --> 00:29:27,870
Ni havas ĉi typedef de struct nodo,

388
00:29:27,870 --> 00:29:34,430
kaj ni donis ĉi struct nodo ĉi nomo de struct nodo antauxe

389
00:29:34,430 --> 00:29:39,350
tiel ke ni povas tiam referi al ĝi ekde ni volas havi struct nodo punteros

390
00:29:39,350 --> 00:29:45,740
kiel parto de nia struct, sed ni tiam cxirkauxis tiun -

391
00:29:45,740 --> 00:29:47,700
aŭ pli ĝuste, enfermita ĉi - en typedef

392
00:29:47,700 --> 00:29:54,600
tiel ke, poste en la kodo, ni povas raporti al ĉi struct kiel ĝuste nodo anstataŭ struct nodo.

393
00:29:54,600 --> 00:30:03,120
>> Ĉi tuj estos tre simila al la unuope-ligillisto difino, kiun ni vidis la pasintan semajnon.

394
00:30:03,120 --> 00:30:20,070
Por tion fari, ni komencu per skribanta el la Boilerplate.

395
00:30:20,070 --> 00:30:23,840
Ni scias, ke ni devas havi entjero valoro,

396
00:30:23,840 --> 00:30:32,170
do ni metos en int valoron, kaj tiam anstataŭ havi nur unu sagon al la sekva elemento -

397
00:30:32,170 --> 00:30:33,970
kiel ni faris kun unuope-ligitaj listoj -

398
00:30:33,970 --> 00:30:38,110
ni havos maldekstra kaj dekstra infano punteros.

399
00:30:38,110 --> 00:30:42,880
Tio estas bela simpla tro - struct nodo * maldekstra infano;

400
00:30:42,880 --> 00:30:51,190
kaj struct nodo * dekstra infano. Cool.

401
00:30:51,190 --> 00:30:54,740
Tio aspektas kiel sufiĉe bona komenco.

402
00:30:54,740 --> 00:30:58,530
Ni reiru al la specifo.

403
00:30:58,530 --> 00:31:05,030
>> Nun ni bezonas por deklari tutmonda nodo * variablo por la radiko de arbo.

404
00:31:05,030 --> 00:31:10,590
Ni tuj faros ĉi tutmonda samkiel ni faris unuan puntero en nia ligitaj listo ankaŭ tutmonda.

405
00:31:10,590 --> 00:31:12,690
Tio estis tiel ke en la funkcioj kiuj ni skribi

406
00:31:12,690 --> 00:31:16,180
ni ne devas subteni pasi ĉirkaŭ ĉi radikon -

407
00:31:16,180 --> 00:31:19,620
kvankam ni vidos, ke se vi faros volas skribi tiujn funkciojn rekursie,

408
00:31:19,620 --> 00:31:22,830
gxi estu pli bone eĉ ne pasi ĝin ĉirkaŭ kiel tutmonda en unua loko

409
00:31:22,830 --> 00:31:28,090
kaj anstataŭ pravalorizi ĝin loke en via ĉefa funkcio.

410
00:31:28,090 --> 00:31:31,960
Sed, ni tion faros sume por komenci.

411
00:31:31,960 --> 00:31:39,920
Denove, ni donos kelkajn spacoj, kaj mi iros por deklari nodo * radiko.

412
00:31:39,920 --> 00:31:46,770
Nur por certigi ke mi ne forlasi tiun uninitialized, mi tuj metis ĝin egala al nula.

413
00:31:46,770 --> 00:31:52,210
Nun, en la ĉefa funkcio - kiu ni skribas vere rapide dekstre tie -

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
kaj mi tuj komencos deklari mian argv tabelo kiel const nur tiel, ke mi scias

416
00:32:10,640 --> 00:32:14,550
ke tiuj argumentoj estas argumentoj, ke mi probable ne volas modifi.

417
00:32:14,550 --> 00:32:18,390
Se mi volas modifi ilin mi probable faris kopiojn de ili.

418
00:32:18,390 --> 00:32:21,740
Vi vidos ĉi multon en kodo.

419
00:32:21,740 --> 00:32:25,440
Ĝi estas bone ajna maniero. Ĝi estas bone lasi ĝin kiel - preterlasi la const se vi ŝatus.

420
00:32:25,440 --> 00:32:28,630
Mi kutime metis ĝin en nur por ke Mi memoras min

421
00:32:28,630 --> 00:32:33,650
 ke mi probable ne volas modifi tiujn argumentojn.

422
00:32:33,650 --> 00:32:39,240
>> Kiel ĉiam, mi tuj inkluzivi ĉi reveno 0 linio je la fino de ĉefa.

423
00:32:39,240 --> 00:32:45,730
Jen, mi pravalorizi miaj radiko nodo.

424
00:32:45,730 --> 00:32:48,900
Kiel ĝi staras nun, mi havas puntero ke tio starigis al nula,

425
00:32:48,900 --> 00:32:52,970
do ĝi estas montrante nenion.

426
00:32:52,970 --> 00:32:57,480
Por efektive komenci konstrui la nodo,

427
00:32:57,480 --> 00:32:59,250
Mi unue bezonas rezervi memoron por ĝi.

428
00:32:59,250 --> 00:33:05,910
Mi faros tion farante memoro sur la havaĵon uzante malloc.

429
00:33:05,910 --> 00:33:10,660
Mi tuj starigis radiko egala al la rezulto de malloc,

430
00:33:10,660 --> 00:33:19,550
kaj mi tuj uzos la sizeof operatoro por kalkuli la grandecon de nodo.

431
00:33:19,550 --> 00:33:24,990
La kialo, ke mi uzas sizeof nodo kontraste al, diros,

432
00:33:24,990 --> 00:33:37,020
faras ion kiel tiu - malloc (4 + 4 +4) aŭ malloc 12 -

433
00:33:37,020 --> 00:33:40,820
estas ĉar mi volas mian kodon por esti kiel kongruaj ebla.

434
00:33:40,820 --> 00:33:44,540
Mi volas povi preni tion. C dosiero, kompili ĝin sur la aparaton,

435
00:33:44,540 --> 00:33:48,820
kaj tiam kompili ĝin sur mia 64-bita Mac -

436
00:33:48,820 --> 00:33:52,040
aŭ tute malsama arkitekturo -

437
00:33:52,040 --> 00:33:54,640
kaj mi volas tiun tutan labori la sama.

438
00:33:54,640 --> 00:33:59,510
>> Se mi faras supozojn pri la grandeco de variabloj -

439
00:33:59,510 --> 00:34:02,070
la grandeco de int aŭ la grandecon de puntero -

440
00:34:02,070 --> 00:34:06,070
tiam Mi ankaŭ faras supozojn pri la specoj de arkitekturoj

441
00:34:06,070 --> 00:34:10,440
sur kiu mia kodo povas sukcese kompili kiam kuri.

442
00:34:10,440 --> 00:34:15,030
Ĉiam uzi sizeof kiel kontraŭ permane sumanta la struct kampoj.

443
00:34:15,030 --> 00:34:20,500
La alia kialo estas, ke tie povus ankaŭ esti Plenigado ke la tradukilo metas en la struct.

444
00:34:20,500 --> 00:34:26,570
Eĉ nur sumanta la individuaj kampoj ne estas iu kiu vi tipe volas fari,

445
00:34:26,570 --> 00:34:30,340
tiel, forviŝi tiun linion.

446
00:34:30,340 --> 00:34:33,090
Nun, por vere pravalorizi ĉi radiko nodo,

447
00:34:33,090 --> 00:34:36,489
Mi tuj devos ŝtopi en valoroj por ĉiu el ĝiaj malsamaj kampoj.

448
00:34:36,489 --> 00:34:41,400
Ekzemple, por valoro Mi scias mi volas pravalorizi al 7,

449
00:34:41,400 --> 00:34:46,920
kaj cxar nun mi iros al starigis la maldekstran infano esti nula

450
00:34:46,920 --> 00:34:55,820
kaj la dekstra infano ankaŭ esti nula. Bonega!

451
00:34:55,820 --> 00:35:02,670
Ni faris tiun parton de la specifon.

452
00:35:02,670 --> 00:35:07,390
>> La specifo malsupren sur la fundo de la paĝo 3 demandas min krei tri pli nodoj -

453
00:35:07,390 --> 00:35:10,600
unu enhavanta 3, unu enhavante 6, kaj unu kun 9 -

454
00:35:10,600 --> 00:35:14,210
kaj tiam telegramon ilin tiom ĝi aspektas precize kiel nia arbo diagramon

455
00:35:14,210 --> 00:35:17,120
ke ni parolis pri antaŭe.

456
00:35:17,120 --> 00:35:20,450
Ni faras tion sufiĉe rapide tie.

457
00:35:20,450 --> 00:35:26,270
Vi vidos vere rapide, ke mi tuj komencu skribi faskon da duplikatajn kodo.

458
00:35:26,270 --> 00:35:32,100
Mi iros por krei nodo * kaj mi iros kaj nomas ĝin tri.

459
00:35:32,100 --> 00:35:36,000
Mi tuj metis ĝin egala al malloc (sizeof (nodo)).

460
00:35:36,000 --> 00:35:41,070
Mi tuj starigis tri-> valoro = 3.

461
00:35:41,070 --> 00:35:54,780
Tri -> left_child = NULL; tri -> dekstre _child = NULL; tiel.

462
00:35:54,780 --> 00:36:01,150
Tio aspektas bela simila al inicializar la radiko, kaj tio estas ĝuste kion

463
00:36:01,150 --> 00:36:05,760
Mi tuj devos fari se mi komencas inicializar 6 kaj 9 tiel.

464
00:36:05,760 --> 00:36:20,720
Mi faros, ke vere rapide tie - vere, mi faros iom kopio kaj alglui,

465
00:36:20,720 --> 00:36:46,140
kaj certigi, ke mi - bona.

466
00:36:46,470 --> 00:37:09,900
 Nun, mi got kopiis kaj mi povas antaŭeniri kaj starigis ĉi egala al 6.

467
00:37:09,900 --> 00:37:14,670
Vi povas vidi ke tiu prenas iom da tempo kaj ne estas super-efika.

468
00:37:14,670 --> 00:37:22,610
En malmulta, ni skribi funkcio kiu faros tion por ni.

469
00:37:22,610 --> 00:37:32,890
Mi volas anstataŭigi ĉi kun 9, anstataŭi ke kun 6.

470
00:37:32,890 --> 00:37:37,360
>> Nun ni havas nian tutan nodoj kreita kaj inicializado.

471
00:37:37,360 --> 00:37:41,200
Ni havas nian radiko starigis egala al 7, aŭ enhavas la valoron 7,

472
00:37:41,200 --> 00:37:46,510
nia nodo enhavanta 3, nia nodo enhavanta 6, kaj nia nodo enhavanta 9.

473
00:37:46,510 --> 00:37:50,390
Je ĉi tiu punkto, ĉiuj ni devas fari estas drato ĉio supren.

474
00:37:50,390 --> 00:37:53,020
La kialo mi inicializado ĉiuj punteros al nula estas nur por ke mi certiĝu, ke

475
00:37:53,020 --> 00:37:56,260
Mi ne havas neniun uninitialized punteros tien hazarde.

476
00:37:56,260 --> 00:38:02,290
Kaj ankaŭ pro tio ke, en ĉi tiu punkto, mi nur devas vere kunligi la nodoj inter si -

477
00:38:02,290 --> 00:38:04,750
al tiuj, kiuj ili estas reale ligita al - mi ne devas iri tra kaj fari

478
00:38:04,750 --> 00:38:08,240
certa, ke ĉiuj nulls estas en tie en la taŭgaj lokoj.

479
00:38:08,240 --> 00:38:15,630
>> Ekde la radiko, mi scias, ke la radiko la maldekstra infano estas 3.

480
00:38:15,630 --> 00:38:21,250
Mi scias, ke la radiko la dekstra infano estas 9.

481
00:38:21,250 --> 00:38:24,880
Post tio, la sola alia infano, ke mi forlasis zorgi pri

482
00:38:24,880 --> 00:38:39,080
estas 3 la dekstra infano, kiu estas 6.

483
00:38:39,080 --> 00:38:44,670
Je ĉi tiu punkto, ĉio aspektas sufiĉe bone.

484
00:38:44,670 --> 00:38:54,210
Ni forviŝi kelkajn el tiuj linioj.

485
00:38:54,210 --> 00:38:59,540
Nun ĉiu rigardas sufiĉe bone.

486
00:38:59,540 --> 00:39:04,240
Ni reiru al nia specifo kaj vidi kion ni devas fari.

487
00:39:04,240 --> 00:39:07,610
>> Je ĉi tiu punkto, ni devas skribi funkcion nomita 'enhavas'

488
00:39:07,610 --> 00:39:14,150
kun prototipo de 'bool enhavas (int valoro)'.

489
00:39:14,150 --> 00:39:17,060
Kaj tiu enhavas funkcion tuj revenos vera

490
00:39:17,060 --> 00:39:21,200
 se la arbo montris per nia tutmonda radiko variablo

491
00:39:21,200 --> 00:39:26,950
 enhavas la valoron transiris en la funkcio kaj falsaj alie.

492
00:39:26,950 --> 00:39:29,000
Ni faru tion.

493
00:39:29,000 --> 00:39:35,380
Ĉi tuj estos ĝuste kiel la serĉo, kiun ni faris per mano sur la iPad malmulta antaŭe.

494
00:39:35,380 --> 00:39:40,130
Estu la zoom reen en iomete kaj rulumu supren.

495
00:39:40,130 --> 00:39:43,130
Ni tuj metis ĉi funkcio dekstra supre nia ĉefa funkcio

496
00:39:43,130 --> 00:39:48,990
por ke ni ne devas fari ian prototipado.

497
00:39:48,990 --> 00:39:55,960
Do, bool enhavas (int valoro).

498
00:39:55,960 --> 00:40:00,330
Tie ni iru. Jen nia Boilerplate deklaro.

499
00:40:00,330 --> 00:40:02,900
Nur por certigi ke tiu estos kompili,

500
00:40:02,900 --> 00:40:06,820
Mi tuj iros antaŭen kaj nur starigis ĝin egala reveni falsaj.

501
00:40:06,820 --> 00:40:09,980
Ĝuste nun tiun funkcion nur ne faros nenion kaj ĉiam informi ke

502
00:40:09,980 --> 00:40:14,010
la valoro kiun ni serĉas ne estas en la arbo.

503
00:40:14,010 --> 00:40:16,280
>> Je ĉi tiu punkto, estas probable bona ideo -

504
00:40:16,280 --> 00:40:19,600
ekde ni skribis tuta amaso de kodo kaj ni eĉ ne provis taksi ĝin ankoraŭ -

505
00:40:19,600 --> 00:40:22,590
certigi ke ĉiuj kompilas.

506
00:40:22,590 --> 00:40:27,460
Estas kelkaj aferoj kiujn ni devas fari por certigi ke tiu estos efektive kompili.

507
00:40:27,460 --> 00:40:33,530
Unue, ĉu ni estis uzante ajnan funkcioj en ajna bibliotekoj ke ni ankoraŭ ne komprenis.

508
00:40:33,530 --> 00:40:37,940
La funkcioj ni uzis ĝis nun estas malloc,

509
00:40:37,940 --> 00:40:43,310
kaj tiam ni ankaŭ uzas tiun ĉi tipon - ĉi nenorma tipo nomita 'bool' -

510
00:40:43,310 --> 00:40:45,750
kio estas inkluzivita en la norma bool header dosiero.

511
00:40:45,750 --> 00:40:53,250
Ni definitive deziras inkludi normo bool.h por la bool tipo,

512
00:40:53,250 --> 00:40:59,230
kaj ni ankaŭ volas # include normo lib.h por la normo bibliotekoj

513
00:40:59,230 --> 00:41:03,530
kiuj inkludas malloc, kaj liberaj, kaj ĉio pri tio.

514
00:41:03,530 --> 00:41:08,660
Do, malzomi, ni tuj forlasis.

515
00:41:08,660 --> 00:41:14,190
Ni provu kaj certiĝu ke ĉi efektive faris kompili.

516
00:41:14,190 --> 00:41:18,150
Ni vidas ke ĝi faras, do ni estas sur la ĝusta vojo.

517
00:41:18,150 --> 00:41:22,990
>> Ni malfermi binary_tree.c denove.

518
00:41:22,990 --> 00:41:34,530
Ĝi kompilas. Ni iru malsupren kaj certigi ke ni enmetu iujn alvokojn al nia enhavas funkcio -

519
00:41:34,530 --> 00:41:40,130
nur por certigi ke jen ĉio bone kaj bona.

520
00:41:40,130 --> 00:41:43,170
Ekzemple, kiam ni faris kelkajn serĉoj en nia arbo antaŭe,

521
00:41:43,170 --> 00:41:48,500
ni provis serĉi la valoroj 6, 10, kaj 1, kaj ni sciis ke la 6 estis en la arbo,

522
00:41:48,500 --> 00:41:52,220
10 ne estis en la arbo, kaj 1 ne estis en la arbo ĉu.

523
00:41:52,220 --> 00:41:57,230
Ni uzas tiujn specimeno alvokoj kiel maniero por kalkuli ĉu aŭ ne

524
00:41:57,230 --> 00:41:59,880
nia enhavas funkcion laboras.

525
00:41:59,880 --> 00:42:05,210
Por fari tion, mi tuj uzos la printf funkcio,

526
00:42:05,210 --> 00:42:10,280
kaj ni tuj presi la rezulto de la alvoko al enhavas.

527
00:42:10,280 --> 00:42:13,280
Mi tuj metos en ĉeno "enhavas (% d) = pro

528
00:42:13,280 --> 00:42:20,470
 ni iras al plug en la valoro kiun ni iras serĉi,

529
00:42:20,470 --> 00:42:27,130
kaj =% s \ n "kaj uzas tiun kiel nia formato kordoj.

530
00:42:27,130 --> 00:42:30,720
Ni nur tuj vidi - laŭvorte presi sur la ekrano -

531
00:42:30,720 --> 00:42:32,060
kio aspektas kiel funkcio nomita.

532
00:42:32,060 --> 00:42:33,580
Tio ne estas vere la funkcio nomita.

533
00:42:33,580 --> 00:42:36,760
 Tiu estas nur ĉeno desegnita por aspekti kiel funkcio nomita.

534
00:42:36,760 --> 00:42:41,140
>> Nun, ni tuj ŝtopi en la valoroj.

535
00:42:41,140 --> 00:42:43,580
Ni tuj provos enhavas la 6,

536
00:42:43,580 --> 00:42:48,340
kaj poste, kion ni faros ĉi tie estas uzi tiun triargumenta operatoro.

537
00:42:48,340 --> 00:42:56,340
Ni vidu - enhavas 6 - tiel, nun mi enhavis 6 kaj se enhavas 6 estas vera,

538
00:42:56,340 --> 00:43:01,850
la kordo, ke ni tuj sendi al la% s formato karaktero

539
00:43:01,850 --> 00:43:04,850
tuj estos la ĉeno "vera".

540
00:43:04,850 --> 00:43:07,690
Ni rulumi pli iom.

541
00:43:07,690 --> 00:43:16,210
Alie, ni volas sendi la ĉeno "falsa" se enhavas 6 revenas falsaj.

542
00:43:16,210 --> 00:43:19,730
Tio estas iom ansera-aspekta, sed mi rigardas mi povus tiel ilustri

543
00:43:19,730 --> 00:43:23,780
kion la triargumenta operatoro similas ĉar ni ne vidis ĝin dum kelka tempo.

544
00:43:23,780 --> 00:43:27,670
Tiu estos bela, oportuna maniero por kalkuli se nia enhavas funkcion laboras.

545
00:43:27,670 --> 00:43:30,040
Mi iros por rulumi reen super la maldekstra,

546
00:43:30,040 --> 00:43:39,900
kaj mi tuj kopii kaj alglui ĉi tiun linion kelkajn fojojn.

547
00:43:39,900 --> 00:43:44,910
Ĝi ŝanĝis kelkajn el tiuj valoroj ĉirkaŭe,

548
00:43:44,910 --> 00:43:59,380
tial ĉi tiu tuj esti 1, kaj tion oni tuj estos 10.

549
00:43:59,380 --> 00:44:02,480
>> Je ĉi tiu punkto ni havas belan enhavas funkcio.

550
00:44:02,480 --> 00:44:06,080
Ni havas kelkajn provojn, kaj ni vidos se ĉi ĉiuj verkoj.

551
00:44:06,080 --> 00:44:08,120
Je ĉi tiu punkto ni skribas iun pli kodo.

552
00:44:08,120 --> 00:44:13,160
Tempo lasi eksteren kaj certigi ke ĉiu ankoraŭ kompilas.

553
00:44:13,160 --> 00:44:20,360
Quit eksteren, kaj nun ni provu fari duuma arbo denove.

554
00:44:20,360 --> 00:44:22,260
Nu, tio aspektas kiel ni havas eraron,

555
00:44:22,260 --> 00:44:26,930
kaj ni atingis tiun eksplicite deklari la biblioteko funkcio printf.

556
00:44:26,930 --> 00:44:39,350
Ĝi aspektas kiel ni devas iri en kaj # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Kaj kun tio, ĉiu devus kompili. Ni estas ĉiuj bonaj.

558
00:44:45,350 --> 00:44:50,420
Nun ni provu kurante duuma arbo kaj vidu kio okazas.

559
00:44:50,420 --> 00:44:53,520
Jen ni estas,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
kaj ni vidas tion, kiel ni atendis -

561
00:44:55,190 --> 00:44:56,910
ĉar ni ne ankoraŭ realigita enhavas ankoraŭ,

562
00:44:56,910 --> 00:44:59,800
aŭ pli ĝuste, ni ĵus metis en reveno falsaj -

563
00:44:59,800 --> 00:45:03,300
ni vidas ke ĝi estas nur redoni malvera por ĉiu el ili,

564
00:45:03,300 --> 00:45:06,180
tiel ke tio ĉio laboras plejparte sufiĉe bone.

565
00:45:06,180 --> 00:45:11,860
>> Ni iru reen en kaj efektive apliki enhavas je ĉi tiu punkto.

566
00:45:11,860 --> 00:45:17,490
Mi iros por rulumi malsupren, zomi, kaj -

567
00:45:17,490 --> 00:45:22,330
memoru, la algoritmo, ke ni uzis estis ke ni komencis ĉe la radika vertico

568
00:45:22,330 --> 00:45:28,010
kaj tiam ĉe ĉiu nodo, ke ni renkontas, ni faru komparon,

569
00:45:28,010 --> 00:45:32,380
kaj surbaze de tiu komparo ni ĉu movi al la maldekstra infano aŭ dekstre infano.

570
00:45:32,380 --> 00:45:39,670
Tiu tuj aspektas tre simila al la duuma serĉo kodo kiu ni skribis antaŭe en la termino.

571
00:45:39,670 --> 00:45:47,810
Kiam ni dividi, ni scias, ke ni volas tenadi la nuna nodo

572
00:45:47,810 --> 00:45:54,050
ke ni rigardas, kaj la nuna nodo tuj estos inicializado al la radika vertico.

573
00:45:54,050 --> 00:45:56,260
Kaj nun, ni iras plu iri tra la arbo,

574
00:45:56,260 --> 00:45:58,140
kaj memoru, ke nia haltante kondiĉo -

575
00:45:58,140 --> 00:46:01,870
 kiam ni efektive laboris tra la ekzemplo mane -

576
00:46:01,870 --> 00:46:03,960
Estis kiam ni renkontis nula nodo,

577
00:46:03,960 --> 00:46:05,480
ne kiam ni rigardis nula infano,

578
00:46:05,480 --> 00:46:09,620
sed prefere kiam ni efektive translokiĝis al nodo en la arbo

579
00:46:09,620 --> 00:46:12,640
kaj trovis, ke ni estas en nula nodo.

580
00:46:12,640 --> 00:46:20,720
Ni tuj persisti ĝis nuna ne estas egala al nula.

581
00:46:20,720 --> 00:46:22,920
Kaj kion ni faros?

582
00:46:22,920 --> 00:46:31,610
Ni tuj testi se (nuna -> valoro == valoro),

583
00:46:31,610 --> 00:46:35,160
tiam ni scias ke ni vere trovis la nodo ke ni serĉas.

584
00:46:35,160 --> 00:46:40,450
Do jen, ni povas reveni vera.

585
00:46:40,450 --> 00:46:49,830
Alie, ni volas vidi, ĉu aŭ ne la valoro estas malpli ol la valoro.

586
00:46:49,830 --> 00:46:53,850
Se la nuna nodo valoro estas malpli ol la valoro ni serĉas,

587
00:46:53,850 --> 00:46:57,280
ni iras al movi al dekstre.

588
00:46:57,280 --> 00:47:10,600
Do, nuna = nuna -> right_child, kaj alie, ni iras al movi al la maldekstra.

589
00:47:10,600 --> 00:47:17,480
nuna = nuna -> left_child;. Bela simpla.

590
00:47:17,480 --> 00:47:22,830
>> Vi verŝajne rekoni la buklo kiun aspektas tre simila al tiu de

591
00:47:22,830 --> 00:47:27,580
duuma serĉo antaŭe en la termino, krom tiam ni pritraktas malalta, meze, kaj alta.

592
00:47:27,580 --> 00:47:30,000
Tie, ni nur devas rigardi aktualan valoron,

593
00:47:30,000 --> 00:47:31,930
do ĝi estas bela kaj simpla.

594
00:47:31,930 --> 00:47:34,960
Ni certigi ĉi tiun kodon laboras.

595
00:47:34,960 --> 00:47:42,780
Unue, certigu kompilas. Aspektas kiel ĝi faras.

596
00:47:42,780 --> 00:47:47,920
Ni provu kurante ĝin.

597
00:47:47,920 --> 00:47:50,160
Kaj ja, ĝi presas el ĉio, kio ni atendis.

598
00:47:50,160 --> 00:47:54,320
Li trovas 6 en la arbo, ne trovas 10 ĉar 10 estas ne en la arbo,

599
00:47:54,320 --> 00:47:57,740
kaj ne trovas 1 bone ĉar 1 estas ankaŭ ne en la arbo.

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

601
00:48:01,420 --> 00:48:04,470
>> Alright. Ni reiru al nia specifo kaj vidu kio estas proksima.

602
00:48:04,470 --> 00:48:07,990
Nun, ĝi volas aldoni iun pli nodoj al nia arbo.

603
00:48:07,990 --> 00:48:11,690
Ĝi volas aldoni 5, 2, kaj 8, kaj certigi ke nia enhavas kodo

604
00:48:11,690 --> 00:48:13,570
ankoraŭ funkcias kiel atendita.

605
00:48:13,570 --> 00:48:14,900
Ni iru do that.

606
00:48:14,900 --> 00:48:19,430
Je ĉi tiu punkto, anstataŭ fari tion tedas kopio kaj alglui denove,

607
00:48:19,430 --> 00:48:23,770
ni skribu funkcio por fakte krei nodo.

608
00:48:23,770 --> 00:48:27,740
Se ni rulumu malsupren la tuta vojo al la ĉefa, ni vidas ke ni estis farante tiun

609
00:48:27,740 --> 00:48:31,210
tre simila kodo denove kaj denove ĉiufoje ke ni volas krei nodo.

610
00:48:31,210 --> 00:48:39,540
>> Ni skribi funkcion kiu vere konstruos nodo por ni kaj redoni ĝin.

611
00:48:39,540 --> 00:48:41,960
Mi iros nomi ĝin build_node.

612
00:48:41,960 --> 00:48:45,130
Mi iros por konstrui nodo kun aparta valoro.

613
00:48:45,130 --> 00:48:51,040
Zomi tie.

614
00:48:51,040 --> 00:48:56,600
La unua afero Mi faros fakte krei spacon por la nodo sur la monteto.

615
00:48:56,600 --> 00:49:05,400
Do, nodo * n = malloc (sizeof (nodo)); n -> valoro = valoro;

616
00:49:05,400 --> 00:49:14,960
kaj tiam ĉi tie, mi nur iras al pravalorizi ĉiuj kampoj por esti taŭga valoroj.

617
00:49:14,960 --> 00:49:22,500
Kaj je la fino, ni revenos nia nodo.

618
00:49:22,500 --> 00:49:28,690
Alright. Unu afero noti estas ke tiu funkcio ĉi tie

619
00:49:28,690 --> 00:49:34,320
tuj revenos puntero al memoro kiu estis amaso-destinis.

620
00:49:34,320 --> 00:49:38,880
Kio estas agrable pri tio estas ke tiu nodo nun -

621
00:49:38,880 --> 00:49:42,420
ni devas deklari gxin sur la havaĵon ĉar se ni deklaras ĝin sur la stako

622
00:49:42,420 --> 00:49:45,050
ni ne povos fari ĝin en tiu funkcio kiel ĉi tio.

623
00:49:45,050 --> 00:49:47,690
Tiu memoro irus el atingo

624
00:49:47,690 --> 00:49:51,590
kaj estus nevalida se ni provis aliri ĝin poste.

625
00:49:51,590 --> 00:49:53,500
Ekde ni deklari amason-asignitaj memoro,

626
00:49:53,500 --> 00:49:55,830
tuj devas prizorgi liberigante ĝin poste

627
00:49:55,830 --> 00:49:58,530
por nia programo ne filtri ajna memoro.

628
00:49:58,530 --> 00:50:01,270
Ni estis punting en tiu por ĉio alia en la kodo

629
00:50:01,270 --> 00:50:02,880
nur por simpleco, kalkaj en la momento,

630
00:50:02,880 --> 00:50:05,610
sed se vi iam skribi funkcion kiu similas tiun

631
00:50:05,610 --> 00:50:10,370
kie vi havas - iuj nomas ĝin malloc aŭ realloc interne -

632
00:50:10,370 --> 00:50:14,330
vi volas certigi ke vi metis ian komenton ĉi tien kiu diras,

633
00:50:14,330 --> 00:50:29,970
hey, vi scias, denove amason-asignitaj nodo inicializado kun la pasinta-en valoro.

634
00:50:29,970 --> 00:50:33,600
Kaj tiam vi volas certigi ke vi metis en ia noto kiu diras

635
00:50:33,600 --> 00:50:41,720
la telefonanto devas liberigi la memoron revenis.

636
00:50:41,720 --> 00:50:45,450
Tiun vojon, se iu iam iras kaj uzas tiun funkcion,

637
00:50:45,450 --> 00:50:48,150
ili scias, ke kion ajn ili reiros de tiu funkcio

638
00:50:48,150 --> 00:50:50,870
en iu momento bezonos esti liberigita.

639
00:50:50,870 --> 00:50:53,940
>> Supozante ke cxio estas bone kaj bonajn tie,

640
00:50:53,940 --> 00:51:02,300
ni povas iri en nian kodon kaj anstataŭu ĉiujn el tiuj linioj ĉi tie

641
00:51:02,300 --> 00:51:05,410
kun alvokoj al nia build nodo funkcio.

642
00:51:05,410 --> 00:51:08,170
Ni faras tion vere rapide.

643
00:51:08,170 --> 00:51:15,840
La parto kiu ni ne tuj anstataŭigi estas tiu parto cxi tie

644
00:51:15,840 --> 00:51:18,520
ĉe la malsupro, kie ni fakte telegramon ĝis la nodoj noti al si,

645
00:51:18,520 --> 00:51:21,030
ĉar ni ne povas fari en nia funkcio.

646
00:51:21,030 --> 00:51:37,400
Sed, ni faru radiko = build_node (7); nodo * tri = build_node (3);

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

648
00:51:47,980 --> 00:51:52,590
Kaj nun, ni ankaŭ volis aldoni nodoj por -

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

650
00:52:03,530 --> 00:52:09,760
kaj kio estis la alia vertico? Vidu ĉi tie. Ni volis ankaŭ aldoni 2 -

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

652
00:52:20,280 --> 00:52:26,850
Alright. Je ĉi tiu punkto, ni scias ke ni havas la 7, la 3, la 9, kaj la 6

653
00:52:26,850 --> 00:52:30,320
ĉiuj telegramis supren taŭge, sed kio pri la 5, la 8, kaj la 2?

654
00:52:30,320 --> 00:52:33,550
Teni ĉion en la taŭgan ordon,

655
00:52:33,550 --> 00:52:39,230
ni scias ke tri la dekstra infano estas 6.

656
00:52:39,230 --> 00:52:40,890
Do, se ni tuj aldonu la 5,

657
00:52:40,890 --> 00:52:46,670
la 5 ankaŭ apartenas en la dekstra flanko de la arbo de kiuj 3 estas la radiko,

658
00:52:46,670 --> 00:52:50,440
tiel 5 apartenas la maldekstra infano de 6.

659
00:52:50,440 --> 00:52:58,650
Ni povas fari ĉi tion dirante, ses -> left_child = kvin;

660
00:52:58,650 --> 00:53:10,790
kaj tiam la 8 apartenas la maldekstra infano de 9, do naŭ -> left_child = ok;

661
00:53:10,790 --> 00:53:22,190
kaj poste 2 estas la maldekstra infano de 3, do ni povas fari tion ĝis tie - vi -> left_child = du;.

662
00:53:22,190 --> 00:53:27,730
Se vi ne sufiĉe sekvi kune kun tio, mi sugestas al vi desegni ĝin vi mem.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Ni savu ĉi. Ni eliros kaj certigi kompilas,

664
00:53:35,660 --> 00:53:40,760
kaj tiam ni povas aldoni en nia enhavas alvokoj.

665
00:53:40,760 --> 00:53:44,120
Aspektas kiel ĉiu ankoraŭ kompilas.

666
00:53:44,120 --> 00:53:51,790
Ni iru en kaj aldoni en iu enhavas alvokoj.

667
00:53:51,790 --> 00:53:59,640
Denove, mi faros iom de kopio kaj pasto.

668
00:53:59,640 --> 00:54:15,860
Nun estu la serĉo por 5, 8, kaj 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Ni certigu ke ĉi ĉiuj aspektas bone ankoraŭ. Bonega! Gardi kaj quit.

670
00:54:28,330 --> 00:54:33,220
Nun ni faru, kompili, kaj nun ni kuras.

671
00:54:33,220 --> 00:54:37,540
El la rezultoj, ĝi aspektas kiel cxio funkcias nur bela kaj bone.

672
00:54:37,540 --> 00:54:41,780
Bonega! Do nun ni havas niajn enhavas funkcion skribita.

673
00:54:41,780 --> 00:54:46,160
Ni movi sur kaj komenci labori pri kiel enmeti nodoj en la arbo

674
00:54:46,160 --> 00:54:50,000
pro tio ke, kiel ni faras ĝin nun, aĵoj ne estas tre bela.

675
00:54:50,000 --> 00:54:52,280
>> Se ni reiru al la specifo,

676
00:54:52,280 --> 00:55:00,540
ĝi petas al ni skribi funkcion nomita insertar - denove, revenante al bool

677
00:55:00,540 --> 00:55:04,400
cxar se ne ni povus efektive enŝovu la nodo en la arbo -

678
00:55:04,400 --> 00:55:07,710
kaj tiam la valoro por enmeti en la arbo estas specifita kiel

679
00:55:07,710 --> 00:55:11,060
la sola argumento por nia insert funkcio.

680
00:55:11,060 --> 00:55:18,180
Ni revenos vera se ni povus ja enmetas la nodo enhavanta valoro al la arbo,

681
00:55:18,180 --> 00:55:20,930
kio signifas, ke ni, unu, havis sufiĉan memoron,

682
00:55:20,930 --> 00:55:24,840
kaj poste du, kiu nodo ne jam ekzistas en la arbo ekde -

683
00:55:24,840 --> 00:55:32,170
memoru, ni ne tuj havas duplikatajn valoroj en la arbo, nur por fari aĵojn simpla.

684
00:55:32,170 --> 00:55:35,590
Alright. Back al la kodo.

685
00:55:35,590 --> 00:55:44,240
Malfermu ĝin. Zoom en iom, tiam rulumu malsupren.

686
00:55:44,240 --> 00:55:47,220
Ni metis la insert funkcio dekstra super la enhavas.

687
00:55:47,220 --> 00:55:56,360
Denove, ĝi tuj nomos bool insert (int valoro).

688
00:55:56,360 --> 00:56:01,840
Donu ĝin iom pli da spaco, kaj tiam, kiel defaŭlta,

689
00:56:01,840 --> 00:56:08,870
ni metas en reveno falsa al la fino.

690
00:56:08,870 --> 00:56:22,620
Nun malsupren sur la fundo, ni iru antaŭen kaj anstataŭ permane konstrui la nodoj

691
00:56:22,620 --> 00:56:27,900
en ĉefa nin kaj cableado ilin atentigi al la alia kiel ni faras,

692
00:56:27,900 --> 00:56:30,600
ni fidas niajn insert funkcio por fari tion.

693
00:56:30,600 --> 00:56:35,510
Ni ne fidi niajn insert funkcio por konstrui la tuta arbo de nulo nur ankoraŭ,

694
00:56:35,510 --> 00:56:39,970
sed prefere ni forigi tiujn liniojn - we'll comment el tiuj linioj -

695
00:56:39,970 --> 00:56:43,430
ke konstrui la nodoj 5, 8, kaj 2.

696
00:56:43,430 --> 00:56:55,740
Kaj anstataŭe, ni enŝovu alvokoj al nia insert funkcio

697
00:56:55,740 --> 00:57:01,280
por certiĝi ke tiu fakte funkcias.

698
00:57:01,280 --> 00:57:05,840
Ĉi tie ni iru.

699
00:57:05,840 --> 00:57:09,300
>> Nun ni diris ĉi tiujn liniojn.

700
00:57:09,300 --> 00:57:13,700
Ni nur havas 7, 3, 9, kaj 6 en nia arbo ĉe ĉi tiu punkto.

701
00:57:13,700 --> 00:57:18,870
Por certigi ke ĉi tio ĉiuj laboras,

702
00:57:18,870 --> 00:57:25,050
ni povas malzomi, fari nian duuma arbo,

703
00:57:25,050 --> 00:57:30,750
ruli ĝin, kaj ni povas vidi ke ĝi enhavas nun diras al ni ke ni tute rajtas -

704
00:57:30,750 --> 00:57:33,110
5, 8, kaj 2 jam ne en la arbo.

705
00:57:33,110 --> 00:57:37,960
Iru returne en la kodo,

706
00:57:37,960 --> 00:57:41,070
kaj kiel ni tuj enigi?

707
00:57:41,070 --> 00:57:46,290
Memoru, kion ni faris kiam ni efektive enmeto 5, 8, kaj 2 antaŭe.

708
00:57:46,290 --> 00:57:50,100
Ni ludis tiun Plinko ludo kie ni komencis ĉe la radiko,

709
00:57:50,100 --> 00:57:52,780
malsupreniris la arbo unu post la alia per unu

710
00:57:52,780 --> 00:57:54,980
gxis ni trovis la taŭgan breĉo,

711
00:57:54,980 --> 00:57:57,570
kaj poste ni telegramis en la nodo ĉe la taŭga loko.

712
00:57:57,570 --> 00:57:59,480
Ni faros la samon.

713
00:57:59,480 --> 00:58:04,070
Tio estas esence kiel skribi la kodon kiun ni uzas en la enhavas funkcio

714
00:58:04,070 --> 00:58:05,910
trovi la lokon, kie la nodo devas esti,

715
00:58:05,910 --> 00:58:10,560
kaj tiam ni ĵus tuj enigi la nodo prava.

716
00:58:10,560 --> 00:58:17,000
Ni komencu fari tion.

717
00:58:17,000 --> 00:58:24,200
>> Do ni havas nodo * nuna = radiko; ni nur tuj sekvu la enhavas kodo

718
00:58:24,200 --> 00:58:26,850
ĝis ni trovos ke ĝi ne sufiĉe laboras por ni.

719
00:58:26,850 --> 00:58:32,390
Ni tuj iros tra la arbo dum la aktuala elemento ne estas nulaj,

720
00:58:32,390 --> 00:58:45,280
kaj se ni trovas ke nuna valoro egalas al la valoro kiu ni provas enmeti -

721
00:58:45,280 --> 00:58:49,600
bone, tio estas unu el la kazoj en kiuj oni ne povis reale enŝovu la nodo

722
00:58:49,600 --> 00:58:52,730
en la arbo ĉar ĉi signifas ke ni havas duplikatajn valoro.

723
00:58:52,730 --> 00:58:59,010
Jen ni fakte tuj revenos falsaj.

724
00:58:59,010 --> 00:59:08,440
Nun, alie se nuna valoro estas malpli ol valoro,

725
00:59:08,440 --> 00:59:10,930
nun ni scias ke ni movi al la dekstra

726
00:59:10,930 --> 00:59:17,190
 ĉar la valoro apartenas en la dekstra duono de la nuna arbo.

727
00:59:17,190 --> 00:59:30,110
Alie, ni iras al movi al la maldekstra.

728
00:59:30,110 --> 00:59:37,980
Tio estas esence nia enhavas funkcii ĝuste tie.

729
00:59:37,980 --> 00:59:41,820
>> Je ĉi tiu punkto, iam ni kompletigis ĉi dum ciklo,

730
00:59:41,820 --> 00:59:47,350
nia nuna puntero tuj estos montrante al nula

731
00:59:47,350 --> 00:59:51,540
se la funkcio ne jam revenis.

732
00:59:51,540 --> 00:59:58,710
Ni do havi nuna ĉe la loko, kie ni volas enmeti la novan nodo.

733
00:59:58,710 --> 01:00:05,210
Kio restas farenda estas reale konstrui la nova nodo,

734
01:00:05,210 --> 01:00:08,480
kion ni povas fari belajn facile.

735
01:00:08,480 --> 01:00:14,930
Ni povas uzi nian super-oportuna build nodo funkcio,

736
01:00:14,930 --> 01:00:17,210
kaj iu kiun ni ne faris pli frue -

737
01:00:17,210 --> 01:00:21,400
ni nur ia prenis por donita sed nun ni faros nur por certigi -

738
01:00:21,400 --> 01:00:27,130
ni testi por certigi ke la valoro revenis por nova nodo estis vere

739
01:00:27,130 --> 01:00:33,410
ne nula, ĉar ni ne volas komenci alirante kiun memoro se ĝi estas nula.

740
01:00:33,410 --> 01:00:39,910
Ni povas provi certigi ke nova nodo estas ne egala al nula.

741
01:00:39,910 --> 01:00:42,910
Aŭ male, ni povas nur vidi, ĉu ĝi vere estas nula,

742
01:00:42,910 --> 01:00:52,120
kaj se estas nula, tiam ni povas nur redoni malvera frue.

743
01:00:52,120 --> 01:00:59,090
>> Je ĉi tiu punkto, ni devas telegramon nova nodo en lia taŭga loko en la arbo.

744
01:00:59,090 --> 01:01:03,510
Se ni retrorigardas al la ĉefa kaj kie ni estis vere cableado en valoroj antaŭ,

745
01:01:03,510 --> 01:01:08,470
ni vidas ke la vojo ni faris ĝin kiam ni volis meti 3 en la arbo

746
01:01:08,470 --> 01:01:11,750
Estis ni Montrita la maldekstra infano de radiko.

747
01:01:11,750 --> 01:01:14,920
Kiam ni metas 9 en la arbo, ni devis aliri al la dekstra infano de la radiko.

748
01:01:14,920 --> 01:01:21,030
Ni devis havi sagon al la patro por enmeti novan valoron en la arbo.

749
01:01:21,030 --> 01:01:24,430
Movo reen ĝis enigi, ke ne estas tuj tute labori tie

750
01:01:24,430 --> 01:01:27,550
ĉar ni ne havas patro puntero.

751
01:01:27,550 --> 01:01:31,650
Kion ni volas por povi fari estas, en ĉi tiu punkto,

752
01:01:31,650 --> 01:01:37,080
kontrolu la gepatroj valoro kaj rigardu - nu, ho,

753
01:01:37,080 --> 01:01:41,990
se la gepatroj valoro estas malpli ol la aktuala valoro,

754
01:01:41,990 --> 01:01:54,440
tiam la patro la dekstra infano devus esti la nova vertico;

755
01:01:54,440 --> 01:02:07,280
se ne, la patro de maldekstra infano devus esti la nova nodo.

756
01:02:07,280 --> 01:02:10,290
Sed, ni ne havas tiun patro puntero sufiĉe ankoraŭ.

757
01:02:10,290 --> 01:02:15,010
>> Por akiri ĝin, ni fakte tuj devos sekvi ĝin kiel ni iru tra la arbo

758
01:02:15,010 --> 01:02:18,440
kaj trovi la taŭgan lokon en nia ciklo supre.

759
01:02:18,440 --> 01:02:26,840
Ni povas fari tion per movo reen sur la supron de nia insert funkcio

760
01:02:26,840 --> 01:02:32,350
kaj sekvado alia puntero variablo nomata patro.

761
01:02:32,350 --> 01:02:39,340
Ni tuj starigis ĝin egala al nula komence,

762
01:02:39,340 --> 01:02:43,640
kaj tiam ĉiu tempo ni iru tra la arbo,

763
01:02:43,640 --> 01:02:51,540
nin tuj fiksis la patro puntero por kongrui la nuna puntero.

764
01:02:51,540 --> 01:02:59,140
Ŝanĝu patro egala al nuna.

765
01:02:59,140 --> 01:03:02,260
Tiel, ĉiu tempo ni trairi,

766
01:03:02,260 --> 01:03:05,550
ni iras por certigi ke la nuna puntero gets incremented

767
01:03:05,550 --> 01:03:12,640
la patro puntero sekvas - nur unu nivelo pli alta ol la aktuala puntero en la arbo.

768
01:03:12,640 --> 01:03:17,370
Ke ĉiuj aspektas sufiĉe bone.

769
01:03:17,370 --> 01:03:22,380
>> Mi kredas la sola afero ke ni volas ĝustigi estas ĉi konstruos nodo reveni nula.

770
01:03:22,380 --> 01:03:25,380
Por akiri konstrui nodo por fakte sukcese revenos nula,

771
01:03:25,380 --> 01:03:31,060
ni devos modifi tiu kodo,

772
01:03:31,060 --> 01:03:37,270
ĉar tie, ni neniam provis certigi ke malloc revenis validan puntero.

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

774
01:03:53,390 --> 01:03:55,250
se malloc revenis validan pointer, tiam ni pravalorizi ĝin;

775
01:03:55,250 --> 01:04:02,540
alie, ni simple reveni kaj kiu finos reveni nula por ni.

776
01:04:02,540 --> 01:04:13,050
Kaj cxio aspektas sufiĉe bone. Ni certigi ĉi reale kompilas.

777
01:04:13,050 --> 01:04:22,240
Faru duuma arbo, kaj ho, ni havas kelkajn aĵojn okazas tie.

778
01:04:22,240 --> 01:04:29,230
>> Ni havas implicitan deklaron de funkcio konstrui nodo.

779
01:04:29,230 --> 01:04:31,950
Denove, kun ĉi tiuj tradukiloj, ni tuj komencos je la supro.

780
01:04:31,950 --> 01:04:36,380
Kion tio devas signifi estas ke mi vokas konstrui nodo antaux mi reale deklaris ĝin.

781
01:04:36,380 --> 01:04:37,730
Ni reiru al la kodo vere rapide.

782
01:04:37,730 --> 01:04:43,510
Rulumu malsupren, kaj vi pravis, mia insert funkcio estas deklarita

783
01:04:43,510 --> 01:04:47,400
super la muntaĵo nodo funkcio,

784
01:04:47,400 --> 01:04:50,070
sed mi provas uzi konstrui nodo ene de insert.

785
01:04:50,070 --> 01:05:06,610
Mi tuj iros kaj kopio - kaj tiam almeti la muntaĵo nodo funkcio vojo ĉi tien al la pinto.

786
01:05:06,610 --> 01:05:11,750
Tiu vojo, mi esperas ke ĝi funkcios. Ni donu tiun alian iri.

787
01:05:11,750 --> 01:05:18,920
Nun ĉiuj kompilas. Ĉiuj estas bona.

788
01:05:18,920 --> 01:05:21,640
>> Sed en ĉi tiu punkto, ni ne vere nomas nian insert funkcio.

789
01:05:21,640 --> 01:05:26,510
Ni nur scias, ke ĝi kompilas, do ni iros kaj metis kelkajn alvokojn in

790
01:05:26,510 --> 01:05:28,240
Ni faras tion en nia ĉefa funkcio.

791
01:05:28,240 --> 01:05:32,390
Tie, ni diris el 5, 8, kaj 2,

792
01:05:32,390 --> 01:05:36,680
kaj tiam ni ne telegramon ilin cxi tie.

793
01:05:36,680 --> 01:05:41,640
Ni faras iujn alvokojn por enigi,

794
01:05:41,640 --> 01:05:46,440
kaj ni ankaux uzas la saman specon de aĵoj kiujn ni uzas

795
01:05:46,440 --> 01:05:52,810
kiam ni faris tiujn printf alvokoj por certigi ke cxio ne get insertos konvene.

796
01:05:52,810 --> 01:06:00,550
Mi tuj kopii kaj alglui,

797
01:06:00,550 --> 01:06:12,450
kaj anstataŭ enhavas ni tuj faros insert.

798
01:06:12,450 --> 01:06:30,140
Kaj anstataŭ 6, 10, kaj 1, ni tuj uzos 5, 8, kaj 2.

799
01:06:30,140 --> 01:06:37,320
Tiu devus espereble enmeti 5, 8, kaj 2 en la arbo.

800
01:06:37,320 --> 01:06:44,050
Kompili. Ĉiuj estas bona. Nun ni vere kuras nia programo.

801
01:06:44,050 --> 01:06:47,330
>> Ĉiu revenis falsaj.

802
01:06:47,330 --> 01:06:53,830
Do, 5, 8, kaj 2 ne iru, kaj ĝi similas enhavas ne trovis ilin ankaŭ ne.

803
01:06:53,830 --> 01:06:58,890
Kio okazas? Ni malzomi.

804
01:06:58,890 --> 01:07:02,160
La unua problemo estis ke insert ŝajnis reveni falsa,

805
01:07:02,160 --> 01:07:08,750
kaj ĝi similas ke estas ĉar ni forlasis en nia reveno falsa alvoko,

806
01:07:08,750 --> 01:07:14,590
kaj ni neniam vere revenis vera.

807
01:07:14,590 --> 01:07:17,880
Ni povas difini, ke ĝis.

808
01:07:17,880 --> 01:07:25,290
La dua problemo estas, nun, eĉ se ni devas fari - krom tio, quit ĉi,

809
01:07:25,290 --> 01:07:34,530
kuri fari denove, ili ĝin kompili, tiam kuras ĝi -

810
01:07:34,530 --> 01:07:37,670
ni vidas ke io okazis tie.

811
01:07:37,670 --> 01:07:42,980
La 5, 8, kaj 2 estis ankoraŭ neniam trovis en la arbo.

812
01:07:42,980 --> 01:07:44,350
Do, kio okazas?

813
01:07:44,350 --> 01:07:45,700
>> Ni rigardu tiun en la kodo.

814
01:07:45,700 --> 01:07:49,790
Ni vidu se ni povas kompreni ĉi tion.

815
01:07:49,790 --> 01:07:57,940
Ni komencu per la patro ne esti nulaj.

816
01:07:57,940 --> 01:07:59,510
Ni starigis la nunan puntero egala al la radiko pointer,

817
01:07:59,510 --> 01:08:04,280
kaj ni iras por labori nian vojon tra la arbo.

818
01:08:04,280 --> 01:08:08,650
Se la nuna nodo estas ne nula, tiam ni scios, ke ni povas movi malsupren iomete.

819
01:08:08,650 --> 01:08:12,330
Ni metis niajn patro puntero esti egala al la nuna pointer,

820
01:08:12,330 --> 01:08:15,420
kontrolis la valoro - se la valoroj estas samaj ni revenis falsaj.

821
01:08:15,420 --> 01:08:17,540
Se la valoroj estas malpli ni translokiĝis al la dekstra;

822
01:08:17,540 --> 01:08:20,399
alie, ni translokiĝis al la maldekstra.

823
01:08:20,399 --> 01:08:24,220
Tiam ni konstruos nodo. Mi zomi iomete.

824
01:08:24,220 --> 01:08:31,410
Kaj tie, ni provos telegramon ĝis la valoroj esti la sama.

825
01:08:31,410 --> 01:08:37,250
Kio okazas? Ni vidu se eble Valgrind povas doni al ni aludo.

826
01:08:37,250 --> 01:08:43,910
>> Mi ŝatas uzi Valgrind nur ĉar Valgrind vere rapide kuras

827
01:08:43,910 --> 01:08:46,729
kaj diras al vi se estas iu memoro eraroj.

828
01:08:46,729 --> 01:08:48,300
Kiam ni kuras Valgrind en la kodo,

829
01:08:48,300 --> 01:08:55,859
kiel vi povas vidi dekstre here--Valgrind./binary_tree--and sukceson eniri.

830
01:08:55,859 --> 01:09:03,640
Vi vidas ke ni ne havis neniun memoro eraro, tiel ĝi aspektas kiel cxio estas bone ĝis nun.

831
01:09:03,640 --> 01:09:07,529
Ni ja havas iujn memoro fugoj, kiun ni konas, ĉar ni ne estas

832
01:09:07,529 --> 01:09:08,910
okazas liberigi iun el niaj nodoj.

833
01:09:08,910 --> 01:09:13,050
Ni provu kurante GDB vidi kio reale okazas.

834
01:09:13,050 --> 01:09:20,010
Ni faros gdb. / Binary_tree. Ĝi booted supren nur fajna.

835
01:09:20,010 --> 01:09:23,670
Ni starigis ripozon punkto sur insert.

836
01:09:23,670 --> 01:09:28,600
Ni kuras.

837
01:09:28,600 --> 01:09:31,200
Ĝi aspektas kiel ni neniam vere nomas insert.

838
01:09:31,200 --> 01:09:39,410
Ĝi aspektas kiel la problemo estis nur, ke kiam mi ŝanĝis cxi tie en ĉefa -

839
01:09:39,410 --> 01:09:44,279
ĉiuj el tiuj printf alvokoj de enhavas -

840
01:09:44,279 --> 01:09:56,430
Mi neniam vere ŝanĝiĝis tiuj nomi insert.

841
01:09:56,430 --> 01:10:01,660
Nun ni doni try. Ni kompili.

842
01:10:01,660 --> 01:10:09,130
Ĉiuj aspektas bona tie. Nun ni provu kurante ĝin, vidu kio okazas.

843
01:10:09,130 --> 01:10:13,320
Alright! Ĉio aspektas sufiĉe bona tie.

844
01:10:13,320 --> 01:10:18,130
>> La fina afero pensi estas, estas tie neniu eĝo kazoj al ĉi insert?

845
01:10:18,130 --> 01:10:23,170
Kaj ĝi rezultas ke, nu, la unu rando kazo kiu estas ĉiam interese pensi

846
01:10:23,170 --> 01:10:26,250
estas, kio okazas se via arbo estas malplena kaj vi nomas tiun insert funkcio?

847
01:10:26,250 --> 01:10:30,330
Ĉu ĝi funkcias? Nu, ni provu.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree. C -

849
01:10:32,110 --> 01:10:35,810
La vojo ni iros por provi ĉi estas, ni tuj iru al nia ĉefa funkcio,

850
01:10:35,810 --> 01:10:41,690
kaj anstataŭ cableado tiuj nodoj ĉe kiel ĉi tiu,

851
01:10:41,690 --> 01:10:56,730
ni ĵus tuj diros el la tuta afero,

852
01:10:56,730 --> 01:11:02,620
kaj anstataŭ cableado ĝis la nodoj ni mem,

853
01:11:02,620 --> 01:11:09,400
ni povas reale nur antaŭeniri kaj forviŝi ĉion ĉi.

854
01:11:09,400 --> 01:11:17,560
Ni tuj faros ĉiu alvoko por enmeti.

855
01:11:17,560 --> 01:11:49,020
Do, ni faru - anstataŭ 5, 8, kaj 2, ni tuj enigi 7, 3, kaj 9.

856
01:11:49,020 --> 01:11:58,440
Kaj tiam ni ankaŭ volas enmeti 6 tiel.

857
01:11:58,440 --> 01:12:05,190
Savi. Quit. Faru duuma arbo.

858
01:12:05,190 --> 01:12:08,540
Ĉiu kompilas.

859
01:12:08,540 --> 01:12:10,320
Ni povas nur funkcii kiel estas kaj vidi kio okazas,

860
01:12:10,320 --> 01:12:12,770
sed ĝi estas ankaŭ tuj estos vere grava por certigi ke

861
01:12:12,770 --> 01:12:14,740
ni ne havas ajnan memoro eraroj,

862
01:12:14,740 --> 01:12:16,840
ekde ĉi tiu estas unu el niaj rando kazoj, ke ni scias pri.

863
01:12:16,840 --> 01:12:20,150
>> Ni certigas, ke ĝi funkcias bone sub Valgrind,

864
01:12:20,150 --> 01:12:28,310
kiuj ni faros por nur kurante Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Ĝi aspektas kiel ni ja havas unu eraro de unu kunteksto -

866
01:12:31,110 --> 01:12:33,790
ni havas ĉi segmentación kulpo.

867
01:12:33,790 --> 01:12:36,690
Kio okazis?

868
01:12:36,690 --> 01:12:41,650
Valgrind fakte diras al ni kie ĝi estas.

869
01:12:41,650 --> 01:12:43,050
Malzomi iomete.

870
01:12:43,050 --> 01:12:46,040
Ĝi aspektas kiel ĝi okazas en nia insert funkcio,

871
01:12:46,040 --> 01:12:53,420
kie ni havas nevalidan legu de grandeco 4, je insert, linio 60.

872
01:12:53,420 --> 01:13:03,590
Ni iru tien kaj vidu kio okazas tie.

873
01:13:03,590 --> 01:13:05,350
Malzomi vere rapida.

874
01:13:05,350 --> 01:13:14,230
Mi volas certigi ke ne iras al la rando de la ekrano tiel ni povas vidi ĉion.

875
01:13:14,230 --> 01:13:18,760
Tiri ke en iom. Alright.

876
01:13:18,760 --> 01:13:35,030
Rulumu malsupren, kaj la problemo estas ĝuste ĉi tie.

877
01:13:35,030 --> 01:13:40,120
Kio okazas se ni preni malsupren kaj nia nuna nodo estas jam nula,

878
01:13:40,120 --> 01:13:44,010
nia patro nodo estas nula, do se ni rigardas supren al la plejsupro, ĉi tie -

879
01:13:44,010 --> 01:13:47,340
se ĉi tiu dum buklo neniam reale ekzekutas

880
01:13:47,340 --> 01:13:52,330
cxar nia aktuala valoro estas nula - nia radiko estas nula do nuna estas nula -

881
01:13:52,330 --> 01:13:57,810
tiam nia patro neniam prenas starigis al nuna aŭ validan valoron,

882
01:13:57,810 --> 01:14:00,580
tiel, patro ankaŭ estos nula.

883
01:14:00,580 --> 01:14:03,700
Ni devas memori por kontroli por ke

884
01:14:03,700 --> 01:14:08,750
por kiam ni atingos cxi tie, kaj ni komencu alirante la gepatroj valoro.

885
01:14:08,750 --> 01:14:13,190
Do, kio okazas? Nu, se la patro estas nula -

886
01:14:13,190 --> 01:14:17,990
if (patro == NULL) - tiam ni scias ke

887
01:14:17,990 --> 01:14:19,530
tie ne devas esti io en la arbo.

888
01:14:19,530 --> 01:14:22,030
Ni devas klopodi por enigi ĝin en la radiko.

889
01:14:22,030 --> 01:14:32,570
Ni povas fari tion per nur opcio la radiko egala al la nova nodo.

890
01:14:32,570 --> 01:14:40,010
Tiam je ĉi tiu punkto, ni ne vere volas iri tra tiuj aliaj aĵoj.

891
01:14:40,010 --> 01:14:44,780
Anstataŭe, ĉi tie, ni povas fari ĉu alia-se-alian,

892
01:14:44,780 --> 01:14:47,610
aŭ ni povus kombini ĉio ĉi tien en alia,

893
01:14:47,610 --> 01:14:56,300
sed tie ni simple uzu pli kaj fari ĝin tiel.

894
01:14:56,300 --> 01:14:59,030
Nun, ni tuj provi certigi ke nia patro ne estas nula

895
01:14:59,030 --> 01:15:02,160
antaux tiam efektive provas aliri liaj kampoj.

896
01:15:02,160 --> 01:15:05,330
Tio helpos nin eviti la segmentación kulpo.

897
01:15:05,330 --> 01:15:14,740
Do, ni forlasis, malzomi, kompili, kuri.

898
01:15:14,740 --> 01:15:18,130
>> Neniu eraroj, sed ni ankoraŭ havas faskon da memoro fugoj

899
01:15:18,130 --> 01:15:20,650
ĉar ni ne liberigi iun el niaj nodoj.

900
01:15:20,650 --> 01:15:24,350
Sed, se ni iros tien, kaj ni rigardu nian printaĵo,

901
01:15:24,350 --> 01:15:30,880
ni vidas ke, nu, aspektas kiel ĉiuj niaj enmetas estis revenantaj vera, kio estas bona.

902
01:15:30,880 --> 01:15:33,050
La enmetas estas ĉiuj veraj,

903
01:15:33,050 --> 01:15:36,670
kaj tiam la taŭga enhavas alvokoj estas ankaŭ vera.

904
01:15:36,670 --> 01:15:41,510
>> Bonan laboron! Ĝi aspektas kiel ni sukcese skribita insert.

905
01:15:41,510 --> 01:15:47,430
Tio estas ĉio ni havas por ĉi tiu semajno Problemo Ara Specification.

906
01:15:47,430 --> 01:15:51,720
Unu amuza defio pensi estas kiel vi reale iros

907
01:15:51,720 --> 01:15:55,340
kaj libera ĉiuj nodoj en ĉi tiu arbo.

908
01:15:55,340 --> 01:15:58,830
Ni povas fari ĝin nombro de malsamaj manieroj,

909
01:15:58,830 --> 01:16:01,930
sed mi lasos tion al vi sperti,

910
01:16:01,930 --> 01:16:06,080
kaj kiel amuza defio, provu kaj certiĝu ke vi povas certigi

911
01:16:06,080 --> 01:16:09,490
ke ĉi Valgrind raporto revenas sen eraroj kaj neniu filtras.

912
01:16:09,490 --> 01:16:12,880
>> Bonŝancon en ĉi tiu semajno Huffman kodigo problemo aro,

913
01:16:12,880 --> 01:16:14,380
kaj ni vidos vin venontsemajne!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]