1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [7. szakasz: További Kényelmes]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard Egyetem]

3
00:00:05,090 --> 00:00:07,930
[Ez CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Rendben van. Szóval, mint mondtam az én e-mail,

5
00:00:10,110 --> 00:00:14,060
ez lesz egy bináris-fa-intenzív szakasz.

6
00:00:14,060 --> 00:00:16,820
De nincs sok kérdés.

7
00:00:16,820 --> 00:00:18,920
Szóval megyünk próbálni, és dolgozzon ki minden kérdésre

8
00:00:18,920 --> 00:00:25,430
és bemegy fájdalmas részletesen minden a legjobb módja a dolgok.

9
00:00:25,430 --> 00:00:31,200
Így rögtön az elején, mi megy keresztül mintán rajzok bináris fák, meg ilyesmi.

10
00:00:31,200 --> 00:00:35,970
Tehát itt, "Emlékezz arra, hogy a bináris fa van csomópont hasonló csatolt lista

11
00:00:35,970 --> 00:00:38,150
kivéve egy helyett két mutató: az egyik a bal oldali "gyermek"

12
00:00:38,150 --> 00:00:41,950
és egy a jobb "gyermek". "

13
00:00:41,950 --> 00:00:45,630
Tehát egy bináris fa olyan, mint egy láncolt lista,

14
00:00:45,630 --> 00:00:47,910
kivéve a struct lesz két mutató.

15
00:00:47,910 --> 00:00:51,390
Van trinary fákat, amelyek majd három mutató,

16
00:00:51,390 --> 00:00:56,540
vannak N-áris fák, amelyek csak egy általános mutató

17
00:00:56,540 --> 00:01:00,320
hogy majd kell malloc nem elégséges ahhoz, hogy a

18
00:01:00,320 --> 00:01:04,840
elegendő mutatókat valamennyi a lehetséges gyermek.

19
00:01:04,840 --> 00:01:08,200
Így bináris fa épp, hogy egy állandó számú kettő.

20
00:01:08,200 --> 00:01:11,260
Ha azt szeretné, hogy egy láncolt lista, mint egy egyváltozós fa,

21
00:01:11,260 --> 00:01:15,360
de nem hiszem, hogy bárki nevezi ezt.

22
00:01:15,360 --> 00:01:18,060
"Rajzolj egy doboz-és-nyilak diagram egy bináris fa csomópont

23
00:01:18,060 --> 00:01:24,110
tartalmazó Nate kedvenc száma, 7, ahol minden gyermek mutató null. "

24
00:01:24,110 --> 00:01:27,780
Szóval iPad mód.

25
00:01:27,780 --> 00:01:30,280
>> Ez lesz nagyon egyszerű.

26
00:01:30,280 --> 00:01:36,150
Mi csak megy, hogy egy csomópont, fogom felhívni, mint egy négyzet.

27
00:01:36,150 --> 00:01:38,730
És én felhívni az értékek itt.

28
00:01:38,730 --> 00:01:41,090
Tehát ez az érték megy itt,

29
00:01:41,090 --> 00:01:44,770
majd le itt lesz a bal oldali kurzort a bal és a jobb mutatót a jobb oldalon.

30
00:01:44,770 --> 00:01:50,430
És ez nagyon is egyezményt hívni balra és jobbra, a mutató nevek.

31
00:01:50,430 --> 00:01:52,460
Mindkét lesznek null.

32
00:01:52,460 --> 00:01:57,870
Ez csak úgy lesz a null, és ez csak úgy lesz a null.

33
00:01:57,870 --> 00:02:03,630
Oké. Tehát vissza ide.

34
00:02:03,630 --> 00:02:05,700
"A láncolt lista, csak kellett tárolni egy mutató

35
00:02:05,700 --> 00:02:09,639
Az első csomópont a lista, hogy emlékezzen a teljes láncolt lista, vagy az egész listát.

36
00:02:09,639 --> 00:02:11,650
Hasonlóképpen, a fák, csak el kell tárolni egy mutató

37
00:02:11,650 --> 00:02:13,420
egyetlen node annak érdekében, hogy emlékezzen az egész fa.

38
00:02:13,420 --> 00:02:15,980
Ez a csomópont calle a 'root' a fa.

39
00:02:15,980 --> 00:02:18,320
Építsd fel a diagram előtti vagy rajzolj egy újat

40
00:02:18,320 --> 00:02:21,690
úgy, hogy van egy doboz-és nyilak ábrázolása egy bináris fa

41
00:02:21,690 --> 00:02:25,730
az az érték 7, majd a 3-ban a bal,

42
00:02:25,730 --> 00:02:32,760
akkor 9 a jobb oldalon, majd a jobb oldalon 6 a 3 ".

43
00:02:32,760 --> 00:02:34,810
Lássuk emlékszem minden, hogy a fejemben.

44
00:02:34,810 --> 00:02:37,670
Szóval ez lesz a mi gyökér itt.

45
00:02:37,670 --> 00:02:41,600
Majd néhány mutató valahol, valami, hívjuk root,

46
00:02:41,600 --> 00:02:45,140
és ez mutató ezt a fickót.

47
00:02:45,140 --> 00:02:48,490
Most, hogy egy új csomópont,

48
00:02:48,490 --> 00:02:52,870
mi van, 3 a bal oldalon?

49
00:02:52,870 --> 00:02:57,140
Tehát egy új csomópontot, 3, és ez kezdetben mutat null.

50
00:02:57,140 --> 00:02:59,190
Én az imént N.

51
00:02:59,190 --> 00:03:02,250
Most szeretnénk, hogy győződjön meg, hogy menjen balra 7.

52
00:03:02,250 --> 00:03:06,840
Tehát változtatni ez a mutató, hogy most pont ezzel a fickóval.

53
00:03:06,840 --> 00:03:12,420
És mi nem ugyanaz. Szeretnénk egy 9 ide

54
00:03:12,420 --> 00:03:14,620
amely kezdetben csak mondja null.

55
00:03:14,620 --> 00:03:19,600
Mi fog változni ez a mutató, mutasson a 9,

56
00:03:19,600 --> 00:03:23,310
és most szeretnénk, hogy 6 a jobb a 3.

57
00:03:23,310 --> 00:03:32,170
Szóval ez lesz -, hogy a 6.

58
00:03:32,170 --> 00:03:34,310
És ez a fickó pont ott.

59
00:03:34,310 --> 00:03:38,320
Oké. Szóval ez az egész azt kéri tőlünk.

60
00:03:38,320 --> 00:03:42,770
>> Most menjünk át néhány terminológiát.

61
00:03:42,770 --> 00:03:46,690
Már beszéltünk arról, hogy a gyökér a fa a legfelső csomópont a fában.

62
00:03:46,690 --> 00:03:54,720
Az egyik, mely 7. A csomópontok alján a fa nevezzük a leveleket.

63
00:03:54,720 --> 00:04:01,240
Minden olyan csomópont, amely csak azt, null, mint a gyermekek egy levél.

64
00:04:01,240 --> 00:04:03,680
Így lehetséges, ha a bináris fa csak egy csomópont,

65
00:04:03,680 --> 00:04:10,130
hogy a fa egy levél, és ennyi.

66
00:04:10,130 --> 00:04:12,060
"A" magassága "a fa az ugrások számát meg kell tenni

67
00:04:12,060 --> 00:04:16,620
hogy a felső a levél. "

68
00:04:16,620 --> 00:04:18,640
Fogunk bejutni, a második, a különbség

69
00:04:18,640 --> 00:04:21,940
között kiegyensúlyozott és kiegyensúlyozatlan bináris fák,

70
00:04:21,940 --> 00:04:29,470
de most, a teljes magassága a fa

71
00:04:29,470 --> 00:04:34,520
Azt mondanám, hogy a 3, de ha számít az ugrások számát

72
00:04:34,520 --> 00:04:39,710
meg kell tenni annak érdekében, hogy 9, akkor ez tényleg csak a magassága, 2.

73
00:04:39,710 --> 00:04:43,340
Most ez egy kiegyensúlyozatlan bináris fa,

74
00:04:43,340 --> 00:04:49,840
de mi beszéltünk kiegyensúlyozott amikor megkapja relevánsnak.

75
00:04:49,840 --> 00:04:52,040
Tehát most beszélhetünk csomópontok egy fa szempontjából

76
00:04:52,040 --> 00:04:54,700
képest más csomópontok a fán.

77
00:04:54,700 --> 00:04:59,730
Így most már a szülők, gyermekek, testvérek, ősök és leszármazottak.

78
00:04:59,730 --> 00:05:05,650
Ezek elég a józan ész, hogy mit jelent.

79
00:05:05,650 --> 00:05:09,610
Ha azt kérdezzük - ez a szülők.

80
00:05:09,610 --> 00:05:12,830
Tehát mi a szülő a 3?

81
00:05:12,830 --> 00:05:16,090
[Diákok] 7. >> Igen. A szülő csak lesz, amit mutat az Ön számára.

82
00:05:16,090 --> 00:05:20,510
Akkor mi a gyermekei 7?

83
00:05:20,510 --> 00:05:23,860
[Diákok] 3 és 9. >> Igen.

84
00:05:23,860 --> 00:05:26,460
Figyeljük meg, hogy a "gyermek" szó szerint azt jelenti gyermekek,

85
00:05:26,460 --> 00:05:31,010
így a 6. nem kell alkalmazni, mert ez olyan, mint egy unoka.

86
00:05:31,010 --> 00:05:35,540
De aztán, ha megyünk leszármazottai, tehát mi a leszármazottai 7?

87
00:05:35,540 --> 00:05:37,500
[Hallgatók] 3, 6 és 9. >> Igen.

88
00:05:37,500 --> 00:05:42,330
A leszármazottai a gyökér csomópont lesz mindent a fa,

89
00:05:42,330 --> 00:05:47,950
kivéve talán a gyökér csomópont is, ha nem akarja, hogy fontolja meg, hogy egy leszármazottja.

90
00:05:47,950 --> 00:05:50,750
És végül, ősök, így az ellenkező irányba.

91
00:05:50,750 --> 00:05:55,740
Tehát mi az ősei 6?

92
00:05:55,740 --> 00:05:58,920
[Diákok] 3 és 7. >> Igen. 9 nem tartalmazza.

93
00:05:58,920 --> 00:06:02,520
Ez csak a közvetlen vonal vissza a gyökér

94
00:06:02,520 --> 00:06:13,230
lesz az ősei.

95
00:06:13,230 --> 00:06:16,300
>> "Azt mondjuk, hogy a bináris fa" megrendelt ", ha minden egyes csomópont a fában,

96
00:06:16,300 --> 00:06:19,530
valamennyi leszármazottai, a bal oldalon van kisebb értékek

97
00:06:19,530 --> 00:06:22,890
és az összes közül a jobb oldalon nagyobb értékeket.

98
00:06:22,890 --> 00:06:27,060
Például a fa fenti sorrendben, de ez nem az egyetlen lehetséges megrendelt megállapodás. "

99
00:06:27,060 --> 00:06:30,180
Mielőtt nekilátnánk az, hogy a

100
00:06:30,180 --> 00:06:36,420
rendezett bináris fa is ismert, mint egy bináris keresési fa.

101
00:06:36,420 --> 00:06:38,660
Itt történik meg kell nevezni egy rendezett bináris fa,

102
00:06:38,660 --> 00:06:41,850
de én még soha nem hallottam, hogy úgynevezett sorrendben bináris fa előtt,

103
00:06:41,850 --> 00:06:46,650
és egy kvíz vagyunk sokkal valószínűbb, hogy terjesszen bináris keresési fa.

104
00:06:46,650 --> 00:06:49,250
Ők egy és ugyanaz,

105
00:06:49,250 --> 00:06:54,580
és ez fontos, hogy ismeri a különbséget a bináris fa és bináris keresési fa.

106
00:06:54,580 --> 00:06:58,830
A bináris fa csak egy fa, amely rámutat arra, hogy két dolgot.

107
00:06:58,830 --> 00:07:02,120
Minden csomópont mutat két dolgot.

108
00:07:02,120 --> 00:07:06,310
Nincs érvelés az értékeket, hogy mutat.

109
00:07:06,310 --> 00:07:11,370
Tehát mint ide, mivel ez egy bináris keresési fa,

110
00:07:11,370 --> 00:07:14,030
tudjuk, hogy ha megyünk balra 7,

111
00:07:14,030 --> 00:07:16,670
akkor az összes értéket, hogy mi lehet esetleg elérni

112
00:07:16,670 --> 00:07:19,310
mellett haladó bal 7 már, hogy kevésbé, mint 7.

113
00:07:19,310 --> 00:07:24,070
Figyeljük meg, hogy minden az érték kisebb, mint 7 Összesen 3 és 6.

114
00:07:24,070 --> 00:07:26,040
Ezek mind a bal oldalon 7.

115
00:07:26,040 --> 00:07:29,020
Ha elmegyünk jobbra 7, mindennek nagyobb, mint 7,

116
00:07:29,020 --> 00:07:33,220
így a 9. jobbra 7, tehát vagyunk jó.

117
00:07:33,220 --> 00:07:36,150
Ez nem az eset egy bináris fa,

118
00:07:36,150 --> 00:07:40,020
a rendszeres bináris fa tudjuk csak van 3 a tetején, 7 balra,

119
00:07:40,020 --> 00:07:47,630
9 balra 7, nincs rendelési értékek nélkül.

120
00:07:47,630 --> 00:07:56,140
Nos, akkor valójában nem ezt, mert unalmas és felesleges,

121
00:07:56,140 --> 00:07:59,400
de "próbálja felhívni annyi Beszerezzük fák tudsz gondolni

122
00:07:59,400 --> 00:08:01,900
használatával a számok 7, 3, 9, és 6.

123
00:08:01,900 --> 00:08:06,800
Hány különböző szabályok vannak? Mi a magassága mindegyik? "

124
00:08:06,800 --> 00:08:10,480
>> Majd csinál egy pár, de az alapötlet az,

125
00:08:10,480 --> 00:08:16,530
ez semmiképpen sem egy egyedülálló ábrázolása egy bináris fa tartalmazó ezeket az értékeket.

126
00:08:16,530 --> 00:08:22,760
Már csak néhány bináris fa, amely 7, 3, 6, és 9.

127
00:08:22,760 --> 00:08:25,960
Egy másik lehetséges érvényesnek lenne a gyökér 3,

128
00:08:25,960 --> 00:08:30,260
menj a balra és ez 6, menj balra, és ez 7,

129
00:08:30,260 --> 00:08:32,730
menj a balra és ez 9.

130
00:08:32,730 --> 00:08:36,169
Ez egy teljesen érvényes bináris keresési fa.

131
00:08:36,169 --> 00:08:39,570
Ez nem túl hasznos, mert olyan, mint egy láncolt lista

132
00:08:39,570 --> 00:08:43,750
és mind ezek pointerek csak nulla.

133
00:08:43,750 --> 00:08:48,900
De ez egy érvényes fa. Igen?

134
00:08:48,900 --> 00:08:51,310
[Student] Nem az értékek nagyobb lesz a jobb?

135
00:08:51,310 --> 00:08:56,700
Vagy ez -? Ezek >> akartam menni a másik irányba.

136
00:08:56,700 --> 00:09:00,960
Ott is - igen, hadd kapcsolja azt.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Jó fogás.

138
00:09:07,770 --> 00:09:11,730
Azt még meg kell engedelmeskedni, amit egy bináris fa keresés kéne csinálni.

139
00:09:11,730 --> 00:09:15,650
Tehát minden balra is kisebb lesz, mint bármelyik adott csomópont.

140
00:09:15,650 --> 00:09:23,180
Mi is csak mozogni, mondjuk, ezt a 6 és tedd ide.

141
00:09:23,180 --> 00:09:26,880
Nem, nem tudjuk. Miért csinálom ezt?

142
00:09:26,880 --> 00:09:35,350
Csináljuk - itt 6, itt 7, 6 pont 3-ra.

143
00:09:35,350 --> 00:09:39,290
Ez még mindig egy érvényes bináris kereső fa.

144
00:09:39,290 --> 00:09:49,260
Mi lehet a baj, ha én - lássuk, ha tudok jönni egy megállapodás.

145
00:09:49,260 --> 00:09:52,280
Ja, oké. Szóval, mi a baj ezzel a fa?

146
00:09:52,280 --> 00:10:08,920
Azt hiszem, már adott egy tippet, hogy valami baj van vele.

147
00:10:08,920 --> 00:10:14,430
Miért csinálom ezt?

148
00:10:14,430 --> 00:10:18,510
Oké. Ez úgy néz ki ésszerű.

149
00:10:18,510 --> 00:10:22,590
Ha megnézzük az egyes csomópont, mint a 7, majd a bal oldalon a 7. 3.

150
00:10:22,590 --> 00:10:24,960
Tehát 3, a dolog, hogy a jog a 3. 6.

151
00:10:24,960 --> 00:10:27,750
És ha megnézi 6, a dolog, hogy a jog a 6. 9.

152
00:10:27,750 --> 00:10:30,910
Akkor miért ez nem érvényes bináris kereső fa?

153
00:10:30,910 --> 00:10:36,330
[Diákok] 9 továbbra is a bal oldalon 7. >> Igen.

154
00:10:36,330 --> 00:10:43,710
Meg kell, hogy igaz legyen, hogy minden értéket akkor esetleg megközelíthető megy a bal 7-kevesebb mint 7.

155
00:10:43,710 --> 00:10:49,120
Ha elmegyünk balra 7, megkapjuk a 3, és mi még mindig 6,

156
00:10:49,120 --> 00:10:52,520
mi még mindig 9, de miután elment kevesebb, mint 7,

157
00:10:52,520 --> 00:10:55,070
nem kellene tudni, hogy egy sor, ami 7-nél nagyobb.

158
00:10:55,070 --> 00:10:59,830
Tehát ez nem érvényes bináris keresési fa.

159
00:10:59,830 --> 00:11:02,330
>> A bátyám tényleg volt egy interjú kérdés

160
00:11:02,330 --> 00:11:07,760
hogy alapvetően ez, csak kódot valamit érvényesíteni

161
00:11:07,760 --> 00:11:10,500
hogy egy fa egy bináris keresési fa,

162
00:11:10,500 --> 00:11:13,580
és így az első dolga volt, csak nézze meg,

163
00:11:13,580 --> 00:11:17,020
ha a bal és jobb helyességét, majd navigálhat odalent.

164
00:11:17,020 --> 00:11:19,700
De nem lehet csak megtenni, meg kell követni

165
00:11:19,700 --> 00:11:22,550
Az a tény, hogy most, hogy elment balra 7,

166
00:11:22,550 --> 00:11:26,340
mindent a részfa kisebbnek kell lennie, mint 7.

167
00:11:26,340 --> 00:11:28,430
A helyes algoritmust kell követni

168
00:11:28,430 --> 00:11:35,970
A határait, hogy az értékek lehet esetleg esik be

169
00:11:35,970 --> 00:11:38,360
Nem megyünk végig őket.

170
00:11:38,360 --> 00:11:41,630
Van egy szép kiújulás kapcsolatban,

171
00:11:41,630 --> 00:11:44,810
bár nem ütött e, vagy mi nem fog ezen,

172
00:11:44,810 --> 00:11:47,030
meghatározza, hogy hány van valójában.

173
00:11:47,030 --> 00:11:53,180
Tehát vannak közülük 14.

174
00:11:53,180 --> 00:11:56,020
Az ötlet, hogy hogyan kellene csinálni, mint matematikailag,

175
00:11:56,020 --> 00:11:59,770
akkor vedd egyetlen egyet a gyökér csomópontot,

176
00:11:59,770 --> 00:12:03,160
és ha vehetem 7, hogy a gyökér csomópont,

177
00:12:03,160 --> 00:12:08,150
akkor van, mondjuk, néhány szám, hogy mehet az én bal csomópont,

178
00:12:08,150 --> 00:12:10,440
és vannak számok, hogy lehet a jobb csomópont,

179
00:12:10,440 --> 00:12:15,090
de ha már n összes számát, akkor az összeg, hogy mehet a bal

180
00:12:15,090 --> 00:12:18,820
plusz az az összeg, lehet menni a jog n - 1.

181
00:12:18,820 --> 00:12:26,130
Így a többi szám, akkor képeseknek kell lenniük, hogy menjen vagy balra vagy jobbra a.

182
00:12:26,130 --> 00:12:31,580
Úgy tűnik, nehéz, hogy ha tettem 3 első, majd mindennek menni balra,

183
00:12:31,580 --> 00:12:35,080
de ha feltettem 7, majd néhány dolog megy a bal és a néhány dolgot lehet menni jobbra.

184
00:12:35,080 --> 00:12:39,570
És '3 első "Úgy értem, mindent lehet menni jobbra.

185
00:12:39,570 --> 00:12:42,350
Ez tényleg, csak meg kell gondolni azt,

186
00:12:42,350 --> 00:12:47,980
mennyi mindent lehet menni a következő szintre a fa.

187
00:12:47,980 --> 00:12:50,420
És ez jön ki, hogy 14, vagy tudod felhívni mindet,

188
00:12:50,420 --> 00:12:54,650
és akkor kapsz 14.

189
00:12:54,650 --> 00:13:01,120
>> Megy vissza,

190
00:13:01,120 --> 00:13:03,510
"Rendezett bináris fák jó, mert tudunk keresni rajtuk keresztül

191
00:13:03,510 --> 00:13:06,910
egy nagyon hasonló módon történő keresést egy rendezett tömbben.

192
00:13:06,910 --> 00:13:10,120
Ehhez kezdjük a gyökér és a munka az utat lefelé a fáról

193
00:13:10,120 --> 00:13:13,440
irányába levelek, ellenőrzése minden csomópont értékek ellen az értékeket fogunk keresni.

194
00:13:13,440 --> 00:13:15,810
Ha az aktuális csomópont értéke kisebb, mint az érték keresünk,

195
00:13:15,810 --> 00:13:18,050
mész mellett a csomópont jobb gyermeke.

196
00:13:18,050 --> 00:13:20,030
Ellenkező esetben, ha megy a csomópont bal gyermekét.

197
00:13:20,030 --> 00:13:22,800
Egy bizonyos ponton, akkor sem találja az értéket, amit keres, vagy akkor befut egy null,

198
00:13:22,800 --> 00:13:28,520
feltüntetve az értéket nem a fán. "

199
00:13:28,520 --> 00:13:32,450
Nekem van, hogy dolgozza át a fa volt azelőtt, hogy elviszem egy pillanatra.

200
00:13:32,450 --> 00:13:38,280
De mi szeretnénk nézni, hogy a 6, 10, és 1 a fán.

201
00:13:38,280 --> 00:13:49,180
Szóval, mi volt, 7, 9, 3, 6. Oké.

202
00:13:49,180 --> 00:13:52,730
A számok szeretnénk nézni, azt akarjuk, hogy felnézzen 6.

203
00:13:52,730 --> 00:13:55,440
Hogyan működik ez az algoritmus működik?

204
00:13:55,440 --> 00:14:03,040
Nos, mi is van néhány gyökér pointer a fa.

205
00:14:03,040 --> 00:14:12,460
És mi megy a gyökér, és azt mondják, ez az érték megegyezik az érték amit keresett?

206
00:14:12,460 --> 00:14:15,000
Tehát keresünk 6, így ez nem egyenlő.

207
00:14:15,000 --> 00:14:20,140
Tehát menj, és most azt mondjuk, rendben, így a 6 kevesebb, mint 7.

208
00:14:20,140 --> 00:14:23,940
Ez azt jelenti, azt akarom, hogy a bal, vagy akarunk menni a jobb?

209
00:14:23,940 --> 00:14:27,340
[Student] Bal. >> Igen.

210
00:14:27,340 --> 00:14:33,340
Ez jelentősen megkönnyítette, mindössze annyit kell tennie, hogy dolgozzon egy lehetséges csomópont a fa

211
00:14:33,340 --> 00:14:37,760
és akkor nem - ahelyett, hogy úgy gondolja, a fejedben,

212
00:14:37,760 --> 00:14:40,020
oké, ha ez kevesebb, akkor megyek a balra vagy menjen jobbra,

213
00:14:40,020 --> 00:14:43,030
csak néztem ezt a képet, nagyon világos, hogy el kell mennem a bal

214
00:14:43,030 --> 00:14:47,700
ha ez a csomópont nagyobb, mint az érték, amit én keresek.

215
00:14:47,700 --> 00:14:52,600
Szóval menj balra, most én vagyok a 3.

216
00:14:52,600 --> 00:14:57,770
Azt akarom, hogy - 3 kisebb, mint az érték keresem, amely 6.

217
00:14:57,770 --> 00:15:03,420
Tehát menj jobbra, és most végül 6,

218
00:15:03,420 --> 00:15:07,380
amelynek az értéke keresem, úgyhogy vissza igaz.

219
00:15:07,380 --> 00:15:15,760
A következő érték fogok keresni a 10.

220
00:15:15,760 --> 00:15:23,230
Oké. Akkor 10, most fog - vágja le, hogy - fogja követni a gyökér.

221
00:15:23,230 --> 00:15:27,670
Most, 10 lesz, 7-nél nagyobb, ezért szeretném, hogy vizsgálja meg a jobb oldalon.

222
00:15:27,670 --> 00:15:31,660
Megyek, hogy jöjjön ide, 10 lesz 9-nél nagyobb,

223
00:15:31,660 --> 00:15:34,520
úgyhogy megyek akarom nézni a jobb oldalon.

224
00:15:34,520 --> 00:15:42,100
Azért jöttem ide, de itt most én vagyok a null.

225
00:15:42,100 --> 00:15:44,170
Mit tegyek, ha megüt null?

226
00:15:44,170 --> 00:15:47,440
[Student] Vissza hamis? >> Igen. Én nem találtam 10.

227
00:15:47,440 --> 00:15:49,800
1 lesz a közel azonos esetben,

228
00:15:49,800 --> 00:15:51,950
kivéve, ez csak lesz tükrözött, ahelyett,

229
00:15:51,950 --> 00:15:56,540
le a jobb oldalon, fogok lenézni a bal oldalon.

230
00:15:56,540 --> 00:16:00,430
>> Most azt gondolom, hogy valóban kap a kódot.

231
00:16:00,430 --> 00:16:04,070
Itt ahol - megnyitja a CS50 készüléket és navigálhat az utat oda,

232
00:16:04,070 --> 00:16:07,010
de akkor is csak csinálni a térben.

233
00:16:07,010 --> 00:16:09,170
Ez talán Ideális kell csinálni a térben,

234
00:16:09,170 --> 00:16:13,760
mert tudunk dolgozni a térben.

235
00:16:13,760 --> 00:16:19,170
"Először is szükségünk lesz egy új típusú meghatározni egy bináris fa csomópontot tartalmazó int értékeket.

236
00:16:19,170 --> 00:16:21,400
A boilerplate typedef alábbi

237
00:16:21,400 --> 00:16:24,510
hozzon létre egy új típus definíció egy csomópont egy bináris fa.

238
00:16:24,510 --> 00:16:27,930
Ha elakad. . . "Bla, bla, bla. Oké.

239
00:16:27,930 --> 00:16:30,380
Szóval fel a boilerplate itt,

240
00:16:30,380 --> 00:16:41,630
typedef struct csomópont, és a csomópont. Ja, oké.

241
00:16:41,630 --> 00:16:44,270
Tehát mi a mezőket fogunk kívánt a csomópont?

242
00:16:44,270 --> 00:16:46,520
[Student] Int, majd két mutató?

243
00:16:46,520 --> 00:16:49,700
Int >> érték, két mutató? Hogyan lehet írni a mutató?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Kéne Nagyítás Igen, struct node * balra,

245
00:16:58,440 --> 00:17:01,320
és struct node * van.

246
00:17:01,320 --> 00:17:03,460
És ne feledd, a vita a múlt idő,

247
00:17:03,460 --> 00:17:15,290
hogy ennek nincs semmi értelme, ennek nincs semmi értelme,

248
00:17:15,290 --> 00:17:18,270
Ennek semmi értelme.

249
00:17:18,270 --> 00:17:25,000
Be kell mindent annak érdekében, hogy meghatározzák e rekurzív struktúra.

250
00:17:25,000 --> 00:17:27,970
Oké, szóval ez az, amit a mi fa fog kinézni.

251
00:17:27,970 --> 00:17:37,670
Ha volt egy trinary fát, majd egy csomópont nézhet b1, b2, struct node * b3,

252
00:17:37,670 --> 00:17:43,470
ahol b egy ága - valójában, már több, hallottam balra, középre, jobbra, de mindegy.

253
00:17:43,470 --> 00:17:55,610
Csak érdekel bináris, ezért jobb, bal.

254
00:17:55,610 --> 00:17:59,110
"Most állapítsa globális node * változót a gyökér a fa."

255
00:17:59,110 --> 00:18:01,510
Szóval nem fogunk csinálni.

256
00:18:01,510 --> 00:18:08,950
Annak érdekében, hogy a dolgok kicsit nehezebbé és generalizált,

257
00:18:08,950 --> 00:18:11,570
nem lesz egy globális csomópont változót.

258
00:18:11,570 --> 00:18:16,710
Ehelyett, a fő fogjuk nyilvánítja minden csomópont dolgokat,

259
00:18:16,710 --> 00:18:20,500
és ez azt jelenti, hogy az alatt, amikor elkezdenek megjelenni

260
00:18:20,500 --> 00:18:23,130
a Tartalom funkciót és a betét funkció,

261
00:18:23,130 --> 00:18:27,410
ahelyett, hogy a Tartalom funkciót csak használ a globális csomópont változó,

262
00:18:27,410 --> 00:18:34,280
megyünk oda, hogy azt tegyen érvként a fa, hogy azt akarjuk, hogy feldolgozni.

263
00:18:34,280 --> 00:18:36,650
Tekintettel a globális változót kellett volna, hogy a dolgok könnyebb.

264
00:18:36,650 --> 00:18:42,310
Megyünk, hogy a dolgok nehezebb.

265
00:18:42,310 --> 00:18:51,210
Most egy percet, vagy úgy, hogy csak ezt a fajta dolog,

266
00:18:51,210 --> 00:18:57,690
ahol a belső fő szeretne létrehozni ezt a fát, és ez minden, amit akarok.

267
00:18:57,690 --> 00:19:04,530
Próbáld ki, és építeni ezt a fát a fő funkciója.

268
00:19:42,760 --> 00:19:47,610
>> Oké. Szóval nem is kell, hogy épített a fa az egész út még.

269
00:19:47,610 --> 00:19:49,840
De bárki valamit tudtam felhúzni

270
00:19:49,840 --> 00:20:03,130
hogy hogyan lehetne kezdeni építése egy ilyen fát?

271
00:20:03,130 --> 00:20:08,080
[Student] Valaki dörömböl, próbál kijutni.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Bárki kényelmes a fa építése?

273
00:20:13,100 --> 00:20:15,520
[Student] Persze. Ez nem történt meg. >> Semmi gond. Mi is csak befejezni -

274
00:20:15,520 --> 00:20:26,860
Ó, tudod menteni? Hurrá.

275
00:20:26,860 --> 00:20:32,020
Tehát itt van - oh, én kicsit vágva.

276
00:20:32,020 --> 00:20:34,770
Én vagyok nagyított?

277
00:20:34,770 --> 00:20:37,730
Nagyítás, lapozzunk ki. >> Lenne egy kérdésem. >> Igen?

278
00:20:37,730 --> 00:20:44,410
[Student] Ha meg struct vannak dolgok, mint inicializálva valamit?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nem >> Oké. Szóval volna inicializálni -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nem Ha meg, vagy ha a struct nyilvánítja,

281
00:20:50,450 --> 00:20:55,600
nem inicializálja alapértelmezés szerint ez ugyanúgy, mint ha állapítsa int.

282
00:20:55,600 --> 00:20:59,020
Ez pontosan ugyanaz a dolog. Ez olyan, mint minden, az egyes területek

283
00:20:59,020 --> 00:21:04,460
lehet egy szemetet értékkel benne. >> És ez lehet határozni - vagy nyilvánítsa a struct

284
00:21:04,460 --> 00:21:07,740
oly módon, hogy ez egyáltalán inicializálni őket?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Igen. Szóval, shortcut inicializálása szintaxis

286
00:21:13,200 --> 00:21:18,660
fog kinézni -

287
00:21:18,660 --> 00:21:22,200
Van két módon meg tudjuk csinálni. Azt hiszem, meg kell fordítani, hogy

288
00:21:22,200 --> 00:21:25,840
hogy győződjön meg arról csenget is teszi ezt.

289
00:21:25,840 --> 00:21:28,510
Az, hogy érvek, hogy jön a struct,

290
00:21:28,510 --> 00:21:32,170
tetted, mint a sorrendben az érvek belül e kapcsos zárójelek.

291
00:21:32,170 --> 00:21:35,690
Tehát, ha szeretné elindítani, hogy a 9. és balra lehet null majd jobb lesz null,

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

293
00:21:41,570 --> 00:21:47,890
Az alternatíva, és a szerkesztő nem tetszik ez a szintaktikai,

294
00:21:47,890 --> 00:21:50,300
és azt hiszi, szeretnék egy új blokk,

295
00:21:50,300 --> 00:22:01,800
de az alternatíva valami hasonló -

296
00:22:01,800 --> 00:22:04,190
itt, teszem azt egy új sort.

297
00:22:04,190 --> 00:22:09,140
Ön kifejezetten mondani, elfelejtettem a pontos szintaxist.

298
00:22:09,140 --> 00:22:13,110
Így kifejezetten foglalkozzanak ezekkel nevét, és azt mondja:

299
00:22:13,110 --> 00:22:21,570
. C vagy. Value = 9. Jobbra = NULL.

300
00:22:21,570 --> 00:22:24,540
Gondolom ezeket kell vessző.

301
00:22:24,540 --> 00:22:29,110
. Jobbra = NULL, tehát így nem teszed

302
00:22:29,110 --> 00:22:33,780
ténylegesen tudni sorrendben a struct,

303
00:22:33,780 --> 00:22:36,650
és ha ezt olvasod, akkor sokkal több explicit

304
00:22:36,650 --> 00:22:41,920
arról, hogy mi az érték ez alatt inicializálódik.

305
00:22:41,920 --> 00:22:44,080
>> Ez történik, hogy az egyik dolog, hogy -

306
00:22:44,080 --> 00:22:49,100
így van, a legtöbb esetben, a C + + felülbírálja a C.

307
00:22:49,100 --> 00:22:54,160
Elviheti C kód, helyezze át a C + +, és meg kell fordítani.

308
00:22:54,160 --> 00:22:59,570
Ez az egyik dolog, hogy a C + + nem támogatja, így az emberek inkább nem csinálni.

309
00:22:59,570 --> 00:23:01,850
Nem tudom, ha ez az egyetlen ok, amiért az emberek inkább nem csinálni,

310
00:23:01,850 --> 00:23:10,540
de ha szükséges, az I. használni kellett dolgozni C + +, és így nem tudtam használni ezt.

311
00:23:10,540 --> 00:23:14,000
Egy másik példa a valamit, ami nem működik a C + +

312
00:23:14,000 --> 00:23:16,940
hogyan malloc függvény a "void *", technikailag,

313
00:23:16,940 --> 00:23:20,200
de akkor csak annyit char * x = malloc bármi,

314
00:23:20,200 --> 00:23:22,840
és ez automatikusan leadott egy char *.

315
00:23:22,840 --> 00:23:25,450
Ez az automatikus leadott nem történik meg a C + +.

316
00:23:25,450 --> 00:23:28,150
Ez ugyanis nem fordul le, és akkor kifejezetten kell mondania

317
00:23:28,150 --> 00:23:34,510
char *, malloc, mindegy, hogy a leadott, hogy a char *.

318
00:23:34,510 --> 00:23:37,270
Nem sok mindent, hogy a C és a C + + nem értenek egyet,

319
00:23:37,270 --> 00:23:40,620
de ezek kettő.

320
00:23:40,620 --> 00:23:43,120
Akkor megyünk ezzel a szintaxissal.

321
00:23:43,120 --> 00:23:46,150
De még ha nem megy, hogy a szintaxis,

322
00:23:46,150 --> 00:23:49,470
ami - lehet baj ezzel?

323
00:23:49,470 --> 00:23:52,170
[Student] Nem kell dereference ez? >> Igen.

324
00:23:52,170 --> 00:23:55,110
Ne feledje, hogy a nyíl van egy implicit dereference,

325
00:23:55,110 --> 00:23:58,230
és így amikor mi csak foglalkozik a struct,

326
00:23:58,230 --> 00:24:04,300
szeretnénk használni. hogy egy terület belsejében a struct.

327
00:24:04,300 --> 00:24:07,200
És az egyetlen alkalommal, amikor használja nyíl, amikor akarunk csinálni -

328
00:24:07,200 --> 00:24:13,450
jól, nyíl megegyezik a -

329
00:24:13,450 --> 00:24:17,020
ez az, ami azt jelentette volna, ha én használt nyíl.

330
00:24:17,020 --> 00:24:24,600
Minden nyíl segítségével is, dereference ezt, most én vagyok egy struct, és tudok a területen.

331
00:24:24,600 --> 00:24:28,040
Vagy kap a területen közvetlenül vagy dereference és kap a területen -

332
00:24:28,040 --> 00:24:30,380
Azt hiszem, ezt kell értéket.

333
00:24:30,380 --> 00:24:33,910
De itt van dolgom csak egy struct, nem egy mutatót egy struct,

334
00:24:33,910 --> 00:24:38,780
, és így nem tudom használni a nyíl.

335
00:24:38,780 --> 00:24:47,510
De ez a fajta dolog, amit tehetünk az összes csomópont.

336
00:24:47,510 --> 00:24:55,790
Ó, istenem.

337
00:24:55,790 --> 00:25:09,540
Ez a 6., 7., és 3.

338
00:25:09,540 --> 00:25:16,470
Akkor létre az ágak a fa, mi lehet a 7 -

339
00:25:16,470 --> 00:25:21,650
tudjuk már, tőle balra kell mutatnia 3-ra.

340
00:25:21,650 --> 00:25:25,130
Szóval hogyan lehet csinálni?

341
00:25:25,130 --> 00:25:29,320
[Diákok, érthetetlen] >> Igen. A címe node3,

342
00:25:29,320 --> 00:25:34,170
és ha nem volt címe, akkor csak nem fordul.

343
00:25:34,170 --> 00:25:38,190
De ne feledjük, hogy ezek a mutatók a következő csomópontok.

344
00:25:38,190 --> 00:25:44,930
A jobb kell mutatnia 9,

345
00:25:44,930 --> 00:25:53,330
és 3 kell mutatnia a jobb 6-ra.

346
00:25:53,330 --> 00:25:58,480
Azt hiszem, ez minden. Bármilyen észrevétele vagy kérdése?

347
00:25:58,480 --> 00:26:02,060
[Diák, érthetetlen] A root lesz 7.

348
00:26:02,060 --> 00:26:08,210
Mi lehet mondjuk node * ptr =

349
00:26:08,210 --> 00:26:14,160
vagy root, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> A mi céljainkra, fogunk foglalkozni betéttel,

351
00:26:20,730 --> 00:26:25,490
így fogunk akar írni egy függvényt beilleszteni ebbe a bináris fa

352
00:26:25,490 --> 00:26:34,230
és betét elkerülhetetlenül fog hívni malloc hozzon létre egy új csomópontot ezt a fát.

353
00:26:34,230 --> 00:26:36,590
Tehát a dolgok, hogy rendetlen a tényt, hogy egyes csomópontok

354
00:26:36,590 --> 00:26:38,590
Jelenleg a verem

355
00:26:38,590 --> 00:26:43,680
és más csomópontok fog végül a heap, amikor be őket.

356
00:26:43,680 --> 00:26:47,640
Ez tökéletesen érvényes, de az egyetlen oka

357
00:26:47,640 --> 00:26:49,600
képesek vagyunk ezt a stack

358
00:26:49,600 --> 00:26:51,840
azért van, mert ez egy ilyen kitalált példa, hogy tudjuk,

359
00:26:51,840 --> 00:26:56,360
a fa kellene felépíteni, 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Ha nem ezt, akkor nem kell malloc az első helyen.

361
00:27:02,970 --> 00:27:06,160
Mint látni fogjuk egy kicsit később, akkor kell malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Most ez teljesen ésszerű fektetni a stack,

363
00:27:08,570 --> 00:27:14,750
de változtassuk meg, hogy ez egy malloc végrehajtását.

364
00:27:14,750 --> 00:27:17,160
Tehát mindegyik most lesz valami hasonló

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

366
00:27:24,240 --> 00:27:28,040
És most mi lesz, hogy meg kell csinálni a csekket.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Nem akartam, hogy -

368
00:27:34,010 --> 00:27:40,950
vissza 1, majd tehetünk node9->, mert most ez a mutató,

369
00:27:40,950 --> 00:27:45,300
value = 6, node9-> bal = NULL,

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

371
00:27:48,930 --> 00:27:51,410
és mi lesz, hogy meg kell tennie, hogy minden egyes ilyen csomópontok.

372
00:27:51,410 --> 00:27:57,490
Tehát ahelyett, mondjuk belsejében egy külön funkció.

373
00:27:57,490 --> 00:28:00,620
Nevezzük meg node * build_node,

374
00:28:00,620 --> 00:28:09,050
és ez némileg hasonlít az API-k nyújtunk Huffman-kódolással.

375
00:28:09,050 --> 00:28:12,730
Adunk inicializáló funkciók egy fa

376
00:28:12,730 --> 00:28:20,520
és deconstructor "funkciók" azon fák és ugyanazt az erdők.

377
00:28:20,520 --> 00:28:22,570
>> Tehát itt fogunk van egy inicializáló függvény

378
00:28:22,570 --> 00:28:25,170
hogy csak építeni egy node számunkra.

379
00:28:25,170 --> 00:28:29,320
És ez fog kinézni nagyjából pontosan olyan, mint ez.

380
00:28:29,320 --> 00:28:32,230
És én még lesz lusta, és nem változtatja meg a nevét, a változó,

381
00:28:32,230 --> 00:28:34,380
bár node9 nincs értelme többé.

382
00:28:34,380 --> 00:28:38,610
Oh, azt hiszem node9 értékét nem kellett volna 6.

383
00:28:38,610 --> 00:28:42,800
Most már vissza node9.

384
00:28:42,800 --> 00:28:49,550
És itt vissza kell null.

385
00:28:49,550 --> 00:28:52,690
Mindenki egyetért, hogy a build-a-node funkció?

386
00:28:52,690 --> 00:28:59,780
Így most már csak hívja, hogy építeni minden csomópont egy adott érték és null mutatók.

387
00:28:59,780 --> 00:29:09,750
Most már meg tudjuk hívni, hogy meg tudjuk csinálni node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
És csináljuk. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
És most szeretnénk létrehozni ugyanazt a mutatók,

391
00:29:39,330 --> 00:29:42,470
kivéve most már minden a szempontból mutatók

392
00:29:42,470 --> 00:29:48,480
így már nincs szükség a címét.

393
00:29:48,480 --> 00:29:56,300
Oké. Szóval, mi volt az utolsó dolog, amit akarok?

394
00:29:56,300 --> 00:30:03,850
Van egy hiba ellenőrzésére, hogy én nem csinálok.

395
00:30:03,850 --> 00:30:06,800
Mit épít csomópont vissza?

396
00:30:06,800 --> 00:30:11,660
[Diák, érthetetlen] >> Igen. Ha malloc sikertelen, akkor az vissza null.

397
00:30:11,660 --> 00:30:16,460
Szóval fogom lustán tedd le ide, ahelyett, hogy a feltétel minden.

398
00:30:16,460 --> 00:30:22,320
Ha a (node9 == NULL, vagy - még egyszerűbb,

399
00:30:22,320 --> 00:30:28,020
ez egyenértékű azzal, hogy csak ha nem node9.

400
00:30:28,020 --> 00:30:38,310
Szóval, ha nem node9, vagy nem node6, vagy nem node3, vagy nem node7, vissza 1.

401
00:30:38,310 --> 00:30:42,850
Talán meg kellene nyomtatni malloc sikertelen, vagy valami ilyesmi.

402
00:30:42,850 --> 00:30:46,680
[Diák] A false egyenlő: null is?

403
00:30:46,680 --> 00:30:51,290
[Bowden] A nulla érték hamis.

404
00:30:51,290 --> 00:30:53,920
Tehát null nulla érték.

405
00:30:53,920 --> 00:30:56,780
Zero nulla érték. Hamis nulla érték.

406
00:30:56,780 --> 00:31:02,130
Bármely - nagyjából csak 2 nulla értékek null és a nulla,

407
00:31:02,130 --> 00:31:07,900
false éppen hash definiált nulla.

408
00:31:07,900 --> 00:31:13,030
Ez azt is érvényes, ha teszünk nyilvánítja globális változót.

409
00:31:13,030 --> 00:31:17,890
Ha tényleg van node * gyökér itt,

410
00:31:17,890 --> 00:31:24,150
akkor - a szép dolog globális változók, hogy mindig van egy kezdeti értéket.

411
00:31:24,150 --> 00:31:27,500
Ez nem igaz a funkciók, hogy belül van,

412
00:31:27,500 --> 00:31:34,870
ha van, mint az, node * vagy csomópont x.

413
00:31:34,870 --> 00:31:37,380
Fogalmunk sincs, mi x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
vagy mi lehet nyomtatni őket, és ők lehetnek önkényes.

415
00:31:40,700 --> 00:31:44,980
Ez nem igaz, a globális változók.

416
00:31:44,980 --> 00:31:47,450
Szóval gyökér csomópont vagy csomópont x.

417
00:31:47,450 --> 00:31:53,410
Alapértelmezés szerint mindent, ami a globális, ha nem kifejezetten inicializálja valamilyen érték,

418
00:31:53,410 --> 00:31:57,390
nulla értéket az értékét.

419
00:31:57,390 --> 00:32:01,150
Tehát itt, node * root, nem kifejezetten inicializálni el semmit,

420
00:32:01,150 --> 00:32:06,350
így az alapértelmezett érték null lesz, amely a nulla érték mutatók.

421
00:32:06,350 --> 00:32:11,870
Az alapértelmezett érték az x fogja jelenti, hogy x.value nulla,

422
00:32:11,870 --> 00:32:14,260
x.left null, és x.right null.

423
00:32:14,260 --> 00:32:21,070
Tehát mivel ez egy struct, minden területen a struct nulla értékeket.

424
00:32:21,070 --> 00:32:24,410
Nem kell használni, hogy itt, mégis.

425
00:32:24,410 --> 00:32:27,320
[Student] A Struktúrák vannak más, mint a többi változót, és a többi változó

426
00:32:27,320 --> 00:32:31,400
szemeteskocsi értékeket; ezek nullák?

427
00:32:31,400 --> 00:32:36,220
[Bowden] egyéb értékek is. Tehát x, x nulla lesz.

428
00:32:36,220 --> 00:32:40,070
Ha ez a globális hatókörű, van egy kezdeti értéket. >> Oké.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Vagy a kezdeti érték adtad, vagy nulla.

430
00:32:48,950 --> 00:32:53,260
Úgy gondolom, hogy gondoskodik mindezt.

431
00:32:53,260 --> 00:32:58,390
>> Oké. Így a következő része a kérdés arra irányul,

432
00:32:58,390 --> 00:33:01,260
"Most szeretnénk levelet nevezett funkció tartalmaz

433
00:33:01,260 --> 00:33:04,930
egy prototípus bool tartalmaz int értéket. "

434
00:33:04,930 --> 00:33:08,340
Mi nem fog csinálni bool tartalmaz int értéket.

435
00:33:08,340 --> 00:33:15,110
A prototípust fog kinézni

436
00:33:15,110 --> 00:33:22,380
bool tartalmaz (int értéket.

437
00:33:22,380 --> 00:33:24,490
És akkor mi is fog múlni, hogy a fa

438
00:33:24,490 --> 00:33:28,870
hogy meg kellene ellenőrzi, hogy ha van az érték.

439
00:33:28,870 --> 00:33:38,290
Szóval node * fa). Oké.

440
00:33:38,290 --> 00:33:44,440
És akkor nevezhetjük azt valami ilyesmi,

441
00:33:44,440 --> 00:33:46,090
talán mi szeretnénk printf vagy valami.

442
00:33:46,090 --> 00:33:51,040
Tartalmaz 6, a root.

443
00:33:51,040 --> 00:33:54,300
Ezt vissza kell adnia egy, vagy igaz,

444
00:33:54,300 --> 00:33:59,390
mivel tartalmaz 5 gyökér vissza kell hamis.

445
00:33:59,390 --> 00:34:02,690
Tehát, hogy egy második végrehajtásához.

446
00:34:02,690 --> 00:34:06,780
Meg tudod csinálni vagy iteratív vagy rekurzív.

447
00:34:06,780 --> 00:34:09,739
A szép dolog, ahogy mi is be a dolgokat, hogy a

448
00:34:09,739 --> 00:34:12,300
ez alkalmas arra, hogy a rekurzív megoldás sokkal könnyebb

449
00:34:12,300 --> 00:34:14,719
mint a globális változó módon tette.

450
00:34:14,719 --> 00:34:19,750
Mert ha csak azt tartalmazza int értéket, akkor nincs módja rekurzív lefelé részfák.

451
00:34:19,750 --> 00:34:24,130
Azt kell, hogy legyen egy külön segítő funkció recurses megállapításáról részfákat számunkra.

452
00:34:24,130 --> 00:34:29,610
De mivel mi már megváltoztatta, hogy a fa, mint egy érvet,

453
00:34:29,610 --> 00:34:32,760
azt meg mindig is az első helyen,

454
00:34:32,760 --> 00:34:35,710
Most tudjuk recurse könnyebben.

455
00:34:35,710 --> 00:34:38,960
Szóval iteratív vagy rekurzív, megyünk át mindkettőt,

456
00:34:38,960 --> 00:34:46,139
de majd meglátjuk, hogy a rekurzív végül is nagyon egyszerű.

457
00:34:59,140 --> 00:35:02,480
Oké. Van valakinek valami, tudunk dolgozni?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Van egy iteratív megoldást. >> Rendben, iteratív.

459
00:35:12,000 --> 00:35:16,030
Oké, ez jól néz ki.

460
00:35:16,030 --> 00:35:18,920
Szóval, akarsz járni nekünk ez?

461
00:35:18,920 --> 00:35:25,780
[Student] Persze. Szóval beállítani temp változót, hogy az első csomópont a fa.

462
00:35:25,780 --> 00:35:28,330
Aztán körhurkolt míg temp nem egyenlő null,

463
00:35:28,330 --> 00:35:31,700
így amíg még a fa, azt hiszem.

464
00:35:31,700 --> 00:35:35,710
És ha az érték megegyezik az értékre, temp re mutat rá,

465
00:35:35,710 --> 00:35:37,640
majd visszatér az értéket.

466
00:35:37,640 --> 00:35:40,210
Ellenkező esetben, ellenőrzi, ha ez a jobb oldalon, vagy a bal oldalon.

467
00:35:40,210 --> 00:35:43,400
Ha valaha is olyan helyzetben, amikor nincs több fa,

468
00:35:43,400 --> 00:35:47,330
majd visszatér - kilép a hurok, és visszatér hamis.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Oké. Szóval úgy tűnik, jó.

470
00:35:52,190 --> 00:35:58,470
Bárki bármilyen észrevétele van a semmit?

471
00:35:58,470 --> 00:36:02,400
Nekem nincs korrektség Megjegyzés egyáltalán.

472
00:36:02,400 --> 00:36:11,020
Az egyetlen dolog, amit tehetünk, ez a fickó.

473
00:36:11,020 --> 00:36:21,660
Oh, ez fog menni egy kicsit hosszúkás.

474
00:36:21,660 --> 00:36:33,460
Megcsinálom, hogy akár. Oké.

475
00:36:33,460 --> 00:36:37,150
>> Mindenkinek meg kell emlékezni, hogyan háromkomponensű működik.

476
00:36:37,150 --> 00:36:38,610
Voltak határozottan nem vetélkedők a múltban

477
00:36:38,610 --> 00:36:41,170
hogy kapsz egy funkciót egy háromkomponensű üzemeltető,

478
00:36:41,170 --> 00:36:45,750
és azt mondják, fordítsd le ezt, tenni valamit, hogy nem használja a hármas.

479
00:36:45,750 --> 00:36:49,140
Tehát ez egy nagyon gyakori eset, amikor azt hiszem, hogy használni háromkomponensű,

480
00:36:49,140 --> 00:36:54,610
ahol ha néhány feltétel egy változó valami,

481
00:36:54,610 --> 00:36:58,580
másnak állítja be, hogy ugyanazt a változót valami másra.

482
00:36:58,580 --> 00:37:03,390
Ez valami, ami nagyon gyakran lehet alakítani ezt a fajta dolog

483
00:37:03,390 --> 00:37:14,420
amennyiben állítja be, hogy a változó e - vagy, nos, ez igaz? Aztán ez, különben ezt.

484
00:37:14,420 --> 00:37:18,550
[Student] Az első, hogy ha igaz, ugye?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Igen. Ahogy én mindig olvassa el azt, hőm egyenlő értéke nagyobb, mint temp érték,

486
00:37:25,570 --> 00:37:30,680
akkor ez, különben ezt. Ez feltettem egy kérdést.

487
00:37:30,680 --> 00:37:35,200
Ez a nagyobb? Ezután hajtsa végre az első dolog. Különben nem a másik dolog.

488
00:37:35,200 --> 00:37:41,670
Én szinte mindig - a vastagbél, csak - a fejemben, olvastam, mint más.

489
00:37:41,670 --> 00:37:47,180
>> Van valakinek egy rekurzív megoldás?

490
00:37:47,180 --> 00:37:49,670
Oké. Ez fogjuk - ez lehet már nagy,

491
00:37:49,670 --> 00:37:53,990
de mi lesz, hogy még jobb.

492
00:37:53,990 --> 00:37:58,720
Ez nagyjából pontosan ugyanolyan ötlet.

493
00:37:58,720 --> 00:38:03,060
Ez csak, nos, nem akarsz megmagyarázni?

494
00:38:03,060 --> 00:38:08,340
[Student] Persze. Szóval meggyőződve arról, hogy a fa nem null az első,

495
00:38:08,340 --> 00:38:13,380
mert ha a fa null akkor fog visszatérni hamis, mert még nem találtam meg.

496
00:38:13,380 --> 00:38:19,200
És ha van még egy fa, akkor menj be - először ellenőrizze, hogy az érték a jelenlegi csomópont.

497
00:38:19,200 --> 00:38:23,740
Vissza igaz, ha van, és ha nem is recurse a balra vagy jobbra.

498
00:38:23,740 --> 00:38:25,970
Hangzik megfelelő? >> Mm-hmm. (Megállapodás)

499
00:38:25,970 --> 00:38:33,880
Így észleli, hogy ez szinte - szerkezetileg nagyon hasonló az iteratív oldathoz.

500
00:38:33,880 --> 00:38:38,200
Csak hogy ahelyett, hogy rekurzív, volt egy while ciklus.

501
00:38:38,200 --> 00:38:40,840
És az alapeset itt, ahol fa nem egyenlő null

502
00:38:40,840 --> 00:38:44,850
volt a feltétel, amelyhez kitört a while ciklus.

503
00:38:44,850 --> 00:38:50,200
Ők nagyon hasonló. De mi lesz, hogy ezt egy lépéssel tovább.

504
00:38:50,200 --> 00:38:54,190
Most már nem ugyanaz a dolog itt.

505
00:38:54,190 --> 00:38:57,680
Figyeljük meg mi vissza ugyanaz mindkét vonalak,

506
00:38:57,680 --> 00:39:00,220
kivéve egy argumentum eltérő.

507
00:39:00,220 --> 00:39:07,950
Így fogunk tenni, hogy egy hármas.

508
00:39:07,950 --> 00:39:13,790
Megütöttem opciót valamit, és tett egy szimbólum. Oké.

509
00:39:13,790 --> 00:39:21,720
Szóval megyünk vissza, hogy tartalmaz.

510
00:39:21,720 --> 00:39:28,030
Ez kezd, hogy több vonal, nos, nagyított benne van.

511
00:39:28,030 --> 00:39:31,060
Általában, mint stilisztikai dolog, nem hiszem, sok ember

512
00:39:31,060 --> 00:39:38,640
hogy egy szóköz után a nyilat, de azt hiszem, ha következetes, ez rendben van.

513
00:39:38,640 --> 00:39:44,320
Ha az érték kisebb, mint fa érték, szeretnénk recurse a fa balra,

514
00:39:44,320 --> 00:39:53,890
mást akarunk recurse a fa van.

515
00:39:53,890 --> 00:39:58,610
Szóval ez volt az első lépés az, hogy ezt meg kisebb.

516
00:39:58,610 --> 00:40:02,660
Második lépés, hogy ezt meg kisebb -

517
00:40:02,660 --> 00:40:09,150
tudjuk elkülöníteni, hogy ez több sorban is.

518
00:40:09,150 --> 00:40:16,500
Oké. Step kettő így néz kisebb itt,

519
00:40:16,500 --> 00:40:25,860
így visszatérési értéke megegyezik fa értéke, illetve tartalmaz bármi.

520
00:40:25,860 --> 00:40:28,340
>> Ez egy fontos dolog.

521
00:40:28,340 --> 00:40:30,860
Nem vagyok biztos benne, hogy azt mondta, hogy kifejezetten az osztályban,

522
00:40:30,860 --> 00:40:34,740
de ez az úgynevezett rövidre értékelés.

523
00:40:34,740 --> 00:40:41,060
Az elképzelés itt az érték == fa értékét.

524
00:40:41,060 --> 00:40:49,960
Ha ez igaz, akkor ez igaz, és azt akarjuk, hogy "vagy", amely, bármilyen vége van.

525
00:40:49,960 --> 00:40:52,520
Így anélkül, hogy gondolkodás nélkül vége van,

526
00:40:52,520 --> 00:40:55,070
mi a teljes kifejezés megy vissza?

527
00:40:55,070 --> 00:40:59,430
[Student] Igaz? >> Igen, mert igaz semmit,

528
00:40:59,430 --> 00:41:04,990
or'd - vagy valós or'd bármi szükségszerűen igaz.

529
00:41:04,990 --> 00:41:08,150
Tehát amint látjuk visszatérési érték = fa érték,

530
00:41:08,150 --> 00:41:10,140
mi csak megy vissza igaz.

531
00:41:10,140 --> 00:41:15,710
Nem is megy recurse tartalmazza továbbá le a pályáról.

532
00:41:15,710 --> 00:41:20,980
Mi ezt egy lépéssel tovább.

533
00:41:20,980 --> 00:41:29,490
Return fa nem egyenlő null, és ezt az egészet.

534
00:41:29,490 --> 00:41:32,650
Ez tette egy sor funkciót.

535
00:41:32,650 --> 00:41:36,790
Ez is egy példa rövidzárlat értékelés.

536
00:41:36,790 --> 00:41:40,680
De most ez ugyanaz a gondolat -

537
00:41:40,680 --> 00:41:47,320
helyett - így a fa nem egyenlő null - vagy, nos,

538
00:41:47,320 --> 00:41:49,580
a fa nem egyenlő nulla, ami a rossz eset,

539
00:41:49,580 --> 00:41:54,790
ha a fa értéke null, akkor az első feltétel lesz hamis.

540
00:41:54,790 --> 00:42:00,550
Tehát hamis anded bármi lesz mi?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Igen. Ez a másik fele rövidzárlat értékelés,

542
00:42:04,640 --> 00:42:10,710
ahol ha fa nem egyenlő nulla, akkor nem fogunk még menni -

543
00:42:10,710 --> 00:42:14,930
vagy ha a fa nem egyenlő null, akkor nem fogunk csinálni érték == fa értékét.

544
00:42:14,930 --> 00:42:17,010
Mi csak megy, hogy azonnal térjen vissza hamis.

545
00:42:17,010 --> 00:42:20,970
Ami azért fontos, mert ha nem rövidzárlat értékeli,

546
00:42:20,970 --> 00:42:25,860
majd ha a fa nem egyenlő null, ezt a második feltételt fog seg hiba

547
00:42:25,860 --> 00:42:32,510
mert a fa-> érték dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Szóval ennyi. Lehet, hogy ez a - műszak egyszer vége.

549
00:42:40,490 --> 00:42:44,840
Ez egy nagyon gyakori dolog is, nem tesz ez összhangban,

550
00:42:44,840 --> 00:42:49,000
de ez egy közös dolog a körülmények, talán nem itt,

551
00:42:49,000 --> 00:42:59,380
de ha (fa! = NULL, és a fa-> érték == érték), nem mindegy.

552
00:42:59,380 --> 00:43:01,560
Ez egy nagyon gyakori állapot, ahol ahelyett, hogy

553
00:43:01,560 --> 00:43:06,770
törni ezt a két IFS, ha tetszik, a fa null?

554
00:43:06,770 --> 00:43:11,780
Oké, ez nem nulla, így most a fa értéke egyenlő értéknek? Tedd ezt.

555
00:43:11,780 --> 00:43:17,300
Ehelyett ez a feltétel, ez soha nem fog seg hiba

556
00:43:17,300 --> 00:43:21,220
mert kitörni, ha ez történetesen null.

557
00:43:21,220 --> 00:43:24,000
Nos, azt hiszem, ha a fa teljesen érvénytelen mutató, akkor is seg hiba,

558
00:43:24,000 --> 00:43:26,620
de nem seg hiba, ha a fa null.

559
00:43:26,620 --> 00:43:32,900
Ha ez nulla, akkor tör ki, mielőtt még másolunk a mutatót az első helyen.

560
00:43:32,900 --> 00:43:35,000
[Diák] Ez úgynevezett lusta értékelést?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy értékelés külön dolog.

562
00:43:40,770 --> 00:43:49,880
Lazy értékelés több hasonlót kérsz egy értéket,

563
00:43:49,880 --> 00:43:54,270
kérsz kiszámításához érték, fajta, de nem kell azonnal.

564
00:43:54,270 --> 00:43:59,040
Szóval, amíg ténylegesen szüksége van rá, nem vizsgálták.

565
00:43:59,040 --> 00:44:03,920
Ez nem pontosan ugyanaz a dolog, de a Huffman Pset,

566
00:44:03,920 --> 00:44:06,520
azt mondja, hogy mi "lustán" írni.

567
00:44:06,520 --> 00:44:08,670
Ennek az az oka, hogy mi, mert mi tulajdonképpen puffer az írás -

568
00:44:08,670 --> 00:44:11,820
nem akarunk írni egyes bitek egy időben,

569
00:44:11,820 --> 00:44:15,450
vagy egyéni byte egy időben, mi inkább szeretnénk, hogy egy darab bájt.

570
00:44:15,450 --> 00:44:19,270
Aztán egyszer van egy darab bájt, aztán írjuk ki.

571
00:44:19,270 --> 00:44:22,640
Annak ellenére, hogy kérje meg, hogy írjon - és fwrite és fread nem ugyanaz a fajta dolog.

572
00:44:22,640 --> 00:44:26,260
A puffer meg olvas és ír.

573
00:44:26,260 --> 00:44:31,610
Annak ellenére, hogy kérje meg, hogy írjon azonnal, akkor valószínűleg nem fog.

574
00:44:31,610 --> 00:44:34,540
És nem biztos, hogy a dolgok lesznek írva

575
00:44:34,540 --> 00:44:37,540
amíg nem hívja hfclose vagy akármi is az,

576
00:44:37,540 --> 00:44:39,620
amelyek aztán azt mondja, oké, én bezárása a fájl,

577
00:44:39,620 --> 00:44:43,450
azt jelenti, hogy én jobban írni mindent nem írtam még.

578
00:44:43,450 --> 00:44:45,770
Azt nem kell írni mindent

579
00:44:45,770 --> 00:44:49,010
amíg közelednek a fájlt, és akkor kell.

580
00:44:49,010 --> 00:44:56,220
Szóval ez az, amit lusta - megvárja, amíg meg kell történnie.

581
00:44:56,220 --> 00:44:59,990
Ez - hogy 51 és akkor megy bele részletesen,

582
00:44:59,990 --> 00:45:05,470
mert OCaml és minden 51, minden rekurziót.

583
00:45:05,470 --> 00:45:08,890
Nincsenek iteratív megoldások, alapvetően.

584
00:45:08,890 --> 00:45:11,550
Minden rekurzió, és lusta értékelés

585
00:45:11,550 --> 00:45:14,790
lesz fontos a sok esetben

586
00:45:14,790 --> 00:45:19,920
ahol, ha nem lustán értékeli, ez azt jelentené -

587
00:45:19,920 --> 00:45:24,760
A példa folyamok, melyek végtelen hosszú.

588
00:45:24,760 --> 00:45:30,990
Elméletileg, akkor gondolom, a természetes számok, mint a patak 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Szóval lustán értékelt dolgok rendben vannak.

590
00:45:33,090 --> 00:45:37,210
Ha azt mondom, hogy akarjuk, hogy a 10. számot, akkor én is értékeli fel a 10. számot.

591
00:45:37,210 --> 00:45:40,300
Ha azt szeretné, hogy a századik számot, akkor én is értékeli fel a századik számot.

592
00:45:40,300 --> 00:45:46,290
Nélkül lusta értékelés, akkor ez lesz, hogy megpróbálja értékelni az összes szám azonnal.

593
00:45:46,290 --> 00:45:50,000
Te értékelése végtelen sok szám, és ez egyszerűen nem lehetséges.

594
00:45:50,000 --> 00:45:52,080
Tehát van egy csomó esetben, ha lusta értékelés

595
00:45:52,080 --> 00:45:57,840
csak elengedhetetlen a dolgok dolgozni.

596
00:45:57,840 --> 00:46:05,260
>> Most szeretnénk írni, ahol a betét betét lesz

597
00:46:05,260 --> 00:46:08,430
hasonlóan változó a meghatározás.

598
00:46:08,430 --> 00:46:10,470
Így most ez bool betét (int érték).

599
00:46:10,470 --> 00:46:23,850
Mi fog változni, hogy a lapka bool (int érték, node * fa).

600
00:46:23,850 --> 00:46:29,120
Mi tényleg meg fog változni, hogy ismét egy kicsit, majd meglátjuk, miért.

601
00:46:29,120 --> 00:46:32,210
És menjünk build_node, csak a fene azt,

602
00:46:32,210 --> 00:46:36,730
felett helyezze így nem kell írni egy függvény prototípus.

603
00:46:36,730 --> 00:46:42,450
Ami egy tipp, hogy fogsz használni build_node a betét.

604
00:46:42,450 --> 00:46:49,590
Oké. Vegyünk egy percet erre.

605
00:46:49,590 --> 00:46:52,130
Azt hiszem, megmentette a felülvizsgálni, ha azt szeretnénk, hogy húzza meg, hogy a

606
00:46:52,130 --> 00:47:00,240
vagy legalábbis, én most.

607
00:47:00,240 --> 00:47:04,190
Szerettem volna egy kis szünetet, hogy úgy gondolja, a logika betét

608
00:47:04,190 --> 00:47:08,750
ha nem gondol rá.

609
00:47:08,750 --> 00:47:12,860
Alapvetően, ha csak valaha is beilleszteni a levelek.

610
00:47:12,860 --> 00:47:18,640
Mint, ha be 1, akkor én elkerülhetetlenül lesz beilleszteni 1 -

611
00:47:18,640 --> 00:47:21,820
Majd váltson fekete - leszek beilleszteni 1 ide.

612
00:47:21,820 --> 00:47:28,070
Vagy ha beilleszteni 4, azt akarom, hogy 4 beilleszteni ide.

613
00:47:28,070 --> 00:47:32,180
Tehát nem számít, mit teszel, te leszel beilleszteni egy levél.

614
00:47:32,180 --> 00:47:36,130
Mindössze annyit kell tennie, hogy navigálhat le a fát, amíg nem kap a csomópont

615
00:47:36,130 --> 00:47:40,890
hogy kell a csomópont szülő, az új csomópont szülő,

616
00:47:40,890 --> 00:47:44,560
majd változtassa meg a balra vagy jobbra mutató, attól függően, hogy

617
00:47:44,560 --> 00:47:47,060
ez kisebb vagy nagyobb, mint a jelenlegi csomópont.

618
00:47:47,060 --> 00:47:51,180
Változás, hogy a mutató arra utalnak, hogy az új csomópont.

619
00:47:51,180 --> 00:48:05,490
Tehát ismételget le a fáról, hogy a levél pont az új csomópontot.

620
00:48:05,490 --> 00:48:09,810
Szintén gondolj, hogy miért tiltja az ilyen helyzetekben előtt,

621
00:48:09,810 --> 00:48:17,990
ahol épített a bináris fa, ahol helyes volt

622
00:48:17,990 --> 00:48:19,920
ha csak ránézett egy csomópont,

623
00:48:19,920 --> 00:48:24,830
de 9 volt, a bal oldalon 7 Ha megismételte le az összes utat.

624
00:48:24,830 --> 00:48:29,770
Szóval ez lehetetlen ebben a forgatókönyvben, hiszen -

625
00:48:29,770 --> 00:48:32,530
gondolnak beszúrásával 9, vagy valami, az első csomópont,

626
00:48:32,530 --> 00:48:35,350
Megyek, hogy 7-es és én csak menni jobbra.

627
00:48:35,350 --> 00:48:38,490
Tehát nem számít, hogy mit tegyek, ha én behelyezésénél megy, egy levél,

628
00:48:38,490 --> 00:48:40,790
és egy levél a megfelelő algoritmus,

629
00:48:40,790 --> 00:48:43,130
ez lesz lehetetlen számomra, hogy helyezze be a 9 bal 7

630
00:48:43,130 --> 00:48:48,250
mert amint elütöttem 7 Én megyek jobbra.

631
00:48:59,740 --> 00:49:02,070
Csinál akárki volna valamit kezdeni?

632
00:49:02,070 --> 00:49:05,480
[Student] én. >> Persze.

633
00:49:05,480 --> 00:49:09,200
[Diák, érthetetlen]

634
00:49:09,200 --> 00:49:14,390
[Other diák, érthetetlen]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Ez értékelik. Oké. Szeretne megmagyarázni?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Mivel tudjuk, hogy mi volt behelyezése

637
00:49:20,690 --> 00:49:24,060
új csomópontok végén a fa,

638
00:49:24,060 --> 00:49:28,070
Én hurkolt át a fa iteratív

639
00:49:28,070 --> 00:49:31,360
amíg kaptam egy csomópont, amely rámutatott null.

640
00:49:31,360 --> 00:49:34,220
És akkor úgy döntöttem, hogy azt akár a jobb oldalon, vagy a bal oldalon

641
00:49:34,220 --> 00:49:37,420
használja ezt a jogot a változó, azt mondta nekem, hogy hol tegye.

642
00:49:37,420 --> 00:49:41,850
És aztán, lényegében csak tenni, hogy az utolsó -

643
00:49:41,850 --> 00:49:47,520
hogy a temp csomópont pont az új csomópont, hogy azt létre,

644
00:49:47,520 --> 00:49:50,770
akár a bal oldalon, vagy a jobb oldalon, attól függően, hogy milyen értéket helyes volt.

645
00:49:50,770 --> 00:49:56,530
Végül, én meg az új csomópont értéket a értékét tesztelés.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Oké, akkor látom, egy kérdés van.

647
00:49:59,550 --> 00:50:02,050
Ez olyan, mint 95%-a az út ott.

648
00:50:02,050 --> 00:50:07,550
Az egyetlen kérdés, hogy látom, nos, nem másnak látni egy kérdés?

649
00:50:07,550 --> 00:50:18,400
Mi az a körülmény, amely alapján törnek ki a hurok?

650
00:50:18,400 --> 00:50:22,100
[Student] Ha a hőmérséklet nulla? >> Igen. Szóval, hogyan tör ki a hurkot, ha temp null.

651
00:50:22,100 --> 00:50:30,220
De mit tegyek itt?

652
00:50:30,220 --> 00:50:35,410
I dereference temp, ami elkerülhetetlenül null.

653
00:50:35,410 --> 00:50:39,840
Szóval a másik dolog, amit meg kell tennie, hogy nem csak nyomon követni, amíg temp null,

654
00:50:39,840 --> 00:50:45,590
szeretné nyomon követni a szülő minden alkalommal.

655
00:50:45,590 --> 00:50:52,190
Mi is szeretnénk, node * szülő, azt hiszem, meg tudjuk tartani, hogy null elején.

656
00:50:52,190 --> 00:50:55,480
Ez megy, hogy furcsa viselkedést a gyökér a fa,

657
00:50:55,480 --> 00:50:59,210
de mi lesz erre.

658
00:50:59,210 --> 00:51:03,950
Ha az érték nagyobb, mint bármi, akkor temp = temp van.

659
00:51:03,950 --> 00:51:07,910
De mielőtt ezt tesszük, szülő = temp.

660
00:51:07,910 --> 00:51:14,500
Vagy a szülők mindig lesz egyenlő temp? Ez a helyzet?

661
00:51:14,500 --> 00:51:19,560
Ha a hőmérséklet nem nulla, akkor megyek lejjebb, nem számít, mit,

662
00:51:19,560 --> 00:51:24,030
olyan csomópont, amely hőmérséklet a szülő.

663
00:51:24,030 --> 00:51:27,500
Szóval szülő lesz temp, aztán mozogni temp lefelé.

664
00:51:27,500 --> 00:51:32,410
Most temp null, de rámutat arra, hogy szülő a szülő a dolog, hogy null.

665
00:51:32,410 --> 00:51:39,110
Tehát itt, nem akarom beállítani jobbra értéke 1.

666
00:51:39,110 --> 00:51:41,300
Szóval költözött a jobb, tehát ha jobbra = 1,

667
00:51:41,300 --> 00:51:45,130
és azt hiszem, te is szeretnél csinálni -

668
00:51:45,130 --> 00:51:48,530
ha mozog balra, szeretné beállítani jobbra 0-val egyenlő.

669
00:51:48,530 --> 00:51:55,950
Vagy ha valaha is mozog jobbra.

670
00:51:55,950 --> 00:51:58,590
Szóval jobb = 0. Ha jobbra = 1,

671
00:51:58,590 --> 00:52:04,260
Most azt szeretnénk, hogy a szülő megfelelő mutató newnode,

672
00:52:04,260 --> 00:52:08,520
más, amit szeretnénk, hogy az anyavállalat balra mutató newnode.

673
00:52:08,520 --> 00:52:16,850
Kérdések az?

674
00:52:16,850 --> 00:52:24,880
Oké. Tehát ez az út is - nos, valójában, ahelyett, hogy ezt,

675
00:52:24,880 --> 00:52:29,630
mi 1/2 várható használatát build_node.

676
00:52:29,630 --> 00:52:40,450
És aztán, ha newnode egyenlő null vissza hamis.

677
00:52:40,450 --> 00:52:44,170
Ez azt. Nos, ez az, amit vártunk tőled.

678
00:52:44,170 --> 00:52:47,690
>> Ez az, amit az alkalmazott megoldásokat csinálni.

679
00:52:47,690 --> 00:52:52,360
Nem értek egyet ezzel a "megfelelő" módon megy róla

680
00:52:52,360 --> 00:52:57,820
de ez teljesen rendben van, és működni fog.

681
00:52:57,820 --> 00:53:02,840
Egy dolog, hogy ez egy kicsit furcsa most is

682
00:53:02,840 --> 00:53:08,310
ha a fa indul a null, átadjuk egy null fa.

683
00:53:08,310 --> 00:53:12,650
Azt hiszem, ez attól függ, hogyan határozza meg a viselkedését halad egy null fa.

684
00:53:12,650 --> 00:53:15,490
Azt gondolom, hogy ha átmegy egy null fa,

685
00:53:15,490 --> 00:53:17,520
majd helyezze az érték egy null fa

686
00:53:17,520 --> 00:53:23,030
kéne vissza egy fát, ahol az egyetlen érték, hogy egyetlen csomópont.

687
00:53:23,030 --> 00:53:25,830
Embereknek Egyetért ezzel? Azt tudta, ha akarod,

688
00:53:25,830 --> 00:53:28,050
ha át egy null fa

689
00:53:28,050 --> 00:53:31,320
és a beszúrni kívánt értéket bele, vissza hamis.

690
00:53:31,320 --> 00:53:33,830
Ez rajtad múlik, hogy meghatározza, hogy az.

691
00:53:33,830 --> 00:53:38,320
Ehhez az első dolog, amit mondtam, és akkor -

692
00:53:38,320 --> 00:53:40,720
nos, akkor fogsz gondot csinál, mert

693
00:53:40,720 --> 00:53:44,090
könnyebb lenne, ha lenne egy globális mutatót a dolog,

694
00:53:44,090 --> 00:53:48,570
de nem, így ha a fa null, ott semmit sem tehetünk róla.

695
00:53:48,570 --> 00:53:50,960
Mi is csak vissza hamis.

696
00:53:50,960 --> 00:53:52,840
Szóval meg fog változni betéttel.

697
00:53:52,840 --> 00:53:56,540
Mi technikailag is csak megváltoztatni ezt itt,

698
00:53:56,540 --> 00:53:58,400
hogyan is iterációjával dolgok felett,

699
00:53:58,400 --> 00:54:04,530
de fogom változtatni betét, hogy egy csomópont ** fa.

700
00:54:04,530 --> 00:54:07,510
Dupla mutatók.

701
00:54:07,510 --> 00:54:09,710
Mit jelent ez?

702
00:54:09,710 --> 00:54:12,330
Ahelyett, hogy foglalkozik mutatókat csomópontok,

703
00:54:12,330 --> 00:54:16,690
a dolog, fogok is manipulálni ez a mutató.

704
00:54:16,690 --> 00:54:18,790
Megyek, hogy manipulálni ez a mutató.

705
00:54:18,790 --> 00:54:21,770
Megyek, hogy manipulálni mutatókat közvetlenül.

706
00:54:21,770 --> 00:54:25,760
Ez logikus is, hiszen gondoljon le -

707
00:54:25,760 --> 00:54:33,340
Nos, most ezt a pontot null.

708
00:54:33,340 --> 00:54:38,130
Amit én akarok, manipulálni ez a mutató, hogy pont nem nulla.

709
00:54:38,130 --> 00:54:40,970
Azt akarom, hogy pont az én új csomópontot.

710
00:54:40,970 --> 00:54:44,870
Ha csak nyomon követni a mutatókat a mutatók,

711
00:54:44,870 --> 00:54:47,840
akkor nem kell nyomon követni a szülő mutató.

712
00:54:47,840 --> 00:54:52,640
Én is csak nyomon követni, hogy ha a mutató mutat null,

713
00:54:52,640 --> 00:54:54,580
és ha a mutató mutat null,

714
00:54:54,580 --> 00:54:57,370
változtassa meg, hogy pont a csomópont akarok.

715
00:54:57,370 --> 00:55:00,070
És tudom megváltoztatni, mivel van egy mutatót a mutatót.

716
00:55:00,070 --> 00:55:02,040
Nézzük meg ezt most.

717
00:55:02,040 --> 00:55:05,470
Tudod valójában csinálni rekurzívan elég könnyen.

718
00:55:05,470 --> 00:55:08,080
Nem akarunk ilyet?

719
00:55:08,080 --> 00:55:10,980
Igen, mi.

720
00:55:10,980 --> 00:55:16,790
>> Lássuk rekurzívan.

721
00:55:16,790 --> 00:55:24,070
Először is, mi a alapeset lesz?

722
00:55:24,070 --> 00:55:29,140
Szinte mindig a bázis esetében, de valójában ez a fajta trükkös.

723
00:55:29,140 --> 00:55:34,370
Először is, ha a (fa == NULL)

724
00:55:34,370 --> 00:55:37,550
Azt hiszem, mi csak megy vissza hamis.

725
00:55:37,550 --> 00:55:40,460
Ez eltér a fa, hogy null.

726
00:55:40,460 --> 00:55:44,510
Ez a mutató a gyökér, hogy null pointer

727
00:55:44,510 --> 00:55:48,360
ami azt jelenti, hogy a root mutató nem létezik.

728
00:55:48,360 --> 00:55:52,390
Tehát itt, ha én nem

729
00:55:52,390 --> 00:55:55,760
node * - nézzük csak újra ezt.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
majd fogom hívni betét csinál valami ilyesmi,

732
00:56:00,730 --> 00:56:04,540
be a 4. és root.

733
00:56:04,540 --> 00:56:06,560
Szóval és gyökér, ha a gyökér csomópont *

734
00:56:06,560 --> 00:56:11,170
akkor és gyökér lesz egy csomópont **.

735
00:56:11,170 --> 00:56:15,120
Ez érvényes. Ebben az esetben a fa, fel itt,

736
00:56:15,120 --> 00:56:20,120
fa nem null - vagy betét.

737
00:56:20,120 --> 00:56:24,630
Tessék. Fa nem null; * fa null, ami rendben van

738
00:56:24,630 --> 00:56:26,680
mert ha * fa null, akkor én is manipulálni

739
00:56:26,680 --> 00:56:29,210
Most hova mutasson a mit akarok, hogy mutasson.

740
00:56:29,210 --> 00:56:34,750
De ha a fa null, azt jelenti, hogy csak azért jöttem ide, és azt mondta: null.

741
00:56:34,750 --> 00:56:42,710
Ennek nincs értelme. Nem tudok mit kezdeni vele.

742
00:56:42,710 --> 00:56:45,540
Ha a fa null vissza hamis.

743
00:56:45,540 --> 00:56:48,220
Szóval alapvetően már mondtam, mi a valódi alap eset.

744
00:56:48,220 --> 00:56:50,580
És mi az, hogy lesz?

745
00:56:50,580 --> 00:56:55,030
[Diák, érthetetlen]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Igen. Tehát, ha (* fa == NULL).

747
00:57:00,000 --> 00:57:04,520
Ez arra az esetre vonatkozik ide

748
00:57:04,520 --> 00:57:09,640
ahol ha a piros mutató a mutató Én összpontosított,

749
00:57:09,640 --> 00:57:12,960
így, mint én összpontosított ez a mutató, most én vagyok összpontosított ez a mutató.

750
00:57:12,960 --> 00:57:15,150
Most elsősorban erre mutató.

751
00:57:15,150 --> 00:57:18,160
Tehát, ha a piros mutató, ami az én csomópont **,

752
00:57:18,160 --> 00:57:22,880
valaha is - ha *, a piros mutató, valaha is null,

753
00:57:22,880 --> 00:57:28,470
azt jelenti, hogy én vagyok az a helyzet, ha én vagyok összpontosítva pointer, amely pontok -

754
00:57:28,470 --> 00:57:32,530
ez egy olyan mutató, amely tartozik a levél.

755
00:57:32,530 --> 00:57:41,090
Szeretném megváltoztatni ezt a mutatót, hogy pont az új csomópont.

756
00:57:41,090 --> 00:57:45,230
Gyere vissza ide.

757
00:57:45,230 --> 00:57:56,490
Erre newnode majd csak lesz node * n = build_node (érték)

758
00:57:56,490 --> 00:58:07,300
akkor n, ha n = NULL vissza hamis.

759
00:58:07,300 --> 00:58:12,600
Különben meg akarjuk változtatni, amit a mutató jelenleg mutat

760
00:58:12,600 --> 00:58:17,830
hogy most pont a mi újonnan épült csomópont.

761
00:58:17,830 --> 00:58:20,280
Mi valóban csinálni itt.

762
00:58:20,280 --> 00:58:30,660
Ahelyett, hogy n, mondjuk * fa * = ha fa.

763
00:58:30,660 --> 00:58:35,450
Mindenki érti ezt? Ez a szó mutatókat mutatók,

764
00:58:35,450 --> 00:58:40,750
meg tudjuk változtatni null mutatók arra utalnak, hogy a dolgokat akarjuk, hogy mutasson.

765
00:58:40,750 --> 00:58:42,820
Ez a mi alapeset.

766
00:58:42,820 --> 00:58:45,740
>> Most a kiújulás, vagy a mi rekurzió,

767
00:58:45,740 --> 00:58:51,430
lesz nagyon hasonló az összes többi recursions voltunk csinál.

768
00:58:51,430 --> 00:58:55,830
Elmegyünk a beszúrni kívánt értéket,

769
00:58:55,830 --> 00:58:59,040
és most fogom használni hármas újra, de mi a feltétele lesz?

770
00:58:59,040 --> 00:59:05,180
Mi is keresünk annak eldöntésére, hogy akarunk menni balra vagy jobbra?

771
00:59:05,180 --> 00:59:07,760
Csináljuk külön lépéseket.

772
00:59:07,760 --> 00:59:18,850
Ha (értéke <) mi?

773
00:59:18,850 --> 00:59:23,200
[Student] A fa értéke?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Úgy emlékszem, hogy én vagyok jelenleg -

775
00:59:27,490 --> 00:59:31,260
[Diákok, érthetetlen]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Igen, itt van, mondjuk, hogy ez a zöld nyíl

777
00:59:34,140 --> 00:59:39,050
egy példa arra, milyen fa jelenleg, egy mutató a mutató.

778
00:59:39,050 --> 00:59:46,610
Tehát ez azt jelenti, én vagyok a mutató egy mutató a 3.

779
00:59:46,610 --> 00:59:48,800
A dereference kétszer jól hangzott.

780
00:59:48,800 --> 00:59:51,010
Mit - hogyan tudom ezt?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference egyszer, majd tegye arrow így?

782
00:59:53,210 --> 00:59:58,420
[Bowden] So (* fa) a dereference egyszer -> értéke

783
00:59:58,420 --> 01:00:05,960
fog adni nekem az érték a csomópont, hogy én vagyok közvetve mutat.

784
01:00:05,960 --> 01:00:11,980
Szóval én is írni ** tree.value, ha azt szeretné, hogy.

785
01:00:11,980 --> 01:00:18,490
Vagy működik.

786
01:00:18,490 --> 01:00:26,190
Ha ez a helyzet, akkor azt akarom, hogy hívja be az értéket.

787
01:00:26,190 --> 01:00:32,590
És mi van az én frissítik csomópont ** lesz?

788
01:00:32,590 --> 01:00:39,440
Azt akarom, hogy a baloldalt, így ** tree.left lesz a bal oldalon.

789
01:00:39,440 --> 01:00:41,900
És azt akarjuk, hogy a mutató a dolog

790
01:00:41,900 --> 01:00:44,930
hogy ha a bal végül is a null pointer,

791
01:00:44,930 --> 01:00:48,360
Én lehet módosítani, hogy mutasson az új csomópont.

792
01:00:48,360 --> 01:00:51,460
>> És a másik esetben is nagyon hasonló.

793
01:00:51,460 --> 01:00:55,600
Nézzük ténylegesen, hogy az én háromkomponensű most.

794
01:00:55,600 --> 01:01:04,480
Helyezze be az értéket, ha értéke <(** fa). Értéket.

795
01:01:04,480 --> 01:01:11,040
Aztán szeretnénk frissíteni a ** a baloldalt,

796
01:01:11,040 --> 01:01:17,030
mást szeretnénk frissíteni a ** jobbra.

797
01:01:17,030 --> 01:01:22,540
[Student] Ez azt kap a mutatót a mutató?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Emlékezz arra, hogy - ** tree.right egy csomópont csillag.

799
01:01:30,940 --> 01:01:35,040
[Diák, érthetetlen] >> Igen.

800
01:01:35,040 --> 01:01:41,140
** Tree.right olyan, mint ez a mutató, vagy valami.

801
01:01:41,140 --> 01:01:45,140
Így azáltal, hogy egy mutatót, hogy ez ad nekem, amit akarok

802
01:01:45,140 --> 01:01:50,090
A mutató a fickó.

803
01:01:50,090 --> 01:01:54,260
[Student] Mehetünk újra, hogy miért használ a két mutató?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Igen. Így - nem, csak tudod, és ezt a megoldást, mielőtt

805
01:01:58,220 --> 01:02:04,540
volt a módja, hogy anélkül, hogy 2 mutatók.

806
01:02:04,540 --> 01:02:08,740
Be kell, hogy képes legyen megérteni, hogy a két mutató,

807
01:02:08,740 --> 01:02:11,660
és ez egy tisztább megoldás.

808
01:02:11,660 --> 01:02:16,090
Emellett észre, hogy mi történik, ha a fa -

809
01:02:16,090 --> 01:02:24,480
mi történik, ha a root volt null? Mi történik, ha nem ebben az esetben itt?

810
01:02:24,480 --> 01:02:30,540
Szóval node * root = NULL, helyezze a 4. és root.

811
01:02:30,540 --> 01:02:35,110
Mi gyökér lesz ezután?

812
01:02:35,110 --> 01:02:37,470
[Diák, érthetetlen] >> Igen.

813
01:02:37,470 --> 01:02:41,710
Root érték lesz 4.

814
01:02:41,710 --> 01:02:45,510
Root balra lesz null a root jogot lesz null.

815
01:02:45,510 --> 01:02:49,490
Abban az esetben, ha már nem felelt meg a gyökér a cím,

816
01:02:49,490 --> 01:02:52,490
nem tudtunk módosítani root.

817
01:02:52,490 --> 01:02:56,020
Abban az esetben, ha a fa - ahol gyökér volt null,

818
01:02:56,020 --> 01:02:58,410
mi csak vissza kellett térnie hamis. Semmit sem tehetünk.

819
01:02:58,410 --> 01:03:01,520
Nem tudjuk beilleszteni a csomópont egy üres fa.

820
01:03:01,520 --> 01:03:06,810
De most már tudjuk, mi csak, hogy egy üres fát egy csomópont fa.

821
01:03:06,810 --> 01:03:13,400
Ami általában a várt módon, hogy úgy kéne dolgozni.

822
01:03:13,400 --> 01:03:21,610
>> Továbbá, ez jóval rövidebb, mint

823
01:03:21,610 --> 01:03:26,240
is nyomon követi az anyavállalat, és így navigálhat le az összes utat.

824
01:03:26,240 --> 01:03:30,140
Most már a szüleim, és én csak az én szülő joga mutató az bármi.

825
01:03:30,140 --> 01:03:35,640
Ehelyett, ha ezt tette iteratív, lenne, ugyanezt a gondolatot egy while ciklus.

826
01:03:35,640 --> 01:03:38,100
De ahelyett, hogy foglalkozni szüleim mutató,

827
01:03:38,100 --> 01:03:40,600
ehelyett a jelenlegi mutató lenne a dolog

828
01:03:40,600 --> 01:03:43,790
hogy én közvetlenül módosítja, hogy pont az új csomópont.

829
01:03:43,790 --> 01:03:46,090
Nem kell foglalkozni, hogy ez mutat a bal oldalon.

830
01:03:46,090 --> 01:03:48,810
Nem kell foglalkozni, hogy ez jobbra mutató.

831
01:03:48,810 --> 01:04:00,860
Csak amit ez a mutató az, fogom beállítani, hogy mutasson az új csomópont.

832
01:04:00,860 --> 01:04:05,740
Mindenki érti, hogyan működik?

833
01:04:05,740 --> 01:04:09,460
Ha nem, miért akarunk csinálni így,

834
01:04:09,460 --> 01:04:14,920
de legalább ez működik, mint a megoldás?

835
01:04:14,920 --> 01:04:17,110
[Student] Hol vissza igaz?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Ez valószínűleg igaza van.

837
01:04:21,550 --> 01:04:26,690
Ha helyesen tegye vissza igaz.

838
01:04:26,690 --> 01:04:32,010
Else, ide megyünk vissza akar térni, amit betét visszatér.

839
01:04:32,010 --> 01:04:35,950
>> És mi van a különleges ebben a rekurzív függvény?

840
01:04:35,950 --> 01:04:43,010
Ez farok rekurzív, így ameddig fordítani némi optimalizálás,

841
01:04:43,010 --> 01:04:48,060
akkor felismeri azt, és soha nem lesz egy halom túlcsordulás e,

842
01:04:48,060 --> 01:04:53,230
akkor is, ha a fa van magassága 10.000 vagy 10 millió.

843
01:04:53,230 --> 01:04:55,630
[Diák, érthetetlen]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Azt hiszem, ez azt Dash - vagy mi optimalizálási szint

845
01:05:00,310 --> 01:05:03,820
szükség van a farok rekurziót el kell ismerni.

846
01:05:03,820 --> 01:05:09,350
Azt hiszem, elismeri - GCC és csenget

847
01:05:09,350 --> 01:05:12,610
is különböző jelentéssel való optimalizálás szintjét.

848
01:05:12,610 --> 01:05:17,870
Azt akarom mondani, hogy ez DashO 2, biztos, hogy felismeri farok rekurziót.

849
01:05:17,870 --> 01:05:27,880
De - meg tudná építeni, mint egy Fibonocci példa, vagy valami.

850
01:05:27,880 --> 01:05:30,030
Ez nem könnyű tesztelni ezt, mert nehéz építeni

851
01:05:30,030 --> 01:05:32,600
egy bináris fa, amely olyan nagy.

852
01:05:32,600 --> 01:05:37,140
De igen, azt hiszem, ez DashO 2, azaz

853
01:05:37,140 --> 01:05:40,580
ha fordítasz DashO 2, hogy fog kinézni a farok rekurzió

854
01:05:40,580 --> 01:05:54,030
és optimalizálja, hogy ki.

855
01:05:54,030 --> 01:05:58,190
Menjünk vissza - be szó szerint az utolsó dolog, amire szüksége van.

856
01:05:58,190 --> 01:06:04,900
Menjünk vissza a betétet ide

857
01:06:04,900 --> 01:06:07,840
hová megyünk, hogy tegyék ugyanezt a gondolatot.

858
01:06:07,840 --> 01:06:14,340
Ez lesz még a hibája az, hogy nem tudja teljes mértékben kezelni

859
01:06:14,340 --> 01:06:17,940
ha a gyökér maga null, vagy a múlt bejegyzés null,

860
01:06:17,940 --> 01:06:20,060
de ahelyett, hogy foglalkozik a szülő mutató,

861
01:06:20,060 --> 01:06:27,430
nézzük alkalmazzák ugyanazt a logikát tartása mutatókat mutatók.

862
01:06:27,430 --> 01:06:35,580
Ha itt tartjuk node ** akt,

863
01:06:35,580 --> 01:06:37,860
, és nem kell nyomon követni a jog többé,

864
01:06:37,860 --> 01:06:47,190
de node ** cur = & fa.

865
01:06:47,190 --> 01:06:54,800
És most mi while ciklus lesz, míg * akt nem egyenlő null.

866
01:06:54,800 --> 01:07:00,270
Nem kell, hogy nyomon követhesse a szülők többé.

867
01:07:00,270 --> 01:07:04,180
Nem kell nyomon követni a balra és jobbra.

868
01:07:04,180 --> 01:07:10,190
És én hívom temp, mert mi már használja temp.

869
01:07:10,190 --> 01:07:17,200
Oké. Tehát, ha (érték> * temp),

870
01:07:17,200 --> 01:07:24,010
akkor & (* temp) -> jobb

871
01:07:24,010 --> 01:07:29,250
más temp = & (* temp) -> balra.

872
01:07:29,250 --> 01:07:32,730
És most, ezen a ponton, ezt követően pedig hurok,

873
01:07:32,730 --> 01:07:36,380
Én csak ezt azért, mert talán könnyebb gondolkodni iteratív módon, mint a rekurzív

874
01:07:36,380 --> 01:07:39,010
de miután ez a while ciklus,

875
01:07:39,010 --> 01:07:43,820
* Temp a mutató akarunk változtatni.

876
01:07:43,820 --> 01:07:48,960
>> Mielőtt volt szülő, és azt akartuk változtatni bármelyik szülő balra vagy jobbra szülő,

877
01:07:48,960 --> 01:07:51,310
de ha meg akarjuk változtatni szülő jobb,

878
01:07:51,310 --> 01:07:54,550
akkor * temp van szülő joga, és meg tudjuk változtatni közvetlenül.

879
01:07:54,550 --> 01:08:05,860
Tehát itt, meg tudjuk csinálni * temp = newnode, és ennyi.

880
01:08:05,860 --> 01:08:09,540
Szóval hirdetmény minden, amit tett ez vegye ki sornyi kódot.

881
01:08:09,540 --> 01:08:14,770
Annak érdekében, hogy nyomon követhesse a szülő minden, ami további erőfeszítéseket igényel.

882
01:08:14,770 --> 01:08:18,689
Itt, ha csak nyomon követi a mutatót a mutatót,

883
01:08:18,689 --> 01:08:22,990
és még ha azt akartuk, hogy megszabaduljon az összes ilyen kapcsos zárójelek most,

884
01:08:22,990 --> 01:08:27,170
azt a látszatot rövidebb.

885
01:08:27,170 --> 01:08:32,529
Ez most pontosan ugyanaz a megoldás,

886
01:08:32,529 --> 01:08:38,210
de kevesebb sornyi kódot.

887
01:08:38,210 --> 01:08:41,229
Miután elkezdte felismerve ezt érvényes megoldás,

888
01:08:41,229 --> 01:08:43,529
ez is könnyebb, mint a hasonló okból mintegy, oké,

889
01:08:43,529 --> 01:08:45,779
miért van ez a flag at int ugye?

890
01:08:45,779 --> 01:08:49,290
Mit jelent ez? Oh, ez jelezve, hogy

891
01:08:49,290 --> 01:08:51,370
minden alkalommal, amikor elindulsz jobbra, azt kell beállítani,

892
01:08:51,370 --> 01:08:53,819
else if elmegyek maradt azt kell beállítani, hogy nulla.

893
01:08:53,819 --> 01:09:04,060
Itt nem kell ok, arról, hogy ez csak könnyebb gondolkodni.

894
01:09:04,060 --> 01:09:06,710
Kérdései vannak?

895
01:09:06,710 --> 01:09:16,290
[Diák, érthetetlen] >> Igen.

896
01:09:16,290 --> 01:09:23,359
Oké, az utolsó bit -

897
01:09:23,359 --> 01:09:28,080
Azt hiszem, egy gyors és egyszerű a funkció, amit tehetünk az,

898
01:09:28,080 --> 01:09:34,910
let's - együtt, azt hiszem, próbálja levelet tartalmaz függvényt

899
01:09:34,910 --> 01:09:38,899
ami nem érdekli, hogy ez egy bináris keresési fa.

900
01:09:38,899 --> 01:09:43,770
Ez tartalmazza a függvény visszatérési értéke true

901
01:09:43,770 --> 01:09:58,330
Ha bárhol az általános bináris fa az érték keresünk.

902
01:09:58,330 --> 01:10:02,520
Úgyhogy első csináljuk rekurzívan aztán megcsináljuk iteratív.

903
01:10:02,520 --> 01:10:07,300
Mi lehet valójában csak együtt csináljuk, mert ez lesz nagyon rövid.

904
01:10:07,300 --> 01:10:11,510
>> Mi az én alapeset lesz?

905
01:10:11,510 --> 01:10:13,890
[Diák, érthetetlen]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Tehát, ha (fa == NULL), akkor mi van?

907
01:10:18,230 --> 01:10:22,740
[Student] Vissza hamis.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, nos, nem kell a mást.

909
01:10:26,160 --> 01:10:30,250
Ha az volt a másik alapeset.

910
01:10:30,250 --> 01:10:32,450
[Student] Tree érték? >> Igen.

911
01:10:32,450 --> 01:10:36,430
Tehát, ha (fa-> érték == értéket.

912
01:10:36,430 --> 01:10:39,920
Figyeljük meg vagyunk vissza node *, nem node ** s?

913
01:10:39,920 --> 01:10:42,990
Tartalom soha nem kell használni a node **,

914
01:10:42,990 --> 01:10:45,480
mivel mi nem módosítja mutatók.

915
01:10:45,480 --> 01:10:50,540
Mi csak áthaladó őket.

916
01:10:50,540 --> 01:10:53,830
Ha ez megtörténik, akkor vissza akarnak térni igaz.

917
01:10:53,830 --> 01:10:58,270
Else szeretnénk keresztezik a gyerekeket.

918
01:10:58,270 --> 01:11:02,620
Tehát nem lehet érvelni arról, hogy mindent a bal kevésbé

919
01:11:02,620 --> 01:11:05,390
és minden jobbra nagyobb.

920
01:11:05,390 --> 01:11:09,590
Szóval, mi a feltétele lesz itt - vagy, mit fogunk csinálni?

921
01:11:09,590 --> 01:11:11,840
[Diák, érthetetlen] >> Igen.

922
01:11:11,840 --> 01:11:17,400
Return tartalmaz (érték, fa-> bal)

923
01:11:17,400 --> 01:11:26,860
illetve tartalmaz (érték, fa-> jobbra). És ennyi.

924
01:11:26,860 --> 01:11:29,080
És észre némi rövidzárlat-értékelés,

925
01:11:29,080 --> 01:11:32,520
ahol ha úgy látjuk, az értéket a bal oldali fa,

926
01:11:32,520 --> 01:11:36,820
soha nem kell nézni a jobb fa.

927
01:11:36,820 --> 01:11:40,430
Ez a teljes funkció.

928
01:11:40,430 --> 01:11:43,690
Most csináljuk iteratív,

929
01:11:43,690 --> 01:11:48,060
ami lesz kevésbé szép.

930
01:11:48,060 --> 01:11:54,750
Elvisszük a szokásos kezdete node * cur = fa.

931
01:11:54,750 --> 01:12:03,250
Míg a (akt! = NULL).

932
01:12:03,250 --> 01:12:08,600
Gyorsan fog látni a problémát.

933
01:12:08,600 --> 01:12:12,250
Ha akt - itt, ha valaha is kitörni ebből,

934
01:12:12,250 --> 01:12:16,020
akkor már elfogy a dolog, hogy nézd meg, így vissza hamis.

935
01:12:16,020 --> 01:12:24,810
Ha az (akt-> érték == érték), vissza igaz.

936
01:12:24,810 --> 01:12:32,910
Tehát most vagyunk egy helyen -

937
01:12:32,910 --> 01:12:36,250
nem tudjuk, hogy akarunk menni balra vagy jobbra.

938
01:12:36,250 --> 01:12:44,590
Szóval önkényesen, menjünk balra.

939
01:12:44,590 --> 01:12:47,910
Én nyilvánvalóan befut olyan kérdés, ahol én már teljesen felhagyott mindent -

940
01:12:47,910 --> 01:12:50,760
Én mindig csak ellenőrzi a bal oldalán egy fa.

941
01:12:50,760 --> 01:12:56,050
Soha nem fogom ellenőrizni semmit, hogy joga van a gyermek semmit.

942
01:12:56,050 --> 01:13:00,910
Hogyan tudom kijavítani ezt?

943
01:13:00,910 --> 01:13:05,260
[Student] Meg kell nyomon követni a jobb és a bal egy verem.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Igen. Szóval hogy ez

945
01:13:13,710 --> 01:13:32,360
struct lista node * n, majd a node ** a következő lépés?

946
01:13:32,360 --> 01:13:40,240
Úgy gondolom, hogy jól működik.

947
01:13:40,240 --> 01:13:45,940
Azt akarom, hogy a bal, vagy let's - itt.

948
01:13:45,940 --> 01:13:54,350
Struct lista list =, akkor kezdjük

949
01:13:54,350 --> 01:13:58,170
ki ez a struct listát.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Annak érdekében, hogy ez lesz a mi linkelt lista

951
01:14:04,040 --> 01:14:08,430
A részfák hogy már átugorja.

952
01:14:08,430 --> 01:14:13,800
Fogunk bejárására balra most

953
01:14:13,800 --> 01:14:17,870
de mivel elkerülhetetlenül kell, hogy térjen vissza a jobb,

954
01:14:17,870 --> 01:14:26,140
Megyünk, hogy a jobb oldali belső mi struct lista.

955
01:14:26,140 --> 01:14:32,620
Akkor mi lesz new_list vagy struct,

956
01:14:32,620 --> 01:14:41,080
struct lista *, new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Megyek mellőzni hibaellenőrző, de ellenőrizni kell, hogy ha ez a null.

958
01:14:44,920 --> 01:14:50,540
New_list a csomópontot, hogy fog mutatni -

959
01:14:50,540 --> 01:14:56,890
oh, ezért szerettem volna itt. Ez lesz, hogy pont egy második struct lista.

960
01:14:56,890 --> 01:15:02,380
Ez csak az, hogy hogyan kapcsolódik listák munkát.

961
01:15:02,380 --> 01:15:04,810
Ez ugyanaz, mint egy int láncolt lista

962
01:15:04,810 --> 01:15:06,960
kivéve, mi csak helyébe int a node *.

963
01:15:06,960 --> 01:15:11,040
Ez pontosan ugyanaz.

964
01:15:11,040 --> 01:15:15,100
Szóval new_list az érték a mi new_list csomópont,

965
01:15:15,100 --> 01:15:19,120
lesz akt-> jobbra.

966
01:15:19,120 --> 01:15:24,280
Az érték a mi new_list-> next lesz az eredeti listán,

967
01:15:24,280 --> 01:15:30,760
majd fogjuk frissíteni a listát, hogy pont new_list.

968
01:15:30,760 --> 01:15:33,650
>> Most arra van szükség valamilyen módon húzza a dolgokat,

969
01:15:33,650 --> 01:15:37,020
mint már áthaladt az egész bal oldali részfa.

970
01:15:37,020 --> 01:15:40,480
Most arra van szükség, hogy húzza cucc belőle,

971
01:15:40,480 --> 01:15:43,850
mint akt null, mi nem akarjuk, hogy csak vissza hamis.

972
01:15:43,850 --> 01:15:50,370
Azt akarjuk, hogy most húzni ezen kívül meg az új lista.

973
01:15:50,370 --> 01:15:53,690
Egy kényelmes módja ennek - nos, valóban, van több lehetőség kínálkozik.

974
01:15:53,690 --> 01:15:56,680
Bárki van egy javaslatom?

975
01:15:56,680 --> 01:15:58,790
Hol kell csinálni ezt, vagy hogyan kellene ezt csinálni?

976
01:15:58,790 --> 01:16:08,010
Már csak egy pár percig, de a javaslatok?

977
01:16:08,010 --> 01:16:14,750
Helyett - egy út, ahelyett a mi feltétel, míg,

978
01:16:14,750 --> 01:16:17,090
amit éppen nézi most nem nulla,

979
01:16:17,090 --> 01:16:22,340
ehelyett fogunk tovább menni, amíg a lista önmagában null.

980
01:16:22,340 --> 01:16:25,680
Tehát, ha a lista végül is null,

981
01:16:25,680 --> 01:16:30,680
akkor már elfogyott a dolgokat keresni, a keresés vége.

982
01:16:30,680 --> 01:16:39,860
De ez azt jelenti, hogy az első dolog, a mi listán csak megy, hogy az első csomópontot.

983
01:16:39,860 --> 01:16:49,730
A legelső dolog lesz - már nem kell látni.

984
01:16:49,730 --> 01:16:58,710
Szóval list-> n lesz a fa.

985
01:16:58,710 --> 01:17:02,860
list-> következő lesz null.

986
01:17:02,860 --> 01:17:07,580
És most, míg a lista nem egyenlő null.

987
01:17:07,580 --> 01:17:11,610
Cur fog húzni valamit a listából.

988
01:17:11,610 --> 01:17:13,500
Szóval akt fog egyenlő list-> n.

989
01:17:13,500 --> 01:17:20,850
És akkor a lista megy egyenlő lista-> n, vagy a lista-> next.

990
01:17:20,850 --> 01:17:23,480
Tehát, ha akt értéke megegyezik értéket.

991
01:17:23,480 --> 01:17:28,790
Most hozzá mind a jobb mutató és a bal mutató

992
01:17:28,790 --> 01:17:32,900
mindaddig, amíg ők nem null.

993
01:17:32,900 --> 01:17:36,390
Itt lent, azt hiszem, meg kellett volna tenni, hogy az első helyen.

994
01:17:36,390 --> 01:17:44,080
Ha az (akt-> jobb! = NULL)

995
01:17:44,080 --> 01:17:56,380
akkor fogjuk beszúrni a csomópont a mi listáját.

996
01:17:56,380 --> 01:17:59,290
Ha az (akt-> balra), ez egy kis extra munkát, de ez rendben van.

997
01:17:59,290 --> 01:18:02,690
Ha az (akt-> balra! = NULL),

998
01:18:02,690 --> 01:18:14,310
és megyünk be a bal oldalon a mi láncolt lista,

999
01:18:14,310 --> 01:18:19,700
és hogy kell azt.

1000
01:18:19,700 --> 01:18:22,670
Mi ismételget - mindaddig, amíg van valami a listán,

1001
01:18:22,670 --> 01:18:26,640
van egy másik csomópont nézni.

1002
01:18:26,640 --> 01:18:28,920
Szóval nézzük, hogy a csomópont,

1003
01:18:28,920 --> 01:18:31,390
mi előre A lista a következő egy.

1004
01:18:31,390 --> 01:18:34,060
Ha ez a csomópont az értéket keresünk, akkor vissza igaz.

1005
01:18:34,060 --> 01:18:37,640
Else be mind a bal és jobb oldali részfa,

1006
01:18:37,640 --> 01:18:40,510
mindaddig, amíg ők nem nulla, a mi lista

1007
01:18:40,510 --> 01:18:43,120
azért, hogy elkerülhetetlenül menjen át őket.

1008
01:18:43,120 --> 01:18:45,160
Tehát, ha nem volt null,

1009
01:18:45,160 --> 01:18:47,950
ha a gyökér pointer mutatott két dolgot,

1010
01:18:47,950 --> 01:18:51,670
majd először húzta ki valamit így a lista végül is null.

1011
01:18:51,670 --> 01:18:56,890
És akkor teszünk két dolgot vissza, így most a lista a 2-es méret.

1012
01:18:56,890 --> 01:19:00,030
Aztán megyünk loop vissza, és mi csak fog húzni,

1013
01:19:00,030 --> 01:19:04,250
mondjuk, a bal mutató a mi gyökér csomópont.

1014
01:19:04,250 --> 01:19:07,730
És ez akkor csak tartsa történik, és mi a végén hurok mindent.

1015
01:19:07,730 --> 01:19:11,280
>> Vegyük észre, hogy ez lényegesen bonyolultabb

1016
01:19:11,280 --> 01:19:14,160
A rekurzív megoldás.

1017
01:19:14,160 --> 01:19:17,260
És azt is mondtam többször

1018
01:19:17,260 --> 01:19:25,120
hogy a rekurzív megoldás általában sok közös az iteratív megoldás.

1019
01:19:25,120 --> 01:19:30,820
Itt pontosan ez az, amit a rekurzív megoldás csinál.

1020
01:19:30,820 --> 01:19:36,740
Az egyetlen változás az, hogy ahelyett, hogy hallgatólagosan a stack, a program verem,

1021
01:19:36,740 --> 01:19:40,840
mint a módja, hogy nyomon követhetőek, amit csomópont még mindig szükség van, hogy látogassa meg,

1022
01:19:40,840 --> 01:19:45,430
most már kifejezetten használni linkelt listát.

1023
01:19:45,430 --> 01:19:49,070
Mindkét esetben a nyomon követése, hogy mi csomópont kell még látogatható.

1024
01:19:49,070 --> 01:19:51,790
Abban az esetben, rekurzív ez csak könnyebb, mert egy halom

1025
01:19:51,790 --> 01:19:57,100
valósul meg az Ön számára, mint a program verem.

1026
01:19:57,100 --> 01:19:59,550
Vegyük észre, hogy ez a láncolt lista, ez egy verem.

1027
01:19:59,550 --> 01:20:01,580
Bármit is csak tedd a verem

1028
01:20:01,580 --> 01:20:09,960
azonnal mit fogunk, hogy húzza le a köteget, hogy látogassa meg a következő.

1029
01:20:09,960 --> 01:20:14,380
Elfogyott az idő, de a kérdése?

1030
01:20:14,380 --> 01:20:23,530
[Diák, érthetetlen]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Igen. Tehát, ha már a linkelt lista,

1032
01:20:27,790 --> 01:20:30,150
áram fog mutatni ez a fickó,

1033
01:20:30,150 --> 01:20:34,690
és most mi csak haladnak a linkelt listát, hogy összpontosítson ezt a fickót.

1034
01:20:34,690 --> 01:20:44,200
Mi áthaladó át a csatolt lista a sorban.

1035
01:20:44,200 --> 01:20:51,200
És akkor azt hiszem, meg kell szabadítani a linkelt lista és a cucc

1036
01:20:51,200 --> 01:20:53,880
egyszer, mielőtt visszatért igaz vagy hamis, meg kell

1037
01:20:53,880 --> 01:20:57,360
iterációkhoz a láncolt lista, és mindig itt, azt hiszem,

1038
01:20:57,360 --> 01:21:03,900
ha akt jog nem egyenlő, add meg, így most szeretnénk felszabadítani

1039
01:21:03,900 --> 01:21:09,600
akt, mert, nos, nem vagyunk teljesen felejtsd el a listát? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Szóval ez az, amit akarunk itt csinálni.

1041
01:21:12,880 --> 01:21:16,730
Hol van a mutató?

1042
01:21:16,730 --> 01:21:23,320
Cur volt akkor - azt akarjuk, hogy egy struct lista * 10 egyenlő melletti listában.

1043
01:21:23,320 --> 01:21:29,240
Free lista list = temp.

1044
01:21:29,240 --> 01:21:32,820
És abban az esetben, ha visszatérünk igaz, mi kell megismételni

1045
01:21:32,820 --> 01:21:37,050
át a fennmaradó mi linkelt lista felszabadítása dolgokat.

1046
01:21:37,050 --> 01:21:39,700
A szép dolog a rekurzív megoldás felszabadítja a dolgokat

1047
01:21:39,700 --> 01:21:44,930
csak azt jelenti, popping factorings ki a stack, amely meg fog történni az Ön számára.

1048
01:21:44,930 --> 01:21:50,720
Így már eltűnt valami, ami olyan, mint 3 sornyi nehezen hiszem, körülbelül kód

1049
01:21:50,720 --> 01:21:57,520
valami, ami lényegesen több a nehezen hiszem, körülbelül sornyi kódot.

1050
01:21:57,520 --> 01:22:00,620
Van még kérdés?

1051
01:22:00,620 --> 01:22:08,760
Rendben van. Jók vagyunk. Viszlát!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]