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
Добра. Крок 2 робячы яго падобным менш тут,

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
Калі я кажу, я хачу 10. ліку, то я магу ацаніць да дзясятага чысла.

591
00:45:37,210 --> 00:45:40,300
Калі я хачу ў соты нумар, то я магу ацаніць да 100. Нумары.

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]