1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Secțiunea 7: mai confortabil]

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

3
00:00:05,090 --> 00:00:07,930
[Acest lucru este CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Bine. Deci, așa cum am spus în email-ul meu,

5
00:00:10,110 --> 00:00:14,060
acest lucru este mergi la a fi o secțiune binar-tree-intensiv.

6
00:00:14,060 --> 00:00:16,820
Dar nu sunt atât de multe întrebări.

7
00:00:16,820 --> 00:00:18,920
Deci, vom încerca să scoată fiecare întrebare

8
00:00:18,920 --> 00:00:25,430
și du-te în detalii dureroase a tuturor cele mai bune moduri de a face lucruri.

9
00:00:25,430 --> 00:00:31,200
Deci, chiar de la început, vom trece prin desene eșantion de copaci binare si alte chestii.

10
00:00:31,200 --> 00:00:35,970
Deci, aici, "Amintiți-vă că un arbore binar are noduri similare cu cele ale unei liste legate,

11
00:00:35,970 --> 00:00:38,150
cu excepția loc de un pointer sunt două: una pentru "copil" din stânga

12
00:00:38,150 --> 00:00:41,950
și unul pentru dreptul de "copil". "

13
00:00:41,950 --> 00:00:45,630
Deci, un arbore binar este la fel ca o listă legat,

14
00:00:45,630 --> 00:00:47,910
cu excepția struct va avea doi pointeri.

15
00:00:47,910 --> 00:00:51,390
E copaci trinary, care urmează să aibă trei indicii,

16
00:00:51,390 --> 00:00:56,540
există N-are copaci, care au doar un pointer generic

17
00:00:56,540 --> 00:01:00,320
că trebuie apoi să malloc să fie suficient de mare pentru a avea

18
00:01:00,320 --> 00:01:04,840
Pointeri suficiente pentru toți copiii posibile.

19
00:01:04,840 --> 00:01:08,200
Deci, arbore binar doar se întâmplă să aibă un număr constant de doi.

20
00:01:08,200 --> 00:01:11,260
Dacă doriți, puteți da o listă legat ca un copac unară,

21
00:01:11,260 --> 00:01:15,360
dar nu cred că cineva îl numește asta.

22
00:01:15,360 --> 00:01:18,060
"Desenați o diagramă Cutii-si-săgeți a unui nod arbore binar

23
00:01:18,060 --> 00:01:24,110
conținând numărul de preferat lui Nate, 7, în cazul în care fiecare copil indicatorul este nulă. "

24
00:01:24,110 --> 00:01:27,780
Deci, iPad modul.

25
00:01:27,780 --> 00:01:30,280
>> O să fie destul de simplu.

26
00:01:30,280 --> 00:01:36,150
Suntem doar de gând să aibă un nod, voi trage ca un pătrat.

27
00:01:36,150 --> 00:01:38,730
Și eu voi trage valorile aici.

28
00:01:38,730 --> 00:01:41,090
Deci, valoarea va merge aici,

29
00:01:41,090 --> 00:01:44,770
și apoi în jos aici, vom avea indicatorul stânga pe stânga și dreapta pe indicatorul din dreapta.

30
00:01:44,770 --> 00:01:50,430
Și este foarte mult, astfel convenție să-l numesc stânga și dreapta, numele indicatorului.

31
00:01:50,430 --> 00:01:52,460
Ambele dintre acestea sunt de gând să fie nul.

32
00:01:52,460 --> 00:01:57,870
Asta va fi doar nulă, și că va fi doar nul.

33
00:01:57,870 --> 00:02:03,630
Bine. Deci, înapoi la aici.

34
00:02:03,630 --> 00:02:05,700
"Cu o listă legată, am avut doar pentru a stoca un pointer

35
00:02:05,700 --> 00:02:09,639
la primul nod din lista, pentru a aminti întreaga listă legată, sau intreaga lista.

36
00:02:09,639 --> 00:02:11,650
De asemenea, cu copaci, avem doar pentru a stoca un pointer

37
00:02:11,650 --> 00:02:13,420
la un singur nod, în scopul de a aminti copac întreg.

38
00:02:13,420 --> 00:02:15,980
Acest nod este Calle "rădăcina" din copac.

39
00:02:15,980 --> 00:02:18,320
Să se bazeze pe diagrama dvs. din înainte de a desena sau de unul nou

40
00:02:18,320 --> 00:02:21,690
astfel că aveți o descriere Cutii-si-săgeți de un copac binar

41
00:02:21,690 --> 00:02:25,730
cu valoarea 7, apoi 3 în stânga,

42
00:02:25,730 --> 00:02:32,760
apoi 9 pe dreapta, și apoi 6 pe dreapta 3. "

43
00:02:32,760 --> 00:02:34,810
Să vedem dacă îmi amintesc toate că, în capul meu.

44
00:02:34,810 --> 00:02:37,670
Deci, acest lucru se va fi radacina noastra aici.

45
00:02:37,670 --> 00:02:41,600
Vom avea niște indicatorul undeva, ceva ce vom numi rădăcină,

46
00:02:41,600 --> 00:02:45,140
și se indică spre acest tip.

47
00:02:45,140 --> 00:02:48,490
Acum, pentru a face un nou nod,

48
00:02:48,490 --> 00:02:52,870
ceea ce avem, 3 pe partea stângă?

49
00:02:52,870 --> 00:02:57,140
Deci, un nou nod cu 3, și-l amintește inițial nule.

50
00:02:57,140 --> 00:02:59,190
Voi pune doar N.

51
00:02:59,190 --> 00:03:02,250
Acum vrem să facem ca merge la stânga 7.

52
00:03:02,250 --> 00:03:06,840
Deci, vom schimba acest indicator pentru a indica acum la acest tip.

53
00:03:06,840 --> 00:03:12,420
Și noi facem la fel. Ne dorim un 9 pe aici

54
00:03:12,420 --> 00:03:14,620
care, inițial, doar spune nul.

55
00:03:14,620 --> 00:03:19,600
Vom schimba acest indicator, punctul 9,

56
00:03:19,600 --> 00:03:23,310
și acum vrem să 6 la dreapta de 3.

57
00:03:23,310 --> 00:03:32,170
Deci, o să - face un 6.

58
00:03:32,170 --> 00:03:34,310
Și că tipul va indica acolo.

59
00:03:34,310 --> 00:03:38,320
Bine. Deci, asta e tot ce ne cere să facem.

60
00:03:38,320 --> 00:03:42,770
>> Acum hai să mergem peste unele terminologia.

61
00:03:42,770 --> 00:03:46,690
Am vorbit deja despre modul în rădăcina arborelui este nodul cel mai de sus în copac.

62
00:03:46,690 --> 00:03:54,720
Unul conținând 7. Nodurile de la partea de jos a arborelui se numesc frunze.

63
00:03:54,720 --> 00:04:01,240
Orice nod care are la fel ca și copiii săi nulă este o frunză.

64
00:04:01,240 --> 00:04:03,680
Deci, este posibil, în cazul în care copacul nostru binar este doar un singur nod,

65
00:04:03,680 --> 00:04:10,130
că un copac este o frunză, și asta e tot.

66
00:04:10,130 --> 00:04:12,060
"" Înălțime "a arborelui este numărul de hamei trebuie să facă

67
00:04:12,060 --> 00:04:16,620
pentru a obține din partea de sus a unei frunze. "

68
00:04:16,620 --> 00:04:18,640
Vom intra in, într-un al doilea, diferența

69
00:04:18,640 --> 00:04:21,940
între copaci echilibrate și neechilibrate binare,

70
00:04:21,940 --> 00:04:29,470
dar pentru moment, înălțimea totală a acestui copac

71
00:04:29,470 --> 00:04:34,520
Aș spune că este de 3, desi daca te numeri numărul de hamei

72
00:04:34,520 --> 00:04:39,710
trebuie să facă, în scopul de a ajunge la 9, atunci este într-adevăr doar o înălțime de 2.

73
00:04:39,710 --> 00:04:43,340
Chiar acum aceasta este un arbore binar dezechilibrat,

74
00:04:43,340 --> 00:04:49,840
dar vom vorbit despre echilibrată atunci când acesta devine a fi relevant.

75
00:04:49,840 --> 00:04:52,040
Deci, acum putem vorbi despre nodurile într-un copac din punct de vedere

76
00:04:52,040 --> 00:04:54,700
în raport cu alte noduri din arbore.

77
00:04:54,700 --> 00:04:59,730
Deci, acum avem părinți, copii, frați, strămoși, și a descendenților.

78
00:04:59,730 --> 00:05:05,650
Ele sunt destul de comune sens, ceea ce înseamnă acestea.

79
00:05:05,650 --> 00:05:09,610
Dacă ne întrebați - parintii sai.

80
00:05:09,610 --> 00:05:12,830
Deci, ce este mamă a 3?

81
00:05:12,830 --> 00:05:16,090
[Studenții] 7. Da >>. Mamă este doar de gând să fie ceea ce arată spre tine.

82
00:05:16,090 --> 00:05:20,510
Atunci de ce sunt copiii de la 7?

83
00:05:20,510 --> 00:05:23,860
Elevii [] 3 și 9. Da >>.

84
00:05:23,860 --> 00:05:26,460
Observați că "copiii" înseamnă, literal, copii,

85
00:05:26,460 --> 00:05:31,010
deci 6 nu s-ar aplica, pentru că e ca un nepot.

86
00:05:31,010 --> 00:05:35,540
Dar, apoi, dacă mergem descendenți, astfel încât ceea ce sunt descendenții 7?

87
00:05:35,540 --> 00:05:37,500
[Studenții] 3, 6 și 9. Da >>.

88
00:05:37,500 --> 00:05:42,330
Descendenți ai nodului radacina va fi totul în copac,

89
00:05:42,330 --> 00:05:47,950
cu excepția, poate nodul rădăcină în sine, în cazul în care nu doriți să ia în considerare faptul că un descendent.

90
00:05:47,950 --> 00:05:50,750
Și, în cele din urmă, strămoșii, așa că e în direcția opusă.

91
00:05:50,750 --> 00:05:55,740
Deci, ce sunt strămoșii din 6?

92
00:05:55,740 --> 00:05:58,920
Elevii [] 3 și 7. Da >>. 9 nu este inclus.

93
00:05:58,920 --> 00:06:02,520
E doar înapoi linia directa la rădăcină

94
00:06:02,520 --> 00:06:13,230
va fi strămoșii dumneavoastră.

95
00:06:13,230 --> 00:06:16,300
>> "Noi spunem că un arbore binar este" comandat ", în cazul în care pentru fiecare nod din arbore,

96
00:06:16,300 --> 00:06:19,530
toti descendentii sai de pe partea stângă au valori mai mici

97
00:06:19,530 --> 00:06:22,890
și toate cele de pe dreapta au valori mai mari.

98
00:06:22,890 --> 00:06:27,060
De exemplu, arborele de mai sus este ordonat, dar nu e posibilă doar aranjament ordonat. "

99
00:06:27,060 --> 00:06:30,180
Înainte de a ajunge la faptul că,

100
00:06:30,180 --> 00:06:36,420
un arbore binar ordonat este, de asemenea, cunoscut ca un arbore binar de căutare.

101
00:06:36,420 --> 00:06:38,660
Aici se întâmplă să fie numindu-l un arbore binar ordonat,

102
00:06:38,660 --> 00:06:41,850
dar nu am auzit numit un arbore binar ordonat înainte,

103
00:06:41,850 --> 00:06:46,650
și pe un test suntem mult mai probabil să afișezi arbore binar de căutare.

104
00:06:46,650 --> 00:06:49,250
Sunt unul și același,

105
00:06:49,250 --> 00:06:54,580
și este important să recunoaștem distincția între arbore binar și arbore binar de căutare.

106
00:06:54,580 --> 00:06:58,830
Un arbore binar este doar un copac care indică spre două lucruri.

107
00:06:58,830 --> 00:07:02,120
Fiecare nod indică două lucruri.

108
00:07:02,120 --> 00:07:06,310
Nu există nici raționamentul cu privire la valorile pe care le puncte la.

109
00:07:06,310 --> 00:07:11,370
Deci, ca aici, din moment ce este un arbore binar de căutare,

110
00:07:11,370 --> 00:07:14,030
știm că dacă vom merge plecat din 7,

111
00:07:14,030 --> 00:07:16,670
atunci toate valorile pe care le pot atinge, eventual,

112
00:07:16,670 --> 00:07:19,310
de a merge mai rămas din 7 trebuie să fie mai mică de 7.

113
00:07:19,310 --> 00:07:24,070
Observați că toate valorile sunt mai puțin de 7 3 și 6.

114
00:07:24,070 --> 00:07:26,040
Acestea sunt toate la stânga 7.

115
00:07:26,040 --> 00:07:29,020
Dacă mergem la dreptul de 7, tot ceea ce trebuie să fie mai mare de 7,

116
00:07:29,020 --> 00:07:33,220
9 este atât de la dreapta din 7, deci suntem bine.

117
00:07:33,220 --> 00:07:36,150
Acest lucru nu este cazul pentru un arbore binar,

118
00:07:36,150 --> 00:07:40,020
pentru un arbore binar regulat, putem avea doar 3 la partea de sus, 7 la stânga,

119
00:07:40,020 --> 00:07:47,630
9 la stânga 7; nu există nici un fel de ordonare a valorilor.

120
00:07:47,630 --> 00:07:56,140
Acum, nu vom face de fapt acest lucru pentru că e plictisitor și inutil,

121
00:07:56,140 --> 00:07:59,400
dar "încearcă să atragă cât mai multe copaci ordonate după cum puteți gândi

122
00:07:59,400 --> 00:08:01,900
folosind 7 numere, 3, 9, și 6.

123
00:08:01,900 --> 00:08:06,800
Câte acorduri distincte sunt acolo? Care este înălțimea de fiecare? "

124
00:08:06,800 --> 00:08:10,480
>> Vom face un cuplu, dar ideea principală este,

125
00:08:10,480 --> 00:08:16,530
aceasta este în nici un fel o reprezentare unică a unui arbore binar care conține aceste valori.

126
00:08:16,530 --> 00:08:22,760
Tot ce avem nevoie este un arbore binar care conține 7, 3, 6, și 9.

127
00:08:22,760 --> 00:08:25,960
Un altul ar fi posibil, valabilă radacina este 3,

128
00:08:25,960 --> 00:08:30,260
du-te la stânga și e 6, du-te la stânga și este 7,

129
00:08:30,260 --> 00:08:32,730
du-te la stânga și e 9.

130
00:08:32,730 --> 00:08:36,169
Acesta este un perfect valabil arbore binar de căutare.

131
00:08:36,169 --> 00:08:39,570
Nu e de mare ajutor, pentru ca este la fel ca o listă legată

132
00:08:39,570 --> 00:08:43,750
și toate aceste indicii sunt doar nule.

133
00:08:43,750 --> 00:08:48,900
Dar este un copac validă. Da?

134
00:08:48,900 --> 00:08:51,310
[Student] Nu valorile trebuie să fie mai mare pe dreapta?

135
00:08:51,310 --> 00:08:56,700
Sau este aceasta -? Acestea >> Am vrut să merg în altă parte.

136
00:08:56,700 --> 00:09:00,960
Există, de asemenea - Da, hai să comutați asta.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Bine captură.

138
00:09:07,770 --> 00:09:11,730
Ea mai are încă să asculte ceea ce un arbore binar de căutare ar trebui să facă.

139
00:09:11,730 --> 00:09:15,650
Deci, totul pentru a stânga trebuie să fie mai mică decât orice nod dat.

140
00:09:15,650 --> 00:09:23,180
Am putea muta doar, să zicem, acest 6 și pune-l aici.

141
00:09:23,180 --> 00:09:26,880
Nu, nu putem. De ce am continui sa faci asta?

142
00:09:26,880 --> 00:09:35,350
Să facem - aici este de 6, aici este de 7, 6 puncte la 3.

143
00:09:35,350 --> 00:09:39,290
Acest lucru este valabil încă un arbore binar de căutare.

144
00:09:39,290 --> 00:09:49,260
Ce este greșit în cazul în care I - Să văd dacă pot veni cu un aranjament.

145
00:09:49,260 --> 00:09:52,280
Da, bine. Deci, ce este în neregulă cu acest copac?

146
00:09:52,280 --> 00:10:08,920
Cred că am dat deja un indiciu că există ceva în neregulă cu ea.

147
00:10:08,920 --> 00:10:14,430
De ce am continui sa faci asta?

148
00:10:14,430 --> 00:10:18,510
Bine. Acest lucru pare rezonabil.

149
00:10:18,510 --> 00:10:22,590
Dacă ne uităm la fiecare nod, cum ar fi 7, apoi la stânga 7 este un 3.

150
00:10:22,590 --> 00:10:24,960
Deci avem 3, lucru de dreapta de 3 este un 6.

151
00:10:24,960 --> 00:10:27,750
Și dacă te uiți la 6, lucru de dreapta 6 este un 9.

152
00:10:27,750 --> 00:10:30,910
Deci, de ce nu este aceasta o adresă de arbore binar de căutare?

153
00:10:30,910 --> 00:10:36,330
Elevii [] 9 este încă la stânga 7. Da >>.

154
00:10:36,330 --> 00:10:43,710
Acesta trebuie să fie adevărat că toate valorile pe care le poate ajunge, eventual, de a merge la stânga din 7 sunt mai puțin de 7.

155
00:10:43,710 --> 00:10:49,120
Dacă mergem plecat din 7, ajungem la 3 și putem obține încă la 6,

156
00:10:49,120 --> 00:10:52,520
putem obține încă la 9, dar prin ce a trecut mai puțin de 7,

157
00:10:52,520 --> 00:10:55,070
nu ar trebui să fie în măsură pentru a ajunge la un număr care este mai mare decât 7.

158
00:10:55,070 --> 00:10:59,830
Deci, acest lucru nu este valabil un arbore binar de căutare.

159
00:10:59,830 --> 00:11:02,330
>> Fratele meu a avut de fapt o întrebare de interviu

160
00:11:02,330 --> 00:11:07,760
care a fost practic acest lucru, pur și simplu cod ceva pentru a valida

161
00:11:07,760 --> 00:11:10,500
dacă un copac este un arbore binar de căutare,

162
00:11:10,500 --> 00:11:13,580
și astfel primul lucru pe care la făcut a fost doar verificați pentru a vedea

163
00:11:13,580 --> 00:11:17,020
în cazul în care stânga și dreapta sunt corecte, iar apoi repeta acolo.

164
00:11:17,020 --> 00:11:19,700
Dar tu nu poți face asta doar, trebuie să țină evidența

165
00:11:19,700 --> 00:11:22,550
de faptul că acum că am plecat plecat din 7,

166
00:11:22,550 --> 00:11:26,340
totul în acest subarbore trebuie să fie mai mică de 7.

167
00:11:26,340 --> 00:11:28,430
Algoritmul corectă trebuie să țină evidența

168
00:11:28,430 --> 00:11:35,970
de limitele pe care valorile pot cădea, eventual inch

169
00:11:35,970 --> 00:11:38,360
Noi nu va trece prin toate.

170
00:11:38,360 --> 00:11:41,630
Există o relație frumoasă recurență,

171
00:11:41,630 --> 00:11:44,810
deși nu am ajuns la cei, sau nu vom ajunge la cei,

172
00:11:44,810 --> 00:11:47,030
definirea cât de multe sunt de fapt.

173
00:11:47,030 --> 00:11:53,180
Deci, există 14 dintre ele.

174
00:11:53,180 --> 00:11:56,020
Ideea de modul în care v-ați putea face matematic este ca,

175
00:11:56,020 --> 00:11:59,770
puteți alege orice unul singur pentru a fi nodul rădăcină,

176
00:11:59,770 --> 00:12:03,160
și apoi, dacă am alege 7 pentru a fi nodul rădăcină,

177
00:12:03,160 --> 00:12:08,150
atunci există, să zicem, unele numere care pot merge fi nodul meu stâng,

178
00:12:08,150 --> 00:12:10,440
și există unele numere care pot fi nodul meu drept,

179
00:12:10,440 --> 00:12:15,090
dar dacă n-am numărul total, atunci suma care poate merge la stânga

180
00:12:15,090 --> 00:12:18,820
plus suma care poate merge la dreapta este n - 1.

181
00:12:18,820 --> 00:12:26,130
Deci, din numerele rămase, acestea trebuie să fie în măsură de a merge, fie la stânga sau la dreapta.

182
00:12:26,130 --> 00:12:31,580
Se pare dificil ca, în cazul în care am pus 3 primul, apoi totul trebuie să meargă la stânga,

183
00:12:31,580 --> 00:12:35,080
dar daca am pus 7, atunci unele lucruri pot merge la stânga și unele lucruri pot merge la dreapta.

184
00:12:35,080 --> 00:12:39,570
Și prin '3 'început, am vrut tot ce pot merge la dreapta.

185
00:12:39,570 --> 00:12:42,350
E adevarat, trebuie doar să se gândească la ea ca,

186
00:12:42,350 --> 00:12:47,980
cât de multe lucruri pot merge la următorul nivel al arborelui.

187
00:12:47,980 --> 00:12:50,420
Și iese să fie 14; sau puteti desena toate acestea,

188
00:12:50,420 --> 00:12:54,650
și apoi veți obține 14.

189
00:12:54,650 --> 00:13:01,120
>> Mergând înapoi aici,

190
00:13:01,120 --> 00:13:03,510
"Copaci ordonate binare sunt cool, deoarece putem căuta prin intermediul lor

191
00:13:03,510 --> 00:13:06,910
într-un mod foarte asemănător cu căutarea într-o matrice sortate.

192
00:13:06,910 --> 00:13:10,120
Pentru a face acest lucru, vom începe de la rădăcină și să lucreze drumul nostru în jos copac

193
00:13:10,120 --> 00:13:13,440
spre frunze, verificarea valorilor fiecare nod împotriva valorilor pe care le căutați.

194
00:13:13,440 --> 00:13:15,810
Dacă valoarea nodul curent este mai mică decât valoarea căutăm,

195
00:13:15,810 --> 00:13:18,050
te duci lângă copilului nodul are dreptate.

196
00:13:18,050 --> 00:13:20,030
În caz contrar, te duci la copil nodului din stânga.

197
00:13:20,030 --> 00:13:22,800
La un moment dat, veți găsi fie valoarea pe care îl căutați pentru, sau vei alerga intr-o nulă,

198
00:13:22,800 --> 00:13:28,520
indicând valoarea nu e în copac. "

199
00:13:28,520 --> 00:13:32,450
Trebuie să aspira copac am avut-o înainte, că va lua o secundă.

200
00:13:32,450 --> 00:13:38,280
Dar vrem să se uite în sus dacă 6, 10, și 1 sunt în copac.

201
00:13:38,280 --> 00:13:49,180
Deci, ceea ce a fost, 7, 9, 3, 6. Bine.

202
00:13:49,180 --> 00:13:52,730
Numerele pe care doriți să te uiți în sus, vrem să te uiți în sus 6.

203
00:13:52,730 --> 00:13:55,440
Cum functioneaza acest algoritm?

204
00:13:55,440 --> 00:14:03,040
Ei bine, avem, de asemenea, unele indicatorul rădăcină la copacul nostru.

205
00:14:03,040 --> 00:14:12,460
Și ne-ar merge la rădăcină și să spunem, această valoare este egală cu valoarea pe care o căutați?

206
00:14:12,460 --> 00:14:15,000
Deci, suntem în căutarea de 6, asa ca nu e egal.

207
00:14:15,000 --> 00:14:20,140
Deci, vom continua, iar acum spunem, ok, deci 6 este mai mică de 7.

208
00:14:20,140 --> 00:14:23,940
Asta înseamnă că vrem să mergem la stânga, sau nu vrem să mergem la dreapta?

209
00:14:23,940 --> 00:14:27,340
[Student] Left. Da >>.

210
00:14:27,340 --> 00:14:33,340
E mult mai ușor, tot ce trebuie să faceți este să atragă un nod posibilă copac

211
00:14:33,340 --> 00:14:37,760
si apoi nu - în loc de a încerca să se gândească în capul tău,

212
00:14:37,760 --> 00:14:40,020
ok, daca e mai putin, nu mă duc la stânga sau la dreapta du-te,

213
00:14:40,020 --> 00:14:43,030
doar se uită la această imagine, este foarte clar că trebuie să mă duc la stânga

214
00:14:43,030 --> 00:14:47,700
în cazul în care acest nod este mai mare decât valoarea pe care îl caut.

215
00:14:47,700 --> 00:14:52,600
Deci, te duci la stânga, acum sunt la 3.

216
00:14:52,600 --> 00:14:57,770
Vreau să - 3 este mai mică decât valoarea caut, care este de 6.

217
00:14:57,770 --> 00:15:03,420
Deci, mergem la dreapta, iar acum am ajuns la 6,

218
00:15:03,420 --> 00:15:07,380
care este valoarea caut, așa că am întoarce adevărat.

219
00:15:07,380 --> 00:15:15,760
Valoarea viitoare am de gând să caute este de 10.

220
00:15:15,760 --> 00:15:23,230
Bine. Deci 10, acum, este de gând să - taie, care - de gând să urmeze rădăcină.

221
00:15:23,230 --> 00:15:27,670
Acum, 10 va fi mai mare de 7, așa că vreau să te uiți la dreapta.

222
00:15:27,670 --> 00:15:31,660
Am de gând să vin aici, 10 va fi mai mare de 9,

223
00:15:31,660 --> 00:15:34,520
așa că am de gând să doriți să te uiți la dreapta.

224
00:15:34,520 --> 00:15:42,100
Am venit aici, dar aici, acum eu sunt la null.

225
00:15:42,100 --> 00:15:44,170
Ce trebuie să fac dacă am lovit nulă?

226
00:15:44,170 --> 00:15:47,440
[Student] Înapoi fals? Da >>. Nu am găsit 10.

227
00:15:47,440 --> 00:15:49,800
1 este de gând să fie un caz aproape identic,

228
00:15:49,800 --> 00:15:51,950
cu excepția faptului că e doar de gând să fie oglindită, în loc de a privi

229
00:15:51,950 --> 00:15:56,540
pe partea dreapta, am de gând să se uite în jos în partea stângă.

230
00:15:56,540 --> 00:16:00,430
>> Acum cred că vom ajunge de fapt la codul.

231
00:16:00,430 --> 00:16:04,070
Iată unde - deschide aparatul și să navigați CS50-ți de drum acolo,

232
00:16:04,070 --> 00:16:07,010
dar tu chiar poti face, de asemenea, că în spațiu.

233
00:16:07,010 --> 00:16:09,170
Este, probabil, ideal pentru a face acest lucru în spațiu,

234
00:16:09,170 --> 00:16:13,760
deoarece putem lucra în spațiu.

235
00:16:13,760 --> 00:16:19,170
"În primul rând avem nevoie de o definiție de tip nou pentru un nod arbore binar care conține valori int.

236
00:16:19,170 --> 00:16:21,400
Utilizarea șabloane typedef de mai jos,

237
00:16:21,400 --> 00:16:24,510
creați o definiție de tip nou pentru un nod într-un arbore binar.

238
00:16:24,510 --> 00:16:27,930
Dacă te blochezi. . . "Bla, bla, bla. Bine.

239
00:16:27,930 --> 00:16:30,380
Așa că hai să punem șabloane aici,

240
00:16:30,380 --> 00:16:41,630
typedef struct nod, nod și. Da, bine.

241
00:16:41,630 --> 00:16:44,270
Deci, ce sunt domeniile am de gând să doriți în nodul nostru?

242
00:16:44,270 --> 00:16:46,520
[Student] Int și apoi doi pointeri?

243
00:16:46,520 --> 00:16:49,700
Int >> valoare, doi pointeri? Cum pot scrie indicii?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. Ar trebui să >> zoom inch Da, așa nod struct * a plecat,

245
00:16:58,440 --> 00:17:01,320
și struct nod * dreapta.

246
00:17:01,320 --> 00:17:03,460
Și amintiți-vă discuția din ultimul timp,

247
00:17:03,460 --> 00:17:15,290
că acest lucru nu are sens, acest lucru nu are sens,

248
00:17:15,290 --> 00:17:18,270
acest lucru nu are sens.

249
00:17:18,270 --> 00:17:25,000
Ai nevoie de tot ce există, în scopul de a defini acest struct recursiv.

250
00:17:25,000 --> 00:17:27,970
Ok, deci asta e ceea ce copacul nostru va arăta.

251
00:17:27,970 --> 00:17:37,670
Dacă am un copac trinary, apoi un nod s-ar putea arata ca B1, B2, B3 struct nod *,

252
00:17:37,670 --> 00:17:43,470
unde b este o ramură - de fapt, am mai auzit-o la stânga, mijloc, dreapta, dar indiferent.

253
00:17:43,470 --> 00:17:55,610
Ne pasă doar despre binar, deci dreapta, stânga.

254
00:17:55,610 --> 00:17:59,110
"Acum, să declare o variabilă globală * nod pentru rădăcina arborelui."

255
00:17:59,110 --> 00:18:01,510
Deci, nu vom face asta.

256
00:18:01,510 --> 00:18:08,950
În scopul de a face lucrurile puțin mai dificil și mai generalizate,

257
00:18:08,950 --> 00:18:11,570
nu vom avea o variabilă globală nod.

258
00:18:11,570 --> 00:18:16,710
În schimb, în ​​principal ne vom declara toate lucrurile noduri,

259
00:18:16,710 --> 00:18:20,500
și asta înseamnă că de mai jos, atunci când vom începe să ruleze

260
00:18:20,500 --> 00:18:23,130
Funcția noastră conține și funcția noastră inserați,

261
00:18:23,130 --> 00:18:27,410
Conține în loc de noastre funcționează doar folosind această variabilă nod la nivel mondial,

262
00:18:27,410 --> 00:18:34,280
am de gând să-l ia ca avea un argument copac pe care ne-o dorim pentru a procesa.

263
00:18:34,280 --> 00:18:36,650
Având în variabila globală a fost trebuia să facă lucrurile mai ușor.

264
00:18:36,650 --> 00:18:42,310
Vom face lucrurile mai greu.

265
00:18:42,310 --> 00:18:51,210
Acum, ia un minut sau cam asa ceva doar pentru a face acest tip de lucru,

266
00:18:51,210 --> 00:18:57,690
în cazul în care în interiorul principal pe care doriți să creați acest copac, și asta e tot ce vrei să faci.

267
00:18:57,690 --> 00:19:04,530
Încercați și construi acest arbore în funcția principală.

268
00:19:42,760 --> 00:19:47,610
>> Bine. Deci, nu trebuie nici măcar să fi construit arborele tot drumul încă.

269
00:19:47,610 --> 00:19:49,840
Dar oricine are ceva ce ar putea trage în sus

270
00:19:49,840 --> 00:20:03,130
pentru a arăta modul în care s-ar putea începe construirea un astfel de copac?

271
00:20:03,130 --> 00:20:08,080
[Student] Cineva trage, încercând să iasă.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Oricine confortabil, cu construcții de copac lor?

273
00:20:13,100 --> 00:20:15,520
[Student] Sigur. Nu e gata. >> E bine. Putem termina doar -

274
00:20:15,520 --> 00:20:26,860
oh, poți să-l salvezi? Ura.

275
00:20:26,860 --> 00:20:32,020
Deci aici avem - Oh, mă taie ușor off.

276
00:20:32,020 --> 00:20:34,770
Sunt mărită?

277
00:20:34,770 --> 00:20:37,730
Măriți, derulați afară. >> Am o întrebare. Da >>?

278
00:20:37,730 --> 00:20:44,410
[Student] Când definiți struct, sunt lucruri cum ar fi inițializat la ceva?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nr >> Bine. Deci, va trebui să se inițializeze -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nr Când definiți, sau atunci când declară un struct,

281
00:20:50,450 --> 00:20:55,600
nu este inițializată în mod implicit, e la fel ca în cazul în care ați declara un int.

282
00:20:55,600 --> 00:20:59,020
E exact acelasi lucru. E ca și cum fiecare dintre domeniile sale individuale

283
00:20:59,020 --> 00:21:04,460
poate avea o valoare de gunoi în ea. Și >> este posibil să se definească - sau pentru a declara o struct

284
00:21:04,460 --> 00:21:07,740
într-un mod care le face inițializa?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Da. Deci, comenzi rapide de inițializare sintaxă

286
00:21:13,200 --> 00:21:18,660
este de gând să arate -

287
00:21:18,660 --> 00:21:22,200
Sunt două moduri prin care putem face acest lucru. Cred că ar trebui să-l compilați

288
00:21:22,200 --> 00:21:25,840
pentru a face să răsune-vă că, de asemenea, face acest lucru.

289
00:21:25,840 --> 00:21:28,510
Pentru a argumentelor care vine în struct,

290
00:21:28,510 --> 00:21:32,170
ai pus ca ordinea de argumente în interiorul acestor acolade.

291
00:21:32,170 --> 00:21:35,690
Deci, dacă doriți să-l inițializa la 9 și a lăsat să fie nul și apoi să fie nul dreapta,

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

293
00:21:41,570 --> 00:21:47,890
Alternativa este, iar editorul nu îi place această sintaxă,

294
00:21:47,890 --> 00:21:50,300
și crede că vreau un bloc nou,

295
00:21:50,300 --> 00:22:01,800
dar alternativa este ceva de genul -

296
00:22:01,800 --> 00:22:04,190
aici, am să-l pun pe o linie nouă.

297
00:22:04,190 --> 00:22:09,140
Poti spune în mod explicit, am uitat sintaxa exactă.

298
00:22:09,140 --> 00:22:13,110
Deci, vă puteți adresa în mod explicit le pe nume, și spune,

299
00:22:13,110 --> 00:22:21,570
C, sau. Valoare. = 9, stânga =. NULL.

300
00:22:21,570 --> 00:22:24,540
Bănuiesc că acestea ar trebui să fie virgule.

301
00:22:24,540 --> 00:22:29,110
. Dreapta = NULL, deci acest mod nu

302
00:22:29,110 --> 00:22:33,780
de fapt, trebuie să știe ordinea de struct,

303
00:22:33,780 --> 00:22:36,650
și atunci când sunteți de lectură acest lucru, este mult mai explicite

304
00:22:36,650 --> 00:22:41,920
despre ceea ce este valoarea fiind pregătit pentru a.

305
00:22:41,920 --> 00:22:44,080
>> Acest lucru se întâmplă să fie unul din lucrurile pe care -

306
00:22:44,080 --> 00:22:49,100
astfel, pentru cea mai mare parte, C + + este un superset a lui C.

307
00:22:49,100 --> 00:22:54,160
Puteți să luați cod C, mutați-l la C + +, și ar trebui să compileze.

308
00:22:54,160 --> 00:22:59,570
Acesta este unul dintre lucrurile pe care C + + nu acceptă, astfel încât oamenii au tendința de a nu-l face.

309
00:22:59,570 --> 00:23:01,850
Nu știu dacă asta e singurul motiv pentru care oamenii au tendința de a nu-l face,

310
00:23:01,850 --> 00:23:10,540
dar cazul în care am nevoie să-l folosească necesare pentru a lucra cu C + + si asa nu am putut folosi asta.

311
00:23:10,540 --> 00:23:14,000
Un alt exemplu de ceva care nu funcționează cu C + + este

312
00:23:14,000 --> 00:23:16,940
cum malloc returnează un "void *," punct de vedere tehnic,

313
00:23:16,940 --> 00:23:20,200
dar ai putea spune doar char * x = indiferent de malloc,

314
00:23:20,200 --> 00:23:22,840
și va fi în mod automat pentru a arunca un char *.

315
00:23:22,840 --> 00:23:25,450
Asta exprimate automată nu se întâmplă în C + +.

316
00:23:25,450 --> 00:23:28,150
Asta nu s-ar compila, și v-ar trebui să spun în mod explicit

317
00:23:28,150 --> 00:23:34,510
char *, malloc, oricare ar fi, să-l arunce într-o char *.

318
00:23:34,510 --> 00:23:37,270
Nu sunt multe lucruri pe care C și C + + nu sunt de acord cu privire,

319
00:23:37,270 --> 00:23:40,620
dar acestea sunt două.

320
00:23:40,620 --> 00:23:43,120
Deci, vom merge cu această sintaxă.

321
00:23:43,120 --> 00:23:46,150
Dar, chiar dacă nu ne-am dus cu sintaxa,

322
00:23:46,150 --> 00:23:49,470
ceea ce este - ar putea fi în neregulă cu asta?

323
00:23:49,470 --> 00:23:52,170
[Student] nu am nevoie să-l dereference? Da >>.

324
00:23:52,170 --> 00:23:55,110
Amintiți-vă că săgeata are un dereference implicită,

325
00:23:55,110 --> 00:23:58,230
și așa că atunci când suntem doar de-a face cu o struct,

326
00:23:58,230 --> 00:24:04,300
vrem sa folosim. pentru a ajunge la o în interiorul câmpului de struct.

327
00:24:04,300 --> 00:24:07,200
Și singura dată când am folosi săgeata este atunci când vrem să facem -

328
00:24:07,200 --> 00:24:13,450
bine, săgeata este echivalent cu -

329
00:24:13,450 --> 00:24:17,020
asta e ceea ce ar fi însemnat dacă am folosit săgeată.

330
00:24:17,020 --> 00:24:24,600
Toate mijloacele săgeata este, dereference asta, acum eu sunt la o struct, și eu pot obține teren.

331
00:24:24,600 --> 00:24:28,040
Obține fie direct în câmp sau dereference și pentru a obține teren -

332
00:24:28,040 --> 00:24:30,380
Cred că acest lucru ar trebui să fie o valoare.

333
00:24:30,380 --> 00:24:33,910
Dar aici am de-a face doar cu o struct, nu un pointer la o structura,

334
00:24:33,910 --> 00:24:38,780
și deci nu pot folosi săgeată.

335
00:24:38,780 --> 00:24:47,510
Dar acest fel de lucru pe care îl putem face pentru toate nodurile.

336
00:24:47,510 --> 00:24:55,790
Oh, Doamne.

337
00:24:55,790 --> 00:25:09,540
Acest lucru este de 6, 7, și 3.

338
00:25:09,540 --> 00:25:16,470
Atunci putem configura sucursale în copacul nostru, putem avea 7 -

339
00:25:16,470 --> 00:25:21,650
Putem avea, stanga ar trebui să arate la 3.

340
00:25:21,650 --> 00:25:25,130
Deci, cum facem asta?

341
00:25:25,130 --> 00:25:29,320
[Elevii, neinteligibil] >> Da. Adresa de node3,

342
00:25:29,320 --> 00:25:34,170
și dacă nu aveți adresa, atunci pur și simplu nu s-ar compila.

343
00:25:34,170 --> 00:25:38,190
Dar amintiți-vă că acestea sunt pointeri la nodurile următoare.

344
00:25:38,190 --> 00:25:44,930
Drept ar trebui să arate la 9,

345
00:25:44,930 --> 00:25:53,330
și 3 ar trebui să arate pe dreapta la 6.

346
00:25:53,330 --> 00:25:58,480
Cred că asta este totul setat. Orice comentarii sau întrebări?

347
00:25:58,480 --> 00:26:02,060
[Student, neinteligibil] rădăcină va fi 7.

348
00:26:02,060 --> 00:26:08,210
Noi putem spune doar nod * ptr =

349
00:26:08,210 --> 00:26:14,160
sau rădăcină, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Pentru scopurile noastre, vom fi de-a face cu inserție,

351
00:26:20,730 --> 00:26:25,490
așa că de gând să doriți să scrie o funcție pentru a insera în acest arbore binar

352
00:26:25,490 --> 00:26:34,230
și inserția este inevitabil va suna malloc pentru a crea un nod nou pentru acest copac.

353
00:26:34,230 --> 00:26:36,590
Deci, lucrurile sunt mergi la a lua murdar cu faptul că unele noduri

354
00:26:36,590 --> 00:26:38,590
sunt în prezent pe stivă

355
00:26:38,590 --> 00:26:43,680
și alte noduri de gând să se încheie pe movila atunci când le introduceți.

356
00:26:43,680 --> 00:26:47,640
Acest lucru este perfect valabil, dar singurul motiv

357
00:26:47,640 --> 00:26:49,600
suntem capabili să facă acest lucru pe stivă

358
00:26:49,600 --> 00:26:51,840
se datorează faptului că este un astfel de exemplu contrived că știm

359
00:26:51,840 --> 00:26:56,360
copac ar trebui să fie construite în așa fel 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Dacă nu am avea acest lucru, atunci nu ne-ar trebui să malloc în primul rând.

361
00:27:02,970 --> 00:27:06,160
După cum vom vedea un pic mai târziu, ar trebui să ne malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Chiar acum e perfect rezonabil pentru a pune în stivă,

363
00:27:08,570 --> 00:27:14,750
dar hai să schimbăm acest lucru să o implementare malloc.

364
00:27:14,750 --> 00:27:17,160
Deci, fiecare dintre acestea este acum va fi ceva de genul

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

366
00:27:24,240 --> 00:27:28,040
Și acum vom avea de a face check nostru.

367
00:27:28,040 --> 00:27:34,010
în cazul în care (node9 == NULL) - N-am vrut asta -

368
00:27:34,010 --> 00:27:40,950
întoarcă 1, și apoi putem face node9-> pentru ca acum e un pointer,

369
00:27:40,950 --> 00:27:45,300
valoare = 6, node9-> left = NULL,

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

371
00:27:48,930 --> 00:27:51,410
și am de gând să aibă de a face acest lucru, pentru fiecare dintre aceste noduri.

372
00:27:51,410 --> 00:27:57,490
Deci, în loc, să-l pună în interiorul unei funcții separate.

373
00:27:57,490 --> 00:28:00,620
Să-i spunem nod * build_node,

374
00:28:00,620 --> 00:28:09,050
și acest lucru este oarecum similar cu API-uri noi oferim pentru codare Huffman.

375
00:28:09,050 --> 00:28:12,730
Noi vă oferim funcții de inițializare pentru un copac

376
00:28:12,730 --> 00:28:20,520
și Deconstructor "funcții" pentru acele copaci și aceleași pentru pădurilor.

377
00:28:20,520 --> 00:28:22,570
>> Deci, aici vom avea o funcție de inițializare

378
00:28:22,570 --> 00:28:25,170
pentru a construi doar un nod pentru noi.

379
00:28:25,170 --> 00:28:29,320
Și se va arata destul de mult exact ca asta.

380
00:28:29,320 --> 00:28:32,230
Iar eu chiar o să fie leneș și nu schimbați numele variabilei,

381
00:28:32,230 --> 00:28:34,380
chiar dacă node9 are nici un sens mai.

382
00:28:34,380 --> 00:28:38,610
Oh, cred că valoarea node9 nu ar fi fost 6.

383
00:28:38,610 --> 00:28:42,800
Acum ne putem întoarce node9.

384
00:28:42,800 --> 00:28:49,550
Și aici ar trebui să ne intoarce null.

385
00:28:49,550 --> 00:28:52,690
Toata lumea de acord cu faptul că funcția Build-a-nod?

386
00:28:52,690 --> 00:28:59,780
Deci, acum putem apela doar că pentru a construi orice nod cu o anumită valoare și pointeri nule.

387
00:28:59,780 --> 00:29:09,750
Acum putem spune așa, putem face nod * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Și să facem. . .

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

390
00:29:33,980 --> 00:29:39,330
Și acum vrem să înființeze pointerii aceleași,

391
00:29:39,330 --> 00:29:42,470
cu excepția acum totul e deja în termeni de pointeri

392
00:29:42,470 --> 00:29:48,480
astfel încât nu mai este nevoie de adresa.

393
00:29:48,480 --> 00:29:56,300
Bine. Deci, ce e ultimul lucru pe care vreau să fac?

394
00:29:56,300 --> 00:30:03,850
E o eroare de verificare pe care eu nu fac.

395
00:30:03,850 --> 00:30:06,800
Ce înseamnă a construi retur nod?

396
00:30:06,800 --> 00:30:11,660
[Student, neinteligibil] >> Da. În cazul în care nu a reușit malloc, aceasta va intoarce null.

397
00:30:11,660 --> 00:30:16,460
Așa că am de gând să-l alene aici jos în loc de a face o condiție pentru fiecare.

398
00:30:16,460 --> 00:30:22,320
În cazul în care (node9 == NULL, sau - mai simplu,

399
00:30:22,320 --> 00:30:28,020
acest lucru este echivalent cu doar dacă nu node9.

400
00:30:28,020 --> 00:30:38,310
Deci, dacă nu node9, sau nu node6, sau nu node3, sau nu node7, întoarce 1.

401
00:30:38,310 --> 00:30:42,850
Poate că ar trebui să imprimați malloc nu a reușit, sau ceva de genul.

402
00:30:42,850 --> 00:30:46,680
[Student] este fals: egal cu zero, precum și?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Orice valoare zero este falsă.

404
00:30:51,290 --> 00:30:53,920
Deci, nul este o valoare zero.

405
00:30:53,920 --> 00:30:56,780
Zero este o valoare zero. Fals este o valoare zero.

406
00:30:56,780 --> 00:31:02,130
Orice - destul de mult de la numai 2 valori zero sunt nule și zero,

407
00:31:02,130 --> 00:31:07,900
fals este la fel de distribuire definit ca zero.

408
00:31:07,900 --> 00:31:13,030
Asta se aplică și dacă noi declarăm variabila globala.

409
00:31:13,030 --> 00:31:17,890
Dacă am fi avut * rădăcină nodul aici,

410
00:31:17,890 --> 00:31:24,150
apoi - lucru frumos despre variabile globale este că ei au întotdeauna o valoare inițială.

411
00:31:24,150 --> 00:31:27,500
Asta nu e adevărat de funcții, cum în interiorul aici,

412
00:31:27,500 --> 00:31:34,870
daca avem, cum ar fi *, nod sau nod x.

413
00:31:34,870 --> 00:31:37,380
Nu avem nici o idee despre ceea ce x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
sau am putea să le imprimați și acestea ar putea fi arbitrară.

415
00:31:40,700 --> 00:31:44,980
Asta nu-i adevărat de variabile globale.

416
00:31:44,980 --> 00:31:47,450
Deci, radacina nod sau nod x.

417
00:31:47,450 --> 00:31:53,410
În mod implicit, tot ceea ce este la nivel mondial, în cazul în care nu este explicit inițializat la o anumită valoare,

418
00:31:53,410 --> 00:31:57,390
are o valoare zero ca valoare.

419
00:31:57,390 --> 00:32:01,150
Deci, aici, radacina nod *, noi nu inițializa în mod explicit la ceva,

420
00:32:01,150 --> 00:32:06,350
astfel încât valoarea sa implicită va fi nul, care este valoarea de zero de pointeri.

421
00:32:06,350 --> 00:32:11,870
Valoarea implicită a lui x este de gând să înseamnă că x.value este zero,

422
00:32:11,870 --> 00:32:14,260
x.left este nul, iar x.right este nul.

423
00:32:14,260 --> 00:32:21,070
Deci, din moment ce este o struct, toate domeniile de struct va fi zero valori.

424
00:32:21,070 --> 00:32:24,410
Nu avem nevoie să utilizați că aici, deși.

425
00:32:24,410 --> 00:32:27,320
[Student] Cele struct sunt diferite de alte variabile, precum și alte variabile sunt

426
00:32:27,320 --> 00:32:31,400
Valorile de gunoi, acestea sunt zerouri?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Alte valori prea. Deci, în x, x va fi zero.

428
00:32:36,220 --> 00:32:40,070
Dacă e de la domeniul de aplicare la nivel mondial, aceasta are o valoare inițială. Bine >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Fie valoarea inițială pe care ați dat-o sau zero.

430
00:32:48,950 --> 00:32:53,260
Cred că are grijă de toate astea.

431
00:32:53,260 --> 00:32:58,390
>> Bine. Deci, următoarea parte a întrebării solicită,

432
00:32:58,390 --> 00:33:01,260
"Acum vrem să scrie o funcție numită conține

433
00:33:01,260 --> 00:33:04,930
cu un prototip de bool conține o valoare int. "

434
00:33:04,930 --> 00:33:08,340
Noi nu suntem de gând să faci bool conține o valoare int.

435
00:33:08,340 --> 00:33:15,110
Prototip nostru este de gând să arate

436
00:33:15,110 --> 00:33:22,380
bool conține (valoare int.

437
00:33:22,380 --> 00:33:24,490
Și apoi vom merge, de asemenea, să-l dați copac

438
00:33:24,490 --> 00:33:28,870
că aceasta ar trebui să fie de verificare pentru a vedea dacă acesta are ca valoare.

439
00:33:28,870 --> 00:33:38,290
Deci, nod * copac). Bine.

440
00:33:38,290 --> 00:33:44,440
Și apoi putem să-l numim cu ceva de genul,

441
00:33:44,440 --> 00:33:46,090
poate vom dori să printf sau ceva.

442
00:33:46,090 --> 00:33:51,040
Conține 6, radacina noastra.

443
00:33:51,040 --> 00:33:54,300
Asta ar trebui să se întoarcă unul, sau adevărat,

444
00:33:54,300 --> 00:33:59,390
întrucât conține 5 rădăcină ar trebui să se întoarcă fals.

445
00:33:59,390 --> 00:34:02,690
Astfel încât să ia un al doilea să pună în aplicare acest lucru.

446
00:34:02,690 --> 00:34:06,780
Poti sa o faci, fie iterativ sau recursiv.

447
00:34:06,780 --> 00:34:09,739
Cel mai frumos lucru despre modul în care ne-am stabilit lucrurile este faptul că

448
00:34:09,739 --> 00:34:12,300
acesta se pretează la soluția noastră recursivă mult mai ușor

449
00:34:12,300 --> 00:34:14,719
decât modul global-variabilă a făcut.

450
00:34:14,719 --> 00:34:19,750
Pentru că dacă avem doar conține o valoare int, atunci avem nici un fel de recursiune jos subarbori.

451
00:34:19,750 --> 00:34:24,130
Ne-ar trebui să aibă o funcție de ajutor separat care recurses stabilire a subarbori pentru noi.

452
00:34:24,130 --> 00:34:29,610
Dar din moment ce ne-am schimbat-l să ia copac ca un argument,

453
00:34:29,610 --> 00:34:32,760
care ar trebui să au fost întotdeauna în primul rând,

454
00:34:32,760 --> 00:34:35,710
acum putem recurse mai ușor.

455
00:34:35,710 --> 00:34:38,960
Deci, iterativ sau recursiv, vom trece peste atât,

456
00:34:38,960 --> 00:34:46,139
dar vom vedea care se termină prin a fi recursive destul de usor.

457
00:34:59,140 --> 00:35:02,480
Bine. Are cineva ceva ce putem lucra cu?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Am o soluție iterativ. >> Regulă, iterativ.

459
00:35:12,000 --> 00:35:16,030
Bine, asta arata bine.

460
00:35:16,030 --> 00:35:18,920
Deci, vrei să ne plimbăm prin ea?

461
00:35:18,920 --> 00:35:25,780
[Student] Sigur. Asa ca am stabilit o variabilă temp pentru a obține primul nod al arborelui.

462
00:35:25,780 --> 00:35:28,330
Și apoi am buclă prin temperatură nu, nu în timp ce nul egal,

463
00:35:28,330 --> 00:35:31,700
astfel încât în ​​timp ce era încă în copac, cred.

464
00:35:31,700 --> 00:35:35,710
Și dacă valoarea este egală cu valoarea pe care temperatura este îndreptat spre,

465
00:35:35,710 --> 00:35:37,640
apoi revine ca valoare.

466
00:35:37,640 --> 00:35:40,210
În caz contrar, se verifică dacă e pe partea dreapta sau stanga.

467
00:35:40,210 --> 00:35:43,400
Dacă aveți vreodată o situație în care nu există nici un copac mai mult,

468
00:35:43,400 --> 00:35:47,330
apoi revine - iese bucla si returneaza false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Ok. Deci, care pare bun.

470
00:35:52,190 --> 00:35:58,470
Oricine are nici un comentariu la ceva?

471
00:35:58,470 --> 00:36:02,400
Nu am nici un comentariu de corectitudine, la toate.

472
00:36:02,400 --> 00:36:11,020
Singurul lucru putem face este tipul ăsta.

473
00:36:11,020 --> 00:36:21,660
Oh, o să meargă un pic alungit.

474
00:36:21,660 --> 00:36:33,460
Voi rezolva asta. Bine.

475
00:36:33,460 --> 00:36:37,150
>> Toată lumea ar trebui să ne amintim cum funcționează ternară.

476
00:36:37,150 --> 00:36:38,610
Au fost cu siguranță teste în trecut

477
00:36:38,610 --> 00:36:41,170
care vă oferă o funcție cu un operator ternar,

478
00:36:41,170 --> 00:36:45,750
și spune, traduce aceasta, face ceva ce nu utilizează ternară.

479
00:36:45,750 --> 00:36:49,140
Deci, acesta este un caz foarte comun de când mi-ar gândi să folosească ternare,

480
00:36:49,140 --> 00:36:54,610
în cazul în care în cazul în care unele condiția stabilită o variabilă la ceva,

481
00:36:54,610 --> 00:36:58,580
stabilit altceva care aceeași variabilă la altceva.

482
00:36:58,580 --> 00:37:03,390
Asta e ceva ce foarte frecvent poate fi transformat în acest fel de lucru

483
00:37:03,390 --> 00:37:14,420
în cazul în care variabila stabilit că la acest lucru - sau, ei bine, e adevărat? Apoi, acest, altceva asta.

484
00:37:14,420 --> 00:37:18,550
[Student] Prima dintre ele este dacă este adevărat, nu?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Da. Modul în care am citit-o întotdeauna este, de temperatură este egală cu valoare mai mare decât valoarea temp,

486
00:37:25,570 --> 00:37:30,680
atunci aceasta, altceva asta. A pune o întrebare.

487
00:37:30,680 --> 00:37:35,200
Este mai mare? Atunci fă primul lucru. Face altceva doilea lucru.

488
00:37:35,200 --> 00:37:41,670
Am aproape întotdeauna - colon, eu doar - în capul meu, am citit ca altcineva.

489
00:37:41,670 --> 00:37:47,180
>> Are cineva o soluție recursiv?

490
00:37:47,180 --> 00:37:49,670
Bine. Aceasta vom - ar putea fi deja mare,

491
00:37:49,670 --> 00:37:53,990
dar vom face chiar mai bine.

492
00:37:53,990 --> 00:37:58,720
Acest lucru este destul de mult exact aceeasi idee.

493
00:37:58,720 --> 00:38:03,060
E doar, de bine, vrei să explici?

494
00:38:03,060 --> 00:38:08,340
[Student] Sigur. Deci suntem asigurându-vă că arborele nu este NULL în primul rând,

495
00:38:08,340 --> 00:38:13,380
pentru că dacă arborele este nulă, atunci o să se întoarcă falsă, deoarece nu am găsit-o.

496
00:38:13,380 --> 00:38:19,200
Și dacă există încă un copac, mergem în - vom verifica mai întâi dacă valoarea este nodul curent.

497
00:38:19,200 --> 00:38:23,740
Return true dacă este, și dacă nu am recurse la stânga sau la dreapta.

498
00:38:23,740 --> 00:38:25,970
Sună caz? >> Mm-hmm. (Acord)

499
00:38:25,970 --> 00:38:33,880
Deci, observăm că acest lucru este aproape - structural foarte similar cu soluția iterativ.

500
00:38:33,880 --> 00:38:38,200
E doar că, în loc de recursiune, am avut o buclă în timp ce.

501
00:38:38,200 --> 00:38:40,840
Și scenariul de bază aici, în cazul în care arborele nu null egal

502
00:38:40,840 --> 00:38:44,850
a fost condiția în care ne-am despartit din bucla timp.

503
00:38:44,850 --> 00:38:50,200
Sunt foarte asemanatoare. Dar vom lua acest pas mai departe.

504
00:38:50,200 --> 00:38:54,190
Acum, facem același lucru aici.

505
00:38:54,190 --> 00:38:57,680
Observați ne intoarcem același lucru în ambele linii,

506
00:38:57,680 --> 00:39:00,220
cu excepția unui singur argument este diferit.

507
00:39:00,220 --> 00:39:07,950
Deci, vom face ca într-un ternar.

508
00:39:07,950 --> 00:39:13,790
Am lovit ceva opțiune, și a făcut un simbol. Bine.

509
00:39:13,790 --> 00:39:21,720
Deci, vom reveni conține asta.

510
00:39:21,720 --> 00:39:28,030
Acest lucru este obtinerea a fi mai multe linii, bine, mărită este.

511
00:39:28,030 --> 00:39:31,060
De obicei, ca un lucru stilistic, nu cred că mulți oameni

512
00:39:31,060 --> 00:39:38,640
pune un spațiu după săgeată, dar cred că dacă ești consecvent, e în regulă.

513
00:39:38,640 --> 00:39:44,320
Dacă valoarea este mai mică decât valoarea copac, dorim să recurse la stânga copac,

514
00:39:44,320 --> 00:39:53,890
altceva vrem să recurse la dreapta copac.

515
00:39:53,890 --> 00:39:58,610
Așa că a fost un pas de a face acest aspect mai mici.

516
00:39:58,610 --> 00:40:02,660
Pasul doi a face acest aspect mai mici -

517
00:40:02,660 --> 00:40:09,150
putem separa acest lucru mai multe linii.

518
00:40:09,150 --> 00:40:16,500
Bine. Pasul doi de a face sa arate mai mic este aici,

519
00:40:16,500 --> 00:40:25,860
astfel încât valoarea este egală cu valoarea de retur copac, sau conține orice.

520
00:40:25,860 --> 00:40:28,340
>> Acesta este un lucru important.

521
00:40:28,340 --> 00:40:30,860
Nu sunt sigur dacă el a spus că în mod explicit în clasă,

522
00:40:30,860 --> 00:40:34,740
dar se numește scurt-circuit de evaluare.

523
00:40:34,740 --> 00:40:41,060
Ideea aici este valoarea == valoare copac.

524
00:40:41,060 --> 00:40:49,960
Dacă acest lucru este adevărat, atunci acest lucru este adevărat, și vrem să "sau" care cu ceea ce este aici.

525
00:40:49,960 --> 00:40:52,520
Deci, fără măcar să ne gândim cu privire la tot ce este aici,

526
00:40:52,520 --> 00:40:55,070
ceea ce este expresia întregii gând să se întoarcă?

527
00:40:55,070 --> 00:40:59,430
[Student] Adevărat? >> Da, pentru că adevărata de nimic,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd sau cu nimic adevărat este neapărat adevărat.

529
00:41:04,990 --> 00:41:08,150
Asa ca imediat ce vom vedea valoare de retur = valoarea copac,

530
00:41:08,150 --> 00:41:10,140
suntem doar de gând să se întoarcă adevărat.

531
00:41:10,140 --> 00:41:15,710
Nici măcar nu o să recurse în continuare conține în jos linie.

532
00:41:15,710 --> 00:41:20,980
Ne putem lua acest pas mai departe.

533
00:41:20,980 --> 00:41:29,490
Rentabilitatea copac nu nul egală și toate astea.

534
00:41:29,490 --> 00:41:32,650
Ea a făcut-o o functie de o linie.

535
00:41:32,650 --> 00:41:36,790
Acest lucru este, de asemenea, un exemplu de scurt-circuit de evaluare.

536
00:41:36,790 --> 00:41:40,680
Dar acum e aceeași idee -

537
00:41:40,680 --> 00:41:47,320
în loc de - asa ca daca arborele nu nul egală - sau, ei bine,

538
00:41:47,320 --> 00:41:49,580
în cazul în care nu copac nul egal, ceea ce este cazul rea,

539
00:41:49,580 --> 00:41:54,790
în cazul în care este egal cu zero copac, apoi prima condiție va fi falsă.

540
00:41:54,790 --> 00:42:00,550
Deci, fals anded cu orice va fi ce?

541
00:42:00,550 --> 00:42:04,640
[Student] Fals. Da >>. Aceasta este cealaltă jumătate a scurt-circuitului de evaluare,

542
00:42:04,640 --> 00:42:10,710
în cazul în care în cazul în care nu copac null nu este egal, atunci nu suntem de gând să meargă chiar -

543
00:42:10,710 --> 00:42:14,930
sau în cazul în care nu copac nul egal, atunci nu vom face value == valoare copac.

544
00:42:14,930 --> 00:42:17,010
Suntem doar de gând să se întoarcă imediat false.

545
00:42:17,010 --> 00:42:20,970
Ceea ce este important, deoarece în cazul în care aceasta nu a scurt-circuit a evalua,

546
00:42:20,970 --> 00:42:25,860
apoi, dacă nu copac null egal, această a doua condiție este de gând să vina seg,

547
00:42:25,860 --> 00:42:32,510
deoarece copac-> valoare este nulă dereferencing.

548
00:42:32,510 --> 00:42:40,490
Deci asta e. Poate face acest lucru - o dată trecerea peste.

549
00:42:40,490 --> 00:42:44,840
Acesta este un lucru foarte comun, de asemenea, nu face asta singură linie cu acest lucru,

550
00:42:44,840 --> 00:42:49,000
dar este un lucru comun în condiții, poate nu chiar aici,

551
00:42:49,000 --> 00:42:59,380
dar dacă (copac = NULL,! și copac-> valoare == valoare), face orice.

552
00:42:59,380 --> 00:43:01,560
Aceasta este o condiție foarte frecvente, în cazul în care în loc de a avea

553
00:43:01,560 --> 00:43:06,770
pentru a sparge această în două FI, în cazul în care doriți, este nul copac?

554
00:43:06,770 --> 00:43:11,780
Bine, nu e nul, asa ca acum este o valoare egală cu valoarea copac? Face acest lucru.

555
00:43:11,780 --> 00:43:17,300
În schimb, această condiție, aceasta nu va SEG vina

556
00:43:17,300 --> 00:43:21,220
pentru că va izbucni în cazul în care acest lucru se întâmplă să fie nul.

557
00:43:21,220 --> 00:43:24,000
Ei bine, cred că în cazul în care arborele este un pointer invalid complet, acesta poate SEG încă vina,

558
00:43:24,000 --> 00:43:26,620
dar nu poate SEG vina în cazul în care copacul este nulă.

559
00:43:26,620 --> 00:43:32,900
Dacă ar fi fost nule, s-ar rupe înainte de ai dereferenced vreodată indicatorul în primul rând.

560
00:43:32,900 --> 00:43:35,000
[Student] Este aceasta evaluare numita leneș?

561
00:43:35,000 --> 00:43:40,770
>> Evaluarea [Bowden] Lazy este un lucru separat.

562
00:43:40,770 --> 00:43:49,880
Evaluarea leneș este mai mult ca să vă întreb pentru o valoare,

563
00:43:49,880 --> 00:43:54,270
vă întreb pentru a calcula o valoare, un fel de, dar nu ai nevoie de ea imediat.

564
00:43:54,270 --> 00:43:59,040
Deci, până când de fapt nevoie de ea, nu este evaluată.

565
00:43:59,040 --> 00:44:03,920
Acest lucru nu este exact același lucru, dar în PSET Huffman,

566
00:44:03,920 --> 00:44:06,520
se spune că noi "alene" scrie.

567
00:44:06,520 --> 00:44:08,670
Motivul pentru care face acest lucru este pentru că suntem, de fapt tamponare scriere -

568
00:44:08,670 --> 00:44:11,820
nu vrem să scrie biți individuali la un moment dat,

569
00:44:11,820 --> 00:44:15,450
sau bytes individuale la un moment dat, am în schimb doriți să obțineți o bucată de octeți.

570
00:44:15,450 --> 00:44:19,270
Apoi, după ce vom avea o bucată de octeți, atunci vom scrie.

571
00:44:19,270 --> 00:44:22,640
Chiar dacă ai cere să scrie - și fwrite si fread facă același tip de lucru.

572
00:44:22,640 --> 00:44:26,260
Ei tampon citește și scrie.

573
00:44:26,260 --> 00:44:31,610
Chiar dacă ai cere să scrie imediat, probabil că nu va fi.

574
00:44:31,610 --> 00:44:34,540
Și nu poți fi sigur că lucrurile se vor fi scris

575
00:44:34,540 --> 00:44:37,540
până când apelați hfclose sau orice ar fi,

576
00:44:37,540 --> 00:44:39,620
care apoi spune, bine, eu sunt de închidere dosarul meu,

577
00:44:39,620 --> 00:44:43,450
înseamnă că aș scrie mai bine tot ceea ce nu am scris încă.

578
00:44:43,450 --> 00:44:45,770
Ea nu are nevoie să scrie totul

579
00:44:45,770 --> 00:44:49,010
până când se închid fișierul, și apoi trebuie să.

580
00:44:49,010 --> 00:44:56,220
Deci, asta e doar ceea ce leneș - se așteaptă până când acesta are să se întâmple.

581
00:44:56,220 --> 00:44:59,990
Acest lucru - să ia 51 și veți intra în el, în mai multe detalii,

582
00:44:59,990 --> 00:45:05,470
deoarece OCaml și totul în 51, totul este recursivitate.

583
00:45:05,470 --> 00:45:08,890
Nu există nici o iterativ solutii, practic.

584
00:45:08,890 --> 00:45:11,550
Totul este recursivitate, leneș și evaluare

585
00:45:11,550 --> 00:45:14,790
va fi important pentru o mulțime de împrejurări

586
00:45:14,790 --> 00:45:19,920
în cazul în care, în cazul în care nu ați evalua leneș, asta ar însemna -

587
00:45:19,920 --> 00:45:24,760
Exemplu este fluxuri, care sunt infinit de lungi.

588
00:45:24,760 --> 00:45:30,990
În teorie, vă puteți gândi la numerele naturale, ca un flux de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Deci, lucrurile sunt bine evaluate alene.

590
00:45:33,090 --> 00:45:37,210
Dacă eu spun că vreau numărul zecelea, atunci pot evalua până la numărul zecea.

591
00:45:37,210 --> 00:45:40,300
Dacă vreau numărul suta, atunci pot evalua până la numărul suta.

592
00:45:40,300 --> 00:45:46,290
Fara evaluare leneș, atunci va încerca să evalueze toate numerele imediat.

593
00:45:46,290 --> 00:45:50,000
Te evaluarea numere infinit de multe, și că nu e doar posibil.

594
00:45:50,000 --> 00:45:52,080
Deci, există o mulțime de situații în care leneș de evaluare

595
00:45:52,080 --> 00:45:57,840
este doar esențial pentru obținerea lucrurile să funcționeze.

596
00:45:57,840 --> 00:46:05,260
>> Acum vrem să scrie inserați în cazul în care se introduce o să fie

597
00:46:05,260 --> 00:46:08,430
În mod similar schimbarea în definiția sa.

598
00:46:08,430 --> 00:46:10,470
Deci, acum e inserați bool (valoare int).

599
00:46:10,470 --> 00:46:23,850
Vom schimba asta pentru a insera bool (int valoare, nod copac *).

600
00:46:23,850 --> 00:46:29,120
Suntem de fapt, se va schimba din nou într-un pic, vom vedea de ce.

601
00:46:29,120 --> 00:46:32,210
Și haideți să mutați build_node, doar pentru placerea de a se,

602
00:46:32,210 --> 00:46:36,730
de mai sus se introduce așa că nu trebuie să scrie un prototip funcție.

603
00:46:36,730 --> 00:46:42,450
Care este un indiciu că ai de gând să fie utilizând build_node în inserare.

604
00:46:42,450 --> 00:46:49,590
Bine. Ia un minut pentru asta.

605
00:46:49,590 --> 00:46:52,130
Cred că am salvat de revizuire în cazul în care doriți să trageți din faptul că,

606
00:46:52,130 --> 00:47:00,240
sau, cel puțin, am făcut-o acum.

607
00:47:00,240 --> 00:47:04,190
Am vrut o pauză ușoară să se gândească la logica Inserare,

608
00:47:04,190 --> 00:47:08,750
în cazul în care nu se poate gândi la ea.

609
00:47:08,750 --> 00:47:12,860
Practic, va fi doar introducerea vreodată la frunze.

610
00:47:12,860 --> 00:47:18,640
Ca, daca am introduce 1, apoi am de gând să fie în mod inevitabil inserarea 1 -

611
00:47:18,640 --> 00:47:21,820
Voi schimba la negru - Voi fi inserarea 1 aici.

612
00:47:21,820 --> 00:47:28,070
Sau dacă am introduce 4, vreau să fie inserarea 4 aici.

613
00:47:28,070 --> 00:47:32,180
Deci, indiferent de ceea ce faci, ai de gând să fie introducerea la o frunză.

614
00:47:32,180 --> 00:47:36,130
Tot ce trebuie să faceți este să itera în jos arborele până când ajunge la nodul

615
00:47:36,130 --> 00:47:40,890
care ar trebui să fie mamă nodului, nodul părinte nou,

616
00:47:40,890 --> 00:47:44,560
și modificați apoi indicatorul sa stânga sau la dreapta, în funcție de

617
00:47:44,560 --> 00:47:47,060
e mai mare sau mai mică decât nodul curent.

618
00:47:47,060 --> 00:47:51,180
Modificarea că indicatorul pentru a indica nodul nou.

619
00:47:51,180 --> 00:48:05,490
Deci, repeta jos copac, face punctul de frunze la nod nou.

620
00:48:05,490 --> 00:48:09,810
De asemenea, cred despre motivul pentru care interzice tip de situație înainte,

621
00:48:09,810 --> 00:48:17,990
în cazul în care am construit arborele binar în cazul în care acesta a fost actualizată

622
00:48:17,990 --> 00:48:19,920
Dacă ați uitat doar la un singur nod,

623
00:48:19,920 --> 00:48:24,830
dar 9 a fost la stânga din 7, dacă reiterat în jos tot drumul.

624
00:48:24,830 --> 00:48:29,770
Deci, asta e imposibil în acest scenariu, deoarece -

625
00:48:29,770 --> 00:48:32,530
cred ca introducerea aproximativ 9 sau ceva, iar la nodul prima,

626
00:48:32,530 --> 00:48:35,350
Mă duc să văd 7 și Mă duc să meargă la dreapta.

627
00:48:35,350 --> 00:48:38,490
Deci, indiferent de ceea ce fac, dacă am introduce prin a merge la o frunză,

628
00:48:38,490 --> 00:48:40,790
și să o frunză folosind algoritmul corespunzător,

629
00:48:40,790 --> 00:48:43,130
că va fi imposibil pentru mine pentru a insera 9 la stânga din 7

630
00:48:43,130 --> 00:48:48,250
pentru ca imediat ce m-am lovit 7 am de gând să merg la dreapta.

631
00:48:59,740 --> 00:49:02,070
Are cineva ceva pentru a începe cu?

632
00:49:02,070 --> 00:49:05,480
[Student] fac. Sigur >>.

633
00:49:05,480 --> 00:49:09,200
[Student, neinteligibil]

634
00:49:09,200 --> 00:49:14,390
[Alt student, neinteligibil]

635
00:49:14,390 --> 00:49:18,330
[Bowden] E apreciat. Bine. Vrei să explici?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Din moment ce știm că am fost inserarea

637
00:49:20,690 --> 00:49:24,060
noduri noi la sfârșitul arborelui,

638
00:49:24,060 --> 00:49:28,070
Am o buclă prin copac iterativ

639
00:49:28,070 --> 00:49:31,360
până când am ajuns la un nod care a indicat zero.

640
00:49:31,360 --> 00:49:34,220
Și apoi m-am decis să-l pună fie pe partea dreapta sau stanga

641
00:49:34,220 --> 00:49:37,420
folosirea acestui drept variabilă, ea mi-a spus unde să-l puneți.

642
00:49:37,420 --> 00:49:41,850
Și apoi, în esență, am facut asta ultima -

643
00:49:41,850 --> 00:49:47,520
acel nod punct temp la nod nou, care a fost crearea,

644
00:49:47,520 --> 00:49:50,770
fie pe partea stângă sau pe partea dreaptă, în funcție de ceea ce a fost corect valoarea.

645
00:49:50,770 --> 00:49:56,530
În cele din urmă, am setat valoarea nod nou la valoarea de testare sale.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Ok, deci văd o problemă aici.

647
00:49:59,550 --> 00:50:02,050
Acest lucru este la fel ca 95% din drum acolo.

648
00:50:02,050 --> 00:50:07,550
Problemă pe care am vedea, ei bine, nu oricine altcineva vedea o problemă?

649
00:50:07,550 --> 00:50:18,400
Care este împrejurarea în care acestea iesi din bucla?

650
00:50:18,400 --> 00:50:22,100
[Student] Dacă temperatura este nul? Da >>. Deci, cum ai rupe din bucla este dacă temperatura este nulă.

651
00:50:22,100 --> 00:50:30,220
Dar ce fac aici?

652
00:50:30,220 --> 00:50:35,410
Am temp dereference, care este în mod inevitabil nulă.

653
00:50:35,410 --> 00:50:39,840
Deci, un alt lucru ce trebuie sa faci este sa tii nu doar piesa pana cand temperatura este nul,

654
00:50:39,840 --> 00:50:45,590
doriți să urmăriți mamă în orice moment.

655
00:50:45,590 --> 00:50:52,190
Ne dorim, de asemenea, * nodul părinte, cred că putem păstra ca la nul la început.

656
00:50:52,190 --> 00:50:55,480
Acest lucru se întâmplă pentru a avea un comportament ciudat pentru rădăcina arborelui,

657
00:50:55,480 --> 00:50:59,210
dar vom ajunge la asta.

658
00:50:59,210 --> 00:51:03,950
Dacă valoarea este mai mare decât orice, atunci temperatura = temp dreapta.

659
00:51:03,950 --> 00:51:07,910
Dar, inainte de a face asta, mamă = temp.

660
00:51:07,910 --> 00:51:14,500
Sau sunt părinții întotdeauna de gând să temperatura egal? Este faptul că cazul?

661
00:51:14,500 --> 00:51:19,560
În cazul în care temperatura nu este nul, atunci am de gând să vă deplasa în jos, indiferent de ce,

662
00:51:19,560 --> 00:51:24,030
la un nod pentru care temperatura este mamă.

663
00:51:24,030 --> 00:51:27,500
Deci, mamă va fi temp, iar apoi m-am muta în jos temp.

664
00:51:27,500 --> 00:51:32,410
Acum, temperatura este nul, dar subliniază mamă la mamă de lucru care este nul.

665
00:51:32,410 --> 00:51:39,110
Deci aici, nu vreau să setați adică dreapta 1.

666
00:51:39,110 --> 00:51:41,300
Așa că m-am mutat la dreapta, așa că, dacă dreapta = 1,

667
00:51:41,300 --> 00:51:45,130
si cred ca tu, de asemenea, doriți să faceți -

668
00:51:45,130 --> 00:51:48,530
în cazul în care vă mutați la stânga, pe care doriți să setați dreptul egal cu 0.

669
00:51:48,530 --> 00:51:55,950
Sau altceva dacă vă mutați vreodată la dreapta.

670
00:51:55,950 --> 00:51:58,590
Deci, dreapta = 0. În cazul în care dreapta = 1,

671
00:51:58,590 --> 00:52:04,260
acum vrem să newnode mamă indicatorul dreapta,

672
00:52:04,260 --> 00:52:08,520
altceva vrem sa facem newnode mamă indicatorul la stânga.

673
00:52:08,520 --> 00:52:16,850
Întrebări cu privire la asta?

674
00:52:16,850 --> 00:52:24,880
Bine. Deci, acesta este modul în care noi - ei bine, de fapt, în loc de a face acest lucru,

675
00:52:24,880 --> 00:52:29,630
am așteptat o jumătate să utilizați build_node.

676
00:52:29,630 --> 00:52:40,450
Și apoi, dacă este egal cu newnode nulă, return false.

677
00:52:40,450 --> 00:52:44,170
Asta e asta. Acum, aceasta este ceea ce ne-am așteptat să faci.

678
00:52:44,170 --> 00:52:47,690
>> Aceasta este ceea ce soluțiile de personal fac.

679
00:52:47,690 --> 00:52:52,360
Nu sunt de acord cu acest lucru ca "dreptul" de a merge cu privire la aceasta

680
00:52:52,360 --> 00:52:57,820
dar acest lucru este perfect în regulă și va funcționa.

681
00:52:57,820 --> 00:53:02,840
Un lucru care e un pic ciudat acum este

682
00:53:02,840 --> 00:53:08,310
în cazul în care arborele începe nul, vom trece într-un copac nul.

683
00:53:08,310 --> 00:53:12,650
Cred că depinde de modul în care definesc comportamentul trece într-un copac nul.

684
00:53:12,650 --> 00:53:15,490
Mi-ar crede că dacă treci într-un copac nul,

685
00:53:15,490 --> 00:53:17,520
apoi introducerea valoare într-un copac nul

686
00:53:17,520 --> 00:53:23,030
ar trebui să se întoarcă la doar un copac în cazul în care valoarea este ca singur nod.

687
00:53:23,030 --> 00:53:25,830
Oamenii sunt de acord cu asta? Ai putea, dacă ai vrut,

688
00:53:25,830 --> 00:53:28,050
daca treci într-un copac nul

689
00:53:28,050 --> 00:53:31,320
și doriți să inserați o valoare în ea, intoarce false.

690
00:53:31,320 --> 00:53:33,830
E de până la tine pentru a defini asta.

691
00:53:33,830 --> 00:53:38,320
Pentru a face primul lucru pe care I-am spus și apoi -

692
00:53:38,320 --> 00:53:40,720
bine, ai de gând să faci asta avea probleme, deoarece

693
00:53:40,720 --> 00:53:44,090
ar fi mai ușor dacă am avea un pointer la nivel mondial la lucru,

694
00:53:44,090 --> 00:53:48,570
dar noi nu, deci, dacă copac este nul, nu e nimic ce putem face despre asta.

695
00:53:48,570 --> 00:53:50,960
Ne putem întoarce pur și simplu false.

696
00:53:50,960 --> 00:53:52,840
Așa că am de gând să schimbe inserați.

697
00:53:52,840 --> 00:53:56,540
Am punct de vedere tehnic ar putea schimba asta chiar aici,

698
00:53:56,540 --> 00:53:58,400
cum se iterarea peste lucruri,

699
00:53:58,400 --> 00:54:04,530
dar am de gând să schimbe inserați pentru a lua un nod ** copac.

700
00:54:04,530 --> 00:54:07,510
Pointeri duble.

701
00:54:07,510 --> 00:54:09,710
Ce înseamnă?

702
00:54:09,710 --> 00:54:12,330
În loc de a face cu pointeri la noduri,

703
00:54:12,330 --> 00:54:16,690
lucru pe care am de gând să fie manipularea este acest indicator.

704
00:54:16,690 --> 00:54:18,790
Am de gând să fie manipularea acestui indicator.

705
00:54:18,790 --> 00:54:21,770
Am de gând să fie manipularea pointeri direct.

706
00:54:21,770 --> 00:54:25,760
Acest lucru are sens, deoarece, gândiți-vă -

707
00:54:25,760 --> 00:54:33,340
Ei bine, acum aceste puncte la zero.

708
00:54:33,340 --> 00:54:38,130
Ceea ce vreau să fac este să manipuleze acest pointer la punctul de a nu null.

709
00:54:38,130 --> 00:54:40,970
Vreau să subliniez la nodul noua mea.

710
00:54:40,970 --> 00:54:44,870
Dacă aș ține doar evidența pointeri la pointeri mele,

711
00:54:44,870 --> 00:54:47,840
atunci nu am nevoie pentru a urmări un pointer-mamă.

712
00:54:47,840 --> 00:54:52,640
Eu pot păstra doar piesa pentru a vedea dacă indicatorul este orientată la nul,

713
00:54:52,640 --> 00:54:54,580
și dacă indicatorul este orientată la nul,

714
00:54:54,580 --> 00:54:57,370
schimba-l la punctul de a nodului vreau.

715
00:54:57,370 --> 00:55:00,070
Și eu pot schimba, deoarece am un pointer la pointer.

716
00:55:00,070 --> 00:55:02,040
Să vedem acum acest drept.

717
00:55:02,040 --> 00:55:05,470
Puteți face de fapt recursiv destul de ușor.

718
00:55:05,470 --> 00:55:08,080
Nu vrem să facem asta?

719
00:55:08,080 --> 00:55:10,980
Da, avem.

720
00:55:10,980 --> 00:55:16,790
>> Să-l vedem recursiv.

721
00:55:16,790 --> 00:55:24,070
În primul rând, ceea ce este cazul nostru de bază va fi?

722
00:55:24,070 --> 00:55:29,140
Aproape întotdeauna cazul nostru de bază, dar, de fapt, acest lucru este un fel de complicat.

723
00:55:29,140 --> 00:55:34,370
Primul lucru, în cazul în care (arbore == NULL)

724
00:55:34,370 --> 00:55:37,550
Cred că suntem doar de gând să se întoarcă fals.

725
00:55:37,550 --> 00:55:40,460
Acest lucru este diferit de zero copac fiind.

726
00:55:40,460 --> 00:55:44,510
Acesta este indicatorul la indicatorul rădăcină fiind nulă

727
00:55:44,510 --> 00:55:48,360
ceea ce înseamnă că indicatorul de root nu exista.

728
00:55:48,360 --> 00:55:52,390
Deci aici, dacă fac

729
00:55:52,390 --> 00:55:55,760
* nod - să reutilizeze asta.

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

731
00:55:58,960 --> 00:56:00,730
si apoi am de gând să sun introduce de a face ceva de genul,

732
00:56:00,730 --> 00:56:04,540
introduceți 4 în & rădăcină.

733
00:56:04,540 --> 00:56:06,560
Deci & rădăcină, în cazul în care rădăcina este un nod *

734
00:56:06,560 --> 00:56:11,170
atunci si radacina va fi un nod **.

735
00:56:11,170 --> 00:56:15,120
Acest lucru este valabil. În acest caz, copac, aici,

736
00:56:15,120 --> 00:56:20,120
copac nu este nulă - sau inserați.

737
00:56:20,120 --> 00:56:24,630
Aici. Arborele nu este nulă; copac * este nul, ceea ce este bine

738
00:56:24,630 --> 00:56:26,680
pentru că dacă copac * este nul, atunci pot să-l manipula

739
00:56:26,680 --> 00:56:29,210
pentru a indica acum la ceea ce vreau să subliniez.

740
00:56:29,210 --> 00:56:34,750
Dar dacă copac este nulă, înseamnă că am venit aici și a spus nul.

741
00:56:34,750 --> 00:56:42,710
Asta nu are nici un sens. Eu nu pot face nimic cu asta.

742
00:56:42,710 --> 00:56:45,540
Dacă arborele este nul, return false.

743
00:56:45,540 --> 00:56:48,220
Așa că am spus deja, practic ceea ce cazul nostru de bază reală este.

744
00:56:48,220 --> 00:56:50,580
Și ce este că va fi?

745
00:56:50,580 --> 00:56:55,030
[Student, neinteligibil]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Da. Deci, în cazul în care (* arbore == NULL).

747
00:57:00,000 --> 00:57:04,520
Acest lucru se referă la cazul aici

748
00:57:04,520 --> 00:57:09,640
în cazul în care în cazul în care indicatorul meu rosu este indicatorul eu axat pe,

749
00:57:09,640 --> 00:57:12,960
asa ca am concentrat pe acest indicator, acum am concentrat pe acest indicator.

750
00:57:12,960 --> 00:57:15,150
Acum, eu sunt concentrat pe acest indicator.

751
00:57:15,150 --> 00:57:18,160
Deci, dacă indicatorul meu rosu, care este nod ** mele,

752
00:57:18,160 --> 00:57:22,880
este tot - în cazul în care *, indicatorul meu rosu, este mereu nul,

753
00:57:22,880 --> 00:57:28,470
asta înseamnă că eu sunt la cazul în care mă concentrându-se pe un pointer care puncte -

754
00:57:28,470 --> 00:57:32,530
aceasta este un pointer care aparține o frunză.

755
00:57:32,530 --> 00:57:41,090
Vreau să schimbe acest indicator pentru a indica nodul noua mea.

756
00:57:41,090 --> 00:57:45,230
Vino înapoi aici.

757
00:57:45,230 --> 00:57:56,490
Newnode mea va fi doar nod * n = build_node (valoare)

758
00:57:56,490 --> 00:58:07,300
apoi n, dacă n = NULL, întoarce false.

759
00:58:07,300 --> 00:58:12,600
Altceva vrem sa schimbam ceea ce indicatorul este în prezent indică spre

760
00:58:12,600 --> 00:58:17,830
pentru a indica acum la nodul nostru recent construit.

761
00:58:17,830 --> 00:58:20,280
Putem face asta de fapt aici.

762
00:58:20,280 --> 00:58:30,660
În loc de a spune n, spunem * = copac, dacă copac *.

763
00:58:30,660 --> 00:58:35,450
Toată lumea înțelege că? Că prin a face cu pointeri la pointeri,

764
00:58:35,450 --> 00:58:40,750
putem schimba pointeri nule pentru a indica lucruri pe care doriți să le indice.

765
00:58:40,750 --> 00:58:42,820
Asta e cazul nostru de bază.

766
00:58:42,820 --> 00:58:45,740
>> Acum ne recurență, sau recursivitate nostru,

767
00:58:45,740 --> 00:58:51,430
va fi foarte similar cu toate celelalte recursions am făcut.

768
00:58:51,430 --> 00:58:55,830
Am de gând să doriți să inserați o valoare,

769
00:58:55,830 --> 00:58:59,040
și acum am de gând să folosească ternare din nou, dar ceea ce este condiția noastră va fi?

770
00:58:59,040 --> 00:59:05,180
Ce este aceasta suntem în căutarea pentru a decide dacă vrem să mergem la stânga sau la dreapta?

771
00:59:05,180 --> 00:59:07,760
Hai să o facem în etape separate.

772
00:59:07,760 --> 00:59:18,850
În cazul în care (valoare <) ce?

773
00:59:18,850 --> 00:59:23,200
[Student] valoarea de copac?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Deci, amintiți-vă că eu sunt în prezent -

775
00:59:27,490 --> 00:59:31,260
[Elevii, neinteligibile]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Da, asa de bine aici, să spunem că această săgeată verde

777
00:59:34,140 --> 00:59:39,050
este un exemplu de ceea ce copac este, în prezent, este un pointer la acest indicator.

778
00:59:39,050 --> 00:59:46,610
Asta înseamnă că eu sunt un pointer la un pointer la 3.

779
00:59:46,610 --> 00:59:48,800
Dereference de două ori suna bine.

780
00:59:48,800 --> 00:59:51,010
Ce am - cum fac asta?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference o dată, și apoi face săgeata în acest fel?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Deci (arbore *) este dereference o dată, -> valoarea

783
00:59:58,420 --> 01:00:05,960
este de gând să-mi dea valoarea nodului pe care am indirect arătând spre.

784
01:00:05,960 --> 01:00:11,980
Deci, eu pot scrie, de asemenea, l ** tree.value, dacă preferați asta.

785
01:00:11,980 --> 01:00:18,490
Fie funcționează.

786
01:00:18,490 --> 01:00:26,190
În cazul în care este cazul, atunci vreau să sun insera cu valoare.

787
01:00:26,190 --> 01:00:32,590
Și ceea ce este nodul meu completa ** va fi?

788
01:00:32,590 --> 01:00:39,440
Vreau să merg la stânga, astfel încât tree.left ** va fi stânga mea.

789
01:00:39,440 --> 01:00:41,900
Și vreau să indicatorul chestia aia

790
01:00:41,900 --> 01:00:44,930
astfel că, dacă stânga se termină prin a fi pointer nul,

791
01:00:44,930 --> 01:00:48,360
Pot să-l modifica pentru a indica nodul noua mea.

792
01:00:48,360 --> 01:00:51,460
>> Și alt caz poate fi foarte asemănătoare.

793
01:00:51,460 --> 01:00:55,600
Să facem de fapt, că ternar mea chiar acum.

794
01:00:55,600 --> 01:01:04,480
Introduceți valoarea dacă valoarea <(** copac). Valoare.

795
01:01:04,480 --> 01:01:11,040
Apoi ne-am dori pentru a actualiza ** noastre la stânga,

796
01:01:11,040 --> 01:01:17,030
altceva vrem să actualizați ** noastre la dreapta.

797
01:01:17,030 --> 01:01:22,540
[Student] se obține că indicatorul la indicatorul?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Amintiți-vă că - ** tree.right este o stea nod.

799
01:01:30,940 --> 01:01:35,040
[Student, neinteligibil] >> Da.

800
01:01:35,040 --> 01:01:41,140
** Tree.right este ca acest indicator sau ceva de genul.

801
01:01:41,140 --> 01:01:45,140
Deci, prin luarea un pointer la asta, dă-mi ceea ce vreau

802
01:01:45,140 --> 01:01:50,090
de pointer la tipul ăla.

803
01:01:50,090 --> 01:01:54,260
[Student] Putem trece peste din nou de ce suntem folosind doi pointeri?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Da. Deci - nu, poți, și că soluția înainte de

805
01:01:58,220 --> 01:02:04,540
a fost o modalitate de a face aceasta fără a face doi pointeri.

806
01:02:04,540 --> 01:02:08,740
Ai nevoie să fie în măsură să înțeleagă folosind doi pointeri,

807
01:02:08,740 --> 01:02:11,660
și aceasta este o soluție mai curat.

808
01:02:11,660 --> 01:02:16,090
De asemenea, observați că, în ceea ce se întâmplă în cazul în care copacul meu -

809
01:02:16,090 --> 01:02:24,480
ce se întâmplă dacă rădăcina mea a fost nulă? Ce se întâmplă dacă fac acest caz aici?

810
01:02:24,480 --> 01:02:30,540
Deci, nod * root = NULL, introduceți 4 în & rădăcină.

811
01:02:30,540 --> 01:02:35,110
Ce se rădăcină va fi după asta?

812
01:02:35,110 --> 01:02:37,470
[Student, neinteligibil] >> Da.

813
01:02:37,470 --> 01:02:41,710
Valoarea rădăcină va fi 4.

814
01:02:41,710 --> 01:02:45,510
Stânga rădăcină va fi nulă, dreptul de rădăcină va fi nul.

815
01:02:45,510 --> 01:02:49,490
În cazul în care nu am trecut prin adresa rădăcină,

816
01:02:49,490 --> 01:02:52,490
nu am putut modifica rădăcină.

817
01:02:52,490 --> 01:02:56,020
În cazul în care copacul - în cazul în care rădăcina a fost nul,

818
01:02:56,020 --> 01:02:58,410
tocmai am avut să se întoarcă false. Nu e nimic de făcut.

819
01:02:58,410 --> 01:03:01,520
Noi nu putem introduce un nod într-un arbore gol.

820
01:03:01,520 --> 01:03:06,810
Dar acum putem, vom face doar un copac gol într-un copac de un nod.

821
01:03:06,810 --> 01:03:13,400
Care este, de obicei, modul preconizat, care ar trebui sa lucreze.

822
01:03:13,400 --> 01:03:21,610
>> În plus, acest lucru este semnificativ mai mică decât

823
01:03:21,610 --> 01:03:26,240
asemenea ține cont de mamă, și așa voi repeta în jos tot drumul.

824
01:03:26,240 --> 01:03:30,140
Acum am părinților mei, și am doar indicatorul dreptul meu părinte la orice.

825
01:03:30,140 --> 01:03:35,640
În schimb, dacă am făcut asta iterativ, ar fi aceeași idee, cu o buclă în timp ce.

826
01:03:35,640 --> 01:03:38,100
Dar, în loc de a avea de a face cu indicatorul părinților mei,

827
01:03:38,100 --> 01:03:40,600
în schimb indicatorul mea actuală ar fi lucrul

828
01:03:40,600 --> 01:03:43,790
că eu sunt direct modificarea pentru a indica nodul noua mea.

829
01:03:43,790 --> 01:03:46,090
Eu nu am de a face cu dacă este îndreptat spre stânga.

830
01:03:46,090 --> 01:03:48,810
Eu nu am de a face cu dacă este îndreptat spre dreapta.

831
01:03:48,810 --> 01:04:00,860
E doar ce acest indicator este, am de gând să-l setați pentru a indica nodul noua mea.

832
01:04:00,860 --> 01:04:05,740
Toată lumea înțelege cum funcționează?

833
01:04:05,740 --> 01:04:09,460
Dacă nu de ce vrem să facem în felul acesta,

834
01:04:09,460 --> 01:04:14,920
dar cel puțin că aceasta funcționează ca o soluție?

835
01:04:14,920 --> 01:04:17,110
[Student] În cazul în care nu ne întoarcem adevărat?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Asta e, probabil, chiar aici.

837
01:04:21,550 --> 01:04:26,690
Dacă am introduce în mod corect că, return true.

838
01:04:26,690 --> 01:04:32,010
Altfel, aici jos vom dori să se întoarcă indiferent de inserare se întoarce.

839
01:04:32,010 --> 01:04:35,950
>> Si ceea ce este special la această funcție recursivă?

840
01:04:35,950 --> 01:04:43,010
E coada recursiv, atâta timp cât vom compila cu unele de optimizare,

841
01:04:43,010 --> 01:04:48,060
se va recunoaște faptul că și niciodată nu se va obține o depășire stivă de acest lucru,

842
01:04:48,060 --> 01:04:53,230
chiar dacă arborele nostru are o înălțime de 10.000 sau 10 milioane de euro.

843
01:04:53,230 --> 01:04:55,630
[Student, neinteligibil]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Cred că o face la Dash - sau ce nivel de optimizare

845
01:05:00,310 --> 01:05:03,820
este necesar pentru o recursivitate coadă să fie recunoscut.

846
01:05:03,820 --> 01:05:09,350
Cred că recunoaște - CCG și zăngănit

847
01:05:09,350 --> 01:05:12,610
au, de asemenea, înțelesuri diferite pentru niveluri de optimizare lor.

848
01:05:12,610 --> 01:05:17,870
Vreau să spun că e DashO 2, sigur că acesta va recunoaște recursivitate coadă.

849
01:05:17,870 --> 01:05:27,880
Dar noi - ai putea construi ca un exemplu Fibonocci sau ceva.

850
01:05:27,880 --> 01:05:30,030
Nu e ușor pentru a testa cu acest lucru, pentru că este dificil de a construi

851
01:05:30,030 --> 01:05:32,600
un arbore binar care este atât de mare.

852
01:05:32,600 --> 01:05:37,140
Dar da, cred că e DashO 2, care

853
01:05:37,140 --> 01:05:40,580
dacă doriți să compilați cu DashO 2, acesta va căuta recursivitate coadă

854
01:05:40,580 --> 01:05:54,030
și a optimiza asta.

855
01:05:54,030 --> 01:05:58,190
Să mergem înapoi la - insera e literalmente ultimul lucru de care are nevoie.

856
01:05:58,190 --> 01:06:04,900
Să ne întoarcem la inserați aici

857
01:06:04,900 --> 01:06:07,840
în cazul în care vom face aceeași idee.

858
01:06:07,840 --> 01:06:14,340
Va avea în continuare defect de a nu fi capabil să se ocupe în întregime

859
01:06:14,340 --> 01:06:17,940
atunci când rădăcina în sine este nulă, sau intrarea trecut este nulă,

860
01:06:17,940 --> 01:06:20,060
dar în loc de a face cu un pointer-mamă,

861
01:06:20,060 --> 01:06:27,430
să se aplice aceeași logică de pointeri păstrare la pointeri.

862
01:06:27,430 --> 01:06:35,580
Dacă ținem aici nod nostru ** actuală,

863
01:06:35,580 --> 01:06:37,860
si nu avem nevoie pentru a urmări mai corect,

864
01:06:37,860 --> 01:06:47,190
dar nod ** actuală = & copac.

865
01:06:47,190 --> 01:06:54,800
Și acum, în timp ce bucla nostru este de gând să fie în același timp actuală * nu nul egal.

866
01:06:54,800 --> 01:07:00,270
Nu am nevoie pentru a ține evidența părinți mai.

867
01:07:00,270 --> 01:07:04,180
Nu trebuie să țină evidența la stânga și la dreapta.

868
01:07:04,180 --> 01:07:10,190
Și eu voi numi temperatură, pentru că suntem deja utilizați temp.

869
01:07:10,190 --> 01:07:17,200
Bine. Deci, dacă (valoarea> * temp),

870
01:07:17,200 --> 01:07:24,010
atunci & (* temp) -> dreapta

871
01:07:24,010 --> 01:07:29,250
altceva temp = & (* temp) -> plecat.

872
01:07:29,250 --> 01:07:32,730
Și acum, în acest moment, după această buclă în timp ce,

873
01:07:32,730 --> 01:07:36,380
Am face acest lucru doar pentru că poate e mai ușor să ne gândim decât iterativ recursiv,

874
01:07:36,380 --> 01:07:39,010
dar după această buclă în timp ce,

875
01:07:39,010 --> 01:07:43,820
* Temperatura este indicatorul vrem să se schimbe.

876
01:07:43,820 --> 01:07:48,960
>> Înainte de a avea mamă, și am vrut să schimbe, fie la stânga mamă sau mamă dreapta,

877
01:07:48,960 --> 01:07:51,310
dar dacă vrem să schimbăm dreapta-mamă,

878
01:07:51,310 --> 01:07:54,550
atunci temperatura * are dreptate părinte, și ne poate schimba în mod direct.

879
01:07:54,550 --> 01:08:05,860
Deci aici, putem face * temp = newnode, și asta e tot.

880
01:08:05,860 --> 01:08:09,540
Deci notificare, tot ce am făcut în acest lucru a fost scoate de linii de cod.

881
01:08:09,540 --> 01:08:14,770
În scopul de a ține evidența mamă în tot ceea ce este un efort suplimentar.

882
01:08:14,770 --> 01:08:18,689
Aici, dacă păstrăm doar evidenta pointer la pointer,

883
01:08:18,689 --> 01:08:22,990
și chiar dacă am vrut să scape de toate aceste acolade acum,

884
01:08:22,990 --> 01:08:27,170
face să arate mai scurt.

885
01:08:27,170 --> 01:08:32,529
Acest lucru este acum solutia exact aceeași,

886
01:08:32,529 --> 01:08:38,210
dar mai putine linii de cod.

887
01:08:38,210 --> 01:08:41,229
Odată ce ați începe să recunoască acest lucru ca pe o soluție viabilă,

888
01:08:41,229 --> 01:08:43,529
este, de asemenea, mai ușor de motiv, decât ca despre, bine,

889
01:08:43,529 --> 01:08:45,779
de ce nu am acest indicator la dreapta int?

890
01:08:45,779 --> 01:08:49,290
Ce înseamnă asta? Oh, e semnificând faptul că

891
01:08:49,290 --> 01:08:51,370
de fiecare dată când mă duc dreptate, am nevoie să-l setați,

892
01:08:51,370 --> 01:08:53,819
altceva dacă mă duc plecat am nevoie pentru a seta la zero.

893
01:08:53,819 --> 01:09:04,060
Aici, nu am un motiv sa cu privire la faptul că, e doar mai ușor să se gândească.

894
01:09:04,060 --> 01:09:06,710
Întrebări?

895
01:09:06,710 --> 01:09:16,290
[Student, neinteligibil] >> Da.

896
01:09:16,290 --> 01:09:23,359
Ok, deci în ultimul bit -

897
01:09:23,359 --> 01:09:28,080
Cred că o funcție ușor și rapid, ce putem face este,

898
01:09:28,080 --> 01:09:34,910
hai - împreună, cred, încercați și de a scrie o funcție conține

899
01:09:34,910 --> 01:09:38,899
care nu-i pasă dacă este un arbore binar de căutare.

900
01:09:38,899 --> 01:09:43,770
Această funcție ar trebui să se întoarcă conține adevărat

901
01:09:43,770 --> 01:09:58,330
în cazul în care nicăieri în acest arbore binar generală este valoarea pe care o căutăm.

902
01:09:58,330 --> 01:10:02,520
Deci, hai sa o facem prima recursiv si apoi vom face iterativ.

903
01:10:02,520 --> 01:10:07,300
Putem de fapt, nu doar împreună, deoarece aceasta va fi foarte scurt.

904
01:10:07,300 --> 01:10:11,510
>> Ceea ce este cazul meu de bază va fi?

905
01:10:11,510 --> 01:10:13,890
[Student, neinteligibil]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Deci, dacă (arbore == NULL), atunci ce?

907
01:10:18,230 --> 01:10:22,740
[Student] întoarce FALSE.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Altele, ei bine, nu am nevoie de altceva.

909
01:10:26,160 --> 01:10:30,250
Dacă a fost cazul meu de bază altele.

910
01:10:30,250 --> 01:10:32,450
[Student] Arborele lui valoare? Da >>.

911
01:10:32,450 --> 01:10:36,430
Deci, în cazul în care (arbore-> valoare == valoare.

912
01:10:36,430 --> 01:10:39,920
Observați ne-am întors la * nodul nu, nod ** e?

913
01:10:39,920 --> 01:10:42,990
Conține nu va trebui să utilizați un nod **,

914
01:10:42,990 --> 01:10:45,480
din moment ce nu se modifica pointeri.

915
01:10:45,480 --> 01:10:50,540
Noi doar le traversează.

916
01:10:50,540 --> 01:10:53,830
În cazul în care acest lucru se întâmplă, atunci vrem să se întoarcă adevărat.

917
01:10:53,830 --> 01:10:58,270
Altceva vrem să traverseze copiilor.

918
01:10:58,270 --> 01:11:02,620
Deci, nu putem gândi cu privire la posibilitatea ca totul sa stanga este mai puțin

919
01:11:02,620 --> 01:11:05,390
și totul a dreapta este mai mare.

920
01:11:05,390 --> 01:11:09,590
Deci, ceea ce se condiția noastră va fi aici - sau, ce vom face?

921
01:11:09,590 --> 01:11:11,840
[Student, neinteligibil] >> Da.

922
01:11:11,840 --> 01:11:17,400
Rentabilitatea conține (valoare, arbore-> stânga)

923
01:11:17,400 --> 01:11:26,860
sau conține (valoare, copac-> dreapta). Și asta e tot.

924
01:11:26,860 --> 01:11:29,080
Și observați există unele evaluare scurt-circuit,

925
01:11:29,080 --> 01:11:32,520
în cazul în care, dacă se întâmplă să aflăm valoarea din copac stânga,

926
01:11:32,520 --> 01:11:36,820
Noi nu trebuie să se uite la copac dreapta.

927
01:11:36,820 --> 01:11:40,430
Asta e funcția intreaga.

928
01:11:40,430 --> 01:11:43,690
Acum, hai să o facem iterativ,

929
01:11:43,690 --> 01:11:48,060
care va fi mai puțin frumos.

930
01:11:48,060 --> 01:11:54,750
Vom lua startul de obicei de nod * actuală = copac.

931
01:11:54,750 --> 01:12:03,250
În timp ce (actuală = NULL!).

932
01:12:03,250 --> 01:12:08,600
Rapid de gând să văd o problemă.

933
01:12:08,600 --> 01:12:12,250
Dacă actuală - aici, dacă ne rupe vreodată de acest lucru,

934
01:12:12,250 --> 01:12:16,020
apoi ne-am alerga afară de lucruri să se uite la, întoarce așa fals.

935
01:12:16,020 --> 01:12:24,810
În cazul în care (actuală-> valoare == valoare), return true.

936
01:12:24,810 --> 01:12:32,910
Deci, acum, suntem la un loc -

937
01:12:32,910 --> 01:12:36,250
nu știm dacă vrem să mergem la stânga sau la dreapta.

938
01:12:36,250 --> 01:12:44,590
Deci arbitrar, să mergem tocmai a plecat.

939
01:12:44,590 --> 01:12:47,910
Am rula în mod evident, o problemă în cazul în care le-am abandonat complet totul -

940
01:12:47,910 --> 01:12:50,760
Voi verifica doar vreodată partea stângă de un copac.

941
01:12:50,760 --> 01:12:56,050
Eu nu va verifica ceva care este un copil dreptul de nimic.

942
01:12:56,050 --> 01:13:00,910
Cum pot remedia acest lucru?

943
01:13:00,910 --> 01:13:05,260
[Student] Trebuie să țină evidența stânga și dreapta într-o stivă.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Da. Așa că hai să-l

945
01:13:13,710 --> 01:13:32,360
struct lista, nodul N *, iar apoi nod ** viitoare?

946
01:13:32,360 --> 01:13:40,240
Cred că merge bine.

947
01:13:40,240 --> 01:13:45,940
Vrem să mergem pe stanga, sau hai - aici.

948
01:13:45,940 --> 01:13:54,350
Struct = jos lista, va începe

949
01:13:54,350 --> 01:13:58,170
, în această listă struct.

950
01:13:58,170 --> 01:14:04,040
* Lista = NULL. Așa că va fi lista noastră de legat

951
01:14:04,040 --> 01:14:08,430
de subarbori pe care le-am sarit peste.

952
01:14:08,430 --> 01:14:13,800
Vom traversa stânga acum,

953
01:14:13,800 --> 01:14:17,870
dar din moment ce inevitabil trebuie să se întoarcă la dreapta,

954
01:14:17,870 --> 01:14:26,140
Mergem să păstreze partea dreaptă în interiorul listei noastre struct.

955
01:14:26,140 --> 01:14:32,620
Apoi vom avea new_list sau 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
Am de gând să ignore erori verificarea asta, dar ar trebui să verificați pentru a vedea dacă e nul.

958
01:14:44,920 --> 01:14:50,540
New_list nodul se va indica -

959
01:14:50,540 --> 01:14:56,890
oh, de aceea l-am vrut aici. O să indice o listă struct secunde.

960
01:14:56,890 --> 01:15:02,380
Asta e doar modul în care locul de muncă legate de preturi.

961
01:15:02,380 --> 01:15:04,810
Acest lucru este la fel ca o listă legată int

962
01:15:04,810 --> 01:15:06,960
cu excepția suntem doar inlocuirea int cu * nod.

963
01:15:06,960 --> 01:15:11,040
Este exact la fel.

964
01:15:11,040 --> 01:15:15,100
Deci new_list, valoarea nodului new_list noastre,

965
01:15:15,100 --> 01:15:19,120
va fi actuală-> dreapta.

966
01:15:19,120 --> 01:15:24,280
Valoarea noastre new_list-> lângă va fi lista noastră inițială,

967
01:15:24,280 --> 01:15:30,760
și apoi vom actualiza lista noastră pentru a indica new_list.

968
01:15:30,760 --> 01:15:33,650
>> Acum avem nevoie de un fel de fel de lucruri de tragere,

969
01:15:33,650 --> 01:15:37,020
ca și cum ne-am străbătut întregul subarbore stânga.

970
01:15:37,020 --> 01:15:40,480
Acum, avem nevoie pentru a scoate lucrurile din ea,

971
01:15:40,480 --> 01:15:43,850
ca actuală este nulă, noi nu vrem să se întoarcă doar false.

972
01:15:43,850 --> 01:15:50,370
Dorim să trageți acum în afara de la lista noastră de nou.

973
01:15:50,370 --> 01:15:53,690
Un mod convenabil de a face acest lucru - ei bine, de fapt, nu e mai multe moduri de a face acest lucru.

974
01:15:53,690 --> 01:15:56,680
Oricine are o sugestie?

975
01:15:56,680 --> 01:15:58,790
În cazul în care ar trebui să fac asta sau cum ar trebui să fac asta?

976
01:15:58,790 --> 01:16:08,010
Avem doar câteva minute, dar orice sugestii?

977
01:16:08,010 --> 01:16:14,750
În loc de - un fel, în loc de starea noastră fiind în timp ce,

978
01:16:14,750 --> 01:16:17,090
ceea ce ne caută în prezent nu este nulă,

979
01:16:17,090 --> 01:16:22,340
în schimb vom continua să meargă până la lista noastră de sine este nulă.

980
01:16:22,340 --> 01:16:25,680
Deci, în cazul în care lista noastră se termină prin a fi nulă,

981
01:16:25,680 --> 01:16:30,680
apoi ne-am alerga afară de lucruri pentru a căuta, de a căuta peste.

982
01:16:30,680 --> 01:16:39,860
Dar asta înseamnă că primul lucru in lista noastra este doar de gând să fie primul nod.

983
01:16:39,860 --> 01:16:49,730
Primul lucru va fi - nu mai avem nevoie pentru a vedea asta.

984
01:16:49,730 --> 01:16:58,710
Deci lista-> n va fi copacul nostru.

985
01:16:58,710 --> 01:17:02,860
lista-> lângă va fi nul.

986
01:17:02,860 --> 01:17:07,580
Și acum în timp ce lista nu nul egal.

987
01:17:07,580 --> 01:17:11,610
Actuală este de gând să trage ceva din lista noastră.

988
01:17:11,610 --> 01:17:13,500
Deci actuală este de gând să egal lista-> n.

989
01:17:13,500 --> 01:17:20,850
Și apoi lista este de gând să egal lista-> n, sau lista-> urmator.

990
01:17:20,850 --> 01:17:23,480
Deci, în cazul în care valoarea actuală este egală cu valoarea.

991
01:17:23,480 --> 01:17:28,790
Acum putem adăuga ambele noastre indicatorul dreapta și stânga noastră indicatorul

992
01:17:28,790 --> 01:17:32,900
atâta timp cât acestea nu sunt nule.

993
01:17:32,900 --> 01:17:36,390
Aici, cred că ar trebui să fi făcut ca, în primul rând.

994
01:17:36,390 --> 01:17:44,080
În cazul în care (actuală-> dreapta = NULL!)

995
01:17:44,080 --> 01:17:56,380
atunci vom insera acel nod în lista noastră.

996
01:17:56,380 --> 01:17:59,290
În cazul în care (actuală-> stânga), aceasta este un pic de muncă suplimentară, dar e în regulă.

997
01:17:59,290 --> 01:18:02,690
În cazul în care (actuală-> stînga = NULL!),

998
01:18:02,690 --> 01:18:14,310
și vom introduce în lista noastră de stânga legat,

999
01:18:14,310 --> 01:18:19,700
și că ar trebui să fie.

1000
01:18:19,700 --> 01:18:22,670
Noi itera - atâta timp cât avem ceva în lista noastră,

1001
01:18:22,670 --> 01:18:26,640
avem un alt nod să se uite la.

1002
01:18:26,640 --> 01:18:28,920
Deci ne uităm la acel nod,

1003
01:18:28,920 --> 01:18:31,390
am avansa lista noastră de la următoarea.

1004
01:18:31,390 --> 01:18:34,060
În cazul în care nodul este valoarea pe care o căutăm, ne putem întoarce adevărat.

1005
01:18:34,060 --> 01:18:37,640
Introduce altceva ambele subarbori noastre stânga și la dreapta,

1006
01:18:37,640 --> 01:18:40,510
atâta timp cât acestea nu sunt nule, în lista noastră

1007
01:18:40,510 --> 01:18:43,120
astfel încât să putem merge în mod inevitabil asupra lor.

1008
01:18:43,120 --> 01:18:45,160
Deci, dacă acestea nu au fost nule,

1009
01:18:45,160 --> 01:18:47,950
în cazul în care indicatorul nostru de rădăcină a indicat două lucruri,

1010
01:18:47,950 --> 01:18:51,670
apoi la prima am scos ceva atât de lista noastră de sfârșește prin a fi nulă.

1011
01:18:51,670 --> 01:18:56,890
Și apoi am pus două lucruri înapoi în, așa că acum lista noastră este de dimensiuni 2.

1012
01:18:56,890 --> 01:19:00,030
Apoi mergem la bucla înapoi și suntem doar de gând să trageți,

1013
01:19:00,030 --> 01:19:04,250
să zicem, indicatorul stângă a nodului radacina noastra.

1014
01:19:04,250 --> 01:19:07,730
Și că voi păstra doar se întâmplă, vom ajunge looping peste tot.

1015
01:19:07,730 --> 01:19:11,280
>> Observați că aceasta a fost semnificativ mai complicat

1016
01:19:11,280 --> 01:19:14,160
în soluția recursivă.

1017
01:19:14,160 --> 01:19:17,260
Și am spus de mai multe ori

1018
01:19:17,260 --> 01:19:25,120
că soluția recursivă, de obicei, are multe în comun cu iterativ soluție.

1019
01:19:25,120 --> 01:19:30,820
Aici acest lucru este exact ceea ce soluția este de a face recursiv.

1020
01:19:30,820 --> 01:19:36,740
Singura schimbare este că în loc de a folosi implicit stiva, stivă programul,

1021
01:19:36,740 --> 01:19:40,840
ca felul tău de a ține evidența a ceea ce nodurile pe care încă mai trebuie să viziteze,

1022
01:19:40,840 --> 01:19:45,430
acum va trebui să utilizați în mod explicit o listă legat.

1023
01:19:45,430 --> 01:19:49,070
În ambele cazuri, se ține evidența a ceea ce nod trebuie încă să fie vizitate.

1024
01:19:49,070 --> 01:19:51,790
În cazul recursiv e doar mai ușor, deoarece o stivă

1025
01:19:51,790 --> 01:19:57,100
este pus în aplicare pentru tine, ca stiva programului.

1026
01:19:57,100 --> 01:19:59,550
Observați că această listă legată, aceasta este o stivă.

1027
01:19:59,550 --> 01:20:01,580
Orice am doar pus pe stivă

1028
01:20:01,580 --> 01:20:09,960
este imediat ceea ce am de gând să scoate teancul pentru a vizita următoare.

1029
01:20:09,960 --> 01:20:14,380
Nu mai avem timp, dar orice întrebări?

1030
01:20:14,380 --> 01:20:23,530
[Student, neinteligibil]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Da. Deci, dacă avem lista noastră de legat,

1032
01:20:27,790 --> 01:20:30,150
curentă este de gând să indice tipul ăsta,

1033
01:20:30,150 --> 01:20:34,690
iar acum suntem avanseaza doar lista noastră de legat să se concentreze pe tipul ăsta.

1034
01:20:34,690 --> 01:20:44,200
Ne traversează peste lista legat în acea linie.

1035
01:20:44,200 --> 01:20:51,200
Și atunci cred că ar trebui să ne eliberăm lista noastră de legat și chestii

1036
01:20:51,200 --> 01:20:53,880
o dată înainte de a reveni adevărate sau false, trebuie să ne

1037
01:20:53,880 --> 01:20:57,360
itera peste lista noastră de legătură și mereu aici, cred,

1038
01:20:57,360 --> 01:21:03,900
dacă actuală dreptul de a nu este egal cu, se adaugă, așa că acum vrem să eliberăm

1039
01:21:03,900 --> 01:21:09,600
actuală pentru că, ei bine, am uitat complet despre lista? Da.

1040
01:21:09,600 --> 01:21:12,880
Deci, asta e ceea ce vrem să facem aici.

1041
01:21:12,880 --> 01:21:16,730
Unde e indicatorul?

1042
01:21:16,730 --> 01:21:23,320
Actuală a fost atunci - vrem să o listă struct * 10 este egal cu lista următoare.

1043
01:21:23,320 --> 01:21:29,240
Lista gratuită, lista = temp.

1044
01:21:29,240 --> 01:21:32,820
Și, în cazul în care ne vom întoarce adevărat, avem nevoie de a repeta

1045
01:21:32,820 --> 01:21:37,050
peste restul listei noastre legate eliberarea lucruri.

1046
01:21:37,050 --> 01:21:39,700
Cel mai frumos lucru despre soluția recursivă este eliberarea lucruri

1047
01:21:39,700 --> 01:21:44,930
înseamnă doar factorings popping off stiva, care se va întâmpla pentru tine.

1048
01:21:44,930 --> 01:21:50,720
Deci, am trecut de la ceva care e ca 3 linii de hard-la-think-despre codul

1049
01:21:50,720 --> 01:21:57,520
pentru ceva care este semnificativ mai multe greu-de-cred-despre linii de cod.

1050
01:21:57,520 --> 01:22:00,620
Orice mai multe întrebări?

1051
01:22:00,620 --> 01:22:08,760
Bine. Suntem bine. Pa!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]