1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] Раздел 7] [по-малко удобни]

2
00:00:02,500 --> 00:00:04,890
[Нейт Hardison] [Харвардския университет]

3
00:00:04,890 --> 00:00:07,000
[Това е CS50. [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Добре дошли в раздел 7.

5
00:00:09,080 --> 00:00:11,330
Благодарение на ураган Sandy,

6
00:00:11,330 --> 00:00:13,440
вместо като нормален раздел тази седмица,

7
00:00:13,440 --> 00:00:17,650
правим тази разходка през чрез секцията на въпроси.

8
00:00:17,650 --> 00:00:22,830
Аз ще бъда заедно с проблема Задайте 6 спецификация,

9
00:00:22,830 --> 00:00:25,650
и преминава през всички въпроси в

10
00:00:25,650 --> 00:00:27,770
Раздел раздел с въпроси.

11
00:00:27,770 --> 00:00:30,940
Ако има някакви въпроси,

12
00:00:30,940 --> 00:00:32,960
моля пускате тези CS50 Обсъждане.

13
00:00:32,960 --> 00:00:35,480
>> Добре. Нека да започнем.

14
00:00:35,480 --> 00:00:40,780
Точно сега съм на стр. 3 от спецификацията за Проблем Set.

15
00:00:40,780 --> 00:00:44,110
Отиваме първо да започнем да говорим за двоични дървета

16
00:00:44,110 --> 00:00:47,850
тъй като тези, които имат много значение за проблем набор тази седмица -

17
00:00:47,850 --> 00:00:49,950
Дървото Huffman кодиране.

18
00:00:49,950 --> 00:00:55,000
Един от първите структури от данни, ние говорихме за CS50 масива.

19
00:00:55,000 --> 00:01:00,170
Не забравяйте, че масив е последователност от елементи -

20
00:01:00,170 --> 00:01:04,019
от същия вид - се съхраняват в непосредствена близост една до друга в паметта.

21
00:01:04,019 --> 00:01:14,420
Ако имам цяло число масив, който може да се направи използването на този кутии числа, числа стил -

22
00:01:14,420 --> 00:01:20,290
Да кажем, че имам 5 в първото поле, имам 7 във втория,

23
00:01:20,290 --> 00:01:27,760
тогава имам 8, 10 и 20 в окончателния кутия.

24
00:01:27,760 --> 00:01:33,000
Не забравяйте, че двамата наистина добри неща за този масив

25
00:01:33,000 --> 00:01:38,800
са, че имаме тази константа време до всеки отделен елемент

26
00:01:38,800 --> 00:01:40,500
 в масива, ако знаем своя индекс.

27
00:01:40,500 --> 00:01:44,670
Например, ако искате да вземете третият елемент в масива -

28
00:01:44,670 --> 00:01:47,870
индекс 2 нулева индексиране система -

29
00:01:47,870 --> 00:01:52,220
Аз буквално просто трябва да направиш просто математическо изчисление,

30
00:01:52,220 --> 00:01:56,170
хоп за тази позиция в масива,

31
00:01:56,170 --> 00:01:57,840
извадя 8, която се съхранява там,

32
00:01:57,840 --> 00:01:59,260
и аз съм добре да тръгвам.

33
00:01:59,260 --> 00:02:03,350
>> Един от най-лошите неща за този масив - че ние говорихме за

34
00:02:03,350 --> 00:02:05,010
когато обсъждахме свързани списъци -

35
00:02:05,010 --> 00:02:09,120
е, че ако искате да вмъкнете елемент в този масив,

36
00:02:09,120 --> 00:02:11,090
Аз ще трябва да направя известно прехвърляне около.

37
00:02:11,090 --> 00:02:12,940
Например, този масив тук

38
00:02:12,940 --> 00:02:16,850
сортират за сортирани във възходящ ред -

39
00:02:16,850 --> 00:02:19,440
5, 7, след 8, 10, и след това 20 -

40
00:02:19,440 --> 00:02:23,100
но ако искате да вмъкнете номер 9 в този масив,

41
00:02:23,100 --> 00:02:27,460
Отивам да трябва да смени някои от елементите, за да направи място.

42
00:02:27,460 --> 00:02:30,440
Можем да направим това тук.

43
00:02:30,440 --> 00:02:35,650
Аз ще трябва да се движат 5, 7 и 8;

44
00:02:35,650 --> 00:02:38,720
създаване на пропастта, където мога да сложа 9,

45
00:02:38,720 --> 00:02:45,910
и след това на 10 и 20 могат да отидат в правото на девет.

46
00:02:45,910 --> 00:02:49,450
Това е вид болка, защото в най-лошия случай -

47
00:02:49,450 --> 00:02:54,350
когато сме се налага да вмъкнете в началото или в края на

48
00:02:54,350 --> 00:02:56,040
на масива, в зависимост от това как ще променят -

49
00:02:56,040 --> 00:02:58,850
бихме могли в крайна сметка се налага да смени всички елементи

50
00:02:58,850 --> 00:03:00,750
, че ние сме в момента съхраняват в масива.

51
00:03:00,750 --> 00:03:03,810
>> Така че, това, което е начин около това?

52
00:03:03,810 --> 00:03:09,260
Начин около това е да отидете на свързан списък метод, при който -

53
00:03:09,260 --> 00:03:19,820
вместо за съхраняване на елементи 5, 7, 8, 10, и 20 всички един до друг в паметта -

54
00:03:19,820 --> 00:03:25,630
вместо това пък бе да ги съхранявате вид, където искахме да ги съхранявате

55
00:03:25,630 --> 00:03:32,470
в тези свързан списък възли, които съм изтегляне тук, на Ad Hoc.

56
00:03:32,470 --> 00:03:42,060
И след това те да са свързани заедно с използване на тези следващите насоки.

57
00:03:42,060 --> 00:03:44,370
Мога да имам показалеца от 5 до 7,

58
00:03:44,370 --> 00:03:46,420
указател от 7 до 8,

59
00:03:46,420 --> 00:03:47,770
указател от 8 до 10,

60
00:03:47,770 --> 00:03:51,220
и накрая, показалеца от 10 до 20,

61
00:03:51,220 --> 00:03:54,880
и след това с нулев указател на 20, което показва, че не е останало нищо.

62
00:03:54,880 --> 00:03:59,690
Компромисът, които имаме тук

63
00:03:59,690 --> 00:04:05,360
е, че сега, ако искате да вмъкнете номер 9 в сортират нашия списък,

64
00:04:05,360 --> 00:04:08,270
всичко, което трябва да направите е да създадете нов възел с 9,

65
00:04:08,270 --> 00:04:12,290
тел до точка на подходящо място,

66
00:04:12,290 --> 00:04:20,630
и след това ре-тел 8 сочи надолу до 9.

67
00:04:20,630 --> 00:04:25,660
Това е доста бързо, ако знаем къде точно искаме да вмъкнем 9.

68
00:04:25,660 --> 00:04:32,610
Но компромис в замяна на това е, че ние сега сме загубили постоянно времето за достъп

69
00:04:32,610 --> 00:04:36,230
за всеки отделен елемент в структурата на данни.

70
00:04:36,230 --> 00:04:40,950
Например, ако искате да намерите Четвъртият елемент в тази свързан списък,

71
00:04:40,950 --> 00:04:43,510
Аз ще трябва да започне в самото начало на списъка

72
00:04:43,510 --> 00:04:48,930
и да работят по моя начин чрез преброяване възел по възел, докато не намеря четвъртата.

73
00:04:48,930 --> 00:04:55,870
>> За да получите по-добра производителност в сравнение с достъп свързан списък -

74
00:04:55,870 --> 00:04:59,360
но също така да запазят някои от ползите, които сме имали

75
00:04:59,360 --> 00:05:01,800
от гледна точка на вмъкване време от свързан списък -

76
00:05:01,800 --> 00:05:05,750
двоично дърво ще трябва да използвате малко повече памет.

77
00:05:05,750 --> 00:05:11,460
По-специално, вместо просто да има един показалеца в двоичен възел дърво -

78
00:05:11,460 --> 00:05:13,350
като свързан списък възел -

79
00:05:13,350 --> 00:05:16,950
отиваме да добавите втори показалеца на двоичен възел дърво.

80
00:05:16,950 --> 00:05:19,950
Вместо просто да има един указател към следващия елемент,

81
00:05:19,950 --> 00:05:24,420
отиваме да имат показалеца на лявата детето и право дете.

82
00:05:24,420 --> 00:05:26,560
>> Да направи снимка, за да видите какво всъщност прилича.

83
00:05:26,560 --> 00:05:31,350
Отново, аз отивам да се използват тези кутии и стрели.

84
00:05:31,350 --> 00:05:37,150
Двоичен възел дърво ще започнем с едно просто кутия.

85
00:05:37,150 --> 00:05:40,940
Ще има място за стойността,

86
00:05:40,940 --> 00:05:47,280
и след това тя също ще има място за лявата детето и правото на детето.

87
00:05:47,280 --> 00:05:49,280
Отивам да ги обозначават тук.

88
00:05:49,280 --> 00:05:57,560
Отиваме в лявата дете, а след това отиваме да имат право дете.

89
00:05:57,560 --> 00:05:59,920
Има много различни начини за това.

90
00:05:59,920 --> 00:06:02,050
Понякога за простор и удобство,

91
00:06:02,050 --> 00:06:06,460
Всъщност аз ще го изготвя, както аз правя тук на дъното

92
00:06:06,460 --> 00:06:10,910
къде отивам да имат стойност в горната част,

93
00:06:10,910 --> 00:06:14,060
а след това и право дете на долния десен ъгъл,

94
00:06:14,060 --> 00:06:16,060
и лявата дете на долния ляв.

95
00:06:16,060 --> 00:06:20,250
Ако се върнем към това горната диаграма,

96
00:06:20,250 --> 00:06:22,560
имаме стойността на самия връх,

97
00:06:22,560 --> 00:06:25,560
тогава имаме дете показалеца на лявата, а след това ние имаме право дете показалеца.

98
00:06:25,560 --> 00:06:30,110
>> В спецификацията Проблем Set,

99
00:06:30,110 --> 00:06:33,110
говорим за съставяне възел, който е на стойност 7,

100
00:06:33,110 --> 00:06:39,750
а след това и показалеца на лявата дете, което е нулев, и право дете показалеца, че е празно.

101
00:06:39,750 --> 00:06:46,040
Могат да напишат NULL капитал в пространството за

102
00:06:46,040 --> 00:06:51,610
както отляво, детето и правото на дете, или можем да направим тази диагонална черта

103
00:06:51,610 --> 00:06:53,750
през всяка от кутиите, за да покаже, че това е нищожна.

104
00:06:53,750 --> 00:06:57,560
Отивам да направя това само защото е по-лесно.

105
00:06:57,560 --> 00:07:03,700
Това, което виждате тук, са два начина на диаграми един много прост възел двоично дърво

106
00:07:03,700 --> 00:07:07,960
където имаме стойност 7 и нулеви указатели за деца.

107
00:07:07,960 --> 00:07:15,220
>> Във втората част на нашите спецификации говори за това как със свързани списъци -

108
00:07:15,220 --> 00:07:18,270
Не забравяйте, че ние само трябваше да се държи на първия елемент в списък

109
00:07:18,270 --> 00:07:20,270
да си спомня целия списък -

110
00:07:20,270 --> 00:07:26,140
и също така, с двоично дърво, ние само трябва да се държат за показалеца на дървото

111
00:07:26,140 --> 00:07:31,120
за да се запази контрол върху цялата структура на данните.

112
00:07:31,120 --> 00:07:36,150
Този специален елемент на дървото се нарича коренът на дървото.

113
00:07:36,150 --> 00:07:43,360
Например, ако този възел - този възел, съдържащ стойност 7

114
00:07:43,360 --> 00:07:45,500
с нулеви лявото и дясното дете указатели -

115
00:07:45,500 --> 00:07:47,360
са единствената ценност в нашето дърво,

116
00:07:47,360 --> 00:07:50,390
то това ще бъде нашия възел корен.

117
00:07:50,390 --> 00:07:52,240
Това е самото начало на нашето дърво.

118
00:07:52,240 --> 00:07:58,530
Можем да видим това малко по-ясно, след като започнете да добавяте повече възли в нашия дърво.

119
00:07:58,530 --> 00:08:01,510
Остави ме да извадя нова страница.

120
00:08:01,510 --> 00:08:05,000
>> Сега отиваме да се направи дърво, което има 7 в основата,

121
00:08:05,000 --> 00:08:10,920
и 3 вътрешната страна на лявата дете, и 9 вътрешността на правото дете.

122
00:08:10,920 --> 00:08:13,500
Отново, това е доста проста.

123
00:08:13,500 --> 00:08:26,510
Имаме 7, изготвя възел за 3 възел за 9,

124
00:08:26,510 --> 00:08:32,150
и аз ще поставите показалеца на лявата дете от 7 до точка възел, съдържащ 3,

125
00:08:32,150 --> 00:08:37,850
и десния дете показалеца на възела, съдържащ 7 възела, съдържаща девет.

126
00:08:37,850 --> 00:08:42,419
Сега, след три и девет нямат никакви деца,

127
00:08:42,419 --> 00:08:48,500
отиваме да зададете всички указатели на детето им да бъде нула.

128
00:08:48,500 --> 00:08:56,060
Тук основата на нашето дърво съответства на възел, съдържащ броя 7.

129
00:08:56,060 --> 00:09:02,440
Можете да видите, че ако всичко, което имаме е указател, че коренът

130
00:09:02,440 --> 00:09:07,330
тогава ще можем да минеш през нашето дърво и достъп до двете деца възли -

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

132
00:09:10,630 --> 00:09:14,820
Не е необходимо да се поддържа указатели към всеки един възел на дървото.

133
00:09:14,820 --> 00:09:22,080
Добре. Сега отиваме да добавите друг възел за тази схема.

134
00:09:22,080 --> 00:09:25,370
Отиваме да добавите възел, съдържащ 6,

135
00:09:25,370 --> 00:09:34,140
и отиваме да добавите това право дете на възела, съдържаща 3.

136
00:09:34,140 --> 00:09:41,850
За да направите това, аз отивам да изтриете, че нулев указател в 3-възел

137
00:09:41,850 --> 00:09:47,750
и да го преведете да сочи към възел, съдържащ 6. Добре.

138
00:09:47,750 --> 00:09:53,800
>> В този момент, нека да отидем малко на терминологията.

139
00:09:53,800 --> 00:09:58,230
За да започнете, причината, поради която това се нарича двоично дърво по-специално

140
00:09:58,230 --> 00:10:00,460
е, че тя има две деца указатели.

141
00:10:00,460 --> 00:10:06,020
Има и други видове дървета, които имат повече деца указатели.

142
00:10:06,020 --> 00:10:10,930
По-специално, "опита" в Проблем Set 5.

143
00:10:10,930 --> 00:10:19,310
Ще забележите, че в този опит, има 27 различни указатели към различните деца -

144
00:10:19,310 --> 00:10:22,410
по един за всяка от 26-те букви на английската азбука,

145
00:10:22,410 --> 00:10:25,410
и след това 27 за апостроф

146
00:10:25,410 --> 00:10:28,900
така, че е подобен на вида на дървото.

147
00:10:28,900 --> 00:10:34,070
Но тук, тъй като това е двоичен, ние само две детски указатели.

148
00:10:34,070 --> 00:10:37,880
>> В допълнение към този корен възел, който ние говорихме за

149
00:10:37,880 --> 00:10:41,470
ние също се хвърлят около този термин "дете".

150
00:10:41,470 --> 00:10:44,470
Какво означава това за един възел да бъде дете на друг възел?

151
00:10:44,470 --> 00:10:54,060
Това буквално означава, че едно дете възел е дете на друг възел

152
00:10:54,060 --> 00:10:58,760
ако това друго възел има един от своите деца указатели, да сочи към този възел.

153
00:10:58,760 --> 00:11:01,230
За да поставите това в по-конкретен план,

154
00:11:01,230 --> 00:11:11,170
ако 3 се посочва по един на детето указатели на 7, а след това 3 е дете на 7 г.

155
00:11:11,170 --> 00:11:14,510
Ако бяхме да разбера какво са деца на 7 -

156
00:11:14,510 --> 00:11:18,510
добре, ще видим, че 7 има указател към 3 и показалеца до 9,

157
00:11:18,510 --> 00:11:22,190
така 9 и 3 са деца на 7.

158
00:11:22,190 --> 00:11:26,650
Девет няма деца, защото детето указатели са нула,

159
00:11:26,650 --> 00:11:30,940
и 3 има само едно дете, 6.

160
00:11:30,940 --> 00:11:37,430
Шест няма деца, защото и двете на своите указатели са нула, което ние ще направим точно сега.

161
00:11:37,430 --> 00:11:45,010
>> Освен това, ние говорим за родителите на даден възел,

162
00:11:45,010 --> 00:11:51,100
и това е, както можете да очаквате, обратната страна на това дете описание.

163
00:11:51,100 --> 00:11:58,620
Всеки възел има само един родител - вместо две, както можете да очаквате с хората.

164
00:11:58,620 --> 00:12:03,390
Например, майка на три е 7.

165
00:12:03,390 --> 00:12:10,800
Майка на 9 е 7, и майка на 6 е 3. Не е много.

166
00:12:10,800 --> 00:12:15,720
Ние също имаме условия да се говори за баби и дядовци и внуци,

167
00:12:15,720 --> 00:12:18,210
и по-общо говорим за предците

168
00:12:18,210 --> 00:12:20,960
и потомците на даден възел.

169
00:12:20,960 --> 00:12:25,710
Прародител на възел или предци, а по-скоро на възел -

170
00:12:25,710 --> 00:12:32,730
са всички възли, които се намират по пътя от корена до този възел.

171
00:12:32,730 --> 00:12:36,640
Например, ако аз съм на възела, 6,

172
00:12:36,640 --> 00:12:46,430
предците ще бъдат 3 и 7.

173
00:12:46,430 --> 00:12:55,310
Предшествениците на 9, например, - но ако ме търсите на възела, 9 -

174
00:12:55,310 --> 00:12:59,990
прародител на 9 е само на 7.

175
00:12:59,990 --> 00:13:01,940
И потомци са точно обратното.

176
00:13:01,940 --> 00:13:05,430
Ако аз искам да гледам на всички потомци на 7,

177
00:13:05,430 --> 00:13:11,020
тогава трябва да разгледаме всички възли под него.

178
00:13:11,020 --> 00:13:16,950
Така че, имам 3, 9 и 6 всичко като потомци на 7.

179
00:13:16,950 --> 00:13:24,170
>> Крайният срок за която ще поговорим за това е идеята на братя и сестри.

180
00:13:24,170 --> 00:13:27,980
Братя и сестри - вид заедно по въпроса с тези условия -

181
00:13:27,980 --> 00:13:33,150
са възли, които са на същото ниво в дървото.

182
00:13:33,150 --> 00:13:42,230
Така че, 3 и 9 са братя и сестри, защото те са на същото ниво в дървото.

183
00:13:42,230 --> 00:13:46,190
И двамата имат една и съща майка, 7.

184
00:13:46,190 --> 00:13:51,400
6 все още няма братя и сестри, защото 9 не са изпитали някакви деца.

185
00:13:51,400 --> 00:13:55,540
И 7 не са изпитали някакви братя и сестри, защото това е основата на нашето дърво,

186
00:13:55,540 --> 00:13:59,010
и има само 1 корен.

187
00:13:59,010 --> 00:14:02,260
За 7 да имат братя и сестри там би трябвало да бъде възел над 7.

188
00:14:02,260 --> 00:14:07,480
Ще трябва да бъде майка на 7, в който случай 7 вече няма да бъде в корените на дървото.

189
00:14:07,480 --> 00:14:10,480
След тази нова майка на 7 също би трябвало да имат дете,

190
00:14:10,480 --> 00:14:16,480
и че детето ще бъде сестра на 7.

191
00:14:16,480 --> 00:14:21,040
>> Добре. Нека продължим.

192
00:14:21,040 --> 00:14:24,930
Когато започнахме нашата дискусия за двоични дървета,

193
00:14:24,930 --> 00:14:28,790
ние говорихме за това, как щяхме да ги използвате, за да

194
00:14:28,790 --> 00:14:32,800
получат предимство пред двата масива и свързани списъци.

195
00:14:32,800 --> 00:14:37,220
И начина, по който започваш да се направи, че е с това поръчване имот.

196
00:14:37,220 --> 00:14:41,080
Ние казваме, че е наредено двоично дърво, в съответствие със спецификацията,

197
00:14:41,080 --> 00:14:45,740
ако за всеки възел в нашето дърво, на неговите потомци от лявата -

198
00:14:45,740 --> 00:14:48,670
отляво детето и всички потомци на лявата детето -

199
00:14:48,670 --> 00:14:54,510
са по-малко ценности, както и всички възли в дясно -

200
00:14:54,510 --> 00:14:57,770
правото детето и всички потомци на правото на детето -

201
00:14:57,770 --> 00:15:02,800
имат възли, по-големи от стойността на текущия възел, че ние не търсим на.

202
00:15:02,800 --> 00:15:07,850
Само за простота, ние ще приемем, че няма никакви дублиращи се възли в нашето дърво.

203
00:15:07,850 --> 00:15:11,180
Например, в това дърво ние не отиваме да се занимава със случая

204
00:15:11,180 --> 00:15:13,680
където имаме стойност 7 в основата

205
00:15:13,680 --> 00:15:16,720
 и след това ние също имаме на стойност 7 другаде в дървото.

206
00:15:16,720 --> 00:15:24,390
В този случай, вие ще забележите, че това дърво е наистина осъден.

207
00:15:24,390 --> 00:15:26,510
Имаме стойност 7 в корена.

208
00:15:26,510 --> 00:15:29,720
Всичко в ляво от 7 -

209
00:15:29,720 --> 00:15:35,310
ако отмените всички тези малки марки -

210
00:15:35,310 --> 00:15:40,450
всичко в ляво от 7 - 3 и 6 -

211
00:15:40,450 --> 00:15:49,410
тези стойности са на по-малко от 7, и всичко в дясно - което е точно това 9 -

212
00:15:49,410 --> 00:15:53,450
е по-голяма от 7.

213
00:15:53,450 --> 00:15:58,650
>> Това не е само наредено дърво, съдържащи тези стойности,

214
00:15:58,650 --> 00:16:03,120
но нека се направи още няколко от тях.

215
00:16:03,120 --> 00:16:05,030
Налице е всъщност един куп начини, по които можем да направим това.

216
00:16:05,030 --> 00:16:09,380
Отивам да се използва стенография, само за да запазим нещата прости, където -

217
00:16:09,380 --> 00:16:11,520
, отколкото цялата кутии и стрели -

218
00:16:11,520 --> 00:16:14,220
Аз съм просто ще направят номера и стрелки, които ги свързват.

219
00:16:14,220 --> 00:16:22,920
За да започнете, ние просто ще напишем отново оригиналния дърво, където имахме 7, и след това 3,

220
00:16:22,920 --> 00:16:25,590
и след това три посочи надясно до 6,

221
00:16:25,590 --> 00:16:30,890
и 7 имали право дете, което беше 9.

222
00:16:30,890 --> 00:16:33,860
Добре. Какво е друг начин, по който би могъл да напише това дърво?

223
00:16:33,860 --> 00:16:38,800
Вместо да се налага 3 лявата дете на 7

224
00:16:38,800 --> 00:16:41,360
ние също може да има 6 лявата дете на 7,

225
00:16:41,360 --> 00:16:44,470
и след това три лявата дете на 6.

226
00:16:44,470 --> 00:16:48,520
Това ще изглежда като това дърво точно тук, където имам 7,

227
00:16:48,520 --> 00:16:57,860
след шест, а след това 3 и 9 на правото.

228
00:16:57,860 --> 00:17:01,490
Ние също така не трябва да има 7, както коренът ни.

229
00:17:01,490 --> 00:17:03,860
Ние също може да има 6, тъй като нашата коренът.

230
00:17:03,860 --> 00:17:06,470
Какво би изглеждало това?

231
00:17:06,470 --> 00:17:09,230
Ако ще да се запази тази поръча имот,

232
00:17:09,230 --> 00:17:12,970
всичко ляво на 6 трябва да бъде по-малко, отколкото.

233
00:17:12,970 --> 00:17:16,540
Има само една възможност и това е 3.

234
00:17:16,540 --> 00:17:19,869
Но тогава, както и право дете на 6, имаме две възможности.

235
00:17:19,869 --> 00:17:25,380
Първо, ние може да има 7 и 9,

236
00:17:25,380 --> 00:17:28,850
или можем да го изготви, като аз съм на път да направя тук -

237
00:17:28,850 --> 00:17:34,790
където имаме 9 правото дете на 6,

238
00:17:34,790 --> 00:17:39,050
и след това 7 като лявата дете на 9.

239
00:17:39,050 --> 00:17:44,240
>> Сега, 7 и 6 не са единствените възможни стойности за корена.

240
00:17:44,240 --> 00:17:50,200
Ние също може да има 3 да бъде в основата.

241
00:17:50,200 --> 00:17:52,240
Какво се случва, ако 3 е в основата?

242
00:17:52,240 --> 00:17:54,390
Тук нещата стават малко по-интересно.

243
00:17:54,390 --> 00:17:58,440
Три не са изпитали някакви стойности, които са по-малко, отколкото,

244
00:17:58,440 --> 00:18:02,070
така че цялата лява страна на дървото е просто ще бъде нула.

245
00:18:02,070 --> 00:18:03,230
Не щеше да бъде нещо там.

246
00:18:03,230 --> 00:18:07,220
В дясно, бихме могли да изброят неща във възходящ ред.

247
00:18:07,220 --> 00:18:15,530
Ние може да има 3, след 6, 7, а след това 9.

248
00:18:15,530 --> 00:18:26,710
Или, бихме могли да направим три, а след това шест, а след това девет, след това 7.

249
00:18:26,710 --> 00:18:35,020
Или, бихме могли да направим 3, 7, 6, след това 9.

250
00:18:35,020 --> 00:18:40,950
Или, 3, 7 - всъщност не, ние не може да направи седем повече.

251
00:18:40,950 --> 00:18:43,330
Това е нашата едно нещо там.

252
00:18:43,330 --> 00:18:54,710
Ние можем да направим 9, и след това от 9 можем да направим 6 и 7.

253
00:18:54,710 --> 00:19:06,980
Или можем да направим три, а след това девет, а след това 7, и след това 6.

254
00:19:06,980 --> 00:19:12,490
>> Едно нещо е да привлека вниманието ви тук е

255
00:19:12,490 --> 00:19:14,510
, че тези дървета са малко странно изглеждащ.

256
00:19:14,510 --> 00:19:17,840
По-специално, ако се вгледаме в четири дървета от дясната страна -

257
00:19:17,840 --> 00:19:20,930
Ще ги обикаля, тук -

258
00:19:20,930 --> 00:19:28,410
тези дървета изглеждат почти точно като свързан списък.

259
00:19:28,410 --> 00:19:32,670
Всеки възел има само едно дете,

260
00:19:32,670 --> 00:19:38,950
и затова не е нужно на тази дървовидна структура, която виждаме, например,

261
00:19:38,950 --> 00:19:44,720
 в това самотно дърво тук в долния ляв.

262
00:19:44,720 --> 00:19:52,490
Тези дървета са всъщност се нарича изродена двоични дървета,

263
00:19:52,490 --> 00:19:54,170
и ние ще говорим за тях повече в бъдеще -

264
00:19:54,170 --> 00:19:56,730
особено, ако отидете да предприемат други курсове по компютърни науки.

265
00:19:56,730 --> 00:19:59,670
Тези дървета са изродени.

266
00:19:59,670 --> 00:20:03,780
Те не са много полезни, защото, наистина, тази структура се поддава

267
00:20:03,780 --> 00:20:08,060
 да се намери пъти, подобни на тази на свързан списък.

268
00:20:08,060 --> 00:20:13,050
Ние не се получи да се възползват от допълнителната памет - това допълнително показалеца -

269
00:20:13,050 --> 00:20:18,840
защото от нашата структура е лошо по този начин.

270
00:20:18,840 --> 00:20:24,700
Вместо да продължи и изтеглете двоичните дървета, които са 9 в основата,

271
00:20:24,700 --> 00:20:27,220
е крайният случай, че щяхме да имаме,

272
00:20:27,220 --> 00:20:32,380
вместо това, ние сме в този момент, ще поговорим малко за този план

273
00:20:32,380 --> 00:20:36,150
, които ние използваме, когато говорим за дървета, която се нарича височина.

274
00:20:36,150 --> 00:20:45,460
>> Височината на дървото е разстоянието от корена до най-далечната възел,

275
00:20:45,460 --> 00:20:48,370
или по-скоро броя на отсечките, които ще трябва да се направи, за да

276
00:20:48,370 --> 00:20:53,750
започне от корена и след това до края на най-далечен възел в дървото.

277
00:20:53,750 --> 00:20:57,330
Ако се вгледаме в някои от тези дървета, които сме привлечени тук,

278
00:20:57,330 --> 00:21:07,870
можем да видим, че ако вземем това дърво в горния ляв ъгъл и ние започваме в 3

279
00:21:07,870 --> 00:21:14,510
тогава ние трябва да направим едно хопа, за да стигнем до 6, втората хопа, за да стигнем до 7,

280
00:21:14,510 --> 00:21:20,560
и 1/3 хопа, за да стигнем до 9.

281
00:21:20,560 --> 00:21:26,120
Така че, височината на това дърво е 3.

282
00:21:26,120 --> 00:21:30,640
Ние можем да направим същото упражнение за другите дървета, очертани с този зелен

283
00:21:30,640 --> 00:21:40,100
и виждаме, че височината на всички тези дървета е наистина 3.

284
00:21:40,100 --> 00:21:45,230
Това е част от това, което ги кара да се изроди -

285
00:21:45,230 --> 00:21:53,750
че височината им е само една по-малко от броя на възлите в цялото дърво.

286
00:21:53,750 --> 00:21:58,400
Ако се вгледаме в това друго дърво, което е обграден с червено, от друга страна,

287
00:21:58,400 --> 00:22:03,920
ние виждаме, че най-далечните листа възли са на 6 и 9 -

288
00:22:03,920 --> 00:22:06,940
листата на тези възли, които нямат деца.

289
00:22:06,940 --> 00:22:11,760
Така че, за да получите от коренът или 6 или 9,

290
00:22:11,760 --> 00:22:17,840
ние трябва да направим един хопа, за да стигнем до 7, а след това и втория хопа, за да стигнем до 9,

291
00:22:17,840 --> 00:22:21,240
и също така, само секунда хоп от 7 на 6.

292
00:22:21,240 --> 00:22:29,080
Така че, височината на това дърво тук е само 2.

293
00:22:29,080 --> 00:22:35,330
Можете да се върнете и да направи това за всички други дървета, които преди обсъдиха

294
00:22:35,330 --> 00:22:37,380
започващи със 7 и 6,

295
00:22:37,480 --> 00:22:42,500
и вие ще откриете, че височината на всички тези дървета е 2.

296
00:22:42,500 --> 00:22:46,320
>> Причина ние сме били говорим за наредил двоични дървета

297
00:22:46,320 --> 00:22:50,250
и защо те са готино е така, защото можете да търсите чрез тях в

298
00:22:50,250 --> 00:22:53,810
по подобен начин за търсене над сортиран масив.

299
00:22:53,810 --> 00:22:58,720
Това е мястото, където ние говорим за получаване, че по-доброто време за търсене

300
00:22:58,720 --> 00:23:02,730
над прост свързан списък.

301
00:23:02,730 --> 00:23:05,010
С свързан списък - ако искате да намерите конкретен елемент

302
00:23:05,010 --> 00:23:07,470
сте най-добрия случай ще направя някакъв вид на линейно търсене

303
00:23:07,470 --> 00:23:10,920
, където можете започват в началото на списъка и хоп един по един -

304
00:23:10,920 --> 00:23:12,620
един възел от един възел -

305
00:23:12,620 --> 00:23:16,060
през целия списък, докато не намерите всичко, което търсите за.

306
00:23:16,060 --> 00:23:19,440
Като има предвид, че ако имате двоично дърво, което се съхранява в тази хубава формат,

307
00:23:19,440 --> 00:23:23,300
всъщност можете да получите повече от двоично търсене

308
00:23:23,300 --> 00:23:25,160
, където можете разделяй и владей

309
00:23:25,160 --> 00:23:29,490
и търсене чрез съответната половина на дървото при всяка стъпка.

310
00:23:29,490 --> 00:23:32,840
Нека да видим как работи.

311
00:23:32,840 --> 00:23:38,850
>> Ако имаме отново, връщайки се към първоначалното ни дърво -

312
00:23:38,850 --> 00:23:46,710
започне в 7, имаме 3 в ляво, 9 от дясната страна,

313
00:23:46,710 --> 00:23:51,740
и под 3 имаме 6.

314
00:23:51,740 --> 00:24:01,880
Ако искаме да търсите под номер 6 в това дърво, щяхме да започне в корена.

315
00:24:01,880 --> 00:24:08,910
Бихме се сравни стойността търсим, да речем 6,

316
00:24:08,910 --> 00:24:12,320
на стойност, съхранявана в възел, който сме в момента търси, 7,

317
00:24:12,320 --> 00:24:21,200
откриете, че 6 е наистина по-малко от 7, така че ние бихме се придвижите наляво.

318
00:24:21,200 --> 00:24:25,530
Ако стойността на шест е бил по-голям от 7, бихме вместо това преместен в дясно.

319
00:24:25,530 --> 00:24:29,770
Тъй като ние знаем, че се дължи на структурата на поръчаните двоично дърво -

320
00:24:29,770 --> 00:24:33,910
всички стойности по-малко от 7 ще се съхраняват в ляво от 7

321
00:24:33,910 --> 00:24:40,520
няма нужда да се притеснява дори през дясната страна на дървото.

322
00:24:40,520 --> 00:24:43,780
След като ние се движат в ляво и сега сме на възела, съдържаща 3,

323
00:24:43,780 --> 00:24:48,110
можем да направим това отново същото сравнение, когато ние сравняваме 3 и 6.

324
00:24:48,110 --> 00:24:52,430
И ние откриваме, че докато 6 - стойността търсим - е по-голяма от 3,

325
00:24:52,430 --> 00:24:58,580
можем да отидем към дясната страна на възела, съдържаща 3.

326
00:24:58,580 --> 00:25:02,670
Не е лявата страна, така че биха могли да игнорират.

327
00:25:02,670 --> 00:25:06,510
Но ние знаем само това, защото ние търсим в самото дърво,

328
00:25:06,510 --> 00:25:08,660
и можем да видим, че дървото няма деца.

329
00:25:08,660 --> 00:25:13,640
>> То също е доста лесно да търсите шест в това дърво, ако ние сме си го прави като хората,

330
00:25:13,640 --> 00:25:16,890
но нека да следи този процес механично като компютър ще направя

331
00:25:16,890 --> 00:25:18,620
наистина да разберем алгоритъма.

332
00:25:18,620 --> 00:25:26,200
В този момент, ние сме вече на възел, който съдържа 6

333
00:25:26,200 --> 00:25:29,180
и ние не търсим за стойност 6,

334
00:25:29,180 --> 00:25:31,740
така, наистина, ние открихме подходящия възел.

335
00:25:31,740 --> 00:25:35,070
Намерихме стойност 6 в нашето дърво, и ние можем да спрем нашето търсене.

336
00:25:35,070 --> 00:25:37,330
В този момент, в зависимост от това какво се случва,

337
00:25:37,330 --> 00:25:41,870
можем да кажем, да, ние сме намерили стойност 6, тя съществува в нашето дърво.

338
00:25:41,870 --> 00:25:47,640
Или, ако планирате да вмъкнете възел или направи нещо, можем да направим това в този момент.

339
00:25:47,640 --> 00:25:53,010
>> Нека да направим още няколко заявки само за да видя как работи това.

340
00:25:53,010 --> 00:25:59,390
Нека да погледнем какво се случва, ако бяхме да се опитаме и да потърсите на стойност 10.

341
00:25:59,390 --> 00:26:02,970
Ако трябва да гледам на стойност 10, ние ще почнем към корена.

342
00:26:02,970 --> 00:26:07,070
Ние ще видите, че 10 е по-голямо от 7, така че ние ще се премести надясно.

343
00:26:07,070 --> 00:26:13,640
, Че ще стигнем до 9 и сравни 9 до 10 и да видим, че девет е наистина по-малко от 10.

344
00:26:13,640 --> 00:26:16,210
Така че отново ще се опита да се движи надясно.

345
00:26:16,210 --> 00:26:20,350
Но в този момент, ние ще забележите, че ние сме на нула възел.

346
00:26:20,350 --> 00:26:23,080
Там няма нищо. Няма нищо, при които 10 трябва да бъде.

347
00:26:23,080 --> 00:26:29,360
Това е мястото, където можем да докладва недостатъчност - че наистина няма 10 в дървото.

348
00:26:29,360 --> 00:26:35,420
И накрая, нека да минем през случаите, когато ние се опитваме да погледнете една в дървото.

349
00:26:35,420 --> 00:26:38,790
Това е подобно на това, което се случва, ако погледнем 10, с изключение вместо да ходят в дясно,

350
00:26:38,790 --> 00:26:41,260
ние ще тръгнем наляво.

351
00:26:41,260 --> 00:26:46,170
Започваме в 7 и се види, че 1 е по-малко от 7, така че ние се движат наляво.

352
00:26:46,170 --> 00:26:51,750
Качваме се на 3 и се види, че 1 е по-малко от три, така че отново ние се опитваме да се движат наляво.

353
00:26:51,750 --> 00:26:59,080
В този момент ние имаме нулева възел, така че отново можем да докладва недостатъчност.

354
00:26:59,080 --> 00:27:10,260
>> Ако искате да научите повече за двоични дървета,

355
00:27:10,260 --> 00:27:14,420
има цял куп забавни малки проблеми, които можете да направите с тях.

356
00:27:14,420 --> 00:27:19,450
Предлагам практикуване на изготвянето на тези диаграми една по една

357
00:27:19,450 --> 00:27:21,910
и след през всички на различните стъпки,

358
00:27:21,910 --> 00:27:25,060
защото това ще дойде в супер-удобен

359
00:27:25,060 --> 00:27:27,480
не само, когато правиш набор Huffman кодиране проблем

360
00:27:27,480 --> 00:27:29,390
но също така и в бъдещи курсове -

361
00:27:29,390 --> 00:27:32,220
просто се научите как да се направи на тези структури от данни и мисля, че през проблемите

362
00:27:32,220 --> 00:27:38,000
с писалка и хартия, или в този случай, IPAD и стилус.

363
00:27:38,000 --> 00:27:41,000
>> В този момент обаче, ние ще продължим да се направят някои кодиране практика

364
00:27:41,000 --> 00:27:44,870
и всъщност играят с тези бинарни дървета и ще видите.

365
00:27:44,870 --> 00:27:52,150
Отивам да се върнете към моя компютър.

366
00:27:52,150 --> 00:27:58,480
За тази част на раздела, вместо да използвате CS50 Run или CS50 пространства,

367
00:27:58,480 --> 00:28:01,500
Отивам да използвате уреда.

368
00:28:01,500 --> 00:28:04,950
>> След като заедно със спецификацията Проблем Set

369
00:28:04,950 --> 00:28:07,740
Виждам, че аз трябва да отворите уреда,

370
00:28:07,740 --> 00:28:11,020
преминете към моята папка Dropbox, създайте папка, наречена раздел 7,

371
00:28:11,020 --> 00:28:15,730
и след това да създадете файл, наречен binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Ето ни. Имам уреда вече е отворен.

373
00:28:22,050 --> 00:28:25,910
Аз ще дръпне един терминал.

374
00:28:25,910 --> 00:28:38,250
Отивам да отидете в папката Dropbox директория, наречена section7

375
00:28:38,250 --> 00:28:42,230
и да видите, че е напълно празна.

376
00:28:42,230 --> 00:28:48,860
Сега аз ще да се отворят binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Добре. Ето ни - празен файл.

378
00:28:51,750 --> 00:28:54,330
>> Нека се върнем към спецификацията.

379
00:28:54,330 --> 00:28:59,850
Спецификацията иска да създаде ново определение на типа

380
00:28:59,850 --> 00:29:03,080
за двоичен възел дърво, съдържащ INT стойности -

381
00:29:03,080 --> 00:29:07,110
точно като ценности, които извади в нашата диаграми преди.

382
00:29:07,110 --> 00:29:11,740
Отиваме да използвате тази стереотипния typedef, че ние сме направили тук

383
00:29:11,740 --> 00:29:14,420
че трябва да се признае от Проблем Set 5 -

384
00:29:14,420 --> 00:29:19,190
ако си направил хеш таблица на завладяването на правопис програма.

385
00:29:19,190 --> 00:29:22,540
Вие също трябва да го признае от раздел миналата седмица

386
00:29:22,540 --> 00:29:23,890
където говорихме за свързани списъци.

387
00:29:23,890 --> 00:29:27,870
Имаме тази typedef на структурата на възел,

388
00:29:27,870 --> 00:29:34,430
и сме създали тази структура възел името на структурата възел предварително

389
00:29:34,430 --> 00:29:39,350
така че тогава ще можем да се отнасят към него, тъй като ще искат да имат указатели възел структура

390
00:29:39,350 --> 00:29:45,740
като част от нашата структура, но ние сме обграден това -

391
00:29:45,740 --> 00:29:47,700
или по-скоро, ограден това - в typedef

392
00:29:47,700 --> 00:29:54,600
, така че по-късно в кода, може да се отнася за тази структура просто като възел вместо структура възел.

393
00:29:54,600 --> 00:30:03,120
>> Това ще бъде много подобен на самостоятелно свързан списък определение, че видяхме миналата седмица.

394
00:30:03,120 --> 00:30:20,070
За да направите това, нека просто да започнете с писането на стереотипния.

395
00:30:20,070 --> 00:30:23,840
Ние знаем, че трябва да имаме целочислена стойност,

396
00:30:23,840 --> 00:30:32,170
така че ние ще поставим в INT стойност, а след това вместо да се налага само един указател към следващия елемент -

397
00:30:32,170 --> 00:30:33,970
както направихме с поединично свързани списъци -

398
00:30:33,970 --> 00:30:38,110
отиваме да има леви и десни указатели на детето.

399
00:30:38,110 --> 00:30:42,880
Това е доста проста - структура възел * левия дете;

400
00:30:42,880 --> 00:30:51,190
и структура възел * право дете. Cool.

401
00:30:51,190 --> 00:30:54,740
Това изглежда доста добро начало.

402
00:30:54,740 --> 00:30:58,530
Нека се върнем към спецификацията.

403
00:30:58,530 --> 00:31:05,030
>> Сега ние трябва да обяви глобална променлива * възел за корените на едно дърво.

404
00:31:05,030 --> 00:31:10,590
Започваш да се направи тази глобална точно както ние направихме първото показалеца в свързани нашия списък също толкова глобален.

405
00:31:10,590 --> 00:31:12,690
Това е така, че във функциите, които пишем

406
00:31:12,690 --> 00:31:16,180
ние не трябва да минава около този корен -

407
00:31:16,180 --> 00:31:19,620
въпреки че ние ще видите, че ако искаш да напиша тези функции рекурсивно,

408
00:31:19,620 --> 00:31:22,830
тя може да бъде по-добре дори да не го Заобикаля като глобален на първо място

409
00:31:22,830 --> 00:31:28,090
и вместо него се инициализира място в основната си функция.

410
00:31:28,090 --> 00:31:31,960
Но ние ще го направим в световен мащаб да се започне.

411
00:31:31,960 --> 00:31:39,920
Отново, ние ще дадем няколко места, и аз отивам да обяви възел * корен.

412
00:31:39,920 --> 00:31:46,770
Просто за да се уверите, че не оставите това неинициализирана, аз отивам да го определя като равна на нула.

413
00:31:46,770 --> 00:31:52,210
Сега, в основна функция - които ние ще напиша много бързо точно тук -

414
00:31:52,210 --> 00:32:00,450
INT главната (INT argc, Const знак * argv []) -

415
00:32:00,450 --> 00:32:10,640
и аз отивам да започне да обявява argv ми масив като строителство, така че аз знам

416
00:32:10,640 --> 00:32:14,550
че тези доводи са аргументи, които вероятно не искате да модифицирате.

417
00:32:14,550 --> 00:32:18,390
Ако искам да ги променяте, може би трябва да се направи копия от тях.

418
00:32:18,390 --> 00:32:21,740
Ще видите много код.

419
00:32:21,740 --> 00:32:25,440
Това е глоба или иначе. Това е добре да го оставите като пропуска на строителство, ако искате.

420
00:32:25,440 --> 00:32:28,630
Аз обикновено го сложи в просто така, че си напомням

421
00:32:28,630 --> 00:32:33,650
 , че вероятно не искате да промените тези аргументи.

422
00:32:33,650 --> 00:32:39,240
>> Както винаги, аз отивам да се включи тази връщането на 0 линия в края на основната.

423
00:32:39,240 --> 00:32:45,730
Ето, аз ще се инициализира моя възел корен.

424
00:32:45,730 --> 00:32:48,900
Както стоят нещата сега, имам указател, който присвоява

425
00:32:48,900 --> 00:32:52,970
така че се посочи нищо.

426
00:32:52,970 --> 00:32:57,480
За да започне изграждането на възела,

427
00:32:57,480 --> 00:32:59,250
Първо трябва да заделя памет за него.

428
00:32:59,250 --> 00:33:05,910
Отивам да направите това, като памет на купчината с помощта на изчистване.

429
00:33:05,910 --> 00:33:10,660
Отивам да зададете корен равен резултат от изчистване,

430
00:33:10,660 --> 00:33:19,550
и аз отивам да използвате sizeof оператора да изчисли размера на възел.

431
00:33:19,550 --> 00:33:24,990
Причината, поради която аз използвам sizeof възел, за разлика от, да речем,

432
00:33:24,990 --> 00:33:37,020
прави нещо подобно - изчистване (4 + 4 +4) или изчистване 12 -

433
00:33:37,020 --> 00:33:40,820
е, защото искам да ми код да бъде възможно най-съвместими.

434
00:33:40,820 --> 00:33:44,540
Искам да бъда в състояние да вземе в файл, да го компилирате на уреда,

435
00:33:44,540 --> 00:33:48,820
и след това да го събират на моя 64-битова Mac -

436
00:33:48,820 --> 00:33:52,040
или за напълно различна архитектура -

437
00:33:52,040 --> 00:33:54,640
и аз искам всичко това да работят по същия.

438
00:33:54,640 --> 00:33:59,510
>> Ако правя предположения за размера на променливи -

439
00:33:59,510 --> 00:34:02,070
размер на вътр или размера на показалеца -

440
00:34:02,070 --> 00:34:06,070
тогава аз също се правят предположения за вида на архитектури

441
00:34:06,070 --> 00:34:10,440
, на която моя код може успешно да съставят, когато тичам.

442
00:34:10,440 --> 00:34:15,030
Винаги използвайте sizeof, за разлика от ръчно сумиране на структурата на полета.

443
00:34:15,030 --> 00:34:20,500
Другата причина е, че може да има и подложка че компилаторът поставя в структурата.

444
00:34:20,500 --> 00:34:26,570
Дори само сумиране на отделните полета, не е нещо, което обикновено искате да направите,

445
00:34:26,570 --> 00:34:30,340
така, изтрийте тази линия.

446
00:34:30,340 --> 00:34:33,090
Сега, наистина да се инициализира този възел корен,

447
00:34:33,090 --> 00:34:36,489
Аз ще трябва да се включи в стойности за всяка от различните му области.

448
00:34:36,489 --> 00:34:41,400
Например, за стойност Знам, че искате да се инициализира 7,

449
00:34:41,400 --> 00:34:46,920
и за сега отивам да настроите ляво детето да бъде нула

450
00:34:46,920 --> 00:34:55,820
и правото на детето да бъде нула. Чудесно!

451
00:34:55,820 --> 00:35:02,670
Ние сме направили тази част от спецификациите.

452
00:35:02,670 --> 00:35:07,390
>> Спецификацията в долната част на страницата 3 ме пита за създаване на още три възли

453
00:35:07,390 --> 00:35:10,600
съдържа 3, съдържащ 6, и с 9 -

454
00:35:10,600 --> 00:35:14,210
и след това да ги свържем, така че тя изглежда точно като нашето дърво диаграма

455
00:35:14,210 --> 00:35:17,120
, че ние говорим за това по-рано.

456
00:35:17,120 --> 00:35:20,450
Да го направим доста бързо тук.

457
00:35:20,450 --> 00:35:26,270
Ще видите много бързо, че аз отивам да започнете да пишете куп от дублиране на кода.

458
00:35:26,270 --> 00:35:32,100
Отивам да се създаде възел *, и аз отивам да го три.

459
00:35:32,100 --> 00:35:36,000
Отивам да го зададете равен на изчистване (sizeof (възел)).

460
00:35:36,000 --> 00:35:41,070
Отивам да се определят три стойност = 3.

461
00:35:41,070 --> 00:35:54,780
Три -> left_child = NULL, три -> дясно _child = NULL;, както добре.

462
00:35:54,780 --> 00:36:01,150
Това изглежда доста подобен за инициализиране на корен, и това е точно това, което

463
00:36:01,150 --> 00:36:05,760
Аз ще трябва да направя, ако започне инициализиране на 6 и 9, както и.

464
00:36:05,760 --> 00:36:20,720
Аз ще направя това наистина бързо тук - всъщност, аз отивам да направя малко копиране и поставяне,

465
00:36:20,720 --> 00:36:46,140
и се уверете, че аз - добре.

466
00:36:46,470 --> 00:37:09,900
 Сега, аз имам да го копира и мога да отида напред и да зададете тази равно на 6.

467
00:37:09,900 --> 00:37:14,670
Можете да видите, че това отнема известно време и не е супер-ефективна.

468
00:37:14,670 --> 00:37:22,610
Само малко, ние ще напиша функция, която ще направи това за нас.

469
00:37:22,610 --> 00:37:32,890
Искам да се замени с 9, сменете с 6.

470
00:37:32,890 --> 00:37:37,360
>> Сега имаме всички наши възли създаден и се инициализира.

471
00:37:37,360 --> 00:37:41,200
Имаме корена ни, равен на 7, или съдържащи стойност 7,

472
00:37:41,200 --> 00:37:46,510
нашата възел съдържа 3, възел съдържащ 6, и нашата възел с 9.

473
00:37:46,510 --> 00:37:50,390
В този момент, всичко, което трябва да направим, е да тел всичко.

474
00:37:50,390 --> 00:37:53,020
Причината, поради която инициализира всички указатели към нула е точно, така че съм сигурен, че

475
00:37:53,020 --> 00:37:56,260
Аз не разполагат с никакви неинициализирани указатели там случайно.

476
00:37:56,260 --> 00:38:02,290
И също така, тъй като, в този момент, аз само трябва да свържете възлите един към друг -

477
00:38:02,290 --> 00:38:04,750
за тези, които те действително свързани с, че не е нужно да отидете и да

478
00:38:04,750 --> 00:38:08,240
сигурни, че всички нули на подходящите места.

479
00:38:08,240 --> 00:38:15,630
>> Започвайки в основата, знам, че лявата детето корен е 3.

480
00:38:15,630 --> 00:38:21,250
Знам, че правото на детето корен е 9.

481
00:38:21,250 --> 00:38:24,880
След това, единственото друго дете, което ми е останало да се притеснявате за

482
00:38:24,880 --> 00:38:39,080
е право дете на 3, което е с 6.

483
00:38:39,080 --> 00:38:44,670
В този момент, всичко това изглежда доста добре.

484
00:38:44,670 --> 00:38:54,210
Ще изтриете някои от тези линии.

485
00:38:54,210 --> 00:38:59,540
Сега всичко изглежда доста добре.

486
00:38:59,540 --> 00:39:04,240
Нека се върнем към нашата спецификация и да видим това, което ние трябва да направим следващата.

487
00:39:04,240 --> 00:39:07,610
>> В този момент, ние трябва да напишете функция, наречена "съдържа"

488
00:39:07,610 --> 00:39:14,150
с прототип на "BOOL съдържа (INT стойност).

489
00:39:14,150 --> 00:39:17,060
И това съдържа функция ще се върне вярно

490
00:39:17,060 --> 00:39:21,200
 ако дървото посочи от нашата глобална променлива на корен

491
00:39:21,200 --> 00:39:26,950
 съдържа стойността премина в функцията и лъжа в противен случай.

492
00:39:26,950 --> 00:39:29,000
Да вървим напред и да направим.

493
00:39:29,000 --> 00:39:35,380
Това ще бъде точно като справка, че ние направихме от страна на IPAD само преди малко.

494
00:39:35,380 --> 00:39:40,130
Да я увеличите малко и превъртете нагоре.

495
00:39:40,130 --> 00:39:43,130
Отиваме да се сложи тази функция точно над нашата основна функция

496
00:39:43,130 --> 00:39:48,990
така че не е нужно да правите всякакъв вид създаване на прототипи.

497
00:39:48,990 --> 00:39:55,960
Така че, булев съдържа (INT стойност).

498
00:39:55,960 --> 00:40:00,330
Точно така. Има нашата стереотипния декларация.

499
00:40:00,330 --> 00:40:02,900
Просто за да се уверите, че това ще се компилира,

500
00:40:02,900 --> 00:40:06,820
Отивам да вървим напред и просто го определя като равна на връщане фалшиви.

501
00:40:06,820 --> 00:40:09,980
В момента тази функция не ще направи нищо и винаги съобщават, че

502
00:40:09,980 --> 00:40:14,010
стойност, която търсим, не е в дървото.

503
00:40:14,010 --> 00:40:16,280
>> В този момент, това е може би добра идея -

504
00:40:16,280 --> 00:40:19,600
тъй като ние сме написал куп код и ние дори не се опитахме го тества още

505
00:40:19,600 --> 00:40:22,590
за да се уверите, че всичко това се съставя.

506
00:40:22,590 --> 00:40:27,460
Има няколко неща, които трябва да направите, за да се уверите, че това действително ще съставят.

507
00:40:27,460 --> 00:40:33,530
Първо, да видим дали ние сме били използване на каквито и да било функции в библиотеки, които ние все още не са включени.

508
00:40:33,530 --> 00:40:37,940
Функциите, които сте използвали досега са изчистване,

509
00:40:37,940 --> 00:40:43,310
и след това сме също така използването на този тип - този нестандартен тип, наречен "bool'

510
00:40:43,310 --> 00:40:45,750
която е включена в стандартната булев заглавен файл.

511
00:40:45,750 --> 00:40:53,250
Ние определено искаме да включим стандартен bool.h за булев тип,

512
00:40:53,250 --> 00:40:59,230
и ние също искаме да # включват стандартен lib.h за стандартните библиотеки

513
00:40:59,230 --> 00:41:03,530
които включват изчистване, и безплатно, и всичко това.

514
00:41:03,530 --> 00:41:08,660
Така че, отдалечаване, отиваме да се откажат.

515
00:41:08,660 --> 00:41:14,190
Нека се опитаме и се уверете, че това действително е компилация.

516
00:41:14,190 --> 00:41:18,150
Ние виждаме, че го прави, така че ние сме на прав път.

517
00:41:18,150 --> 00:41:22,990
>> Нека отворим binary_tree.c отново.

518
00:41:22,990 --> 00:41:34,530
Компилира. Нека да отидем и да сме сигурни, че вмъкнете някои разговори в нашия съдържа функция -

519
00:41:34,530 --> 00:41:40,130
само за да се уверите, че всичко това е много добре.

520
00:41:40,130 --> 00:41:43,170
Например, когато ние направихме някои заявки в нашето дърво по-рано,

521
00:41:43,170 --> 00:41:48,500
ние се опитахме да погледнем стойностите, 6, 10 и 1, и ние знаехме, че 6 е в дървото,

522
00:41:48,500 --> 00:41:52,220
10 не е в дървото, а една не е в дървото.

523
00:41:52,220 --> 00:41:57,230
Нека използваме тези примерни разговори като начин да разбера дали или не

524
00:41:57,230 --> 00:41:59,880
ни съдържа функция работи.

525
00:41:59,880 --> 00:42:05,210
За да се направи това, аз отивам да се използва ФОРМАТ функция,

526
00:42:05,210 --> 00:42:10,280
и ние ще изведе резултата на поканата да съдържа.

527
00:42:10,280 --> 00:42:13,280
Отивам да се сложи в низ "съдържа (% г) = защото

528
00:42:13,280 --> 00:42:20,470
 отиваме да включите в стойността, която отива да търси,

529
00:42:20,470 --> 00:42:27,130
=% S \ N "и да използва това като наш формат низ.

530
00:42:27,130 --> 00:42:30,720
Ние просто ще видим - буквално отпечатате на екрана -

531
00:42:30,720 --> 00:42:32,060
това, което изглежда като извикване на функция.

532
00:42:32,060 --> 00:42:33,580
Това всъщност не е извикването на функцията.

533
00:42:33,580 --> 00:42:36,760
 Това е просто низ проектиран да изглежда като извикване на функция.

534
00:42:36,760 --> 00:42:41,140
>> Сега отиваме да се включите в стойностите.

535
00:42:41,140 --> 00:42:43,580
Ние ще се опитаме съдържа по 6,

536
00:42:43,580 --> 00:42:48,340
и след това, което ще направим тук, е да използвате този оператор третичния.

537
00:42:48,340 --> 00:42:56,340
Нека да видим - съдържа 6 - така, сега съм съдържат 6 и ако съдържа 6 е вярно,

538
00:42:56,340 --> 00:43:01,850
низ, който отива да изпрати във формат характер на% S

539
00:43:01,850 --> 00:43:04,850
ще бъде низ "истинска".

540
00:43:04,850 --> 00:43:07,690
Да сменя малко.

541
00:43:07,690 --> 00:43:16,210
В противен случай, ние искаме да прати стринга "фалшиви", ако съдържа шест връща фалшиви.

542
00:43:16,210 --> 00:43:19,730
Това е малко шантаво изглеждащи, но Предполагам, че може и да илюстрират

543
00:43:19,730 --> 00:43:23,780
третичния оператор прилича тъй като не съм го виждал за известно време.

544
00:43:23,780 --> 00:43:27,670
Това ще бъде хубаво, удобен начин да разбера, ако ни съдържа функция работи.

545
00:43:27,670 --> 00:43:30,040
Отивам да превъртате назад, наляво,

546
00:43:30,040 --> 00:43:39,900
и аз отивам да копирате и поставите този ред на няколко пъти.

547
00:43:39,900 --> 00:43:44,910
Той се е променил някои от тези стойности около

548
00:43:44,910 --> 00:43:59,380
така че това ще да бъде 1, и това ще бъде 10.

549
00:43:59,380 --> 00:44:02,480
>> В този момент ние имаме хубава функция съдържа.

550
00:44:02,480 --> 00:44:06,080
Имаме някои тестове и ще видим Ако всичко това работи.

551
00:44:06,080 --> 00:44:08,120
На този етап съм писал още малко код.

552
00:44:08,120 --> 00:44:13,160
Време е да излезете и да се уверите, че всичко все още съставя.

553
00:44:13,160 --> 00:44:20,360
Излезете, а сега нека се опитаме двоично дърво отново.

554
00:44:20,360 --> 00:44:22,260
Е, изглежда, че имаме грешка,

555
00:44:22,260 --> 00:44:26,930
и ние имаме това изрично обявяване на библиотека функция ФОРМАТ.

556
00:44:26,930 --> 00:44:39,350
Изглежда, че трябва да отидем и # включват standardio.h.

557
00:44:39,350 --> 00:44:45,350
И с това, всичко трябва да се компилира. Ние всички сме добре.

558
00:44:45,350 --> 00:44:50,420
Сега нека се опитаме работи двоично дърво и да видим какво ще се случи.

559
00:44:50,420 --> 00:44:53,520
Ние сме тук,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
и ние виждаме, че, както очаквахме -

561
00:44:55,190 --> 00:44:56,910
защото ние не са приложили съдържа още

562
00:44:56,910 --> 00:44:59,800
или по-скоро, ние току-що пуснати в замяна фалшива -

563
00:44:59,800 --> 00:45:03,300
ние виждаме, че това е просто връщане фалшиви за всички от тях,

564
00:45:03,300 --> 00:45:06,180
така че всички те работят за по-голямата си част доста добре.

565
00:45:06,180 --> 00:45:11,860
>> Нека се върнем и реалното изпълнение съдържа в този момент.

566
00:45:11,860 --> 00:45:17,490
Отивам да превъртите надолу, увеличавате, и -

567
00:45:17,490 --> 00:45:22,330
помнете, алгоритъм, който използва, е, че ние започнахме в основата възел

568
00:45:22,330 --> 00:45:28,010
и след това на всеки възел, който се сблъскваме, правим сравнение,

569
00:45:28,010 --> 00:45:32,380
и въз основа на това сравнение да се премести в лявата дете или надясно дете.

570
00:45:32,380 --> 00:45:39,670
Това ще изглежда много подобно на двоичен код за търсене, която писахме по-рано в срока.

571
00:45:39,670 --> 00:45:47,810
Когато започнете, ние знаем, че искаме да се държат за текущия възел

572
00:45:47,810 --> 00:45:54,050
че ние търсим и текущия възел ще се инициализира да е коренът.

573
00:45:54,050 --> 00:45:56,260
И сега, ние ще продължим да става чрез дървото,

574
00:45:56,260 --> 00:45:58,140
и не забравяйте, че нашата спиране състояние -

575
00:45:58,140 --> 00:46:01,870
 , когато ние действително работи чрез примера на ръка -

576
00:46:01,870 --> 00:46:03,960
беше, когато открихме нулева възел,

577
00:46:03,960 --> 00:46:05,480
когато не погледна към нула дете,

578
00:46:05,480 --> 00:46:09,620
, а по-скоро, когато ние действително се премества в един възел в дървото

579
00:46:09,620 --> 00:46:12,640
и е установено, че ние сме на нула възел.

580
00:46:12,640 --> 00:46:20,720
Отиваме, за да превъртите до тек не е равна на нула.

581
00:46:20,720 --> 00:46:22,920
И какво ще правим?

582
00:46:22,920 --> 00:46:31,610
Отиваме да проверите дали (тек -> стойност == стойност),

583
00:46:31,610 --> 00:46:35,160
тогава ние знаем, че всъщност сме намерили възел, който ние търсим.

584
00:46:35,160 --> 00:46:40,450
Така че тук, можем да се върнем вярно.

585
00:46:40,450 --> 00:46:49,830
В противен случай, ние искаме да се види дали стойността е по-малка от стойността.

586
00:46:49,830 --> 00:46:53,850
Ако стойността на текущия възел е по-малко от стойността търсим,

587
00:46:53,850 --> 00:46:57,280
отиваме да се движи надясно.

588
00:46:57,280 --> 00:47:10,600
Така че, тек = тек -> right_child; и по друг начин, ние отиваме да се движат наляво.

589
00:47:10,600 --> 00:47:17,480
тек = тек -> left_child; Доста прост.

590
00:47:17,480 --> 00:47:22,830
>> Можете да признаят линия, която изглежда много подобно на това от

591
00:47:22,830 --> 00:47:27,580
двоично търсене по-рано в срока, освен тогава ние се занимавахме с нисък, среден и високо.

592
00:47:27,580 --> 00:47:30,000
Ето, ние просто трябва да погледнете по текущата стойност,

593
00:47:30,000 --> 00:47:31,930
така че е хубаво и лесно.

594
00:47:31,930 --> 00:47:34,960
Нека се уверим, че този код работи.

595
00:47:34,960 --> 00:47:42,780
Първо, уверете се, че тя компилира. Изглежда, че го прави.

596
00:47:42,780 --> 00:47:47,920
Нека се опитаме да я пуснете.

597
00:47:47,920 --> 00:47:50,160
И наистина, тя се отпечатва всичко, което сме очаквали.

598
00:47:50,160 --> 00:47:54,320
Тя намира 6 в дървото, не намери 10, защото 10 не е в дървото,

599
00:47:54,320 --> 00:47:57,740
и не намери една или защото 1 също не е в дървото.

600
00:47:57,740 --> 00:48:01,420
Готини неща.

601
00:48:01,420 --> 00:48:04,470
>> Добре. Нека се върнем към нашата спецификация и да видим какво следва.

602
00:48:04,470 --> 00:48:07,990
Сега тя иска да добави повече възли в нашия дърво.

603
00:48:07,990 --> 00:48:11,690
Той иска да добави 5, 2 и 8, уверете се, че нашият съдържа код

604
00:48:11,690 --> 00:48:13,570
все още работи както се очаква.

605
00:48:13,570 --> 00:48:14,900
Да направя това.

606
00:48:14,900 --> 00:48:19,430
В този момент, а от това, че досадно копиране и поставяне отново,

607
00:48:19,430 --> 00:48:23,770
нека да напишем функция, за да създаде наистина възел.

608
00:48:23,770 --> 00:48:27,740
Ако превъртете надолу целия път до основната, виждаме, че ние сме били прави това

609
00:48:27,740 --> 00:48:31,210
много подобен код отново и отново, всеки път, когато искате да създадете възел.

610
00:48:31,210 --> 00:48:39,540
>> Да напишем функция, които действително ще изгради възел за нас и да го върне.

611
00:48:39,540 --> 00:48:41,960
Отивам да го наричат ​​build_node.

612
00:48:41,960 --> 00:48:45,130
Отивам да се изгради възел с определена стойност.

613
00:48:45,130 --> 00:48:51,040
Zoom тук.

614
00:48:51,040 --> 00:48:56,600
Първото нещо, което ще направя е действително да се създаде пространство за възел на куп.

615
00:48:56,600 --> 00:49:05,400
Така че, възел * N = изчистване (sizeof (възел)); N -> стойност = стойност;

616
00:49:05,400 --> 00:49:14,960
и след това тук, аз съм просто ще инициализира всички полета, за да бъдат подходящи стойности.

617
00:49:14,960 --> 00:49:22,500
И в самия край, ще се върнем нашата възел.

618
00:49:22,500 --> 00:49:28,690
Добре. Едно нещо е да се отбележи, че тази функция тук

619
00:49:28,690 --> 00:49:34,320
ще се върне указател към паметта, която е била купчина разпределени.

620
00:49:34,320 --> 00:49:38,880
Това, което е хубаво за това е, че този възел -

621
00:49:38,880 --> 00:49:42,420
ние трябва да го декларира на куп, защото ако го обявява в стека

622
00:49:42,420 --> 00:49:45,050
ние не ще бъде в състояние да го направи в тази функция като тази.

623
00:49:45,050 --> 00:49:47,690
Този спомен ще излязат от обхвата

624
00:49:47,690 --> 00:49:51,590
и ще бъде недействителна, ако ние се опитахме да получите достъп до него по-късно.

625
00:49:51,590 --> 00:49:53,500
Тъй като ние се обявяват куп заделената памет,

626
00:49:53,500 --> 00:49:55,830
ние ще трябва да се грижи за по-късно го освобождава

627
00:49:55,830 --> 00:49:58,530
за нашата програма да не изтече никаква памет.

628
00:49:58,530 --> 00:50:01,270
Ние сме били плоскодънни лодки, че за всичко останало в кода

629
00:50:01,270 --> 00:50:02,880
само за улеснение на времето,

630
00:50:02,880 --> 00:50:05,610
но ако някога напиша функция, която изглежда по този начин

631
00:50:05,610 --> 00:50:10,370
където имаш - някои я наричат ​​изчистване или презаделяне вътре -

632
00:50:10,370 --> 00:50:14,330
искате да се уверите, че сте поставили някакъв коментар тук, който казва,

633
00:50:14,330 --> 00:50:29,970
Хей, знаеш ли, връща купчина разпределени възел инициализира с издържал в стойност.

634
00:50:29,970 --> 00:50:33,600
И след това искате да се уверите, че сте поставили някаква бележка, която казва

635
00:50:33,600 --> 00:50:41,720
повикващия трябва да освободи връща паметта.

636
00:50:41,720 --> 00:50:45,450
По този начин, ако някой някога отива и използва тази функция,

637
00:50:45,450 --> 00:50:48,150
те знаят, че каквото и да се върна от тази функция

638
00:50:48,150 --> 00:50:50,870
в някакъв момент ще трябва да бъдат освободени.

639
00:50:50,870 --> 00:50:53,940
>> Ако приемем, че всичко е наред и е добре тук,

640
00:50:53,940 --> 00:51:02,300
можем да слизат в нашия код и да замени всички тези редове тук

641
00:51:02,300 --> 00:51:05,410
с разговори към нашата възел изграждане функция.

642
00:51:05,410 --> 00:51:08,170
Нека го направим много бързо.

643
00:51:08,170 --> 00:51:15,840
От една страна, че ние няма да замени тази част тук

644
00:51:15,840 --> 00:51:18,520
в дъното, където ние всъщност тел възли, за да се отбележи един към друг,

645
00:51:18,520 --> 00:51:21,030
защото това не можем да направим в нашата функция.

646
00:51:21,030 --> 00:51:37,400
Но, нека да го направим корен = build_node (7); възел * три = build_node (3);

647
00:51:37,400 --> 00:51:47,980
възел * Шест = build_node (6); възел * девет = build_node (9);

648
00:51:47,980 --> 00:51:52,590
И сега, ние също исках да добавите възли за

649
00:51:52,590 --> 00:52:03,530
възел * Пет = build_node (5); възел * Осем = build_node (8);

650
00:52:03,530 --> 00:52:09,760
и какво е друг възел? Нека видим тук. Искахме да добавите 2 -

651
00:52:09,760 --> 00:52:20,280
възел * = build_node (2);

652
00:52:20,280 --> 00:52:26,850
Добре. В този момент, ние знаем, че имаме 7, 3, 9 и 6

653
00:52:26,850 --> 00:52:30,320
всички жични по подходящ начин, но какво да кажем за 5, 8, и 2?

654
00:52:30,320 --> 00:52:33,550
За да запазите всичко в съответния ред,

655
00:52:33,550 --> 00:52:39,230
ние знаем, че право дете на три е шест.

656
00:52:39,230 --> 00:52:40,890
Така че, ако отиваме да добавите 5,

657
00:52:40,890 --> 00:52:46,670
5 също принадлежи в дясната страна на дървото, от които 3 е корен,

658
00:52:46,670 --> 00:52:50,440
така че 5 принадлежи като лявата дете на 6.

659
00:52:50,440 --> 00:52:58,650
Ние можем да направим това, като казва, шест -> left_child = пет;

660
00:52:58,650 --> 00:53:10,790
и след това на 8 принадлежи на лявата дете на 9, така че девет -> left_child = осем;

661
00:53:10,790 --> 00:53:22,190
и след това 2 е лявата дете на 3, така че можем да направим това тук - ти -> left_child = два.

662
00:53:22,190 --> 00:53:27,730
Ако не сте съвсем следват заедно с това, аз предлагам да го извади себе си.

663
00:53:27,730 --> 00:53:35,660
>> Добре. Да спасим това. Да излезем и се уверете, че тя компилира,

664
00:53:35,660 --> 00:53:40,760
и след това можем да добавим в нашите съдържа разговори.

665
00:53:40,760 --> 00:53:44,120
Изглежда, че всичко се компилира.

666
00:53:44,120 --> 00:53:51,790
Нека да отидем и да добавите в някои съдържа разговори.

667
00:53:51,790 --> 00:53:59,640
Отново, аз отивам да се направи малко на копиране и поставяне.

668
00:53:59,640 --> 00:54:15,860
Сега нека да търсите за 5, 8 и 2. Добре.

669
00:54:15,860 --> 00:54:28,330
Нека се уверим, че всичко това изглежда добре все още. Чудесно! Запазване и напусна.

670
00:54:28,330 --> 00:54:33,220
Сега нека направим, съставяне и сега да работи.

671
00:54:33,220 --> 00:54:37,540
От резултатите, изглежда, че всичко работи само хубаво и добре.

672
00:54:37,540 --> 00:54:41,780
Чудесно! Така че сега ние имаме нашите съдържа функция писмено.

673
00:54:41,780 --> 00:54:46,160
Нека продължим и да започнем да работим за това как да вмъкнете възли в дървото

674
00:54:46,160 --> 00:54:50,000
тъй като, както го правим сега, нещата не са много красиви.

675
00:54:50,000 --> 00:54:52,280
>> Ако се върнем на спецификацията,

676
00:54:52,280 --> 00:55:00,540
иска от нас да напише функция, наречена поставете отново, връщане на булев

677
00:55:00,540 --> 00:55:04,400
за това дали или не ние в действителност може да поставите възел в дървото -

678
00:55:04,400 --> 00:55:07,710
и след това стойността да вмъкнете в дървото е посочен като

679
00:55:07,710 --> 00:55:11,060
единственият аргумент в нашия вложка функция.

680
00:55:11,060 --> 00:55:18,180
Ние ще се върне вярно, ако наистина бихме могли да поставите на възела, съдържащ стойност на дървото,

681
00:55:18,180 --> 00:55:20,930
което означава, че ние, има достатъчно памет,

682
00:55:20,930 --> 00:55:24,840
и след това две, този възел не вече съществуват в дървото, тъй като -

683
00:55:24,840 --> 00:55:32,170
забравяйте, че ние не ще да има дублиращи се стойности на дървото, само за да направи нещата по-лесни.

684
00:55:32,170 --> 00:55:35,590
Добре. Обратно към кода.

685
00:55:35,590 --> 00:55:44,240
Отворете го. Увеличи малко, след което превъртете надолу.

686
00:55:44,240 --> 00:55:47,220
Нека сложим функция за вмъкване точно над съдържа.

687
00:55:47,220 --> 00:55:56,360
Отново, това ще се нарича булев вложка (INT стойност).

688
00:55:56,360 --> 00:56:01,840
Дай го малко повече пространство, а след това, по подразбиране,

689
00:56:01,840 --> 00:56:08,870
нека да поставим в замяна фалшиво в самия край.

690
00:56:08,870 --> 00:56:22,620
Сега надолу към дъното, да вървим напред и вместо ръчно изграждане на възлите

691
00:56:22,620 --> 00:56:27,900
в основната себе си и ги окабеляване да посоча един към друг, като правим,

692
00:56:27,900 --> 00:56:30,600
ние ще разчитаме на нашия вложка функция, за да го направя.

693
00:56:30,600 --> 00:56:35,510
Ние няма да разчита на ни вложка функция, за да изгради цялото дърво от нулата, просто все още,

694
00:56:35,510 --> 00:56:39,970
а по-скоро ще се отърве от тези линии - Ще коментират тези редове -

695
00:56:39,970 --> 00:56:43,430
, които изграждат възли 5, 8 и 2.

696
00:56:43,430 --> 00:56:55,740
И вместо това, ние ще вмъкнете повиквания към нашия вложка функция

697
00:56:55,740 --> 00:57:01,280
за да сте сигурни, че това наистина работи.

698
00:57:01,280 --> 00:57:05,840
Ето ни.

699
00:57:05,840 --> 00:57:09,300
>> Сега сме коментирали тези линии.

700
00:57:09,300 --> 00:57:13,700
Ние имаме само 7, 3, 9 и 6 в дърво в този момент.

701
00:57:13,700 --> 00:57:18,870
За да сте сигурни, че всичко това е работа,

702
00:57:18,870 --> 00:57:25,050
можем да я увеличите, направим дърво двоичен,

703
00:57:25,050 --> 00:57:30,750
го изпълним, и ние можем да видим, че съдържа сега ни казват, че ние сме напълно прав -

704
00:57:30,750 --> 00:57:33,110
5, 8 и 2, вече не са в дървото.

705
00:57:33,110 --> 00:57:37,960
Върнете се в кода,

706
00:57:37,960 --> 00:57:41,070
и как ще да вмъкнете?

707
00:57:41,070 --> 00:57:46,290
Не забравяйте, това, което направихме, когато бяхме всъщност поставяте 5, 8 и 2 по-рано.

708
00:57:46,290 --> 00:57:50,100
Играхме тази игра Plinko там, откъдето започнахме в основата,

709
00:57:50,100 --> 00:57:52,780
слезе от дървото един по един по един

710
00:57:52,780 --> 00:57:54,980
докато намерим подходящ разликата,

711
00:57:54,980 --> 00:57:57,570
и след това сме вързани на възел на подходящо място.

712
00:57:57,570 --> 00:57:59,480
Отиваме да направят същото нещо.

713
00:57:59,480 --> 00:58:04,070
Това е основно като писане на код, който ние използвахме съдържа функция

714
00:58:04,070 --> 00:58:05,910
да намерите място, където възел трябва да бъде,

715
00:58:05,910 --> 00:58:10,560
и след това просто щяхме да вмъкнете възела точно там.

716
00:58:10,560 --> 00:58:17,000
Нека започнем от това.

717
00:58:17,000 --> 00:58:24,200
>> Така че ние имаме възел * тек = корен, ние просто ще следват съдържа код

718
00:58:24,200 --> 00:58:26,850
докато не открием, че не работят за нас.

719
00:58:26,850 --> 00:58:32,390
Отиваме да мине през дървото, докато текущия елемент не е празен,

720
00:58:32,390 --> 00:58:45,280
и ако намерим стойност, която тек е равна на стойността, която ние се опитваме да вмъкнете

721
00:58:45,280 --> 00:58:49,600
добре, това е един от случаите, в които не бихме могли вмъкване на възел

722
00:58:49,600 --> 00:58:52,730
в дървото, защото това означава, че ние имаме дубликат стойност.

723
00:58:52,730 --> 00:58:59,010
Тук ние всъщност ще се върне фалшиви.

724
00:58:59,010 --> 00:59:08,440
Сега е друго, ако стойността на тек, е по-малко от стойността,

725
00:59:08,440 --> 00:59:10,930
сега знаем, че се движим в дясно

726
00:59:10,930 --> 00:59:17,190
 , тъй като стойността принадлежи в дясната половина на текущата дърво.

727
00:59:17,190 --> 00:59:30,110
В противен случай, отиваме да се движат наляво.

728
00:59:30,110 --> 00:59:37,980
Това е основното ни съдържа функционира там.

729
00:59:37,980 --> 00:59:41,820
>> В този момент, след като сме завършили тази линия, докато

730
00:59:41,820 --> 00:59:47,350
тек показалеца ни ще бъдат насочени към нула

731
00:59:47,350 --> 00:59:51,540
ако функцията все още не е върнат.

732
00:59:51,540 --> 00:59:58,710
Ние сме като тек на мястото, където искате да вмъкнете нов възел.

733
00:59:58,710 --> 01:00:05,210
Това, което остава да се направи, е действително да се изгради нов възел,

734
01:00:05,210 --> 01:00:08,480
което можем да направим доста лесно.

735
01:00:08,480 --> 01:00:14,930
Ние можем да използваме нашите супер-удобен строителство функция възел,

736
01:00:14,930 --> 01:00:17,210
и нещо, което не сме направили по-рано -

737
01:00:17,210 --> 01:00:21,400
ние просто се приема за даденост, но сега ще направя, за да съм сигурен -

738
01:00:21,400 --> 01:00:27,130
ще тестваме за да се уверите, че всъщност е стойността, върната от нов възел

739
01:00:27,130 --> 01:00:33,410
не е нула, защото ние не искаме да започне достъп до тази памет, ако тя е нула.

740
01:00:33,410 --> 01:00:39,910
Ние можем да се тестват, за да се уверите, че нов възел не е равна на нула.

741
01:00:39,910 --> 01:00:42,910
Или вместо да се види, ако действително е нула,

742
01:00:42,910 --> 01:00:52,120
и ако тя е нула, тогава ние може просто връщане фалшиви рано.

743
01:00:52,120 --> 01:00:59,090
>> В този момент, ние трябва да свържете нов възел в своето подходящо място в дървото.

744
01:00:59,090 --> 01:01:03,510
Ако погледнем назад в основния и къде сме всъщност са кабелите в стойностите преди,

745
01:01:03,510 --> 01:01:08,470
ние виждаме, че начина, по който са го правили, когато искахме да се сложи 3 в дърво

746
01:01:08,470 --> 01:01:11,750
е достъп до лявата дете на корен.

747
01:01:11,750 --> 01:01:14,920
Когато ние поставяме 9 в дървото, имахме достъп до точните дете на корена.

748
01:01:14,920 --> 01:01:21,030
Ние трябваше да има указател на родителя, за да се сложи нова стойност в дървото.

749
01:01:21,030 --> 01:01:24,430
Превъртате назад да вмъкнете, че не става доста работа тук

750
01:01:24,430 --> 01:01:27,550
защото ние не разполагат с показалеца майка.

751
01:01:27,550 --> 01:01:31,650
Това, което искаме да бъдем в състояние да направи в този момент, е,

752
01:01:31,650 --> 01:01:37,080
проверите стойността майка и виж - добре, Боже,

753
01:01:37,080 --> 01:01:41,990
ако стойността на компанията-майка е по-малко от текущата стойност,

754
01:01:41,990 --> 01:01:54,440
правото на детето на родителите трябва да бъде нов възел;

755
01:01:54,440 --> 01:02:07,280
в противен случай, наляво дете на родител трябва да бъде новият възел.

756
01:02:07,280 --> 01:02:10,290
Но ние не трябва този указател майка доста още.

757
01:02:10,290 --> 01:02:15,010
>> За да го получи, ние всъщност ще трябва да го следите, тъй като ние преминаваме през дървото

758
01:02:15,010 --> 01:02:18,440
и да намерят подходящо място в нашата линия по-горе.

759
01:02:18,440 --> 01:02:26,840
Ние можем да направим това, като превъртате назад до върха на нашия вложка функция

760
01:02:26,840 --> 01:02:32,350
и проследяване на друга показалеца променлива, наречена майка.

761
01:02:32,350 --> 01:02:39,340
Отиваме да го определя като равна на нула първоначално,

762
01:02:39,340 --> 01:02:43,640
и след това всеки път, когато мине през дървото,

763
01:02:43,640 --> 01:02:51,540
отиваме да настроите показалеца на майка да съответства на сегашната показалеца.

764
01:02:51,540 --> 01:02:59,140
Задайте майка равна на тек.

765
01:02:59,140 --> 01:03:02,260
По този начин, всеки път, когато минават през

766
01:03:02,260 --> 01:03:05,550
отиваме да се гарантира, че тъй като сегашното показалеца получава увеличава

767
01:03:05,550 --> 01:03:12,640
показалеца майка следва - само една степен по-висока от текущата показалеца на дървото.

768
01:03:12,640 --> 01:03:17,370
Всичко това изглежда доста добре.

769
01:03:17,370 --> 01:03:22,380
>> Мисля, че единственото нещо, което ще искате да регулирате това е изграждане на възел връщане на нула.

770
01:03:22,380 --> 01:03:25,380
С цел да се изгради възел всъщност успешно се върне нула,

771
01:03:25,380 --> 01:03:31,060
ние ще трябва да се промени този код,

772
01:03:31,060 --> 01:03:37,270
защото тук, никога не сме тествани, за да се уверите, че изчистване върна валиден показалеца.

773
01:03:37,270 --> 01:03:53,390
Така че, ако (N = NULL), а след това -

774
01:03:53,390 --> 01:03:55,250
ако изчистване върна валиден показалеца, тогава ние ще го инициализира;

775
01:03:55,250 --> 01:04:02,540
в противен случай, ние просто ще се върнат и че ще приключи до връщане на нула за нас.

776
01:04:02,540 --> 01:04:13,050
Сега всичко изглежда доста добре. Нека се уверим, че това всъщност съставя.

777
01:04:13,050 --> 01:04:22,240
Направи двоично дърво, и о, ние имаме някои неща тук.

778
01:04:22,240 --> 01:04:29,230
>> Имаме имплицитно декларация на функцията изгради възел.

779
01:04:29,230 --> 01:04:31,950
Отново с тези компилатори, ние отиваме да започне най-отгоре.

780
01:04:31,950 --> 01:04:36,380
Какво трябва да означава, че Обаждам се изгради възел, преди да съм всъщност тя обяви.

781
01:04:36,380 --> 01:04:37,730
Нека се върнем към кода наистина бързо.

782
01:04:37,730 --> 01:04:43,510
Превъртете надолу, и разбира се, ми посочете функция е обявена

783
01:04:43,510 --> 01:04:47,400
над изграждане на възел функция,

784
01:04:47,400 --> 01:04:50,070
но аз се опитвам да се използва за изграждане на възел вътрешността на вложка.

785
01:04:50,070 --> 01:05:06,610
Аз ще отида и копие и след това поставете изграждане функция възел начин тук на върха.

786
01:05:06,610 --> 01:05:11,750
По този начин, да се надяваме, че ще работи. Нека дадем още веднъж.

787
01:05:11,750 --> 01:05:18,920
Сега всичко това се компилира. Всичко е добре.

788
01:05:18,920 --> 01:05:21,640
>> Но в този момент, ние не са всъщност се нарича ни вложка функция.

789
01:05:21,640 --> 01:05:26,510
Ние просто знам, че тя компилира, така че нека влезем вътре и сложи няколко обаждания.

790
01:05:26,510 --> 01:05:28,240
Да го направим в нашата основна функция.

791
01:05:28,240 --> 01:05:32,390
Ето, ние коментира 5, 8 и 2,

792
01:05:32,390 --> 01:05:36,680
и тогава ние не ги тел тук.

793
01:05:36,680 --> 01:05:41,640
Нека направим някои разговори да вмъкнете,

794
01:05:41,640 --> 01:05:46,440
и нека да използват един и същ вид неща, които ние използвахме

795
01:05:46,440 --> 01:05:52,810
когато ние направихме тези ФОРМАТ разговори, за да се уверите, че всичко се получи поставена правилно.

796
01:05:52,810 --> 01:06:00,550
Отивам да копирате и поставите,

797
01:06:00,550 --> 01:06:12,450
и вместо да съдържа ние ще направим вложка.

798
01:06:12,450 --> 01:06:30,140
И вместо на 6, 10 и 1, отива да се използва 5, 8 и 2.

799
01:06:30,140 --> 01:06:37,320
Това трябва да се надяваме вмъкнете 5, 8 и 2 на дървото.

800
01:06:37,320 --> 01:06:44,050
Съставете. Всичко е добре. Сега ние действително ще работи нашата програма.

801
01:06:44,050 --> 01:06:47,330
>> Всичко се връща фалшиви.

802
01:06:47,330 --> 01:06:53,830
Така че, 5, 8 и 2 не си отиват, и тя изглежда като съдържа не ги намерите.

803
01:06:53,830 --> 01:06:58,890
Какво става? Да намалите.

804
01:06:58,890 --> 01:07:02,160
Първият проблем е, че се добавя сякаш връщане фалшиви,

805
01:07:02,160 --> 01:07:08,750
и тя изглежда като това е така, защото ние напуснахме в нашето завръщане фалшиво повикване,

806
01:07:08,750 --> 01:07:14,590
и всъщност ние никога не връща вярно.

807
01:07:14,590 --> 01:07:17,880
Ние можем да го измисли.

808
01:07:17,880 --> 01:07:25,290
Вторият проблем е, че сега дори и ако ние не направим - освен това, се откажат от това,

809
01:07:25,290 --> 01:07:34,530
тичам направи отново, да го компилирате, след което го стартирате -

810
01:07:34,530 --> 01:07:37,670
ние виждаме, че нещо друго се е случило тук.

811
01:07:37,670 --> 01:07:42,980
5, 8 и 2 все още никога не са били намерени на дървото.

812
01:07:42,980 --> 01:07:44,350
Така че, какво става?

813
01:07:44,350 --> 01:07:45,700
>> Нека да разгледаме това в кода.

814
01:07:45,700 --> 01:07:49,790
Нека видим дали ще мога да го разбера това.

815
01:07:49,790 --> 01:07:57,940
Започваме с майка не е нищожна.

816
01:07:57,940 --> 01:07:59,510
Текущата показалеца, равен на корен показалеца,

817
01:07:59,510 --> 01:08:04,280
и ние ще работим пътя ни през дървото.

818
01:08:04,280 --> 01:08:08,650
Ако текущият възел не е нула, а след това ние знаем, че можем да се движим малко.

819
01:08:08,650 --> 01:08:12,330
Ние си поставихме нашите майки показалеца, за да бъде равна на показалеца,

820
01:08:12,330 --> 01:08:15,420
провери стойност, ако стойностите са същите, ние се върнахме фалшива.

821
01:08:15,420 --> 01:08:17,540
Ако стойностите са по-малко, ние се премества надясно;

822
01:08:17,540 --> 01:08:20,399
В противен случай, ние се премества наляво.

823
01:08:20,399 --> 01:08:24,220
След това ние изграждаме възел. Ще я увеличите малко.

824
01:08:24,220 --> 01:08:31,410
И тук, ние ще се опитаме да свържете ценности, да бъде същата.

825
01:08:31,410 --> 01:08:37,250
Какво става? Нека видим дали евентуално Valgrind може да ни даде един намек.

826
01:08:37,250 --> 01:08:43,910
>> Обичам да използвам Valgrind, само защото Valgrind наистина бързо бяга

827
01:08:43,910 --> 01:08:46,729
и ви каже, ако има някакви грешки в паметта.

828
01:08:46,729 --> 01:08:48,300
Когато стартирате Valgrind на кода,

829
01:08:48,300 --> 01:08:55,859
както можете да видите право хит here--Valgrind./binary_tree--and влиза.

830
01:08:55,859 --> 01:09:03,640
Вие виждате, че ние не разполагаме с никаква грешка памет, така че да изглежда, че всичко е наред засега.

831
01:09:03,640 --> 01:09:07,529
Имаме някои изтичане на памет, което ние знаем, защото не сме

832
01:09:07,529 --> 01:09:08,910
случва да се освободи някой от нашите възли.

833
01:09:08,910 --> 01:09:13,050
Нека се опитаме работи GDB да се види какво всъщност се случва.

834
01:09:13,050 --> 01:09:20,010
Ние ще направим GDB. / Binary_tree. Заредил добре.

835
01:09:20,010 --> 01:09:23,670
Нека да критичната точка на вмъкване.

836
01:09:23,670 --> 01:09:28,600
Нека тече.

837
01:09:28,600 --> 01:09:31,200
Изглежда, че ние никога не сме всъщност се нарича вложка.

838
01:09:31,200 --> 01:09:39,410
Изглежда, че проблемът е само, че когато смених тук в основната

839
01:09:39,410 --> 01:09:44,279
всички тези ФОРМАТ обаждания от съдържа -

840
01:09:44,279 --> 01:09:56,430
Никога не съм се променили те да се обадя вложка.

841
01:09:56,430 --> 01:10:01,660
Сега нека да го пробвам. Нека състави.

842
01:10:01,660 --> 01:10:09,130
Всичко изглежда добре. Сега нека се опитаме да я пуснете, да видим какво ще стане.

843
01:10:09,130 --> 01:10:13,320
Добре! Всичко изглежда доста добре там.

844
01:10:13,320 --> 01:10:18,130
>> Крайният нещо да си помисля е, има ли някакви крайни случаи това се добавя?

845
01:10:18,130 --> 01:10:23,170
И се оказва, че, добре, единия край случай, че винаги е интересно да се мисли за

846
01:10:23,170 --> 01:10:26,250
е, какво ще се случи, ако вашето дърво е празна и наричате това се добавя функция?

847
01:10:26,250 --> 01:10:30,330
Ще проработи ли? Ами, нека да го опитам.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree в. -

849
01:10:32,110 --> 01:10:35,810
Начинът, по който започваш да тествате това, ние ще отидем до нашата основна функция,

850
01:10:35,810 --> 01:10:41,690
и по-скоро от окабеляване тези възли като този,

851
01:10:41,690 --> 01:10:56,730
ние просто няма да коментирам цялото нещо,

852
01:10:56,730 --> 01:11:02,620
и вместо окабеляване сами възли,

853
01:11:02,620 --> 01:11:09,400
всъщност ние можем да вървим напред и да изтриете всичко това.

854
01:11:09,400 --> 01:11:17,560
Ние ще направим всичко покана да вмъкнете.

855
01:11:17,560 --> 01:11:49,020
Така че, нека да направим - вместо 5, 8 и 2, започваш да вмъкнете 7, 3 и 9.

856
01:11:49,020 --> 01:11:58,440
И тогава ние също ще искате да вмъкнете 6, както и.

857
01:11:58,440 --> 01:12:05,190
Запиши. Quit. Двоично дърво.

858
01:12:05,190 --> 01:12:08,540
Всичко това се компилира.

859
01:12:08,540 --> 01:12:10,320
Ние можем само да го изпълним както и да видим какво ще се случи,

860
01:12:10,320 --> 01:12:12,770
но тя също ще бъде наистина важно да се уверите, че

861
01:12:12,770 --> 01:12:14,740
ние не разполагат с никакви грешки в паметта,

862
01:12:14,740 --> 01:12:16,840
тъй като това е един от нашите крайни случаи, за които знаем.

863
01:12:16,840 --> 01:12:20,150
>> Нека се уверим, че той работи и под Valgrind,

864
01:12:20,150 --> 01:12:28,310
който ние ще направим от само Valgrind / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Изглежда, че ние наистина имаме една грешка от един контекст -

866
01:12:31,110 --> 01:12:33,790
ние имаме това сегментиране вина.

867
01:12:33,790 --> 01:12:36,690
Какво се е случило?

868
01:12:36,690 --> 01:12:41,650
Valgrind всъщност ни казва къде се намира.

869
01:12:41,650 --> 01:12:43,050
Zoom малко.

870
01:12:43,050 --> 01:12:46,040
Изглежда, че това се случва в нашата вложка функция,

871
01:12:46,040 --> 01:12:53,420
където имаме невалиден четене с размер 4 на вложка, ред 60.

872
01:12:53,420 --> 01:13:03,590
Нека се върнем и да видим какво се случва тук.

873
01:13:03,590 --> 01:13:05,350
Zoom наистина бързо.

874
01:13:05,350 --> 01:13:14,230
Искам да се уверите, че той не отиде до ръба на екрана, за да можем да видим всичко.

875
01:13:14,230 --> 01:13:18,760
Издърпайте че в малко. Добре.

876
01:13:18,760 --> 01:13:35,030
Превъртете надолу, а проблемът е точно тук.

877
01:13:35,030 --> 01:13:40,120
Какво се случва ако се надолу и сегашната ни възел вече е нула,

878
01:13:40,120 --> 01:13:44,010
майка възел е нула, така че ако погледнем на самия връх, точно тук -

879
01:13:44,010 --> 01:13:47,340
ако никога тази линия, докато всъщност изпълнява

880
01:13:47,340 --> 01:13:52,330
защото нашата текущата стойност е нула - корена ни е нула, така че тек е нищожна -

881
01:13:52,330 --> 01:13:57,810
тогава нашите родители никога не се поставя към тек или валидна стойност,

882
01:13:57,810 --> 01:14:00,580
така, майка също ще бъде нула.

883
01:14:00,580 --> 01:14:03,700
Трябва да помним, за да проверите за това

884
01:14:03,700 --> 01:14:08,750
от време получаваме тук, и ние започваме достъп до стойността на родителя.

885
01:14:08,750 --> 01:14:13,190
Така че, какво се случва? Е, ако родителят е нулев

886
01:14:13,190 --> 01:14:17,990
(майка == NULL) - тогава знаем, че

887
01:14:17,990 --> 01:14:19,530
не трябва да има нищо в дървото.

888
01:14:19,530 --> 01:14:22,030
Ние трябва да се опитвате да го поставите в основата.

889
01:14:22,030 --> 01:14:32,570
Ние можем да направим това само с корена, равна на нов възел.

890
01:14:32,570 --> 01:14:40,010
След това, в този момент, ние не всъщност искат да мине през тези други неща.

891
01:14:40,010 --> 01:14:44,780
Вместо това, точно тук, можем да направим или друго, ако друго,

892
01:14:44,780 --> 01:14:47,610
или бихме могли да комбинирате всичко тук в друго,

893
01:14:47,610 --> 01:14:56,300
но тук ние просто ще използвате друг и да го направя по този начин.

894
01:14:56,300 --> 01:14:59,030
Сега отиваме да се тестват, за да се уверите, че нашите майки не е празен

895
01:14:59,030 --> 01:15:02,160
преди това всъщност се опитва да достъп до своите области.

896
01:15:02,160 --> 01:15:05,330
Това ще ни помогне да се избегне сегментирането вина.

897
01:15:05,330 --> 01:15:14,740
Така че, ние се откажат, отдалечаване, съставяне, стартирайте.

898
01:15:14,740 --> 01:15:18,130
>> Не грешки, но ние все още имаме куп изтичане на памет

899
01:15:18,130 --> 01:15:20,650
защото ние не освободи някой от нашите възли.

900
01:15:20,650 --> 01:15:24,350
Но, ако се върнем тук и ние с нетърпение в нашия разпечатка

901
01:15:24,350 --> 01:15:30,880
виждаме, че е добре, изглежда като всички от нашите вложки се връщат вярно, което е добре.

902
01:15:30,880 --> 01:15:33,050
Вложки са истина,

903
01:15:33,050 --> 01:15:36,670
и след това съответните призовава съдържа също е вярно.

904
01:15:36,670 --> 01:15:41,510
>> Добра работа! Изглежда, че ние успешно писмено вложка.

905
01:15:41,510 --> 01:15:47,430
Това е всичко, което имаме за уточняване на проблема тази седмица Set.

906
01:15:47,430 --> 01:15:51,720
Едно забавно предизвикателство да си помисля е как вие всъщност ще отиде в

907
01:15:51,720 --> 01:15:55,340
и безплатно всички възли в това дърво.

908
01:15:55,340 --> 01:15:58,830
Ние можем да направим така редица различни начини,

909
01:15:58,830 --> 01:16:01,930
но аз ще оставя, че до вас да експериментирате,

910
01:16:01,930 --> 01:16:06,080
и забавно предизвикателство, опитайте и се уверете, че можете да се уверите

911
01:16:06,080 --> 01:16:09,490
че този доклад Valgrind връща грешки и няма течове.

912
01:16:09,490 --> 01:16:12,880
>> Успех на Хъфман проблем тази седмица кодиране набор,

913
01:16:12,880 --> 01:16:14,380
и ние ще се видим следващата седмица!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]