1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Sadaļa 7] [mazāk apmierināti]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Hārvarda]

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

4
00:00:07,000 --> 00:00:09,080
>> Laipni lūdzam likuma 7.

5
00:00:09,080 --> 00:00:11,330
Pateicoties viesuļvētru Sandy,

6
00:00:11,330 --> 00:00:13,440
vietā, normālas sadaļā šonedēļ,

7
00:00:13,440 --> 00:00:17,650
mēs darām šī arkveida, izmantojot sadaļā jautājumiem.

8
00:00:17,650 --> 00:00:22,830
Es esmu būs pēc kopā ar problēmu Set 6 specifikācijas,

9
00:00:22,830 --> 00:00:25,650
un iet cauri visiem minētajos jautājumos

10
00:00:25,650 --> 00:00:27,770
Nodaļa Jautājumi sadaļā.

11
00:00:27,770 --> 00:00:30,940
Ja ir kādi jautājumi,

12
00:00:30,940 --> 00:00:32,960
lūdzu, pēc tās uz CS50 apspriest.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Pieņemsim sāktu.

14
00:00:35,480 --> 00:00:40,780
Šobrīd es esmu meklē no problēmas Set specifikācijā 3 lpp.

15
00:00:40,780 --> 00:00:44,110
Mēs ejam, lai vispirms sākt runāt par bināro koku

16
00:00:44,110 --> 00:00:47,850
jo tiem ir daudz svarīgas šīs nedēļas problēmu kopumu -

17
00:00:47,850 --> 00:00:49,950
Huffman Tree kodējumu.

18
00:00:49,950 --> 00:00:55,000
Viens no pašiem pirmajiem datu struktūrām, mēs runājām arī par CS50 bija masīvs.

19
00:00:55,000 --> 00:01:00,170
Atcerieties, ka masīvs ir secība elementi -

20
00:01:00,170 --> 00:01:04,019
visi tā paša tipa - uzglabā blakus viens otram atmiņā.

21
00:01:04,019 --> 00:01:14,420
Ja man ir veselu virkni, ka es varu izdarīt, izmantojot šo kastes numuriem-integers stilā -

22
00:01:14,420 --> 00:01:20,290
Pieņemsim, ka man ir 5 pirmajā ailē, man ir 7 otrajā,

23
00:01:20,290 --> 00:01:27,760
tad man ir 8, 10, 20 un galīgajā lodziņā.

24
00:01:27,760 --> 00:01:33,000
Atcerieties, ka divi patiešām labas lietas par šo masīva

25
00:01:33,000 --> 00:01:38,800
ir, ka mums ir šī konstante laika piekļuvi kādu konkrētu elementu

26
00:01:38,800 --> 00:01:40,500
 masīvā, ja mēs zinām savu indeksu.

27
00:01:40,500 --> 00:01:44,670
Piemēram, ja es vēlos, lai greifers trešo elementu masīvs -

28
00:01:44,670 --> 00:01:47,870
pie indeksu 2, izmantojot mūsu nulles balstītu indeksēšanas sistēma -

29
00:01:47,870 --> 00:01:52,220
Es burtiski vienkārši ir darīt vienkāršu matemātisku aprēķinu,

30
00:01:52,220 --> 00:01:56,170
hop uz šo pozīciju masīvā,

31
00:01:56,170 --> 00:01:57,840
izvelciet 8, ka tur glabājas,

32
00:01:57,840 --> 00:01:59,260
un es esmu labi iet.

33
00:01:59,260 --> 00:02:03,350
>> Viens no sliktas lietas par šo masīva - ka mēs runājām

34
00:02:03,350 --> 00:02:05,010
kad mēs apspriedām saistīti saraksti -

35
00:02:05,010 --> 00:02:09,120
ir tas, ka, ja es gribu, lai ievietotu elementu šajā masīvs,

36
00:02:09,120 --> 00:02:11,090
Es esmu nāksies darīt kādu novirzot apkārt.

37
00:02:11,090 --> 00:02:12,940
Piemēram, šis masīvs tieši šeit

38
00:02:12,940 --> 00:02:16,850
ir sakārtoti secībā - sakārtoti augošā secībā -

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

40
00:02:19,440 --> 00:02:23,100
bet, ja es gribu ievietot numuru 9 šajā masīvs,

41
00:02:23,100 --> 00:02:27,460
Es esmu nāksies novirzīt dažus elementus, lai padarītu telpu.

42
00:02:27,460 --> 00:02:30,440
Mēs varam izdarīt šo šeit.

43
00:02:30,440 --> 00:02:35,650
Es esmu nāksies pārvietoties 5, 7, un tad 8;

44
00:02:35,650 --> 00:02:38,720
izveidot trūkumu, ja es varētu likt 9,

45
00:02:38,720 --> 00:02:45,910
un tad 10 un 20 var iet pa labi no 9 mēnešu.

46
00:02:45,910 --> 00:02:49,450
Tas ir sava veida sāpes, jo sliktākajā scenārijā -

47
00:02:49,450 --> 00:02:54,350
kad mēs esam ņemot ievietot vai nu sākumā vai beigās

48
00:02:54,350 --> 00:02:56,040
masīva, atkarībā no tā, kā mēs esam novirzot -

49
00:02:56,040 --> 00:02:58,850
mēs varētu galu galā, kam novirzīt visus elementus

50
00:02:58,850 --> 00:03:00,750
ka mēs pašlaik uzglabājot masīvā.

51
00:03:00,750 --> 00:03:03,810
>> Tātad, kāda bija ap šādā veidā?

52
00:03:03,810 --> 00:03:09,260
Ap šādā veidā bija doties uz mūsu Linked-saraksts metode kur -

53
00:03:09,260 --> 00:03:19,820
vietā, lai uzglabātu elementus 5, 7, 8, 10 un 20 visi blakus viens otram atmiņā -

54
00:03:19,820 --> 00:03:25,630
ko mēs tā vietā bija tika glabāt tos veida, kur mēs vēlējāmies, lai saglabātu tos

55
00:03:25,630 --> 00:03:32,470
Šajās Linked-sarakstā mezglu, ko es esmu zīmēšanas šeit, veida ad hoc.

56
00:03:32,470 --> 00:03:42,060
Un tad mēs savienotas kopā, izmantojot šīs nākamajai norādes.

57
00:03:42,060 --> 00:03:44,370
Es varu būt rādītāju 5-7 The,

58
00:03:44,370 --> 00:03:46,420
rādītājs no 7 līdz 8,

59
00:03:46,420 --> 00:03:47,770
rādītājs no 8 līdz 10 jaunajām dalībvalstīm,

60
00:03:47,770 --> 00:03:51,220
un visbeidzot, rādītājs no 10 jaunajām dalībvalstīm līdz 20 vienībām,

61
00:03:51,220 --> 00:03:54,880
un tad null rādītājs pie 20 vienībām, norādot, ka tur nekas pa kreisi.

62
00:03:54,880 --> 00:03:59,690
Kompromiss, kas mums šeit ir

63
00:03:59,690 --> 00:04:05,360
ir tas, ka tagad, ja mēs vēlamies ievietot numuru 9 mūsu sakārtoti sarakstā,

64
00:04:05,360 --> 00:04:08,270
viss, kas mums ir jādara, ir izveidot jaunu mezglu ar 9,

65
00:04:08,270 --> 00:04:12,290
vadu to līdz norādīt uz atbilstošu vietu,

66
00:04:12,290 --> 00:04:20,630
un pēc tam atkārtoti vadu 8 norādīt līdz 9 mēnešu.

67
00:04:20,630 --> 00:04:25,660
Tas ir diezgan ātri, pieņemot mēs zinām, kur tieši mēs vēlamies ievietot 9.

68
00:04:25,660 --> 00:04:32,610
Bet kompromiss apmaiņā tas, ka mēs esam tagad zaudējuši pastāvīga laika piekļuvi

69
00:04:32,610 --> 00:04:36,230
uz kādu konkrētu elementu mūsu datu struktūru.

70
00:04:36,230 --> 00:04:40,950
Piemēram, ja es vēlos, lai atrastu ceturto elements šajā saistītajā sarakstā,

71
00:04:40,950 --> 00:04:43,510
Es esmu nāksies sākt jau pašā sākumā saraksta

72
00:04:43,510 --> 00:04:48,930
un strādāt manu ceļu cauri skaitīšanas mezglā-by-mezglā līdz es atrast ceturtais.

73
00:04:48,930 --> 00:04:55,870
>> Lai iegūtu labāku piekļuvi sniegumu nekā saistīts saraksts -

74
00:04:55,870 --> 00:04:59,360
bet arī saglabāt dažas no priekšrocībām, kas mums bija

75
00:04:59,360 --> 00:05:01,800
izteiksmē ievietošanas laika no saistītajā sarakstā -

76
00:05:01,800 --> 00:05:05,750
binārs koks gatavojas nepieciešams izmantot mazliet vairāk atmiņas.

77
00:05:05,750 --> 00:05:11,460
Jo īpaši, nevis tikai ar vienu rādītāju bināru koku mezglu -

78
00:05:11,460 --> 00:05:13,350
piemēram Linked-sarakstā mezglu dara -

79
00:05:13,350 --> 00:05:16,950
mēs esam gatavojas pievienot otru rādītāju uz bināro koku mezglā.

80
00:05:16,950 --> 00:05:19,950
Nevis tikai ar vienu rādītāju uz nākamo elementu,

81
00:05:19,950 --> 00:05:24,420
mēs esam nāksies rādītāju uz kreiso bērnu un pareizā bērnu.

82
00:05:24,420 --> 00:05:26,560
>> Pieņemsim uzzīmēt, lai redzētu, kas patiesībā izskatās.

83
00:05:26,560 --> 00:05:31,350
Atkal, es esmu gatavojas izmantot šīs kastes un bultas.

84
00:05:31,350 --> 00:05:37,150
Binārs koks mezgls sākt ar pavisam vienkāršu kastē.

85
00:05:37,150 --> 00:05:40,940
Tas notiek, lai būtu telpu vērtību,

86
00:05:40,940 --> 00:05:47,280
un tad tas ir arī nāksies telpu kreisajā bērnu un labo bērnu.

87
00:05:47,280 --> 00:05:49,280
Es esmu gatavojas marķēt tos šeit.

88
00:05:49,280 --> 00:05:57,560
Mēs ejam, lai būtu kreiso bērnu, un tad mēs ejam, lai ir tiesības bērnu.

89
00:05:57,560 --> 00:05:59,920
Ir daudz dažādi veidi, kā to izdarīt.

90
00:05:59,920 --> 00:06:02,050
Dažreiz telpu un ērtības,

91
00:06:02,050 --> 00:06:06,460
Es tiešām izdarīt to kā es esmu dara šeit apakšā

92
00:06:06,460 --> 00:06:10,910
kur es esmu nāksies vērtību augšā,

93
00:06:10,910 --> 00:06:14,060
un tad tiesības bērns uz grunts labi,

94
00:06:14,060 --> 00:06:16,060
un kreiso bērns uz apakšējā kreisajā.

95
00:06:16,060 --> 00:06:20,250
Dodas atpakaļ uz šo top diagrammu,

96
00:06:20,250 --> 00:06:22,560
Mums ir vērtība pašā augšā,

97
00:06:22,560 --> 00:06:25,560
tad mums ir kreisās bērnu rādītāju, un tad mums ir tiesības un bērnu rādītāju.

98
00:06:25,560 --> 00:06:30,110
>> Jo problēma Set specifikāciju,

99
00:06:30,110 --> 00:06:33,110
mēs runājam par zīmēšanas mezglu, kas ir vērtība 7,

100
00:06:33,110 --> 00:06:39,750
un tad kreisās bērns rādītājs, kas ir spēkā, un labo bērns rādītājs, kas ir nulle.

101
00:06:39,750 --> 00:06:46,040
Mēs varam vai nu rakstīt kapitāla NULL telpā uz

102
00:06:46,040 --> 00:06:51,610
gan kreisajā bērns un labi bērnam, vai arī mēs varam izdarīt šo slīpsvītra

103
00:06:51,610 --> 00:06:53,750
caur katru no kastes, lai norādītu, ka tā ir null.

104
00:06:53,750 --> 00:06:57,560
Es esmu gatavojas darīt, ka tikai tāpēc, ka ir vienkāršāk.

105
00:06:57,560 --> 00:07:03,700
Ko jūs redzat šeit ir divi veidi, kā diagrammu ļoti vienkāršu bināru koku mezglu

106
00:07:03,700 --> 00:07:07,960
kur mums ir vērtība 7 un Null bērnu norādes.

107
00:07:07,960 --> 00:07:15,220
>> Otrā daļa no mūsu parametri runā par to, kā ar saistītas sarakstiem -

108
00:07:15,220 --> 00:07:18,270
Atcerieties, mums bija tikai turēt uz pašu pirmo elementu sarakstā

109
00:07:18,270 --> 00:07:20,270
atcerēties visu sarakstu -

110
00:07:20,270 --> 00:07:26,140
un tāpat, ar bināru koku, mums ir tikai turēt uz vienu rādītāju uz koku

111
00:07:26,140 --> 00:07:31,120
lai saglabātu kontroli pār visu datu struktūru.

112
00:07:31,120 --> 00:07:36,150
Šis īpašais elements koka sauc sakne mezgla koka.

113
00:07:36,150 --> 00:07:43,360
Piemēram, ja tas viens mezgls - tas mezgls satur vērtību 7

114
00:07:43,360 --> 00:07:45,500
ar Null kreisās un labās bērnu šautru -

115
00:07:45,500 --> 00:07:47,360
bija vienīgais vērtību mūsu koku,

116
00:07:47,360 --> 00:07:50,390
tad tas būtu mūsu saknes mezgla.

117
00:07:50,390 --> 00:07:52,240
Tas ir pats sākums mūsu koku.

118
00:07:52,240 --> 00:07:58,530
Mēs varam redzēt šo mazliet precīzāk, tiklīdz mēs sākt pievienot vairāk mezglu mūsu koku.

119
00:07:58,530 --> 00:08:01,510
Ļaujiet man uzvilkt jaunu lapu.

120
00:08:01,510 --> 00:08:05,000
>> Tagad mēs esam gatavojas izdarīt koks, kas ir 7 saknē,

121
00:08:05,000 --> 00:08:10,920
un 3 iekšpusē kreisajā bērnu, un 9 iekšpusē labajā bērnu.

122
00:08:10,920 --> 00:08:13,500
Atkal, tas ir diezgan vienkārši.

123
00:08:13,500 --> 00:08:26,510
Mēs esam ieguvuši 7, izdarīt mezglu 3, mezglā 9,

124
00:08:26,510 --> 00:08:32,150
un es esmu gatavojas noteikt kreiso bērnu rādītāju no 7, lai norādītu uz mezglā ir 3,

125
00:08:32,150 --> 00:08:37,850
un tiesības bērna rādītājs no mezgla ar 7 uz mezglu, kas satur 9.

126
00:08:37,850 --> 00:08:42,419
Tagad, jo 3 un 9 nav nekādas bērnus,

127
00:08:42,419 --> 00:08:48,500
mēs esam gatavojas noteikt visas savas bērnu norādes būt nulle.

128
00:08:48,500 --> 00:08:56,060
Lūk, mūsu koka sakne atbilst mezglu satur numuru 7.

129
00:08:56,060 --> 00:09:02,440
Jūs varat redzēt, ka, ja viss, kas mums ir, ir rādītājs uz šo saknes mezgla,

130
00:09:02,440 --> 00:09:07,330
tad mēs varam staigāt pa mūsu koku un piekļūt gan bērnu mezgliem -

131
00:09:07,330 --> 00:09:10,630
gan 3 un 9.

132
00:09:10,630 --> 00:09:14,820
Nav nepieciešams, lai uzturētu norādes uz katru mezglu uz koku.

133
00:09:14,820 --> 00:09:22,080
Alright. Tagad mēs esam gatavojas pievienot citu mezglu, lai šīs shēmas.

134
00:09:22,080 --> 00:09:25,370
Mēs ejam, lai pievienotu mezglu satur 6,

135
00:09:25,370 --> 00:09:34,140
un mēs esam gatavojas pievienot to kā labo bērns mezglā satur 3.

136
00:09:34,140 --> 00:09:41,850
Lai to izdarītu, es esmu gatavojas dzēst šo null rādītāju 3-mezglu

137
00:09:41,850 --> 00:09:47,750
un vadu to līdz norādīt uz mezglu, kas satur 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Šajā brīdī, iesim pa mazliet terminoloģiju.

139
00:09:53,800 --> 00:09:58,230
Lai sāktu, tāpēc, ka tas ir sauc bināro koku jo īpaši

140
00:09:58,230 --> 00:10:00,460
ir tas, ka ir divas bērnu norādes.

141
00:10:00,460 --> 00:10:06,020
Ir arī citi veidi, koku, kas ir vairāk bērnu norādes.

142
00:10:06,020 --> 00:10:10,930
Jo īpaši, jūs "izmēģināt", kas Problem Set 5.

143
00:10:10,930 --> 00:10:19,310
Jūs pamanīsiet, ka šajā izmēģināt, jums bija 27 dažādas norādes uz dažādiem bērniem -

144
00:10:19,310 --> 00:10:22,410
viens katrai no 26 burtiem angļu alfabētā,

145
00:10:22,410 --> 00:10:25,410
un tad 27. par apostrofam -

146
00:10:25,410 --> 00:10:28,900
tā, ka ir līdzīga tipa koka.

147
00:10:28,900 --> 00:10:34,070
Bet šeit, jo tas ir bināro, mums ir tikai divas bērnu norādes.

148
00:10:34,070 --> 00:10:37,880
>> Papildus šim saknes mezgla ka mēs runājām par,

149
00:10:37,880 --> 00:10:41,470
mēs esam arī throwing ap šī termina "bērns".

150
00:10:41,470 --> 00:10:44,470
Ko tas nozīmē viens mezgls būtu bērns citu mezglu?

151
00:10:44,470 --> 00:10:54,060
Tas burtiski nozīmē, ka bērns mezgls ir bērns citu mezglu

152
00:10:54,060 --> 00:10:58,760
ja cits mezgls ir viens no tās bērnu norādes, kas, lai norādītu uz šo mezglu.

153
00:10:58,760 --> 00:11:01,230
Lai to īstenotu vēl konkrēti,

154
00:11:01,230 --> 00:11:11,170
ja 3 norādīja uz viena no bērnu norādes 7, tad 3 ir bērns gada 7.

155
00:11:11,170 --> 00:11:14,510
Ja mēs izdomāt ko gada 7 bērni -

156
00:11:14,510 --> 00:11:18,510
labi, mēs redzam, ka 7 ir rādītāju uz 3 un rādītāju uz 9,

157
00:11:18,510 --> 00:11:22,190
tik 9 un 3 ir bērni 7.

158
00:11:22,190 --> 00:11:26,650
Deviņi nav bērni, jo tās bērnam norādes ir Null,

159
00:11:26,650 --> 00:11:30,940
un 3 ir tikai viens bērns, 6.

160
00:11:30,940 --> 00:11:37,430
Seši nav arī bērni, jo gan tās norādes ir nulle, ko mēs izdarīt jau tagad.

161
00:11:37,430 --> 00:11:45,010
>> Bez tam, mēs arī runājam par konkrētu mezglu vecākiem,

162
00:11:45,010 --> 00:11:51,100
un tas ir, kā jūs gaidījāt, reversā šī bērna aprakstu.

163
00:11:51,100 --> 00:11:58,620
Katrs mezgls ir tikai viens no vecākiem - nevis divi, kā jūs varētu gaidīt ar cilvēkiem.

164
00:11:58,620 --> 00:12:03,390
Piemēram, no 3 mātes ir 7.

165
00:12:03,390 --> 00:12:10,800
Gada 9 vecākiem ir arī 7 un 6 vecākiem ir 3. Nav daudz uz to.

166
00:12:10,800 --> 00:12:15,720
Mums ir arī terminus, lai runātu par vecvecākiem un mazbērniem,

167
00:12:15,720 --> 00:12:18,210
un vispār mēs runājam par senčiem

168
00:12:18,210 --> 00:12:20,960
un pēcnācēji konkrētā mezglā.

169
00:12:20,960 --> 00:12:25,710
Sencis mezglu - vai senči, drīzāk, no mezgla -

170
00:12:25,710 --> 00:12:32,730
ir visi mezglu, kas atrodas uz ceļa no saknes uz šo mezglu.

171
00:12:32,730 --> 00:12:36,640
Piemēram, ja es esmu meklē mezglu 6,

172
00:12:36,640 --> 00:12:46,430
tad senči ir būs gan 3 līdz 7.

173
00:12:46,430 --> 00:12:55,310
No 9 senči, piemēram, ir - ja es esmu meklē mezglu 9 -

174
00:12:55,310 --> 00:12:59,990
tad gada 9 sencis ir tikai 7.

175
00:12:59,990 --> 00:13:01,940
Un pēcnācēji ir tieši otrādi.

176
00:13:01,940 --> 00:13:05,430
Ja es gribu, lai apskatīt visu par 7 pēcnācējiem,

177
00:13:05,430 --> 00:13:11,020
tad man ir jāskatās uz visu zem tā mezgliem.

178
00:13:11,020 --> 00:13:16,950
Tātad, man ir 3, 9, 6 un visi kā pēcteči 7.

179
00:13:16,950 --> 00:13:24,170
>> Galīgā termiņa, ka mēs runājam par to ir šis jēdziens ir brālis.

180
00:13:24,170 --> 00:13:27,980
Vecvecākus - veida seko līdzi šiem ģimenes nosacījumiem -

181
00:13:27,980 --> 00:13:33,150
ir mezgli, kas ir tajā pašā līmenī koku.

182
00:13:33,150 --> 00:13:42,230
Tātad, 3 un 9 ir brāļi un māsas, jo tie ir tajā pašā līmenī koku.

183
00:13:42,230 --> 00:13:46,190
Viņiem abiem ir tādas pašas mātes, 7.

184
00:13:46,190 --> 00:13:51,400
6 nav brāļi un māsas, jo 9 Vai nav bērnu.

185
00:13:51,400 --> 00:13:55,540
Un 7 nav nekādas vecvecākus, jo tas ir galvenais mūsu koku,

186
00:13:55,540 --> 00:13:59,010
un tur ir tikai kādreiz 1 sakne.

187
00:13:59,010 --> 00:14:02,260
7 līdz būt vecvecākus tur būtu jābūt mezglā virs 7.

188
00:14:02,260 --> 00:14:07,480
Tur būtu jābūt vecākiem par 7, jo tādā gadījumā 7 vairs nebūs sakne no koka.

189
00:14:07,480 --> 00:14:10,480
Tad ka jaunā mātes gada 7 būtu arī jābūt ar bērnu,

190
00:14:10,480 --> 00:14:16,480
un ka bērns tad būtu sibling gada 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Pārvietojas on.

192
00:14:21,040 --> 00:14:24,930
Kad mēs sākām mūsu diskusija par bināro koku,

193
00:14:24,930 --> 00:14:28,790
Mēs runājām par to, kā mēs gatavojamies izmantot tos, lai

194
00:14:28,790 --> 00:14:32,800
iegūt priekšrocības pār gan masīvu un saistīto saraksti.

195
00:14:32,800 --> 00:14:37,220
Un kā mēs esam gatavojas darīt, ir ar šo pasūtīšanas īpašumu.

196
00:14:37,220 --> 00:14:41,080
Mēs sakām, ka bināro koks ir pasūtīts, saskaņā ar specifikāciju,

197
00:14:41,080 --> 00:14:45,740
ja par katru mezglu mūsu koku, visi tās pēcnācēji, no kreisās -

198
00:14:45,740 --> 00:14:48,670
kreisi bērns un visa kreisā bērna pēctečiem -

199
00:14:48,670 --> 00:14:54,510
ir mazāk vērtības un visu uz tiesībām mezglu -

200
00:14:54,510 --> 00:14:57,770
tiesības bērnam un visas tiesības bērna pēctečiem -

201
00:14:57,770 --> 00:15:02,800
ir mezglu lielākas nekā vērtība pašreizējās mezglā ka mēs esam meklē.

202
00:15:02,800 --> 00:15:07,850
Tikai pēc vienkāršības, mēs esam gatavojas pieņemt, ka tajā nav dublēt mezgli mūsu koku.

203
00:15:07,850 --> 00:15:11,180
Piemēram, šajā kokā mēs nebrauksim, lai risinātu ar lietu

204
00:15:11,180 --> 00:15:13,680
kur mums ir vērtība 7 pie saknes

205
00:15:13,680 --> 00:15:16,720
 un tad mums ir arī vērtība 7 citur koku.

206
00:15:16,720 --> 00:15:24,390
Šajā gadījumā, jūs pamanīsiet, ka šis koks ir patiesi pasūtīts.

207
00:15:24,390 --> 00:15:26,510
Mums ir vērtība 7 pie saknes.

208
00:15:26,510 --> 00:15:29,720
Viss pa kreisi no 7 -

209
00:15:29,720 --> 00:15:35,310
ja es atsaukt visus šos maz zīmju šeit -

210
00:15:35,310 --> 00:15:40,450
viss pa kreisi no 7 - 3 un 6 -

211
00:15:40,450 --> 00:15:49,410
šīs vērtības ir gan mazāk nekā 7, un viss pa labi - kas ir tikai šāda 9 -

212
00:15:49,410 --> 00:15:53,450
ir lielāks par 7.

213
00:15:53,450 --> 00:15:58,650
>> Tas ir ne tikai lika koks satur šīs vērtības,

214
00:15:58,650 --> 00:16:03,120
bet pieņemsim izdarīt vēl dažus no tiem.

215
00:16:03,120 --> 00:16:05,030
Ir tiešām viss ķekars veidiem, ka mēs varam darīt.

216
00:16:05,030 --> 00:16:09,380
Es esmu gatavojas izmantot stenogrāfija tikai, lai saglabātu lietas vienkārši, ja -

217
00:16:09,380 --> 00:16:11,520
nevis zīmēšanas veic visa kastes-un-bultiņām -

218
00:16:11,520 --> 00:16:14,220
Es esmu tikai gatavojas izdarīt numurus un pievienot bultas, kas tos savieno.

219
00:16:14,220 --> 00:16:22,920
Lai sāktu, mēs vienkārši uzrakstīt savu sākotnējo koku atkal, ja mums bija 7, un tad 3,

220
00:16:22,920 --> 00:16:25,590
un tad 3 norādīja atpakaļ uz tiesībām uz 6,

221
00:16:25,590 --> 00:16:30,890
un 7 bija tiesības bērns, kas bija 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Kas ir vēl viens veids, ka mēs varētu uzrakstīt šo koku?

223
00:16:33,860 --> 00:16:38,800
Vietā, 3 kurām kreiso bērns 7,

224
00:16:38,800 --> 00:16:41,360
mēs varētu arī būt 6 kurām kreiso bērns 7,

225
00:16:41,360 --> 00:16:44,470
un tad 3 kurām kreiso bērns 6.

226
00:16:44,470 --> 00:16:48,520
Tas izskatās šī koka tepat kur man 7,

227
00:16:48,520 --> 00:16:57,860
tad 6, tad 3, un par tiesībām 9.

228
00:16:57,860 --> 00:17:01,490
Mēs arī nav jābūt ar 7 kā mūsu saknes mezgla.

229
00:17:01,490 --> 00:17:03,860
Mēs varētu arī būt 6 kā mūsu saknes mezgla.

230
00:17:03,860 --> 00:17:06,470
Kas būtu, ka izskatās?

231
00:17:06,470 --> 00:17:09,230
Ja mēs spēsim saglabāt šo pasūtīts īpašumu,

232
00:17:09,230 --> 00:17:12,970
viss pa kreisi no 6, ir mazāks nekā to.

233
00:17:12,970 --> 00:17:16,540
Ir tikai viena iespēja, un tas ir 3.

234
00:17:16,540 --> 00:17:19,869
Bet tad kā labo bērns 6, mums ir divas iespējas.

235
00:17:19,869 --> 00:17:25,380
Pirmkārt, mēs varētu būt 7 un tad 9,

236
00:17:25,380 --> 00:17:28,850
vai mēs varētu izdarīt to - piemēram, es esmu par to darīt šeit -

237
00:17:28,850 --> 00:17:34,790
kur mums ir 9 kā labo bērns 6,

238
00:17:34,790 --> 00:17:39,050
un tad 7, kā kreisajā bērnu 9 mēnešu.

239
00:17:39,050 --> 00:17:44,240
>> Tagad, 7 un 6 ir ne tikai iespējamās vērtības saknes.

240
00:17:44,240 --> 00:17:50,200
Mēs varētu arī ir 3 būt saknes.

241
00:17:50,200 --> 00:17:52,240
Kas notiek, ja 3 ir pie saknes?

242
00:17:52,240 --> 00:17:54,390
Lūk, lietas iegūt mazliet interesanti.

243
00:17:54,390 --> 00:17:58,440
Trīs nav nekādas vērtības, kas ir mazāk nekā to,

244
00:17:58,440 --> 00:18:02,070
lai viss kreisajā pusē koks ir tikai būs nulle.

245
00:18:02,070 --> 00:18:03,230
Tur nav būs kaut tur.

246
00:18:03,230 --> 00:18:07,220
Pa labi, mēs varētu saraksts lietas augošā secībā.

247
00:18:07,220 --> 00:18:15,530
Mēs varētu būt 3, 6 tad, tad 7, tad 9.

248
00:18:15,530 --> 00:18:26,710
Vai mēs varētu darīt 3, tad 6, tad 9, tad līdz 7.

249
00:18:26,710 --> 00:18:35,020
Vai mēs varētu darīt 3, tad 7, tad 6, tad 9.

250
00:18:35,020 --> 00:18:40,950
Vai, 3, 7 - patiesībā nē, mēs nevaram darīt 7 vairs.

251
00:18:40,950 --> 00:18:43,330
Tas ir mūsu viena lieta tur.

252
00:18:43,330 --> 00:18:54,710
Mēs varam darīt 9, un tad no 9 mēs varam darīt 6 un tad līdz 7.

253
00:18:54,710 --> 00:19:06,980
Vai arī mēs varam darīt 3, tad 9, tad 7, un tad 6.

254
00:19:06,980 --> 00:19:12,490
>> Viena lieta, lai pievērstu Jūsu uzmanību šeit ir

255
00:19:12,490 --> 00:19:14,510
ka šie koki ir mazliet dīvaini izskata.

256
00:19:14,510 --> 00:19:17,840
Jo īpaši, ja mēs skatāmies uz 4 kokiem labajā pusē -

257
00:19:17,840 --> 00:19:20,930
Es aplis viņiem, šeit -

258
00:19:20,930 --> 00:19:28,410
šie koki izskatās gandrīz tieši tāpat saistītajā sarakstā.

259
00:19:28,410 --> 00:19:32,670
Katrs mezgls ir tikai viens bērns,

260
00:19:32,670 --> 00:19:38,950
un tāpēc mums nav kāds no šīs koka līdzīgu struktūru, ka mēs redzam, piemēram,

261
00:19:38,950 --> 00:19:44,720
 šajā vienā vientuļo koku nekā šeit uz apakšējā kreisajā pusē.

262
00:19:44,720 --> 00:19:52,490
Šie koki ir faktiski aicināja izvirst bināro koku,

263
00:19:52,490 --> 00:19:54,170
un mēs runājam par šiem vairāk nākotnē -

264
00:19:54,170 --> 00:19:56,730
it īpaši, ja jūs doties uz veikt citus datorzinātņu kursus.

265
00:19:56,730 --> 00:19:59,670
Šie koki ir izdzimtenis.

266
00:19:59,670 --> 00:20:03,780
Viņi nav ļoti noderīgs, jo, protams, šī struktūra pakļauj sevi

267
00:20:03,780 --> 00:20:08,060
 lai uzmeklēšanas reizes līdzīgi tā saistītajā sarakstā.

268
00:20:08,060 --> 00:20:13,050
Mums nav nokļūt izmantot papildu atmiņu - šo papildu rādītāju -

269
00:20:13,050 --> 00:20:18,840
jo mūsu struktūras ir slikti šādā veidā.

270
00:20:18,840 --> 00:20:24,700
Nevis iet un izņemt bināro koku, kas ir 9 saknē,

271
00:20:24,700 --> 00:20:27,220
kas ir pēdējais gadījums, ka mēs būtu,

272
00:20:27,220 --> 00:20:32,380
mēs esam vietā, šajā brīdī, gatavojas runāt mazliet par šo citu terminu

273
00:20:32,380 --> 00:20:36,150
ka mēs izmantojam, runājot par kokiem, ko sauc augstums.

274
00:20:36,150 --> 00:20:45,460
>> Par koku augstums ir attālums no saknes līdz visvairāk tālā mezglā,

275
00:20:45,460 --> 00:20:48,370
vai drīzāk skaitu apiņu, kas jums būs darīt, lai

276
00:20:48,370 --> 00:20:53,750
sākas no saknes, un tad galu galā pie visvairāk tālā mezglu koku.

277
00:20:53,750 --> 00:20:57,330
Ja mēs apskatīt dažus no šiem kokiem, ka mēs esam izdarīt tieši šeit,

278
00:20:57,330 --> 00:21:07,870
mēs varam redzēt, ka, ja mēs šo koku augšējā kreisajā stūrī, un mēs sākam pie 3,

279
00:21:07,870 --> 00:21:14,510
tad mums ir, lai 1 hop nokļūt 6, otrs hop nokļūt līdz 7,

280
00:21:14,510 --> 00:21:20,560
un trešo hop nokļūt 9 mēnešu.

281
00:21:20,560 --> 00:21:26,120
Tātad, šī koka augstums ir 3.

282
00:21:26,120 --> 00:21:30,640
Mēs varam darīt to pašu izmantot citu kokiem izklāstīti ar šo zaļo,

283
00:21:30,640 --> 00:21:40,100
un mēs redzam, ka no visiem šiem kokiem augstums ir arī patiešām 3.

284
00:21:40,100 --> 00:21:45,230
Tas ir daļa, kas padara viņus deģenerāts -

285
00:21:45,230 --> 00:21:53,750
ka to augstums ir tikai viens mazāks nekā skaits mezglu visu koku.

286
00:21:53,750 --> 00:21:58,400
Ja mēs skatāmies uz šo citu koku, kas ir apņemta ar sarkanu, no otras puses,

287
00:21:58,400 --> 00:22:03,920
mēs redzam, ka lielākā daļa tālā lapu mezgli ir 6, 9 -

288
00:22:03,920 --> 00:22:06,940
atstāj šo ziņu mezgli, kurām nav bērnu.

289
00:22:06,940 --> 00:22:11,760
Tātad, lai iegūtu no saknes mezgla nu 6 vai 9,

290
00:22:11,760 --> 00:22:17,840
mums ir, lai viens apiņu nokļūt līdz 7 un tad otro hop nokļūt 9,

291
00:22:17,840 --> 00:22:21,240
un tāpat, tikai otrais apiņu no 7 līdz nokļūt 6.

292
00:22:21,240 --> 00:22:29,080
Tātad, no šī koka augstums nekā šeit ir tikai 2.

293
00:22:29,080 --> 00:22:35,330
Jūs varat doties atpakaļ un darīt, ka visi citi koki, ka mēs iepriekš apspriests

294
00:22:35,330 --> 00:22:37,380
sākot ar 7, 6,

295
00:22:37,480 --> 00:22:42,500
un jūs atradīsiet, ka no visiem šiem kokiem augstums ir arī 2.

296
00:22:42,500 --> 00:22:46,320
>> Iemesls, kāpēc mēs esam runājuši par pasūtīts bināro koku

297
00:22:46,320 --> 00:22:50,250
un kāpēc viņi foršs, jo jūs varat meklēt, izmantojot tām

298
00:22:50,250 --> 00:22:53,810
ļoti līdzīgi kā meklējot pa šķiroto masīvs.

299
00:22:53,810 --> 00:22:58,720
Tas ir, ja mēs runājam par kļūst, ka uzlabota uzmeklēšanas laiks

300
00:22:58,720 --> 00:23:02,730
pār vienkāršu saistīts saraksts.

301
00:23:02,730 --> 00:23:05,010
Ar saistīts saraksts - ja jūs vēlaties atrast konkrētu elementu -

302
00:23:05,010 --> 00:23:07,470
Jūs esat pie vislabāk gatavojas darīt kaut kādas lineārās meklēšanas

303
00:23:07,470 --> 00:23:10,920
kur jūs sākat sākumā saraksta un apiņu vienu pēc otras -

304
00:23:10,920 --> 00:23:12,620
viens mezgls ar vienu mezglu -

305
00:23:12,620 --> 00:23:16,060
pa visu sarakstu, līdz jūs atradīsiet ko jūs meklējat.

306
00:23:16,060 --> 00:23:19,440
Tā kā, ja jums ir bināro koku, kas glabājas šajā jauka formātā,

307
00:23:19,440 --> 00:23:23,300
Jūs faktiski var iegūt vairāk par bināro meklēšanu notiek

308
00:23:23,300 --> 00:23:25,160
kur tu skaldi un valdi

309
00:23:25,160 --> 00:23:29,490
un meklēt, izmantojot atbilstošu pusē koku pie katra soļa.

310
00:23:29,490 --> 00:23:32,840
Let 's redzēt, kā kas darbojas.

311
00:23:32,840 --> 00:23:38,850
>> Ja mums ir - atkal dodas atpakaļ uz mūsu sākotnējā koku -

312
00:23:38,850 --> 00:23:46,710
Mēs sākas 7, mums ir 3 pa kreisi, 9 par tiesībām,

313
00:23:46,710 --> 00:23:51,740
un zem 3 Mums ir 6.

314
00:23:51,740 --> 00:24:01,880
Ja mēs gribam, lai meklētu numuru 6 šajā kokā, mēs gribētu sākt saknē.

315
00:24:01,880 --> 00:24:08,910
Mēs varētu salīdzināt vērtību mēs meklējam, teiksim 6,

316
00:24:08,910 --> 00:24:12,320
ar vērtību glabājas mezglā, ka mēs pašlaik meklē, 7,

317
00:24:12,320 --> 00:24:21,200
Ierīce 6 ir patiešām mazāk nekā 7, tāpēc mēs gribētu pārcelties uz kreiso pusi.

318
00:24:21,200 --> 00:24:25,530
Ja gada 6 vērtība bija lielāka nekā 7, mēs būtu tā vietā pārvietots pa labi.

319
00:24:25,530 --> 00:24:29,770
Jo mēs zinām, ka - sakarā ar struktūru mūsu pasūtīto bināro koku -

320
00:24:29,770 --> 00:24:33,910
visas vērtības mazāk nekā 7 gatavojas glabāt pa kreisi no 7,

321
00:24:33,910 --> 00:24:40,520
nav nepieciešams pat apnikt meklē caur labajā pusē no koka.

322
00:24:40,520 --> 00:24:43,780
Kad mēs pāriet uz kreiso pusi, un mēs esam tagad pie mezglā ir 3,

323
00:24:43,780 --> 00:24:48,110
mēs varam darīt to pašu salīdzinājumu atkal, ja mēs salīdzinām 3 un 6.

324
00:24:48,110 --> 00:24:52,430
Un mēs redzam, ka, lai gan 6 - vērtība, mēs meklējam - ir lielāks par 3,

325
00:24:52,430 --> 00:24:58,580
mēs varam iet uz labo pusi mezglu satur 3.

326
00:24:58,580 --> 00:25:02,670
Nav kreisā puse šeit, lai mēs varētu neņemt vērā to.

327
00:25:02,670 --> 00:25:06,510
Bet mēs tikai zinām, ka tāpēc, ka mēs esam apskatot koku pati,

328
00:25:06,510 --> 00:25:08,660
un mēs varam redzēt, ka koks nav bērni.

329
00:25:08,660 --> 00:25:13,640
>> Tas ir arī diezgan viegli uzmeklēt 6 Šajā kokā, ja mēs darām to sevi par cilvēkiem,

330
00:25:13,640 --> 00:25:16,890
bet pieņemsim sekot šim procesam mehāniski, piemēram, datoru varētu darīt

331
00:25:16,890 --> 00:25:18,620
lai tiešām saprastu algoritmu.

332
00:25:18,620 --> 00:25:26,200
Šajā brīdī, mēs šobrīd meklē mezglu, kas satur 6,

333
00:25:26,200 --> 00:25:29,180
un mēs meklējam vērtību 6,

334
00:25:29,180 --> 00:25:31,740
tik tiešām, mēs esam atraduši piemērotu mezglā.

335
00:25:31,740 --> 00:25:35,070
Mēs atradām vērtība 6 mūsu koku, un mēs varam apturēt mūsu meklēšanu.

336
00:25:35,070 --> 00:25:37,330
Šajā brīdī, atkarībā no tā, kas notiek,

337
00:25:37,330 --> 00:25:41,870
mēs varam teikt, jā, mēs esam atraduši vērtību 6, tā pastāv mūsu koku.

338
00:25:41,870 --> 00:25:47,640
Vai, ja mēs plānojam ievietot mezglu vai darīt kaut ko, mēs varam darīt, ka šajā brīdī.

339
00:25:47,640 --> 00:25:53,010
>> Darīsim pāris vairāk lookups tikai, lai redzētu, kā tas darbojas.

340
00:25:53,010 --> 00:25:59,390
Apskatīsim, kas notiek, ja mēs mēģinātu meklēt vērtību 10.

341
00:25:59,390 --> 00:26:02,970
Ja mēs meklēt vērtību 10, mēs varētu sākt saknē.

342
00:26:02,970 --> 00:26:07,070
Mēs gribētu redzēt, ka 10 ir lielāks par 7, tāpēc mēs gribētu pārcelties uz labo pusi.

343
00:26:07,070 --> 00:26:13,640
Mēs gribētu nokļūt 9 mēnešu un salīdzināt 9-10 AND redzēt, ka 9 patiešām mazāk nekā 10.

344
00:26:13,640 --> 00:26:16,210
Tātad vēlreiz, mēs gribētu mēģināt pāriet uz labo pusi.

345
00:26:16,210 --> 00:26:20,350
Bet šajā brīdī, mēs paziņojums, ka mēs esam pie Null mezglā.

346
00:26:20,350 --> 00:26:23,080
Tur nekā nav. Tur nekas, kur 10 jābūt.

347
00:26:23,080 --> 00:26:29,360
Tas ir, ja mēs varam ziņot neveiksmi - ka patiešām nav kokā 10.

348
00:26:29,360 --> 00:26:35,420
Un visbeidzot, iesim cauri ja mēs cenšamies meklēt 1 no koka.

349
00:26:35,420 --> 00:26:38,790
Tas ir līdzīgi tam, kas notiek, ja mēs skatāmies uz augšu 10, izņemot nevis doties pa labi,

350
00:26:38,790 --> 00:26:41,260
mēs gatavojamies iet pa kreisi.

351
00:26:41,260 --> 00:26:46,170
Mēs sākas 7 un redzēt, ka 1 ir mazāks nekā 7, tāpēc mēs pāriet uz kreiso pusi.

352
00:26:46,170 --> 00:26:51,750
Mēs nokļūt 3 un redzēt, ka 1 ir mazāks par 3, lai atkal mēs cenšamies, lai pārvietotos pa kreisi.

353
00:26:51,750 --> 00:26:59,080
Šajā brīdī mums ir null mezglā, lai atkal mēs varam ziņot neveiksmi.

354
00:26:59,080 --> 00:27:10,260
>> Ja jūs vēlaties uzzināt vairāk par bināro koku,

355
00:27:10,260 --> 00:27:14,420
tur ir viss ķekars fun maz problēmas, kas jūs varat darīt ar tiem.

356
00:27:14,420 --> 00:27:19,450
Es iesaku praktizē zīmējumu no šīm diagrammām vienu pēc otras

357
00:27:19,450 --> 00:27:21,910
un pēc caur visiem dažādos posmos,

358
00:27:21,910 --> 00:27:25,060
jo tas nāk super-ērts

359
00:27:25,060 --> 00:27:27,480
ne tikai tad, kad jūs darāt Huffman kodēšanas problēmu kopumu

360
00:27:27,480 --> 00:27:29,390
bet arī turpmākās kursos -

361
00:27:29,390 --> 00:27:32,220
tikai mācīties, kā izdarīt šos datu struktūras un domāt ar problēmām

362
00:27:32,220 --> 00:27:38,000
ar pildspalvu un papīru vai, šajā gadījumā, iPad un spalvai.

363
00:27:38,000 --> 00:27:41,000
>> Šajā brīdī, lai gan, mēs spēsim virzīties uz darīt kādu kodēšanas praksi

364
00:27:41,000 --> 00:27:44,870
un faktiski spēlē ar šiem bināriem kokiem un redzēt.

365
00:27:44,870 --> 00:27:52,150
Es esmu gatavojas pāriet atpakaļ uz manu datoru.

366
00:27:52,150 --> 00:27:58,480
Šajā daļā sadaļā, nevis izmantojot CS50 Run vai CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Es esmu gatavojas izmantot ierīci.

368
00:28:01,500 --> 00:28:04,950
>> Pēc kopā ar šo problēmu Set specifikāciju,

369
00:28:04,950 --> 00:28:07,740
Es redzu, ka es esmu vajadzēja atvērt ierīci,

370
00:28:07,740 --> 00:28:11,020
dodieties uz manu Dropbox mapi, izveidot mapi sauc 7.pants,

371
00:28:11,020 --> 00:28:15,730
un pēc tam izveidot failu sauc binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Šeit mēs iet. Man ierīce jau ir atvērts.

373
00:28:22,050 --> 00:28:25,910
Es esmu gatavojas uzvilkt terminālu.

374
00:28:25,910 --> 00:28:38,250
Es iešu uz Dropbox mapi, lai direktoriju sauc section7,

375
00:28:38,250 --> 00:28:42,230
un redzu, tas ir pilnīgi tukšs.

376
00:28:42,230 --> 00:28:48,860
Tagad es esmu gatavojas atvērt binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Šeit mēs aiziet - tukšu failu.

378
00:28:51,750 --> 00:28:54,330
>> Iesim atpakaļ uz specifikācijai.

379
00:28:54,330 --> 00:28:59,850
Specifikācija prasa izveidot jaunu tipa definīciju

380
00:28:59,850 --> 00:29:03,080
par bināro koku mezglu satur int vērtības -

381
00:29:03,080 --> 00:29:07,110
tāpat kā vērtības, kas mums izvilka jo mūsu diagrammu iepriekš.

382
00:29:07,110 --> 00:29:11,740
Mēs ejam, lai izmantotu šo tekstveidnes typedef ka mēs esam darījuši šeit

383
00:29:11,740 --> 00:29:14,420
ka jums vajadzētu atpazīt no Problem Set 5 -

384
00:29:14,420 --> 00:29:19,190
ja jūs hash tabulas ceļu iekarošana Speller programmā.

385
00:29:19,190 --> 00:29:22,540
Jums vajadzētu arī atzīt to no pagājušās nedēļas sadaļā

386
00:29:22,540 --> 00:29:23,890
kur mēs runājām par saistītas sarakstiem.

387
00:29:23,890 --> 00:29:27,870
Mēs esam ieguvuši šo typedef no struct mezglā,

388
00:29:27,870 --> 00:29:34,430
un mēs esam dota šī struct mezglā šo vārdu struct mezglā pirms tam rūpīgi

389
00:29:34,430 --> 00:29:39,350
lai mēs varētu tad uz to, jo mēs vēlamies, lai būtu struct mezglā norādes

390
00:29:39,350 --> 00:29:45,740
kā daļu no mūsu struct, bet mēs esam tam apkārt šo -

391
00:29:45,740 --> 00:29:47,700
vai drīzāk, liktas šo - jo typedef

392
00:29:47,700 --> 00:29:54,600
tā ka, vēlāk kodu, mēs varam atsaukties uz šo struct kā tikai mezglu, nevis struct mezglā.

393
00:29:54,600 --> 00:30:03,120
>> Tas būs ļoti līdzīgs atsevišķi saistītās saraksta definīcijas, ka mēs redzējām pagājušajā nedēļā.

394
00:30:03,120 --> 00:30:20,070
Lai to izdarītu, pieņemsim tikai sākt ar izrakstīšanas tekstveidnes.

395
00:30:20,070 --> 00:30:23,840
Mēs zinām, ka mums ir jābūt veselam skaitlim vērtība,

396
00:30:23,840 --> 00:30:32,170
tāpēc mēs nodot int vērtību, un pēc tam tā vietā, tikai vienu rādītāju uz nākamo elementu -

397
00:30:32,170 --> 00:30:33,970
kā mēs to darījām ar atsevišķi saistītiem sarakstiem -

398
00:30:33,970 --> 00:30:38,110
mēs ejam, lai būtu labi un kreisi bērnu norādes.

399
00:30:38,110 --> 00:30:42,880
Tas ir diezgan vienkārši pārāk - struct mezglā * kreisi bērns;

400
00:30:42,880 --> 00:30:51,190
un struktūrai mezglu * labi bērns;. Atdzist.

401
00:30:51,190 --> 00:30:54,740
Tas izskatās diezgan labs sākums.

402
00:30:54,740 --> 00:30:58,530
Iesim atpakaļ uz specifikācijai.

403
00:30:58,530 --> 00:31:05,030
>> Tagad mums ir nepieciešams deklarēt globāla mezglu * mainīgo, lai saknes koku.

404
00:31:05,030 --> 00:31:10,590
Mēs ejam, lai padarītu šo globālo tāpat kā mēs tos vispirms rādītāju mūsu saistīts sarakstā arī pasaules.

405
00:31:10,590 --> 00:31:12,690
Tas bija tā, ka funkcijas, ko mēs rakstīt

406
00:31:12,690 --> 00:31:16,180
mums nav, lai saglabātu iet ap šo sakni -

407
00:31:16,180 --> 00:31:19,620
gan mēs redzēsim, ka, ja jūs vēlaties rakstīt šīs funkcijas rekursīvi,

408
00:31:19,620 --> 00:31:22,830
tas varētu būt labāk, lai nav pat iet tā apkārt kā globāla pirmajā vietā

409
00:31:22,830 --> 00:31:28,090
un tā vietā sāktu to lokāli savā galvenā funkcija.

410
00:31:28,090 --> 00:31:31,960
Bet, mēs darīsim to globāli, lai sāktu.

411
00:31:31,960 --> 00:31:39,920
Atkal, mēs sniegsim pāris telpās, un es esmu gatavojas pasludināt mezglu * saknes.

412
00:31:39,920 --> 00:31:46,770
Tikai, lai pārliecinātos, ka man nav atstāt šajā neinicializēts, es esmu gatavojas noteikt to vienāds ar null.

413
00:31:46,770 --> 00:31:52,210
Tagad, galvenā funkcija - ko mēs rakstīt ļoti ātri šeit -

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

415
00:32:00,450 --> 00:32:10,640
un es esmu gatavojas sākt deklarējot savu argv masīvs kā const tikai tāpēc, ka es zinu

416
00:32:10,640 --> 00:32:14,550
ka šie argumenti ir argumenti, ka es, iespējams, nevēlas mainīt.

417
00:32:14,550 --> 00:32:18,390
Ja es gribu, lai tos grozīt man būtu iespējams padarīt to kopijas.

418
00:32:18,390 --> 00:32:21,740
Jūs redzēt šo partiju kodu.

419
00:32:21,740 --> 00:32:25,440
Tas ir jauki, vai nu veidā. Tas ir jauki, lai atstāt to kā - neveikt const ja vēlaties.

420
00:32:25,440 --> 00:32:28,630
Es parasti likt to tikai tāpēc, ka es sev atgādinu

421
00:32:28,630 --> 00:32:33,650
 ka es, iespējams, nevēlaties mainīt šos argumentus.

422
00:32:33,650 --> 00:32:39,240
>> Kā vienmēr, es esmu gatavojas iekļaut šo atpakaļ 0 līnijas beigās galvenais.

423
00:32:39,240 --> 00:32:45,730
Lūk, es sāktu savu saknes mezgla.

424
00:32:45,730 --> 00:32:48,900
Kā tas ir tagad, es esam ieguvuši rādītāju, kas ir iestatīts uz null,

425
00:32:48,900 --> 00:32:52,970
tāpēc tas ir pavērsts neko.

426
00:32:52,970 --> 00:32:57,480
Lai faktiski sākt ēkas mezglā,

427
00:32:57,480 --> 00:32:59,250
Man vispirms ir piešķirt atmiņu par to.

428
00:32:59,250 --> 00:33:05,910
Es esmu gatavojas darīt, ka, veicot atmiņas par kaudzes, izmantojot malloc.

429
00:33:05,910 --> 00:33:10,660
Es esmu gatavojas noteikt saknes vienāds ar rezultātu malloc,

430
00:33:10,660 --> 00:33:19,550
un es esmu gatavojas izmantot sizeof operators aprēķina lielumu mezglā.

431
00:33:19,550 --> 00:33:24,990
Iemesls, ka es izmantot sizeof mezgla pretstatā, teiksim,

432
00:33:24,990 --> 00:33:37,020
kaut kas līdzīgs šim - malloc (4 + 4 +4) vai malloc 12 -

433
00:33:37,020 --> 00:33:40,820
ir tāpēc, ka es vēlos, lai mana koda būt iespējamā savienojamība.

434
00:33:40,820 --> 00:33:44,540
Es gribu, lai varētu izmantot šo. C failu, apkopo to uz ierīces,

435
00:33:44,540 --> 00:33:48,820
un tad sastādīt to par manu 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
vai uz pavisam citu arhitektūru -

437
00:33:52,040 --> 00:33:54,640
un es gribu šo visu darbu pats.

438
00:33:54,640 --> 00:33:59,510
>> Ja es esmu padarot pieņēmumus par lielumu mainīgie -

439
00:33:59,510 --> 00:34:02,070
lielumu int vai par rādītāju lielumu -

440
00:34:02,070 --> 00:34:06,070
tad es esmu arī izdarīt pieņēmumus par to arhitektūru veidiem

441
00:34:06,070 --> 00:34:10,440
par kuru mans kods var veiksmīgi sastādīt kad rādīt.

442
00:34:10,440 --> 00:34:15,030
Vienmēr izmantot sizeof pretstatā manuāli summējot struct laukus.

443
00:34:15,030 --> 00:34:20,500
Otrs iemesls ir tas, ka tur varētu būt arī polsterējums, ka kompilators liek uz struct.

444
00:34:20,500 --> 00:34:26,570
Pat tikai summējot atsevišķu lauku nav kaut kas jūs parasti vēlas darīt,

445
00:34:26,570 --> 00:34:30,340
tāpēc, izdzēsiet šo līniju.

446
00:34:30,340 --> 00:34:33,090
Tagad, lai patiešām sāktu šo saknes mezgla,

447
00:34:33,090 --> 00:34:36,489
Es esmu nāksies plug vērtības katrā no dažādām jomām.

448
00:34:36,489 --> 00:34:41,400
Piemēram, par vērtību es zinu, es gribu, lai sāktu 7,

449
00:34:41,400 --> 00:34:46,920
un tagad es esmu gatavojas noteikt kreisi bērnam būt Null

450
00:34:46,920 --> 00:34:55,820
un tiesības bērnam arī būt nulle. Lieliski!

451
00:34:55,820 --> 00:35:02,670
Mēs esam darījuši, ka daļa no spec.

452
00:35:02,670 --> 00:35:07,390
>> Specifikācija leju apakšā 3 lapas man prasa, lai radītu vēl trīs mezglus -

453
00:35:07,390 --> 00:35:10,600
viens, kas satur 3, viens, kas satur 6, viens un 9 -

454
00:35:10,600 --> 00:35:14,210
un tad stiepļu tos uz augšu, lai tas izskatās tieši tāpat kā mūsu koku diagrammu

455
00:35:14,210 --> 00:35:17,120
ka mēs runājām par agrāk.

456
00:35:17,120 --> 00:35:20,450
Darīsim ka diezgan ātri šeit.

457
00:35:20,450 --> 00:35:26,270
Jūs redzēsiet patiešām ātri, ka es esmu gatavojas sākt rakstīt ķekars dublikātu kodu.

458
00:35:26,270 --> 00:35:32,100
Es esmu gatavojas izveidot mezglu * un es esmu gatavojas saukt trīs.

459
00:35:32,100 --> 00:35:36,000
Es esmu gatavojas noteikt to vienāds ar malloc (sizeof (mezgls)).

460
00:35:36,000 --> 00:35:41,070
Es esmu gatavojas noteikt triju> Value = 3.

461
00:35:41,070 --> 00:35:54,780
Trīs -> left_child = NULL; trīs -> labo _child = NULL; kā arī.

462
00:35:54,780 --> 00:36:01,150
Kas izskatās diezgan līdzīgs inicializēšana saknes, un tas ir tieši tas, ko

463
00:36:01,150 --> 00:36:05,760
Es esmu nāksies darīt, ja es sāktu inicializējot 6 un 9, kā arī.

464
00:36:05,760 --> 00:36:20,720
Es darīšu, ka tiešām ātri šeit - patiesībā, es esmu gatavojas darīt nedaudz kopēt un ielīmēt,

465
00:36:20,720 --> 00:36:46,140
un pārliecinieties, ka es - alright.

466
00:36:46,470 --> 00:37:09,900
 Tagad man to nokopēt un es varētu iet uz priekšu un noteikt šī vienāds ar 6.

467
00:37:09,900 --> 00:37:14,670
Jūs varat redzēt, ka tas aizņem awhile un nav super-efektīvas.

468
00:37:14,670 --> 00:37:22,610
Tikai mazliet, mēs rakstīt funkciju, kas to dara par mums.

469
00:37:22,610 --> 00:37:32,890
Es gribu, lai aizstātu šo ar 9, nomainiet ka ar 6.

470
00:37:32,890 --> 00:37:37,360
>> Tagad mēs esam ieguvuši visas mūsu mezglu izveidota un inicializēts.

471
00:37:37,360 --> 00:37:41,200
Mēs esam ieguvuši mūsu saknes noteikts vienāds ar 7, vai satur vērtību 7,

472
00:37:41,200 --> 00:37:46,510
Mūsu mezglā ir 3, mūsu mezgls satur 6, un mūsu mezglu, kas satur 9.

473
00:37:46,510 --> 00:37:50,390
Šajā brīdī, viss, kas mums ir jādara, ir stieples viss uz augšu.

474
00:37:50,390 --> 00:37:53,020
Iemesls es inicializēts visas norādes uz null, ir tikai tāpēc, ka es pārliecinos, ka

475
00:37:53,020 --> 00:37:56,260
Man nav nekādas neinicializēts norādes ar tur nejauši.

476
00:37:56,260 --> 00:38:02,290
Un arī tā, šajā brīdī, man ir tikai faktiski savienotu mezglu ar otru -

477
00:38:02,290 --> 00:38:04,750
uz tiem, kas viņi patiesībā savienotas - Man nav iet cauri un padarīt

478
00:38:04,750 --> 00:38:08,240
pārliecinieties, ka visas nulls ir tur piemērotās vietās.

479
00:38:08,240 --> 00:38:15,630
>> Sākot saknē, es zinu, ka sakne ir kreisā bērns ir 3.

480
00:38:15,630 --> 00:38:21,250
Es zinu, ka sakne tiesības bērns ir 9.

481
00:38:21,250 --> 00:38:24,880
Pēc tam, vienīgais bērns, kas man ir pa kreisi, lai jāuztraucas par

482
00:38:24,880 --> 00:38:39,080
ir 3 tiesības bērns, kas ir 6.

483
00:38:39,080 --> 00:38:44,670
Šajā brīdī, tas viss izskatās diezgan labi.

484
00:38:44,670 --> 00:38:54,210
Mēs izdzēstu dažas no šīm līnijām.

485
00:38:54,210 --> 00:38:59,540
Tagad viss izskatās diezgan labi.

486
00:38:59,540 --> 00:39:04,240
Iesim atpakaļ uz mūsu specifikācijām un redzēt, kas mums ir jādara nākamo.

487
00:39:04,240 --> 00:39:07,610
>> Šajā brīdī, mums ir rakstīt sauc funkciju "satur"

488
00:39:07,610 --> 00:39:14,150
ar prototipu "bool satur (int vērtība)".

489
00:39:14,150 --> 00:39:17,060
Un tas satur funkcija ir gatavojas atgriezties true

490
00:39:17,060 --> 00:39:21,200
 ja koku mūsu globālo saknes mainīgā norādīja

491
00:39:21,200 --> 00:39:26,950
 satur vērtību pārgāja funkciju un viltus citādi.

492
00:39:26,950 --> 00:39:29,000
Iesim uz priekšu un darīt.

493
00:39:29,000 --> 00:39:35,380
Tas būs tieši tāpat lookup ka mums bija ar roku uz iPad tikai nedaudz atpakaļ.

494
00:39:35,380 --> 00:39:40,130
Pieņemsim tuvinātu atpakaļ mazliet un ritiniet uz augšu.

495
00:39:40,130 --> 00:39:43,130
Mēs ejam, lai šo funkciju tieši virs mūsu galvenā funkcija

496
00:39:43,130 --> 00:39:48,990
tāpēc, ka mums nav jādara jebkādu prototipu.

497
00:39:48,990 --> 00:39:55,960
Tātad, bool satur (int vērtība).

498
00:39:55,960 --> 00:40:00,330
Tur mums iet. Tur ir mūsu tekstveidnes deklarācija.

499
00:40:00,330 --> 00:40:02,900
Tikai, lai pārliecinātos, ka tas apkopo,

500
00:40:02,900 --> 00:40:06,820
Es iešu uz priekšu un vienkārši noteikt to vienāds atgriezties viltus.

501
00:40:06,820 --> 00:40:09,980
Tieši tagad šī funkcija vienkārši nevar darīt neko, un vienmēr ziņo, ka

502
00:40:09,980 --> 00:40:14,010
vērtību, ko mēs meklējam, nav kokā.

503
00:40:14,010 --> 00:40:16,280
>> Šajā brīdī, tas ir iespējams, laba ideja -

504
00:40:16,280 --> 00:40:19,600
jo mēs esam rakstiski visu ķekars kodu un mums nav pat mēģinājuši testēšana vēl -

505
00:40:19,600 --> 00:40:22,590
lai pārliecinātos, ka tas viss apkopo.

506
00:40:22,590 --> 00:40:27,460
Ir lietas, kas mums ir jādara, lai pārliecinātos, ka tas patiešām apkopo pāris.

507
00:40:27,460 --> 00:40:33,530
Pirmkārt, vai mēs esam izmantojuši kādas funkcijas jebkuros bibliotēkās, ka mēs vēl neesam iekļauti.

508
00:40:33,530 --> 00:40:37,940
Funkcijas mēs esam, ko līdz šim ir malloc,

509
00:40:37,940 --> 00:40:43,310
un tad mēs esam arī izmanto šāda veida - šo nestandarta veida sauc par "bool' -

510
00:40:43,310 --> 00:40:45,750
kas ir iekļauta standarta bool header failu.

511
00:40:45,750 --> 00:40:53,250
Mēs noteikti vēlamies iekļaut standarta bool.h par bool tipa,

512
00:40:53,250 --> 00:40:59,230
un mēs arī vēlamies # ietvert standarta lib.h par standarta bibliotēkām

513
00:40:59,230 --> 00:41:03,530
kas ietver malloc un bezmaksas, un visi no tā.

514
00:41:03,530 --> 00:41:08,660
Tātad, zoom out, mēs ejam, lai izietu.

515
00:41:08,660 --> 00:41:14,190
Pamēģināsim un pārliecinieties, ka tas tiešām bija sastādīt.

516
00:41:14,190 --> 00:41:18,150
Mēs redzam, ka tas tā ir, tāpēc mēs esam uz pareizā ceļa.

517
00:41:18,150 --> 00:41:22,990
>> Pieņemsim atvērt binary_tree.c atkal.

518
00:41:22,990 --> 00:41:34,530
Tā apkopo. Iesim uz leju un pārliecinieties, ka mēs ievietot dažas zvanus uz mūsu Satur funkciju -

519
00:41:34,530 --> 00:41:40,130
tikai, lai pārliecinātos, ka viss ir labi un labs.

520
00:41:40,130 --> 00:41:43,170
Piemēram, ja mēs kādu lookups mūsu koku agrāk,

521
00:41:43,170 --> 00:41:48,500
mēs mēģināja uzzināt vērtības 6, 10, 1 un, un mēs zinājām, ka 6 bija kokā,

522
00:41:48,500 --> 00:41:52,220
10 bija nevis no koka, un 1 nebija kokā nu.

523
00:41:52,220 --> 00:41:57,230
Pieņemsim izmantot šos paraugus zvanus, kā veids, lai noskaidrotu, vai nav

524
00:41:57,230 --> 00:41:59,880
Mūsu Satur funkcija darbojas.

525
00:41:59,880 --> 00:42:05,210
Lai to izdarītu, es esmu gatavojas izmantot printf funkciju,

526
00:42:05,210 --> 00:42:10,280
un mēs esam gatavojas izdrukāt rezultātu aicinājumu satur.

527
00:42:10,280 --> 00:42:13,280
Es esmu gatavojas īstenot virkni "satur (% d) = jo

528
00:42:13,280 --> 00:42:20,470
 mēs ejam uz kontaktdakšu vērtībā ka mēs ejam meklēt,

529
00:42:20,470 --> 00:42:27,130
un =% s \ n "un izmantot to kā mūsu formāta virknes.

530
00:42:27,130 --> 00:42:30,720
Mēs esam tikai gatavojas, lai redzētu - burtiski izdrukāt uz ekrāna -

531
00:42:30,720 --> 00:42:32,060
kāda izskatās funkciju zvanu.

532
00:42:32,060 --> 00:42:33,580
Tas nav reāli funkcija zvans.

533
00:42:33,580 --> 00:42:36,760
 Tas ir tikai virkne paredzēti, lai izskatās funkciju zvanu.

534
00:42:36,760 --> 00:42:41,140
>> Tagad mēs esam gatavojas plug vērtībām.

535
00:42:41,140 --> 00:42:43,580
Mēs ejam, lai mēģinātu satur gada 6,

536
00:42:43,580 --> 00:42:48,340
un tad ko mēs gatavojamies darīt, šeit ir izmantot šo trīskāršo operators.

537
00:42:48,340 --> 00:42:56,340
Pieņemsim redzēt - satur 6 - tāpēc, tagad es esmu iekļauts 6 un ja ir 6 ir taisnība,

538
00:42:56,340 --> 00:43:01,850
virkne, kas mēs esam gatavojas sūtīt uz% s formātā rakstura

539
00:43:01,850 --> 00:43:04,850
būs virkne "patiess".

540
00:43:04,850 --> 00:43:07,690
Pieņemsim ritināt pa mazliet.

541
00:43:07,690 --> 00:43:16,210
Pretējā gadījumā mēs vēlamies, lai nosūtītu virkne "viltus", ja ir 6 atdevi viltus.

542
00:43:16,210 --> 00:43:19,730
Tas ir maz dumjš izskata, bet es skaitlis es varētu arī ilustrētu

543
00:43:19,730 --> 00:43:23,780
ko trīskāršo operators izskatās, jo mēs neesam redzējuši to awhile.

544
00:43:23,780 --> 00:43:27,670
Tas būs jauks, ērts veids, lai noskaidrotu, vai mūsu Satur funkcija darbojas.

545
00:43:27,670 --> 00:43:30,040
Es esmu gatavojas ritināt atpakaļ pāri pa kreisi,

546
00:43:30,040 --> 00:43:39,900
un es esmu gatavojas kopēt un ielīmēt šo līniju pāris reizes.

547
00:43:39,900 --> 00:43:44,910
Tas mainīja dažas no šīm vērtībām apkārt,

548
00:43:44,910 --> 00:43:59,380
tāpēc šī būs 1, un tas būs 10.

549
00:43:59,380 --> 00:44:02,480
>> Šajā brīdī mēs esam ieguvuši jauku satur funkciju.

550
00:44:02,480 --> 00:44:06,080
Mēs esam ieguvuši dažas pārbaudes, un mēs redzēsim, ja tas viss darbojas.

551
00:44:06,080 --> 00:44:08,120
Šajā brīdī mēs esam rakstiski dažas vairāk kodu.

552
00:44:08,120 --> 00:44:13,160
Laiks atmest, un pārliecinieties, ka viss vēl apkopo.

553
00:44:13,160 --> 00:44:20,360
Atmest, un tagad pieņemsim mēģināt padarīt bināro koku vēlreiz.

554
00:44:20,360 --> 00:44:22,260
Nu, izskatās, ka mēs esam ieguvuši kļūda,

555
00:44:22,260 --> 00:44:26,930
un mēs esam ieguvuši šo skaidri deklarējot bibliotēkas funkciju printf.

556
00:44:26,930 --> 00:44:39,350
Izskatās, ka mums ir nepieciešams, lai iet un # ietvert standardio.h.

557
00:44:39,350 --> 00:44:45,350
Un ar to, viss būtu jāapkopo. Mēs visi esam labi.

558
00:44:45,350 --> 00:44:50,420
Tagad pamēģināsim darbojas bināro koku un redzēt, kas notiek.

559
00:44:50,420 --> 00:44:53,520
Šeit mēs esam,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
un mēs redzam, ka, kā mēs gaidīts -

561
00:44:55,190 --> 00:44:56,910
jo mēs esam nav īstenots satur vēl,

562
00:44:56,910 --> 00:44:59,800
vai drīzāk, mēs esam tikai likts pretī viltus -

563
00:44:59,800 --> 00:45:03,300
mēs redzam, ka tā ir tikai atgriežas viltus visiem tiem,

564
00:45:03,300 --> 00:45:06,180
lai viss strādā lielākoties diezgan labi.

565
00:45:06,180 --> 00:45:11,860
>> Iesim atpakaļ un faktiski īstenot satur šajā brīdī.

566
00:45:11,860 --> 00:45:17,490
Es esmu gatavojas, lai ritinātu uz leju, tuvinātu, un -

567
00:45:17,490 --> 00:45:22,330
atcerieties, algoritms, ka mēs izmantojām bija tas, ka mēs sākām pie saknes mezgla

568
00:45:22,330 --> 00:45:28,010
un tad katrā mezglā ka mēs saskaramies, mēs salīdzinājumu,

569
00:45:28,010 --> 00:45:32,380
un, pamatojoties uz šo salīdzinājumu, mēs vai nu pāriet uz kreiso bērnam vai uz labo bērnam.

570
00:45:32,380 --> 00:45:39,670
Tas ir gatavojas izskatās ļoti līdzīgi bināro meklēšanas kodu, kas mums rakstīja agrāk termiņā.

571
00:45:39,670 --> 00:45:47,810
Kad mēs sāktu, mēs zinām, ka mēs vēlamies, lai turēt uz pašreizējo mezglu

572
00:45:47,810 --> 00:45:54,050
ka mēs esam apskatot, un pašreizējā mezglā tiks inicializēts uz saknes mezgla.

573
00:45:54,050 --> 00:45:56,260
Un tagad mēs esam gatavojas glabāt iet caur koku,

574
00:45:56,260 --> 00:45:58,140
un atcerēties, ka mūsu apstāšanās nosacījumu -

575
00:45:58,140 --> 00:46:01,870
 kad mēs faktiski strādāja ar piemēru ar roku -

576
00:46:01,870 --> 00:46:03,960
bija, kad mēs saskārāmies ar null mezglā,

577
00:46:03,960 --> 00:46:05,480
nevis kad mēs paskatījās Null bērnu,

578
00:46:05,480 --> 00:46:09,620
bet, kad mēs faktiski pārcēlās uz mezglu kokā

579
00:46:09,620 --> 00:46:12,640
un konstatēja, ka mēs esam pie Null mezglā.

580
00:46:12,640 --> 00:46:20,720
Mēs ejam, lai atkārtot līdz hronoloģija nav vienāds ar null.

581
00:46:20,720 --> 00:46:22,920
Un ko mēs darīsim?

582
00:46:22,920 --> 00:46:31,610
Mēs ejam, lai pārbaudītu, vai (ar pašreizējo -> vērtība == vērtība),

583
00:46:31,610 --> 00:46:35,160
tad mēs zinām, ka mēs esam faktiski konstatēts mezglu ka mēs meklējam.

584
00:46:35,160 --> 00:46:40,450
Tātad šeit mēs varam atgriezties taisnība.

585
00:46:40,450 --> 00:46:49,830
Pretējā gadījumā mēs gribam redzēt, vai vērtība ir mazāka par vērtību.

586
00:46:49,830 --> 00:46:53,850
Ja pašreizējais mezgla vērtība ir mazāka par vērtību, mēs meklējam,

587
00:46:53,850 --> 00:46:57,280
mēs esam gatavojas pārcelties uz labo pusi.

588
00:46:57,280 --> 00:47:10,600
Tātad, cur = cur -> right_child, un citādi, mēs ejam, lai pārvietotos pa kreisi.

589
00:47:10,600 --> 00:47:17,480
cur = cur -> left_child;. Diezgan vienkārši.

590
00:47:17,480 --> 00:47:22,830
>> Jūs, iespējams, atzīst cilpa, kas izskatās ļoti līdzīgs šim no

591
00:47:22,830 --> 00:47:27,580
binārā meklēšana agrāk termiņā, izņemot tad mēs būtu darīšana ar zemu, vidēja un augsta.

592
00:47:27,580 --> 00:47:30,000
Lūk, mums vienkārši ir apskatīt pašreizējo vērtību,

593
00:47:30,000 --> 00:47:31,930
tāpēc tas ir jauki un vienkārši.

594
00:47:31,930 --> 00:47:34,960
Pārliecināsimies šis kods strādā.

595
00:47:34,960 --> 00:47:42,780
Pirmkārt, pārliecinieties, ka tā apkopo. Izskatās, ka tas dara.

596
00:47:42,780 --> 00:47:47,920
Mēģināsim rādīt to.

597
00:47:47,920 --> 00:47:50,160
Un tiešām, tas izdrukā visu, kas mums gaidāms.

598
00:47:50,160 --> 00:47:54,320
Tā konstatē 6 kokā, nav atrast 10, jo 10 nav kokā,

599
00:47:54,320 --> 00:47:57,740
un neatrod 1 nu, jo 1 arī nav kokā.

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

601
00:48:01,420 --> 00:48:04,470
>> Alright. Iesim atpakaļ uz mūsu specifikācijām un redzēt, ko tālāk.

602
00:48:04,470 --> 00:48:07,990
Tagad tā vēlas pievienot dažas vairāk punktus, mūsu koku.

603
00:48:07,990 --> 00:48:11,690
Tā vēlas, lai pievienotu 5, 2, 8 un, un pārliecinieties, ka mūsu ir kods

604
00:48:11,690 --> 00:48:13,570
joprojām darbojas, kā paredzēts.

605
00:48:13,570 --> 00:48:14,900
Iesim darīt.

606
00:48:14,900 --> 00:48:19,430
Šajā brīdī, nevis darot, ka kaitinošas kopēt un ielīmēt atkal,

607
00:48:19,430 --> 00:48:23,770
pieņemsim uzrakstīt funkciju, lai faktiski izveidotu mezglu.

608
00:48:23,770 --> 00:48:27,740
Ja mēs ritiniet uz leju visu ceļu uz galveno, mēs redzam, ka mēs esam darot

609
00:48:27,740 --> 00:48:31,210
ļoti līdzīgs kods atkal un atkal katru reizi, ka mēs vēlamies, lai izveidotu mezglu.

610
00:48:31,210 --> 00:48:39,540
>> Pieņemsim uzrakstīt funkciju, kas būs faktiski veidot mezglu mums un atpakaļ.

611
00:48:39,540 --> 00:48:41,960
Es esmu gatavojas saukt build_node.

612
00:48:41,960 --> 00:48:45,130
Es esmu gatavojas būvēt mezglu ar īpašu vērtību.

613
00:48:45,130 --> 00:48:51,040
Tuvinātu šeit.

614
00:48:51,040 --> 00:48:56,600
Pirmā lieta, es esmu gatavojas darīt, ir faktiski izveidot telpu mezgla uz kaudzes.

615
00:48:56,600 --> 00:49:05,400
Tātad, mezglu * n = malloc (sizeof (mezgls)), n -> vērtība = vērtība;

616
00:49:05,400 --> 00:49:14,960
un tad šeit, es esmu tikai gatavojas, lai sāktu visu no jomām būtu atbilstošas ​​vērtības.

617
00:49:14,960 --> 00:49:22,500
Un pašās beigās, mēs atgrieztos mūsu mezglā.

618
00:49:22,500 --> 00:49:28,690
Alright. Viena lieta ir tas, ka šo funkciju tieši šeit

619
00:49:28,690 --> 00:49:34,320
gatavojas atgriezties rādītāju uz atmiņu, kas ir kaudze-piešķirta.

620
00:49:34,320 --> 00:49:38,880
Kas ir jauka par šo ir tas, ka šis mezgls tagad -

621
00:49:38,880 --> 00:49:42,420
mums ir atzīt to par kaudzes, jo, ja mēs deklarēta to skursteņa

622
00:49:42,420 --> 00:49:45,050
mēs nevarētu to darīt šo funkciju kā šis.

623
00:49:45,050 --> 00:49:47,690
Ka atmiņas varētu aiziet no jomas

624
00:49:47,690 --> 00:49:51,590
un būtu nederīgs, ja mēs centāmies, lai piekļūtu to vēlāk.

625
00:49:51,590 --> 00:49:53,500
Tā kā mēs esam paziņojot kaudze-piešķirto atmiņu,

626
00:49:53,500 --> 00:49:55,830
mēs nāksies rūpēties par atbrīvojot to vēlāk

627
00:49:55,830 --> 00:49:58,530
mūsu programmā nav noplūdes nekādas atmiņas.

628
00:49:58,530 --> 00:50:01,270
Mēs esam punting par ka viss pārējais kodu

629
00:50:01,270 --> 00:50:02,880
tikai Vienkāršības labad laikā,

630
00:50:02,880 --> 00:50:05,610
bet, ja jūs kādreiz uzrakstīt funkciju, kas izskatās šādi

631
00:50:05,610 --> 00:50:10,370
kur jūs esat ieguvuši - daži to sauc malloc vai realloc iekšā -

632
00:50:10,370 --> 00:50:14,330
Jūs vēlaties pārliecināties, ka jūs varat ievietot sava veida komentāru šeit, kas saka,

633
00:50:14,330 --> 00:50:29,970
hey, jūs zināt, atgriež kaudze iedalītas mezglu inicializēts ar neuzskaitītu-vērtības.

634
00:50:29,970 --> 00:50:33,600
Un tad jūs vēlaties, lai pārliecinātos, ka jūs nodot kaut kādas piezīmes, kas saka

635
00:50:33,600 --> 00:50:41,720
zvanītājs jāatbrīvo atgriezto atmiņu.

636
00:50:41,720 --> 00:50:45,450
Tādā veidā, ja kāds kādreiz iet un izmanto šo funkciju,

637
00:50:45,450 --> 00:50:48,150
viņi zina, ka neatkarīgi viņi saņem atpakaļ no šī funkcija

638
00:50:48,150 --> 00:50:50,870
kādā brīdī būs nepieciešams atbrīvot.

639
00:50:50,870 --> 00:50:53,940
>> Pieņemot, ka viss ir labi un labs šeit,

640
00:50:53,940 --> 00:51:02,300
mēs varam iet uz leju mūsu kodu un aizstāt visus šos līniju tieši šeit

641
00:51:02,300 --> 00:51:05,410
ar zvaniem uz mūsu būvēt mezgla funkciju.

642
00:51:05,410 --> 00:51:08,170
Darīsim kas tiešām ātri.

643
00:51:08,170 --> 00:51:15,840
No vienas puses, ka mēs nebrauksim, lai aizstātu ir šī daļa noteikti šeit

644
00:51:15,840 --> 00:51:18,520
apakšā, kur mēs faktiski vadi līdz mezglus norādīt uz otru,

645
00:51:18,520 --> 00:51:21,030
tāpēc, ka mēs nevaram darīt mūsu funkcija.

646
00:51:21,030 --> 00:51:37,400
Bet, pieņemsim do saknes = build_node (7); mezglā * trīs = build_node (3);

647
00:51:37,400 --> 00:51:47,980
mezglu * Sešu = build_node (6); mezglā * 9 = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
Un tagad mēs arī vēlējāmies, lai pievienotu mezglu -

649
00:51:52,590 --> 00:52:03,530
mezglu * Pieci = build_node (5); mezglā * 8 = build_node (8);

650
00:52:03,530 --> 00:52:09,760
un kāda bija citu mezglu? Pieņemsim redzēt šeit. Mēs vēlējāmies, lai arī pievienot 2 -

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

652
00:52:20,280 --> 00:52:26,850
Alright. Šajā brīdī, mēs zinām, ka mēs esam ieguvuši 7, 3, 9, un 6

653
00:52:26,850 --> 00:52:30,320
visu vadu uz augšu pareizi, bet kas par 5, 8 un 2?

654
00:52:30,320 --> 00:52:33,550
Saglabāt visu atbilstošā kārtībā,

655
00:52:33,550 --> 00:52:39,230
Mēs zinām, ka trīs tiesības bērns ir 6.

656
00:52:39,230 --> 00:52:40,890
Tātad, ja mēs ejam, lai pievienotu 5,

657
00:52:40,890 --> 00:52:46,670
5 arī pieder pareizajā pusē koka, no kuriem 3 ir saknes,

658
00:52:46,670 --> 00:52:50,440
tā 5 pieder kā kreisajā bērns gada 6.

659
00:52:50,440 --> 00:52:58,650
Mēs varam darīt, sakot, sešus -> left_child = pieciem;

660
00:52:58,650 --> 00:53:10,790
un tad 8 pieder kā kreisajā bērns gada 9, tā nine -> left_child = astoņi;

661
00:53:10,790 --> 00:53:22,190
un tad 2 ir kreisā bērns no 3, lai mēs varam darīt, ka šeit - tev -> left_child = divi;.

662
00:53:22,190 --> 00:53:27,730
Ja Jums nav gluži sekot kopā ar to, ka es jums iesakām izdarīt to ārā pats.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Pieņemsim glābt šo. Iesim ārā un pārliecinieties, ka tā apkopo,

664
00:53:35,660 --> 00:53:40,760
un tad mēs varam pievienot mūsu satur zvaniem.

665
00:53:40,760 --> 00:53:44,120
Izskatās viss vēl apkopo.

666
00:53:44,120 --> 00:53:51,790
Iesim un pievienot dažas satur zvanus.

667
00:53:51,790 --> 00:53:59,640
Atkal, es esmu gatavojas darīt mazliet kopēt un ielīmēt.

668
00:53:59,640 --> 00:54:15,860
Tagad meklēt 5, 8, un 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Pieņemsim pārliecinieties, ka tas viss izskatās labi vēl. Lieliski! Saglabāt un atmest.

670
00:54:28,330 --> 00:54:33,220
Tagad pieņemsim, apkopot, un tagad pieņemsim darboties.

671
00:54:33,220 --> 00:54:37,540
No rezultātiem, izskatās, ka viss strādā tikai jauki un labi.

672
00:54:37,540 --> 00:54:41,780
Lieliski! Tāpēc tagad mēs esam ieguvuši mūsu Satur funkcija rakstīts.

673
00:54:41,780 --> 00:54:46,160
Pieņemsim pāriet un sākt strādāt, kā ievietot mezglu kokā

674
00:54:46,160 --> 00:54:50,000
jo, kā mēs darām to jau tagad, lietas nav ļoti skaists.

675
00:54:50,000 --> 00:54:52,280
>> Ja mēs ejam atpakaļ uz specifikāciju,

676
00:54:52,280 --> 00:55:00,540
tā lūdz mūs uzrakstīt funkciju sauc ievietot - atkal atgriežas bool

677
00:55:00,540 --> 00:55:04,400
par to, vai mēs patiešām varētu ievietot mezglu kokā -

678
00:55:04,400 --> 00:55:07,710
un tad vērtība ir iekļaut koku ir norādīts kā

679
00:55:07,710 --> 00:55:11,060
vienīgais arguments, lai mūsu ievietot funkciju.

680
00:55:11,060 --> 00:55:18,180
Mēs atgriezīsimies taisnība, ja mēs patiesi varētu ievietot mezglu satur vērtību kokā,

681
00:55:18,180 --> 00:55:20,930
kas nozīmē, ka mēs, viens, bija pietiekami daudz atmiņas,

682
00:55:20,930 --> 00:55:24,840
un tad divas, ka mezgls nav jau kokā, jo -

683
00:55:24,840 --> 00:55:32,170
Atcerieties, mēs neesam nāksies dublikātus kokā, tikai, lai lietas vienkārši.

684
00:55:32,170 --> 00:55:35,590
Alright. Atpakaļ uz kodu.

685
00:55:35,590 --> 00:55:44,240
Atveriet to. Tuvināt mazliet, tad ritiniet uz leju.

686
00:55:44,240 --> 00:55:47,220
Palūkosimies ievietot funkciju tieši virs satur.

687
00:55:47,220 --> 00:55:56,360
Atkal, tas notiek, lai varētu saukt bool ieliktnis (int vērtība).

688
00:55:56,360 --> 00:56:01,840
Dodiet tai nedaudz vairāk vietas, un pēc tam, kā noklusējuma

689
00:56:01,840 --> 00:56:08,870
pieņemsim likts pretī viltus pašās beigās.

690
00:56:08,870 --> 00:56:22,620
Tagad leju apakšā, iesim uz priekšu un nevis manuāli ēkas mezglus

691
00:56:22,620 --> 00:56:27,900
galvenajā sevi un elektroinstalācijas tos norādīt uz otru, piemēram, mēs darām,

692
00:56:27,900 --> 00:56:30,600
mēs paļauties uz mūsu ievietot funkciju, lai to izdarītu.

693
00:56:30,600 --> 00:56:35,510
Mēs ne paļauties uz mūsu ievietot funkciju, lai izveidotu visu koku no nulles tikai vēl,

694
00:56:35,510 --> 00:56:39,970
bet mēs atbrīvoties no šīm līnijām - we'll komentēt šo līniju -

695
00:56:39,970 --> 00:56:43,430
ka veidot mezglu 5, 8, un 2.

696
00:56:43,430 --> 00:56:55,740
Un tā vietā, mēs ievietot zvanu uz mūsu ievietot funkciju

697
00:56:55,740 --> 00:57:01,280
lai pārliecinātos, ka tas patiešām darbojas.

698
00:57:01,280 --> 00:57:05,840
Šeit mēs iet.

699
00:57:05,840 --> 00:57:09,300
>> Tagad mēs esam komentēja šos līnijas.

700
00:57:09,300 --> 00:57:13,700
Mums ir tikai 7, 3, 9, 6 un mūsu kokā šajā brīdī.

701
00:57:13,700 --> 00:57:18,870
Lai pārliecinātos, ka tas ir viss strādā,

702
00:57:18,870 --> 00:57:25,050
mēs varam zoom out, lai mūsu bināro koku,

703
00:57:25,050 --> 00:57:30,750
palaist to, un mēs varam redzēt, ka ir tagad stāsta mums, ka mēs esam pilnīgi taisnība -

704
00:57:30,750 --> 00:57:33,110
5, 8, 2 un vairs kokā.

705
00:57:33,110 --> 00:57:37,960
Iet atpakaļ uz kodu,

706
00:57:37,960 --> 00:57:41,070
un kā mēs gatavojamies, lai ievietotu?

707
00:57:41,070 --> 00:57:46,290
Atcerēties, ko mēs darījām, kad mēs faktiski Ievietojot 5, 8, 2 un iepriekš.

708
00:57:46,290 --> 00:57:50,100
Mēs spēlējām ka Plinko spēle, kur mēs sākām pie saknes,

709
00:57:50,100 --> 00:57:52,780
gāja pa koku pa vienam pa vienam

710
00:57:52,780 --> 00:57:54,980
līdz mēs atradām piemērotu plaisu,

711
00:57:54,980 --> 00:57:57,570
un tad mēs vadu no mezglā atbilstošā vietā.

712
00:57:57,570 --> 00:57:59,480
Mēs ejam, lai darīt to pašu.

713
00:57:59,480 --> 00:58:04,070
Tas ir būtībā tāpat rakstot kodu, ka mēs izmantojām satur funkcijas

714
00:58:04,070 --> 00:58:05,910
lai atrastu vietas, kur mezglā jābūt,

715
00:58:05,910 --> 00:58:10,560
un tad mēs esam tikai gatavojas ievietot mezglu tiesības tur.

716
00:58:10,560 --> 00:58:17,000
Sāksim darām.

717
00:58:17,000 --> 00:58:24,200
>> Tātad mums ir mezglu * cur = saknes, mēs esam tikai gatavojas sekot satur kodu

718
00:58:24,200 --> 00:58:26,850
līdz mēs redzam, ka tas nav gluži strādā mums.

719
00:58:26,850 --> 00:58:32,390
Mēs ejam, lai iet cauri koku bet pašreizējais elements nav nulle,

720
00:58:32,390 --> 00:58:45,280
un ja mēs redzam, ka ar pašreizējo vērtība ir vienāda ar vērtību, ko mēs esam mēģina ievietot -

721
00:58:45,280 --> 00:58:49,600
labi, šis ir viens no gadījumiem, kad mēs varētu faktiski nav ievietot mezglu

722
00:58:49,600 --> 00:58:52,730
kokā, jo tas nozīmē, ka mums ir dublikātu vērtību.

723
00:58:52,730 --> 00:58:59,010
Šeit mēs esam patiešām gatavojas atgriezties viltus.

724
00:58:59,010 --> 00:59:08,440
Tagad, cits ja CUR vērtība ir mazāka nekā vērtība,

725
00:59:08,440 --> 00:59:10,930
Tagad mēs zinām, ka mēs virzāmies uz labo

726
00:59:10,930 --> 00:59:17,190
 jo vērtība pieder pareizajā pusē cur koku.

727
00:59:17,190 --> 00:59:30,110
Pretējā gadījumā mēs spēsim virzīties uz kreiso pusi.

728
00:59:30,110 --> 00:59:37,980
Tas būtībā mūsu Satur darbotos labi tur.

729
00:59:37,980 --> 00:59:41,820
>> Šajā brīdī, kad mēs esam izgājuši šo kamēr cilpa,

730
00:59:41,820 --> 00:59:47,350
Mūsu pašreizējo rādītājs ir būs norādot uz null

731
00:59:47,350 --> 00:59:51,540
ja funkcija jau nav atgriezies.

732
00:59:51,540 --> 00:59:58,710
Mēs esam tādēļ, kam cur pie vietas, kur mēs gribam, lai ievietotu jaunu mezglu.

733
00:59:58,710 --> 01:00:05,210
Kas jāpaveic, ir faktiski veidot jaunu mezglu,

734
01:00:05,210 --> 01:00:08,480
ko mēs varam darīt diezgan viegli.

735
01:00:08,480 --> 01:00:14,930
Mēs varam izmantot mūsu super ērts būvēt mezgla funkciju,

736
01:00:14,930 --> 01:00:17,210
un kaut kas mums nav jādara agrāk -

737
01:00:17,210 --> 01:00:21,400
Mēs tikko veida ņēma par pašsaprotamu, bet tagad mēs darīsim tikai, lai pārliecinātos -

738
01:00:21,400 --> 01:00:27,130
mēs pārbaudīt, lai pārliecinātos, ka atgriezto vērtību jaunu mezglu bija patiešām

739
01:00:27,130 --> 01:00:33,410
nav null, jo mēs nevēlamies, lai sāktu piekļuvi šai atmiņu, ja tas ir nulle.

740
01:00:33,410 --> 01:00:39,910
Mēs varam pārbaudīt, lai pārliecinātos, ka jaunais mezgls nav vienāds ar null.

741
01:00:39,910 --> 01:00:42,910
Vai vietā, mēs varam tikai redzēt, ja tas tiešām ir nulle,

742
01:00:42,910 --> 01:00:52,120
un ja tas ir nulle, tad mēs varam vienkārši atgriezties viltus agri.

743
01:00:52,120 --> 01:00:59,090
>> Šajā brīdī, mums ir vadu jaunu mezglu savā piemērotā vietā kokā.

744
01:00:59,090 --> 01:01:03,510
Ja mēs atskatāmies uz galveno un kur mēs faktiski bija elektroinstalācijas vērtībām pirms,

745
01:01:03,510 --> 01:01:08,470
mēs redzam, ka veids, kā mēs darām to, kad mēs vēlējāmies īstenot 3 kokā

746
01:01:08,470 --> 01:01:11,750
Tika mēs piekļūt kreiso bērns saknes.

747
01:01:11,750 --> 01:01:14,920
Kad mēs 9 kokā, mums bija, lai piekļūtu tiesības bērns saknes.

748
01:01:14,920 --> 01:01:21,030
Mums bija jābūt rādītāju uz vecākiem, lai likt jaunu vērtību kokā.

749
01:01:21,030 --> 01:01:24,430
Ritinot atpakaļ uz augšu, lai ievietotu, ka nav gatavojas gluži darbs šeit

750
01:01:24,430 --> 01:01:27,550
jo mums nav mātes rādītāju.

751
01:01:27,550 --> 01:01:31,650
Ko mēs gribam, lai varētu darīt, ir, šajā brīdī,

752
01:01:31,650 --> 01:01:37,080
pārbaudiet vecāku vērtības un redzēt - labi, ak Dievs,

753
01:01:37,080 --> 01:01:41,990
Ja vecāks vērtība ir mazāka nekā pašreizējā vērtība,

754
01:01:41,990 --> 01:01:54,440
Tad vecāku tiesībām bērnam vajadzētu būt jaunais mezgls;

755
01:01:54,440 --> 01:02:07,280
citādi, vecāku kreisā bērnam jābūt jaunu mezglu.

756
01:02:07,280 --> 01:02:10,290
Bet, mums nav šo vecāku rādītāju diezgan yet.

757
01:02:10,290 --> 01:02:15,010
>> Lai saņemtu to, mēs esam patiešām nāksies izsekot to, kā mums iet cauri koku

758
01:02:15,010 --> 01:02:18,440
un atrast piemērotu vietu mūsu cilpa iepriekš.

759
01:02:18,440 --> 01:02:26,840
Mēs varam darīt, ritinot atpakaļ uz augšu uz augšu mūsu ievietot funkciju

760
01:02:26,840 --> 01:02:32,350
un uzskaites citu rādītāju mainīgo sauc mātes.

761
01:02:32,350 --> 01:02:39,340
Mēs ejam, lai uzstādītu to vienāda null sākotnēji,

762
01:02:39,340 --> 01:02:43,640
un tad katru reizi, kad mēs iet cauri koku,

763
01:02:43,640 --> 01:02:51,540
mēs esam gatavojas noteikt mātes rādītāju saskaņot pašreizējo rādītāju.

764
01:02:51,540 --> 01:02:59,140
Uzstādīt vecākiem vienāds ar cur.

765
01:02:59,140 --> 01:03:02,260
Tādā veidā, katru reizi mēs iet cauri,

766
01:03:02,260 --> 01:03:05,550
mēs spēsim nodrošināt, ka pašreizējais rādītājs kļūst pieaudzis

767
01:03:05,550 --> 01:03:12,640
mātes rādītājs izriet tas - tikai vienu līmeni augstāks nekā pašreizējā rādītāja kokā.

768
01:03:12,640 --> 01:03:17,370
Tas viss izskatās diezgan labi.

769
01:03:17,370 --> 01:03:22,380
>> Es domāju, ka viena lieta, ka mēs gribam, lai pielāgotu tas būvēt mezglā atgriežas null.

770
01:03:22,380 --> 01:03:25,380
Lai iegūtu veidotu mezglu faktiski veiksmīgi atgriezties null,

771
01:03:25,380 --> 01:03:31,060
mums nāksies mainīt šo kodu,

772
01:03:31,060 --> 01:03:37,270
jo šeit, mēs nekad nav pārbaudīta, lai pārliecinātos, ka malloc atgriezies derīgu rādītāju.

773
01:03:37,270 --> 01:03:53,390
Tātad, ja (n = NULL!), Tad -

774
01:03:53,390 --> 01:03:55,250
ja malloc atgriezās derīgu rādītāju, tad mēs sāktu to;

775
01:03:55,250 --> 01:04:02,540
Pretējā gadījumā mēs vienkārši atgriezties un ka galu galā atgriežas null mums.

776
01:04:02,540 --> 01:04:13,050
Tagad viss izskatās diezgan labi. Pārliecināsimies tas patiesībā apkopo.

777
01:04:13,050 --> 01:04:22,240
Padarīt bināro koku, un oh, mēs esam ieguvuši dažas lietas notiek šeit.

778
01:04:22,240 --> 01:04:29,230
>> Mēs esam ieguvuši netiešs deklarācija funkciju būvēt mezglā.

779
01:04:29,230 --> 01:04:31,950
Atkal, ar šiem kompilatori, mēs esam gatavojas sākt augšpusē.

780
01:04:31,950 --> 01:04:36,380
Ko tas jāsaprot, ka es esmu aicinot veidot mezglu, pirms es esmu faktiski atzina to.

781
01:04:36,380 --> 01:04:37,730
Iesim atpakaļ uz kodu tiešām ātri.

782
01:04:37,730 --> 01:04:43,510
Ritiniet uz leju, un tik tiešām, mans ieliktnis funkcija tiek deklarēta

783
01:04:43,510 --> 01:04:47,400
virs būvēt mezgla funkciju,

784
01:04:47,400 --> 01:04:50,070
bet es cenšos izmantot veidot mezglu iekšā ieliktņa.

785
01:04:50,070 --> 01:05:06,610
Es esmu gatavojas iet un kopēt - un pēc tam ielīmējiet būvēt mezgla funkciju ceļu augšup šeit augšā.

786
01:05:06,610 --> 01:05:11,750
Tādā veidā, cerams, ka būs darbs. Dosim tas vēl iet.

787
01:05:11,750 --> 01:05:18,920
Tagad tas viss apkopo. Viss ir labi.

788
01:05:18,920 --> 01:05:21,640
>> Bet šajā brīdī, mēs esam faktiski nav saukta mūsu ievietot funkciju.

789
01:05:21,640 --> 01:05:26,510
Mēs tikai zinām, ka tā apkopo, tāpēc pieņemsim iet un nodot dažus zvanus iekšā

790
01:05:26,510 --> 01:05:28,240
Darīsim, ka mūsu galvenā funkcija.

791
01:05:28,240 --> 01:05:32,390
Lūk, mēs komentēja, 5, 8, un 2,

792
01:05:32,390 --> 01:05:36,680
un tad mēs neesam stiepļu tos uz augšu uz leju šeit.

793
01:05:36,680 --> 01:05:41,640
Pieņemsim veikt dažas prasa ievietot,

794
01:05:41,640 --> 01:05:46,440
un pieņemsim arī izmantot to pašu veida stuff, ka mēs izmantojām

795
01:05:46,440 --> 01:05:52,810
kad mēs, šos printf zvanus, lai pārliecinātos, ka viss did get ievietota pareizi.

796
01:05:52,810 --> 01:06:00,550
Es esmu gatavojas kopēt un ielīmēt,

797
01:06:00,550 --> 01:06:12,450
un tā vietā, satur mēs gatavojamies darīt ieliktni.

798
01:06:12,450 --> 01:06:30,140
Un nevis 6, 10, 1 un, mēs spēsim izmantot 5, 8, un 2.

799
01:06:30,140 --> 01:06:37,320
Tas būtu cerams ievietot 5, 8, 2 un kokā.

800
01:06:37,320 --> 01:06:44,050
Sastādīt. Viss ir labi. Tagad mēs faktiski vadīt mūsu programmu.

801
01:06:44,050 --> 01:06:47,330
>> Viss atgriezās nepatiesa.

802
01:06:47,330 --> 01:06:53,830
Tātad, 5, 8, 2 un nav iet, un tas izskatās Satur nav atrast tos vai nu.

803
01:06:53,830 --> 01:06:58,890
Kas notiek? Pieņemsim attālinātu.

804
01:06:58,890 --> 01:07:02,160
Pirmā problēma bija tā, ka ievietot šķita atgriezties viltus,

805
01:07:02,160 --> 01:07:08,750
un izskatās, ka tas tāpēc, ka mēs atstāt mūsu atgriešanās viltus zvanu,

806
01:07:08,750 --> 01:07:14,590
un mēs nekad faktiski atgriezās taisnība.

807
01:07:14,590 --> 01:07:17,880
Mēs varam noteikt, ka uz augšu.

808
01:07:17,880 --> 01:07:25,290
Otra problēma ir, tagad pat ja mēs darām - glābt šo, atmest šo,

809
01:07:25,290 --> 01:07:34,530
palaist padarīt atkal, ir tas apkopot, tad palaist to -

810
01:07:34,530 --> 01:07:37,670
mēs redzam, ka kaut kas cits noticis šeit.

811
01:07:37,670 --> 01:07:42,980
5, 8, 2 un joprojām nekad nav atrasts kokā.

812
01:07:42,980 --> 01:07:44,350
Tātad, kas notiek?

813
01:07:44,350 --> 01:07:45,700
>> Pieņemsim to apskatīt šo kodu.

814
01:07:45,700 --> 01:07:49,790
Redzēsim, vai mēs varam izrēķināt šo out.

815
01:07:49,790 --> 01:07:57,940
Mēs sākam ar vecākiem nav Null.

816
01:07:57,940 --> 01:07:59,510
Mēs noteikti pašreizējo rādītāju, kas vienāds ar saknes rādītājs,

817
01:07:59,510 --> 01:08:04,280
un mēs esam gatavojas strādāt mūsu ceļu uz leju caur koku.

818
01:08:04,280 --> 01:08:08,650
Ja pašreizējā mezglā nav Null, tad mēs zinām, ka mēs varam virzīties uz leju mazliet.

819
01:08:08,650 --> 01:08:12,330
Mēs, kas mūsu mātes rādītāju ir vienāda ar pašreizējo rādītāju,

820
01:08:12,330 --> 01:08:15,420
pārbauda vērtības - ja vērtības ir pašas mēs atgriezās nepatiesa.

821
01:08:15,420 --> 01:08:17,540
Ja vērtības ir mazāk mēs pārcēlās uz labo;

822
01:08:17,540 --> 01:08:20,399
citādi, mēs pārcēlās uz kreiso pusi.

823
01:08:20,399 --> 01:08:24,220
Tad mēs veidot mezglu. Es tuvinātu mazliet.

824
01:08:24,220 --> 01:08:31,410
Un šeit mēs esam gatavojas izmēģināt, lai vadi līdz vērtības, ir tādi paši.

825
01:08:31,410 --> 01:08:37,250
Kas notiek? Redzēsim, vai, iespējams, Valgrind var dot mums mājienu.

826
01:08:37,250 --> 01:08:43,910
>> Man patīk izmantot Valgrind tikai tāpēc Valgrind tiešām ātri skrien

827
01:08:43,910 --> 01:08:46,729
un stāsta jums, ja ir kādas atmiņas kļūdas.

828
01:08:46,729 --> 01:08:48,300
Kad mēs palaist Valgrind uz kodu,

829
01:08:48,300 --> 01:08:55,859
kā jūs varat redzēt labo here--Valgrind./binary_tree--and hit ienākt.

830
01:08:55,859 --> 01:09:03,640
Tu redzi, ka mums nav nekādas atmiņas kļūda, tāpēc tas izskatās viss ir labi līdz šim.

831
01:09:03,640 --> 01:09:07,529
Mums ir dažas atmiņas noplūdes, ko mēs zinām, jo ​​mēs neesam

832
01:09:07,529 --> 01:09:08,910
notiek, lai atbrīvotu kādu no mūsu mezgliem.

833
01:09:08,910 --> 01:09:13,050
Pamēģināsim darbojas gdb lai redzētu, kas patiesībā notiek.

834
01:09:13,050 --> 01:09:20,010
Mēs darīsim gdb / binary_tree.. Tā booted tikai naudas sodu.

835
01:09:20,010 --> 01:09:23,670
Pieņemsim noteikt lūzuma punkts par ieliktņa.

836
01:09:23,670 --> 01:09:28,600
Pieņemsim darboties.

837
01:09:28,600 --> 01:09:31,200
Izskatās, ka mēs nekad faktiski aicināja ieliktnis.

838
01:09:31,200 --> 01:09:39,410
Izskatās, problēma bija tikai, ka tad, kad es mainīja noteikti šeit galvenā -

839
01:09:39,410 --> 01:09:44,279
Visu šo printf zvaniem no satur -

840
01:09:44,279 --> 01:09:56,430
Es nekad tiešām mainījusies zvanīt ieliktni.

841
01:09:56,430 --> 01:10:01,660
Tagad pieņemsim pamēģināt. Pieņemsim apkopot.

842
01:10:01,660 --> 01:10:09,130
Viss izskatās labi tur. Tagad pamēģināsim darbojas tā, redzēt, kas notiek.

843
01:10:09,130 --> 01:10:13,320
Alright! Viss izskatās diezgan labi tur.

844
01:10:13,320 --> 01:10:18,130
>> Pēdējā lieta, domāt par ir, vai pastāv kādi malu gadījumi šajā ieliktni?

845
01:10:18,130 --> 01:10:23,170
Un izrādās, ka, labi, viena mala lieta, kas vienmēr ir interesanti domāt par

846
01:10:23,170 --> 01:10:26,250
ir, kas notiek, ja jūsu koks ir tukša un jūs nosaukt šo ievietot funkciju?

847
01:10:26,250 --> 01:10:30,330
Vai tas darbojas? Nu, pieņemsim pamēģināt.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c -.

849
01:10:32,110 --> 01:10:35,810
Veids, kā mēs ejam, lai pārbaudītu to, mēs gatavojamies iet uz leju, lai mūsu galvenā funkcija,

850
01:10:35,810 --> 01:10:41,690
un nevis vadu šiem mezgliem up kā šis,

851
01:10:41,690 --> 01:10:56,730
mēs esam tikai gatavojas komentēt visa lieta,

852
01:10:56,730 --> 01:11:02,620
un tā vietā, elektroinstalācijas līdz mezgliem sevi,

853
01:11:02,620 --> 01:11:09,400
mēs faktiski var vienkārši iet uz priekšu un dzēst visu.

854
01:11:09,400 --> 01:11:17,560
Mēs ejam, lai viss zvanu, lai ievietotu.

855
01:11:17,560 --> 01:11:49,020
Tātad, pieņemsim do - nevis 5, 8, 2 un, mēs ejam, lai ievietotu 7, 3, 9 un.

856
01:11:49,020 --> 01:11:58,440
Un tad mēs arī vēlamies, lai ievietotu 6, kā arī.

857
01:11:58,440 --> 01:12:05,190
Saglabāt. Atmest. Padarīt bināro koku.

858
01:12:05,190 --> 01:12:08,540
Tas viss apkopo.

859
01:12:08,540 --> 01:12:10,320
Mēs varam tikai palaist to kā ir, un redzēt, kas notiek,

860
01:12:10,320 --> 01:12:12,770
bet tas arī būs ļoti svarīgi, lai pārliecinātos, ka

861
01:12:12,770 --> 01:12:14,740
mums nav nekādas atmiņas kļūdas,

862
01:12:14,740 --> 01:12:16,840
jo tas ir viens no mūsu malas gadījumu ka mēs zinām par.

863
01:12:16,840 --> 01:12:20,150
>> Pieņemsim pārliecinieties, ka tā darbojas arī zem Valgrind,

864
01:12:20,150 --> 01:12:28,310
ko mēs darīsim, tikai rādīt Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Izskatās, ka mēs patiešām ir viena kļūda no vienā kontekstā -

866
01:12:31,110 --> 01:12:33,790
mums ir šis segmentāciju vaina.

867
01:12:33,790 --> 01:12:36,690
Kas notika?

868
01:12:36,690 --> 01:12:41,650
Valgrind patiesībā stāsta mums, kur tā ir.

869
01:12:41,650 --> 01:12:43,050
Zoom out mazliet.

870
01:12:43,050 --> 01:12:46,040
Izskatās, ka tas, kas notiek mūsu ievietot funkciju,

871
01:12:46,040 --> 01:12:53,420
kur mums ir nederīgs palasīt 4 Platība pie ieliktni, līnija 60.

872
01:12:53,420 --> 01:13:03,590
Iesim atpakaļ un redzēt, kas notiek šeit.

873
01:13:03,590 --> 01:13:05,350
Tāliniet tiešām ātri.

874
01:13:05,350 --> 01:13:14,230
Es gribu, lai pārliecinātos, ka tas nav iet uz ekrāna malā, lai mēs varētu redzēt visu.

875
01:13:14,230 --> 01:13:18,760
Pull ka mazliet. Alright.

876
01:13:18,760 --> 01:13:35,030
Ritiniet uz leju, un problēma ir tieši šeit.

877
01:13:35,030 --> 01:13:40,120
Kas notiek, ja mēs uz leju un mūsu pašreizējā mezglā jau ir nulle,

878
01:13:40,120 --> 01:13:44,010
Mūsu mātes mezglā ir nulle, tāpēc, ja mēs skatāmies uz augšu pie ļoti top, tieši šeit -

879
01:13:44,010 --> 01:13:47,340
ja tas savukārt cilpa nekad faktiski izpilda

880
01:13:47,340 --> 01:13:52,330
jo mūsu pašreizējā vērtība ir Null - mūsu saknes ir spēkā tik hronoloģija ir nulle -

881
01:13:52,330 --> 01:13:57,810
tad mūsu mātes nekad izpaužas iestatīts uz cur vai derīga vērtība,

882
01:13:57,810 --> 01:14:00,580
tāpēc, vecākiem būs arī nulle.

883
01:14:00,580 --> 01:14:03,700
Mums ir nepieciešams atcerēties, lai pārbaudītu, ka

884
01:14:03,700 --> 01:14:08,750
ar laiku mēs noteikti šeit, un mēs sākam piekļūstot vecāku vērtību.

885
01:14:08,750 --> 01:14:13,190
Tātad, kas notiek? Nu, ja vecāks ir Null -

886
01:14:13,190 --> 01:14:17,990
ja (mātes == NULL) - tad mēs zinām, ka

887
01:14:17,990 --> 01:14:19,530
nedrīkst būt kaut kas kokā.

888
01:14:19,530 --> 01:14:22,030
Mums ir jābūt mēģināt ievietot to saknē.

889
01:14:22,030 --> 01:14:32,570
Mēs varam darīt, tikai nosakot saknes vienāds ar jauno mezglu.

890
01:14:32,570 --> 01:14:40,010
Tad šajā brīdī, mēs faktiski gribam iet caur šīm citām lietām.

891
01:14:40,010 --> 01:14:44,780
Tā vietā, tieši šeit, mēs varam darīt, vai nu citur, ja-cits,

892
01:14:44,780 --> 01:14:47,610
vai mēs varētu apvienot visu, šeit cits,

893
01:14:47,610 --> 01:14:56,300
bet šeit mēs tikai izmantot citur, un darīt to, ka veidā.

894
01:14:56,300 --> 01:14:59,030
Tagad mēs esam gatavojas izmēģināt, lai pārliecinātos, ka mūsu vecākiem nav Null

895
01:14:59,030 --> 01:15:02,160
Pirms tam faktiski cenšas piekļūt saviem laukiem.

896
01:15:02,160 --> 01:15:05,330
Tas mums palīdzēs izvairīties no segmentācijas vaina.

897
01:15:05,330 --> 01:15:14,740
Tātad, mēs atmest, zoom out, apkopot, vadīt.

898
01:15:14,740 --> 01:15:18,130
>> Nekādas kļūdas, taču mums vēl ir ķekars atmiņas noplūdes

899
01:15:18,130 --> 01:15:20,650
jo mēs neesam brīvi kādu no mūsu mezgliem.

900
01:15:20,650 --> 01:15:24,350
Bet, ja mēs ejam uz augšu šeit, un mēs skatāmies uz mūsu izdrukas,

901
01:15:24,350 --> 01:15:30,880
mēs redzam, ka, labi, izskatās visi mūsu ieliktņiem tika atgriežas taisnība, kas ir labs.

902
01:15:30,880 --> 01:15:33,050
Šie ieliktņi ir taisnība,

903
01:15:33,050 --> 01:15:36,670
un tad attiecīgi satur zvani ir arī taisnība.

904
01:15:36,670 --> 01:15:41,510
>> Labs darbs! Izskatās, ka mēs esam veiksmīgi rakstīts ieliktni.

905
01:15:41,510 --> 01:15:47,430
Tas ir viss, kas mums ir šīs nedēļas Problem Set specifikācijā.

906
01:15:47,430 --> 01:15:51,720
Viens fun izaicinājums domāt par ir, kā jūs tiešām iet

907
01:15:51,720 --> 01:15:55,340
un bez visas šīs koku mezgliem.

908
01:15:55,340 --> 01:15:58,830
Mēs varam darīt vairākas dažādos veidos,

909
01:15:58,830 --> 01:16:01,930
bet es ņemšu atvaļinājumu, ka līdz jums, lai eksperimentētu,

910
01:16:01,930 --> 01:16:06,080
un kā jautru izaicinājums, izmēģināt un pārliecināties, ka jūs varat pārliecināties

911
01:16:06,080 --> 01:16:09,490
ka šis Valgrind ziņojumā nedeva kļūdas un nav noplūdes.

912
01:16:09,490 --> 01:16:12,880
>> Good luck par šīs nedēļas Huffman kodēšanas problēmu kopumu,

913
01:16:12,880 --> 01:16:14,380
un mēs redzēt jūs nākamajā nedēļā!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]