1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [7 dalis] [mažiau patogūs]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvardo universiteto]

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

4
00:00:07,000 --> 00:00:09,080
>> Sveiki atvykę į 7 skirsnyje.

5
00:00:09,080 --> 00:00:11,330
Dėl uragano Sandy,

6
00:00:11,330 --> 00:00:13,440
vietoj normalų skyrių šią savaitę,

7
00:00:13,440 --> 00:00:17,650
ką mes darome, tai walk-through, per klausimų skyriuje.

8
00:00:17,650 --> 00:00:22,830
Aš ruošiuosi po Nustatykite 6 specifikacija kartu su problema,

9
00:00:22,830 --> 00:00:25,650
ir išgyvena visus klausimus

10
00:00:25,650 --> 00:00:27,770
Klausimų skyriuje skyrius.

11
00:00:27,770 --> 00:00:30,940
Jei yra kokių nors klausimų,

12
00:00:30,940 --> 00:00:32,960
rašykite juos CS50 aptarti.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Pradėkime.

14
00:00:35,480 --> 00:00:40,780
Dabar aš žiūri į problemą, specifikaciją 3 puslapiuose.

15
00:00:40,780 --> 00:00:44,110
Mes ketiname pirmą kartą pradėti kalbėti apie dvejetainiai medžiai

16
00:00:44,110 --> 00:00:47,850
nes pastarieji daug EEE šią savaitę problemą, -

17
00:00:47,850 --> 00:00:49,950
Huffman medis kodavimas.

18
00:00:49,950 --> 00:00:55,000
Vienas iš pirmųjų duomenų struktūrų, mes kalbėjome apie CS50 masyvas.

19
00:00:55,000 --> 00:01:00,170
Atminkite, kad masyvas yra elementų seka -

20
00:01:00,170 --> 00:01:04,019
visų saugomi to paties tipo - visai šalia vienas kito atmintyje.

21
00:01:04,019 --> 00:01:14,420
Jeigu aš turiu integer masyvas, kad galiu piešti naudojant šį dėžės numeriai sveikieji skaičiai stilių -

22
00:01:14,420 --> 00:01:20,290
Tarkime, turiu 5 į pirmą langelį, aš turiu 7 antrojoje,

23
00:01:20,290 --> 00:01:27,760
tada aš turiu 8, 10 ir 20 galutiniame lange.

24
00:01:27,760 --> 00:01:33,000
Atminkite, kad du tikrai gerų dalykų apie šio masyvo

25
00:01:33,000 --> 00:01:38,800
yra tai, kad mes turime šį pastovaus laiko prieigą prie konkretaus elemento

26
00:01:38,800 --> 00:01:40,500
 masyve, jei mes žinome savo indeksą.

27
00:01:40,500 --> 00:01:44,670
Pavyzdžiui, jei aš noriu patraukti trečiąjį elementą masyvo -

28
00:01:44,670 --> 00:01:47,870
indeksuoti 2 naudojant nulinės indeksavimo sistemą -

29
00:01:47,870 --> 00:01:52,220
Aš tiesiog tiesiog turite padaryti paprasto matematinio skaičiavimo,

30
00:01:52,220 --> 00:01:56,170
hop to masyve pozicijos,

31
00:01:56,170 --> 00:01:57,840
ištraukite 8, kuri yra saugoma,

32
00:01:57,840 --> 00:01:59,260
ir aš tikiu, gera eiti.

33
00:01:59,260 --> 00:02:03,350
>> Vienas iš blogų dalykų apie šio masyvo, kad mes kalbėjome apie

34
00:02:03,350 --> 00:02:05,010
kai aptarėme, susijusius sąrašus -

35
00:02:05,010 --> 00:02:09,120
yra tai, kad, jei noriu įterpti elementą į šio masyvo,

36
00:02:09,120 --> 00:02:11,090
Aš ruošiuosi daryti, kai perkeliant aplink.

37
00:02:11,090 --> 00:02:12,940
Pavyzdžiui, šis masyvas čia

38
00:02:12,940 --> 00:02:16,850
rūšiuotas tvarka yra rūšiuojami didėjimo tvarka

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

40
00:02:19,440 --> 00:02:23,100
bet jei aš noriu įterpti skaičių "9", į šio masyvo,

41
00:02:23,100 --> 00:02:27,460
Aš ruošiuosi pereiti tam tikrus elementus, siekiant padaryti vietos.

42
00:02:27,460 --> 00:02:30,440
Mes galime padaryti, tai iš čia.

43
00:02:30,440 --> 00:02:35,650
Aš ruošiuosi perkelti 5, 7, tada 8;

44
00:02:35,650 --> 00:02:38,720
sukurti spragą, kur aš galiu įdėti į 9,

45
00:02:38,720 --> 00:02:45,910
, o po to 10 ir 20 gali eiti į dešinę iš 9.

46
00:02:45,910 --> 00:02:49,450
Tai tipo skausmas, nes blogiausiam scenarijui -

47
00:02:49,450 --> 00:02:54,350
kai mes įterpti arba pradžioje arba pabaigoje

48
00:02:54,350 --> 00:02:56,040
masyvą, priklausomai nuo to kaip mes perkeliant

49
00:02:56,040 --> 00:02:58,850
mes gali baigtis pereiti visus elementus,

50
00:02:58,850 --> 00:03:00,750
, kad mes šiuo metu saugoti masyve.

51
00:03:00,750 --> 00:03:03,810
>> Taigi, kas buvo būdas išspręsti šią problemą?

52
00:03:03,810 --> 00:03:09,260
Aplink tokiu būdu buvo eiti į Susietos sąrašą metodas, kai

53
00:03:09,260 --> 00:03:19,820
, o ne saugoti elementus, 5, 7, 8, 10 ir 20 Visi šalia vienas kito atmintyje

54
00:03:19,820 --> 00:03:25,630
tai, ką mes, o ne darė, buvo laikyti juos natūra, kur mes norėjome juos laikyti

55
00:03:25,630 --> 00:03:32,470
šių susijusių sąrašą mazgų, aš parengiant čia, ad hoc pobūdžio.

56
00:03:32,470 --> 00:03:42,060
Ir tada mes prijungti juos kartu naudojant šiuos Çstaigose.

57
00:03:42,060 --> 00:03:44,370
Galiu turėti žymeklį nuo 5 iki 7,

58
00:03:44,370 --> 00:03:46,420
rodyklė 7 8

59
00:03:46,420 --> 00:03:47,770
rodyklė nuo 8 iki 10,

60
00:03:47,770 --> 00:03:51,220
ir, galiausiai, rodyklė iš 10 į 20,

61
00:03:51,220 --> 00:03:54,880
ir tada null tuo 20 rodyklė, nurodant, kad nėra nieko kairėje.

62
00:03:54,880 --> 00:03:59,690
Kompromisą, kad mes turime čia

63
00:03:59,690 --> 00:04:05,360
tai, kad dabar, jei norime įterpti skaičių "9" į mūsų rūšiuotų sąrašą,

64
00:04:05,360 --> 00:04:08,270
visi mes turime padaryti, tai sukurti naują mazgas su 9,

65
00:04:08,270 --> 00:04:12,290
pervesti jį atkreipti į tinkamą vietą,

66
00:04:12,290 --> 00:04:20,630
ir tada vėl laidas 8 atkreipti į 9.

67
00:04:20,630 --> 00:04:25,660
Kad gana greitai, jei mes žinome tiksliai, kur mes norime įterpti 9.

68
00:04:25,660 --> 00:04:32,610
Tačiau kompromisą mainais už tai, kad mes dabar prarado dėl nuolatinės laiko susipažinti

69
00:04:32,610 --> 00:04:36,230
bet konkretaus elemento mūsų duomenų struktūros.

70
00:04:36,230 --> 00:04:40,950
Pavyzdžiui, jei aš noriu rasti Ketvirtasis elementas šioje susietą sąrašą,

71
00:04:40,950 --> 00:04:43,510
Aš ruošiuosi pradėti pačioje pradžioje sąrašo

72
00:04:43,510 --> 00:04:48,930
ir dirbti savo kelią per skaičiavimo mazgas mazgas, kol rasiu ketvirta.

73
00:04:48,930 --> 00:04:55,870
>> , Siekiant gauti geresnį našumą, nei susietos sąrašą prieigos -

74
00:04:55,870 --> 00:04:59,360
, bet taip pat išlaikyti kai į naudą, kad mes turėjome

75
00:04:59,360 --> 00:05:01,800
įterpimo laiko iš susietą sąrašą -

76
00:05:01,800 --> 00:05:05,750
dvejetainis medis, reikia naudoti šiek tiek daugiau atminties.

77
00:05:05,750 --> 00:05:11,460
Visų pirma, o ne tik vieną žymeklį, dvejetainis medis mazgas -

78
00:05:11,460 --> 00:05:13,350
kaip prijungto sąrašą mazgas -

79
00:05:13,350 --> 00:05:16,950
mes ketiname pridėti antrą žymiklį į dvejetainis medis mazgas.

80
00:05:16,950 --> 00:05:19,950
, O ne tik vieną žymiklį į kito elemento,

81
00:05:19,950 --> 00:05:24,420
mes ketiname turėti žymeklį į kairę vaiko ir teisingu vaiko.

82
00:05:24,420 --> 00:05:26,560
>> Leiskite atkreipti paveikslėlį, kurį norite pamatyti, ką tai iš tikrųjų atrodo.

83
00:05:26,560 --> 00:05:31,350
Vėlgi, aš ruošiuosi naudoti šiuos langelius ir rodyklės.

84
00:05:31,350 --> 00:05:37,150
Dvejetainis medis mazgas pradėsite tik paprastas lange.

85
00:05:37,150 --> 00:05:40,940
Jis ketina turėti vertės erdvę,

86
00:05:40,940 --> 00:05:47,280
ir tada jis taip pat ketina turėti erdvę kairėje vaiko ir dešiniojo vaiko.

87
00:05:47,280 --> 00:05:49,280
Aš ruošiuosi čia juos ženklinti.

88
00:05:49,280 --> 00:05:57,560
Mes ketiname kairįjį vaiką, ir tada mes ketiname turėti teisę vaiką.

89
00:05:57,560 --> 00:05:59,920
Yra daug įvairių būdų, kaip tai daryti.

90
00:05:59,920 --> 00:06:02,050
Kartais erdvės ir patogumo,

91
00:06:02,050 --> 00:06:06,460
Aš iš tikrųjų padaryti tai, kaip aš darau čia apačioje

92
00:06:06,460 --> 00:06:10,910
kur aš ruošiuosi turėti vertę viršuje

93
00:06:10,910 --> 00:06:14,060
ir tada vaikas apačioje, dešinėje pusėje,

94
00:06:14,060 --> 00:06:16,060
ir kairėje vaikas kairiajame apatiniame.

95
00:06:16,060 --> 00:06:20,250
Grįžtant prie šio viršų diagrama,

96
00:06:20,250 --> 00:06:22,560
mes turime vertę pačiame viršuje,

97
00:06:22,560 --> 00:06:25,560
tada mes turime kairėje ir vaikų rodyklė, ir tada mes turime vaikų dešiniuoju pelės žymeklį.

98
00:06:25,560 --> 00:06:30,110
>> Problemą, specifikaciją,

99
00:06:30,110 --> 00:06:33,110
mes kalbame apie piešimo mazgas, turi vertę, 7,

100
00:06:33,110 --> 00:06:39,750
ir tada kairėje vaikas rodyklę, kad yra niekinis, ir dešiniuoju pelės vaikas rodyklė yra tuščias.

101
00:06:39,750 --> 00:06:46,040
Mes galime parašyti kapitalo NULL erdvėje

102
00:06:46,040 --> 00:06:51,610
tiek kairėje, tiek vaikas ir teisę vaikui ar mes galime padaryti šį įstrižainės velniop

103
00:06:51,610 --> 00:06:53,750
per kiekvieną langelius, nurodyti, kad tai niekinis.

104
00:06:53,750 --> 00:06:57,560
Aš ruošiuosi padaryti, kad tik todėl, kad paprasčiau.

105
00:06:57,560 --> 00:07:03,700
, Ką jūs matote čia yra du būdai, kaip diagramų labai paprastas dvejetainis medis mazgas

106
00:07:03,700 --> 00:07:07,960
kur mes turime vertę 7 ir tuščių vaikų Pointeriai.

107
00:07:07,960 --> 00:07:15,220
>> Antroji dalis mūsų specifikacijos diskusijas apie tai, kaip, susijusius sąrašus -

108
00:07:15,220 --> 00:07:18,270
Nepamirškite, kad mes tik turėjo eiti į labai pirmąjį elementą į sąrašą

109
00:07:18,270 --> 00:07:20,270
prisiminti visą sąrašą -

110
00:07:20,270 --> 00:07:26,140
ir taip pat, dvejetainis medis, mes tik eiti į vienos rodyklė į medžio

111
00:07:26,140 --> 00:07:31,120
siekiant išlaikyti kontroliuoti visą duomenų struktūros.

112
00:07:31,120 --> 00:07:36,150
Šis specialus elementas iš medžio vadinama šakninis mazgas iš medžio.

113
00:07:36,150 --> 00:07:43,360
Pavyzdžiui, jei tai vienas mazgas - 7 vertę šis mazgas, kuriame

114
00:07:43,360 --> 00:07:45,500
null kairėje ir dešinėje vaikas rodykles

115
00:07:45,500 --> 00:07:47,360
buvo tik mūsų medžio vertė,

116
00:07:47,360 --> 00:07:50,390
tuomet tai būtų mūsų šakninis mazgas.

117
00:07:50,390 --> 00:07:52,240
Tai pati pradžia mūsų medžio.

118
00:07:52,240 --> 00:07:58,530
Mes galime matyti, tai šiek tiek aiškiau, kai mes pradėti pridėti daugiau mazgų mūsų medžio.

119
00:07:58,530 --> 00:08:01,510
Leiskite man atsigriebti naują puslapį.

120
00:08:01,510 --> 00:08:05,000
>> Dabar mes ketiname atkreipti medį, kuris turi 7 šaknų,

121
00:08:05,000 --> 00:08:10,920
ir 3 viduje iš kairės vaikui, ir 9 viduje teisinga vaiko.

122
00:08:10,920 --> 00:08:13,500
Vėlgi, tai yra gana paprasta.

123
00:08:13,500 --> 00:08:26,510
Mes turime 7, parengti už 3 mazgas, mazgas 9

124
00:08:26,510 --> 00:08:32,150
ir aš ruošiuosi nustatyti kairės vaikų žymeklį 7, kad rodytų į mazgą, kuriame yra 3,

125
00:08:32,150 --> 00:08:37,850
ir dešiniuoju pelės vaikas mazgo mazge, kuriame 9 7, kuriame rodyklė.

126
00:08:37,850 --> 00:08:42,419
Dabar, nes 3 ir 9 neturite jokių vaikų,

127
00:08:42,419 --> 00:08:48,500
mes ketiname nustatyti savo vaiko rodykles yra niekinis.

128
00:08:48,500 --> 00:08:56,060
Čia, mūsų medžio šaknis atitinka mazgas, kuriame yra 7.

129
00:08:56,060 --> 00:09:02,440
Galite matyti, kad, jei viskas, ką turime, yra rodyklė į tą šakninis mazgas,

130
00:09:02,440 --> 00:09:07,330
tada mes galime eiti per mūsų medžio ir naudotis ir vaikų mazgai -

131
00:09:07,330 --> 00:09:10,630
tiek 3 ir 9.

132
00:09:10,630 --> 00:09:14,820
Nereikia išlaikyti patarimų į kiekvieną mazgą ant medžio.

133
00:09:14,820 --> 00:09:22,080
Alright. Dabar mes ketiname pridėti dar vieną mazgą šioje diagramoje.

134
00:09:22,080 --> 00:09:25,370
Mes ketiname pridėti mazgas, kuriame yra 6,

135
00:09:25,370 --> 00:09:34,140
ir mes ketiname pridėti šį elementą kaip teisinga vaiko mazgas, kuriame yra 3.

136
00:09:34,140 --> 00:09:41,850
Norėdami tai padaryti, aš ruošiuosi ištrinti, kad null žymeklį 3-mazgas

137
00:09:41,850 --> 00:09:47,750
ir vielos, kad rodytų į mazgą, kuriame yra 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Šiuo metu, geriau patys eikime per šiek tiek terminologijos.

139
00:09:53,800 --> 00:09:58,230
Norėdami pradėti, tos priežasties, kad tai ir yra dvejetainis medis, visų pirma

140
00:09:58,230 --> 00:10:00,460
yra tai, kad dviejų vaikų patarimų.

141
00:10:00,460 --> 00:10:06,020
Yra ir kitų rūšių medžių, kurie turi daugiau vaikų patarimų.

142
00:10:06,020 --> 00:10:10,930
Visų pirma, tu "pabandyti" problemą, 5.

143
00:10:10,930 --> 00:10:19,310
Jūs pastebėsite, kad toje pabandyti, jums turėjo 27 skirtingų patarimų skirtingiems vaikams

144
00:10:19,310 --> 00:10:22,410
po vieną kiekvienai iš 26 anglų abėcėlės raidėmis,

145
00:10:22,410 --> 00:10:25,410
ir tada į kabutes 27 -

146
00:10:25,410 --> 00:10:28,900
taip, kad panašus į medžio tipo.

147
00:10:28,900 --> 00:10:34,070
Bet čia, nes tai dvejetainis, mes tik turime du vaikų patarimų.

148
00:10:34,070 --> 00:10:37,880
>> Be to, šio šakninis mazgas, kad mes kalbėjome apie,

149
00:10:37,880 --> 00:10:41,470
mes taip pat mesti aplink šį terminą "vaiko".

150
00:10:41,470 --> 00:10:44,470
Ką tai reiškia, vienas mazgas būti kito mazgo vaikas?

151
00:10:44,470 --> 00:10:54,060
Tai tiesiog reiškia, kad vaikas mazgas yra kitos mazgo vaikas

152
00:10:54,060 --> 00:10:58,760
jei tas kitas mazgas turi vieną iš savo vaikų rodykles, kad rodytų į tą mazgą.

153
00:10:58,760 --> 00:11:01,230
Norėdami įdėti šią nuorodą į daugiau konkrečiais terminais,

154
00:11:01,230 --> 00:11:11,170
jei atkreipė dėmesį į 3 dalis vienu iš vaikų rodykles 7, tada 3 yra 7 vaikas.

155
00:11:11,170 --> 00:11:14,510
Jeigu mes buvo išsiaiškinti, kas 7 vaikai -

156
00:11:14,510 --> 00:11:18,510
gerai, mes matome, kad 7 turi rodyklę į 3 ir rodyklę iki 9,

157
00:11:18,510 --> 00:11:22,190
taip 9 ir 3 yra 7 vaikai.

158
00:11:22,190 --> 00:11:26,650
Devyni neturi vaikų, nes jos vaikas patarimų yra nulis,

159
00:11:26,650 --> 00:11:30,940
ir 3 turi tik vieną vaiką, 6.

160
00:11:30,940 --> 00:11:37,430
Šeši taip pat neturi vaikų, nes abi jos rodykles null, kuriuos mes atkreipti dabar.

161
00:11:37,430 --> 00:11:45,010
>> Be to, mes taip pat kalbame apie tam tikro mazgo tėvų,

162
00:11:45,010 --> 00:11:51,100
ir tai yra, kaip jūs tikitės, šis vaikas aprašymo reverse.

163
00:11:51,100 --> 00:11:58,620
Kiekvienas mazgas turi tik vieną iš tėvų - vietoj dviejų, kaip galite tikėtis su žmonėmis.

164
00:11:58,620 --> 00:12:03,390
Pavyzdžiui, 3 tėvų yra 7.

165
00:12:03,390 --> 00:12:10,800
9 iš tėvų taip pat 7 ir 6 tėvų yra 3. Ne per daug į jį.

166
00:12:10,800 --> 00:12:15,720
Mes taip pat turime sąlygas, kad kalbėti apie senelių ir vaikaičių,

167
00:12:15,720 --> 00:12:18,210
ir apskritai mes kalbame apie protėvių

168
00:12:18,210 --> 00:12:20,960
ir palikuonys tam tikro mazgo.

169
00:12:20,960 --> 00:12:25,710
Mazgas protėvis - arba protėviai, o mazgas -

170
00:12:25,710 --> 00:12:32,730
visų mazgų, kurie laukia kelyje nuo šaknų Šis mazgas.

171
00:12:32,730 --> 00:12:36,640
Pavyzdžiui, jei aš žiūriu mazgas 6,

172
00:12:36,640 --> 00:12:46,430
tada protėviai bus tiek 3 ir 7.

173
00:12:46,430 --> 00:12:55,310
9 protėviai, pavyzdžiui, - jei aš žiūriu mazgas 9

174
00:12:55,310 --> 00:12:59,990
9 protėvis yra tik 7.

175
00:12:59,990 --> 00:13:01,940
Ir palikuonys yra lygiai atvirkščiai.

176
00:13:01,940 --> 00:13:05,430
Jei aš noriu pažvelgti iš 7 palikuonių,

177
00:13:05,430 --> 00:13:11,020
tada aš turiu pažvelgti visi po juo mazgų.

178
00:13:11,020 --> 00:13:16,950
Taigi, turiu 3, 9, ir 6 bet kaip palikuonių 7.

179
00:13:16,950 --> 00:13:24,170
>> Galutinis terminas, kad mes kalbame apie tai sąvoka yra broliai ir seserys.

180
00:13:24,170 --> 00:13:27,980
Broliai ir seserys - kartu dėl šių šeimos sąlygų rūšies -

181
00:13:27,980 --> 00:13:33,150
yra mazgai, kurie yra tame pačiame lygyje medyje.

182
00:13:33,150 --> 00:13:42,230
Taigi, 3 ir 9 yra broliai ir seserys, nes jie yra tame pačiame lygyje medyje.

183
00:13:42,230 --> 00:13:46,190
Jie abu turi tą pačią tėvų, 7.

184
00:13:46,190 --> 00:13:51,400
6 neturi brolių ir seserų, nes 9 neturi vaikų.

185
00:13:51,400 --> 00:13:55,540
Ir 7 broliai ir seserys neturi, nes tai mūsų medžio šaknis,

186
00:13:55,540 --> 00:13:59,010
ir ten tik 1 root.

187
00:13:59,010 --> 00:14:02,260
For 7 turi brolių ir seserų, ten turi būti virš 7 mazgas.

188
00:14:02,260 --> 00:14:07,480
Turėtų būti tėvų 7, 7 byla nebebūtų iš medžio šaknis.

189
00:14:07,480 --> 00:14:10,480
Tada, kad naujoji patronuojanti įmonė yra 7, tai taip pat turi turėti vaiką,

190
00:14:10,480 --> 00:14:16,480
ir kad vaikas tada būtų 7 broliai ir seserys.

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

192
00:14:21,040 --> 00:14:24,930
Kai mes pradėjome mūsų diskusiją dvejetainiai medžiai,

193
00:14:24,930 --> 00:14:28,790
mes kalbėjome apie tai, kaip mes ketiname juos naudoti siekiant

194
00:14:28,790 --> 00:14:32,800
įgyti pranašumą nagrinėti abu masyvai ir susietų sąrašus.

195
00:14:32,800 --> 00:14:37,220
Ir tai, kaip mes ketiname daryti, kad su šia užsakymo turto.

196
00:14:37,220 --> 00:14:41,080
Mes sakome, kad yra užsakytas, dvejetainis medis pagal specifikacijos

197
00:14:41,080 --> 00:14:45,740
jei kiekvieno mūsų medžio mazgas, visų savo palikuonių kairėje -

198
00:14:45,740 --> 00:14:48,670
kairėje vaikas ir visa kairiojo vaiko palikuonys -

199
00:14:48,670 --> 00:14:54,510
turi mažiau vertybes, ir visus iš dešinėje pusėje mazgų -

200
00:14:54,510 --> 00:14:57,770
teisę vaikui ir visų teisių vaiko palikuonys -

201
00:14:57,770 --> 00:15:02,800
mazgų didesnis nei dabartinės mazgo vertės, kad mes ieškome.

202
00:15:02,800 --> 00:15:07,850
Tiesiog paprastumo, mes ketiname daryti prielaidą, kad nėra dublikato mazgai mūsų medžio.

203
00:15:07,850 --> 00:15:11,180
Pavyzdžiui, šio medžio mes neketiname nagrinėti bylą

204
00:15:11,180 --> 00:15:13,680
kur mes turime vertę 7 šaknų

205
00:15:13,680 --> 00:15:16,720
 ir tada mes taip pat turi vertę 7 kitur į medį.

206
00:15:16,720 --> 00:15:24,390
Šiuo atveju, jūs pastebėsite, kad šis medis yra iš tikrųjų užsakė.

207
00:15:24,390 --> 00:15:26,510
Mes turime 7 vertę ne šaknis.

208
00:15:26,510 --> 00:15:29,720
Viskas į kairę nuo 7 -

209
00:15:29,720 --> 00:15:35,310
jei atšaukti visų šių mažai ženklų čia -

210
00:15:35,310 --> 00:15:40,450
viskas į kairę nuo 7 - 3 ir 6 -

211
00:15:40,450 --> 00:15:49,410
šios vertybės yra tiek mažiau nei 7, ir viskas į dešinę - kuris yra tik tai 9 -

212
00:15:49,410 --> 00:15:53,450
yra didesnis kaip 7.

213
00:15:53,450 --> 00:15:58,650
>> Tai ne tik užsisakyti medis, kurių sudėtyje yra šių vertybes,

214
00:15:58,650 --> 00:16:03,120
tačiau leiskite atkreipti keli iš jų.

215
00:16:03,120 --> 00:16:05,030
Yra iš tikrųjų visa krūva būdų, kad mes galime tai padaryti.

216
00:16:05,030 --> 00:16:09,380
Aš ruošiuosi naudoti stenografistų tik išlaikyti viskas paprasta, kur -

217
00:16:09,380 --> 00:16:11,520
o ne visa dėžės ir strėlės -

218
00:16:11,520 --> 00:16:14,220
Aš tik ketina padaryti numerius ir pridėti rodykles juos siejančios.

219
00:16:14,220 --> 00:16:22,920
Norėdami pradėti, mes tiesiog parašyti savo medį, kur mes turėjome 7 ir tada 3,

220
00:16:22,920 --> 00:16:25,590
ir tada 3 atkreipė į dešinę į 6,

221
00:16:25,590 --> 00:16:30,890
ir 7 turėjo teisę vaiką, kuris buvo 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Kaip dar galima, kad galėtume rašyti šį medį?

223
00:16:33,860 --> 00:16:38,800
Vietoj to, kad 3 yra kairėje vaikas 7

224
00:16:38,800 --> 00:16:41,360
mes taip pat gali turėti 6 yra kairėje vaikas 7

225
00:16:41,360 --> 00:16:44,470
ir tada 3 kairėje vaikas iš 6.

226
00:16:44,470 --> 00:16:48,520
, Kad atrodytų kaip šio medžio čia, kur aš turiu 7,

227
00:16:48,520 --> 00:16:57,860
tada 6, tada 3, ir dešinėje 9.

228
00:16:57,860 --> 00:17:01,490
Mes taip pat neturi turėti 7, kaip mūsų šakninis mazgas.

229
00:17:01,490 --> 00:17:03,860
Mes taip pat gali turėti 6 mūsų šakninis mazgas.

230
00:17:03,860 --> 00:17:06,470
Ką tai atrodo?

231
00:17:06,470 --> 00:17:09,230
Jei mes ketiname išlaikyti tvarkingą turtą,

232
00:17:09,230 --> 00:17:12,970
viskas 6 kairėje turi būti mažiau, nei ji.

233
00:17:12,970 --> 00:17:16,540
Yra tik viena galimybė, ir tai 3.

234
00:17:16,540 --> 00:17:19,869
Bet tada teisinga vaikui nuo 6, turime dvi galimybes.

235
00:17:19,869 --> 00:17:25,380
Pirma, mes galime turėti 7 ir tada 9,

236
00:17:25,380 --> 00:17:28,850
ar mes galime padaryti tai, kaip aš apie padaryti čia -

237
00:17:28,850 --> 00:17:34,790
, kur mes turime 9 dešinėje vaiką iš 6

238
00:17:34,790 --> 00:17:39,050
ir tada kairėje vaiku 9 7.

239
00:17:39,050 --> 00:17:44,240
>> Dabar, 7 ir 6 yra ne tik galimos reikšmės šaknų.

240
00:17:44,240 --> 00:17:50,200
Mes taip pat gali turėti 3 ne šaknis.

241
00:17:50,200 --> 00:17:52,240
Kas atsitiks, jei 3 yra ne šaknis?

242
00:17:52,240 --> 00:17:54,390
Čia, ko gauti šiek tiek įdomus.

243
00:17:54,390 --> 00:17:58,440
Trys neturi jokių vertybes, kurios yra mažiau, nei ji,

244
00:17:58,440 --> 00:18:02,070
kad visa kairioji pusė nuo medžio yra tik ketina, yra niekinis.

245
00:18:02,070 --> 00:18:03,230
Ten nebus nieko ten.

246
00:18:03,230 --> 00:18:07,220
Į dešinę, galėtume išvardyti dalykus, didėjančia tvarka.

247
00:18:07,220 --> 00:18:15,530
Galėtume turėti 3, tada 6, tada 7, tada 9.

248
00:18:15,530 --> 00:18:26,710
Arba mes galime padaryti 3, tada 6, tada 9, tada 7.

249
00:18:26,710 --> 00:18:35,020
Arba mes galime padaryti 3, tada 7, tada 6, tada 9.

250
00:18:35,020 --> 00:18:40,950
Arba, 3, 7 - iš tikrųjų nėra, mes negali padaryti 7 daugiau.

251
00:18:40,950 --> 00:18:43,330
Tai mūsų vienas dalykas ten.

252
00:18:43,330 --> 00:18:54,710
Mes galime padaryti, 9, ir tada iš 9 mes galime padaryti 6 ir tada 7.

253
00:18:54,710 --> 00:19:06,980
Arba mes galime padaryti 3, tada 9, tada 7 ir tada 6.

254
00:19:06,980 --> 00:19:12,490
>> Vienas dalykas, kad atkreipti jūsų dėmesį į čia

255
00:19:12,490 --> 00:19:14,510
kad šie medžiai yra šiek tiek keistai atrodantį.

256
00:19:14,510 --> 00:19:17,840
Visų pirma, jei pažvelgsime į 4 medžių dešinėje pusėje -

257
00:19:17,840 --> 00:19:20,930
Aš ratas, čia -

258
00:19:20,930 --> 00:19:28,410
šie medžiai atrodo beveik lygiai taip pat kaip susietą sąrašą.

259
00:19:28,410 --> 00:19:32,670
Kiekvienas mazgas turi tik vieną vaiką,

260
00:19:32,670 --> 00:19:38,950
ir taip mes ne turite kokių nors šio medžio tipo struktūrą, kad mes matome, pavyzdžiui,

261
00:19:38,950 --> 00:19:44,720
 šį vieną Lone Tree per čia apačioje kairėje.

262
00:19:44,720 --> 00:19:52,490
Šie medžiai yra iš tikrųjų vadinamas peraugti dvejetainiai medžiai,

263
00:19:52,490 --> 00:19:54,170
ir mes kalbame apie tai daugiau į ateitį -

264
00:19:54,170 --> 00:19:56,730
ypač jei jūs einate imtis kitų informatikos kursus.

265
00:19:56,730 --> 00:19:59,670
Šie medžiai yra peraugti.

266
00:19:59,670 --> 00:20:03,780
Jie nėra labai naudinga, nes, tiesą sakant, ši struktūra pati savaime

267
00:20:03,780 --> 00:20:08,060
 peržvalgos kartus panašius į susietą sąrašą.

268
00:20:08,060 --> 00:20:13,050
Mes negalime gauti pasinaudoti papildomos atminties - šį papildomą žymeklį

269
00:20:13,050 --> 00:20:18,840
nes mūsų struktūra yra blogai šiuo būdu.

270
00:20:18,840 --> 00:20:24,700
O ne eiti ir atkreipti dėmesį į dvejetainius medžius, kurie 9 šaknų,

271
00:20:24,700 --> 00:20:27,220
kuris yra galutinis, kad mes turėtume,

272
00:20:27,220 --> 00:20:32,380
mes vietoj to, šiuo metu, norėčiau pakalbėti šiek tiek apie šį laikotarpį

273
00:20:32,380 --> 00:20:36,150
, kad mes naudojame, kai kalbame apie medžius, kuris yra vadinamas aukštis.

274
00:20:36,150 --> 00:20:45,460
>> Iš medžio aukštis yra atstumas nuo šaknų iki labiausiai tolimoje mazgai,

275
00:20:45,460 --> 00:20:48,370
arba, tiksliau, apynių, kad jūs turite padaryti, siekiant

276
00:20:48,370 --> 00:20:53,750
pradėti nuo šaknų ir tada galų gale labiausiai tolimoje medžio mazgo.

277
00:20:53,750 --> 00:20:57,330
Jei pažvelgsime į kai kuriuos iš šių medžių, kad mes sudarytas čia,

278
00:20:57,330 --> 00:21:07,870
matome, kad, jei mes šį medį viršutiniame kairiajame kampe, ir mes pradedame ne 3,

279
00:21:07,870 --> 00:21:14,510
tada mes turime padaryti 1 hop patekti į 6-2.-hop gauti iki 7,

280
00:21:14,510 --> 00:21:20,560
ir trečioji apynių gauti į 9.

281
00:21:20,560 --> 00:21:26,120
Taigi, šio medžio aukštis yra 3.

282
00:21:26,120 --> 00:21:30,640
Mes galime padaryti tą patį pratimą kitų medžių, išdėstytų šia žaliąja,

283
00:21:30,640 --> 00:21:40,100
ir matome, kad visų šių medžių aukštis yra taip pat iš tikrųjų 3.

284
00:21:40,100 --> 00:21:45,230
Štai kas leidžia jiems peraugti dalis

285
00:21:45,230 --> 00:21:53,750
kad jų aukštis yra tik mažiau nei vienas visą medžio mazgų skaičių.

286
00:21:53,750 --> 00:21:58,400
Jei pažvelgsime į šio medžio, kuris apibrauktas raudonai, kita vertus,

287
00:21:58,400 --> 00:22:03,920
matome, kad labiausiai toli lapų mazgai yra 6 ir 9 -

288
00:22:03,920 --> 00:22:06,940
lapai, kurie yra mazgai, kad neturiu vaikų.

289
00:22:06,940 --> 00:22:11,760
Taigi, norint gauti nuo šaknų mazgas arba į 6 arba 9,

290
00:22:11,760 --> 00:22:17,840
mes turime padaryti vieną hop gauti iki 7 ir tada antrasis apynių į gauti į 9,

291
00:22:17,840 --> 00:22:21,240
ir taip pat, tik antras iš 7-hop gauti į 6.

292
00:22:21,240 --> 00:22:29,080
Taigi, šio medžio aukštis virš čia yra tik 2.

293
00:22:29,080 --> 00:22:35,330
Jūs galite grįžti ir padaryti, kad visų kitų medžių, kad mes aptarta anksčiau

294
00:22:35,330 --> 00:22:37,380
pradedant su 7 ir 6,

295
00:22:37,480 --> 00:22:42,500
ir jūs pamatysite, kad visų minėtų medžių aukštis yra 2.

296
00:22:42,500 --> 00:22:46,320
>> Priežastis, mes kalbame apie nurodė dvejetainius medžius

297
00:22:46,320 --> 00:22:50,250
ir kodėl jie cool, nes jūs galite ieškoti per juos

298
00:22:50,250 --> 00:22:53,810
labai panašus būdas ieškoti per rūšiuotų masyvo.

299
00:22:53,810 --> 00:22:58,720
Tai yra, kai mes kalbame apie tai, kad geresnės peržvalgos laikas

300
00:22:58,720 --> 00:23:02,730
per paprastą susijęs sąrašą.

301
00:23:02,730 --> 00:23:05,010
Su susietą sąrašą, jei norite rasti tam tikrą elementą -

302
00:23:05,010 --> 00:23:07,470
jūs esate geriausias ketinate daryti kažkokią linijinio paieška

303
00:23:07,470 --> 00:23:10,920
kai jūs pradedate sąrašo pradžioje ir apynių vienas po kito -

304
00:23:10,920 --> 00:23:12,620
vienas mazgas vienam mazgui -

305
00:23:12,620 --> 00:23:16,060
per visą sąrašą, kol rasite bet jūs ieškote.

306
00:23:16,060 --> 00:23:19,440
Kadangi tuo atveju, jei turite dvejetainis medis, saugomas, šis gražus formatu,

307
00:23:19,440 --> 00:23:23,300
jūs iš tikrųjų galite gauti daugiau dvejetainis paieškos vyksta

308
00:23:23,300 --> 00:23:25,160
kur jūs skaldyk ir valdyk

309
00:23:25,160 --> 00:23:29,490
ir paieškos per atitinkamą pusmetį kiekviename žingsnyje medžio.

310
00:23:29,490 --> 00:23:32,840
Pažiūrėkime, kaip tai veikia.

311
00:23:32,840 --> 00:23:38,850
>> Jei mes turime - vėl grįžta į mūsų pradinės medžio -

312
00:23:38,850 --> 00:23:46,710
mes pradedame 7, mes turime 3 kairėje, 9 dešinėje,

313
00:23:46,710 --> 00:23:51,740
ir po 3 mes turime 6.

314
00:23:51,740 --> 00:24:01,880
Jei norime ieškoti šio medžio skaičiumi 6, mes norime pradėti ne šaknis.

315
00:24:01,880 --> 00:24:08,910
Mes norėtume palyginti vertę, mes ieškome, tarkim, 6,

316
00:24:08,910 --> 00:24:12,320
vertės saugomą mazgo, kad mes šiuo metu ieško, 7,

317
00:24:12,320 --> 00:24:21,200
rasti, kad 6 iš tiesų mažiau kaip 7, todėl mes norime judėti į kairę.

318
00:24:21,200 --> 00:24:25,530
Jei vertė iš 6 buvo didesnė už 7, mes, atvirkščiai, perkelta į dešinę.

319
00:24:25,530 --> 00:24:29,770
Nes mes žinome, kad dėl į mūsų užsakytą dvejetainis medis struktūrą

320
00:24:29,770 --> 00:24:33,910
vertės yra mažiau nei 7 ketinate būti saugomi 7 kairėje,

321
00:24:33,910 --> 00:24:40,520
nereikia net vargintis ieško per dešinėje pusėje medžio.

322
00:24:40,520 --> 00:24:43,780
, Kai mes einame į kairę ir dabar mes mazgas, kuriame yra 3,

323
00:24:43,780 --> 00:24:48,110
mes galime padaryti tą patį palyginimą, kur mes palyginti 3 ir 6.

324
00:24:48,110 --> 00:24:52,430
Ir mes manome, kad nors 6 - vertė mes ieškome - yra didesnis kaip 3,

325
00:24:52,430 --> 00:24:58,580
mes galime eiti į mazgo dešinėje pusėje, kurioje yra 3.

326
00:24:58,580 --> 00:25:02,670
Nėra jokios kairėje pusėje, kad galėtume pamiršti, kad.

327
00:25:02,670 --> 00:25:06,510
Bet mes žinome, kad tik todėl, kad mes ieškome į medį,

328
00:25:06,510 --> 00:25:08,660
ir mes galime pamatyti, kad medis neturi vaikų.

329
00:25:08,660 --> 00:25:13,640
>> Jis taip pat yra gana lengva prižiūrėti 6 iš šio medžio, jei mes darome patys, kaip žmonės,

330
00:25:13,640 --> 00:25:16,890
bet tegul šį procesą mechaniškai kaip kompiuteryje būtų padaryti

331
00:25:16,890 --> 00:25:18,620
tikrai suprasti algoritmą.

332
00:25:18,620 --> 00:25:26,200
Šiuo metu, mes dabar žiūri mazgas, kuriame yra 6,

333
00:25:26,200 --> 00:25:29,180
ir mes ieškome vertės 6,

334
00:25:29,180 --> 00:25:31,740
taip, iš tiesų, mes pastebėjome atitinkamą mazgą.

335
00:25:31,740 --> 00:25:35,070
Mes radome 6 vertę mūsų medžio, ir mes galime sustabdyti mūsų paieškos.

336
00:25:35,070 --> 00:25:37,330
Šiuo metu, priklausomai nuo to, kas vyksta,

337
00:25:37,330 --> 00:25:41,870
mes galime pasakyti, taip, mes vertę 6, jis egzistuoja mūsų medžio.

338
00:25:41,870 --> 00:25:47,640
Arba, jei mes planuojame įterpti mazgas ar ką nors, mes galime padaryti, kad šiame taške.

339
00:25:47,640 --> 00:25:53,010
>> Padarykime keletą peržvalgų tik pamatyti, kaip tai veikia.

340
00:25:53,010 --> 00:25:59,390
Pažvelkime, kas atsitinka, jei mes išbandyti ir ieškoti vertę 10.

341
00:25:59,390 --> 00:26:02,970
Jei mes ieškoti vertę 10, mes norėtume pradėti nuo šaknų.

342
00:26:02,970 --> 00:26:07,070
Mes norime pamatyti, kad 10 yra didesnė už 7, todėl mes norime judėti į dešinę.

343
00:26:07,070 --> 00:26:13,640
Mes norime patekti į 9 ir 10 9 palyginti ir pamatyti, kad 9 iš tiesų yra mažiau nei 10.

344
00:26:13,640 --> 00:26:16,210
Taigi dar kartą, mes norime bandyti judėti į dešinę.

345
00:26:16,210 --> 00:26:20,350
Tačiau šiuo metu, mes norime pastebėti, kad mes ne nulinis mazgas.

346
00:26:20,350 --> 00:26:23,080
Nieko ten. Nėra nieko, kur 10 turėtų būti.

347
00:26:23,080 --> 00:26:29,360
Tai vieta, kur mes galime pranešti neįvykdymas - kad iš tiesų į medį 10 ne.

348
00:26:29,360 --> 00:26:35,420
Ir, pagaliau, eikime per tuo atveju, kai mes bandome ieškoti 1 į medį.

349
00:26:35,420 --> 00:26:38,790
Tai panašu, kas atsitiks, jei mes žiūrime iki 10, išskyrus tuos atvejus, o ne eiti į dešinę,

350
00:26:38,790 --> 00:26:41,260
mes ketiname eiti į kairę.

351
00:26:41,260 --> 00:26:46,170
Mes pradedame nuo 7 ir matyti, kad 1 yra mažiau nei 7, todėl mes einame į kairę.

352
00:26:46,170 --> 00:26:51,750
Mes gauname į 3 ir pamatyti, kad 1 yra mažesnis nei 3, todėl mes dar kartą bandyti judėti į kairę.

353
00:26:51,750 --> 00:26:59,080
Šiuo metu mes turime null mazgas, todėl mes vėl gali pranešti apie gedimą.

354
00:26:59,080 --> 00:27:10,260
>> Jei jūs norite sužinoti daugiau apie dvejetainiai medžiai,

355
00:27:10,260 --> 00:27:14,420
yra visa krūva įdomus mažai problemų, kad jūs galite padaryti su jais.

356
00:27:14,420 --> 00:27:19,450
Siūlau praktikuojančių po vieną šių diagramų

357
00:27:19,450 --> 00:27:21,910
ir taip per visus skirtingus etapus,

358
00:27:21,910 --> 00:27:25,060
, nes tai bus super patogus

359
00:27:25,060 --> 00:27:27,480
ne tik, kai jūs darote Huffman Kodavimo problema rinkinys

360
00:27:27,480 --> 00:27:29,390
bet ateityje kursų

361
00:27:29,390 --> 00:27:32,220
tiesiog išmokti atkreipti dėmesį į šias duomenų struktūras ir apgalvoti problemų

362
00:27:32,220 --> 00:27:38,000
su rašiklį ir popieriaus arba, šiuo atveju, iPad ir plunksna.

363
00:27:38,000 --> 00:27:41,000
>> Nors šiuo metu, mes ketiname pereiti padaryti tam tikrą kodavimo praktika

364
00:27:41,000 --> 00:27:44,870
ir iš tikrųjų žaisti su šių dvejetainiai medžiai ir pamatyti.

365
00:27:44,870 --> 00:27:52,150
Aš ketina pereiti atgal į savo kompiuterį.

366
00:27:52,150 --> 00:27:58,480
Šio skyriaus, o ne naudojant CS50 Vykdyti arba CS50 Spaces ",

367
00:27:58,480 --> 00:28:01,500
Aš ruošiuosi naudoti prietaisą.

368
00:28:01,500 --> 00:28:04,950
>> Kartu su problemą, specifikaciją,

369
00:28:04,950 --> 00:28:07,740
Matau, kad aš turėjo atverti prietaisą,

370
00:28:07,740 --> 00:28:11,020
eikite į mano Dropbox aplanką, sukurti aplanką, pavadintą 7 skirsnis,

371
00:28:11,020 --> 00:28:15,730
ir tada sukurti failą pavadinta binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Čia mes einame. Aš turiu prietaisas jau atidarytas.

373
00:28:22,050 --> 00:28:25,910
Aš ruošiuosi atsigriebti terminalą.

374
00:28:25,910 --> 00:28:38,250
Aš ruošiuosi eiti į Dropbox aplanką, įsitikinkite, katalogą, pavadintą section7,

375
00:28:38,250 --> 00:28:42,230
ir pamatyti, tai visiškai tuščias.

376
00:28:42,230 --> 00:28:48,860
Dabar aš ruošiuosi atverti binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Here we go - tuščią failą.

378
00:28:51,750 --> 00:28:54,330
>> Grįžkime specifikacijos.

379
00:28:54,330 --> 00:28:59,850
Specifikacija prašo sukurti naujo tipo apibrėžimą

380
00:28:59,850 --> 00:29:03,080
dvejetainis medis mazgas, kuriame yra int vertybes -

381
00:29:03,080 --> 00:29:07,110
kaip ir vertybių, kad atkreipė mūsų diagramų prieš.

382
00:29:07,110 --> 00:29:11,740
Mes ketiname naudoti Standartiniai Typedef, kad mes padarėme čia

383
00:29:11,740 --> 00:29:14,420
kad jūs turėtumėte suvokti problemą, 5 -

384
00:29:14,420 --> 00:29:19,190
jei tu maišos lentelės būdas užkariauja Speller programos.

385
00:29:19,190 --> 00:29:22,540
Jūs taip pat turėtų pripažinti, kad iš skyriuje praėjusią savaitę

386
00:29:22,540 --> 00:29:23,890
kur mes kalbėjome apie tai, susijusius sąrašus.

387
00:29:23,890 --> 00:29:27,870
Mes turime tai Typedef struct mazgas,

388
00:29:27,870 --> 00:29:34,430
ir mes Atsižvelgiant į tai struct mazgas šį struct mazgo vardą iš anksto

389
00:29:34,430 --> 00:29:39,350
, kad galėtume tada kreiptis į jį, nes mes nori turėti struct mazgas patarimų

390
00:29:39,350 --> 00:29:45,740
kaip mūsų struct, bet mes tada apsuptas tai -

391
00:29:45,740 --> 00:29:47,700
arba, tiksliau, uždara - Typedef

392
00:29:47,700 --> 00:29:54,600
taip, kad vėliau kodą, galime nuorodą į šią struct kaip tik vietoj struct mazgo mazgas.

393
00:29:54,600 --> 00:30:03,120
>> Tai bus labai panašus į atskirai, susietą sąrašą apibrėžimą, kad mes matėme praėjusią savaitę.

394
00:30:03,120 --> 00:30:20,070
Norėdami tai padaryti, tegul tiesiog pradėti rašyti iš Standartiniai.

395
00:30:20,070 --> 00:30:23,840
Mes žinome, kad mes turime turėti skaitinę vertę,

396
00:30:23,840 --> 00:30:32,170
todėl mes įdėti int vertės, ir tada, o ne turėti vieną žymiklį į kito elemento -

397
00:30:32,170 --> 00:30:33,970
kaip mes padarėme su atskirai susietus sąrašus

398
00:30:33,970 --> 00:30:38,110
mes ketiname turėti kairę ir į dešinę vaikų patarimų.

399
00:30:38,110 --> 00:30:42,880
Tai gana paprasta, taip pat - Struct mazgas * kairėje vaikas;

400
00:30:42,880 --> 00:30:51,190
ir Struct mazgas * dešinė vaikas;. Cool.

401
00:30:51,190 --> 00:30:54,740
Tai atrodo gana gera pradžia.

402
00:30:54,740 --> 00:30:58,530
Grįžkime specifikacijos.

403
00:30:58,530 --> 00:31:05,030
>> Dabar mes turime paskelbti pasaulinį mazgas * kintamąjį medžio šaknis.

404
00:31:05,030 --> 00:31:10,590
Mes ketiname padaryti tai pasaulio, kaip mes pirmą rodyklę Susietos sąrašą taip pat pasaulio.

405
00:31:10,590 --> 00:31:12,690
Tai buvo taip, kad funkcijų, kad mes rašome

406
00:31:12,690 --> 00:31:16,180
mes neturime išlaikyti einančios aplink Ši šaknis -

407
00:31:16,180 --> 00:31:19,620
nors mes pamatysime, kad jei jūs norite parašyti šias funkcijas rekursyviai,

408
00:31:19,620 --> 00:31:22,830
jis gali būti geriau net perduoti jį aplink kaip į pirmąją vietą pasaulio

409
00:31:22,830 --> 00:31:28,090
ir vietoj to initialize lokaliai savo pagrindinę funkciją.

410
00:31:28,090 --> 00:31:31,960
Tačiau, mes tai padaryti visame pasaulyje pradėti.

411
00:31:31,960 --> 00:31:39,920
Vėlgi, mes duosiu keletą erdvių, ir aš einu paskelbti mazgas * šaknis.

412
00:31:39,920 --> 00:31:46,770
Tiesiog įsitikinkite, kad aš ne palikti šį niezainicjowanymi, aš nustatyti, kad jis lygus nulis.

413
00:31:46,770 --> 00:31:52,210
Dabar pagrindinė funkcija - mes rašyti tikrai greitai čia -

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
ir aš ruošiuosi pradėti pripažinti savo argv masyvas kaip const tik todėl, kad aš žinau,

416
00:32:10,640 --> 00:32:14,550
kad šie argumentai yra argumentai, kad aš tikriausiai nenori keisti.

417
00:32:14,550 --> 00:32:18,390
Jei aš noriu juos pakeisti, aš tikriausiai turėtų būti padaryti jų kopijas.

418
00:32:18,390 --> 00:32:21,740
Jūs pamatysite šį kodą daug.

419
00:32:21,740 --> 00:32:25,440
Tai gerai bet kuriuo atveju. Tai gerai, palikti jį praleisti const, jei norite.

420
00:32:25,440 --> 00:32:28,630
Aš paprastai įdėti jį tik todėl, kad aš priminti sau,

421
00:32:28,630 --> 00:32:33,650
 , kad aš tikriausiai nenorite keisti šiuos argumentus.

422
00:32:33,650 --> 00:32:39,240
>> Kaip visada, aš ruošiuosi šį return 0 liniją pagrindinis pabaigoje.

423
00:32:39,240 --> 00:32:45,730
Čia, aš inicijuoti mano šakninis mazgas.

424
00:32:45,730 --> 00:32:48,900
, Kokia ji yra dabar, aš turiu rodyklę, kad nustatyta reikšmė NULL,

425
00:32:48,900 --> 00:32:52,970
todėl jis rodo nieko.

426
00:32:52,970 --> 00:32:57,480
Tam, kad iš tikrųjų pradėti statybos mazgas,

427
00:32:57,480 --> 00:32:59,250
Aš pirmiausia reikia skirti atminties.

428
00:32:59,250 --> 00:33:05,910
Aš ruošiuosi padaryti, kad atmintis malloc krūvos.

429
00:33:05,910 --> 00:33:10,660
Aš ruošiuosi nustatyti vienodas šaknis į malloc rezultatas,

430
00:33:10,660 --> 00:33:19,550
ir aš ruošiuosi naudoti sizeof operatoriaus mazgo dydį apskaičiuoti.

431
00:33:19,550 --> 00:33:24,990
Priežastis, kad aš naudoju, sizeof mazgas, o ne, tarkim,

432
00:33:24,990 --> 00:33:37,020
daryti kažką panašaus į tai - malloc (4 + 4 +4) arba malloc 12 -

433
00:33:37,020 --> 00:33:40,820
yra todėl, kad aš noriu, kad mano kodas turi būti kuo labiau suderintos.

434
00:33:40,820 --> 00:33:44,540
Aš noriu, kad būtų galima pasinaudoti šia C failą, kaupia jį ant prietaiso,

435
00:33:44,540 --> 00:33:48,820
ir kaupia jį ant mano 64-bitų "Mac -

436
00:33:48,820 --> 00:33:52,040
arba visiškai skirtingos architektūros

437
00:33:52,040 --> 00:33:54,640
ir aš noriu, kad visa tai veikia taip pat.

438
00:33:54,640 --> 00:33:59,510
>> Jei aš darant prielaidas apie kintamųjų dydžio

439
00:33:59,510 --> 00:34:02,070
int ar rodykle dydžio dydis -

440
00:34:02,070 --> 00:34:06,070
tada aš taip pat darant prielaidas apie architektūrų rūšių

441
00:34:06,070 --> 00:34:10,440
mano kodas gali sėkmingai sudaryti, kai paleisti.

442
00:34:10,440 --> 00:34:15,030
Sizeof visada naudoti, o ne rankiniu būdu sudedant struct laukus.

443
00:34:15,030 --> 00:34:20,500
Kita priežastis yra tai, kad taip pat gali būti prikimšti, kad kompiliatorius pradeda struct.

444
00:34:20,500 --> 00:34:26,570
Net tik sudedant atskirų laukų nėra kažkas, kad jūs paprastai nori daryti,

445
00:34:26,570 --> 00:34:30,340
taip, ištrinti tą eilutę.

446
00:34:30,340 --> 00:34:33,090
Dabar tikrai inicijuoti šį šakninis mazgas,

447
00:34:33,090 --> 00:34:36,489
Aš ruošiuosi turite prijungti verčių kiekvienam savo įvairių sričių.

448
00:34:36,489 --> 00:34:41,400
Pavyzdžiui, vertės, aš žinau, aš noriu inicijuoti iki 7,

449
00:34:41,400 --> 00:34:46,920
ir dabar aš ruošiuosi kairėje vaikas yra niekinis

450
00:34:46,920 --> 00:34:55,820
ir teisę vaikui taip pat turi būti nulinis. Puiku!

451
00:34:55,820 --> 00:35:02,670
Mes padarėme, kad spec dalis.

452
00:35:02,670 --> 00:35:07,390
>> Specifikacija 3 psl apačioje prašo manęs sukurti tris daugiau mazgų -

453
00:35:07,390 --> 00:35:10,600
Kurių sudėtyje yra ne daugiau kaip 3, vienas yra 6, ir vienas su 9 -

454
00:35:10,600 --> 00:35:14,210
ir tada pervesti juos, todėl jis atrodo lygiai taip pat kaip mūsų medžio diagrama

455
00:35:14,210 --> 00:35:17,120
, kad mes kalbame apie anksčiau.

456
00:35:17,120 --> 00:35:20,450
Darykime, kad gana greitai čia.

457
00:35:20,450 --> 00:35:26,270
Jūs pamatysite labai greitai, kad aš ruošiuosi pradėti rašyti pasikartojančių kodas krūva.

458
00:35:26,270 --> 00:35:32,100
Aš ruošiuosi sukurti mazgas * ir aš ruošiuosi jį pavadinti 3.

459
00:35:32,100 --> 00:35:36,000
Aš ruošiuosi nustatyti, kad jis lygus malloc (sizeof (mazgas)).

460
00:35:36,000 --> 00:35:41,070
Aš ruošiuosi nustatyti trys-> value = 3.

461
00:35:41,070 --> 00:35:54,780
Trys -> left_child = NULL, trys -> į dešinę _child = NULL, taip pat.

462
00:35:54,780 --> 00:36:01,150
Kad atrodo gana panašus į Inicijuojama šaknis, ir tai yra būtent tai, ko

463
00:36:01,150 --> 00:36:05,760
Aš ruošiuosi daryti, jei aš pradedu Inicijuojama 6 ir 9 straipsniuose, taip pat.

464
00:36:05,760 --> 00:36:20,720
Aš padarysiu, kad tikrai greitai čia - iš tiesų, aš padaryti šiek tiek kopijuoti ir įklijuoti,

465
00:36:20,720 --> 00:36:46,140
ir įsitikinkite, kad aš - viskas tvarkoj.

466
00:36:46,470 --> 00:37:09,900
 Dabar, aš turiu jį nukopijuoti ir aš galiu eiti į priekį ir nustatyti tai, lygus 6.

467
00:37:09,900 --> 00:37:14,670
Jūs galite pamatyti, kad tai trunka kurį laiką ir nėra itin efektyvus.

468
00:37:14,670 --> 00:37:22,610
Tik šiek tiek, mes parašyti funkciją, kuri bus tai padaryti už mus.

469
00:37:22,610 --> 00:37:32,890
Aš noriu pakeisti, tai su 9, pakeisti, kad su 6.

470
00:37:32,890 --> 00:37:37,360
>> Dabar mes turime visus mūsų mazgų sukurta ir inicializuoti.

471
00:37:37,360 --> 00:37:41,200
Mes turime mūsų šaknis nustatyti lygi 7, arba kurių sudėtyje yra vertę 7

472
00:37:41,200 --> 00:37:46,510
mūsų mazgas, kurioje yra 3, mūsų mazgas yra 6, o mūsų mazgas yra 9.

473
00:37:46,510 --> 00:37:50,390
Šiuo metu, visi mes turime padaryti, yra vielos viską aukštyn.

474
00:37:50,390 --> 00:37:53,020
Priežastis, kodėl aš inicijuoti visų patarimų nulis yra tik todėl, kad aš įsitikinkite, kad

475
00:37:53,020 --> 00:37:56,260
Aš neturiu ten jokių niezainicjowanymi patarimų dėl nelaimingo atsitikimo.

476
00:37:56,260 --> 00:38:02,290
Ir taip pat nuo, šiuo metu, aš tik turi realiai prisijungti mazgai vienas su kitu -

477
00:38:02,290 --> 00:38:04,750
į tuos, kurie, kad jie iš tikrųjų susijusių Aš neturiu eiti ir padaryti

478
00:38:04,750 --> 00:38:08,240
tikrai, kad visi nulls ten į reikiamas vietas.

479
00:38:08,240 --> 00:38:15,630
>> Pradedant nuo šaknų, žinau, kad root kairėje vaikas 3.

480
00:38:15,630 --> 00:38:21,250
Aš žinau, kad root teisės vaikui yra 9.

481
00:38:21,250 --> 00:38:24,880
Po to, tik kitas vaikas, kad man liko nerimauti

482
00:38:24,880 --> 00:38:39,080
yra 3 teisingas vaikas, kuris yra 6.

483
00:38:39,080 --> 00:38:44,670
Šiuo metu, viskas atrodo gana gerai.

484
00:38:44,670 --> 00:38:54,210
Mes ištrinti kai kuriuos iš šių eilučių.

485
00:38:54,210 --> 00:38:59,540
Dabar viskas atrodo gana gerai.

486
00:38:59,540 --> 00:39:04,240
Grįžkime mūsų specifikacija ir pamatyti, ką mes turime daryti toliau.

487
00:39:04,240 --> 00:39:07,610
>> Šiuo metu, mes turime rašyti funkcija, vadinama "yra"

488
00:39:07,610 --> 00:39:14,150
"bool Sudėtyje yra (int vertė)" prototipas.

489
00:39:14,150 --> 00:39:17,060
Ir tai yra funkcija return true

490
00:39:17,060 --> 00:39:21,200
 jei atkreipė dėmesį į mūsų pasaulio šaknies kintamojo medis

491
00:39:21,200 --> 00:39:26,950
 yra vertę perėjo į funkcijos ir klaidingas kitaip.

492
00:39:26,950 --> 00:39:29,000
Eikime į priekį ir padaryti, kad.

493
00:39:29,000 --> 00:39:35,380
Tai bus lygiai taip pat kaip peržvalgos, kad mes padarėme ranka iPad truputį prieš.

494
00:39:35,380 --> 00:39:40,130
Tegul padidinti šiek tiek ir slinkdami aukštyn.

495
00:39:40,130 --> 00:39:43,130
Mes ketiname įdėti šią funkciją, tiesiai virš mūsų pagrindinė funkcija

496
00:39:43,130 --> 00:39:48,990
kad mes neturime daryti jokių prototipų rūšiuoti.

497
00:39:48,990 --> 00:39:55,960
Taigi, bool yra (int vertė).

498
00:39:55,960 --> 00:40:00,330
Čia mes eiti. Mūsų Standartiniai deklaracija.

499
00:40:00,330 --> 00:40:02,900
Tiesiog įsitikinkite, kad tai bus sudaryti,

500
00:40:02,900 --> 00:40:06,820
Aš ruošiuosi eiti į priekį ir tik nustatyti, kad jis lygus gražins false.

501
00:40:06,820 --> 00:40:09,980
Dabar ši funkcija tiesiog nebus nieko daryti ir visada teigia, kad

502
00:40:09,980 --> 00:40:14,010
ta vertybė, kad mes ieškome ne į medį.

503
00:40:14,010 --> 00:40:16,280
>> Šiuo metu, tai tikriausiai gera idėja -

504
00:40:16,280 --> 00:40:19,600
nes mes jau parašyta visa krūva kodo, ir mes net bandė išbandyti jį dar

505
00:40:19,600 --> 00:40:22,590
įsitikinti, kad visa tai rengia.

506
00:40:22,590 --> 00:40:27,460
Yra pora dalykų, kad mes turime padaryti, siekiant įsitikinti, kad tai iš tikrųjų sudaryti.

507
00:40:27,460 --> 00:40:33,530
Pirma, pamatyti, jei mes jau naudoju bet kokius bet kokių bibliotekų funkcijas, kad mes dar nėra įtrauktos.

508
00:40:33,530 --> 00:40:37,940
Funkcijos, mes naudojame iki šiol yra malloc,

509
00:40:37,940 --> 00:40:43,310
ir tada mes taip pat naudojant šio tipo - šį nestandartinį tipas vadinamas "bool'

510
00:40:43,310 --> 00:40:45,750
, kuris yra įtrauktas į standartinę Bool antraštės faile.

511
00:40:45,750 --> 00:40:53,250
Mes tikrai norite įtraukti standartinę už bool tipo bool.h,

512
00:40:53,250 --> 00:40:59,230
ir mes taip pat norime # include standartinę standartinių bibliotekų lib.h

513
00:40:59,230 --> 00:41:03,530
kad malloc ir nemokamai, ir visa tai.

514
00:41:03,530 --> 00:41:08,660
Taigi, nutolinti, mes ruošiamės mesti rūkyti.

515
00:41:08,660 --> 00:41:14,190
Pabandykime ir įsitikinti, kad tai iš tikrųjų kompiliavimo.

516
00:41:14,190 --> 00:41:18,150
Mes matome, kad jis, kad esame teisingame kelyje.

517
00:41:18,150 --> 00:41:22,990
>> Tegul atverti binary_tree.c vėl.

518
00:41:22,990 --> 00:41:34,530
Ji rengia. Eikime ir įsitikinkite, kad mes įterpti keletą skambučius į mūsų Sudėtyje yra funkcija -

519
00:41:34,530 --> 00:41:40,130
tiesiog įsitikinkite, kad viskas gerai ir gerai.

520
00:41:40,130 --> 00:41:43,170
Pavyzdžiui, kai mes padarėme kai kuriuos mūsų medžio paieška ir anksčiau,

521
00:41:43,170 --> 00:41:48,500
mes bandėme ieškoti vertes, 6, 10, ir 1, ir mes žinojome, kad 6 medyje,

522
00:41:48,500 --> 00:41:52,220
10 buvo ne į medį, ir 1 ne į medį.

523
00:41:52,220 --> 00:41:57,230
Leiskite naudoti imties skambučius, tokiu būdu išsiaiškinti, ar

524
00:41:57,230 --> 00:41:59,880
mūsų Contains funkcija veikia.

525
00:41:59,880 --> 00:42:05,210
Tam, kad padaryti, kad aš ruošiuosi naudoti printf funkciją,

526
00:42:05,210 --> 00:42:10,280
ir mes ketiname atsispausdinti raginimą kuriame rezultatą.

527
00:42:10,280 --> 00:42:13,280
Aš ruošiuosi įdėti į eilutę "Sudėtyje yra (% d) =, nes

528
00:42:13,280 --> 00:42:20,470
 mes ketiname prijungti vertės, kad mes ketiname ieškoti,

529
00:42:20,470 --> 00:42:27,130
=% s \ n "ir naudoti, kad mūsų formato eilutę.

530
00:42:27,130 --> 00:42:30,720
Mes tiesiog ketiname pamatyti - tiesiog atspausdinti ekrane

531
00:42:30,720 --> 00:42:32,060
kas atrodo skambinimo funkcijos.

532
00:42:32,060 --> 00:42:33,580
Tai nėra iš tikrųjų funkcija skambinti.

533
00:42:33,580 --> 00:42:36,760
 Tai tik eilutė, skirta atrodyti skambinimo funkcijos.

534
00:42:36,760 --> 00:42:41,140
>> Dabar mes ketiname prijungti vertybėmis.

535
00:42:41,140 --> 00:42:43,580
Mes ketiname bandyti yra apie 6,

536
00:42:43,580 --> 00:42:48,340
ir po to, ką mes ketiname daryti čia yra naudoti, kad trijų komponentų operatorių.

537
00:42:48,340 --> 00:42:56,340
Pažiūrėkime, - yra 6 - taip, dabar aš yra 6, ir jei turi 6 yra tiesa,

538
00:42:56,340 --> 00:43:01,850
eilutė, kad mes ketiname siųsti% s formatas pobūdžio

539
00:43:01,850 --> 00:43:04,850
bus eilutė "true".

540
00:43:04,850 --> 00:43:07,690
Leiskite slinkti per šiek tiek.

541
00:43:07,690 --> 00:43:16,210
Priešingu atveju, mes norime siųsti eilutė "false", jei yra 6 False.

542
00:43:16,210 --> 00:43:19,730
Tai yra šiek tiek Goofy ieškote, bet aš paveikslą aš taip pat iliustruoja

543
00:43:19,730 --> 00:43:23,780
Ternary operatorius atrodo, nes mes nemačiau kurį laiką.

544
00:43:23,780 --> 00:43:27,670
Tai bus gražus, patogus būdas išsiaiškinti, ar mūsų Contains funkcija veikia.

545
00:43:27,670 --> 00:43:30,040
Aš ruošiuosi slinkti atgal perkelti į kairę,

546
00:43:30,040 --> 00:43:39,900
ir aš ruošiuosi, nukopijuokite ir įklijuokite šią eilutę kelis kartus.

547
00:43:39,900 --> 00:43:44,910
Pasikeitė kai kurie iš šių verčių aplink,

548
00:43:44,910 --> 00:43:59,380
todėl tai bus 1, o tai bus 10.

549
00:43:59,380 --> 00:44:02,480
>> Šiuo metu mes turime gražią Sudėtyje yra funkcija.

550
00:44:02,480 --> 00:44:06,080
Mes turime tam tikrus tyrimus, ir mes pamatyti, jei visa tai veikia.

551
00:44:06,080 --> 00:44:08,120
Šiuo metu mes parašiau šiek tiek daugiau kodą.

552
00:44:08,120 --> 00:44:13,160
Laikas mesti, ir įsitikinkite, kad viskas dar rengia.

553
00:44:13,160 --> 00:44:20,360
Mesti, o dabar pabandykime vėl dvejetainis medis.

554
00:44:20,360 --> 00:44:22,260
Na, atrodo, kad mes turime klaidą

555
00:44:22,260 --> 00:44:26,930
Ir mes turime tai aiškiai skelbiantis bibliotekos funkcija printf.

556
00:44:26,930 --> 00:44:39,350
Atrodo, kad mes turime eiti ir # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
O, kad viskas turėtų sudaryti. Mes visi gerai.

558
00:44:45,350 --> 00:44:50,420
Dabar pabandykime paleisti dvejetainis medis, ir žiūrėsime kas atsitiks.

559
00:44:50,420 --> 00:44:53,520
Mes čia,. / Binary_tree

560
00:44:53,520 --> 00:44:55,190
ir mes matome, kad, kaip ir tikėjomės -

561
00:44:55,190 --> 00:44:56,910
nes mes ne įgyvendintos, yra dar

562
00:44:56,910 --> 00:44:59,800
arba, tiksliau, mes tiesiog įdėti Return FALSE -

563
00:44:59,800 --> 00:45:03,300
matome, kad ji manimi tik grįžau false juos visus,

564
00:45:03,300 --> 00:45:06,180
kad didžiąja dalimi visi dirba pakankamai gerai.

565
00:45:06,180 --> 00:45:11,860
>> Eikime atgal ir iš tikrųjų įgyvendinti yra šiuo metu.

566
00:45:11,860 --> 00:45:17,490
Aš ruošiuosi slinkti žemyn, padidinti, ir -

567
00:45:17,490 --> 00:45:22,330
atminkite, kad mes naudojamas algoritmas buvo, kad mes pradėjome šakninis mazgas

568
00:45:22,330 --> 00:45:28,010
, o vėliau kiekvieną mazgą, kad mes susiduriame, mes palyginti

569
00:45:28,010 --> 00:45:32,380
ir remiantis šio palyginimo, mes arba judėti į kairę vaikui, ar į dešinę vaikui.

570
00:45:32,380 --> 00:45:39,670
Tai va, atrodo labai panaši į dvejetainis paieškos kodą, kad mes parašė anksčiau termino.

571
00:45:39,670 --> 00:45:47,810
Kai mes pradėti žaisti, mes žinome, kad nori eiti į dabartinio mazgo

572
00:45:47,810 --> 00:45:54,050
, kurioje mes ir būti inicializuoti su šakninis mazgas mazgas.

573
00:45:54,050 --> 00:45:56,260
Ir dabar, mes ketiname nuolat išgyvena medžio,

574
00:45:56,260 --> 00:45:58,140
ir prisiminti, kad mūsų stabdymo sąlygą -

575
00:45:58,140 --> 00:46:01,870
 kai mes iš tikrųjų dirbo per pavyzdyje ranka -

576
00:46:01,870 --> 00:46:03,960
buvo, kai mes susidūrėme su null mazgas,

577
00:46:03,960 --> 00:46:05,480
kai mes pažvelgė neapibrėžta vaikui,

578
00:46:05,480 --> 00:46:09,620
, o tada, kai mes iš tikrųjų persikėlė į mazgo į medį

579
00:46:09,620 --> 00:46:12,640
ir nustatė, kad mes ne nulinis mazgas.

580
00:46:12,640 --> 00:46:20,720
Mes ketiname pakartoti iki dab nėra lygus NULL.

581
00:46:20,720 --> 00:46:22,920
Ir ką mes ketiname daryti?

582
00:46:22,920 --> 00:46:31,610
Mes ketiname išbandyti, jei (dab -> == vertė),

583
00:46:31,610 --> 00:46:35,160
tada mes žinome, kad mes iš tikrųjų surado mazgas, mes ieškome.

584
00:46:35,160 --> 00:46:40,450
Taigi čia, mes galime grįžti tiesa.

585
00:46:40,450 --> 00:46:49,830
Priešingu atveju, mes norime pamatyti, ar vertė yra mažesnė už vertę,.

586
00:46:49,830 --> 00:46:53,850
Jei dabartinės mazgo vertė yra mažesnė už vertę, mes ieškome,

587
00:46:53,850 --> 00:46:57,280
mes ketiname pereiti į dešinę.

588
00:46:57,280 --> 00:47:10,600
Taigi, dab = Suo -> right_child; ir kitaip, mes ketiname judėti į kairę.

589
00:47:10,600 --> 00:47:17,480
dab = dab -> left_child;. Gana paprasta.

590
00:47:17,480 --> 00:47:22,830
>> Jūs tikriausiai pripažinti kilpa, kuri atrodo labai panašus į šį

591
00:47:22,830 --> 00:47:27,580
dvejetainis paieškos anksčiau termino, išskyrus tada mes buvo susijusios su mažos, vidutinės ir aukštos.

592
00:47:27,580 --> 00:47:30,000
Čia, mes tiesiog turime pažvelgti į dabartinės vertės,

593
00:47:30,000 --> 00:47:31,930
todėl gražus ir paprastas.

594
00:47:31,930 --> 00:47:34,960
Padarykime, kad šis kodas veikia.

595
00:47:34,960 --> 00:47:42,780
Pirmiausia, įsitikinkite, kad ji rengia. Atrodo, kad ji veikia.

596
00:47:42,780 --> 00:47:47,920
Pabandykime paleisti jį.

597
00:47:47,920 --> 00:47:50,160
Ir iš tiesų, tai spausdina viską, kad tikėjomės.

598
00:47:50,160 --> 00:47:54,320
Ji nustato, 6 medyje, nemano, kad 10, nes 10 ne į medį,

599
00:47:54,320 --> 00:47:57,740
ir nemano, kad nors 1, nes 1 taip pat ne į medį.

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

601
00:48:01,420 --> 00:48:04,470
>> Alright. Grįžkime mūsų specifikacija ir pamatyti, kas toliau.

602
00:48:04,470 --> 00:48:07,990
Dabar jis nori pridėti šiek tiek daugiau mazgų mūsų medžio.

603
00:48:07,990 --> 00:48:11,690
Jis nori pridėti 5, 2 ir 8, ir įsitikinkite, kad mūsų yra kodas

604
00:48:11,690 --> 00:48:13,570
vis dar veikia taip, kaip tikėtasi.

605
00:48:13,570 --> 00:48:14,900
Eikime daryti.

606
00:48:14,900 --> 00:48:19,430
Šiuo metu, o ne daro, kad erzina kopijuoti ir įklijuoti vėl,

607
00:48:19,430 --> 00:48:23,770
tegul parašyti funkciją, kad iš tikrųjų sukurti mazgas.

608
00:48:23,770 --> 00:48:27,740
Jei mes slinkti žemyn visą kelią į pagrindinį, matome, kad mes jau tai daryti

609
00:48:27,740 --> 00:48:31,210
labai panašus kodas vėl ir vėl kiekvieną kartą, kad mes norime sukurti mazgas.

610
00:48:31,210 --> 00:48:39,540
>> Tegul parašyti funkciją, kad tikrai bus statyti mazgas mums ir grąžinti jį.

611
00:48:39,540 --> 00:48:41,960
Aš ruošiuosi jį vadinti build_node.

612
00:48:41,960 --> 00:48:45,130
Aš ruošiuosi sukurti mazgas su konkrečios vertės.

613
00:48:45,130 --> 00:48:51,040
Padidinti čia.

614
00:48:51,040 --> 00:48:56,600
Pirmas dalykas, aš ruošiuosi daryti iš tikrųjų sukurti vietos krūvos mazgas.

615
00:48:56,600 --> 00:49:05,400
Taigi, mazgas * n = malloc (sizeof (mazgas)), n -> = vertė;

616
00:49:05,400 --> 00:49:14,960
ir tada čia, aš tik ketina inicijuoti visus laukus būti atitinkamas vertes.

617
00:49:14,960 --> 00:49:22,500
Ir pačioje pabaigoje, sugrįšime mūsų mazgas.

618
00:49:22,500 --> 00:49:28,690
Alright. Vienas dalykas, reikia pažymėti, kad šią funkciją čia

619
00:49:28,690 --> 00:49:34,320
vyksta grąžina rodyklę į atmintį, kad buvo krūva skirtos.

620
00:49:34,320 --> 00:49:38,880
Kas yra malonu apie tai, kad šis mazgas -

621
00:49:38,880 --> 00:49:42,420
mes turime paskelbti ją suderinama su bendrąja rinka. krūvą, nes jei mes paskelbė jį ant kamino

622
00:49:42,420 --> 00:49:45,050
mes negalėtų tai padaryti šią funkciją, kaip šis.

623
00:49:45,050 --> 00:49:47,690
Kad atmintis būtų išeiti iš taikymo srities

624
00:49:47,690 --> 00:49:51,590
ir negalioja, jei mes bandėme kreiptis į jį vėliau.

625
00:49:51,590 --> 00:49:53,500
Kadangi mes skelbiantis krūva skirtos atminties,

626
00:49:53,500 --> 00:49:55,830
mes ketiname rūpintis išlaisvinant jį vėliau

627
00:49:55,830 --> 00:49:58,530
mūsų programos negalėtų ištekėti bet kokią atmintį.

628
00:49:58,530 --> 00:50:01,270
Mes jau Punting, kad visa kita kodą

629
00:50:01,270 --> 00:50:02,880
tik Paprastumo dėlei metu,

630
00:50:02,880 --> 00:50:05,610
tačiau, jei jūs kada nors parašyti funkciją, kuri atrodo taip

631
00:50:05,610 --> 00:50:10,370
kur jūs turite kai ją vadina malloc arba realloc viduje -

632
00:50:10,370 --> 00:50:14,330
jūs norite įsitikinti, kad jūs įtraukėte kažkokią komentarų čia, kad sako,

633
00:50:14,330 --> 00:50:29,970
ei, juk žinot, grąžina krūva skirtos praėjo vertės inicijuotas mazgas.

634
00:50:29,970 --> 00:50:33,600
Ir tada jūs norite įsitikinti, kad jūs įtraukėte į kažkokiu pastabos, kad sako

635
00:50:33,600 --> 00:50:41,720
skambinantysis turi išlaisvinti grįžo atmintį.

636
00:50:41,720 --> 00:50:45,450
Tokiu būdu, jei kas nors kada nors eina, ir naudoja šią funkciją,

637
00:50:45,450 --> 00:50:48,150
jie žino, kad ką jie grįžti iš šios funkcijos

638
00:50:48,150 --> 00:50:50,870
tam tikru momentu turės būti išlaisvintas.

639
00:50:50,870 --> 00:50:53,940
>> Darant prielaidą, kad viskas yra gerai ir gera čia,

640
00:50:53,940 --> 00:51:02,300
mes galime eiti į mūsų kodą ir pakeisti visi šių eilučių čia

641
00:51:02,300 --> 00:51:05,410
skambučius į mūsų statyti mazgo funkcijos.

642
00:51:05,410 --> 00:51:08,170
Darykime, kad tikrai greitai.

643
00:51:08,170 --> 00:51:15,840
Viena dalis yra tai, kad mes neketiname pakeisti dalis žemyn čia

644
00:51:15,840 --> 00:51:18,520
apačioje, kur mes iš tikrųjų viela iki mazgai vienas su kitu,

645
00:51:18,520 --> 00:51:21,030
dėl to, kad mes negalime padaryti savo funkcijas.

646
00:51:21,030 --> 00:51:37,400
Bet, darykime root = build_node (7); mazgas * trys = build_node (3);

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

648
00:51:47,980 --> 00:51:52,590
Ir dabar, mes taip pat norėjo pridėti mazgų -

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

650
00:52:03,530 --> 00:52:09,760
ir kas buvo kitas mazgas? Pažiūrėkime čia. Mes norėjome taip pat pridėti 2 -

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

652
00:52:20,280 --> 00:52:26,850
Alright. Šiuo metu, mes žinome, kad mes turime 7, 3, 9, ir 6

653
00:52:26,850 --> 00:52:30,320
visi laidinio tinkamai, bet ką galima pasakyti apie 5, 8, o 2?

654
00:52:30,320 --> 00:52:33,550
Išlaikyti viskas kaip pridera,

655
00:52:33,550 --> 00:52:39,230
mes žinome, kad 3 teisė vaikui yra 6.

656
00:52:39,230 --> 00:52:40,890
Taigi, jei mes ketiname pridėti 5,

657
00:52:40,890 --> 00:52:46,670
5 taip pat priklauso į dešinę iš medžio, iš kurių 3 yra šaknis,

658
00:52:46,670 --> 00:52:50,440
taip 5 priklauso kairėje vaikui nuo 6.

659
00:52:50,440 --> 00:52:58,650
Mes galime tai padaryti, sakydamas: 6 -> left_child = penki;

660
00:52:58,650 --> 00:53:10,790
ir tada 8 priklauso kairėje vaiku 9, todėl devintų -> left_child = 8;

661
00:53:10,790 --> 00:53:22,190
ir tada 2 yra kairėje vaikas 3, todėl mes galime padaryti, kad čia - tave -> left_child = dvi;

662
00:53:22,190 --> 00:53:27,730
Jei tu ne visai sekti kartu su tuo, aš siūlau jums padaryti ją sau.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Išsaugokime tai. Eikime ir įsitikinkite, kad ji rengia,

664
00:53:35,660 --> 00:53:40,760
ir tada mes galime įdėti mūsų Contains skambučius.

665
00:53:40,760 --> 00:53:44,120
Atrodo, viskas vis dar rengia.

666
00:53:44,120 --> 00:53:51,790
Eikime ir pridėti kai yra skambučius.

667
00:53:51,790 --> 00:53:59,640
Vėlgi, aš ruošiuosi daryti šiek tiek kopijuoti ir įklijuoti.

668
00:53:59,640 --> 00:54:15,860
Dabar galime ieškoti 5, 8 ir 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Kurkime tikri, kad visa tai gerai atrodo dar. Puiku! Išsaugoti ir išeiti.

670
00:54:28,330 --> 00:54:33,220
Dabar padarykime, kaupti, ir dabar galime paleisti.

671
00:54:33,220 --> 00:54:37,540
Iš gautų rezultatų, atrodo, viskas veikia tiesiog gražus ir gerai.

672
00:54:37,540 --> 00:54:41,780
Puiku! Taigi dabar mes turime parašyta mūsų Contains funkciją.

673
00:54:41,780 --> 00:54:46,160
Pereikime ir pradėti dirbti, kaip įterpti į medį mazgų

674
00:54:46,160 --> 00:54:50,000
, nes, kaip mes darome tai dabar, viskas nėra labai gražus.

675
00:54:50,000 --> 00:54:52,280
>> Jei mes einame atgal į specifikaciją,

676
00:54:52,280 --> 00:55:00,540
jis klausia mums parašyti funkcija vadinama įterpti - vėl grįžta bool

677
00:55:00,540 --> 00:55:04,400
ar mes iš tikrųjų galėtų įterpti į medį mazgas -

678
00:55:04,400 --> 00:55:07,710
ir tada reikšmė, įterpti į medį, yra nurodyta kaip

679
00:55:07,710 --> 00:55:11,060
Vienintelis argumentas mūsų įterpti funkciją.

680
00:55:11,060 --> 00:55:18,180
Mes grąžina true, jei mes iš tiesų galėtų įterpti mazgo, kuriame vertę į medį,

681
00:55:18,180 --> 00:55:20,930
, o tai reiškia, kad mes, vienas, turėjo pakankamai atminties,

682
00:55:20,930 --> 00:55:24,840
ir tada du, kad mazgas nebuvo jau egzistuoja į medį, nes -

683
00:55:24,840 --> 00:55:32,170
Nepamirškite, kad mes neketiname turėti pasikartojančius vertybes į medį, tik kad viskas paprasta.

684
00:55:32,170 --> 00:55:35,590
Alright. Atgal, kad kodą.

685
00:55:35,590 --> 00:55:44,240
Atidarykite jį. Padidinti šiek tiek, tada slinkite žemyn.

686
00:55:44,240 --> 00:55:47,220
Tegul įterpimo funkciją tiesiai virš sudėtį įeina.

687
00:55:47,220 --> 00:55:56,360
Vėlgi, tai bus vadinama bool įterpti (int vertė).

688
00:55:56,360 --> 00:56:01,840
Suteikite jam šiek tiek daugiau erdvės, ir tada, kaip numatytąjį,

689
00:56:01,840 --> 00:56:08,870
tegul Return FALSE pačioje pabaigoje.

690
00:56:08,870 --> 00:56:22,620
Dabar žemyn apačioje, eikime į priekį ir, o ne rankiniu būdu pastato mazgai

691
00:56:22,620 --> 00:56:27,900
Pagrindinis save ir instaliacijos juos vienas su kitu, kaip mes darome,

692
00:56:27,900 --> 00:56:30,600
mes pasikliauti mūsų įterpti funkciją, kaip tai padaryti.

693
00:56:30,600 --> 00:56:35,510
Mes negali remtis mūsų įterpti funkciją, sukurti visą medį nuo nulio tik dar,

694
00:56:35,510 --> 00:56:39,970
, o mes atsikratyti šių eilučių - we'll pastabas iš šių linijų -

695
00:56:39,970 --> 00:56:43,430
kad sukurti mazgai 5, 8 ir 2.

696
00:56:43,430 --> 00:56:55,740
Ir vietoj to, mes įterpti skambučius į mūsų įterpti funkciją

697
00:56:55,740 --> 00:57:01,280
įsitikinti,, kad tai iš tiesų veikia.

698
00:57:01,280 --> 00:57:05,840
Čia mes einame.

699
00:57:05,840 --> 00:57:09,300
>> Dabar mes komentavo šias eilutes.

700
00:57:09,300 --> 00:57:13,700
Turime tik 7, 3, 9, ir 6 Šiuo metu mūsų medžio.

701
00:57:13,700 --> 00:57:18,870
Norėdami įsitikinti, kad tai yra visi dirba,

702
00:57:18,870 --> 00:57:25,050
mes galime nutolinti, kad mūsų dvejetainis medis,

703
00:57:25,050 --> 00:57:30,750
paleiskite jį ir matome, kad yra dabar mums sako, kad mes visiškai teisus -

704
00:57:30,750 --> 00:57:33,110
5, 8 ir 2 nebėra į medį.

705
00:57:33,110 --> 00:57:37,960
Grįžti į kodą,

706
00:57:37,960 --> 00:57:41,070
ir kaip mes ketiname įterpti?

707
00:57:41,070 --> 00:57:46,290
Prisiminkite, ką mes padarėme, kai mes iš tikrųjų buvo įterpiant 5, 8 ir 2 anksčiau.

708
00:57:46,290 --> 00:57:50,100
Mes grojo, kad Plinko žaidimas, kur mes pradėjome ne šaknis,

709
00:57:50,100 --> 00:57:52,780
sumažėjo medžio vieną po vieną

710
00:57:52,780 --> 00:57:54,980
kol mes radome tinkamą spragą,

711
00:57:54,980 --> 00:57:57,570
ir tada mes laidinio mazgas ne tinkamoje vietoje.

712
00:57:57,570 --> 00:57:59,480
Mes ketiname padaryti tą patį.

713
00:57:59,480 --> 00:58:04,070
Tai iš esmės kaip rašyti kodą, kad mes panaudojome yra funkcija

714
00:58:04,070 --> 00:58:05,910
rasti vietoje, kur turėtų būti mazgas,

715
00:58:05,910 --> 00:58:10,560
ir tada mes tiesiog įterpti mazgas.

716
00:58:10,560 --> 00:58:17,000
Pradėkime tai daro.

717
00:58:17,000 --> 00:58:24,200
>> Taigi, mes turime mazgas * dab = root, mes tiesiog sekti, yra kodas

718
00:58:24,200 --> 00:58:26,850
kol mes suprato, kad tai ne visai dirbti pas mus.

719
00:58:26,850 --> 00:58:32,390
Mes ketiname eiti per medį, o dabartinis elementas nėra lygus nuliui,

720
00:58:32,390 --> 00:58:45,280
ir jei mes to dab vertė yra lygi vertės, kad mes bandome įterpti -

721
00:58:45,280 --> 00:58:49,600
gerai, tai vienas iš atvejų, kuriais mes tikrai negalėjo įterpti mazgas

722
00:58:49,600 --> 00:58:52,730
į medį, nes tai reiškia, kad turime pasikartojančią reikšmę.

723
00:58:52,730 --> 00:58:59,010
Čia mes iš tikrųjų ketiname gražins false.

724
00:58:59,010 --> 00:59:08,440
Dabar, dar jei dab vertė yra mažesnė nei vertės,

725
00:59:08,440 --> 00:59:10,930
dabar mes žinome, kad mes einame į dešinę

726
00:59:10,930 --> 00:59:17,190
 nes vertė priklauso dešinėje pusėje dab medžio.

727
00:59:17,190 --> 00:59:30,110
Priešingu atveju, mes ketiname pereiti į kairę.

728
00:59:30,110 --> 00:59:37,980
Tai iš esmės mūsų Contains veikti tiesiai ten.

729
00:59:37,980 --> 00:59:41,820
>> Šiuo metu, kai baigsime šį while cikle,

730
00:59:41,820 --> 00:59:47,350
mūsų dab rodyklė turi būti nukreipta į null

731
00:59:47,350 --> 00:59:51,540
jei ši funkcija nėra jau grįžo.

732
00:59:51,540 --> 00:59:58,710
Todėl mes dab toje vietoje, kur mes norime įterpti naują mazgas.

733
00:59:58,710 --> 01:00:05,210
Ką dar reikia padaryti, kad iš tikrųjų sukurti naują mazgas,

734
01:00:05,210 --> 01:00:08,480
mes galime padaryti gana lengvai.

735
01:00:08,480 --> 01:00:14,930
Mes galime naudoti mūsų super patogu statyti mazgo funkciją,

736
01:00:14,930 --> 01:00:17,210
ir kažkas, kad mes nepadarė anksčiau -

737
01:00:17,210 --> 01:00:21,400
Mes tiesiog rūšies laikė savaime suprantamu, bet dabar mes padaryti, tiesiog įsitikinkite, kad

738
01:00:21,400 --> 01:00:27,130
mes išbandyti, įsitikinti, kad iš tikrųjų buvo grąžinta reikšmė pagal naujas mazgas

739
01:00:27,130 --> 01:00:33,410
nėra lygus nuliui, nes mes nenorime pradėti pasiekti tą atmintį, jei jis yra niekinis.

740
01:00:33,410 --> 01:00:39,910
Mes galime tai patikrinti, įsitikinti, kad naujas mazgas nėra lygus NULL.

741
01:00:39,910 --> 01:00:42,910
Arba vietoj, mes galime tik pamatyti, jei ji iš tikrųjų yra niekinis,

742
01:00:42,910 --> 01:00:52,120
ir, jei jis yra niekinis, tada mes galime tik gražins false anksti.

743
01:00:52,120 --> 01:00:59,090
>> Šiuo metu, mes turime pervesti naują mazgas į jo tinkamoje vietoje medyje.

744
01:00:59,090 --> 01:01:03,510
Jei pažvelgsime atgal pagrindinis ir, jei mes iš tikrųjų vertybių laidų ir anksčiau,

745
01:01:03,510 --> 01:01:08,470
mes matome, kad tai, kaip mes darome tai, kai mes norėjome įdėti į medį 3

746
01:01:08,470 --> 01:01:11,750
mes buvo atvertas kairįjį vaiką root.

747
01:01:11,750 --> 01:01:14,920
Kai mes įdėti 9 į medį, mes turėjome prieiti prie tos šaknų vaikas.

748
01:01:14,920 --> 01:01:21,030
Mums reikėjo žymiklį į tėvų, siekiant pradėti taikyti naują vertę į medį.

749
01:01:21,030 --> 01:01:24,430
SCROLLING Atgal į viršų įterpti, kad nesiruošia gana dirbti čia

750
01:01:24,430 --> 01:01:27,550
nes mes neturime patronuojanti žymeklį.

751
01:01:27,550 --> 01:01:31,650
Ką mes norime, kad būtų galima tai padaryti, yra šiuo metu,

752
01:01:31,650 --> 01:01:37,080
patikrinti tėvų vertę ir pamatyti, - gerai, GOSH,

753
01:01:37,080 --> 01:01:41,990
jei patronuojančios įmonės turto vertė yra mažesnė nei dabartinės vertės,

754
01:01:41,990 --> 01:01:54,440
tėvų teisė Vaikas turi būti naujas mazgas;

755
01:01:54,440 --> 01:02:07,280
kitaip, kairėje tėvų vaikas turėtų būti naujas mazgas.

756
01:02:07,280 --> 01:02:10,290
Tačiau, mes ne turėti šią patronuojančią žymeklį gana dar.

757
01:02:10,290 --> 01:02:15,010
>> Tam, kad jį gauti, mes iš tikrųjų ketiname jį sekti, kaip mes einame per medžio

758
01:02:15,010 --> 01:02:18,440
ir rasti tinkamą mūsų kilpa virš vietoje.

759
01:02:18,440 --> 01:02:26,840
Mes galime padaryti, kad slinkimo atgal iki mūsų įterpti funkciją viršuje

760
01:02:26,840 --> 01:02:32,350
ir stebėjimo kitą žymiklio kintamasis vadinamas tėvų.

761
01:02:32,350 --> 01:02:39,340
Mes ketiname nustatyti, kad jis lygus nulis pradžių,

762
01:02:39,340 --> 01:02:43,640
ir tada kiekvieną kartą, mes einame per medžio,

763
01:02:43,640 --> 01:02:51,540
mes ketiname nustatyti tėvų žymeklį, kad atitiktų esamą žymeklį.

764
01:02:51,540 --> 01:02:59,140
Nustatyti tėvų lygią dab.

765
01:02:59,140 --> 01:03:02,260
Tokiu būdu, kiekvieną kartą, mes einame per

766
01:03:02,260 --> 01:03:05,550
mes ketiname užtikrinti, kad, kaip dabartinę poziciją gauna padidinamas

767
01:03:05,550 --> 01:03:12,640
patronuojanti rodyklė taip - tik vienas lygis didesnis nei dabartinis rodyklė medyje.

768
01:03:12,640 --> 01:03:17,370
Kad visi atrodo gana gerai.

769
01:03:17,370 --> 01:03:22,380
>> Manau, kad vienas dalykas, kad mes norite reguliuoti tai sukurti mazgas grįžtantį null.

770
01:03:22,380 --> 01:03:25,380
Siekiant gauti statyti mazgas sėkmingai grąžina NULL,

771
01:03:25,380 --> 01:03:31,060
mes turime pakeisti tą kodą,

772
01:03:31,060 --> 01:03:37,270
nes čia, mes niekada išbandyti, įsitikinti, kad malloc grąžino galiojantį žymeklį.

773
01:03:37,270 --> 01:03:53,390
Taigi, jei (n = NULL), tada -

774
01:03:53,390 --> 01:03:55,250
jei malloc grąžino galiojantį žymeklį, tada mes inicijuoti;

775
01:03:55,250 --> 01:04:02,540
kitaip, mes tiesiog grįžti ir, galų gale grįžta null mums.

776
01:04:02,540 --> 01:04:13,050
Dabar viskas atrodo gana gera. Galime padaryti, kad tai iš tikrųjų kaupia.

777
01:04:13,050 --> 01:04:22,240
Padaryti dvejetainis medis, ir oh, mes turime kai kurių dalykų čia vyksta.

778
01:04:22,240 --> 01:04:29,230
>> Mes turime numanoma deklaracija funkcija kurti mazgas.

779
01:04:29,230 --> 01:04:31,950
Vėlgi, šių kompiliatorius, mes ketiname pradėti viršuje.

780
01:04:31,950 --> 01:04:36,380
Kas, kad turi reikšti, kad vadinu sukurti mazgas, aš iš tikrųjų paskelbė jį.

781
01:04:36,380 --> 01:04:37,730
Eikime vėl į kodą tikrai greitai.

782
01:04:37,730 --> 01:04:43,510
Slinkti žemyn, ir tikrai pakankamai, mano įterpti funkciją pareiškė

783
01:04:43,510 --> 01:04:47,400
virš build mazgo funkciją,

784
01:04:47,400 --> 01:04:50,070
bet aš bandau naudoti kurti mazgas viduje įdėklu.

785
01:04:50,070 --> 01:05:06,610
Aš ruošiuosi eiti ir kopiją - ir tada įklijuokite statyti mazgas funkcija čia viršuje.

786
01:05:06,610 --> 01:05:11,750
Kad taip, tikiuosi, kad veiks. Leiskite duoti kitą eiti.

787
01:05:11,750 --> 01:05:18,920
Dabar visa tai rengia. Viskas yra gerai.

788
01:05:18,920 --> 01:05:21,640
>> Tačiau šiuo metu, mes ne iš tikrųjų vadinamas mūsų įterpti funkciją.

789
01:05:21,640 --> 01:05:26,510
Mes tiesiog žinau, kad ji rengia, tad eikime ir įdėti kelis skambučius in

790
01:05:26,510 --> 01:05:28,240
Darykime, kad mūsų pagrindinė funkcija.

791
01:05:28,240 --> 01:05:32,390
Čia mes komentavo, 5, 8 ir 2,

792
01:05:32,390 --> 01:05:36,680
ir tada mes ne vielos juos čia.

793
01:05:36,680 --> 01:05:41,640
Galime padaryti, kai ragina įterpti,

794
01:05:41,640 --> 01:05:46,440
ir tegul taip pat naudoti tos pačios rūšies daiktų, kad mes naudojamas

795
01:05:46,440 --> 01:05:52,810
, kai mes padarėme šias printf ragina įsitikinti, kad viskas buvo gauti įdėta tinkamai.

796
01:05:52,810 --> 01:06:00,550
Aš ruošiuosi kopijuoti ir įklijuoti,

797
01:06:00,550 --> 01:06:12,450
ir vietoj yra, mes ketiname padaryti įdėklą.

798
01:06:12,450 --> 01:06:30,140
Ir vietoj 6, 10 ir 1, mes ketiname naudoti 5, 8 ir 2.

799
01:06:30,140 --> 01:06:37,320
Tai turėtų tikiuosi įterpti 5, 8 ir 2 į medį.

800
01:06:37,320 --> 01:06:44,050
Surinkti. Viskas yra gerai. Dabar mes iš tikrųjų paleisti mūsų programą.

801
01:06:44,050 --> 01:06:47,330
>> Viskas grįžo klaidinga.

802
01:06:47,330 --> 01:06:53,830
Taigi, 5, 8 ir 2 ne eiti, ir atrodo, kad Contains nerado arba.

803
01:06:53,830 --> 01:06:58,890
Kas vyksta? Leiskite nutolinti.

804
01:06:58,890 --> 01:07:02,160
Pirmoji problema buvo, kad įterpti atrodė, kad gražins false,

805
01:07:02,160 --> 01:07:08,750
ir atrodo, kaip tai todėl, kad mes palikome mūsų Return FALSE skambučio,

806
01:07:08,750 --> 01:07:14,590
ir mes niekada iš tikrųjų grįžo tiesa.

807
01:07:14,590 --> 01:07:17,880
Mes galime nustatyti, kad iki.

808
01:07:17,880 --> 01:07:25,290
Antroji problema yra, dabar, net jei mes darome - išsaugoti, mesti,

809
01:07:25,290 --> 01:07:34,530
paleisti, kad vėl, tai kaupti, tada paleiskite ją -

810
01:07:34,530 --> 01:07:37,670
matome, kad kažkas čia nutiko.

811
01:07:37,670 --> 01:07:42,980
5, 8, ir 2 buvo dar niekada nebuvo rasta medyje.

812
01:07:42,980 --> 01:07:44,350
Taigi, kas vyksta?

813
01:07:44,350 --> 01:07:45,700
>> Paimkime pažiūrėk kode.

814
01:07:45,700 --> 01:07:49,790
Leiskite pamatyti, jei mes galime suprasti tai.

815
01:07:49,790 --> 01:07:57,940
Mes pradedame su patronuojanti nėra null.

816
01:07:57,940 --> 01:07:59,510
Mes nustatyti dabartinę žymeklį prilygstantį į šakninį rodyklė,

817
01:07:59,510 --> 01:08:04,280
ir mes ketiname dirbti savo kelią žemyn per medžio.

818
01:08:04,280 --> 01:08:08,650
Jei dabartinė mazgas nėra lygus nuliui, tada mes žinome, kad galime perkelti šiek tiek.

819
01:08:08,650 --> 01:08:12,330
Mes nustatome mūsų tėvų žymeklį turi būti lygus su dabartine rodyklė,

820
01:08:12,330 --> 01:08:15,420
patikrinti vertę, jei vertybės yra tos pačios, mes grįžo klaidinga.

821
01:08:15,420 --> 01:08:17,540
Jeigu vertės yra mažesnės, mes persikėlė į dešinę;

822
01:08:17,540 --> 01:08:20,399
kitaip, mes persikėlė į kairę.

823
01:08:20,399 --> 01:08:24,220
Tada mes sukurti mazgas. Aš padidinti šiek tiek.

824
01:08:24,220 --> 01:08:31,410
Ir čia mes ketiname pabandyti pervesti vertybes, yra tas pats.

825
01:08:31,410 --> 01:08:37,250
Kas vyksta? Leiskite pamatyti, jei galbūt Valgrind gali duoti užuominą.

826
01:08:37,250 --> 01:08:43,910
>> Man patinka naudoti Valgrind tik todėl, kad Valgrind tikrai greitai veikia

827
01:08:43,910 --> 01:08:46,729
ir jums pasakys, jei yra kokių nors atminties klaidos.

828
01:08:46,729 --> 01:08:48,300
Kai mes paleisti Valgrind kodą,

829
01:08:48,300 --> 01:08:55,859
kaip matote teisę here--Valgrind./binary_tree--and paspauskite Enter.

830
01:08:55,859 --> 01:09:03,640
Jūs matote, kad mes neturėjo atminties klaidos, todėl atrodo, kad viskas bus gerai iki šiol.

831
01:09:03,640 --> 01:09:07,529
Mes turime kai kuriuos atminties nutekėjimas, kurį mes žinome, nes mes ne

832
01:09:07,529 --> 01:09:08,910
vyksta išlaisvinti mūsų mazgų.

833
01:09:08,910 --> 01:09:13,050
Pabandykime veikia GDB pamatyti, kas iš tikrųjų vyksta.

834
01:09:13,050 --> 01:09:20,010
Mes padarysime gdb / binary_tree. Jis įkrautas iki tik baudą.

835
01:09:20,010 --> 01:09:23,670
Leiskite nustatyti pertraukos tašką įdėklu.

836
01:09:23,670 --> 01:09:28,600
Leiskite paleisti.

837
01:09:28,600 --> 01:09:31,200
Atrodo, kad mes niekada iš tikrųjų vadinamas įterpti.

838
01:09:31,200 --> 01:09:39,410
Atrodo, kad problema buvo tik tai, kad, kai aš pakeičiau čia pagrindinis -

839
01:09:39,410 --> 01:09:44,279
šių printf skambučių iš yra

840
01:09:44,279 --> 01:09:56,430
Aš niekada iš tikrųjų pasikeitė, skambinti įdėklą.

841
01:09:56,430 --> 01:10:01,660
Dabar tegul give it a try. Leiskite sudaryti.

842
01:10:01,660 --> 01:10:09,130
Viskas atrodo gerai. Dabar pabandykime paleisti jį, pamatyti, kas atsitiks.

843
01:10:09,130 --> 01:10:13,320
Sutinku! Viskas atrodo gana gerai ten.

844
01:10:13,320 --> 01:10:18,130
>> Galutinis dalykas, galvoti apie tai, ar yra kokių nors krašto atvejai intarpu?

845
01:10:18,130 --> 01:10:23,170
Ir paaiškėja, kad gerai, vienu kraštu, kad visada yra įdomu galvoti apie

846
01:10:23,170 --> 01:10:26,250
tai, kas atsitinka, jei jūsų medis yra tuščia ir skambinate šį įterpti funkciją?

847
01:10:26,250 --> 01:10:30,330
Ar jis veikia? Ką gi, give it a try.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c -

849
01:10:32,110 --> 01:10:35,810
Taip, kaip mes ketiname išbandyti šį, mes ketiname eiti į mūsų pagrindinė funkcija,

850
01:10:35,810 --> 01:10:41,690
ir, o ne laidų Šie mazgai panašaus į tai,

851
01:10:41,690 --> 01:10:56,730
mes tik ketina komentaras iš visą dalykas,

852
01:10:56,730 --> 01:11:02,620
ir vietoj mazgų save laidus,

853
01:11:02,620 --> 01:11:09,400
mes iš tikrųjų galite tiesiog eiti į priekį ir trinti visa tai.

854
01:11:09,400 --> 01:11:17,560
Mes ketiname, kad viskas pokalbį įterpti.

855
01:11:17,560 --> 01:11:49,020
Taigi, galime daryti - vietoj 5, 8 ir 2, mes ketiname įterpti 7, 3, ir 9.

856
01:11:49,020 --> 01:11:58,440
Ir tada mes taip pat norite įterpti 6, taip pat.

857
01:11:58,440 --> 01:12:05,190
Įrašyti. Baigti. Padaryti dvejetainis medis.

858
01:12:05,190 --> 01:12:08,540
Visa tai rengia.

859
01:12:08,540 --> 01:12:10,320
Mes galime tiesiog paleisti jį ir pamatyti, kas atsitiks,

860
01:12:10,320 --> 01:12:12,770
tačiau ji taip pat bus tikrai svarbu įsitikinti, kad

861
01:12:12,770 --> 01:12:14,740
mes neturime jokių atminties klaidų,

862
01:12:14,740 --> 01:12:16,840
, nes tai yra vienas iš mūsų krašto atvejų, kad mes žinome apie.

863
01:12:16,840 --> 01:12:20,150
>> Leiskite įsitikinkite, kad jis veikia gerai, pagal Valgrind

864
01:12:20,150 --> 01:12:28,310
kuriuos mes tiesiog veikia Valgrind / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Atrodo, kad mes iš tikrųjų turi vieną klaidą iš vieno konteksto -

866
01:12:31,110 --> 01:12:33,790
mes turime šį segmentavimo kaltės.

867
01:12:33,790 --> 01:12:36,690
Kas atsitiko?

868
01:12:36,690 --> 01:12:41,650
Valgrind tikrųjų mums sako, kur ji yra.

869
01:12:41,650 --> 01:12:43,050
Šiek tiek nutolinti.

870
01:12:43,050 --> 01:12:46,040
Atrodo, kad jis vyksta mūsų įterpti funkciją,

871
01:12:46,040 --> 01:12:53,420
kur mes turime neteisingą paskaityti dydis 4 įdėklo, eilutė 60.

872
01:12:53,420 --> 01:13:03,590
Eikime atgal ir pamatyti, kas čia vyksta.

873
01:13:03,590 --> 01:13:05,350
Nutolinti tikrai greitai.

874
01:13:05,350 --> 01:13:14,230
Noriu įsitikinti, kad jis neturi eiti į ekrano kraštą, kad mes galime pamatyti viską.

875
01:13:14,230 --> 01:13:18,760
Traukti, kad šiek tiek. Alright.

876
01:13:18,760 --> 01:13:35,030
Slinkti žemyn, ir problema yra čia.

877
01:13:35,030 --> 01:13:40,120
Kas atsitiks, jei mes ir mūsų dabartinis mazgas yra jau null,

878
01:13:40,120 --> 01:13:44,010
mūsų pagrindinė mazgas yra nulis, todėl, jei mes ieškoti pačiame viršuje, čia -

879
01:13:44,010 --> 01:13:47,340
jei tai while cikle niekada faktiškai vykdo

880
01:13:47,340 --> 01:13:52,330
nes mūsų dabartinė vertė yra niekinis - mūsų šaknis yra niekinis, todėl dab yra niekinis -

881
01:13:52,330 --> 01:13:57,810
tada mūsų tėvų niekada pasireiškia dabartiniu arba galiojantį vertės,

882
01:13:57,810 --> 01:14:00,580
taip, tėvai taip pat turi būti nulinis.

883
01:14:00,580 --> 01:14:03,700
Mes turime prisiminti, siekiant patikrinti, ar

884
01:14:03,700 --> 01:14:08,750
iki to laiko mes kibti čia, ir mes pradedame gauti tėvų vertę.

885
01:14:08,750 --> 01:14:13,190
Taigi, kas atsitinka? Na, jei vienas iš tėvų yra niekinis -

886
01:14:13,190 --> 01:14:17,990
if (patronuojanti == NULL) - tada mes žinome,

887
01:14:17,990 --> 01:14:19,530
ten neturi būti nieko į medį.

888
01:14:19,530 --> 01:14:22,030
Mes turime būti bando įterpti jį į šaknis.

889
01:14:22,030 --> 01:14:32,570
Mes galime padaryti, kad tiesiog šaknis lygi į naujas mazgas.

890
01:14:32,570 --> 01:14:40,010
Tada šiuo metu, mes ne iš tikrųjų nori eiti per šių kitų dalykų.

891
01:14:40,010 --> 01:14:44,780
Vietoj to, čia, mes galime nors kitur, jei dar,

892
01:14:44,780 --> 01:14:47,610
ar mes galime derinti viską, čia dar,

893
01:14:47,610 --> 01:14:56,300
bet čia mes tiesiog naudoti kitur, ir tai padaryti, kad taip.

894
01:14:56,300 --> 01:14:59,030
Dabar mes ketiname išbandyti, ar gerai, kad mūsų tėvų nėra lygus nuliui

895
01:14:59,030 --> 01:15:02,160
iki to laiko iš tikrųjų bando prieiti prie savo laukus.

896
01:15:02,160 --> 01:15:05,330
Tai padės mums išvengti segmentavimo kaltės.

897
01:15:05,330 --> 01:15:14,740
Taigi, mes mesti, nutolinti, kaupti, paleisti.

898
01:15:14,740 --> 01:15:18,130
>> Jokių klaidų, tačiau mes vis dar turime krūva atminties nutekėjimas

899
01:15:18,130 --> 01:15:20,650
nes mes ne nemokamai bet mūsų mazgų.

900
01:15:20,650 --> 01:15:24,350
Tačiau, jei mes einame čia ir mes pažvelgti į mūsų spausdintoje medžiagoje,

901
01:15:24,350 --> 01:15:30,880
matome, kad gerai, atrodo, kad visi mūsų intarpais grįžta tiesa, kuri yra gera.

902
01:15:30,880 --> 01:15:33,050
Įdėklai yra tiesa,

903
01:15:33,050 --> 01:15:36,670
, o po to atitinkami Contains ragina taip pat tiesa.

904
01:15:36,670 --> 01:15:41,510
>> Puikus darbas! Atrodo, kad mes sėkmingai parašyta įdėklą.

905
01:15:41,510 --> 01:15:47,430
Štai ir viskas, mes turime šią savaitę problemą, specifikaciją.

906
01:15:47,430 --> 01:15:51,720
Vienas įdomus iššūkis, galvoti apie tai, kaip jūs iš tikrųjų eiti į

907
01:15:51,720 --> 01:15:55,340
ir nemokamai visus šio medžio mazgų.

908
01:15:55,340 --> 01:15:58,830
Mes galime tai padaryti daug įvairių būdų,

909
01:15:58,830 --> 01:16:01,930
bet aš palikti, kad iki jums eksperimentuoti,

910
01:16:01,930 --> 01:16:06,080
ir kaip įdomus iššūkis, pabandykite ir įsitikinkite, kad jūs galite įsitikinti,

911
01:16:06,080 --> 01:16:09,490
,, kad ši Valgrind ataskaita vėl jokių klaidų ir nėra nuotėkio.

912
01:16:09,490 --> 01:16:12,880
>> Sėkmės šią savaitę Hafmano kodavimo problema rinkinys,

913
01:16:12,880 --> 01:16:14,380
ir mes Pasimatysime kitą savaitę!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]