1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Частина 7: більш комфортним]

2
00:00:02,770 --> 00:00:05,090
[Rob Боуден] [Harvard University]

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

4
00:00:07,930 --> 00:00:10,110
Добре. Так як я сказав у моїй електронній пошті,

5
00:00:10,110 --> 00:00:14,060
це буде двійкового дерева інтенсивної розділі.

6
00:00:14,060 --> 00:00:16,820
Але є не те, що багато питань.

7
00:00:16,820 --> 00:00:18,920
Отже, ми збираємося, щоб спробувати витягнути на кожне питання

8
00:00:18,920 --> 00:00:25,430
і перейти в хворобливе докладно все кращі способи ведення справ.

9
00:00:25,430 --> 00:00:31,200
Таким чином, на самому початку, ми проходимо через зразків малюнків бінарні дерева та інше.

10
00:00:31,200 --> 00:00:35,970
Так от, "Пам'ятай, що бінарне дерево має вузли, аналогічні зв'язаний список,

11
00:00:35,970 --> 00:00:38,150
тільки замість одного покажчика існує два: один для «дитини» лівий

12
00:00:38,150 --> 00:00:41,950
і один для правого "дитина".

13
00:00:41,950 --> 00:00:45,630
Таким чином, бінарне дерево так само, як зв'язаний список,

14
00:00:45,630 --> 00:00:47,910
крім структура матиме два покажчика.

15
00:00:47,910 --> 00:00:51,390
Там в троичной дерев, які матиме три покажчика,

16
00:00:51,390 --> 00:00:56,540
Є N-арной дерева, які тільки є загальний покажчик

17
00:00:56,540 --> 00:01:00,320
що ви тоді повинні Танос бути достатньо великим, щоб мати

18
00:01:00,320 --> 00:01:04,840
Досить покажчики на всі можливі дітей.

19
00:01:04,840 --> 00:01:08,200
Таким чином, бінарне дерево тільки, трапляється, мають постійне число два.

20
00:01:08,200 --> 00:01:11,260
Якщо ви хочете, ви можете дати зв'язаний список як унарний дерева,

21
00:01:11,260 --> 00:01:15,360
Але я не думаю, що хтось називає її цим.

22
00:01:15,360 --> 00:01:18,060
"Нічия коробки-і-стрілки схема двійкового дерева вузлів

23
00:01:18,060 --> 00:01:24,110
містять улюблений номер Нейта, 7, де кожна дитина покажчик нульовий ".

24
00:01:24,110 --> 00:01:27,780
Так Ipad режимі.

25
00:01:27,780 --> 00:01:30,280
>> Це буде досить просто.

26
00:01:30,280 --> 00:01:36,150
Ми просто будемо мати вузол, я намалюю його як квадрат.

27
00:01:36,150 --> 00:01:38,730
І я намалюю значення тут.

28
00:01:38,730 --> 00:01:41,090
Таким чином, значення буде йти сюди,

29
00:01:41,090 --> 00:01:44,770
, А потім тут ми матимемо лівий покажчик на лівий і правий покажчик праворуч.

30
00:01:44,770 --> 00:01:50,430
І це навіть дуже конвенції назвати його лівим і правим, імена покажчиків.

31
00:01:50,430 --> 00:01:52,460
Обидва цих збираєтеся бути нульовим.

32
00:01:52,460 --> 00:01:57,870
Це буде просто нульовим, і це буде просто нульовим.

33
00:01:57,870 --> 00:02:03,630
Добре. Отже, повернемося сюди.

34
00:02:03,630 --> 00:02:05,700
"З пов'язаного списку, ми тільки повинні були зберігати покажчик

35
00:02:05,700 --> 00:02:09,639
на перший вузол у списку, щоб запам'ятати весь зв'язаний список, або весь список.

36
00:02:09,639 --> 00:02:11,650
Крім того, з деревами, у нас є тільки для зберігання покажчика

37
00:02:11,650 --> 00:02:13,420
в один вузол, щоб пам'ятати все дерево.

38
00:02:13,420 --> 00:02:15,980
Цей вузол Calle «корінь» дерева.

39
00:02:15,980 --> 00:02:18,320
Побудувати на вашій схемі від до або залучити нове

40
00:02:18,320 --> 00:02:21,690
таке, що у вас є коробки-і-стрілки зображення бінарне дерево

41
00:02:21,690 --> 00:02:25,730
з значенням 7, потім 3 в лівій,

42
00:02:25,730 --> 00:02:32,760
Потім 9 на праву, а потім 6 на право 3 ".

43
00:02:32,760 --> 00:02:34,810
Давайте подивимося, якщо я можу пам'ятати все, що в моїй голові.

44
00:02:34,810 --> 00:02:37,670
Таким чином, це буде наш корінь тут.

45
00:02:37,670 --> 00:02:41,600
У нас буде декілька покажчиків десь, щось, що ми називаємо коренем,

46
00:02:41,600 --> 00:02:45,140
, І це вказує на цього хлопця.

47
00:02:45,140 --> 00:02:48,490
Тепер, щоб зробити новий вузол,

48
00:02:48,490 --> 00:02:52,870
Що ми маємо, 3 зліва?

49
00:02:52,870 --> 00:02:57,140
Таким чином, новий вузол з 3 років, і спочатку відзначає нульовий.

50
00:02:57,140 --> 00:02:59,190
Я просто поклав N.

51
00:02:59,190 --> 00:03:02,250
Тепер ми хочемо, щоб це піти наліво 7.

52
00:03:02,250 --> 00:03:06,840
Таким чином, ми змінити це покажчик тепер вказує на цього хлопця.

53
00:03:06,840 --> 00:03:12,420
І ми робимо те ж саме. Ми хочемо, щоб в 9 тут

54
00:03:12,420 --> 00:03:14,620
який спочатку просто говорить нульовим.

55
00:03:14,620 --> 00:03:19,600
Ми збираємося змінити це покажчик, крапка до 9,

56
00:03:19,600 --> 00:03:23,310
і тепер ми хочемо покласти 6 на право 3.

57
00:03:23,310 --> 00:03:32,170
Так що це буде - зробити 6.

58
00:03:32,170 --> 00:03:34,310
І цей хлопець буде вказувати там.

59
00:03:34,310 --> 00:03:38,320
Добре. Так що це все, що просить нас зробити.

60
00:03:38,320 --> 00:03:42,770
>> Тепер давайте пройдемося по термінології.

61
00:03:42,770 --> 00:03:46,690
Ми вже говорили про те, як корінь дерева є самий верхній вузол в дереві.

62
00:03:46,690 --> 00:03:54,720
Одна з яких 7. Вузлів у нижній частині дерева називаються листям.

63
00:03:54,720 --> 00:04:01,240
Будь вузол, який просто має нульове своїм дітям аркуша.

64
00:04:01,240 --> 00:04:03,680
Таким чином, це можливо, якщо наші бінарне дерево знаходиться всього в одному вузлі,

65
00:04:03,680 --> 00:04:10,130
, Що дерево є листом, і це все.

66
00:04:10,130 --> 00:04:12,060
"" Висота "дерева є кількість стрибків ви повинні зробити

67
00:04:12,060 --> 00:04:16,620
щоб отримати від вершини до листа ".

68
00:04:16,620 --> 00:04:18,640
Ми увійдемо в у другому, різниця

69
00:04:18,640 --> 00:04:21,940
між симетричними і несиметричними бінарні дерева,

70
00:04:21,940 --> 00:04:29,470
але зараз, загальна висота цього дерева

71
00:04:29,470 --> 00:04:34,520
Я б сказав, це 3, хоча якщо порахувати кількість стрибків

72
00:04:34,520 --> 00:04:39,710
Ви повинні зробити для того, щоб дістатися до 9, то це дійсно тільки висота 2.

73
00:04:39,710 --> 00:04:43,340
Зараз це незбалансоване бінарне дерево,

74
00:04:43,340 --> 00:04:49,840
але ми говорили про збалансоване, коли воно стане актуальним.

75
00:04:49,840 --> 00:04:52,040
Так що тепер ми можемо говорити про вузлів в дереві з точки зору

76
00:04:52,040 --> 00:04:54,700
по відношенню до інших вузлів в дереві.

77
00:04:54,700 --> 00:04:59,730
Так що тепер у нас є батьки, діти, брати, сестри, предки, і нащадки.

78
00:04:59,730 --> 00:05:05,650
Вони досить здорового глузду, що вони означають.

79
00:05:05,650 --> 00:05:09,610
Якщо ми запитаємо, - це батьки.

80
00:05:09,610 --> 00:05:12,830
Так що батько 3?

81
00:05:12,830 --> 00:05:16,090
[Студенти] 7. >> Да. Батько просто буде те, що вказує на вас.

82
00:05:16,090 --> 00:05:20,510
Тоді що діти від 7?

83
00:05:20,510 --> 00:05:23,860
[Студенти] 3 і 9. >> Да.

84
00:05:23,860 --> 00:05:26,460
Зверніть увагу, що "діти" буквально означає діти,

85
00:05:26,460 --> 00:05:31,010
так 6 не буде застосовуватися, тому що це, як онук.

86
00:05:31,010 --> 00:05:35,540
Але тоді, якщо ми підемо нащадків, так що є нащадками 7?

87
00:05:35,540 --> 00:05:37,500
[Студенти] 3, 6 і 9. >> Да.

88
00:05:37,500 --> 00:05:42,330
Нащадки кореневого вузла буде все в дереві,

89
00:05:42,330 --> 00:05:47,950
крім, може бути кореневим вузлом себе, якщо ви не хочете, щоб розглянути, що нащадок.

90
00:05:47,950 --> 00:05:50,750
І, нарешті, предки, так що це в протилежному напрямку.

91
00:05:50,750 --> 00:05:55,740
Так що предки 6?

92
00:05:55,740 --> 00:05:58,920
[Студенти] 3 і 7. >> Да. 9 не включені.

93
00:05:58,920 --> 00:06:02,520
Це просто пряма спина лінії в корінь

94
00:06:02,520 --> 00:06:13,230
буде вашим предкам.

95
00:06:13,230 --> 00:06:16,300
>> "Ми говоримо, що бінарне дерево" замовити ", якщо для кожного вузла в дереві,

96
00:06:16,300 --> 00:06:19,530
всі його нащадки зліва мають менші значення

97
00:06:19,530 --> 00:06:22,890
і всі ті, на правому мати більше значення.

98
00:06:22,890 --> 00:06:27,060
Наприклад, дерево вище замовили, але це не єдиний можливий впорядковане розташування ".

99
00:06:27,060 --> 00:06:30,180
Перш ніж ми перейдемо до цього,

100
00:06:30,180 --> 00:06:36,420
наказав бінарне дерево також відомий як бінарне дерево пошуку.

101
00:06:36,420 --> 00:06:38,660
Тут ми, трапляється, назвавши його замовив бінарне дерево,

102
00:06:38,660 --> 00:06:41,850
Але я ніколи не чув його називають наказав двійкового дерева перш,

103
00:06:41,850 --> 00:06:46,650
і на тест ми набагато більше шансів поставити двійкового дерева пошуку.

104
00:06:46,650 --> 00:06:49,250
Вони одне і те ж,

105
00:06:49,250 --> 00:06:54,580
і дуже важливо, ви дізнаєтеся відмінність між бінарне дерево і дерево двійкового пошуку.

106
00:06:54,580 --> 00:06:58,830
Бінарне дерево це просто дерево, яке вказує на дві речі.

107
00:06:58,830 --> 00:07:02,120
Кожен вузол вказує на дві речі.

108
00:07:02,120 --> 00:07:06,310
Існує немає міркувань про цінності, які він вказує.

109
00:07:06,310 --> 00:07:11,370
Так як тут, так як це бінарне дерево пошуку,

110
00:07:11,370 --> 00:07:14,030
Ми знаємо, що якщо ми підемо ліворуч від 7,

111
00:07:14,030 --> 00:07:16,670
Потім всі цінності, які ми може досягти

112
00:07:16,670 --> 00:07:19,310
, Йдучи зліва від 7 повинні бути менше 7.

113
00:07:19,310 --> 00:07:24,070
Зверніть увагу, що всі значення менше, ніж 7, 3 і 6.

114
00:07:24,070 --> 00:07:26,040
Це все до лівої 7.

115
00:07:26,040 --> 00:07:29,020
Якщо ми йдемо направо з 7, все повинно бути більше, ніж 7,

116
00:07:29,020 --> 00:07:33,220
тому 9 з правого боку 7, так що ми хороші.

117
00:07:33,220 --> 00:07:36,150
Це не так у випадку двійкового дерева,

118
00:07:36,150 --> 00:07:40,020
для звичайного бінарного дерева ми можемо просто є 3 у верхньому, 7 вліво,

119
00:07:40,020 --> 00:07:47,630
9 зліва від 7; немає впорядкованості значень взагалі.

120
00:07:47,630 --> 00:07:56,140
Тепер ми насправді не роблять цього, тому що це нудно і непотрібно,

121
00:07:56,140 --> 00:07:59,400
але "намагаються залучити стільки наказав дерев, як ви можете думати про

122
00:07:59,400 --> 00:08:01,900
за допомогою чисел 7, 3, 9 та 6.

123
00:08:01,900 --> 00:08:06,800
Скільки різних механізмів є? Що таке висота кожного з них? "

124
00:08:06,800 --> 00:08:10,480
>> Ми зробимо пару, але основна ідея в тому,

125
00:08:10,480 --> 00:08:16,530
це жодною мірою унікальне уявлення двійкового дерева, що містить ці значення.

126
00:08:16,530 --> 00:08:22,760
Все, що нам потрібно, це деякий бінарне дерево, яке містить 7, 3, 6 і 9.

127
00:08:22,760 --> 00:08:25,960
Інший можливий дійсно був би корінь 3,

128
00:08:25,960 --> 00:08:30,260
ідіть ліворуч, та це 6, йти наліво, і це 7,

129
00:08:30,260 --> 00:08:32,730
ідіть ліворуч, та це 9.

130
00:08:32,730 --> 00:08:36,169
Це цілком припустимо бінарне дерево пошуку.

131
00:08:36,169 --> 00:08:39,570
Це не дуже корисно, тому що це як зв'язаний список

132
00:08:39,570 --> 00:08:43,750
і всі ці покажчики просто нульовий.

133
00:08:43,750 --> 00:08:48,900
Але це дійсно дерева. Так?

134
00:08:48,900 --> 00:08:51,310
[Студент] Не значення повинні бути більше на правій?

135
00:08:51,310 --> 00:08:56,700
Або це -? >> Ці Я хотів піти іншим шляхом.

136
00:08:56,700 --> 00:09:00,960
Там же - да, давайте перейдемо це.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Хороший улов.

138
00:09:07,770 --> 00:09:11,730
Він як і раніше має підпорядковуватися, що пошук бінарне дерево, що повинен робити.

139
00:09:11,730 --> 00:09:15,650
Таким чином, все, що лівіше повинна бути менше будь-якого заданого вузла.

140
00:09:15,650 --> 00:09:23,180
Ми могли б просто рухатися, говорити, що це 6 і поклав його тут.

141
00:09:23,180 --> 00:09:26,880
Ні, ми не можемо. Чому я роблю це?

142
00:09:26,880 --> 00:09:35,350
Давайте робити - ось 6, тут 7, 6 очок 3.

143
00:09:35,350 --> 00:09:39,290
Це як і раніше дійсні бінарне дерево пошуку.

144
00:09:39,290 --> 00:09:49,260
Що поганого, якщо я - подивимося, чи зможу я придумати домовленості.

145
00:09:49,260 --> 00:09:52,280
Так, все в порядку. Так що ж не так з цим деревом?

146
00:09:52,280 --> 00:10:08,920
Я припускаю, що я вже дав вам підказку, що щось не в порядку з цим.

147
00:10:08,920 --> 00:10:14,430
Чому я роблю це?

148
00:10:14,430 --> 00:10:18,510
Добре. Це виглядає розумним.

149
00:10:18,510 --> 00:10:22,590
Якщо ми подивимося на кожен вузол, як і 7, то зліва від 7, 3.

150
00:10:22,590 --> 00:10:24,960
Таким чином, ми маємо 3, річ праворуч від 3 являє собою 6.

151
00:10:24,960 --> 00:10:27,750
І якщо ви подивитеся на 6, річ праворуч від 6, 9.

152
00:10:27,750 --> 00:10:30,910
Так чому ж це не є допустимим бінарне дерево пошуку?

153
00:10:30,910 --> 00:10:36,330
[Студенти] 9 і раніше в лівій частині 7. >> Да.

154
00:10:36,330 --> 00:10:43,710
Це повинно бути вірно, що всі значення, які може досягти, перейшовши в ліву від 7 менше, ніж 7.

155
00:10:43,710 --> 00:10:49,120
Якщо ми йдемо наліво з 7, ми отримуємо 3, і ми все ще можете отримати до 6,

156
00:10:49,120 --> 00:10:52,520
Ми все ще можете отримати до 9, але, пройшовши менше 7,

157
00:10:52,520 --> 00:10:55,070
ми не повинні бути в змозі дістатися до ряду, що це більше 7.

158
00:10:55,070 --> 00:10:59,830
Так що це не є допустимим бінарне дерево пошуку.

159
00:10:59,830 --> 00:11:02,330
>> Мій брат насправді було інтерв'ю питання

160
00:11:02,330 --> 00:11:07,760
, Що в основному це, просто код щось для перевірки

161
00:11:07,760 --> 00:11:10,500
Чи дерево бінарне дерево пошуку,

162
00:11:10,500 --> 00:11:13,580
і тому перше, що він зробив, було просто перевірити,

163
00:11:13,580 --> 00:11:17,020
якщо лівий і правий правильно, а потім повторювати там.

164
00:11:17,020 --> 00:11:19,700
Але ви не можете просто зробити це, ви повинні стежити

165
00:11:19,700 --> 00:11:22,550
той факт, що тепер, коли я пішов лівіше 7,

166
00:11:22,550 --> 00:11:26,340
всі в цьому поддереве повинно бути менше 7.

167
00:11:26,340 --> 00:11:28,430
Правильний алгоритм повинен стежити

168
00:11:28,430 --> 00:11:35,970
за межі значень, що може впасти можливо дюйма

169
00:11:35,970 --> 00:11:38,360
Ми не будемо пройти через всі з них.

170
00:11:38,360 --> 00:11:41,630
Існує гарне ставлення рецидиву,

171
00:11:41,630 --> 00:11:44,810
хоча ми ще не дійшли до тих, чи ми не отримаємо тих,

172
00:11:44,810 --> 00:11:47,030
визначає, скільки там насправді.

173
00:11:47,030 --> 00:11:53,180
Таким чином, існує 14 з них.

174
00:11:53,180 --> 00:11:56,020
Ідея про те, як ви могли б зробити це математично, як,

175
00:11:56,020 --> 00:11:59,770
Ви можете вибрати будь-якої однієї, щоб бути кореневий вузол,

176
00:11:59,770 --> 00:12:03,160
а потім, якщо я вибираю бути від 7 до кореневого вузла,

177
00:12:03,160 --> 00:12:08,150
тобто, скажімо, деякі цифри, які можуть піти моїм лівим вузлом,

178
00:12:08,150 --> 00:12:10,440
і є деякі номери, які можуть бути моя права вузла,

179
00:12:10,440 --> 00:12:15,090
але якщо я п загального числа, то сума, яка може піти наліво

180
00:12:15,090 --> 00:12:18,820
плюс сума, яка може піти на право N - 1.

181
00:12:18,820 --> 00:12:26,130
Таким чином, з решти чисел, вони повинні бути в змозі піти або вліво або вправо.

182
00:12:26,130 --> 00:12:31,580
Здається, важко, що, якщо я поставлю 3 перших, то все має піти наліво,

183
00:12:31,580 --> 00:12:35,080
але якщо я поставлю 7, то деякі речі можуть піти лівої і деякі речі можуть піти направо.

184
00:12:35,080 --> 00:12:39,570
І '3 перший "я мав на увазі все може піти направо.

185
00:12:39,570 --> 00:12:42,350
Це дійсно, ви просто повинні думати про це, як,

186
00:12:42,350 --> 00:12:47,980
як багато може піти на наступному рівні дерева.

187
00:12:47,980 --> 00:12:50,420
І він виходить на 14, або ви можете намалювати всі,

188
00:12:50,420 --> 00:12:54,650
і тоді ви отримаєте 14.

189
00:12:54,650 --> 00:13:01,120
>> Повертаючись сюди,

190
00:13:01,120 --> 00:13:03,510
"Впорядковані бінарні дерева є здорово, тому що ми можемо шукати через них

191
00:13:03,510 --> 00:13:06,910
У дуже схоже на пошуки більш впорядкований масив.

192
00:13:06,910 --> 00:13:10,120
Щоб зробити це, ми починаємо з кореня і працювати наш шлях вниз по дереву

193
00:13:10,120 --> 00:13:13,440
на листках, перевіряючи значення кожного вузла у відношенні цінностей, які ми шукаємо.

194
00:13:13,440 --> 00:13:15,810
Якщо значення поточного вузла менше, ніж значення, яке ми шукаємо,

195
00:13:15,810 --> 00:13:18,050
Ви йдете поруч з правим нащадком вузла.

196
00:13:18,050 --> 00:13:20,030
В іншому випадку, ви йдете в лівому нащадка.

197
00:13:20,030 --> 00:13:22,800
У якийсь момент, ви або знайти значення, яке ви шукаєте, або ви будете працювати в нуль,

198
00:13:22,800 --> 00:13:28,520
із зазначенням значення не в дереві ".

199
00:13:28,520 --> 00:13:32,450
У мене є для перемальовування дерева, що було раніше, то візьму другий.

200
00:13:32,450 --> 00:13:38,280
Але ми хочемо, щоб шукати чи 6, 10, і 1 в дерево.

201
00:13:38,280 --> 00:13:49,180
Так що ж це було, 7, 9, 3, 6. Добре.

202
00:13:49,180 --> 00:13:52,730
Цифри, які ви хочете подивитися, ми хочемо, щоб подивитися 6.

203
00:13:52,730 --> 00:13:55,440
Як це алгоритм роботи?

204
00:13:55,440 --> 00:14:03,040
Ну, у нас є кілька кореневих покажчик на дерево.

205
00:14:03,040 --> 00:14:12,460
І ми пішли б в корені і говорити, це значення дорівнює значенню ми шукаємо?

206
00:14:12,460 --> 00:14:15,000
Таким чином, ми шукаємо 6, так що це не рівні.

207
00:14:15,000 --> 00:14:20,140
Таким чином, ми продовжуємо, і тепер ми говоримо, ладно, так 6 менше 7.

208
00:14:20,140 --> 00:14:23,940
Чи означає це, ми хочемо йти наліво, або ми хочемо, щоб піти в порядку?

209
00:14:23,940 --> 00:14:27,340
[Студент] вліво. >> Да.

210
00:14:27,340 --> 00:14:33,340
Це значно простіше, все, що вам потрібно зробити, це зробити один можливий вузол дерева

211
00:14:33,340 --> 00:14:37,760
і тоді ви не - замість того, щоб думати головою,

212
00:14:37,760 --> 00:14:40,020
Добре, якщо вона менше, я можу піти наліво або піти направо,

213
00:14:40,020 --> 00:14:43,030
просто дивлячись на цю картину, це дуже ясно, що я повинен йти зліва

214
00:14:43,030 --> 00:14:47,700
якщо цей вузол більше, ніж значення, що я шукав.

215
00:14:47,700 --> 00:14:52,600
Таким чином, ви йдіть наліво, тепер я на 3.

216
00:14:52,600 --> 00:14:57,770
Я хочу - 3 менше, ніж значення, я шукаю, що на 6.

217
00:14:57,770 --> 00:15:03,420
Таким чином, ми йдемо направо, і тепер я в кінцевому підсумку на 6,

218
00:15:03,420 --> 00:15:07,380
яка є значенням я шукаю, так що я повертаюся правда.

219
00:15:07,380 --> 00:15:15,760
Таке значення, я буду дивитися на це 10.

220
00:15:15,760 --> 00:15:23,230
Добре. Так що 10, зараз буде - відрізав, що - будемо слідувати кореня.

221
00:15:23,230 --> 00:15:27,670
Тепер, 10 буде більше 7, тому я хочу, щоб дивитися направо.

222
00:15:27,670 --> 00:15:31,660
Я збираюся приїхати сюди, 10 буде більше 9,

223
00:15:31,660 --> 00:15:34,520
так що я збираюся хочете подивитися вправо.

224
00:15:34,520 --> 00:15:42,100
Я прийшов сюди, але тут зараз я в нуль.

225
00:15:42,100 --> 00:15:44,170
Що мені робити, якщо я вдарив нуль?

226
00:15:44,170 --> 00:15:47,440
[Студент] Повернутися помилковим? >> Да. Я не знайшов 10.

227
00:15:47,440 --> 00:15:49,800
1, буде майже ідентична випадку,

228
00:15:49,800 --> 00:15:51,950
винятком того, що тільки збирається бути перевернута, замість того щоб шукати

229
00:15:51,950 --> 00:15:56,540
вниз по правій стороні, я буду дивитися на ліву сторону.

230
00:15:56,540 --> 00:16:00,430
>> Тепер я думаю, що ми насправді отримати код.

231
00:16:00,430 --> 00:16:04,070
Ось де - відкрити CS50 прилад і прокладаєте свій шлях там,

232
00:16:04,070 --> 00:16:07,010
але ви також можете просто зробити це в просторі.

233
00:16:07,010 --> 00:16:09,170
Це, напевно, ідеальний зробити це в просторі,

234
00:16:09,170 --> 00:16:13,760
тому що ми можемо працювати в космосі.

235
00:16:13,760 --> 00:16:19,170
"Спочатку потрібно нове визначення типу для бінарного вузла дерева, що містить Int значення.

236
00:16:19,170 --> 00:16:21,400
Використання шаблону ЬурейеЕ нижче,

237
00:16:21,400 --> 00:16:24,510
створити нове визначення типу для вузла в бінарному дереві.

238
00:16:24,510 --> 00:16:27,930
Якщо ви застрягли. . . "Бла, бла, бла. Гаразд.

239
00:16:27,930 --> 00:16:30,380
Так давайте шаблонного тут,

240
00:16:30,380 --> 00:16:41,630
ЬурейеЕ вузла структури і вузлів. Так, все в порядку.

241
00:16:41,630 --> 00:16:44,270
Так що поле ми збираємося хочемо в нашій вузла?

242
00:16:44,270 --> 00:16:46,520
[Студент] Int, а потім два покажчика?

243
00:16:46,520 --> 00:16:49,700
>> Int значення, два покажчика? Як написати покажчики?

244
00:16:49,700 --> 00:16:58,440
[Студент] Struct. >> Я повинна збільшити масштаб Так, так що структура вузла * пішов,

245
00:16:58,440 --> 00:17:01,320
і структура вузла * прав.

246
00:17:01,320 --> 00:17:03,460
І пам'ятайте обговорення в минулий раз,

247
00:17:03,460 --> 00:17:15,290
що це не має сенсу, це не має сенсу,

248
00:17:15,290 --> 00:17:18,270
це не має сенсу.

249
00:17:18,270 --> 00:17:25,000
Вам потрібно все, для того, щоб визначити це рекурсивна структура.

250
00:17:25,000 --> 00:17:27,970
Гаразд, так це те, що наше дерево буде виглядати.

251
00:17:27,970 --> 00:17:37,670
Якщо б ми зробили трійкового дерева, то вузол може виглядати В1, В2, структура вузла * b3,

252
00:17:37,670 --> 00:17:43,470
де Ь філії - насправді, я більше чув він залишив, середній, правий, але незалежно.

253
00:17:43,470 --> 00:17:55,610
Ми дбаємо лише про бінарних, так вправо, вліво.

254
00:17:55,610 --> 00:17:59,110
"Тепер оголосити глобальну змінну * вузол для кореня дерева".

255
00:17:59,110 --> 00:18:01,510
Таким чином, ми не збираємося цього робити.

256
00:18:01,510 --> 00:18:08,950
Для того, щоб зробити речі трохи більш складним і більш узагальнені,

257
00:18:08,950 --> 00:18:11,570
у нас не буде глобальної змінної вузла.

258
00:18:11,570 --> 00:18:16,710
Замість цього, в головному ми оголосимо всі наші вузол речі,

259
00:18:16,710 --> 00:18:20,500
і це означає, що нижче, коли ми почнемо роботи

260
00:18:20,500 --> 00:18:23,130
наші містить функцію і наші функції вставки,

261
00:18:23,130 --> 00:18:27,410
замість того, щоб наші містить функцію тільки за допомогою цієї глобальної змінної вузла,

262
00:18:27,410 --> 00:18:34,280
ми будемо мати його прийняти в якості аргументу дерево, яке ми хочемо, щоб обробити.

263
00:18:34,280 --> 00:18:36,650
Наявність глобальних змінних повинен був зробити речі простіше.

264
00:18:36,650 --> 00:18:42,310
Ми збираємося зробити все важче.

265
00:18:42,310 --> 00:18:51,210
Тепер візьміть хвилину або близько того, щоб просто робити такого роду речі,

266
00:18:51,210 --> 00:18:57,690
де всередині основного ви хочете створити це дерево, і це все, що ви хочете зробити.

267
00:18:57,690 --> 00:19:04,530
Спробуйте побудувати це дерево в основною функцією.

268
00:19:42,760 --> 00:19:47,610
>> Добре. Таким чином, ви не повинні навіть побудували дерево всю дорогу поки немає.

269
00:19:47,610 --> 00:19:49,840
Але у кого щось я міг би підтягнути

270
00:19:49,840 --> 00:20:03,130
щоб показати, як можна було б розпочати будівництво такого дерева?

271
00:20:03,130 --> 00:20:08,080
[Студент] Хтось стукіт, намагаючись вибратися назовні.

272
00:20:08,080 --> 00:20:13,100
[Боуден] Будь комфортно з їх побудови дерева?

273
00:20:13,100 --> 00:20:15,520
[Студент] Звичайно. Це не зроблено. >> Це нормально. Ми можемо просто закінчити -

274
00:20:15,520 --> 00:20:26,860
ой, ви можете зберегти його? Ура.

275
00:20:26,860 --> 00:20:32,020
Таким чином, тут ми маємо - ой, я трохи обрізаються.

276
00:20:32,020 --> 00:20:34,770
Чи можу я збільшив?

277
00:20:34,770 --> 00:20:37,730
Збільшення, прокрутка з. >> У мене є питання. >> Да?

278
00:20:37,730 --> 00:20:44,410
[Студент] При визначенні структури, такі речі, як ініціалізується небудь?

279
00:20:44,410 --> 00:20:47,160
[Боуден] Немає >> Добре. Таким чином, ви повинні ініціалізувати -

280
00:20:47,160 --> 00:20:50,450
[Боуден] Немає Коли ви визначаєте, чи при оголошенні структури,

281
00:20:50,450 --> 00:20:55,600
він не ініціалізований за замовчуванням, це все одно, якщо ви оголосите Int.

282
00:20:55,600 --> 00:20:59,020
Це рівно те ж саме. Це як кожен з її окремих полів

283
00:20:59,020 --> 00:21:04,460
може мати значення сміття в ньому. >> А чи можна визначити - чи оголосити структуру

284
00:21:04,460 --> 00:21:07,740
таким чином, що це робить їх ініціалізації?

285
00:21:07,740 --> 00:21:13,200
[Боуден] Так. Таким чином, контекстне синтаксис ініціалізації

286
00:21:13,200 --> 00:21:18,660
буде виглядати -

287
00:21:18,660 --> 00:21:22,200
Там дві, як ми можемо це зробити. Я думаю, ми повинні скомпілювати його

288
00:21:22,200 --> 00:21:25,840
щоб переконатися, що Clang робить теж саме.

289
00:21:25,840 --> 00:21:28,510
Порядок аргументів, який входить в структуру,

290
00:21:28,510 --> 00:21:32,170
ви покладете в порядок аргументів усередині цих фігурні дужки.

291
00:21:32,170 --> 00:21:35,690
Тому якщо ви хочете, щоб підготувати його до 9 і залишили бути нульовою, а потім праву бути нульовим,

292
00:21:35,690 --> 00:21:41,570
було б 9, NULL, NULL.

293
00:21:41,570 --> 00:21:47,890
В якості альтернативи, і редактор не подобається цей синтаксис,

294
00:21:47,890 --> 00:21:50,300
і він думає, що я хочу новий блок,

295
00:21:50,300 --> 00:22:01,800
але альтернатива є щось подібне -

296
00:22:01,800 --> 00:22:04,190
Тут, я покладу її на новий рядок.

297
00:22:04,190 --> 00:22:09,140
Можна прямо сказати, не пам'ятаю точно синтаксис.

298
00:22:09,140 --> 00:22:13,110
Таким чином, ви можете явно звернутися до них по імені, і говорю:

299
00:22:13,110 --> 00:22:21,570
. С, або. Значення = 9. Ліва = NULL.

300
00:22:21,570 --> 00:22:24,540
Я припускаю, це необхідність бути коми.

301
00:22:24,540 --> 00:22:29,110
. Право = NULL, щоб таким чином ви не

302
00:22:29,110 --> 00:22:33,780
насправді потрібно знати порядок структури,

303
00:22:33,780 --> 00:22:36,650
і коли ви це читаєте, це набагато більш явну

304
00:22:36,650 --> 00:22:41,920
про те, що цінність буття ініціалізується.

305
00:22:41,920 --> 00:22:44,080
>> Це трапляється, одна з речей, які -

306
00:22:44,080 --> 00:22:49,100
так, по більшій частині, C + + є розширенням C.

307
00:22:49,100 --> 00:22:54,160
Ви можете взяти C код, перемістити його на C + +, і вона повинна зібрати.

308
00:22:54,160 --> 00:22:59,570
Це одна з речей, які C + + не підтримує, так що люди, як правило не робити цього.

309
00:22:59,570 --> 00:23:01,850
Я не знаю, якщо це єдина причина, люди, як правило не робити цього,

310
00:23:01,850 --> 00:23:10,540
але справа, де я повинен його використовувати необхідні для роботи з C + + і тому я не міг використовувати це.

311
00:23:10,540 --> 00:23:14,000
Інший приклад того, що не працює з C + + є

312
00:23:14,000 --> 00:23:16,940
як Танос повертає "порожнеча *," технічно,

313
00:23:16,940 --> 00:23:20,200
але ви могли б просто сказати, символ * х = Танос що завгодно,

314
00:23:20,200 --> 00:23:22,840
і він автоматично буде приведений до символ *.

315
00:23:22,840 --> 00:23:25,450
Це автоматичний литих не буває в C + +.

316
00:23:25,450 --> 00:23:28,150
Це не буде компілюватися, і ви б явно потрібно сказати

317
00:23:28,150 --> 00:23:34,510
символ *, Танос, що завгодно, щоб кинути його в символ *.

318
00:23:34,510 --> 00:23:37,270
Є не так багато речей, які C і C + + не згодні з,

319
00:23:37,270 --> 00:23:40,620
але ці два.

320
00:23:40,620 --> 00:23:43,120
Таким чином, ми підемо з цим синтаксисом.

321
00:23:43,120 --> 00:23:46,150
Але навіть якщо б ми не йшли з синтаксисом,

322
00:23:46,150 --> 00:23:49,470
що таке - може бути поганого в цьому?

323
00:23:49,470 --> 00:23:52,170
[Студент] Мені не потрібно разименовать це? >> Да.

324
00:23:52,170 --> 00:23:55,110
Пам'ятайте, що стрілка має неявний разименованія,

325
00:23:55,110 --> 00:23:58,230
і тому, коли ми просто маємо справу з структурою,

326
00:23:58,230 --> 00:24:04,300
Ми хочемо використовувати. щоб дістатися до поля всередині структури.

327
00:24:04,300 --> 00:24:07,200
І єдиний раз, коли ми використовуємо стрілки, коли ми хочемо зробити -

328
00:24:07,200 --> 00:24:13,450
Ну, стрілки еквівалентно -

329
00:24:13,450 --> 00:24:17,020
ось що це означало б, якби я використовував стрілку.

330
00:24:17,020 --> 00:24:24,600
Всі стрілки засіб, разименовать, тепер я в структури, і я можу отримати полю.

331
00:24:24,600 --> 00:24:28,040
Або отримати полю прямо або разименованія і отримати полю -

332
00:24:28,040 --> 00:24:30,380
Я думаю, це має бути значення.

333
00:24:30,380 --> 00:24:33,910
Але тут я маю справу тільки з структуру, а не покажчик на структуру,

334
00:24:33,910 --> 00:24:38,780
і тому я не можу використовувати стрілки.

335
00:24:38,780 --> 00:24:47,510
Але такого роду речі ми можемо зробити для всіх вузлів.

336
00:24:47,510 --> 00:24:55,790
О, мій Бог.

337
00:24:55,790 --> 00:25:09,540
Це 6, 7 і 3.

338
00:25:09,540 --> 00:25:16,470
Тоді ми можемо створити філії в нашому дереві, ми можемо мати 7 -

339
00:25:16,470 --> 00:25:21,650
Ми можемо мати, його ліва повинна вказувати на 3.

340
00:25:21,650 --> 00:25:25,130
Так як же нам це зробити?

341
00:25:25,130 --> 00:25:29,320
[Студенти, нерозбірливо] >> Да. Адреса node3,

342
00:25:29,320 --> 00:25:34,170
і якщо у вас не було адреси, то він просто не буде компілюватися.

343
00:25:34,170 --> 00:25:38,190
Але пам'ятайте, що ці покажчики на наступний вузлів.

344
00:25:38,190 --> 00:25:44,930
Право повинно вказувати на 9,

345
00:25:44,930 --> 00:25:53,330
і 3 слід вказати на право 6.

346
00:25:53,330 --> 00:25:58,480
Я думаю, що це все в порядку. Будь-які коментарі або питання?

347
00:25:58,480 --> 00:26:02,060
[Студент, нерозбірливо] корінь буде 7.

348
00:26:02,060 --> 00:26:08,210
Ми можемо тільки сказати, вузол * PTR =

349
00:26:08,210 --> 00:26:14,160
або корінь = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Для наших цілей, ми будемо мати справу зі вставкою,

351
00:26:20,730 --> 00:26:25,490
так що ми збираємося хочете написати функцію, щоб вставити в цю бінарне дерево

352
00:26:25,490 --> 00:26:34,230
і вставки неминуче будемо називати Танос, щоб створити новий вузол цього дерева.

353
00:26:34,230 --> 00:26:36,590
Так що все буде заплутатися з тим, що деякі вузли

354
00:26:36,590 --> 00:26:38,590
В даний час в стеку

355
00:26:38,590 --> 00:26:43,680
та інші вузли збираються в кінцевому підсумку на купі коли ми вставляємо їх.

356
00:26:43,680 --> 00:26:47,640
Це цілком справедливо, але єдина причина,

357
00:26:47,640 --> 00:26:49,600
ми в змозі зробити це в стеку

358
00:26:49,600 --> 00:26:51,840
Тому що це такий надуманий приклад, що ми знаємо

359
00:26:51,840 --> 00:26:56,360
Дерево має бути побудовано як 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Якщо ми цього не було, то ми не мали б Танос в першу чергу.

361
00:27:02,970 --> 00:27:06,160
Як ми побачимо трохи пізніше, ми повинні malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Зараз це цілком розумно поставити в стек,

363
00:27:08,570 --> 00:27:14,750
але давайте змінимо цю Танос реалізації.

364
00:27:14,750 --> 00:27:17,160
Таким чином, кожен з них тепер буде щось подібне

365
00:27:17,160 --> 00:27:24,240
вузол * node9 = Танос (SizeOf (вузла)).

366
00:27:24,240 --> 00:27:28,040
І тепер ми збираємося потрібно зробити наш чек.

367
00:27:28,040 --> 00:27:34,010
якщо (node9 == NULL) - я не хочу, -

368
00:27:34,010 --> 00:27:40,950
повертає 1, а потім ми можемо зробити node9-> тому що тепер це покажчик,

369
00:27:40,950 --> 00:27:45,300
Значення = 6, node9-> вліво = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> Право = NULL,

371
00:27:48,930 --> 00:27:51,410
і ми збираємося потрібно зробити, що для кожного з цих вузлів.

372
00:27:51,410 --> 00:27:57,490
Таким чином, замість, скажімо всередині окремої функції.

373
00:27:57,490 --> 00:28:00,620
Давайте назвемо це вузол * build_node,

374
00:28:00,620 --> 00:28:09,050
і це дещо схоже на API, ми пропонуємо для кодування Хаффмана.

375
00:28:09,050 --> 00:28:12,730
Ми даємо вам ініціалізатор функцій для дерева

376
00:28:12,730 --> 00:28:20,520
деконструкторів і «функції» для тих, дерева і те ж саме для лісу.

377
00:28:20,520 --> 00:28:22,570
>> Отже, ми збираємося мати функцію ініціалізації

378
00:28:22,570 --> 00:28:25,170
просто побудувати вузол для нас.

379
00:28:25,170 --> 00:28:29,320
І це буде виглядати досить багато саме так.

380
00:28:29,320 --> 00:28:32,230
І я навіть збирався бути ледачим і не змінювати ім'я змінної,

381
00:28:32,230 --> 00:28:34,380
хоча node9 не має ніякого сенсу.

382
00:28:34,380 --> 00:28:38,610
О, я думаю node9 значення не повинно було бути 6.

383
00:28:38,610 --> 00:28:42,800
Тепер ми можемо повернутися node9.

384
00:28:42,800 --> 00:28:49,550
І тут ми повинні повернутися нульовий.

385
00:28:49,550 --> 00:28:52,690
Усі згодні з цим Build-A-вузла функцію?

386
00:28:52,690 --> 00:28:59,780
Так що тепер ми можемо просто подзвонити, що для створення будь-якого вузла із заданим значенням і нульових покажчиків.

387
00:28:59,780 --> 00:29:09,750
Тепер ми можемо викликати те, що ми можемо зробити вузол * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
І давайте робити. . .

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

390
00:29:33,980 --> 00:29:39,330
І тепер ми хочемо створити такий же покажчики,

391
00:29:39,330 --> 00:29:42,470
тільки тепер все це вже в термінах покажчиків

392
00:29:42,470 --> 00:29:48,480
так більше не потрібні адреси.

393
00:29:48,480 --> 00:29:56,300
Добре. Так що останнє, що я хочу зробити?

394
00:29:56,300 --> 00:30:03,850
Там у виправлення помилок, що я не роблю.

395
00:30:03,850 --> 00:30:06,800
Що побудувати вузол натомість?

396
00:30:06,800 --> 00:30:11,660
[Студент, нерозбірливо] >> Да. Якщо Танос не вдалося, він буде повертати NULL.

397
00:30:11,660 --> 00:30:16,460
Так що я збираюся ліниво поклав його сюди, а не робити умова для кожного.

398
00:30:16,460 --> 00:30:22,320
Якщо (node9 == NULL, або - ще простіше,

399
00:30:22,320 --> 00:30:28,020
це рівносильно тому, якщо тільки не node9.

400
00:30:28,020 --> 00:30:38,310
Так що, якщо не node9, або не node6, або не node3, або не node7, повернути 1.

401
00:30:38,310 --> 00:30:42,850
Може бути, ми повинні друкувати Танос не вдалося, або щось ще.

402
00:30:42,850 --> 00:30:46,680
[Студент] Помилково дорівнює нулю, а?

403
00:30:46,680 --> 00:30:51,290
[Боуден] Будь нульове значення є хибним.

404
00:30:51,290 --> 00:30:53,920
Таким чином, нульові є нульове значення.

405
00:30:53,920 --> 00:30:56,780
Нуль нуль. Помилкові є нульове значення.

406
00:30:56,780 --> 00:31:02,130
Будь - в значній мірі тільки 2 нульові значення не мають законної нуля,

407
00:31:02,130 --> 00:31:07,900
помилковими тільки хеш визначається як нуль.

408
00:31:07,900 --> 00:31:13,030
Це відноситься і якщо ми заявляємо глобальної змінної.

409
00:31:13,030 --> 00:31:17,890
Якби ми мали кореневий вузол * тут,

410
00:31:17,890 --> 00:31:24,150
Потім - хороша річ про глобальних змінних є те, що вони завжди мають початкове значення.

411
00:31:24,150 --> 00:31:27,500
Це не правда функцій, як всередині тут,

412
00:31:27,500 --> 00:31:34,870
якщо у нас є, начебто, вузла або вузла * х.

413
00:31:34,870 --> 00:31:37,380
Ми поняття не маємо, що x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
або ми можемо роздрукувати їх, і вони можуть бути довільними.

415
00:31:40,700 --> 00:31:44,980
Це не правда глобальних змінних.

416
00:31:44,980 --> 00:31:47,450
Так кореневого вузла або вузла х.

417
00:31:47,450 --> 00:31:53,410
За замовчуванням, все, що глобальне, якщо явно не ініціалізований до деякого значення,

418
00:31:53,410 --> 00:31:57,390
має нульове значення як значення.

419
00:31:57,390 --> 00:32:01,150
Так от, вузол * корінь, ми явно не ініціалізувати його ні до чого,

420
00:32:01,150 --> 00:32:06,350
таким чином, його значення за замовчуванням буде нульовим, яка є нульове значення покажчика.

421
00:32:06,350 --> 00:32:11,870
За замовчуванням значення х буде означати, що x.value дорівнює нулю,

422
00:32:11,870 --> 00:32:14,260
x.left є недійсним, і x.right є недійсним.

423
00:32:14,260 --> 00:32:21,070
Таким чином, так як він є структурою, всі поля структури будуть дорівнюють нулю значень.

424
00:32:21,070 --> 00:32:24,410
Ми не повинні використовувати що тут, однако.

425
00:32:24,410 --> 00:32:27,320
[Студент] структури відрізняються від інших змінних, і інші змінні

426
00:32:27,320 --> 00:32:31,400
сміття цінностей; ці нулі?

427
00:32:31,400 --> 00:32:36,220
[Боуден] Інші значення теж. Таким чином, в х, х буде дорівнювати нулю.

428
00:32:36,220 --> 00:32:40,070
Якщо це в глобальній області, вона має первинне значення. >> Добре.

429
00:32:40,070 --> 00:32:48,950
[Боуден] Або початкове значення ви дали його або дорівнюють нулю.

430
00:32:48,950 --> 00:32:53,260
Я думаю, що бере на себе все це.

431
00:32:53,260 --> 00:32:58,390
>> Добре. Так що в наступний частини питання питає,

432
00:32:58,390 --> 00:33:01,260
"Тепер ми хочемо написати функцію, називається містить

433
00:33:01,260 --> 00:33:04,930
з прототипом BOOL містить цілочисельне значення ".

434
00:33:04,930 --> 00:33:08,340
Ми не збираємося робити BOOL містить цілочисельне значення.

435
00:33:08,340 --> 00:33:15,110
Наш прототип буде виглядати

436
00:33:15,110 --> 00:33:22,380
BOOL містить (цілочисельне значення.

437
00:33:22,380 --> 00:33:24,490
І тоді ми також збираємося передати його дерево

438
00:33:24,490 --> 00:33:28,870
що вона повинна бути перевірка, щоб побачити, якщо вона має це значення.

439
00:33:28,870 --> 00:33:38,290
Таким чином, вузол * дерево). Добре.

440
00:33:38,290 --> 00:33:44,440
І тоді ми можемо назвати це чимось на зразок,

441
00:33:44,440 --> 00:33:46,090
може бути, ми хочемо Printf або щось.

442
00:33:46,090 --> 00:33:51,040
Містить 6, наш корінь.

443
00:33:51,040 --> 00:33:54,300
Це повинно повернути один або правда,

444
00:33:54,300 --> 00:33:59,390
в той час як містить 5 корінь повинен повернутися помилковим.

445
00:33:59,390 --> 00:34:02,690
Так що беріть другу для реалізації цього.

446
00:34:02,690 --> 00:34:06,780
Ви можете зробити це або ітераційно або рекурсивно.

447
00:34:06,780 --> 00:34:09,739
Гарна річ про те, як ми встановили речей є те, що

448
00:34:09,739 --> 00:34:12,300
вона піддається нашому рекурсивне рішення набагато простіше

449
00:34:12,300 --> 00:34:14,719
ніж глобальна змінна шляху і зробили.

450
00:34:14,719 --> 00:34:19,750
Тому що, якщо ми просто містить цілочисельне значення, то немає ніякого способу рекурсії вниз піддерев.

451
00:34:19,750 --> 00:34:24,130
Ми повинні були б мати окрему допоміжну функцію, яка рекурсивно вниз піддерев для нас.

452
00:34:24,130 --> 00:34:29,610
Але так як ми змінили його взяти дерево в якості аргументу,

453
00:34:29,610 --> 00:34:32,760
які він повинен завжди були на першому місці,

454
00:34:32,760 --> 00:34:35,710
Тепер ми можемо рекурсивно більш легко.

455
00:34:35,710 --> 00:34:38,960
Таким чином, ітераційний або рекурсивний, ми підемо на обох,

456
00:34:38,960 --> 00:34:46,139
але ми побачимо, що рекурсивні закінчує тим, що досить легко.

457
00:34:59,140 --> 00:35:02,480
Добре. Хто-небудь є щось, що ми можемо працювати з?

458
00:35:02,480 --> 00:35:12,000
>> [Студент] У мене є рішення ітеративним. >> Гаразд, ітераційні.

459
00:35:12,000 --> 00:35:16,030
Гаразд, це добре виглядає.

460
00:35:16,030 --> 00:35:18,920
Так що, хочете йти з нами через це?

461
00:35:18,920 --> 00:35:25,780
[Студент] Звичайно. Тому я тимчасову змінну, щоб отримати перший вузол дерева.

462
00:35:25,780 --> 00:35:28,330
А потім я просто петельні через час температура не дорівнює нулю,

463
00:35:28,330 --> 00:35:31,700
так що поки все ще був у дерево, я думаю.

464
00:35:31,700 --> 00:35:35,710
І якщо значення дорівнює значенню, температура вказує на,

465
00:35:35,710 --> 00:35:37,640
Потім він повертає це значення.

466
00:35:37,640 --> 00:35:40,210
В іншому випадку, він перевіряє, якщо він знаходиться на правій стороні або до лівої сторони.

467
00:35:40,210 --> 00:35:43,400
Якщо ви коли-небудь ситуація, коли немає більше дерев,

468
00:35:43,400 --> 00:35:47,330
Потім він повертається - він виходить з циклу і повертає брехня.

469
00:35:47,330 --> 00:35:52,190
[Боуден] Добре. Так що здається хорошим.

470
00:35:52,190 --> 00:35:58,470
Будь-який, є коментарі на що-небудь?

471
00:35:58,470 --> 00:36:02,400
У мене немає коректності коментарів взагалі.

472
00:36:02,400 --> 00:36:11,020
Єдине, що ми можемо зробити це за хлопець.

473
00:36:11,020 --> 00:36:21,660
О, він збирається піти трохи задовгий.

474
00:36:21,660 --> 00:36:33,460
Я полагоджу, що до. Добре.

475
00:36:33,460 --> 00:36:37,150
>> Кожен повинен пам'ятати, як потрійний працює.

476
00:36:37,150 --> 00:36:38,610
Там безумовно були тести в минулому

477
00:36:38,610 --> 00:36:41,170
, Які дають вам функції з потрійною оператор,

478
00:36:41,170 --> 00:36:45,750
і говорять, перевести це, робити те, що не використовується потрійний.

479
00:36:45,750 --> 00:36:49,140
Так що це дуже поширений випадок, коли я думав використовувати потрійні,

480
00:36:49,140 --> 00:36:54,610
де, якщо деякі умови встановити змінну на щось,

481
00:36:54,610 --> 00:36:58,580
ще встановити, що ж змінну на щось інше.

482
00:36:58,580 --> 00:37:03,390
Це те, що дуже часто може бути перетворена в такого роду речі

483
00:37:03,390 --> 00:37:14,420
, Де встановлено, що змінна це - або, ну, це правда? Тоді це, інакше це.

484
00:37:14,420 --> 00:37:18,550
[Студент] Перша якщо це правда, чи не так?

485
00:37:18,550 --> 00:37:25,570
[Боуден] Так. Те, як я завжди читав це, темп одно значення більше, ніж тимчасовий значення,

486
00:37:25,570 --> 00:37:30,680
то це, інакше це. Він задає питання.

487
00:37:30,680 --> 00:37:35,200
Це більше? Тоді зробіть перший крок. Решта роблять друге.

488
00:37:35,200 --> 00:37:41,670
Я майже завжди - товсту кишку, я просто - у мене в голові, я читав, як решта.

489
00:37:41,670 --> 00:37:47,180
>> Хто-небудь є рекурсивне рішення?

490
00:37:47,180 --> 00:37:49,670
Добре. Це той, який ми збираємося - це вже може бути більшим,

491
00:37:49,670 --> 00:37:53,990
але ми збираємося зробити його ще краще.

492
00:37:53,990 --> 00:37:58,720
Це в значній мірі точно такий же ідеєю.

493
00:37:58,720 --> 00:38:03,060
Це просто, ну, ти хочеш пояснити?

494
00:38:03,060 --> 00:38:08,340
[Студент] Звичайно. Таким чином, ми переконайтеся, що дерево не є нульовим першим,

495
00:38:08,340 --> 00:38:13,380
тому що, якщо дерево є нульовим, тоді вона збирається повернутися помилковим, тому що ми не знайшли його.

496
00:38:13,380 --> 00:38:19,200
І якщо є ще дерево, йдемо в - ми спочатку перевіряємо, якщо значення поточного вузла.

497
00:38:19,200 --> 00:38:23,740
Повернутися вірно, якщо вона є, і якщо не ми рекурсивно ліворуч або праворуч.

498
00:38:23,740 --> 00:38:25,970
Звучить так це необхідно? >> Угу. (Угоду)

499
00:38:25,970 --> 00:38:33,880
Так зауважити, що це майже - конструктивно дуже схожі на ітераційному розв'язанні.

500
00:38:33,880 --> 00:38:38,200
Це просто, що замість рекурсії, у нас був час циклу.

501
00:38:38,200 --> 00:38:40,840
І справа тут базу, де дерев не однаково NULL

502
00:38:40,840 --> 00:38:44,850
була умова, при якому ми вирвалися з циклу.

503
00:38:44,850 --> 00:38:50,200
Вони дуже схожі. Але ми збираємося зробити ще один крок вперед.

504
00:38:50,200 --> 00:38:54,190
Тепер ми робимо те ж саме і тут.

505
00:38:54,190 --> 00:38:57,680
Зверніть увагу, ми повертаємося одне і те ж в обох цих рядків,

506
00:38:57,680 --> 00:39:00,220
за винятком одного аргументу інший.

507
00:39:00,220 --> 00:39:07,950
Так що ми збираємося зробити це в потрійному.

508
00:39:07,950 --> 00:39:13,790
Я вдарив варіант щось, і він зробив символом. Добре.

509
00:39:13,790 --> 00:39:21,720
Так що ми збираємося повернутися містить цьому.

510
00:39:21,720 --> 00:39:28,030
Це стає бути кілька рядків, а, збільшеної в цьому є.

511
00:39:28,030 --> 00:39:31,060
Як правило, в якості стилістичного річ, я не думаю, що багато людей

512
00:39:31,060 --> 00:39:38,640
поставити пробіл після стрілки, але я думаю, якщо ви послідовні, це прекрасно.

513
00:39:38,640 --> 00:39:44,320
Якщо значення менше, ніж значення дерева, ми хочемо, щоб рекурсивно по дереву зліва,

514
00:39:44,320 --> 00:39:53,890
ще ми хочемо, щоб рекурсивно по дереву права.

515
00:39:53,890 --> 00:39:58,610
Так що було кроком одним з рішень цієї виглядати менше.

516
00:39:58,610 --> 00:40:02,660
Другий крок зробити цей вид менше -

517
00:40:02,660 --> 00:40:09,150
ми можемо розділити це на кілька рядків.

518
00:40:09,150 --> 00:40:16,500
Добре. Крок два роблячи його схожим менше тут,

519
00:40:16,500 --> 00:40:25,860
так що повернене значення дорівнює дерево значення, чи містить завгодно.

520
00:40:25,860 --> 00:40:28,340
>> Це важлива річ.

521
00:40:28,340 --> 00:40:30,860
Я не впевнений, якщо б він сказав, що це в явному вигляді в класі,

522
00:40:30,860 --> 00:40:34,740
але це називається коротке замикання оцінки.

523
00:40:34,740 --> 00:40:41,060
Ідея тут полягає значення == дерева значення.

524
00:40:41,060 --> 00:40:49,960
Якщо це правда, то це дійсно так, і ми хочемо »або« що з тим, що є тут.

525
00:40:49,960 --> 00:40:52,520
Таким чином, навіть не думаючи про все, що знаходиться тут,

526
00:40:52,520 --> 00:40:55,070
що всі вираз збирається повернутися?

527
00:40:55,070 --> 00:40:59,430
[Студент] True? >> Так, тому що істинне нічого,

528
00:40:59,430 --> 00:41:04,990
з'єднані через АБО - або істинний з'єднані через АБО з чим обов'язково вірно.

529
00:41:04,990 --> 00:41:08,150
Тому, як тільки ми бачимо, повертається значення = Дерево значення,

530
00:41:08,150 --> 00:41:10,140
ми тільки збираємося повернутися вірно.

531
00:41:10,140 --> 00:41:15,710
Навіть не збираюся рекурсивно додатково містить по лінії.

532
00:41:15,710 --> 00:41:20,980
Ми можемо прийняти це ще один крок вперед.

533
00:41:20,980 --> 00:41:29,490
Повернутися дерево не дорівнює NULL і все це.

534
00:41:29,490 --> 00:41:32,650
Він зробив це один рядок функції.

535
00:41:32,650 --> 00:41:36,790
Це також приклад короткого замикання оцінки.

536
00:41:36,790 --> 00:41:40,680
Але тепер це та ж сама ідея -

537
00:41:40,680 --> 00:41:47,320
замість того, щоб - так, якщо дерево не дорівнює NULL - або, ну,

538
00:41:47,320 --> 00:41:49,580
якщо дерево має рівні нулю, що є поганою випадок,

539
00:41:49,580 --> 00:41:54,790
якщо дерево дорівнює нулю, то перша умова буде хибним.

540
00:41:54,790 --> 00:42:00,550
Так помилкова операція AND з чим буде що?

541
00:42:00,550 --> 00:42:04,640
[Студент] False. >> Да. Це інша половина короткого замикання оцінки,

542
00:42:04,640 --> 00:42:10,710
де, якщо дерево не дорівнюють нулю, то ми не збираємося навіть піти -

543
00:42:10,710 --> 00:42:14,930
або якщо дерево має рівні нулю, то ми не збираємося робити значення == дерева значення.

544
00:42:14,930 --> 00:42:17,010
Ми просто збираємося, щоб негайно повернутися помилковим.

545
00:42:17,010 --> 00:42:20,970
Що важливо, так як якщо це не коротке замикання оцінки,

546
00:42:20,970 --> 00:42:25,860
потім, якщо дерево має рівні нулю, це друга умова буде вини сегмента,

547
00:42:25,860 --> 00:42:32,510
тому що дерево-> значення разименованія NULL.

548
00:42:32,510 --> 00:42:40,490
Так ось що. Можете зробити це - перейти рази старше.

549
00:42:40,490 --> 00:42:44,840
Це дуже звична річ, також, не робить це один Відповідно до цього,

550
00:42:44,840 --> 00:42:49,000
але це звичайна справа в умовах, може бути, не прямо тут,

551
00:42:49,000 --> 00:42:59,380
але якщо (дерево! = NULL, і дерево-> значення == значення), робити що завгодно.

552
00:42:59,380 --> 00:43:01,560
Це дуже поширене захворювання, де замість того,

553
00:43:01,560 --> 00:43:06,770
розірвати її на дві IFS, де завгодно, це дерево нуль?

554
00:43:06,770 --> 00:43:11,780
Гаразд, це не нульовий, так що тепер це дерево значення, рівного вартості? Зробіть це.

555
00:43:11,780 --> 00:43:17,300
Замість цього стану, цього ніколи не буде сегментам вина

556
00:43:17,300 --> 00:43:21,220
тому що він вирветься назовні, якщо це відбудеться, є недійсними.

557
00:43:21,220 --> 00:43:24,000
Ну, я думаю, якщо ваше дерево зовсім невірний покажчик, він все ще може сегментам вина,

558
00:43:24,000 --> 00:43:26,620
але вона не може сегментам вина, якщо дерево є недійсним.

559
00:43:26,620 --> 00:43:32,900
Якби це був нульовим, це порушило б перш, ніж ви коли-небудь разименован покажчик на перше місце.

560
00:43:32,900 --> 00:43:35,000
[Студент] Це званих ледачих оцінки?

561
00:43:35,000 --> 00:43:40,770
>> [Боуден] Ледачі обчислення окрема річ.

562
00:43:40,770 --> 00:43:49,880
Ледачі обчислення більш, як ви просите значення,

563
00:43:49,880 --> 00:43:54,270
Ви запитаєте для обчислення значення, свого роду, але ви не повинні його негайно.

564
00:43:54,270 --> 00:43:59,040
Так що, поки ви насправді потрібно, воно не обчислюється.

565
00:43:59,040 --> 00:44:03,920
Це не зовсім те ж саме, але в Хаффман PSET,

566
00:44:03,920 --> 00:44:06,520
він говорить, що ми "ліниво" писати.

567
00:44:06,520 --> 00:44:08,670
Тому ми робимо це тому, що ми насправді буферизації запису -

568
00:44:08,670 --> 00:44:11,820
Ми не хочемо, щоб написати окремі біти в той час,

569
00:44:11,820 --> 00:44:15,450
або окремих байтів за раз, замість цього ми хочемо отримати шматок байт.

570
00:44:15,450 --> 00:44:19,270
Потім, коли у нас є шматок байт, то ми будемо його виписувати.

571
00:44:19,270 --> 00:44:22,640
Навіть якщо ви попросите його написати - і FWRITE і FREAD зробити таку ж річ.

572
00:44:22,640 --> 00:44:26,260
Вони буфер вашого читання і запису.

573
00:44:26,260 --> 00:44:31,610
Навіть якщо ви попросите його написати відразу, він, ймовірно, не буде.

574
00:44:31,610 --> 00:44:34,540
І ви не можете бути впевнені, що речі будуть написані

575
00:44:34,540 --> 00:44:37,540
до виклику hfclose або що це таке,

576
00:44:37,540 --> 00:44:39,620
які потім каже, гаразд, я закриваю свій файл,

577
00:44:39,620 --> 00:44:43,450
це означає, що мені краще написати все, що я ще не написана.

578
00:44:43,450 --> 00:44:45,770
Це не потрібно писати все з

579
00:44:45,770 --> 00:44:49,010
поки ви не закриваєте файл, а потім це необхідно.

580
00:44:49,010 --> 00:44:56,220
Так що це саме те, що лінь - він чекає, поки це має статися.

581
00:44:56,220 --> 00:44:59,990
Це - взяти 51 і ви будете входити в його більш докладно,

582
00:44:59,990 --> 00:45:05,470
тому що OCaml і все в 51, все рекурсії.

583
00:45:05,470 --> 00:45:08,890
Є ніяких ітераційного рішення, в основному.

584
00:45:08,890 --> 00:45:11,550
Всі рекурсії і ледачі обчислення

585
00:45:11,550 --> 00:45:14,790
буде важливим для багатьох обставин

586
00:45:14,790 --> 00:45:19,920
де, якщо не ліниво оцінку, це буде означати -

587
00:45:19,920 --> 00:45:24,760
Прикладом є потоків, які є нескінченно довго.

588
00:45:24,760 --> 00:45:30,990
У теорії, ви можете думати про натуральних чисел у вигляді потоку 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Так ліниво оцінювати речі в порядку.

590
00:45:33,090 --> 00:45:37,210
Якщо я кажу, я хочу десятого числа, то я можу оцінити до десятого числа.

591
00:45:37,210 --> 00:45:40,300
Якщо я хочу в сотий номер, то я можу оцінити до сотого номера.

592
00:45:40,300 --> 00:45:46,290
Без ледачих обчислень, то він буде намагатися оцінити всі номери відразу.

593
00:45:46,290 --> 00:45:50,000
Ти оцінці нескінченно багато чисел, і це просто не можливо.

594
00:45:50,000 --> 00:45:52,080
Таким чином, є багато випадків, коли ліниві обчислення

595
00:45:52,080 --> 00:45:57,840
просто необхідно для отримання речей на роботу.

596
00:45:57,840 --> 00:46:05,260
>> Тепер ми хочемо написати вставку, де вставка буде

597
00:46:05,260 --> 00:46:08,430
Аналогічно зміни в його визначенні.

598
00:46:08,430 --> 00:46:10,470
Так що зараз це BOOL вставки (цілочисельне значення).

599
00:46:10,470 --> 00:46:23,850
Ми збираємося змінити це BOOL вставки (цілочисельне значення, вузол * дерево).

600
00:46:23,850 --> 00:46:29,120
Ми дійсно збираємося змінити це знову в трохи, ми побачимо, чому.

601
00:46:29,120 --> 00:46:32,210
І давайте перейдемо build_node, просто заради цього,

602
00:46:32,210 --> 00:46:36,730
вставити вище, тому ми не повинні написати прототип функції.

603
00:46:36,730 --> 00:46:42,450
Які це натяк, що ви збираєтеся використовувати build_node в вставки.

604
00:46:42,450 --> 00:46:49,590
Добре. Зупиніться на хвилинку за це.

605
00:46:49,590 --> 00:46:52,130
Я думаю, що я врятував редакції, якщо ви хочете, щоб витягнути з цього,

606
00:46:52,130 --> 00:47:00,240
або, принаймні, я зробив зараз.

607
00:47:00,240 --> 00:47:04,190
Я хотіла невелику перерву, щоб думати про логіку вставки,

608
00:47:04,190 --> 00:47:08,750
якщо ви не можете думати про це.

609
00:47:08,750 --> 00:47:12,860
В принципі, ви тільки коли-небудь вставки на листках.

610
00:47:12,860 --> 00:47:18,640
Мовляв, якщо я вставляю 1, то я неминуче буде вставка 1 -

611
00:47:18,640 --> 00:47:21,820
Я зміню в чорному - I'll бути вставка 1 над тут.

612
00:47:21,820 --> 00:47:28,070
Або, якщо я вставляю 4, я хочу, щоб вставка 4 над тут.

613
00:47:28,070 --> 00:47:32,180
Так що не має значення, що ви робите, ви будете вставки на аркуш.

614
00:47:32,180 --> 00:47:36,130
Все, що вам потрібно зробити, це ітерації вниз по дереву, поки не дійдете до вузла

615
00:47:36,130 --> 00:47:40,890
, Які повинні бути батьком вузла, батько нового вузла,

616
00:47:40,890 --> 00:47:44,560
, А потім змінити її вліво або вправо, покажчик, в залежності від того,

617
00:47:44,560 --> 00:47:47,060
це більше або менше поточного вузла.

618
00:47:47,060 --> 00:47:51,180
Змінити цей покажчик, щоб вказати на новий вузол.

619
00:47:51,180 --> 00:48:05,490
Таким чином, ітерації по дереву, зробити кінцевий пункт нового вузла.

620
00:48:05,490 --> 00:48:09,810
Крім того, думаю про те, чому, який забороняє тип ситуації і колись,

621
00:48:09,810 --> 00:48:17,990
де я побудував двійкового дерева, де це було правильно

622
00:48:17,990 --> 00:48:19,920
якщо ви дивилися тільки на одному вузлі,

623
00:48:19,920 --> 00:48:24,830
але 9 був зліва від 7, якщо ви повторних вниз до упору.

624
00:48:24,830 --> 00:48:29,770
Так, що це неможливо в цій ситуації, так як -

625
00:48:29,770 --> 00:48:32,530
думаю про встановлення 9 або щось; на самому першому вузлі,

626
00:48:32,530 --> 00:48:35,350
Я збираюся дивитися 7, і я просто збираюся йти з правого боку.

627
00:48:35,350 --> 00:48:38,490
Так що не має значення, що мені робити, якщо я вставка, перейшовши на лист,

628
00:48:38,490 --> 00:48:40,790
і листя допомогою відповідного алгоритму,

629
00:48:40,790 --> 00:48:43,130
це буде для мене неможливо вставити 9 до лівого з 7

630
00:48:43,130 --> 00:48:48,250
тому що як тільки я потрапив 7 я піду направо.

631
00:48:59,740 --> 00:49:02,070
Хто-небудь є щось почати?

632
00:49:02,070 --> 00:49:05,480
[Студент] я роблю. >> Звичайно.

633
00:49:05,480 --> 00:49:09,200
[Студент, нерозбірливо]

634
00:49:09,200 --> 00:49:14,390
[Інший студент, нерозбірливо]

635
00:49:14,390 --> 00:49:18,330
[Боуден] Це цінується. Добре. Хочете пояснити?

636
00:49:18,330 --> 00:49:20,690
>> [Студент] Оскільки ми знаємо, що ми вставка

637
00:49:20,690 --> 00:49:24,060
нові вузли в кінці дерева,

638
00:49:24,060 --> 00:49:28,070
Я петлю по дереву итеративно

639
00:49:28,070 --> 00:49:31,360
поки я не дістався до вузла, який вказав на нуль.

640
00:49:31,360 --> 00:49:34,220
І тоді я вирішив поставити його або на правій, або з лівої сторони

641
00:49:34,220 --> 00:49:37,420
використання цього права змінна, вона сказала мені, куди його покласти.

642
00:49:37,420 --> 00:49:41,850
І тоді, по суті, я тільки що зробив, що в минулому -

643
00:49:41,850 --> 00:49:47,520
цієї точки температура вузла на новий вузол, який він створює,

644
00:49:47,520 --> 00:49:50,770
або на лівій стороні або на правій стороні, в залежності від того, що значення прав був.

645
00:49:50,770 --> 00:49:56,530
Нарешті, я встановив нове значення вузла до вартості його тестування.

646
00:49:56,530 --> 00:49:59,550
[Боуден] Отже, я бачу одне питання тут.

647
00:49:59,550 --> 00:50:02,050
Це як 95% шляху.

648
00:50:02,050 --> 00:50:07,550
Одне питання, який я бачу, ну, хто-небудь ще бачив проблеми?

649
00:50:07,550 --> 00:50:18,400
Що таке обставина, при яких вони вирватися з петлі?

650
00:50:18,400 --> 00:50:22,100
[Студент] Якщо температура є недійсним? >> Да. Отже, як ви вирватися з петлі, якщо температура є недійсним.

651
00:50:22,100 --> 00:50:30,220
Але те, що я роблю тут?

652
00:50:30,220 --> 00:50:35,410
Я разименованія температура, яка неминуче нульовий.

653
00:50:35,410 --> 00:50:39,840
Таким чином, інші, що вам потрібно зробити, це не просто відстежувати, поки температура порожній,

654
00:50:39,840 --> 00:50:45,590
Ви хочете, щоб стежити за батьків у всі часи.

655
00:50:45,590 --> 00:50:52,190
Ми також хочемо батьківський вузол *, я думаю, ми можемо зберегти, що при нульових на перший погляд.

656
00:50:52,190 --> 00:50:55,480
Це матиме дивну поведінку для кореня дерева,

657
00:50:55,480 --> 00:50:59,210
але ми повернемося до цього.

658
00:50:59,210 --> 00:51:03,950
Якщо значення більше, ніж будь-який інший, то Temp = Температура права.

659
00:51:03,950 --> 00:51:07,910
Але перш ніж ми це зробимо, батько = темп.

660
00:51:07,910 --> 00:51:14,500
Або батьки завжди будуть рівні температурі? Чи так це?

661
00:51:14,500 --> 00:51:19,560
Якщо температура не є нульовим, то я буду рухатися вниз, незважаючи ні на що,

662
00:51:19,560 --> 00:51:24,030
до вузла, для якого тимчасовий батьків.

663
00:51:24,030 --> 00:51:27,500
Таким чином, батько це буде тимчасовий, а потім рухатися темп вниз.

664
00:51:27,500 --> 00:51:32,410
Зараз температура є дійсним, але батько вказує на батька те, що є нульовим.

665
00:51:32,410 --> 00:51:39,110
Так що тут, я не хочу, щоб встановити право дорівнює 1.

666
00:51:39,110 --> 00:51:41,300
Так я переїхав в праву, так що якщо правий = 1,

667
00:51:41,300 --> 00:51:45,130
і я думаю, ви також хочете робити -

668
00:51:45,130 --> 00:51:48,530
якщо рухатися вліво, ви хочете встановити права дорівнюють 0.

669
00:51:48,530 --> 00:51:55,950
Або ж, якщо ви коли-небудь рухатися вправо.

670
00:51:55,950 --> 00:51:58,590
Таким чином, право = 0. Якщо право = 1,

671
00:51:58,590 --> 00:52:04,260
Тепер ми хочемо, щоб батьки право newnode покажчик,

672
00:52:04,260 --> 00:52:08,520
ще ми хочемо, щоб батьки лівої newnode покажчик.

673
00:52:08,520 --> 00:52:16,850
Питань з цього приводу?

674
00:52:16,850 --> 00:52:24,880
Добре. Отже, це те, як ми - ну, насправді, а не робити цього,

675
00:52:24,880 --> 00:52:29,630
Ми майже очікував використовувати build_node.

676
00:52:29,630 --> 00:52:40,450
І потім, якщо newnode дорівнює нулю, повернутися помилковим.

677
00:52:40,450 --> 00:52:44,170
Ось і все. Тепер, це те, що ми очікували, що ви робите.

678
00:52:44,170 --> 00:52:47,690
>> Це те, що співробітники рішень роблять.

679
00:52:47,690 --> 00:52:52,360
Я не згоден з цим, як "правильний" спосіб йти про нього

680
00:52:52,360 --> 00:52:57,820
Але це чудово, і вона буде працювати.

681
00:52:57,820 --> 00:53:02,840
Єдине, що трохи дивно прямо зараз

682
00:53:02,840 --> 00:53:08,310
якщо дерево починається як нульові, ми передаємо в нульове дерево.

683
00:53:08,310 --> 00:53:12,650
Я думаю, це залежить від того, як визначати поведінку проходять в нульових дерева.

684
00:53:12,650 --> 00:53:15,490
Я думаю, що якщо ви проходите в нульове дерево,

685
00:53:15,490 --> 00:53:17,520
потім вставити значення в нульовий дерева

686
00:53:17,520 --> 00:53:23,030
треба просто повернути дерево, де єдина цінність у тому, що один вузол.

687
00:53:23,030 --> 00:53:25,830
У людей з цим згодні? Ви могли б, якщо б ви хотіли,

688
00:53:25,830 --> 00:53:28,050
якщо ви проходите в нульове дерево

689
00:53:28,050 --> 00:53:31,320
і ви хочете вставити значення в ній, повернутися помилковим.

690
00:53:31,320 --> 00:53:33,830
Це до вас, щоб визначити, що.

691
00:53:33,830 --> 00:53:38,320
Для цього перше, що я сказав, а потім -

692
00:53:38,320 --> 00:53:40,720
добре, ви будете мати проблеми роблять це, тому що

693
00:53:40,720 --> 00:53:44,090
було б легше, якби ми мали глобальний покажчик на річ,

694
00:53:44,090 --> 00:53:48,570
але у нас немає, так що якщо дерево є нульовим, то ми нічого не можемо з цим зробити.

695
00:53:48,570 --> 00:53:50,960
Ми можемо просто повернутися помилковим.

696
00:53:50,960 --> 00:53:52,840
Так що я збираюся змінити вставки.

697
00:53:52,840 --> 00:53:56,540
Ми технічно міг би просто змінити це прямо тут,

698
00:53:56,540 --> 00:53:58,400
як це ітерації речі,

699
00:53:58,400 --> 00:54:04,530
але я збираюся змінити вставки прийняти вузла ** дерево.

700
00:54:04,530 --> 00:54:07,510
Двомісний покажчиків.

701
00:54:07,510 --> 00:54:09,710
Що це значить?

702
00:54:09,710 --> 00:54:12,330
Замість того, щоб мати справу з покажчиками на вузли,

703
00:54:12,330 --> 00:54:16,690
що я збираюся бути маніпулювання це покажчик.

704
00:54:16,690 --> 00:54:18,790
Я збираюся бути маніпулювання цей покажчик.

705
00:54:18,790 --> 00:54:21,770
Я збираюся бути маніпуляцій покажчиками напряму.

706
00:54:21,770 --> 00:54:25,760
Це має сенс, оскільки, думаю про вниз -

707
00:54:25,760 --> 00:54:33,340
Ну, зараз це вказує на нуль.

708
00:54:33,340 --> 00:54:38,130
Те, що я хочу зробити, це управляти цією покажчик, щоб вказати на не нульовий.

709
00:54:38,130 --> 00:54:40,970
Я хочу, щоб вона вказувала на моєму новому вузлі.

710
00:54:40,970 --> 00:54:44,870
Якби я просто стежити за покажчиками на мій покажчиків,

711
00:54:44,870 --> 00:54:47,840
то мені не потрібно стежити за предка.

712
00:54:47,840 --> 00:54:52,640
Я можу тільки стежити, щоб переконатися, що покажчик направлений до нуля,

713
00:54:52,640 --> 00:54:54,580
і якщо покажчик вказує на нуль,

714
00:54:54,580 --> 00:54:57,370
змінити його, щоб вказати на вузол я хочу.

715
00:54:57,370 --> 00:55:00,070
І я можу змінити його, так як у мене є покажчик на покажчик.

716
00:55:00,070 --> 00:55:02,040
Давайте подивимося це прямо зараз.

717
00:55:02,040 --> 00:55:05,470
Ви дійсно можете зробити це рекурсивно досить легко.

718
00:55:05,470 --> 00:55:08,080
Чи хочемо ми це зробити?

719
00:55:08,080 --> 00:55:10,980
Так, ми робимо.

720
00:55:10,980 --> 00:55:16,790
>> Давайте подивимося, що рекурсивно.

721
00:55:16,790 --> 00:55:24,070
По-перше, те, що наш базовий сценарій буде?

722
00:55:24,070 --> 00:55:29,140
Майже завжди наш базовий сценарій, але насправді, це ніби складно.

723
00:55:29,140 --> 00:55:34,370
Насамперед, якщо (дерево == NULL)

724
00:55:34,370 --> 00:55:37,550
Я думаю, ми просто збираємося, щоб повернутися помилковим.

725
00:55:37,550 --> 00:55:40,460
Це відрізняється від вашого дерева бути нульовим.

726
00:55:40,460 --> 00:55:44,510
Це покажчик на кореневий покажчик бути нульовим

727
00:55:44,510 --> 00:55:48,360
Це означає, що ваш кореневої покажчик не існує.

728
00:55:48,360 --> 00:55:52,390
Так що тут, якщо я роблю

729
00:55:52,390 --> 00:55:55,760
вузол * - давайте просто повторно використовувати цей.

730
00:55:55,760 --> 00:55:58,960
Node * корінь = NULL,

731
00:55:58,960 --> 00:56:00,730
і тоді я буду називати вставки, роблячи щось подібне,

732
00:56:00,730 --> 00:56:04,540
вставте 4 і в корені.

733
00:56:04,540 --> 00:56:06,560
Так і кореня, якщо корінь вузол *

734
00:56:06,560 --> 00:56:11,170
то і корінь буде вузлом. **

735
00:56:11,170 --> 00:56:15,120
Це справедливо. У цьому випадку, дерево, тут,

736
00:56:15,120 --> 00:56:20,120
Дерево не порожній - або вставки.

737
00:56:20,120 --> 00:56:24,630
Тут. Дерево не є нульовим; * Дерево є недійсним, і це добре

738
00:56:24,630 --> 00:56:26,680
тому що, якщо * Дерево є нульовим, то я можу керувати ним

739
00:56:26,680 --> 00:56:29,210
в даний час вказують на те, що я хочу, щоб це вказують.

740
00:56:29,210 --> 00:56:34,750
Але якщо дерево є порожнім, це означає, що я тільки що прийшов сюди і сказав, нульовий.

741
00:56:34,750 --> 00:56:42,710
Це не має сенсу. Я нічого не можу зробити з цим.

742
00:56:42,710 --> 00:56:45,540
Якщо дерево є порожнім, повернутися помилковим.

743
00:56:45,540 --> 00:56:48,220
Так що я в принципі вже говорив, що наші реальні справи бази.

744
00:56:48,220 --> 00:56:50,580
І що це буде?

745
00:56:50,580 --> 00:56:55,030
[Студент, нерозбірливо]

746
00:56:55,030 --> 00:57:00,000
[Боуден] Так. Так що, якщо (* дерево == NULL).

747
00:57:00,000 --> 00:57:04,520
Це відноситься до випадку тут

748
00:57:04,520 --> 00:57:09,640
де, якщо мій червоний покажчик вказує я зосереджений на,

749
00:57:09,640 --> 00:57:12,960
так як я зосереджений на цей покажчик, зараз я зосереджений на цей покажчик.

750
00:57:12,960 --> 00:57:15,150
Зараз я зосереджений на цей покажчик.

751
00:57:15,150 --> 00:57:18,160
Так що, якщо мій червоний покажчик, який є моїм ** вузла,

752
00:57:18,160 --> 00:57:22,880
це все - якщо *, моя червона стрілка, це ніколи не нульовий,

753
00:57:22,880 --> 00:57:28,470
це означає, що я перебуваю в тому випадку, коли я зосереджений на покажчик, який вказує -

754
00:57:28,470 --> 00:57:32,530
це покажчик, який належить аркуша.

755
00:57:32,530 --> 00:57:41,090
Я хочу змінити цей покажчик, щоб вказати на моєму новому вузлі.

756
00:57:41,090 --> 00:57:45,230
Приходьте сюди.

757
00:57:45,230 --> 00:57:56,490
Мій newnode буде просто вузол * п = build_node (вартість)

758
00:57:56,490 --> 00:58:07,300
Потім п, якщо п = NULL, повертає брехня.

759
00:58:07,300 --> 00:58:12,600
Решту ми хочемо змінити те, що покажчик в даний момент вказує

760
00:58:12,600 --> 00:58:17,830
в даний час вказують на нашому новому вузлі.

761
00:58:17,830 --> 00:58:20,280
Ми можемо реально зробити це тут.

762
00:58:20,280 --> 00:58:30,660
Замість того щоб сказати я, ми говоримо * = дерево, якщо дерево *.

763
00:58:30,660 --> 00:58:35,450
Всі розуміють, що? Це, маючи справу з покажчиками на покажчики,

764
00:58:35,450 --> 00:58:40,750
ми можемо змінити нульові покажчики вказують на те, що ми хочемо, щоб вони вказують.

765
00:58:40,750 --> 00:58:42,820
Це наш базовий сценарій.

766
00:58:42,820 --> 00:58:45,740
>> Тепер наші рецидиву, або наш рекурсії,

767
00:58:45,740 --> 00:58:51,430
буде дуже схожий на всі інші рекурсії ми робили.

768
00:58:51,430 --> 00:58:55,830
Ми збираємося хочете вставити значення,

769
00:58:55,830 --> 00:58:59,040
і тепер я збираюся використовувати потрійні знову, але те, що наша умова буде?

770
00:58:59,040 --> 00:59:05,180
Що це ми шукаємо вирішити, чи хочемо ми йти вліво або вправо?

771
00:59:05,180 --> 00:59:07,760
Давайте робити це в окремих кроків.

772
00:59:07,760 --> 00:59:18,850
Якщо (значення <) що?

773
00:59:18,850 --> 00:59:23,200
[Студент] Значення дерево?

774
00:59:23,200 --> 00:59:27,490
[Боуден] Тому пам'ятайте, що я в даний час -

775
00:59:27,490 --> 00:59:31,260
[Студенти, нерозбірливо]

776
00:59:31,260 --> 00:59:34,140
[Боуден] Так, так прямо тут, скажемо, що ця зелена стрілка

777
00:59:34,140 --> 00:59:39,050
є прикладом того, що дерево в даний час, є покажчиком на цей покажчик.

778
00:59:39,050 --> 00:59:46,610
Таким чином, це означає, що я покажчик на покажчик до 3.

779
00:59:46,610 --> 00:59:48,800
Разименованія двічі звучало добре.

780
00:59:48,800 --> 00:59:51,010
Що мені - як я можу це зробити?

781
00:59:51,010 --> 00:59:53,210
[Студент] Dereference один раз, а потім зробити стрілки таким чином?

782
00:59:53,210 --> 00:59:58,420
[Боуден] Таким чином, (* дерево) є разименованія один раз, -> значення

783
00:59:58,420 --> 01:00:05,960
збирається дати мені значення вузла, що я побічно вказує.

784
01:00:05,960 --> 01:00:11,980
Так що я теж можу писати ** tree.value, якщо ви віддаєте перевагу це.

785
01:00:11,980 --> 01:00:18,490
Або працює.

786
01:00:18,490 --> 01:00:26,190
Якщо це так, то я хочу звернути вставити зі значенням.

787
01:00:26,190 --> 01:00:32,590
І те, що мій оновлений вузол ** буде?

788
01:00:32,590 --> 01:00:39,440
Я хочу піти наліво, так ** tree.left буде ліворуч від мене.

789
01:00:39,440 --> 01:00:41,900
І я хочу, покажчик на цю річ

790
01:00:41,900 --> 01:00:44,930
так що якщо ліва закінчує тим, що нульовий покажчик,

791
01:00:44,930 --> 01:00:48,360
Я можу змінити його, щоб вказати на моєму новому вузлі.

792
01:00:48,360 --> 01:00:51,460
>> І в іншому випадку можуть бути дуже схожі.

793
01:00:51,460 --> 01:00:55,600
Давайте реально зробити, що мій потрійний прямо зараз.

794
01:00:55,600 --> 01:01:04,480
Вставте значення, якщо значення <(** дерево). Значення.

795
01:01:04,480 --> 01:01:11,040
Потім ми хочемо оновити нашу ** вліво,

796
01:01:11,040 --> 01:01:17,030
ще ми хочемо оновити нашу ** вправо.

797
01:01:17,030 --> 01:01:22,540
[Студент] Чи означає це, що отримати покажчик на покажчик?

798
01:01:22,540 --> 01:01:30,940
[Боуден] Пам'ятайте, що - ** tree.right є вузлом зірки.

799
01:01:30,940 --> 01:01:35,040
[Студент, нерозбірливо] >> Да.

800
01:01:35,040 --> 01:01:41,140
** Tree.right, як цей покажчик або щось.

801
01:01:41,140 --> 01:01:45,140
Таким чином, приймаючи покажчик на те, що це дає мені те, що я хочу

802
01:01:45,140 --> 01:01:50,090
покажчика на цього хлопця.

803
01:01:50,090 --> 01:01:54,260
[Студент] Чи можемо ми піти знову, чому ми використовуємо два покажчика?

804
01:01:54,260 --> 01:01:58,220
[Боуден] Так. Так що - ні, ви можете, і це рішення до

805
01:01:58,220 --> 01:02:04,540
був спосіб зробити це, не роблячи двох покажчиків.

806
01:02:04,540 --> 01:02:08,740
Ви повинні бути в змозі зрозуміти за допомогою двох покажчиків,

807
01:02:08,740 --> 01:02:11,660
і це чисте рішення.

808
01:02:11,660 --> 01:02:16,090
Крім того, зауважив, що те, що відбувається, якщо моє дерево -

809
01:02:16,090 --> 01:02:24,480
Що станеться, якщо мій корінь був нульовим? Що станеться, якщо я зроблю це випадок прямо тут?

810
01:02:24,480 --> 01:02:30,540
Таким чином, вузол * корінь = NULL, вставте 4 і в корені.

811
01:02:30,540 --> 01:02:35,110
Те, що корінь буде після цього?

812
01:02:35,110 --> 01:02:37,470
[Студент, нерозбірливо] >> Да.

813
01:02:37,470 --> 01:02:41,710
Коренева значення буде 4.

814
01:02:41,710 --> 01:02:45,510
Коренева лівого буде нульовим, корінь право буде нульовим.

815
01:02:45,510 --> 01:02:49,490
У разі, коли ми не пройшли корінь за адресою,

816
01:02:49,490 --> 01:02:52,490
ми не могли змінити корінь.

817
01:02:52,490 --> 01:02:56,020
У разі, коли дерево - де корінь був нульовим,

818
01:02:56,020 --> 01:02:58,410
ми просто повинні були повернутися помилковим. Там немає нічого, що ми могли зробити.

819
01:02:58,410 --> 01:03:01,520
Ми не можемо вставити вузол в порожнє дерево.

820
01:03:01,520 --> 01:03:06,810
Але тепер ми можемо, ми просто зробити порожнє дерево в одній вузла дерева.

821
01:03:06,810 --> 01:03:13,400
Яка зазвичай очікуваним чином, що воно має працювати.

822
01:03:13,400 --> 01:03:21,610
>> Крім того, це значно менше, ніж

823
01:03:21,610 --> 01:03:26,240
Також стежити за батьками, і тому ви ітерації до упору.

824
01:03:26,240 --> 01:03:30,140
Тепер у мене є мої батьки, і я просто мої батьки право покажчик на що завгодно.

825
01:03:30,140 --> 01:03:35,640
Замість цього, якщо б ми робили це багато разів, це було б те ж ідею з циклу.

826
01:03:35,640 --> 01:03:38,100
Але замість того, щоб мати справу з моїми батьками покажчик,

827
01:03:38,100 --> 01:03:40,600
Замість мого поточного покажчика б річ

828
01:03:40,600 --> 01:03:43,790
що я безпосередньо змінювати, щоб вказати на моєму новому вузлі.

829
01:03:43,790 --> 01:03:46,090
Я не доводиться мати справу з того, що це вказує на лівому.

830
01:03:46,090 --> 01:03:48,810
Я не доводиться мати справу з того, що це вказує на права.

831
01:03:48,810 --> 01:04:00,860
Це просто, що цей покажчик, я збираюся встановити його, щоб вказати на моєму новому вузлі.

832
01:04:00,860 --> 01:04:05,740
Всі розуміють, як це працює?

833
01:04:05,740 --> 01:04:09,460
Якщо ні, то чому ми хочемо зробити це таким чином,

834
01:04:09,460 --> 01:04:14,920
але принаймні, що це працює як рішення?

835
01:04:14,920 --> 01:04:17,110
[Студент] Куди ми повертаємося правда?

836
01:04:17,110 --> 01:04:21,550
[Боуден] Це, напевно, прямо тут.

837
01:04:21,550 --> 01:04:26,690
Якщо ми правильно вставити його, повернути істинний.

838
01:04:26,690 --> 01:04:32,010
В іншому випадку, тут ми збираємося хочете повернути все повертається вставки.

839
01:04:32,010 --> 01:04:35,950
>> А що особливого в цій рекурсивної функції?

840
01:04:35,950 --> 01:04:43,010
Це хвіст рекурсивної, так як поки ми складаємо з деякої оптимізації,

841
01:04:43,010 --> 01:04:48,060
вона буде визнати, що і ви ніколи не отримаєте переповнення стека з цього,

842
01:04:48,060 --> 01:04:53,230
навіть якщо наше дерево має висоту 10.000 чи 10 мільйонів.

843
01:04:53,230 --> 01:04:55,630
[Студент, нерозбірливо]

844
01:04:55,630 --> 01:05:00,310
[Боуден] Я думаю, що він це робить на Dash - або те, що рівень оптимізації

845
01:05:00,310 --> 01:05:03,820
вимагається для хвостовій рекурсії щоб бути визнаним.

846
01:05:03,820 --> 01:05:09,350
Я думаю, що він визнає - GCC і Clang

847
01:05:09,350 --> 01:05:12,610
Також мають різні значення для їх рівня оптимізації.

848
01:05:12,610 --> 01:05:17,870
Я хочу сказати, що це Дашо 2, переконатися, що він не визнає хвостовій рекурсії.

849
01:05:17,870 --> 01:05:27,880
Але ми - ви можете побудувати, як наприклад Fibonocci або щось.

850
01:05:27,880 --> 01:05:30,030
Це не легко перевірити за цим, тому що це важко побудувати

851
01:05:30,030 --> 01:05:32,600
бінарне дерево, що такий великий.

852
01:05:32,600 --> 01:05:37,140
Але так, я думаю, що це Дашо 2,

853
01:05:37,140 --> 01:05:40,580
Якщо ви компілюєте з Дашо 2, він буде шукати хвостову рекурсію

854
01:05:40,580 --> 01:05:54,030
і оптимізувати це.

855
01:05:54,030 --> 01:05:58,190
Давайте повернемося до - вставити буквально останнім, що йому потрібно.

856
01:05:58,190 --> 01:06:04,900
Давайте повернемося до вставці тут

857
01:06:04,900 --> 01:06:07,840
де ми збираємося робити ту ж ідею.

858
01:06:07,840 --> 01:06:14,340
Він все ще будете мати недолік не в змозі повністю впоратися

859
01:06:14,340 --> 01:06:17,940
коли сам корінь є порожнім, або минуле вступу порожній,

860
01:06:17,940 --> 01:06:20,060
але замість того щоб впоратися з одним з батьків покажчик,

861
01:06:20,060 --> 01:06:27,430
Давайте застосувати ту ж логіку зберігання покажчиків на покажчики.

862
01:06:27,430 --> 01:06:35,580
Якщо при цьому ми продовжуємо наш вузол ** текущ.,

863
01:06:35,580 --> 01:06:37,860
і нам не потрібно стежити за право більше,

864
01:06:37,860 --> 01:06:47,190
але вузлі ** = текущ. та дерева.

865
01:06:47,190 --> 01:06:54,800
І тепер наша в той час як цикл буде час * струму не дорівнює нулю.

866
01:06:54,800 --> 01:07:00,270
Не потрібно стежити за батьків більше.

867
01:07:00,270 --> 01:07:04,180
Не потрібно стежити за ліву і праву.

868
01:07:04,180 --> 01:07:10,190
І я буду називати його темп, тому що ми вже використовує темп.

869
01:07:10,190 --> 01:07:17,200
Добре. Так що, якщо (значення> * температура),

870
01:07:17,200 --> 01:07:24,010
то й (* температура) -> Право

871
01:07:24,010 --> 01:07:29,250
ще Temp = & (* температура) -> пішов.

872
01:07:29,250 --> 01:07:32,730
І зараз, в даний момент, після цього час циклу,

873
01:07:32,730 --> 01:07:36,380
Я тільки роблю це тому, можливо, легше думати про що багаторазово рекурсивно,

874
01:07:36,380 --> 01:07:39,010
але після цього час циклу,

875
01:07:39,010 --> 01:07:43,820
* Тимчасовий покажчик ми хочемо змінити.

876
01:07:43,820 --> 01:07:48,960
>> Перш, ніж ми мали батьків, і ми хотіли змінити чи лівої батьків або батька права,

877
01:07:48,960 --> 01:07:51,310
Але якщо ми хочемо змінити батьківський прав,

878
01:07:51,310 --> 01:07:54,550
Потім * тимчасовий батьки мають рацію, і ми можемо змінити його безпосередньо.

879
01:07:54,550 --> 01:08:05,860
Так що тут, внизу, ми можемо зробити * Temp = newnode, ось і все.

880
01:08:05,860 --> 01:08:09,540
Таким чином, повідомлення, все, що ми зробили в цьому було вивезти рядків коду.

881
01:08:09,540 --> 01:08:14,770
Для того, щоб стежити за батьків у всьому, що додаткові зусилля.

882
01:08:14,770 --> 01:08:18,689
При цьому, якщо ми просто стежити за покажчиком на покажчик,

883
01:08:18,689 --> 01:08:22,990
і навіть якщо б ми хотіли, щоб позбутися від усіх цих фігурні дужки зараз,

884
01:08:22,990 --> 01:08:27,170
зробити його коротшим.

885
01:08:27,170 --> 01:08:32,529
Це тепер точно такий же розчин,

886
01:08:32,529 --> 01:08:38,210
але менше рядків коду.

887
01:08:38,210 --> 01:08:41,229
Як тільки ви починаєте визнаючи це як правильне рішення,

888
01:08:41,229 --> 01:08:43,529
це також легше розмірковувати про що, як, в порядку,

889
01:08:43,529 --> 01:08:45,779
чому я повинен цим прапором на Int вірно?

890
01:08:45,779 --> 01:08:49,290
Що це значить? О, це означало, що

891
01:08:49,290 --> 01:08:51,370
кожен раз, коли я йду рацію, мені потрібно, щоб встановити його,

892
01:08:51,370 --> 01:08:53,819
ще, якщо я йду залишив мені потрібно встановити його до нуля.

893
01:08:53,819 --> 01:09:04,060
Ось, у мене немає причин, щоб про це, це просто легше думати.

894
01:09:04,060 --> 01:09:06,710
Питання?

895
01:09:06,710 --> 01:09:16,290
[Студент, нерозбірливо] >> Да.

896
01:09:16,290 --> 01:09:23,359
Отже, в останній біт -

897
01:09:23,359 --> 01:09:28,080
Я думаю, одна швидкий і простий функції ми можемо зробити, це,

898
01:09:28,080 --> 01:09:34,910
let's - разом, я думаю, спробувати і написати функцію, містить

899
01:09:34,910 --> 01:09:38,899
який не дбає, чи є це бінарне дерево пошуку.

900
01:09:38,899 --> 01:09:43,770
У ньому міститься функція повинна повертати істинним

901
01:09:43,770 --> 01:09:58,330
якщо де-небудь в цьому загальному бінарне дерево є значення, яке ми шукаємо.

902
01:09:58,330 --> 01:10:02,520
Так давайте робити це рекурсивно, і тоді ми будемо робити це повторно.

903
01:10:02,520 --> 01:10:07,300
Ми можемо насправді просто робити це разом, тому що це буде дуже коротким.

904
01:10:07,300 --> 01:10:11,510
>> Те, що мій базовий варіант буде?

905
01:10:11,510 --> 01:10:13,890
[Студент, нерозбірливо]

906
01:10:13,890 --> 01:10:18,230
[Боуден] Так що, якщо (дерево == NULL), то що?

907
01:10:18,230 --> 01:10:22,740
[Студент] Повернутися помилковим.

908
01:10:22,740 --> 01:10:26,160
[Боуден] інше, ну, мені не потрібно іншого.

909
01:10:26,160 --> 01:10:30,250
Якщо був моїм другом випадку база.

910
01:10:30,250 --> 01:10:32,450
[Студент] Дерева значення? >> Да.

911
01:10:32,450 --> 01:10:36,430
Так що, якщо (дерево-> значення == значення.

912
01:10:36,430 --> 01:10:39,920
Зверніть увагу, що ми повернулися до вузла *, а не вузла ** и?

913
01:10:39,920 --> 01:10:42,990
Містить ніколи не потрібно буде використовувати вузол **

914
01:10:42,990 --> 01:10:45,480
так як ми не змінюємо покажчиків.

915
01:10:45,480 --> 01:10:50,540
Ми просто через них.

916
01:10:50,540 --> 01:10:53,830
Якщо це відбудеться, то ми хочемо повернути істинний.

917
01:10:53,830 --> 01:10:58,270
Решту ми хочемо, щоб перетнути дітей.

918
01:10:58,270 --> 01:11:02,620
Тому ми не можемо міркувати про те, щоб все залишилося менше

919
01:11:02,620 --> 01:11:05,390
і все, що правіше більше.

920
01:11:05,390 --> 01:11:09,590
Так що ж наш стан буде тут - або, що ми будемо робити?

921
01:11:09,590 --> 01:11:11,840
[Студент, нерозбірливо] >> Да.

922
01:11:11,840 --> 01:11:17,400
Повернутися містить (значення, дерево-> ліворуч)

923
01:11:17,400 --> 01:11:26,860
або містить (значення, дерево-> праворуч). І це все.

924
01:11:26,860 --> 01:11:29,080
І зверніть увагу, є деяке коротке замикання оцінки,

925
01:11:29,080 --> 01:11:32,520
де, якщо ми, трапляється, знайти значення в лівому дереві,

926
01:11:32,520 --> 01:11:36,820
Ми ніколи не повинні дивитися на правому дереві.

927
01:11:36,820 --> 01:11:40,430
Це ціла функція.

928
01:11:40,430 --> 01:11:43,690
Тепер давайте робити це багато разів,

929
01:11:43,690 --> 01:11:48,060
який буде менш приємно.

930
01:11:48,060 --> 01:11:54,750
Ми візьмемо звичайну початку вузла * текущ. = Дерево.

931
01:11:54,750 --> 01:12:03,250
У той час (поточн.! = NULL).

932
01:12:03,250 --> 01:12:08,600
Швидко збираємося бачу проблеми.

933
01:12:08,600 --> 01:12:12,250
Якщо текущ. - Тут, якщо ми коли-небудь вирватися з цього,

934
01:12:12,250 --> 01:12:16,020
Потім ми запускаємо з речей, щоб дивитися на, так що повернутися помилковим.

935
01:12:16,020 --> 01:12:24,810
Якщо (в даний> значення == значення), повернутися вірно.

936
01:12:24,810 --> 01:12:32,910
Отже, тепер ми знаходимося на місці -

937
01:12:32,910 --> 01:12:36,250
Ми не знаємо, чи хочемо ми, щоб піти наліво або направо.

938
01:12:36,250 --> 01:12:44,590
Таким чином, довільно, давайте просто піти наліво.

939
01:12:44,590 --> 01:12:47,910
Я, очевидно, зіткнулися з питанням, де я повністю відмовилася від усього -

940
01:12:47,910 --> 01:12:50,760
Я тільки коли-небудь перевірити лівій стороні дерева.

941
01:12:50,760 --> 01:12:56,050
Я ніколи не буду перевірити все, що право дитини на все.

942
01:12:56,050 --> 01:13:00,910
Як я можу це виправити?

943
01:13:00,910 --> 01:13:05,260
[Студент] Ви повинні стежити за лівий і правий в стеці.

944
01:13:05,260 --> 01:13:13,710
[Боуден] Так. Так давайте зробимо це

945
01:13:13,710 --> 01:13:32,360
Структура списку вузлів * N, а потім вузол ** далі?

946
01:13:32,360 --> 01:13:40,240
Я думаю, що відмінно працює.

947
01:13:40,240 --> 01:13:45,940
Ми хочемо йти по лівій або let's - тут.

948
01:13:45,940 --> 01:13:54,350
Struct = список список, він почне

949
01:13:54,350 --> 01:13:58,170
при цьому структура списку.

950
01:13:58,170 --> 01:14:04,040
* Список = NULL. Так що це буде наш пов'язаного списку

951
01:14:04,040 --> 01:14:08,430
піддерев, які ми пропустили.

952
01:14:08,430 --> 01:14:13,800
Ми збираємося пройти залишилося,

953
01:14:13,800 --> 01:14:17,870
але так як ми неминуче повинні повернутися до права,

954
01:14:17,870 --> 01:14:26,140
Ми збираємося тримати в правій частині всередині нашої структури списку.

955
01:14:26,140 --> 01:14:32,620
Тоді ми будемо мати new_list або структури,

956
01:14:32,620 --> 01:14:41,080
Структура списку *, new_list = Танос (SizeOf (список)).

957
01:14:41,080 --> 01:14:44,920
Я збираюся ігнорувати перевірки помилок, але ви повинні перевірити, якщо це нульовий.

958
01:14:44,920 --> 01:14:50,540
New_list вузла це буде вказувати на -

959
01:14:50,540 --> 01:14:56,890
Ах, ось чому я хотів його тут. Це буде вказувати на другий список структуру.

960
01:14:56,890 --> 01:15:02,380
От тільки як зв'язані списки робіт.

961
01:15:02,380 --> 01:15:04,810
Це те ж саме, як Int зв'язаний список

962
01:15:04,810 --> 01:15:06,960
крім ми просто замінивши Int з вузлом *.

963
01:15:06,960 --> 01:15:11,040
Це точно так само.

964
01:15:11,040 --> 01:15:15,100
Так new_list, вартість наших new_list вузла,

965
01:15:15,100 --> 01:15:19,120
буде струм> рацію.

966
01:15:19,120 --> 01:15:24,280
Цінність нашого new_list-> наступний буде наш початковий список,

967
01:15:24,280 --> 01:15:30,760
, А потім ми будемо оновлювати наш список, щоб вказати на new_list.

968
01:15:30,760 --> 01:15:33,650
>> Тепер нам потрібно якийсь спосіб витягування речей,

969
01:15:33,650 --> 01:15:37,020
як у нас пройшов увесь лівого піддерева.

970
01:15:37,020 --> 01:15:40,480
Тепер нам потрібно витягнути речі з нього,

971
01:15:40,480 --> 01:15:43,850
як струму є нульовим, ми не хочемо, щоб просто повернутися помилковим.

972
01:15:43,850 --> 01:15:50,370
Ми хочемо зараз тягнути за межами на нашому новому списку.

973
01:15:50,370 --> 01:15:53,690
Зручний спосіб зробити це - добре, насправді, є кілька способів зробити це.

974
01:15:53,690 --> 01:15:56,680
Будь-який, є пропозиції?

975
01:15:56,680 --> 01:15:58,790
Де я повинен це зробити, або, як я повинен це зробити?

976
01:15:58,790 --> 01:16:08,010
У нас є тільки пара хвилин, але які-небудь пропозиції?

977
01:16:08,010 --> 01:16:14,750
Замість того, щоб - в одну сторону, а наші умовою є час,

978
01:16:14,750 --> 01:16:17,090
те, що ми в даний час дивимося на це не нульовий,

979
01:16:17,090 --> 01:16:22,340
Замість цього ми збираємося продовжувати йти, поки наші Сам список є порожнім.

980
01:16:22,340 --> 01:16:25,680
Таким чином, якщо наш список закінчує тим, що нульовий,

981
01:16:25,680 --> 01:16:30,680
Потім ми запустили з речей, щоб шукати, шукати більш.

982
01:16:30,680 --> 01:16:39,860
Але це означає, що в першу чергу в нашому списку тільки збирається стати першим вузлом.

983
01:16:39,860 --> 01:16:49,730
Найперше, що буде - ми більше не повинні бачити, що.

984
01:16:49,730 --> 01:16:58,710
Таким чином, список-> N буде наше дерево.

985
01:16:58,710 --> 01:17:02,860
Список-> наступна буде нульовим.

986
01:17:02,860 --> 01:17:07,580
І зараз, поки список не дорівнює нулю.

987
01:17:07,580 --> 01:17:11,610
Cur збирається витягнути щось з нашого списку.

988
01:17:11,610 --> 01:17:13,500
Так текущ. Буде рівним список-> л.

989
01:17:13,500 --> 01:17:20,850
І тоді список буде рівним список-> п, або список-> далі.

990
01:17:20,850 --> 01:17:23,480
Так що, якщо текущ. Значення дорівнює значенню.

991
01:17:23,480 --> 01:17:28,790
Тепер ми можемо додати і наше право і наш покажчик лівого покажчика

992
01:17:28,790 --> 01:17:32,900
тих пір, поки вони не нульові.

993
01:17:32,900 --> 01:17:36,390
Тут, внизу, я думаю, ми повинні були це зробити в першу чергу.

994
01:17:36,390 --> 01:17:44,080
Якщо (в даний> праві! = NULL)

995
01:17:44,080 --> 01:17:56,380
Потім ми збираємося, щоб вставити цей вузол в наш список.

996
01:17:56,380 --> 01:17:59,290
Якщо (в даний> ліворуч), це трохи додаткової роботи, але це нормально.

997
01:17:59,290 --> 01:18:02,690
Якщо (в даний> зліва! = NULL),

998
01:18:02,690 --> 01:18:14,310
і ми збираємося, щоб вставити ліворуч в нашу зв'язаний список,

999
01:18:14,310 --> 01:18:19,700
і що повинно бути.

1000
01:18:19,700 --> 01:18:22,670
Ми ітерації - поки у нас є щось у нашому списку

1001
01:18:22,670 --> 01:18:26,640
у нас є ще один вузол на що подивитися.

1002
01:18:26,640 --> 01:18:28,920
Таким чином, ми дивимося на цей вузол,

1003
01:18:28,920 --> 01:18:31,390
ми просуваємо наш список в наступному.

1004
01:18:31,390 --> 01:18:34,060
Якщо вузол є значення, яке ми шукаємо, ми можемо повернутися вірно.

1005
01:18:34,060 --> 01:18:37,640
Решта вставити обидві наші ліві і праві піддерев,

1006
01:18:37,640 --> 01:18:40,510
тих пір, поки вони не нульовий, в нашому списку

1007
01:18:40,510 --> 01:18:43,120
так що ми неминуче йдуть за ними.

1008
01:18:43,120 --> 01:18:45,160
Так що, якщо вони не були нульові,

1009
01:18:45,160 --> 01:18:47,950
якщо наш кореневої покажчик вказував на дві речі:

1010
01:18:47,950 --> 01:18:51,670
Потім ми спочатку витягнув щось з нашого списку так закінчує тим, що нульовий.

1011
01:18:51,670 --> 01:18:56,890
І тоді ми ставимо дві речі назад, так що тепер наш список має розмір 2.

1012
01:18:56,890 --> 01:19:00,030
Потім ми збираємося циклу резервного копіювання і ми тільки збираємося тягти,

1013
01:19:00,030 --> 01:19:04,250
скажімо, лівий покажчик нашого кореневого вузла.

1014
01:19:04,250 --> 01:19:07,730
І це буде просто тримати відбувається, ми закінчимо цикл над усім.

1015
01:19:07,730 --> 01:19:11,280
>> Зверніть увагу, що це було значно складніше

1016
01:19:11,280 --> 01:19:14,160
У рекурсивне рішення.

1017
01:19:14,160 --> 01:19:17,260
І я вже говорив кілька разів

1018
01:19:17,260 --> 01:19:25,120
, Що рекурсивне рішення, як правило, має багато спільного з вирішенням ітеративним.

1019
01:19:25,120 --> 01:19:30,820
Ось це саме те, що рекурсивне рішення робить.

1020
01:19:30,820 --> 01:19:36,740
Єдина зміна полягає в тому, що замість неявно за допомогою стека, стек програми,

1021
01:19:36,740 --> 01:19:40,840
як ваш спосіб відслідковувати, які вузли ви все ще повинні відвідати,

1022
01:19:40,840 --> 01:19:45,430
Тепер ви повинні явно використовувати зв'язаний список.

1023
01:19:45,430 --> 01:19:49,070
В обох випадках ви відстеження того, що вузол ще потрібно відвідати.

1024
01:19:49,070 --> 01:19:51,790
У рекурсивному випадку це просто легше, тому що стек

1025
01:19:51,790 --> 01:19:57,100
реалізується для вас, як стек програми.

1026
01:19:57,100 --> 01:19:59,550
Зверніть увагу, що це зв'язаний список, це стек.

1027
01:19:59,550 --> 01:20:01,580
Все, що ми просто покласти в стек

1028
01:20:01,580 --> 01:20:09,960
відразу, що ми збираємося витягти з стека, щоб відвідати наступний.

1029
01:20:09,960 --> 01:20:14,380
Ми поза часом, але є питання?

1030
01:20:14,380 --> 01:20:23,530
[Студент, нерозбірливо]

1031
01:20:23,530 --> 01:20:27,790
[Боуден] Так. Так що, якщо у нас є зв'язаний список,

1032
01:20:27,790 --> 01:20:30,150
Струм буде вказувати на цього хлопця,

1033
01:20:30,150 --> 01:20:34,690
і тепер ми просто просування наших зв'язаний список, щоб зосередитися на цього хлопця.

1034
01:20:34,690 --> 01:20:44,200
Ми переміщення через зв'язаний список у цьому рядку.

1035
01:20:44,200 --> 01:20:51,200
І тоді я думаю, ми повинні звільнити наші зв'язаний список та інше

1036
01:20:51,200 --> 01:20:53,880
разів, перш ніж повернутися істинним або хибним, ми повинні

1037
01:20:53,880 --> 01:20:57,360
перебору наших зв'язаний список і завжди тут, я думаю,

1038
01:20:57,360 --> 01:21:03,900
якщо ми текущ. право не є рівним, додайте його, так що тепер ми хочемо, щоб звільнити

1039
01:21:03,900 --> 01:21:09,600
текущ. тому що, ну, хіба ми абсолютно забуваємо про список? Так.

1040
01:21:09,600 --> 01:21:12,880
Так ось що ми хочемо зробити тут.

1041
01:21:12,880 --> 01:21:16,730
Де покажчик?

1042
01:21:16,730 --> 01:21:23,320
Cur було потім - ми хочемо, щоб список структур * 10 дорівнює списку поруч.

1043
01:21:23,320 --> 01:21:29,240
Безкоштовні список, список = темп.

1044
01:21:29,240 --> 01:21:32,820
І в разі, коли ми повертаємося правда, нам потрібно ітерації

1045
01:21:32,820 --> 01:21:37,050
протягом решти наші зв'язаний список, звільняючи речі.

1046
01:21:37,050 --> 01:21:39,700
Гарна річ про рекурсивні рішення визволення речі

1047
01:21:39,700 --> 01:21:44,930
просто означає, з'являються factorings стека, які відбуватимуться для вас.

1048
01:21:44,930 --> 01:21:50,720
Таким чином, ми пішли від чогось, що походить на 3 лінії важко думати про код-

1049
01:21:50,720 --> 01:21:57,520
до того, що значно багато інших важко думати-о рядках коду.

1050
01:21:57,520 --> 01:22:00,620
Є ще питання?

1051
01:22:00,620 --> 01:22:08,760
Добре. Ми добре. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]