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

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

3
00:00:04,890 --> 00:00:07,000
[Acest lucru este CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Bine ați venit la secțiunea 7.

5
00:00:09,080 --> 00:00:11,330
Datorită uragan Sandy,

6
00:00:11,330 --> 00:00:13,440
în loc de a avea o secțiune normală în această săptămână,

7
00:00:13,440 --> 00:00:17,650
facem această plimbare-prin, prin sectiunea de intrebari.

8
00:00:17,650 --> 00:00:22,830
Am de gând să fie în urma împreună cu problema Set 6 Caietul de sarcini,

9
00:00:22,830 --> 00:00:25,650
și trece prin toate întrebările din

10
00:00:25,650 --> 00:00:27,770
O secțiune a secțiunii Întrebări.

11
00:00:27,770 --> 00:00:30,940
Dacă există orice intrebari,

12
00:00:30,940 --> 00:00:32,960
vă rugăm să postați-le pe CS50 Discuss.

13
00:00:32,960 --> 00:00:35,480
>> Bine. Să începem.

14
00:00:35,480 --> 00:00:40,780
Chiar acum mă uit la pagina 3 din Caietul de sarcini set de probleme.

15
00:00:40,780 --> 00:00:44,110
Vom începe să discutați mai întâi despre arbori binari

16
00:00:44,110 --> 00:00:47,850
deoarece cei care au o mulțime de relevanță pentru set de probleme din această săptămână -

17
00:00:47,850 --> 00:00:49,950
Arborele Huffman de codificare.

18
00:00:49,950 --> 00:00:55,000
Una dintre structurile de date foarte primul am vorbit despre pe CS50 a fost matrice.

19
00:00:55,000 --> 00:01:00,170
Amintiți-vă că o matrice este o secvență de elemente -

20
00:01:00,170 --> 00:01:04,019
toate de același tip - depozitate chiar lângă altul în memorie.

21
00:01:04,019 --> 00:01:14,420
Dacă am o matrice întreg ca pot desena folosind acest stil de cutii de-numere întregi--

22
00:01:14,420 --> 00:01:20,290
Să spunem că am 5 în prima casetă, am 7 în al doilea,

23
00:01:20,290 --> 00:01:27,760
atunci am 8, 10, și 20 în caseta de finală.

24
00:01:27,760 --> 00:01:33,000
Amintiți-vă lucrurile, cei doi într-adevăr bune despre această matrice

25
00:01:33,000 --> 00:01:38,800
sunt că avem această acces constant în timp la orice element particular

26
00:01:38,800 --> 00:01:40,500
 în matrice, dacă știm indexul său.

27
00:01:40,500 --> 00:01:44,670
De exemplu, dacă vreau să iau al treilea element din matrice -

28
00:01:44,670 --> 00:01:47,870
la index 2 cu ajutorul nostru zero-based sistem de indexare -

29
00:01:47,870 --> 00:01:52,220
Am literalmente Trebuie doar pentru a face un calcul matematic simplu,

30
00:01:52,220 --> 00:01:56,170
hop la această poziție în matrice,

31
00:01:56,170 --> 00:01:57,840
scoate 8 care este depozitat acolo,

32
00:01:57,840 --> 00:01:59,260
și eu sunt bine să plec.

33
00:01:59,260 --> 00:02:03,350
>> Unul dintre lucrurile rele despre această matrice - despre care am vorbit

34
00:02:03,350 --> 00:02:05,010
atunci când am discutat de preturi legate de -

35
00:02:05,010 --> 00:02:09,120
este că, dacă vreau să inserați un element în această matrice,

36
00:02:09,120 --> 00:02:11,090
Am de gând să aibă de a face unele schimbarea în jurul valorii de.

37
00:02:11,090 --> 00:02:12,940
De exemplu, aceasta matrice aici

38
00:02:12,940 --> 00:02:16,850
este în ordine sortate - sortate în ordine crescătoare -

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

40
00:02:19,440 --> 00:02:23,100
dar dacă vreau să inserați numărul 9 în această matrice,

41
00:02:23,100 --> 00:02:27,460
Am de gând să aibă de a schimba unele dintre elementele pentru a face spațiu.

42
00:02:27,460 --> 00:02:30,440
Putem trage asta aici.

43
00:02:30,440 --> 00:02:35,650
Am de gând să aibă de a muta 5, 7, și apoi 8;

44
00:02:35,650 --> 00:02:38,720
crea o discrepanță în cazul în care pot pune 9,

45
00:02:38,720 --> 00:02:45,910
și apoi 10 și 20 pot merge la dreapta 9.

46
00:02:45,910 --> 00:02:49,450
Aceasta este un fel de durere, deoarece, în cel mai rău caz -

47
00:02:49,450 --> 00:02:54,350
atunci când avem de a insera fie la începutul sau la sfârșitul

48
00:02:54,350 --> 00:02:56,040
de matrice, în funcție de modul în care suntem deplasare -

49
00:02:56,040 --> 00:02:58,850
s-ar putea sfârși prin a fi nevoie să transfere toate elementele

50
00:02:58,850 --> 00:03:00,750
că suntem în prezent, stocarea în matrice.

51
00:03:00,750 --> 00:03:03,810
>> Deci, ceea ce a fost în jurul valorii de acest fel?

52
00:03:03,810 --> 00:03:09,260
Mod în jurul valorii de acest lucru a fost pentru a merge la metoda lista noastră legat-în cazul în care -

53
00:03:09,260 --> 00:03:19,820
în loc de a stoca elementele 5, 7, 8, 10, 20 și tot unul lângă celălalt în memorie -

54
00:03:19,820 --> 00:03:25,630
ceea ce am făcut a fost în schimb a le stoca fel de oriunde am vrut să le stocați

55
00:03:25,630 --> 00:03:32,470
în aceste noduri listă legat-pe care eu desen aici, un fel de ad-hoc.

56
00:03:32,470 --> 00:03:42,060
Și apoi i-am conectate împreună folosind aceste indicii pentru următoarele.

57
00:03:42,060 --> 00:03:44,370
Pot avea un pointer de la 5 la 7,

58
00:03:44,370 --> 00:03:46,420
un pointer la 7 la 8,

59
00:03:46,420 --> 00:03:47,770
un pointer la 8 la 10,

60
00:03:47,770 --> 00:03:51,220
și, în sfârșit, un pointer la 10 la 20,

61
00:03:51,220 --> 00:03:54,880
și apoi un pointer nul la 20 care indică faptul că nu este nimic stânga.

62
00:03:54,880 --> 00:03:59,690
Compromisul pe care le avem aici

63
00:03:59,690 --> 00:04:05,360
este că acum, dacă vrem să inserați numărul 9 în lista noastră de sortat,

64
00:04:05,360 --> 00:04:08,270
tot ce trebuie să faceți este să creați un nou nod cu 9,

65
00:04:08,270 --> 00:04:12,290
cabla-l până la punctul la locul potrivit,

66
00:04:12,290 --> 00:04:20,630
și apoi re-fir de la punctul 8 până la 9.

67
00:04:20,630 --> 00:04:25,660
Asta e destul de repede, presupunând că știm exact unde vrem să inserați 9.

68
00:04:25,660 --> 00:04:32,610
Dar compromis în schimbul pentru acest lucru este că ne-am pierdut acum acces constant în timp

69
00:04:32,610 --> 00:04:36,230
pentru orice element special în structura noastră de date.

70
00:04:36,230 --> 00:04:40,950
De exemplu, dacă vreau să găsesc al patrulea element în această listă legată,

71
00:04:40,950 --> 00:04:43,510
Am de gând să trebuie să înceapă de la începutul listei

72
00:04:43,510 --> 00:04:48,930
și de a lucra prin felul meu de numărare nod-de-nod până când am găsit patra.

73
00:04:48,930 --> 00:04:55,870
>> În scopul de a obține performanțe mai bune decât acces o listă legată -

74
00:04:55,870 --> 00:04:59,360
dar păstrează, de asemenea, câteva dintre beneficiile pe care le-am avut

75
00:04:59,360 --> 00:05:01,800
în ceea ce privește introducerea în timp dintr-o listă legată -

76
00:05:01,800 --> 00:05:05,750
un arbore binar este de gând să nevoie de a utiliza memoria un pic mai mult.

77
00:05:05,750 --> 00:05:11,460
În special, în loc de a avea doar un pointer într-un nod arbore binar -

78
00:05:11,460 --> 00:05:13,350
cum ar fi lista de legat-nod nu -

79
00:05:13,350 --> 00:05:16,950
vom adăuga un pointer al doilea nod arbore binar.

80
00:05:16,950 --> 00:05:19,950
Mai degrabă decât având în doar un pointer la elementul următor,

81
00:05:19,950 --> 00:05:24,420
vom avea un pointer la un copil la stânga și la dreapta un copil.

82
00:05:24,420 --> 00:05:26,560
>> Să deseneze o imagine pentru a vedea ce că de fapt arata ca.

83
00:05:26,560 --> 00:05:31,350
Din nou, am de gând să utilizeze aceste cutii și săgeți.

84
00:05:31,350 --> 00:05:37,150
Un nod arbore binar se va începe cu doar o cutie simpla.

85
00:05:37,150 --> 00:05:40,940
Se va avea un spațiu pentru valoarea,

86
00:05:40,940 --> 00:05:47,280
și apoi, de asemenea, va avea un spatiu pentru copilul stânga și dreapta copilului.

87
00:05:47,280 --> 00:05:49,280
Am de gând să-i eticheteze aici.

88
00:05:49,280 --> 00:05:57,560
Vom avea copilul din stânga, iar apoi vom avea dreptul copilului.

89
00:05:57,560 --> 00:05:59,920
Există multe moduri diferite de a face acest lucru.

90
00:05:59,920 --> 00:06:02,050
Uneori, pentru spațiu și confort,

91
00:06:02,050 --> 00:06:06,460
Voi trage de fapt ca eu fac aici, pe jos

92
00:06:06,460 --> 00:06:10,910
în cazul în care am de gând să aibă o valoare în partea de sus,

93
00:06:10,910 --> 00:06:14,060
și apoi copilul dreapta pe dreapta-jos,

94
00:06:14,060 --> 00:06:16,060
și copilul stânga pe stânga-jos.

95
00:06:16,060 --> 00:06:20,250
Revenind la această diagramă de top,

96
00:06:20,250 --> 00:06:22,560
avem valoare la foarte de sus,

97
00:06:22,560 --> 00:06:25,560
atunci avem indicatorul din stânga-copil, și apoi avem indicatorul dreapta-copil.

98
00:06:25,560 --> 00:06:30,110
>> În problema Specificatii Set,

99
00:06:30,110 --> 00:06:33,110
vorbim despre desen un nod care are o valoare de 7,

100
00:06:33,110 --> 00:06:39,750
și apoi un pointer la stânga-copil, care este nul, iar un indicator dreapta-copil, care este nul.

101
00:06:39,750 --> 00:06:46,040
Putem scrie, fie NULL capital în spațiul pentru

102
00:06:46,040 --> 00:06:51,610
atât copilul stânga și dreapta copil, sau putem desena această linie oblică

103
00:06:51,610 --> 00:06:53,750
prin fiecare dintre casetele pentru a indica faptul că e nul.

104
00:06:53,750 --> 00:06:57,560
Am de gând să fac asta doar pentru ca e mai simplu.

105
00:06:57,560 --> 00:07:03,700
Ceea ce vedeti aici sunt două modalități de a diagramelor un foarte simplu nod arbore binar

106
00:07:03,700 --> 00:07:07,960
în cazul în care avem valoarea 7 și pointeri nule copilului.

107
00:07:07,960 --> 00:07:15,220
>> A doua parte a discuțiilor noastre despre modul în specificații cu liste legate de -

108
00:07:15,220 --> 00:07:18,270
Amintiți-vă, am avut doar să stai la element foarte primul dintr-o listă

109
00:07:18,270 --> 00:07:20,270
să-și amintească întreaga listă -

110
00:07:20,270 --> 00:07:26,140
și, de asemenea, cu un arbore binar, trebuie doar să stai la un pointer la copac

111
00:07:26,140 --> 00:07:31,120
în scopul de a menține controlul asupra întregii structuri de date.

112
00:07:31,120 --> 00:07:36,150
Acest element special al arborelui este numit nodul rădăcină al arborelui.

113
00:07:36,150 --> 00:07:43,360
De exemplu, în cazul în care acest nod una - acest nod care conține valoarea 7

114
00:07:43,360 --> 00:07:45,500
cu indicii nule stânga-dreapta și-copil -

115
00:07:45,500 --> 00:07:47,360
au fost valoare numai în copacul nostru,

116
00:07:47,360 --> 00:07:50,390
atunci acest lucru ar fi nodul radacina noastra.

117
00:07:50,390 --> 00:07:52,240
E începutul copacul nostru.

118
00:07:52,240 --> 00:07:58,530
Putem vedea acest mic o mai clar după ce vom începe să adăugați mai multe noduri la copacul nostru.

119
00:07:58,530 --> 00:08:01,510
Lasă-mă să trageți o pagină nouă.

120
00:08:01,510 --> 00:08:05,000
>> Acum vom desena un copac care are 7 la rădăcină,

121
00:08:05,000 --> 00:08:10,920
și 3 interiorul copilului stânga, și 9 în interiorul copilului drept.

122
00:08:10,920 --> 00:08:13,500
Din nou, acest lucru este destul de simplu.

123
00:08:13,500 --> 00:08:26,510
Avem 7, trage un nod pentru 3, un nod pentru 9,

124
00:08:26,510 --> 00:08:32,150
și am de gând să setați indicatorul din stânga-copil de 7 pentru a indica nodul care conține 3,

125
00:08:32,150 --> 00:08:37,850
și indicatorul dreapta copil al nodului care conține 7 la nodul care conține 9.

126
00:08:37,850 --> 00:08:42,419
Acum, din 3 și 9 nu au copii,

127
00:08:42,419 --> 00:08:48,500
vom stabili toate indicii copiilor lor să fie nul.

128
00:08:48,500 --> 00:08:56,060
Aici, rădăcina arborelui nostru corespunde nodul care conține numărul 7.

129
00:08:56,060 --> 00:09:02,440
Puteți vedea că, dacă tot ce avem este un pointer la acel nod rădăcină,

130
00:09:02,440 --> 00:09:07,330
putem merge apoi prin copacul nostru și accesa ambele noduri copil -

131
00:09:07,330 --> 00:09:10,630
3, cât și 9.

132
00:09:10,630 --> 00:09:14,820
Nu este nevoie de a menține indicii pentru fiecare nod unic pe copac.

133
00:09:14,820 --> 00:09:22,080
Bine. Acum vom adăuga un alt nod la această schemă.

134
00:09:22,080 --> 00:09:25,370
Vom adăuga un nod care conține 6,

135
00:09:25,370 --> 00:09:34,140
și vom adăuga acest copil ca dreptul de nodul care conține 3.

136
00:09:34,140 --> 00:09:41,850
Pentru a face asta, am de gând să șteargă care pointer nul în 3-nodul

137
00:09:41,850 --> 00:09:47,750
și-l sarme pana la punctul la nodul care conține 6. Bine.

138
00:09:47,750 --> 00:09:53,800
>> În acest moment, să trecem peste un pic de terminologie.

139
00:09:53,800 --> 00:09:58,230
Pentru a începe, motivul pentru care aceasta se numește un arbore binar, în special,

140
00:09:58,230 --> 00:10:00,460
este faptul că are doi pointeri copil.

141
00:10:00,460 --> 00:10:06,020
Există alte tipuri de copaci, care au mai multe indicații copilului.

142
00:10:06,020 --> 00:10:10,930
În special, ai făcut-o "încerca" din seria Problema 5.

143
00:10:10,930 --> 00:10:19,310
Veți observa că în această încercare, ai avut 27 indicii diferite la diferiți copii -

144
00:10:19,310 --> 00:10:22,410
una pentru fiecare din cele 26 de litere din alfabetul englez,

145
00:10:22,410 --> 00:10:25,410
și apoi pentru 27 apostrof -

146
00:10:25,410 --> 00:10:28,900
astfel, care este similar cu un tip de copac.

147
00:10:28,900 --> 00:10:34,070
Dar aici, din moment binar e, avem doar doi pointeri copil.

148
00:10:34,070 --> 00:10:37,880
>> În plus față de acest nod rădăcină despre care am vorbit,

149
00:10:37,880 --> 00:10:41,470
am fost, de asemenea aruncat în jurul valorii de acest termen "copil".

150
00:10:41,470 --> 00:10:44,470
Ce înseamnă pentru un nod să fie un copil de un alt nod?

151
00:10:44,470 --> 00:10:54,060
Este literalmente înseamnă că un nod copil este un copil de un alt nod

152
00:10:54,060 --> 00:10:58,760
în cazul în care alt nod are una dintre indicii copil sale stabilite pentru a indica faptul că nodul.

153
00:10:58,760 --> 00:11:01,230
Pentru a pune acest lucru în termeni mai concreți,

154
00:11:01,230 --> 00:11:11,170
dacă 3 este indicat de unul dintre indicii copil de 7, apoi 3 este un copil de 7.

155
00:11:11,170 --> 00:11:14,510
Dacă ar fi să ne dăm seama ce copiii de la 7 sunt -

156
00:11:14,510 --> 00:11:18,510
ei bine, vom vedea că 7 are un pointer la 3 și un pointer la 9,

157
00:11:18,510 --> 00:11:22,190
deci 9 și 3 sunt copii de 7.

158
00:11:22,190 --> 00:11:26,650
Nouă nu are copii, deoarece indicii sai copii sunt nule,

159
00:11:26,650 --> 00:11:30,940
și 3 are un singur copil, 6.

160
00:11:30,940 --> 00:11:37,430
Șase copii nu are, de asemenea, deoarece ambele indicii sai sunt nule, pe care o vom trage chiar acum.

161
00:11:37,430 --> 00:11:45,010
>> În plus, vorbim, de asemenea, despre parintii unui nod special,

162
00:11:45,010 --> 00:11:51,100
și acest lucru este, după cum te-ai astepta, reversul acestei descrieri copil.

163
00:11:51,100 --> 00:11:58,620
Fiecare nod are un singur părinte - în loc de două ca s-ar putea aștepta cu oamenii.

164
00:11:58,620 --> 00:12:03,390
De exemplu, mamă a 3 este 7.

165
00:12:03,390 --> 00:12:10,800
Mamă a 9 este, de asemenea, 7, și mamă a 6 este 3. Nu de mult la ea.

166
00:12:10,800 --> 00:12:15,720
Avem, de asemenea termeni pentru a vorbi despre bunici și nepoți,

167
00:12:15,720 --> 00:12:18,210
și, în general, mai vorbim despre strămoși

168
00:12:18,210 --> 00:12:20,960
și descendenți ai un anumit nod.

169
00:12:20,960 --> 00:12:25,710
Strămoș al unui nod - sau strămoșii, mai degrabă, de un nod -

170
00:12:25,710 --> 00:12:32,730
sunt toate nodurile care se află pe calea de la radacina la nodul.

171
00:12:32,730 --> 00:12:36,640
De exemplu, dacă mă uit la nodul 6,

172
00:12:36,640 --> 00:12:46,430
atunci strămoșii sunt de gând să fie atât 3 și 7.

173
00:12:46,430 --> 00:12:55,310
Strămoșii din 9, de exemplu, sunt - dacă mă uit la nodul 9 -

174
00:12:55,310 --> 00:12:59,990
apoi strămoș al 9 este la doar 7.

175
00:12:59,990 --> 00:13:01,940
Și urmașii sunt exact invers.

176
00:13:01,940 --> 00:13:05,430
Dacă vreau să se uite la toate descendenți din 7,

177
00:13:05,430 --> 00:13:11,020
atunci am să te uiți la toate nodurile de sub el.

178
00:13:11,020 --> 00:13:16,950
Deci, am 3, 9, 6 și toți, ca descendenți ai 7.

179
00:13:16,950 --> 00:13:24,170
>> Termenul final, că vom vorbi despre această noțiune este de a fi un frate.

180
00:13:24,170 --> 00:13:27,980
Fratii - un fel de urma de-a lungul pe acești termeni de familie -

181
00:13:27,980 --> 00:13:33,150
sunt noduri care sunt la același nivel în copac.

182
00:13:33,150 --> 00:13:42,230
Deci, 3 și 9 sunt frații, deoarece acestea sunt la același nivel în arbore.

183
00:13:42,230 --> 00:13:46,190
Amândoi au același părinte, 7.

184
00:13:46,190 --> 00:13:51,400
Cele 6 nu are frați, deoarece 9 nu are nici un copil.

185
00:13:51,400 --> 00:13:55,540
Și 7 nu are nici frați, pentru că e rădăcina arborelui nostru,

186
00:13:55,540 --> 00:13:59,010
și nu există decât vreodată 1 radacina.

187
00:13:59,010 --> 00:14:02,260
Pentru 7 pentru a avea frați ar trebui să fie un nod de mai sus 7.

188
00:14:02,260 --> 00:14:07,480
Nu ar trebui să fie un părinte de 7, caz în care 7 nu ar mai fi rădăcina arborelui.

189
00:14:07,480 --> 00:14:10,480
Apoi, faptul că noua mamă din 7 ar trebui, de asemenea, să aibă un copil,

190
00:14:10,480 --> 00:14:16,480
și acel copil ar fi atunci fratele de 7.

191
00:14:16,480 --> 00:14:21,040
>> Bine. Mergem mai departe.

192
00:14:21,040 --> 00:14:24,930
Când am început discuția noastră de arbori binari,

193
00:14:24,930 --> 00:14:28,790
am vorbit despre modul în care am fost de gând să le folosească pentru a

194
00:14:28,790 --> 00:14:32,800
obține un avantaj în ambele tablouri si liste legate.

195
00:14:32,800 --> 00:14:37,220
Și modul în care ne vom face acest lucru este cu această proprietate prin care se dispune.

196
00:14:37,220 --> 00:14:41,080
Spunem că un arbore binar ordonat se, conform caietului de sarcini,

197
00:14:41,080 --> 00:14:45,740
în cazul în care pentru fiecare nod din arbore noastră, toți urmașii săi pe stânga -

198
00:14:45,740 --> 00:14:48,670
copilul din stânga și pentru toți urmașii copilului stanga -

199
00:14:48,670 --> 00:14:54,510
au valori mai mici, și toate nodurile de pe dreapta -

200
00:14:54,510 --> 00:14:57,770
copilului dreptul și pentru toți urmașii copilului dreptul de -

201
00:14:57,770 --> 00:15:02,800
au noduri mai mari decât valoarea nodului curent care ne uitam la.

202
00:15:02,800 --> 00:15:07,850
Doar pentru simplitate, vom presupune că nu există nici o noduri duplicate din copacul nostru.

203
00:15:07,850 --> 00:15:11,180
De exemplu, în acest copac nu am de gând să se ocupe de caz

204
00:15:11,180 --> 00:15:13,680
în cazul în care avem valoarea 7 la rădăcină

205
00:15:13,680 --> 00:15:16,720
 și apoi avem, de asemenea, valoarea 7 în altă parte în copac.

206
00:15:16,720 --> 00:15:24,390
În acest caz, veți observa că acest copac este într-adevăr comandat.

207
00:15:24,390 --> 00:15:26,510
Avem 7 la valoarea rădăcină.

208
00:15:26,510 --> 00:15:29,720
Totul la stânga din 7 -

209
00:15:29,720 --> 00:15:35,310
dacă am anula toate aceste mărci mici aici -

210
00:15:35,310 --> 00:15:40,450
totul la stânga de 7 - 3 și 6 -

211
00:15:40,450 --> 00:15:49,410
aceste valori sunt atât mai puțin de 7, și totul la dreapta - care este doar asta 9 -

212
00:15:49,410 --> 00:15:53,450
este mai mare decât 7.

213
00:15:53,450 --> 00:15:58,650
>> Acest lucru nu este singurul copac care conțin comandat aceste valori,

214
00:15:58,650 --> 00:16:03,120
dar hai sa mai trage o câteva dintre ele.

215
00:16:03,120 --> 00:16:05,030
Acolo este de fapt o grămadă de moduri în care putem face acest lucru.

216
00:16:05,030 --> 00:16:09,380
Am de gând să utilizeze o prescurtare doar pentru a menține lucrurile simple în cazul în care -

217
00:16:09,380 --> 00:16:11,520
mai degrabă decât să se inspire din întreaga Cutii-si-săgeți -

218
00:16:11,520 --> 00:16:14,220
Sunt doar de gând să tragă numerele și adăugați-le săgeți de legătură.

219
00:16:14,220 --> 00:16:22,920
Pentru a începe, vom scrie doar copacul nostru original, din nou, în cazul în care am avut 7, iar apoi un 3,

220
00:16:22,920 --> 00:16:25,590
și apoi înapoi la 3 subliniat dreptul la 6,

221
00:16:25,590 --> 00:16:30,890
și 7 au avut un copil care a fost drept 9.

222
00:16:30,890 --> 00:16:33,860
Bine. Ce e un alt mod pe care am putea scrie acest copac?

223
00:16:33,860 --> 00:16:38,800
În loc de a avea 3 să fie copilul din stânga din 7,

224
00:16:38,800 --> 00:16:41,360
am putea avea, de asemenea, să fie 6 copil de 7 stânga,

225
00:16:41,360 --> 00:16:44,470
și apoi 3 să fie copilul stânga 6.

226
00:16:44,470 --> 00:16:48,520
Asta ar arata ca acest copac chiar aici, unde am luat 7,

227
00:16:48,520 --> 00:16:57,860
apoi 6, apoi 3, și un 9 pe dreapta.

228
00:16:57,860 --> 00:17:01,490
De asemenea, nu trebuie să aibă ca nodul 7 radacina noastra.

229
00:17:01,490 --> 00:17:03,860
Am putea avea, de asemenea, ca nod de 6 radacina noastra.

230
00:17:03,860 --> 00:17:06,470
Ce-ar fi ca arata?

231
00:17:06,470 --> 00:17:09,230
Dacă vom menține această proprietate ordonate,

232
00:17:09,230 --> 00:17:12,970
totul la stânga de 6 trebuie să fie mai mică de ea.

233
00:17:12,970 --> 00:17:16,540
Există doar o singură posibilitate, și asta e 3.

234
00:17:16,540 --> 00:17:19,869
Dar, apoi ca copilul dreptul de 6, avem două posibilități.

235
00:17:19,869 --> 00:17:25,380
În primul rând, am putea avea 7 și apoi 9,

236
00:17:25,380 --> 00:17:28,850
sau am putea trage - ca sunt pe cale să fac aici -

237
00:17:28,850 --> 00:17:34,790
în cazul în care avem 9, copilul drept al 6,

238
00:17:34,790 --> 00:17:39,050
si apoi 7 ca copilul din stânga a 9.

239
00:17:39,050 --> 00:17:44,240
>> Acum, 7 și 6 nu sunt valorile posibile numai pentru rădăcină.

240
00:17:44,240 --> 00:17:50,200
Am putea avea, de asemenea, 3 fie la rădăcină.

241
00:17:50,200 --> 00:17:52,240
Ce se întâmplă dacă 3 este la radacina?

242
00:17:52,240 --> 00:17:54,390
Aici, lucrurile devin un pic interesant.

243
00:17:54,390 --> 00:17:58,440
Trei nu are nici o valoare, care sunt mai puțin decât,

244
00:17:58,440 --> 00:18:02,070
astfel încât partea stângă a întregul copac este doar de gând să fie nul.

245
00:18:02,070 --> 00:18:03,230
Nu va fi nimic acolo.

246
00:18:03,230 --> 00:18:07,220
Pentru a dreptul, am putea enumera lucrurile în ordine crescătoare.

247
00:18:07,220 --> 00:18:15,530
Am putea avea 3, apoi 6, apoi 7, apoi 9.

248
00:18:15,530 --> 00:18:26,710
Sau, am putea face 3, apoi 6, apoi 9, apoi 7.

249
00:18:26,710 --> 00:18:35,020
Sau, am putea face 3, apoi 7, apoi 6, apoi 9.

250
00:18:35,020 --> 00:18:40,950
Sau, 3, 7 - de fapt, nu, nu putem face un 7 mai.

251
00:18:40,950 --> 00:18:43,330
Asta e un lucru noastră acolo.

252
00:18:43,330 --> 00:18:54,710
Putem face 9, și apoi de la 9 putem face 6 și apoi 7.

253
00:18:54,710 --> 00:19:06,980
Sau, putem face 3, apoi 9, apoi 7, apoi 6.

254
00:19:06,980 --> 00:19:12,490
>> Un lucru să vă atrag atenția aici este

255
00:19:12,490 --> 00:19:14,510
că acești copaci sunt un pic ciudat.

256
00:19:14,510 --> 00:19:17,840
În special, dacă ne uităm la cele 4 copacii de pe partea dreapta -

257
00:19:17,840 --> 00:19:20,930
Le voi inconjura, aici -

258
00:19:20,930 --> 00:19:28,410
acești copaci arata aproape exact ca o listă legată.

259
00:19:28,410 --> 00:19:32,670
Fiecare nod are un singur copil,

260
00:19:32,670 --> 00:19:38,950
și astfel nu avem nici de această structură arborescentă pe care le vedea, de exemplu,

261
00:19:38,950 --> 00:19:44,720
 în acest copac singuratic o aici pe stânga jos.

262
00:19:44,720 --> 00:19:52,490
Acești copaci sunt de fapt numite degenera arbori binari,

263
00:19:52,490 --> 00:19:54,170
și vom vorbi despre acestea mai mult în viitor -

264
00:19:54,170 --> 00:19:56,730
mai ales dacă te duci să le ia alte cursuri de informatică.

265
00:19:56,730 --> 00:19:59,670
Acesti copaci sunt degenerate.

266
00:19:59,670 --> 00:20:03,780
Ele nu sunt foarte folositoare, deoarece, într-adevăr, această structură se pretează

267
00:20:03,780 --> 00:20:08,060
 pentru căutare de ori similare cu cele dintr-o listă legată.

268
00:20:08,060 --> 00:20:13,050
Noi nu ajung să profite de memorie suplimentar - acest indicator suplimentar -

269
00:20:13,050 --> 00:20:18,840
din cauza structurii noastre a fi rău în acest fel.

270
00:20:18,840 --> 00:20:24,700
Mai degrabă decât merge pe și de scoate copacii binare, care au 9 la rădăcină,

271
00:20:24,700 --> 00:20:27,220
care este ultimul caz pe care le-ar avea,

272
00:20:27,220 --> 00:20:32,380
suntem în schimb, în ​​acest moment, o să vorbesc un pic despre acest alt termen

273
00:20:32,380 --> 00:20:36,150
pe care le folosim atunci când vorbim despre copaci, care se numește înălțime.

274
00:20:36,150 --> 00:20:45,460
>> Înălțimea unui copac este distanta de la radacina la nodul cel mai îndepărtat,

275
00:20:45,460 --> 00:20:48,370
sau mai degrabă numărul de hamei, care va trebui să facă, în scopul de a

276
00:20:48,370 --> 00:20:53,750
începe de la rădăcină și apoi ajunge la nodul cel mai îndepărtat în copac.

277
00:20:53,750 --> 00:20:57,330
Dacă ne uităm la unele dintre aceste copaci pe care le-am elaborat chiar aici,

278
00:20:57,330 --> 00:21:07,870
putem vedea că, dacă luăm acest copac, în colțul din stânga sus și vom începe de la 3,

279
00:21:07,870 --> 00:21:14,510
atunci avem de a face 1 hamei pentru a ajunge la 6, un hop secunde pentru a ajunge la 7,

280
00:21:14,510 --> 00:21:20,560
și un hop treia pentru a ajunge la 9.

281
00:21:20,560 --> 00:21:26,120
Deci, înălțimea acestui arbore este de 3.

282
00:21:26,120 --> 00:21:30,640
Putem face acelasi exercitiu pentru alți arbori prezentate cu acest verde,

283
00:21:30,640 --> 00:21:40,100
și vedem că înălțimea de toate aceste copaci este, de asemenea, într-adevăr 3.

284
00:21:40,100 --> 00:21:45,230
Asta e parte din ceea ce le face degenerate -

285
00:21:45,230 --> 00:21:53,750
că înălțimea lor este doar unul mai puțin decât numărul de noduri din arbore întreg.

286
00:21:53,750 --> 00:21:58,400
Dacă ne uităm la acest copac de altă natură care e înconjurat cu roșu, pe de altă parte,

287
00:21:58,400 --> 00:22:03,920
vom vedea că nodurile cele mai îndepărtate-frunze sunt 6 și 9 -

288
00:22:03,920 --> 00:22:06,940
frunze fiind acele noduri care nu au copii.

289
00:22:06,940 --> 00:22:11,760
Deci, în scopul de a obține de la nodul rădăcină fie la 6 sau de 9,

290
00:22:11,760 --> 00:22:17,840
avem de a face un hop pentru a ajunge la 7 și apoi un hop secunde pentru a ajunge la 9,

291
00:22:17,840 --> 00:22:21,240
și, de asemenea, doar un hop a doua din 7 pentru a ajunge la 6.

292
00:22:21,240 --> 00:22:29,080
Deci, înălțimea acestui copac de aici este la numai 2.

293
00:22:29,080 --> 00:22:35,330
Puteți merge înapoi și face acest lucru pentru toate celelalte pe care le copaci discutat anterior

294
00:22:35,330 --> 00:22:37,380
începând cu 7 și 6,

295
00:22:37,480 --> 00:22:42,500
și veți găsi că înălțimea tuturor acestor arbori este de asemenea, 2.

296
00:22:42,500 --> 00:22:46,320
>> Motivul pentru care am vorbit despre copaci ordonate binare

297
00:22:46,320 --> 00:22:50,250
și de ce sunt cool este că puteți căuta prin ele, în

298
00:22:50,250 --> 00:22:53,810
un mod foarte asemănător cu căutarea într-o matrice sortate.

299
00:22:53,810 --> 00:22:58,720
Acest lucru este în cazul în care vorbim despre obtinerea acel moment de căutare îmbunătățită

300
00:22:58,720 --> 00:23:02,730
peste simplă listă legată.

301
00:23:02,730 --> 00:23:05,010
Cu o listă legată - dacă doriți să găsiți un anumit element -

302
00:23:05,010 --> 00:23:07,470
esti cel mai bun de gând să facă un fel de căutare liniară

303
00:23:07,470 --> 00:23:10,920
în cazul în care începe de la începutul unei liste și unu-hop câte unul -

304
00:23:10,920 --> 00:23:12,620
un nod de un nod -

305
00:23:12,620 --> 00:23:16,060
prin întreaga listă până când găsiți tot ce căutați.

306
00:23:16,060 --> 00:23:19,440
Întrucât, în cazul în care aveți un arbore binar care este stocat în acest format frumos,

307
00:23:19,440 --> 00:23:23,300
puteți obține de fapt, mai mult de o căutare binară se întâmplă

308
00:23:23,300 --> 00:23:25,160
în cazul în care vă dezbina si cucereste

309
00:23:25,160 --> 00:23:29,490
si cauta prin jumatatea corespunzătoare a arborelui la fiecare pas.

310
00:23:29,490 --> 00:23:32,840
Să vedem cum funcționează.

311
00:23:32,840 --> 00:23:38,850
>> Dacă avem - din nou, merge inapoi la copacul nostru originale -

312
00:23:38,850 --> 00:23:46,710
vom începe la 7, avem 3 pe partea stângă, 9 pe dreapta,

313
00:23:46,710 --> 00:23:51,740
și sub 3 avem 6.

314
00:23:51,740 --> 00:24:01,880
Dacă vrem să caute numărul 6 în acest copac, să începem de la rădăcină.

315
00:24:01,880 --> 00:24:08,910
Ne-ar compara valoarea pe care o căutăm, să zicem 6,

316
00:24:08,910 --> 00:24:12,320
la valoarea stocate în nodul care ne caută în prezent, 7,

317
00:24:12,320 --> 00:24:21,200
constată că, într-adevăr 6 este mai mic de 7, deci am muta la stânga.

318
00:24:21,200 --> 00:24:25,530
În cazul în care valoarea de 6 au fost mai mare de 7, ne-am fi mutat în schimb spre dreapta.

319
00:24:25,530 --> 00:24:29,770
Din moment ce știm că - din cauza structurii de arbore binar ordonat noastre -

320
00:24:29,770 --> 00:24:33,910
toate valorile mai mici de 7 vor fi depozitate la stânga din 7,

321
00:24:33,910 --> 00:24:40,520
nu este nevoie de a deranja chiar în căutarea prin partea dreaptă a arborelui.

322
00:24:40,520 --> 00:24:43,780
După ce vom trece la stânga și suntem acum la nodul care conține 3,

323
00:24:43,780 --> 00:24:48,110
putem face o astfel de comparație din nou aceeași în cazul în care vom compara 3 și 6.

324
00:24:48,110 --> 00:24:52,430
Și am găsit că în timp ce 6 - valoarea pe care o căutăm - este mai mare decât 3,

325
00:24:52,430 --> 00:24:58,580
putem merge la partea din dreapta a nodului conține 3.

326
00:24:58,580 --> 00:25:02,670
Nu e nici partea stanga aici, asa ca am putut ignora faptul că.

327
00:25:02,670 --> 00:25:06,510
Dar noi știm că doar pentru că ne uităm la copac în sine,

328
00:25:06,510 --> 00:25:08,660
și putem vedea că arborele nu are copii.

329
00:25:08,660 --> 00:25:13,640
>> Este, de asemenea, destul de ușor să se uite în sus 6 din acest copac, dacă facem noi înșine ca oameni,

330
00:25:13,640 --> 00:25:16,890
dar hai să urmați acest proces mecanic ca un calculator ar face

331
00:25:16,890 --> 00:25:18,620
pentru a înțelege cu adevărat algoritm.

332
00:25:18,620 --> 00:25:26,200
În acest moment, suntem acum se uită la un nod care conține 6,

333
00:25:26,200 --> 00:25:29,180
și noi suntem în căutarea pentru valoarea 6,

334
00:25:29,180 --> 00:25:31,740
astfel, într-adevăr, am găsit nodul corespunzător.

335
00:25:31,740 --> 00:25:35,070
Am găsit valoarea 6 în copacul nostru, și ne putem opri căutarea noastră.

336
00:25:35,070 --> 00:25:37,330
În acest moment, în funcție de ce se întâmplă,

337
00:25:37,330 --> 00:25:41,870
putem spune, da, am gasit valoarea 6, acesta există în copacul nostru.

338
00:25:41,870 --> 00:25:47,640
Sau, dacă suntem de planificare pentru a insera un nod sau de a face ceva, putem face asta în acest moment.

339
00:25:47,640 --> 00:25:53,010
>> Hai sa facem un cuplu mai multe căutări doar pentru a vedea cum funcționează.

340
00:25:53,010 --> 00:25:59,390
Să ne uităm la ce se întâmplă dacă ar fi să încercăm și privi în sus valoarea de 10.

341
00:25:59,390 --> 00:26:02,970
Dacă ar fi să se uite în sus valoarea 10, vom începe de la rădăcină.

342
00:26:02,970 --> 00:26:07,070
Ne-ar vedea că 10 este mai mare decât 7, deci am muta la dreapta.

343
00:26:07,070 --> 00:26:13,640
Ne-ar ajunge la 9 și compara 9 la 10 și vedea că 9 este într-adevăr mai puțin de 10.

344
00:26:13,640 --> 00:26:16,210
Deci, din nou, ne-ar încerca să se mute în dreapta.

345
00:26:16,210 --> 00:26:20,350
Dar, în acest moment, am observat că suntem la un nod nul.

346
00:26:20,350 --> 00:26:23,080
Nu e nimic acolo. Nu e nimic în cazul în care ar trebui să fie 10.

347
00:26:23,080 --> 00:26:29,360
Acest lucru este în cazul în care ne putem raporta eșec - că nu există într-adevăr, nu 10 în copac.

348
00:26:29,360 --> 00:26:35,420
Și, în sfârșit, să mergem prin cazul în care noi încercăm să te uiți în sus 1 din copac.

349
00:26:35,420 --> 00:26:38,790
Acest lucru este similar cu ceea ce se întâmplă dacă ne uităm în sus 10, cu excepția în loc de a merge la dreapta,

350
00:26:38,790 --> 00:26:41,260
vom merge la stânga.

351
00:26:41,260 --> 00:26:46,170
Vom începe de la 7 și vezi că 1 este mai mic de 7, asa ca am muta la stânga.

352
00:26:46,170 --> 00:26:51,750
Noi ajungem la 3 și vezi că 1 este mai mic de 3, deci vom încerca din nou, pentru a vă deplasa spre stânga.

353
00:26:51,750 --> 00:26:59,080
În acest moment avem un nod nul, deci din nou, ne putem raporta eșec.

354
00:26:59,080 --> 00:27:10,260
>> Dacă vreți să aflați mai multe despre copaci binare,

355
00:27:10,260 --> 00:27:14,420
există o grămadă de probleme dragute pe care le puteți face cu ele.

356
00:27:14,420 --> 00:27:19,450
Eu sugerez practicarea desen din aceste diagrame unu-de-unu

357
00:27:19,450 --> 00:27:21,910
și în urma prin toate etapele diferite,

358
00:27:21,910 --> 00:27:25,060
deoarece acest lucru va veni în super-îndemână

359
00:27:25,060 --> 00:27:27,480
nu numai atunci când faci problema Huffman set de codificare

360
00:27:27,480 --> 00:27:29,390
dar, de asemenea, la cursuri viitoare -

361
00:27:29,390 --> 00:27:32,220
doar de învățare cum să atragă în aceste structuri de date și că, prin problemele

362
00:27:32,220 --> 00:27:38,000
cu pix și hârtie sau, în acest caz, iPad și stylus.

363
00:27:38,000 --> 00:27:41,000
>> În acest moment însă, vom trece la a face unele practici de codare

364
00:27:41,000 --> 00:27:44,870
și să se joace de fapt, cu aceste copaci binare și a vedea.

365
00:27:44,870 --> 00:27:52,150
Mă duc pentru a comuta înapoi peste la calculatorul meu.

366
00:27:52,150 --> 00:27:58,480
Pentru această parte a secțiunii, în loc de a folosi CS50 CS50 Run sau Spaces,

367
00:27:58,480 --> 00:28:01,500
Am de gând să folosească aparatul.

368
00:28:01,500 --> 00:28:04,950
>> În urma împreună cu caietul de sarcini set de probleme,

369
00:28:04,950 --> 00:28:07,740
Văd că eu ar trebui să deschidă aparatul,

370
00:28:07,740 --> 00:28:11,020
du-te la folderul My Dropbox, creați un folder denumit secțiunea 7,

371
00:28:11,020 --> 00:28:15,730
și de a crea apoi un fișier numit binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Aici vom merge. Am aparatul deja deschis.

373
00:28:22,050 --> 00:28:25,910
Mă duc trage un terminal.

374
00:28:25,910 --> 00:28:38,250
Am de gând să merg la folderul Dropbox, face un director numit section7,

375
00:28:38,250 --> 00:28:42,230
si vezi e complet goală.

376
00:28:42,230 --> 00:28:48,860
Acum am de gând să deschidă binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Bine. Aici vom merge - fișier gol.

378
00:28:51,750 --> 00:28:54,330
>> Să ne întoarcem la caietul de sarcini.

379
00:28:54,330 --> 00:28:59,850
Caietul de sarcini solicită să creați o definiție de tip nou

380
00:28:59,850 --> 00:29:03,080
pentru un nod arbore binar care conține valori int -

381
00:29:03,080 --> 00:29:07,110
la fel ca valorile pe care le-au atras în diagrame noastră înainte.

382
00:29:07,110 --> 00:29:11,740
Vom folosi această șabloane typedef pe care le-am făcut chiar aici

383
00:29:11,740 --> 00:29:14,420
că ar trebui să recunoască de la Set Problema 5 -

384
00:29:14,420 --> 00:29:19,190
dacă ai făcut-o modalitate de a cuceri tabel hash programului abecedar.

385
00:29:19,190 --> 00:29:22,540
Tu ar trebui să recunoască, de asemenea, că din punctul de săptămâna trecută

386
00:29:22,540 --> 00:29:23,890
în cazul în care am vorbit despre listele legate.

387
00:29:23,890 --> 00:29:27,870
Am luat acest typedef struct nod al unui,

388
00:29:27,870 --> 00:29:34,430
și ne-am dat acest nod struct acest nume de nod struct în prealabil

389
00:29:34,430 --> 00:29:39,350
astfel încât să putem referi apoi la ea, deoarece vom dori să aibă indicii struct nod

390
00:29:39,350 --> 00:29:45,740
ca parte dintr-o structura noastră, dar ne-am încercuit atunci acest lucru -

391
00:29:45,740 --> 00:29:47,700
sau, mai degrabă, această închise - într-un typedef

392
00:29:47,700 --> 00:29:54,600
astfel încât, mai târziu, în cod, ne putem referi la acest struct ca doar un nod in loc de un nod struct.

393
00:29:54,600 --> 00:30:03,120
>> Acest lucru va fi foarte similar cu definiția lista individual-linked, care am văzut săptămâna trecută.

394
00:30:03,120 --> 00:30:20,070
Pentru a face acest lucru, hai să începem prin a scrie în șabloane.

395
00:30:20,070 --> 00:30:23,840
Știm că trebuie să avem o valoare întreagă,

396
00:30:23,840 --> 00:30:32,170
asa ca vom pune in valoare int, și apoi în loc de a avea doar un pointer la elementul următor -

397
00:30:32,170 --> 00:30:33,970
așa cum am făcut cu individual legate de preturi -

398
00:30:33,970 --> 00:30:38,110
vom avea pointeri stânga și dreapta copil.

399
00:30:38,110 --> 00:30:42,880
Asta e destul de simplu prea - struct nod * copilul din stânga;

400
00:30:42,880 --> 00:30:51,190
și struct nod * copil dreapta;. Mișto.

401
00:30:51,190 --> 00:30:54,740
Care arata ca un început destul de bun.

402
00:30:54,740 --> 00:30:58,530
Să ne întoarcem la caietul de sarcini.

403
00:30:58,530 --> 00:31:05,030
>> Acum, avem nevoie de a declara o variabilă globală * nod pentru rădăcina unui copac.

404
00:31:05,030 --> 00:31:10,590
Vom face acest lucru la nivel mondial ca ne-am facut indicatorul prima în lista noastră de legat, de asemenea, la nivel mondial.

405
00:31:10,590 --> 00:31:12,690
Acest lucru a fost, astfel încât, în funcțiile pe care le scrie

406
00:31:12,690 --> 00:31:16,180
noi nu trebuie să țină de întâlnire în jurul valorii de această rădăcină -

407
00:31:16,180 --> 00:31:19,620
deși vom vedea că, dacă doresc să se scrie aceste funcții recursiv,

408
00:31:19,620 --> 00:31:22,830
ar fi mai bine să nu treci chiar în jurul valorii de ca un nivel global în primul rând

409
00:31:22,830 --> 00:31:28,090
și inițializa în schimb, la nivel local, în funcție de dvs. principal.

410
00:31:28,090 --> 00:31:31,960
Dar, vom face la nivel global pentru a începe.

411
00:31:31,960 --> 00:31:39,920
Din nou, vom da o pereche de spații, și am de gând să declare o rădăcină * nod.

412
00:31:39,920 --> 00:31:46,770
Doar pentru a vă asigura că nu-mi părăsi această neinitializata, am de gând să-l setați egale cu null.

413
00:31:46,770 --> 00:31:52,210
Acum, în funcția de principal - pe care o vom scrie foarte repede chiar aici -

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

415
00:32:00,450 --> 00:32:10,640
și am de gând să încep declarând matrice mea argv ca const doar pentru ca stiu

416
00:32:10,640 --> 00:32:14,550
că aceste argumente sunt argumente că, probabil, nu doriți să le modificați.

417
00:32:14,550 --> 00:32:18,390
Dacă vreau să-i modifice I ar trebui, probabil, face copii ale acestora.

418
00:32:18,390 --> 00:32:21,740
Veți vedea acest lucru un lot în cod.

419
00:32:21,740 --> 00:32:25,440
E bine oricum. E bine să-l lase ca - omite const, dacă doriți.

420
00:32:25,440 --> 00:32:28,630
Am pus-o în mod normal doar pentru ca m-am reamintesc

421
00:32:28,630 --> 00:32:33,650
 Probabil că eu nu vreau să modifice aceste argumente.

422
00:32:33,650 --> 00:32:39,240
>> Ca întotdeauna, am de gând să includă această return 0 linie la sfârșitul anului principal.

423
00:32:39,240 --> 00:32:45,730
Aici, voi inițializa nodul rădăcină meu.

424
00:32:45,730 --> 00:32:48,900
Așa cum stau lucrurile acum, am un pointer care este setat la nul,

425
00:32:48,900 --> 00:32:52,970
așa că e îndreptat de la nimic.

426
00:32:52,970 --> 00:32:57,480
În scopul de a porni efectiv construcția nodului,

427
00:32:57,480 --> 00:32:59,250
Prima dată am nevoie pentru a aloca memorie pentru ea.

428
00:32:59,250 --> 00:33:05,910
Am de gând să fac asta prin memorie pe heap folosind malloc.

429
00:33:05,910 --> 00:33:10,660
Am de gând să se stabilească rădăcină egală cu rezultatul malloc,

430
00:33:10,660 --> 00:33:19,550
și am de gând să utilizați operatorul sizeof pentru a calcula dimensiunea unui nod.

431
00:33:19,550 --> 00:33:24,990
Motivul pentru care am folosi sizeof nod, spre deosebire de, să zicem,

432
00:33:24,990 --> 00:33:37,020
a face ceva de genul asta - malloc (4 + 4 +4) sau malloc 12 -

433
00:33:37,020 --> 00:33:40,820
este pentru că vreau să fie codul meu cât mai compatibil.

434
00:33:40,820 --> 00:33:44,540
Vreau să fie în măsură să ia acest fișier C., Compilați-l pe aparat,

435
00:33:44,540 --> 00:33:48,820
și apoi compila-l pe pagina mea 64-biți Mac -

436
00:33:48,820 --> 00:33:52,040
sau pe o arhitectură complet diferită -

437
00:33:52,040 --> 00:33:54,640
și vreau toate astea pentru a lucra la fel.

438
00:33:54,640 --> 00:33:59,510
>> Dacă am face presupuneri cu privire la dimensiunea de variabile -

439
00:33:59,510 --> 00:34:02,070
dimensiunea unui int sau dimensiunea unui pointer -

440
00:34:02,070 --> 00:34:06,070
atunci am face, de asemenea, presupuneri cu privire la tipurile de arhitecturi

441
00:34:06,070 --> 00:34:10,440
pe care codul meu poate compila cu succes atunci când rulați.

442
00:34:10,440 --> 00:34:15,030
Utilizați întotdeauna sizeof, spre deosebire de însumarea manual câmpurile struct.

443
00:34:15,030 --> 00:34:20,500
Alt motiv este faptul că ar putea exista, de asemenea, faptul că padding compilatorul pune în struct.

444
00:34:20,500 --> 00:34:26,570
Chiar însumând doar câmpurile individuale nu este ceva ce vrei sa faci de obicei,

445
00:34:26,570 --> 00:34:30,340
astfel, ștergeți acea linie.

446
00:34:30,340 --> 00:34:33,090
Acum, pentru a inițializa cu adevărat acest nod rădăcină,

447
00:34:33,090 --> 00:34:36,489
Am de gând să aibă de a conecta valorile pentru fiecare dintre domeniile sale diferite.

448
00:34:36,489 --> 00:34:41,400
De exemplu, pentru valoarea știu că vreau să inițializa la 7,

449
00:34:41,400 --> 00:34:46,920
si de acum am de gând să setați copilul din stânga pentru a fi nul

450
00:34:46,920 --> 00:34:55,820
și copilul dreptul de a fi, de asemenea, nulă. Minunat!

451
00:34:55,820 --> 00:35:02,670
Am făcut ca o parte din spec..

452
00:35:02,670 --> 00:35:07,390
>> Caietul de sarcini jos la partea de jos a paginii 3-mi cere mai mult pentru a crea trei noduri -

453
00:35:07,390 --> 00:35:10,600
unul conținând 3, unul conținând 6, și unul cu 9 -

454
00:35:10,600 --> 00:35:14,210
și sârmă, apoi le așa că arată exact ca diagrama copacul nostru

455
00:35:14,210 --> 00:35:17,120
că am vorbit despre anterior.

456
00:35:17,120 --> 00:35:20,450
Să facem asta destul de repede aici.

457
00:35:20,450 --> 00:35:26,270
Veți vedea foarte repede că am de gând să înceapă să scrie o grămadă de cod duplicat.

458
00:35:26,270 --> 00:35:32,100
Am de gând să creeze un nod * și am de gând să-l sun trei.

459
00:35:32,100 --> 00:35:36,000
Am de gând să-l setați egale cu malloc (sizeof (nod)).

460
00:35:36,000 --> 00:35:41,070
Am de gând să se stabilească trei> valoare = 3.

461
00:35:41,070 --> 00:35:54,780
Trei -> left_child = NULL; trei -> dreapta = NULL _child; precum și.

462
00:35:54,780 --> 00:36:01,150
Care arată destul de similar cu initializarea rădăcină, și asta e exact ceea ce

463
00:36:01,150 --> 00:36:05,760
Am de gând să aibă de a face dacă am începe inițializarea 6 și 9, precum și.

464
00:36:05,760 --> 00:36:20,720
Voi face asta foarte repede aici - de fapt, am de gând să fac o copie puțin și pastă,

465
00:36:20,720 --> 00:36:46,140
și asigurați-vă că eu - bine.

466
00:36:46,470 --> 00:37:09,900
 Acum, eu am copiat-o si eu pot merge mai departe și a stabilit acest egală cu 6.

467
00:37:09,900 --> 00:37:14,670
Puteți vedea că aceasta are un timp și nu este super-eficiente.

468
00:37:14,670 --> 00:37:22,610
În doar un pic, vom scrie o functie care va face acest lucru pentru noi.

469
00:37:22,610 --> 00:37:32,890
Vreau să le înlocuiască cu un 9, să le înlocuiască cu un 6.

470
00:37:32,890 --> 00:37:37,360
>> Acum avem toate nodurile noastre, creat si initializat.

471
00:37:37,360 --> 00:37:41,200
Avem radacina noastra setat egal cu 7, sau care conțin valoarea 7,

472
00:37:41,200 --> 00:37:46,510
nostru nodul care conține 3, nodul noastră conține 6, și nodul noastră conține 9.

473
00:37:46,510 --> 00:37:50,390
În acest moment, tot ce trebuie să faceți este totul sârmă în sus.

474
00:37:50,390 --> 00:37:53,020
Motivul pentru care am initializat toate indicii la zero este doar ca să mă asigur că

475
00:37:53,020 --> 00:37:56,260
Eu nu am nici indicii neinițializate acolo din întâmplare.

476
00:37:56,260 --> 00:38:02,290
Și, de asemenea, deoarece, în acest moment, am doar pentru a conecta nodurile de fapt, reciproc -

477
00:38:02,290 --> 00:38:04,750
pentru cei care acestea sunt de fapt conectate la - Eu nu trebuie să treacă printr-și face

478
00:38:04,750 --> 00:38:08,240
sigur că toate sunt valori nule acolo, în locurile corespunzătoare.

479
00:38:08,240 --> 00:38:15,630
>> Începând de la rădăcină, știu că copilul root stânga este 3.

480
00:38:15,630 --> 00:38:21,250
Știu că copilul root dreapta este 9.

481
00:38:21,250 --> 00:38:24,880
După aceea, singurul copil de altă natură care le-am lăsat să vă faceți griji cu privire la

482
00:38:24,880 --> 00:38:39,080
este copilul dreapta 3, care este de 6.

483
00:38:39,080 --> 00:38:44,670
În acest moment, totul pare destul de bine.

484
00:38:44,670 --> 00:38:54,210
Vom șterge unele dintre aceste linii.

485
00:38:54,210 --> 00:38:59,540
Acum totul arata destul de bine.

486
00:38:59,540 --> 00:39:04,240
Să ne întoarcem la caietul de sarcini nostru și să vedem ce trebuie să facem următoarea.

487
00:39:04,240 --> 00:39:07,610
>> În acest moment, avem de a scrie o funcție numită "conține"

488
00:39:07,610 --> 00:39:14,150
cu un prototip de "conține bool (int valoare)".

489
00:39:14,150 --> 00:39:17,060
Și aceasta conține funcție este de gând să se întoarcă adevărat

490
00:39:17,060 --> 00:39:21,200
 dacă arborele indicat de variabila nostru rădăcină la nivel mondial

491
00:39:21,200 --> 00:39:26,950
 conține valoarea trecut în funcția și false în caz contrar.

492
00:39:26,950 --> 00:39:29,000
Să mergem mai departe și face asta.

493
00:39:29,000 --> 00:39:35,380
Acest lucru va fi exact ca de căutare pe care am făcut-o de mână, pe iPad doar un pic în urmă.

494
00:39:35,380 --> 00:39:40,130
Hai înapoi în mări un pic și derulați în sus.

495
00:39:40,130 --> 00:39:43,130
Vom pune această funcție chiar deasupra funcție nostru principal

496
00:39:43,130 --> 00:39:48,990
astfel încât să nu trebuie să facem nici un fel de prototipuri.

497
00:39:48,990 --> 00:39:55,960
Deci, bool conține (int valoare).

498
00:39:55,960 --> 00:40:00,330
Acolo mergem. E declarația noastră șabloane.

499
00:40:00,330 --> 00:40:02,900
Doar pentru a vă asigura că acest lucru se va compila,

500
00:40:02,900 --> 00:40:06,820
Am de gând să merg mai departe și doar egală cu return false.

501
00:40:06,820 --> 00:40:09,980
Chiar acum această funcție pur si simplu nu va face nimic și raporta întotdeauna că

502
00:40:09,980 --> 00:40:14,010
valoarea pe care o căutăm pentru că nu este în copac.

503
00:40:14,010 --> 00:40:16,280
>> În acest moment, este probabil o idee bună -

504
00:40:16,280 --> 00:40:19,600
de când am scris o grămadă de cod și nu am încercat chiar testând-o inca -

505
00:40:19,600 --> 00:40:22,590
pentru a vă asigura că totul compilează.

506
00:40:22,590 --> 00:40:27,460
Există o serie de lucruri pe care trebuie să le faceți pentru a vă asigura că acest lucru se va compila, de fapt.

507
00:40:27,460 --> 00:40:33,530
În primul rând, a se vedea dacă am fost folosind orice funcții în orice biblioteci pe care nu le-am încă incluse.

508
00:40:33,530 --> 00:40:37,940
Funcțiile le-am folosit până acum sunt malloc,

509
00:40:37,940 --> 00:40:43,310
și apoi am fost, de asemenea folosirea acestui tip - acest tip de non-standard numită "bool' -

510
00:40:43,310 --> 00:40:45,750
care este inclus în fișierul standard de antet bool.

511
00:40:45,750 --> 00:40:53,250
Noi cu siguranta doriți să includeți bool.h standard pentru tipul de bool,

512
00:40:53,250 --> 00:40:59,230
iar noi, de asemenea, să includă # lib.h standard pentru bibliotecile standard de

513
00:40:59,230 --> 00:41:03,530
care includ malloc, și liber, și toate astea.

514
00:41:03,530 --> 00:41:08,660
Deci, zoom out, vom să renunțe.

515
00:41:08,660 --> 00:41:14,190
Să încercăm și asigurați-vă că aceasta a făcut, de fapt compilare.

516
00:41:14,190 --> 00:41:18,150
Vedem că o face, așa că suntem pe drumul cel bun.

517
00:41:18,150 --> 00:41:22,990
>> Să deschidem din nou binary_tree.c.

518
00:41:22,990 --> 00:41:34,530
Se compilează. Să mergem în jos și asigurați-vă că introduceți unele apeluri la funcția noastră conține -

519
00:41:34,530 --> 00:41:40,130
doar pentru a vă asigura că asta e tot bine și bună.

520
00:41:40,130 --> 00:41:43,170
De exemplu, atunci când am făcut niște căutări în copacul nostru mai devreme,

521
00:41:43,170 --> 00:41:48,500
am încercat să caute cele 6 valori, 10, și 1, și am știut că era în 6 copac,

522
00:41:48,500 --> 00:41:52,220
10 nu a fost în copac, și 1 nu a fost în nici copac.

523
00:41:52,220 --> 00:41:57,230
Să folosească aceste apeluri prin sondaj, ca o modalitate de a da seama dacă este sau nu

524
00:41:57,230 --> 00:41:59,880
Funcția noastră conține este de lucru.

525
00:41:59,880 --> 00:42:05,210
În scopul de a face acest lucru, am de gând să utilizeze funcția printf,

526
00:42:05,210 --> 00:42:10,280
și am de gând să imprima rezultatul apelului de a conține.

527
00:42:10,280 --> 00:42:13,280
Am de gând să pună într-un șir "conține (% d) =, deoarece

528
00:42:13,280 --> 00:42:20,470
 vom conectați în valoarea pe care am de gând să caute,

529
00:42:20,470 --> 00:42:27,130
și =% s \ n ", și de a folosi că, în șir format noastră.

530
00:42:27,130 --> 00:42:30,720
Noi doar o să vezi - literalmente imprima pe ecran -

531
00:42:30,720 --> 00:42:32,060
ceea ce arata ca un apel de funcție.

532
00:42:32,060 --> 00:42:33,580
Acest lucru nu este de fapt apelul funcției.

533
00:42:33,580 --> 00:42:36,760
 Acesta este doar un șir conceput sa arate ca un apel de funcție.

534
00:42:36,760 --> 00:42:41,140
>> Acum, vom conectați în valorile.

535
00:42:41,140 --> 00:42:43,580
Vom încerca contine pe 6,

536
00:42:43,580 --> 00:42:48,340
si atunci ce vom face aici este faptul că utilizați operatorul ternar.

537
00:42:48,340 --> 00:42:56,340
Să vedem - conține 6 - deci, acum am cuprinse 6 și dacă conține 6 este adevărat,

538
00:42:56,340 --> 00:43:01,850
șir pe care am de gând să trimită la caracterul format% s

539
00:43:01,850 --> 00:43:04,850
va fi șirul de caractere "adevărată".

540
00:43:04,850 --> 00:43:07,690
Să defila peste un pic.

541
00:43:07,690 --> 00:43:16,210
În caz contrar, ne dorim pentru a trimite șirul de caractere "false" daca contine 6 întoarce false.

542
00:43:16,210 --> 00:43:19,730
Acest lucru este un pic nătărău aspect, dar m-am gândit eu s-ar putea la fel de bine ilustra

543
00:43:19,730 --> 00:43:23,780
ceea ce operatorul ternar arata ca, deoarece nu am văzut-o pentru o vreme.

544
00:43:23,780 --> 00:43:27,670
Acest lucru va fi un mod frumos, la îndemână pentru a afla dacă funcția noastră conține este de lucru.

545
00:43:27,670 --> 00:43:30,040
Mă duc pentru a defila înapoi peste la stânga,

546
00:43:30,040 --> 00:43:39,900
și am de gând să copiați și să inserați această linie de câteva ori.

547
00:43:39,900 --> 00:43:44,910
Mi-a schimbat unele dintre aceste valori în jurul valorii de,

548
00:43:44,910 --> 00:43:59,380
astfel încât aceasta va fi 1, iar acest lucru va fi 10.

549
00:43:59,380 --> 00:44:02,480
>> În acest moment avem un frumos funcție conține.

550
00:44:02,480 --> 00:44:06,080
Avem unele teste, și vom vedea dacă acest lucru toate lucrările.

551
00:44:06,080 --> 00:44:08,120
În acest moment am scris codul de ceva mai mult.

552
00:44:08,120 --> 00:44:13,160
E timpul să renunțe afară și asigurați-vă că totul încă compilează.

553
00:44:13,160 --> 00:44:20,360
Părăsiți afară, și acum hai să încercăm a face arbore binar din nou.

554
00:44:20,360 --> 00:44:22,260
Ei bine, se pare ca avem o eroare,

555
00:44:22,260 --> 00:44:26,930
Și avem această declarare în mod explicit funcția de bibliotecă printf.

556
00:44:26,930 --> 00:44:39,350
Se pare ca avem nevoie pentru a merge în și includ # standardio.h.

557
00:44:39,350 --> 00:44:45,350
Și cu asta, totul ar trebui să compileze. Suntem bine.

558
00:44:45,350 --> 00:44:50,420
Acum, haideți să încercați să rulați arbore binar și a vedea ce se întâmplă.

559
00:44:50,420 --> 00:44:53,520
Iată-ne, / binary_tree.,

560
00:44:53,520 --> 00:44:55,190
și vedem că, așa cum ne-am așteptat -

561
00:44:55,190 --> 00:44:56,910
pentru că nu ne-am pus în aplicare conține încă,

562
00:44:56,910 --> 00:44:59,800
sau, mai degrabă, tocmai am pus în schimbul fals -

563
00:44:59,800 --> 00:45:03,300
vom vedea că e doar revenind falsă pentru toate acestea,

564
00:45:03,300 --> 00:45:06,180
Deci, asta e tot de lucru pentru cea mai mare parte destul de bine.

565
00:45:06,180 --> 00:45:11,860
>> Să ne întoarcem și să pună în aplicare de fapt, conține în acest moment.

566
00:45:11,860 --> 00:45:17,490
Mă duc pentru a defila în jos, zoom in, și -

567
00:45:17,490 --> 00:45:22,330
Amintiți-vă, algoritmul pe care am folosit a fost că am început de la nodul rădăcină

568
00:45:22,330 --> 00:45:28,010
și apoi la fiecare nod pe care le întâlnim, să facem o comparație,

569
00:45:28,010 --> 00:45:32,380
și se bazează pe faptul că compararea ne muta, fie la stânga sau la copil copilul dreapta.

570
00:45:32,380 --> 00:45:39,670
Acest lucru se întâmplă pentru a arata foarte similar cu cod binar de căutare pe care am scris mai devreme în termen.

571
00:45:39,670 --> 00:45:47,810
Când ne-am începe, știm că vrem să stai la nodul curent

572
00:45:47,810 --> 00:45:54,050
că ne uităm la, și nodul curent va fi inițializat la nodul rădăcină.

573
00:45:54,050 --> 00:45:56,260
Și acum, vom continua prin copac,

574
00:45:56,260 --> 00:45:58,140
și amintiți-vă că starea noastră de oprire -

575
00:45:58,140 --> 00:46:01,870
 când am lucrat efectiv, prin exemplul de mână -

576
00:46:01,870 --> 00:46:03,960
a fost atunci când am întâlnit un nod nul,

577
00:46:03,960 --> 00:46:05,480
nu atunci când ne-am uitat la un copil nul,

578
00:46:05,480 --> 00:46:09,620
ci mai degrabă atunci când am de fapt, sa mutat într-un nod în arbore

579
00:46:09,620 --> 00:46:12,640
si a constatat ca suntem la un nod nul.

580
00:46:12,640 --> 00:46:20,720
Vom repeta pana cand actuală nu este egal cu zero.

581
00:46:20,720 --> 00:46:22,920
Și ce vom face?

582
00:46:22,920 --> 00:46:31,610
Vom testa dacă (actuală -> valoare == valoare),

583
00:46:31,610 --> 00:46:35,160
atunci știm că am găsit de fapt, nodul pe care-l căutăm.

584
00:46:35,160 --> 00:46:40,450
Deci, aici, ne putem întoarce adevărat.

585
00:46:40,450 --> 00:46:49,830
În caz contrar, vrem să vedem dacă este sau nu este o valoare mai mică decât valoarea.

586
00:46:49,830 --> 00:46:53,850
Dacă valoarea nodul curent este mai mică decât valoarea căutăm,

587
00:46:53,850 --> 00:46:57,280
vom trece la dreapta.

588
00:46:57,280 --> 00:47:10,600
Deci, actuală = actuală -> right_child, și în caz contrar, vom deplasa spre stânga.

589
00:47:10,600 --> 00:47:17,480
actuală actuală = -> left_child;. Destul de simplu.

590
00:47:17,480 --> 00:47:22,830
>> Tu, probabil, recunosc bucla care arată foarte similar cu acest lucru de la

591
00:47:22,830 --> 00:47:27,580
binar de căutare mai devreme în termen, cu excepția atunci avem de-a face cu mijlocul anului, mici, și de înaltă.

592
00:47:27,580 --> 00:47:30,000
Aici, trebuie doar să se uite la o valoare actuală,

593
00:47:30,000 --> 00:47:31,930
asa ca e frumos si simplu.

594
00:47:31,930 --> 00:47:34,960
Să asigurați-vă că acest cod este de lucru.

595
00:47:34,960 --> 00:47:42,780
În primul rând, asigurați-vă că compilează. Se pare ca o face.

596
00:47:42,780 --> 00:47:47,920
Să încercați să rulați-l.

597
00:47:47,920 --> 00:47:50,160
Și într-adevăr, acesta imprimă tot ceea ce ne-am asteptat.

598
00:47:50,160 --> 00:47:54,320
Se găsește 6 în copac, nu găsiți 10, pentru că 10 nu e în copac,

599
00:47:54,320 --> 00:47:57,740
și nu găsiți o, fie pentru că nu e un copac, de asemenea, în.

600
00:47:57,740 --> 00:48:01,420
Misto chestii.

601
00:48:01,420 --> 00:48:04,470
>> Bine. Să ne întoarcem la caietul de sarcini nostru si sa vedem ce urmează.

602
00:48:04,470 --> 00:48:07,990
Acum, ea vrea sa adauge unele noduri mai multe copacul nostru.

603
00:48:07,990 --> 00:48:11,690
Acesta dorește să adauge 5, 2, și 8, și asigurați-vă că ne conține cod

604
00:48:11,690 --> 00:48:13,570
încă mai funcționează cum era de asteptat.

605
00:48:13,570 --> 00:48:14,900
Să mergem să facem asta.

606
00:48:14,900 --> 00:48:19,430
În acest moment, mai degrabă decât a face acea copie enervant si paste din nou,

607
00:48:19,430 --> 00:48:23,770
să scrie o funcție pentru a crea de fapt un nod.

608
00:48:23,770 --> 00:48:27,740
Dacă vom defila în jos tot drumul spre principal, vom vedea că am făcut acest lucru

609
00:48:27,740 --> 00:48:31,210
Codul foarte asemănătoare de peste si peste din nou, de fiecare dată când vrem să creați un nod.

610
00:48:31,210 --> 00:48:39,540
>> Să scrie o functie care va construi de fapt, un nod pentru noi și îl returnează.

611
00:48:39,540 --> 00:48:41,960
Am de gând să-l sun build_node.

612
00:48:41,960 --> 00:48:45,130
Am de gând să construiască un nod cu o anumită valoare.

613
00:48:45,130 --> 00:48:51,040
Măriți aici.

614
00:48:51,040 --> 00:48:56,600
Primul lucru pe care am de gând să faceți este să creați de fapt spațiu pentru nodul pe heap.

615
00:48:56,600 --> 00:49:05,400
Deci, nod * n = malloc (sizeof (nod)); n -> valoare = valoare;

616
00:49:05,400 --> 00:49:14,960
si apoi aici, mă duc pentru a inițializa toate domeniile pentru a fi valori corespunzătoare.

617
00:49:14,960 --> 00:49:22,500
Și la sfârșitul foarte, ne vom întoarce nod nostru.

618
00:49:22,500 --> 00:49:28,690
Bine. Un lucru de remarcat este faptul că această funcție chiar aici

619
00:49:28,690 --> 00:49:34,320
este de gând să se întoarcă la un pointer de memorie care a fost heap-alocate.

620
00:49:34,320 --> 00:49:38,880
Ce e frumos despre acest lucru este faptul că acest nod acum -

621
00:49:38,880 --> 00:49:42,420
trebuie să-l declare pe heap, deoarece în cazul în care l-am declarat pe stivă

622
00:49:42,420 --> 00:49:45,050
nu am putea să-l facă în această funcție ca asta.

623
00:49:45,050 --> 00:49:47,690
Ca memoria ar merge afara domeniului de aplicare

624
00:49:47,690 --> 00:49:51,590
și ar fi nulă în cazul în care am încercat să-l accesați mai târziu.

625
00:49:51,590 --> 00:49:53,500
Din moment ce se declară heap-alocate de memorie,

626
00:49:53,500 --> 00:49:55,830
am de gând să trebuie să aibă grijă de a elibera mai târziu

627
00:49:55,830 --> 00:49:58,530
pentru programul nostru să nu se scurgă nici de memorie.

628
00:49:58,530 --> 00:50:01,270
Am fost punting pe care pentru orice altceva în codul

629
00:50:01,270 --> 00:50:02,880
doar de dragul simplitate, la timp,

630
00:50:02,880 --> 00:50:05,610
dar dacă vreodată a scrie o funcție care arata ca acest

631
00:50:05,610 --> 00:50:10,370
în cazul în care v-ați luat - unii o numesc malloc sau realloc interior -

632
00:50:10,370 --> 00:50:14,330
doriți să vă asigurați că ați pus un fel de comentariu aici care spune,

633
00:50:14,330 --> 00:50:29,970
hei, stii, returnează un nod de tip heap-alocat inițializat cu valoarea pass-in.

634
00:50:29,970 --> 00:50:33,600
Și apoi doriți să vă asigurați că ați pus într-un fel de act de faptul că spune

635
00:50:33,600 --> 00:50:41,720
apelantului trebuie să elibereze memoria întors.

636
00:50:41,720 --> 00:50:45,450
În acest fel, dacă cineva vreodată merge și utilizează această funcție,

637
00:50:45,450 --> 00:50:48,150
ei știu că tot ce primesc înapoi de la această funcție

638
00:50:48,150 --> 00:50:50,870
la un moment dat va trebui să fie eliberat.

639
00:50:50,870 --> 00:50:53,940
>> Presupunând că totul este bine și bună aici,

640
00:50:53,940 --> 00:51:02,300
putem merge în jos în codul nostru și să înlocuiască toate aceste linii chiar aici

641
00:51:02,300 --> 00:51:05,410
cu apeluri la funcția noastră nod build.

642
00:51:05,410 --> 00:51:08,170
Să facem asta foarte repede.

643
00:51:08,170 --> 00:51:15,840
Pe de o parte că nu vom să înlocuiască această parte este aici jos

644
00:51:15,840 --> 00:51:18,520
la partea de jos unde am sârmă de fapt, până la punctul de noduri reciproc,

645
00:51:18,520 --> 00:51:21,030
pentru că nu putem face în funcție nostru.

646
00:51:21,030 --> 00:51:37,400
Dar, hai sa facem root = build_node (7); nod * = build_node trei (3);

647
00:51:37,400 --> 00:51:47,980
nod * = build_node șase (6); nod * = build_node nouă (9);.

648
00:51:47,980 --> 00:51:52,590
Și acum, am vrut, de asemenea pentru a adăuga noduri pentru -

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

650
00:52:03,530 --> 00:52:09,760
și ceea ce a fost alt nod? Să vedem aici. Ne-am dorit pentru a adăuga, de asemenea, un 2 -

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

652
00:52:20,280 --> 00:52:26,850
Bine. În acest moment, știm că avem 7, 3, 9, și 6

653
00:52:26,850 --> 00:52:30,320
toate cablat în mod corespunzător, dar ceea ce despre 5, 8, si 2?

654
00:52:30,320 --> 00:52:33,550
Pentru a păstra totul în ordine corespunzătoare,

655
00:52:33,550 --> 00:52:39,230
știm că dreptul copilului cei trei este de 6.

656
00:52:39,230 --> 00:52:40,890
Deci, dacă am de gând să adăugați 5,

657
00:52:40,890 --> 00:52:46,670
5, de asemenea aparține în partea dreaptă a arborelui din care 3 este radacina,

658
00:52:46,670 --> 00:52:50,440
astfel 5 aparține ca copilul stânga 6.

659
00:52:50,440 --> 00:52:58,650
Putem face acest lucru prin a spune, de sase -> left_child = cinci;

660
00:52:58,650 --> 00:53:10,790
și apoi 8 aparține ca copilul stânga 9, astfel încât nouă -> left_child = opt;

661
00:53:10,790 --> 00:53:22,190
și apoi 2 este copilul stanga de 3, astfel încât să putem face asta aici - tine -> left_child = două;.

662
00:53:22,190 --> 00:53:27,730
Dacă nu ați urmat destul, împreună cu faptul că, îți sugerez să-l scoată singur.

663
00:53:27,730 --> 00:53:35,660
>> Bine. Să salvăm asta. Să mergem afară și asigurați-vă că compilează,

664
00:53:35,660 --> 00:53:40,760
și apoi putem adăuga în apelurile noastre conține.

665
00:53:40,760 --> 00:53:44,120
Se pare că totul încă compilează.

666
00:53:44,120 --> 00:53:51,790
Să mergem și să adăugați în unele conține apeluri.

667
00:53:51,790 --> 00:53:59,640
Din nou, am de gând să fac un pic de copy si paste.

668
00:53:59,640 --> 00:54:15,860
Acum, haideți să caute 5, 8, și 2. Bine.

669
00:54:15,860 --> 00:54:28,330
Să ne asigurăm că toate aceste încă arată bine. Minunat! Salvați și ieșiți.

670
00:54:28,330 --> 00:54:33,220
Acum, hai să facem, compila, și acum să ruleze.

671
00:54:33,220 --> 00:54:37,540
Din rezultatele, se pare ca totul este de lucru doar frumos și bine.

672
00:54:37,540 --> 00:54:41,780
Minunat! Deci, acum avem Contains noastre funcționa în scris.

673
00:54:41,780 --> 00:54:46,160
Să trecem mai departe și începe să lucreze cu privire la modul de a insera noduri în arbore

674
00:54:46,160 --> 00:54:50,000
deoarece, așa cum o facem acum, lucrurile nu sunt foarte drăguță.

675
00:54:50,000 --> 00:54:52,280
>> Dacă ne întoarcem la caietul de sarcini,

676
00:54:52,280 --> 00:55:00,540
ne cere să scrie o funcție numită insera - din nou, revenind o bool

677
00:55:00,540 --> 00:55:04,400
pentru a vedea dacă sunt sau nu am putea introduce, de fapt nod în arbore -

678
00:55:04,400 --> 00:55:07,710
și apoi pentru a introduce valoarea în copac este specificat ca

679
00:55:07,710 --> 00:55:11,060
singurul argument pentru funcția de inserare nostru.

680
00:55:11,060 --> 00:55:18,180
Vom reveni adevărat dacă am putea introduce într-adevăr, valoarea nodul care conține în copac,

681
00:55:18,180 --> 00:55:20,930
ceea ce înseamnă că noi, o, avea suficientă memorie,

682
00:55:20,930 --> 00:55:24,840
și apoi două, că nodul nu există deja în copac, deoarece -

683
00:55:24,840 --> 00:55:32,170
Amintiți-vă, nu vom avea valori duplicat în copac, doar pentru a face lucrurile simple.

684
00:55:32,170 --> 00:55:35,590
Bine. Înapoi la codul.

685
00:55:35,590 --> 00:55:44,240
Deschide-l. Mări într-un pic, apoi derulați în jos.

686
00:55:44,240 --> 00:55:47,220
Să punem funcția de inserare dreptul de deasupra conține.

687
00:55:47,220 --> 00:55:56,360
Din nou, aceasta va fi numit inserați bool (int valoare).

688
00:55:56,360 --> 00:56:01,840
Dă-i un pic mai mult spatiu, iar apoi, ca implicit,

689
00:56:01,840 --> 00:56:08,870
să pună în schimb fals, la sfârșitul foarte.

690
00:56:08,870 --> 00:56:22,620
Acum, in partea de jos, hai să mergem mai departe și în loc de a construi manual noduri

691
00:56:22,620 --> 00:56:27,900
în principal pe noi înșine și cablajul le până la punctul la altul ca și cum facem,

692
00:56:27,900 --> 00:56:30,600
ne vom baza pe funcția Inserare noastră de a face acest lucru.

693
00:56:30,600 --> 00:56:35,510
Nu ne vom baza pe funcția Inserare noastră de a construi de la zero tot arborele încă,

694
00:56:35,510 --> 00:56:39,970
ci mai degrabă vom scăpa de aceste linii - Vom comenta aceste linii -

695
00:56:39,970 --> 00:56:43,430
care construiesc cele 5 noduri, 8, și 2.

696
00:56:43,430 --> 00:56:55,740
Și în loc, vom insera apeluri la funcția de inserare nostru

697
00:56:55,740 --> 00:57:01,280
pentru a vă asigura că funcționează de fapt.

698
00:57:01,280 --> 00:57:05,840
Aici vom merge.

699
00:57:05,840 --> 00:57:09,300
>> Acum ne-am comentat aceste linii.

700
00:57:09,300 --> 00:57:13,700
Avem doar 7, 3, 9, și 6 în copacul nostru în acest moment.

701
00:57:13,700 --> 00:57:18,870
Pentru a vă asigura că acest lucru este tot de lucru,

702
00:57:18,870 --> 00:57:25,050
putem micșora, face copacul nostru binar,

703
00:57:25,050 --> 00:57:30,750
executați-l, și putem vedea că conține acum ne spune că suntem în totalitate dreptate -

704
00:57:30,750 --> 00:57:33,110
5, 8, și 2 nu mai sunt în copac.

705
00:57:33,110 --> 00:57:37,960
Du-te înapoi în cod,

706
00:57:37,960 --> 00:57:41,070
și cum vom insera?

707
00:57:41,070 --> 00:57:46,290
Amintiți-vă ce am făcut atunci când am fost de fapt introducerea 5, 8, și 2 anterior.

708
00:57:46,290 --> 00:57:50,100
Am jucat acest joc Plinko unde am pornit de la rădăcină,

709
00:57:50,100 --> 00:57:52,780
coborât un copac de unul câte unul

710
00:57:52,780 --> 00:57:54,980
până când am găsit decalajul corespunzător,

711
00:57:54,980 --> 00:57:57,570
și apoi am cablat în nodul de la fața locului corespunzătoare.

712
00:57:57,570 --> 00:57:59,480
Am de gând să faci același lucru.

713
00:57:59,480 --> 00:58:04,070
Aceasta este, practic la fel ca scrierea codul pe care am folosit în funcția conține

714
00:58:04,070 --> 00:58:05,910
pentru a găsi locul în care nodul ar trebui să fie,

715
00:58:05,910 --> 00:58:10,560
și apoi vom merge doar pentru a insera nodul acolo.

716
00:58:10,560 --> 00:58:17,000
Să începem face asta.

717
00:58:17,000 --> 00:58:24,200
>> Deci, avem un nod * actuală = radacina; suntem doar de gând să urmeze conține codul

718
00:58:24,200 --> 00:58:26,850
până când vom găsi că acesta nu funcționează destul pentru noi.

719
00:58:26,850 --> 00:58:32,390
Vom trece prin copac în timp ce elementul curent nu este nulă,

720
00:58:32,390 --> 00:58:45,280
și dacă vom descoperi că valoarea actuală este egală cu valoarea pe care noi încercăm să introduceți -

721
00:58:45,280 --> 00:58:49,600
Ei bine, aceasta este unul din cazurile în care nu am putut insera de fapt, nodul

722
00:58:49,600 --> 00:58:52,730
în copac, deoarece aceasta înseamnă că avem o valoare duplicat.

723
00:58:52,730 --> 00:58:59,010
Aici vom fapt de gând să se întoarcă fals.

724
00:58:59,010 --> 00:59:08,440
Acum altceva, în cazul în care valoarea actuală este mai mică decât valoarea,

725
00:59:08,440 --> 00:59:10,930
Acum știm că vom trece la dreapta

726
00:59:10,930 --> 00:59:17,190
 deoarece valoarea aparține în jumătatea dreaptă a arborelui actuală.

727
00:59:17,190 --> 00:59:30,110
În caz contrar, vom deplasa spre stânga.

728
00:59:30,110 --> 00:59:37,980
Asta e, practic Contains noastre funcționa chiar acolo.

729
00:59:37,980 --> 00:59:41,820
>> În acest moment, odată ce ne-am finalizat această buclă în timp ce,

730
00:59:41,820 --> 00:59:47,350
indicatorul nostru actuală va fi îndreptată la zero

731
00:59:47,350 --> 00:59:51,540
dacă funcția nu și-a revenit deja.

732
00:59:51,540 --> 00:59:58,710
Avem, prin urmare, actuală la fața locului în cazul în care dorim să inserați noul nod.

733
00:59:58,710 --> 01:00:05,210
Ceea ce rămâne de făcut este de a construi, de fapt nou nod,

734
01:00:05,210 --> 01:00:08,480
pe care le putem face destul de ușor.

735
01:00:08,480 --> 01:00:14,930
Putem folosi nostru de super-util funcția construi nod,

736
01:00:14,930 --> 01:00:17,210
și ceva ce nu am făcut mai devreme -

737
01:00:17,210 --> 01:00:21,400
am doar un fel de a pentru totdeauna, ci acum vom face doar să vă asigurați că -

738
01:00:21,400 --> 01:00:27,130
vom testa pentru a vă asigura că valoarea returnată de nod nou a fost de fapt

739
01:00:27,130 --> 01:00:33,410
Nu null, pentru că nu vrem să înceapă accesarea că memoria în cazul în care este nulă.

740
01:00:33,410 --> 01:00:39,910
Putem testa pentru a vă asigura că noul nod nu este egal cu zero.

741
01:00:39,910 --> 01:00:42,910
Sau schimb, putem vedea doar în cazul în care de fapt este nul,

742
01:00:42,910 --> 01:00:52,120
și în cazul în care este nulă, atunci ne putem întoarce pur și simplu falsă devreme.

743
01:00:52,120 --> 01:00:59,090
>> În acest moment, avem de a firului de nod nou în locul său corespunzător în copac.

744
01:00:59,090 --> 01:01:03,510
Dacă ne uităm înapoi la principal și în cazul în care am fost, de fapt de cabluri în valori înainte,

745
01:01:03,510 --> 01:01:08,470
vom vedea că modul în care ne-au l facem atunci când ne-am dorit să pună 3 în copac

746
01:01:08,470 --> 01:01:11,750
a fost accesat am copilul stânga rădăcină.

747
01:01:11,750 --> 01:01:14,920
Când ne-am pus 9 în copac, am avut pentru a accesa copilului dreptul de rădăcină.

748
01:01:14,920 --> 01:01:21,030
Am avut de a avea un pointer la mamă, în scopul de a pune o valoare nouă în copac.

749
01:01:21,030 --> 01:01:24,430
Derulând înapoi pentru a insera, că nu va merge destul de aici

750
01:01:24,430 --> 01:01:27,550
pentru că nu avem un pointer-mamă.

751
01:01:27,550 --> 01:01:31,650
Ceea ce vrem să fie capabil să facă este, în acest moment,

752
01:01:31,650 --> 01:01:37,080
verifica valoarea de mamă și de a se vedea - ei bine, Doamne,

753
01:01:37,080 --> 01:01:41,990
dacă valoarea mamă este mai mică decât valoarea curentă,

754
01:01:41,990 --> 01:01:54,440
atunci copilul mamă dreapta ar trebui să fie noul nod;

755
01:01:54,440 --> 01:02:07,280
în caz contrar, copilul mamă stânga ar trebui să fie noul nod.

756
01:02:07,280 --> 01:02:10,290
Dar, noi nu avem acest pointer-mamă destul de încă.

757
01:02:10,290 --> 01:02:15,010
>> În scopul de a-l, de fapt, ne va trebui să-l urmărească pe măsură ce trece prin copac

758
01:02:15,010 --> 01:02:18,440
și de a găsi locul adecvat în buclă nostru de mai sus.

759
01:02:18,440 --> 01:02:26,840
Putem face asta prin derularea înapoi până la partea de sus a funcției inserați noastre

760
01:02:26,840 --> 01:02:32,350
și urmărirea altă variabilă pointer numit mamă.

761
01:02:32,350 --> 01:02:39,340
Mergem să-l setați egale cu null inițial,

762
01:02:39,340 --> 01:02:43,640
și apoi de fiecare dată când trecem prin copac,

763
01:02:43,640 --> 01:02:51,540
vom seta indicatorul mamă pentru a se potrivi indicatorul curent.

764
01:02:51,540 --> 01:02:59,140
Setați părinte egal cu actuală.

765
01:02:59,140 --> 01:03:02,260
În acest fel, de fiecare dată când trecem prin,

766
01:03:02,260 --> 01:03:05,550
am de gând să se asigure că, indicatorul actual devine incrementează

767
01:03:05,550 --> 01:03:12,640
indicatorul mamă rezultă - doar cu un nivel mai ridicat decât indicatorul actual în copac.

768
01:03:12,640 --> 01:03:17,370
Ca toate arata destul de bine.

769
01:03:17,370 --> 01:03:22,380
>> Cred ca singurul lucru pe care vom dori să reglați este acest construi nulă nod revin.

770
01:03:22,380 --> 01:03:25,380
În scopul de a obține construi nod pentru a reveni cu succes de fapt, null,

771
01:03:25,380 --> 01:03:31,060
vom avea de a modifica acest cod,

772
01:03:31,060 --> 01:03:37,270
deoarece aici, nu am testat pentru a se asigura că malloc returnat un pointer valid.

773
01:03:37,270 --> 01:03:53,390
Deci, în cazul în care (n = NULL!), Apoi -

774
01:03:53,390 --> 01:03:55,250
dacă malloc returnat un pointer valid, apoi ne vom initializa;

775
01:03:55,250 --> 01:04:02,540
în caz contrar, vom returna doar și care se va încheia la returnarea nul pentru noi.

776
01:04:02,540 --> 01:04:13,050
Acum, toate arata destul de bine. Să ne asigurăm că acest fapt compilează.

777
01:04:13,050 --> 01:04:22,240
Asigurați-arbore binar, și oh, am luat niște lucruri se întâmplă aici.

778
01:04:22,240 --> 01:04:29,230
>> Avem o declarație implicită a funcției construi nod.

779
01:04:29,230 --> 01:04:31,950
Din nou, cu aceste compilatoare, vom incepe de la partea de sus.

780
01:04:31,950 --> 01:04:36,380
Ceea ce trebuie să spun este că am sunat înainte de a construi nod am de fapt declarate.

781
01:04:36,380 --> 01:04:37,730
Să ne întoarcem la codul foarte repede.

782
01:04:37,730 --> 01:04:43,510
Derulați în jos, și destul de sigur, funcția mea inserați este declarată

783
01:04:43,510 --> 01:04:47,400
de mai sus nodul funcția construi,

784
01:04:47,400 --> 01:04:50,070
dar am încercat să folosească construi nod în interiorul fragmentului.

785
01:04:50,070 --> 01:05:06,610
Am de gând să merg în copie și - apoi lipiți funcția de a construi calea nod aici la partea de sus.

786
01:05:06,610 --> 01:05:11,750
În acest fel, sperăm că va funcționa. Să-i dăm această alt du-te.

787
01:05:11,750 --> 01:05:18,920
Acum totul compilează. Totul este bine.

788
01:05:18,920 --> 01:05:21,640
>> Dar, în acest moment, nu ne-am chemat de fapt, funcția noastră de inserare.

789
01:05:21,640 --> 01:05:26,510
Știm doar că acesta compilează, așa că hai să mergem și să pună niște telefoane inch

790
01:05:26,510 --> 01:05:28,240
Să facem asta în funcție nostru principal.

791
01:05:28,240 --> 01:05:32,390
Aici, am comentat 5, 8, și 2,

792
01:05:32,390 --> 01:05:36,680
și apoi nu le-am sarme pana aici.

793
01:05:36,680 --> 01:05:41,640
Să facem niște telefoane pentru a insera,

794
01:05:41,640 --> 01:05:46,440
și să utilizeze, de asemenea, același tip de lucruri pe care am folosit

795
01:05:46,440 --> 01:05:52,810
atunci când am făcut aceste apeluri printf pentru a vă asigura că totul a se introduce în mod corespunzător.

796
01:05:52,810 --> 01:06:00,550
Am de gând să copiați și să lipiți,

797
01:06:00,550 --> 01:06:12,450
și în loc de contine vom face inserați.

798
01:06:12,450 --> 01:06:30,140
Și în loc de 6, 10, și 1, vom folosi 5, 8, și 2.

799
01:06:30,140 --> 01:06:37,320
Acest lucru ar trebui să introducă sperăm 5, 8, și 2 în copac.

800
01:06:37,320 --> 01:06:44,050
Compila. Totul este bine. Acum vom rula de fapt, programul nostru.

801
01:06:44,050 --> 01:06:47,330
>> Totul a revenit fals.

802
01:06:47,330 --> 01:06:53,830
Deci, 5, 8, și 2 nu merge, si se pare ca nu conține i-au găsit, fie.

803
01:06:53,830 --> 01:06:58,890
Ce se întâmplă? Să micșora.

804
01:06:58,890 --> 01:07:02,160
Prima problemă a fost că inserați părea să se întoarcă false,

805
01:07:02,160 --> 01:07:08,750
si se pare ca asta e pentru că am plecat în apel întoarcerea noastră falsă,

806
01:07:08,750 --> 01:07:14,590
și nu ne-am întors de fapt adevărat.

807
01:07:14,590 --> 01:07:17,880
Noi putem realiza acest lucru.

808
01:07:17,880 --> 01:07:25,290
A doua problemă este, acum, chiar dacă o facem - salva acest lucru, iesi acest lucru,

809
01:07:25,290 --> 01:07:34,530
rulați din nou face, l-au compila, apoi rulați-l -

810
01:07:34,530 --> 01:07:37,670
vom vedea că ceva sa întâmplat aici.

811
01:07:37,670 --> 01:07:42,980
5, 8, și 2 nu au fost niciodată încă găsite în copac.

812
01:07:42,980 --> 01:07:44,350
Deci, ce se întâmplă?

813
01:07:44,350 --> 01:07:45,700
>> Să aruncăm o privire la acest lucru în cod.

814
01:07:45,700 --> 01:07:49,790
Să vedem dacă ne putem da seama asta.

815
01:07:49,790 --> 01:07:57,940
Vom începe cu mamă nu este nul.

816
01:07:57,940 --> 01:07:59,510
Am stabilit indicatorul curent egal cu indicatorul rădăcină,

817
01:07:59,510 --> 01:08:04,280
și am de gând să lucreze drumul nostru în jos, prin copac.

818
01:08:04,280 --> 01:08:08,650
Dacă nodul curent nu este nul, atunci știm că ne putem muta în jos un pic.

819
01:08:08,650 --> 01:08:12,330
Ne-am stabilit indicatorul noastră mamă să fie egală cu indicatorul curent,

820
01:08:12,330 --> 01:08:15,420
verificat valoarea - în cazul în care valorile sunt aceleași ne-am întors fals.

821
01:08:15,420 --> 01:08:17,540
Dacă valorile sunt mai puțin ne-am mutat la dreapta;

822
01:08:17,540 --> 01:08:20,399
în caz contrar, ne-am mutat la stânga.

823
01:08:20,399 --> 01:08:24,220
Apoi, vom construi un nod. Voi mări un pic.

824
01:08:24,220 --> 01:08:31,410
Și aici, vom încerca să sarme pana valorile să fie la fel.

825
01:08:31,410 --> 01:08:37,250
Ce se întâmplă? Să vedem dacă, eventual, Valgrind ne poate da un indiciu.

826
01:08:37,250 --> 01:08:43,910
>> Imi place sa folosesc Valgrind Valgrind doar pentru că într-adevăr rapid rulează

827
01:08:43,910 --> 01:08:46,729
și vă spune dacă există erori de memorie.

828
01:08:46,729 --> 01:08:48,300
Când vom rula Valgrind pe cod,

829
01:08:48,300 --> 01:08:55,859
după cum puteți vedea hit here--Valgrind./binary_tree--and dreapta intra.

830
01:08:55,859 --> 01:09:03,640
Veți vedea că nu am avut nici o eroare de memorie, astfel încât se pare că totul e în regulă până acum.

831
01:09:03,640 --> 01:09:07,529
Avem niste scurgeri de memorie, pe care le cunosc, pentru că nu suntem

832
01:09:07,529 --> 01:09:08,910
se întâmplă pentru a elibera orice noduri noastre.

833
01:09:08,910 --> 01:09:13,050
Să încercați să rulați GDB pentru a vedea ce se întâmplă de fapt pe.

834
01:09:13,050 --> 01:09:20,010
Vom face gdb / binary_tree.. Acesta cizme sus chiar fin.

835
01:09:20,010 --> 01:09:23,670
Să stabilim un punct de întrerupere pe Inserare.

836
01:09:23,670 --> 01:09:28,600
Să fugi.

837
01:09:28,600 --> 01:09:31,200
Se pare ca n-am sunat, de fapt inserați.

838
01:09:31,200 --> 01:09:39,410
Se pare ca problema a fost doar că atunci când m-am schimbat aici în principal -

839
01:09:39,410 --> 01:09:44,279
toate aceste apeluri de la printf conține -

840
01:09:44,279 --> 01:09:56,430
N-am schimbat, de fapt acestea pentru a apela inserați.

841
01:09:56,430 --> 01:10:01,660
Acum, hai să încercăm. Să compilați.

842
01:10:01,660 --> 01:10:09,130
Toate arată bine acolo. Acum, haideți să încercați să rulați-l, vezi ce se întâmplă.

843
01:10:09,130 --> 01:10:13,320
Bine! Totul arata destul de bine acolo.

844
01:10:13,320 --> 01:10:18,130
>> Ultimul lucru care ne gândim este, sunt acolo orice cazuri de margine de la acest insert?

845
01:10:18,130 --> 01:10:23,170
Și se dovedește că, ei bine, un caz margine, care este întotdeauna interesant să ne gândim la

846
01:10:23,170 --> 01:10:26,250
este, ce se întâmplă dacă arborele este gol și te sun această funcție inserați?

847
01:10:26,250 --> 01:10:30,330
Va funcționa? Ei bine, hai să o încerc.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree C -.

849
01:10:32,110 --> 01:10:35,810
Modul în care ne vom testa acest lucru este, vom merge în jos la functia nostru principal,

850
01:10:35,810 --> 01:10:41,690
și, mai degrabă decât de cabluri aceste noduri până în acest fel,

851
01:10:41,690 --> 01:10:56,730
suntem doar de gând să comentați lucru întreg,

852
01:10:56,730 --> 01:11:02,620
și în loc de cablare pana noduri noi înșine,

853
01:11:02,620 --> 01:11:09,400
de fapt, putem merge doar înainte și ștergeți toate astea.

854
01:11:09,400 --> 01:11:17,560
Vom face tot ceea ce un apel pentru a insera.

855
01:11:17,560 --> 01:11:49,020
Deci, hai sa facem - în loc de 5, 8, și 2, vom introduce 7, 3 și 9.

856
01:11:49,020 --> 01:11:58,440
Și apoi vom dori, de asemenea, pentru a insera 6, precum și.

857
01:11:58,440 --> 01:12:05,190
Salvare. Quit. Asigurați-arbore binar.

858
01:12:05,190 --> 01:12:08,540
Totul compilează.

859
01:12:08,540 --> 01:12:10,320
Ne poate rula doar ca este si sa vedem ce se intampla,

860
01:12:10,320 --> 01:12:12,770
dar este, de asemenea, va fi foarte important să vă asigurați că

861
01:12:12,770 --> 01:12:14,740
nu avem erori de memorie,

862
01:12:14,740 --> 01:12:16,840
deoarece aceasta este una dintre cauzele de margine noastre pe care le știu despre.

863
01:12:16,840 --> 01:12:20,150
>> Să asigurați-vă că acesta funcționează bine sub Valgrind,

864
01:12:20,150 --> 01:12:28,310
pe care o vom face prin rularea doar Valgrind / binary_tree..

865
01:12:28,310 --> 01:12:31,110
Se pare că avem într-adevăr, o eroare de la un context -

866
01:12:31,110 --> 01:12:33,790
avem această eroare de segmentare.

867
01:12:33,790 --> 01:12:36,690
Ce sa întâmplat?

868
01:12:36,690 --> 01:12:41,650
Valgrind de fapt, ne spune unde este.

869
01:12:41,650 --> 01:12:43,050
Micșora un pic.

870
01:12:43,050 --> 01:12:46,040
Se pare că se întâmplă în funcția de inserare noastră,

871
01:12:46,040 --> 01:12:53,420
în cazul în care avem o citire invalid de marimea 4 la inserați, linia 60.

872
01:12:53,420 --> 01:13:03,590
Să ne întoarcem și să vedem ce se întâmplă pe aici.

873
01:13:03,590 --> 01:13:05,350
Micșora foarte repede.

874
01:13:05,350 --> 01:13:14,230
Vreau să vă asigurați că nu merge la marginea ecranului astfel încât să putem vedea totul.

875
01:13:14,230 --> 01:13:18,760
Trage că într-o pic. Bine.

876
01:13:18,760 --> 01:13:35,030
Derulați în jos, iar problema este chiar aici.

877
01:13:35,030 --> 01:13:40,120
Ce se întâmplă dacă am lua în jos și nodul nostru actual este deja nul,

878
01:13:40,120 --> 01:13:44,010
nod noastră mamă este nul, deci, dacă ne uităm în sus la foarte de sus, chiar aici -

879
01:13:44,010 --> 01:13:47,340
dacă nu această buclă în timp ce, de fapt execută

880
01:13:47,340 --> 01:13:52,330
pentru că valoarea noastră actuală este nul - radacina noastra este nulă atât de actuală este nulă -

881
01:13:52,330 --> 01:13:57,810
atunci nu se nostru părinte setat la actuală sau la o valoare validă,

882
01:13:57,810 --> 01:14:00,580
astfel, părinte va fi, de asemenea, nulă.

883
01:14:00,580 --> 01:14:03,700
Avem nevoie să ne amintim pentru a verifica faptul că

884
01:14:03,700 --> 01:14:08,750
de când am ajuns aici, și vom începe accesarea valoarea mamă.

885
01:14:08,750 --> 01:14:13,190
Deci, ce se întâmplă? Ei bine, în cazul în care părintele este nul -

886
01:14:13,190 --> 01:14:17,990
în cazul în care (mamă NULL ==) -, atunci știm că

887
01:14:17,990 --> 01:14:19,530
nu trebuie să existe nimic în copac.

888
01:14:19,530 --> 01:14:22,030
Trebuie să fi încercat să-l introduceți la rădăcină.

889
01:14:22,030 --> 01:14:32,570
Putem face asta doar prin stabilirea rădăcină egală cu nod nou.

890
01:14:32,570 --> 01:14:40,010
Apoi, la acest moment, nu vrem de fapt să treacă prin aceste alte lucruri.

891
01:14:40,010 --> 01:14:44,780
În schimb, chiar aici, putem face fie o altă-if-else,

892
01:14:44,780 --> 01:14:47,610
sau am putea combina totul aici, într-o altcineva,

893
01:14:47,610 --> 01:14:56,300
dar aici vom folosi doar altcineva și de a face în felul acesta.

894
01:14:56,300 --> 01:14:59,030
Acum, vom testa pentru a vă asigura că părintele nostru nu este nulă

895
01:14:59,030 --> 01:15:02,160
înainte de atunci, de fapt încearcă să acceseze domeniile sale.

896
01:15:02,160 --> 01:15:05,330
Acest lucru ne va ajuta să evite eroare de segmentare.

897
01:15:05,330 --> 01:15:14,740
Deci, am renuntat, zoom out, compila, fugi.

898
01:15:14,740 --> 01:15:18,130
>> Nu există erori, dar încă mai avem o grămadă de pierderi de memorie

899
01:15:18,130 --> 01:15:20,650
pentru ca nu am nici o elibera de noduri noastre.

900
01:15:20,650 --> 01:15:24,350
Dar, dacă mergem aici și ne uităm la imprimare noastră,

901
01:15:24,350 --> 01:15:30,880
vom vedea că, ei bine, se pare ca toate insertii noastre au fost returnarea adevărat, ceea ce e bine.

902
01:15:30,880 --> 01:15:33,050
Introduce toate sunt adevărate,

903
01:15:33,050 --> 01:15:36,670
și apoi apelurile corespunzătoare conține, de asemenea, sunt adevărate.

904
01:15:36,670 --> 01:15:41,510
>> Bună treabă! Se pare ca am scris cu succes inserați.

905
01:15:41,510 --> 01:15:47,430
Asta e tot ce avem pentru Caietul de sarcini din această săptămână set de probleme.

906
01:15:47,430 --> 01:15:51,720
O provocare distractiv să ne gândim este modul în care ar merge de fapt, în

907
01:15:51,720 --> 01:15:55,340
și gratuit toate nodurile din acest copac.

908
01:15:55,340 --> 01:15:58,830
Putem face acest lucru un număr de moduri diferite,

909
01:15:58,830 --> 01:16:01,930
dar voi lăsa că până la tine pentru a experimenta,

910
01:16:01,930 --> 01:16:06,080
și ca o provocare distracție, încercați și asigurați-vă că puteți să vă asigurați

911
01:16:06,080 --> 01:16:09,490
că acest raport Valgrind returnează nici o eroare si nici scurgeri.

912
01:16:09,490 --> 01:16:12,880
>> Mult noroc pe această săptămână Huffman problemă set de codare,

913
01:16:12,880 --> 01:16:14,380
și ne vedem săptămâna viitoare!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]