1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Частка 7] [менш камфортна]

2
00:00:02,500 --> 00:00:04,890
[Nate Хардисон] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[Гэта CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Сардэчна запрашаем у профіль 7.

5
00:00:09,080 --> 00:00:11,330
Дзякуючы ўраган Sandy,

6
00:00:11,330 --> 00:00:13,440
замест таго нармальнага сячэння на гэтым тыдні,

7
00:00:13,440 --> 00:00:17,650
Мы робім гэта прахадной, праз профіль пытанняў.

8
00:00:17,650 --> 00:00:22,830
Я збіраюся быць наступныя Разам з праблемай Set 6 Спецыфікацыя,

9
00:00:22,830 --> 00:00:25,650
і перажывае ўсе пытанні ў

10
00:00:25,650 --> 00:00:27,770
Раздзел падзелу Пытанні.

11
00:00:27,770 --> 00:00:30,940
Калі ёсць якія-небудзь пытанні,

12
00:00:30,940 --> 00:00:32,960
калі ласка, напішыце іх на CS50 абмеркаваць.

13
00:00:32,960 --> 00:00:35,480
>> Добра. Давайце пачнем.

14
00:00:35,480 --> 00:00:40,780
Прама цяпер я гляджу на стр. 3 Спецыфікацыя пастаўленай задачы.

15
00:00:40,780 --> 00:00:44,110
Мы ідзем да першага пачаць размову аб бінарных дрэў

16
00:00:44,110 --> 00:00:47,850
З тых ёсць шмат, якія маюць дачыненне да праблемы набору на гэтым тыдні -

17
00:00:47,850 --> 00:00:49,950
Кадаванне Хафман дрэва.

18
00:00:49,950 --> 00:00:55,000
Адзін з самых першых структур дадзеных мы казалі аб на CS50 быў масіва.

19
00:00:55,000 --> 00:01:00,170
Памятаеце, што масіў ўяўляе сабой паслядоўнасць элементаў -

20
00:01:00,170 --> 00:01:04,019
Усё ж тыпу - захоўваюцца побач адзін з адным у памяці.

21
00:01:04,019 --> 00:01:14,420
Калі ў мяне ёсць масіў цэлых лікаў, што я магу зрабіць з дапамогай гэтай скрынкі-ліку-цэлыя стыль -

22
00:01:14,420 --> 00:01:20,290
Скажам, у мяне ёсць 5 у першым полі, у мяне 7 у другой,

23
00:01:20,290 --> 00:01:27,760
то ў мяне ёсць 8, 10, і 20 у канчатковым поле.

24
00:01:27,760 --> 00:01:33,000
Памятаеце, што два сапраўды добрых рэчаў аб гэтым масіве

25
00:01:33,000 --> 00:01:38,800
у тым, што ў нас ёсць гэтая пастаянная часу доступ да любой канкрэтны элемент

26
00:01:38,800 --> 00:01:40,500
 ў масіве, калі мы ведаем яго індэкс.

27
00:01:40,500 --> 00:01:44,670
Напрыклад, калі я хачу, каб захапіць трэці элемент масіва -

28
00:01:44,670 --> 00:01:47,870
з індэксам 2, выкарыстоўваючы нашу з нуля сістэмы -

29
00:01:47,870 --> 00:01:52,220
Я літаральна толькі што трэба зрабіць просты матэматычны разлік,

30
00:01:52,220 --> 00:01:56,170
скакаць на гэтую пасаду ў масіве,

31
00:01:56,170 --> 00:01:57,840
выцягнеце 8, які захоўваецца там,

32
00:01:57,840 --> 00:01:59,260
і я добра ісці.

33
00:01:59,260 --> 00:02:03,350
>> Адзін з дрэнных рэчаў пра гэта масіва - пра якія мы казалі

34
00:02:03,350 --> 00:02:05,010
Калі мы абмяркоўвалі звязаныя спісы -

35
00:02:05,010 --> 00:02:09,120
з'яўляецца тое, што калі я хачу, каб ўставіць элемент у гэтым масіве,

36
00:02:09,120 --> 00:02:11,090
Я збіраюся зрабіць некаторы перасоўванне вакол.

37
00:02:11,090 --> 00:02:12,940
Напрыклад, гэты масіў прама тут

38
00:02:12,940 --> 00:02:16,850
з'яўляецца ў пэўным парадку - адсартаваныя ў парадку ўзрастання -

39
00:02:16,850 --> 00:02:19,440
5, потым 7, потым 8, потым 10, а затым 20 -

40
00:02:19,440 --> 00:02:23,100
але калі я хачу, каб ўставіць нумар 9 у гэтым масіве,

41
00:02:23,100 --> 00:02:27,460
Я хачу, каб перанесці некаторыя элементы для таго, каб вызваліць месца.

42
00:02:27,460 --> 00:02:30,440
Мы можам зрабіць гэта тут.

43
00:02:30,440 --> 00:02:35,650
Я збіраюся павінны рухацца 5, 7, а затым 8;

44
00:02:35,650 --> 00:02:38,720
стварыць зазор, дзе я магу паставіць 9,

45
00:02:38,720 --> 00:02:45,910
, А затым 10 і 20 можа пайсці ў праве 9.

46
00:02:45,910 --> 00:02:49,450
Гэта свайго роду болю, таму што ў горшым выпадку -

47
00:02:49,450 --> 00:02:54,350
калі мы таго, каб ўставіць альбо ў пачатку, альбо ў канцы

48
00:02:54,350 --> 00:02:56,040
масіва, у залежнасці ад таго, як мы зрушэння -

49
00:02:56,040 --> 00:02:58,850
Мы маглі б у канчатковым выніку таго, каб зрушыць ўсе элементы

50
00:02:58,850 --> 00:03:00,750
што мы ў цяперашні час захоўванне ў масіве.

51
00:03:00,750 --> 00:03:03,810
>> Такім чынам, што быў спосаб абыйсці гэта?

52
00:03:03,810 --> 00:03:09,260
Спосаб абыйсці гэта быў пайсці ў наш звязанага спісу метад, дзе -

53
00:03:09,260 --> 00:03:19,820
замест захоўвання элементаў 5, 7, 8, 10 і 20 усё побач адзін з адным у памяці -

54
00:03:19,820 --> 00:03:25,630
Замест таго, што мы рабілі, было захоўваць іх выгляду, дзе б мы хацелі, каб захаваць іх

55
00:03:25,630 --> 00:03:32,470
У гэтых звязаны спіс вузлоў, якія я малюю тут, накшталт адмысловых.

56
00:03:32,470 --> 00:03:42,060
І тады мы злучылі іх разам, выкарыстоўваючы гэтыя наступныя паказальнікі.

57
00:03:42,060 --> 00:03:44,370
Я магу ёсць паказальнік ад 5 да 7,

58
00:03:44,370 --> 00:03:46,420
Паказальнік ад 7 да 8,

59
00:03:46,420 --> 00:03:47,770
Паказальнік ад 8 да 10,

60
00:03:47,770 --> 00:03:51,220
І, нарэшце, паказальнік ад 10 да 20,

61
00:03:51,220 --> 00:03:54,880
, А затым нулявым паказальнікам на 20 пра тое, што там нічога не засталося.

62
00:03:54,880 --> 00:03:59,690
Кампраміс, што мы маем тут

63
00:03:59,690 --> 00:04:05,360
з'яўляецца тое, што цяпер, калі мы хочам, каб ўставіць нумар 9 у нашай адсартаваны спіс,

64
00:04:05,360 --> 00:04:08,270
усё, што нам трэба зрабіць, гэта стварыць новы вузел з 9,

65
00:04:08,270 --> 00:04:12,290
падлучыць яго да кропкі ў патрэбнае месца,

66
00:04:12,290 --> 00:04:20,630
, А затым паўторна провада ад 8 да кропкі да 9.

67
00:04:20,630 --> 00:04:25,660
Гэта даволі хутка, мяркуючы, што мы дакладна ведаем, дзе мы хочам, каб ўставіць 9.

68
00:04:25,660 --> 00:04:32,610
Але кампраміс у абмен на гэта, што мы цяпер страцілі пастаяннае час доступу

69
00:04:32,610 --> 00:04:36,230
любы канкрэтны элемент у нашай структуры дадзеных.

70
00:04:36,230 --> 00:04:40,950
Напрыклад, калі я хачу знайсці чацвёрты элемент у гэтай звязанага спісу,

71
00:04:40,950 --> 00:04:43,510
Я збіраюся мець, каб пачаць у самым пачатку спісу

72
00:04:43,510 --> 00:04:48,930
і працуе свой шлях праз рахункі вузла-на-вузле, пакуль не знайду чацвёрты.

73
00:04:48,930 --> 00:04:55,870
>> Для таго каб атрымаць больш шырокі доступ прадукцыйнасць, чым звязаны спіс -

74
00:04:55,870 --> 00:04:59,360
але і захаваць некаторыя з пераваг, якія ў нас былі

75
00:04:59,360 --> 00:05:01,800
Ва ўмовах увядзення часу ад звязанага спісу -

76
00:05:01,800 --> 00:05:05,750
бінарнае дрэва будзе неабходна выкарыстоўваць трохі больш памяці.

77
00:05:05,750 --> 00:05:11,460
У прыватнасці, замест таго, каб проста мець адзін паказальнік ў бінарным дрэве вузлоў -

78
00:05:11,460 --> 00:05:13,350
як звязаны спіс вузлоў робіць -

79
00:05:13,350 --> 00:05:16,950
Мы збіраемся дадаць другі паказальнік на двайковы вузла дрэва.

80
00:05:16,950 --> 00:05:19,950
Замест таго, каб проста мець адзін паказальнік на наступны элемент,

81
00:05:19,950 --> 00:05:24,420
мы будзем мець паказальнік на левы дзіцяці і права дзіцяці.

82
00:05:24,420 --> 00:05:26,560
>> Давайце намалюем карцінку, каб паглядзець, што на самой справе выглядае.

83
00:05:26,560 --> 00:05:31,350
Зноў жа, я збіраюся выкарыстоўваць гэтыя скрынкі і стрэлы.

84
00:05:31,350 --> 00:05:37,150
Бінарны вузел дрэва будзе пачаць з простай скрынцы.

85
00:05:37,150 --> 00:05:40,940
Гэта будзе мець месца для значэння,

86
00:05:40,940 --> 00:05:47,280
а затым ён таксама будзе мець прастору для левага дзіцяці і права дзіцяці.

87
00:05:47,280 --> 00:05:49,280
Я буду называць іх тут.

88
00:05:49,280 --> 00:05:57,560
Мы збіраемся ў левая дзіцяці, і тады мы будзем мець права дзіцяці.

89
00:05:57,560 --> 00:05:59,920
Ёсць шмат розных спосабаў зрабіць гэта.

90
00:05:59,920 --> 00:06:02,050
Часам для прасторы і выгоды,

91
00:06:02,050 --> 00:06:06,460
Я на самой справе зрабіць гэта, як я раблю тут на дне

92
00:06:06,460 --> 00:06:10,910
дзе я збіраюся мець значэнне ў верхняй частцы,

93
00:06:10,910 --> 00:06:14,060
, А затым правую дзіцяці на правай ніжняй,

94
00:06:14,060 --> 00:06:16,060
і левай дзіцяці на левай ніжняй.

95
00:06:16,060 --> 00:06:20,250
Вяртаючыся да гэтай вяршыні дыяграмы,

96
00:06:20,250 --> 00:06:22,560
у нас ёсць значэнне на самым версе,

97
00:06:22,560 --> 00:06:25,560
Затым у нас ёсць левы паказальнік дзіцяці, і тады мы маем права дзіцяці паказальнік.

98
00:06:25,560 --> 00:06:30,110
>> У спецыфікацыі пастаўленай задачы,

99
00:06:30,110 --> 00:06:33,110
мы гаворым аб распрацоўцы вузла, які мае значэнне 7,

100
00:06:33,110 --> 00:06:39,750
, А затым левую дзіцяці паказальнік, які з'яўляецца пустым, і правы дзіцяці-паказальнік, які з'яўляецца нулявым.

101
00:06:39,750 --> 00:06:46,040
Мы можам альбо напісаць капіталу NULL ў прасторы для

102
00:06:46,040 --> 00:06:51,610
як левай дзіцяці і права дзіцяці, ці мы можам зрабіць гэта касая рыса

103
00:06:51,610 --> 00:06:53,750
у кожным з скрынкі, каб паказаць, што гэта нулявы.

104
00:06:53,750 --> 00:06:57,560
Я збіраюся зрабіць гэта проста, таму што гэта прасцей.

105
00:06:57,560 --> 00:07:03,700
Тое, што вы бачыце тут два спосабу пабудовы дыяграм вельмі просты вузел двайковага дрэва

106
00:07:03,700 --> 00:07:07,960
дзе ў нас ёсць значэнне 7 і нулявых паказальнікаў дзіцяці.

107
00:07:07,960 --> 00:07:15,220
>> Другая частка нашай спецыфікацыі перамовы аб тым, як са звязанымі спісамі -

108
00:07:15,220 --> 00:07:18,270
Памятаеце, мы толькі павінны былі трымацца за першы элемент у спісе

109
00:07:18,270 --> 00:07:20,270
ўспомніць ўвесь спіс -

110
00:07:20,270 --> 00:07:26,140
і аналагічна, з бінарным дрэвам, мы толькі павінны трымаць на аднаго паказальніка на дрэве

111
00:07:26,140 --> 00:07:31,120
У мэтах захавання кантролю над усёй структурай дадзеных.

112
00:07:31,120 --> 00:07:36,150
Гэты адмысловы элемент дрэва называецца каранёвым вузлом дрэва.

113
00:07:36,150 --> 00:07:43,360
Напрыклад, калі гэты вузел - гэта вузел, які змяшчае значэнне 7

114
00:07:43,360 --> 00:07:45,500
з нулявой левай і правай дзіцяці паказальнікі -

115
00:07:45,500 --> 00:07:47,360
былі адзінай каштоўнасцю ў нашым дрэве,

116
00:07:47,360 --> 00:07:50,390
то гэта будзе нашым каранёвым вузлом.

117
00:07:50,390 --> 00:07:52,240
Гэта самы пачатак нашага дрэва.

118
00:07:52,240 --> 00:07:58,530
Мы можам убачыць гэта трохі ясней, як толькі мы пачнем дадаваць дадатковыя вузлы да нашага дрэве.

119
00:07:58,530 --> 00:08:01,510
Дазвольце мне падцягнуць новую старонку.

120
00:08:01,510 --> 00:08:05,000
>> Цяпер мы будзем маляваць дрэва, якое мае 7 на пні,

121
00:08:05,000 --> 00:08:10,920
і 3 ўнутраным боку левага дзіцяці, і 9 ў правым дзіцяці.

122
00:08:10,920 --> 00:08:13,500
Зноў жа, гэта даволі проста.

123
00:08:13,500 --> 00:08:26,510
У нас ёсць 7, намаляваць вузел 3, вузел 9,

124
00:08:26,510 --> 00:08:32,150
і я збіраюся ўсталяваць левы паказальнік дзіця ад 7 да паказваюць на вузел, які змяшчае 3,

125
00:08:32,150 --> 00:08:37,850
і права дзіцяці паказальнік вузел, які змяшчае ад 7 да вузел, які змяшчае 9.

126
00:08:37,850 --> 00:08:42,419
Цяпер, так як 3 і 9 не маюць дзяцей,

127
00:08:42,419 --> 00:08:48,500
мы збіраемся ўсталяваць ўсе іх паказальнікі дзіцяці, з'яўляюцца несапраўднымі.

128
00:08:48,500 --> 00:08:56,060
Тут корань нашага дрэва адпавядае вузел, які змяшчае нумар 7.

129
00:08:56,060 --> 00:09:02,440
Вы можаце бачыць, што калі ўсе мы маем паказальнік на каранёвай вузел,

130
00:09:02,440 --> 00:09:07,330
мы можам прайсці праз наша дрэва і доступ як даччыныя вузлы -

131
00:09:07,330 --> 00:09:10,630
як 3 і 9.

132
00:09:10,630 --> 00:09:14,820
Не трэба захаваць паказальнікі на кожным вузле дрэва.

133
00:09:14,820 --> 00:09:22,080
Добра. Цяпер мы збіраемся дадаць яшчэ адзін вузел да гэтай схеме.

134
00:09:22,080 --> 00:09:25,370
Мы збіраемся дадаць вузел, які змяшчае 6,

135
00:09:25,370 --> 00:09:34,140
і мы збіраемся дадаць яго ў якасці правага нашчадка вузла, які змяшчае 3.

136
00:09:34,140 --> 00:09:41,850
Каб зрабіць гэта, я збіраюся сцерці гэтую нулявога паказальніка ў 3-вузле

137
00:09:41,850 --> 00:09:47,750
і падлучыць яго да паказвала на вузел, які змяшчае 6. Добра.

138
00:09:47,750 --> 00:09:53,800
>> На дадзены момант, давайце пяройдзем трохі тэрміналогіі.

139
00:09:53,800 --> 00:09:58,230
Для пачатку, прычына таго, што гэта называецца бінарнае дрэва, у прыватнасці,

140
00:09:58,230 --> 00:10:00,460
з'яўляецца тое, што яна мае два паказальніка дзіцяці.

141
00:10:00,460 --> 00:10:06,020
Ёсць і іншыя віды дрэў, якія маюць больш паказальнікаў дзіцяці.

142
00:10:06,020 --> 00:10:10,930
У прыватнасці, вы зрабілі "паспрабаваць" ў праблеме Set 5.

143
00:10:10,930 --> 00:10:19,310
Вы заўважыце, што ў гэтай спробе, у вас было 27 розных паказальнікаў на розныя дзеці -

144
00:10:19,310 --> 00:10:22,410
па адным для кожнай з 26 літар англійскага алфавіту,

145
00:10:22,410 --> 00:10:25,410
, А затым 27-й па апострафа -

146
00:10:25,410 --> 00:10:28,900
так, што падобны на тып дрэва.

147
00:10:28,900 --> 00:10:34,070
Але тут, так як гэта двайковы, у нас ёсць толькі два паказальніка дзіцяці.

148
00:10:34,070 --> 00:10:37,880
>> У дадатак да гэтай каранёвай вузел, што мы казалі пра тое,

149
00:10:37,880 --> 00:10:41,470
Мы таксама кідалі вакол гэтага тэрміну "дзіця".

150
00:10:41,470 --> 00:10:44,470
Што гэта значыць для аднаго вузла, каб быць нашчадкам іншага вузла?

151
00:10:44,470 --> 00:10:54,060
Гэта літаральна азначае, што дзіця вузел з'яўляецца нашчадкам іншага вузла

152
00:10:54,060 --> 00:10:58,760
калі іншы вузел мае адну з яго даччыных паказальнікі ўстаноўлены, каб паказаць на гэтым вузле.

153
00:10:58,760 --> 00:11:01,230
Каб паставіць гэта ў больш канкрэтных тэрмінах,

154
00:11:01,230 --> 00:11:11,170
калі 3, паказаў на аднаго дзіцяці паказальнікі 7, затым 3 з'яўляецца даччыным 7.

155
00:11:11,170 --> 00:11:14,510
Калі б мы маглі зразумець, што дзеці да 7 гадоў -

156
00:11:14,510 --> 00:11:18,510
Ну, мы бачым, што 7 мае паказальнік на 3 і паказальнік на 9,

157
00:11:18,510 --> 00:11:22,190
таму 9 і 3 дзяцей 7.

158
00:11:22,190 --> 00:11:26,650
Дзевяць дзяцей няма, таму што яго паказальнікі дзіцяці з'яўляюцца несапраўднымі,

159
00:11:26,650 --> 00:11:30,940
і 3 мае толькі аднаго дзіцяці, 6.

160
00:11:30,940 --> 00:11:37,430
Шэсць таксама не мае дзяцей, таму што абодва яго паказальнікі з'яўляюцца несапраўднымі, якую мы будзем маляваць прама цяпер.

161
00:11:37,430 --> 00:11:45,010
>> Акрамя таго, мы таксама гаворым пра бацькоў канкрэтнага вузла,

162
00:11:45,010 --> 00:11:51,100
і гэта, як і варта было чакаць, зваротны гэтага дзіцяці апісання.

163
00:11:51,100 --> 00:11:58,620
Кожны вузел мае толькі аднаго з бацькоў - замест двух, як вы маглі б чакаць з людзьмі.

164
00:11:58,620 --> 00:12:03,390
Напрыклад, бацька 3, 7.

165
00:12:03,390 --> 00:12:10,800
Бацька 9 таксама 7 і бацькоў 6, 3. Не так шмат да яго.

166
00:12:10,800 --> 00:12:15,720
У нас таксама ёсць умовы, каб казаць пра бабуль і дзядуляў і ўнукаў,

167
00:12:15,720 --> 00:12:18,210
і наогул мы гаворым пра продкаў

168
00:12:18,210 --> 00:12:20,960
і нашчадкаў канкрэтнага вузла.

169
00:12:20,960 --> 00:12:25,710
Продкам вузла - ці продкаў, хутчэй, вузел -

170
00:12:25,710 --> 00:12:32,730
Усе вузлоў, якія ляжаць на шляху ад кораня да гэтага вузла.

171
00:12:32,730 --> 00:12:36,640
Напрыклад, калі я гляджу на вузле 6,

172
00:12:36,640 --> 00:12:46,430
Затым продкі збіраюцца быць як 3 і 7.

173
00:12:46,430 --> 00:12:55,310
Продкі 9, напрыклад, ёсць - калі я гляджу на вузле 9 -

174
00:12:55,310 --> 00:12:59,990
Затым продка з 9 знаходзіцца ўсяго ў 7.

175
00:12:59,990 --> 00:13:01,940
І нашчадкі ў дакладнасці наадварот.

176
00:13:01,940 --> 00:13:05,430
Калі я хачу паглядзець на ўсе нашчадкі 7,

177
00:13:05,430 --> 00:13:11,020
Затым я павінен глядзець на ўсе вузлы пад ім.

178
00:13:11,020 --> 00:13:16,950
Такім чынам, у мяне ёсць 3, 9 і 6, усё як нашчадкі 7.

179
00:13:16,950 --> 00:13:24,170
>> Апошні тэрмін, які мы будзем казаць пра гэта паняцце быцця роднага брата.

180
00:13:24,170 --> 00:13:27,980
Браты і сёстры - накшталт наступных разам на гэтых сямейных умовах -

181
00:13:27,980 --> 00:13:33,150
вузлы, якія знаходзяцца на тым жа ўзроўні ў дрэве.

182
00:13:33,150 --> 00:13:42,230
Так, 3 і 9 братоў і сясцёр, таму што яны на тым жа ўзроўні ў дрэве.

183
00:13:42,230 --> 00:13:46,190
Яны абодва маюць аднаго з бацькоў, 7.

184
00:13:46,190 --> 00:13:51,400
6 не мае братоў і сясцёр, таму што 9 не мае дзяцей.

185
00:13:51,400 --> 00:13:55,540
І 7 не мае братоў і сясцёр, таму што гэта корань нашага дрэва,

186
00:13:55,540 --> 00:13:59,010
і ёсьць толькі калі-небудзь 1 корань.

187
00:13:59,010 --> 00:14:02,260
На 7 братоў і сясцёр, каб там павінны былі б быць вышэй 7 вузлоў.

188
00:14:02,260 --> 00:14:07,480
Там павінна было б быць бацькам 7, у якім выпадку 7 больш не будзе коранем дрэва.

189
00:14:07,480 --> 00:14:10,480
Затым, што новыя бацькі з 7 таксама будзе мець дзіцяці,

190
00:14:10,480 --> 00:14:16,480
і што дзіця б тады брат 7.

191
00:14:16,480 --> 00:14:21,040
>> Добра. Рухаемся далей.

192
00:14:21,040 --> 00:14:24,930
Калі мы пачалі наш размова аб бінарных дрэў,

193
00:14:24,930 --> 00:14:28,790
мы казалі пра тое, як мы збіраемся выкарыстаць іх для

194
00:14:28,790 --> 00:14:32,800
атрымаць перавагу над абодвух масіваў і звязаных спісаў.

195
00:14:32,800 --> 00:14:37,220
І тое, як мы збіраемся зрабіць гэта з гэтай замовай уласнасці.

196
00:14:37,220 --> 00:14:41,080
Мы кажам, што бінарнае дрэва упарадкаваны, у адпаведнасці са спецыфікацыяй,

197
00:14:41,080 --> 00:14:45,740
калі для кожнага вузла ў дрэве, усе яго нашчадкі злева -

198
00:14:45,740 --> 00:14:48,670
левы дзіцяці, і ўсіх нашчадкаў левай дзіцяці -

199
00:14:48,670 --> 00:14:54,510
маюць меншыя значэння, а ўсе вузлы справа -

200
00:14:54,510 --> 00:14:57,770
правы дзіцяці і ўсіх нашчадкаў правы дзіцяці -

201
00:14:57,770 --> 00:15:02,800
ёсць вузлы больш, чым значэнне бягучага вузла, што мы глядзім.

202
00:15:02,800 --> 00:15:07,850
Проста для прастаты мы будзем лічыць, што няма ніякіх дублюючых вузлоў у нашым дрэве.

203
00:15:07,850 --> 00:15:11,180
Напрыклад, у гэтым дрэве мы не збіраемся мець справу з выпадкам

204
00:15:11,180 --> 00:15:13,680
дзе ў нас ёсць значэнне 7 у корані

205
00:15:13,680 --> 00:15:16,720
 і ў нас таксама ёсць значэнне 7 у іншым месцы ў дрэва.

206
00:15:16,720 --> 00:15:24,390
У гэтым выпадку, вы заўважыце, што гэта дрэва сапраўды замоўлены.

207
00:15:24,390 --> 00:15:26,510
У нас ёсць значэнне 7 на пні.

208
00:15:26,510 --> 00:15:29,720
Усе злева ад 7 -

209
00:15:29,720 --> 00:15:35,310
калі я адмяню ўсе гэтыя маленькія знакі тут -

210
00:15:35,310 --> 00:15:40,450
усё, што злева ад 7 - 3 і 6 -

211
00:15:40,450 --> 00:15:49,410
гэтыя значэнні знаходзяцца менш чым у 7, і ўсё, што правей - што менавіта гэта 9 -

212
00:15:49,410 --> 00:15:53,450
больш за 7.

213
00:15:53,450 --> 00:15:58,650
>> Гэта не толькі спарадкаванае дрэва, якія змяшчаюць гэтыя значэнні,

214
00:15:58,650 --> 00:16:03,120
Але давайце намаляваць некалькі з іх.

215
00:16:03,120 --> 00:16:05,030
Існуе на самой справе цэлая куча спосабаў, якімі мы можам гэта зрабіць.

216
00:16:05,030 --> 00:16:09,380
Я збіраюся выкарыстоўваць скарочаны толькі, каб трымаць рэчы простымі, дзе -

217
00:16:09,380 --> 00:16:11,520
, А не расцягваючы цэлым скрынкі-і-стрэлкі -

218
00:16:11,520 --> 00:16:14,220
Я проста хачу звярнуць нумароў і дадаць стрэлкі, якія злучаюць іх.

219
00:16:14,220 --> 00:16:22,920
Для пачатку, мы будзем проста пісаць свае арыгінальныя дрэва яшчэ раз, дзе ў нас было 7, а затым 3,

220
00:16:22,920 --> 00:16:25,590
, А затым 3 паказана назад у праве на 6,

221
00:16:25,590 --> 00:16:30,890
і 7 мелі права дзіцяці, які быў 9.

222
00:16:30,890 --> 00:16:33,860
Добра. Якія яшчэ адзін спосаб, што мы маглі б напісаць гэта дрэва?

223
00:16:33,860 --> 00:16:38,800
Замест таго, каб быць 3 левы дзіця 7,

224
00:16:38,800 --> 00:16:41,360
Мы таксама маглі б быць 6 левым дзіця 7,

225
00:16:41,360 --> 00:16:44,470
, А затым 3 будзе левы дзіцяці 6.

226
00:16:44,470 --> 00:16:48,520
Гэта будзе выглядаць наступным чынам дрэва прама тут, дзе ў мяне 7,

227
00:16:48,520 --> 00:16:57,860
потым 6, потым 3, і 9 справа.

228
00:16:57,860 --> 00:17:01,490
Мы таксама не павінны мець 7, як наш каранёвай вузел.

229
00:17:01,490 --> 00:17:03,860
Мы маглі б таксама мець 6, як наш каранёвай вузел.

230
00:17:03,860 --> 00:17:06,470
Што б выглядаць?

231
00:17:06,470 --> 00:17:09,230
Калі мы збіраемся захаваць гэтую загадаў уласнасці,

232
00:17:09,230 --> 00:17:12,970
усё, што лявей з 6 павінен быць менш, чым яна.

233
00:17:12,970 --> 00:17:16,540
Там толькі адна магчымасць, і вось 3.

234
00:17:16,540 --> 00:17:19,869
Але тады, як права дзіцяці з 6, у нас ёсць дзве магчымасці.

235
00:17:19,869 --> 00:17:25,380
Па-першае, мы маглі б 7, а затым 9,

236
00:17:25,380 --> 00:17:28,850
ці мы можам зрабіць гэта - як я збіраюся зрабіць тут -

237
00:17:28,850 --> 00:17:34,790
дзе ў нас ёсць 9, правы дзіцяці 6,

238
00:17:34,790 --> 00:17:39,050
, А затым 7 у якасці левага дзіцем з 9.

239
00:17:39,050 --> 00:17:44,240
>> Цяпер, 7 і 6 не з'яўляюцца адзіна магчымымі значэннямі кораня.

240
00:17:44,240 --> 00:17:50,200
Мы маглі б таксама мець 3 быць у корані.

241
00:17:50,200 --> 00:17:52,240
Што адбудзецца, калі 3 з'яўляецца ў корані?

242
00:17:52,240 --> 00:17:54,390
Тут усё становіцца трохі цікавей.

243
00:17:54,390 --> 00:17:58,440
Тры не мае ніякага значэння, якія менш, чым ён,

244
00:17:58,440 --> 00:18:02,070
так што ўся левая бок дрэва проста будзе нулявы.

245
00:18:02,070 --> 00:18:03,230
Там не будзе нічога няма.

246
00:18:03,230 --> 00:18:07,220
Справа, мы маглі б пералічыць рэчы ў парадку ўзрастання.

247
00:18:07,220 --> 00:18:15,530
Мы маглі б 3, то 6, то 7, то 9.

248
00:18:15,530 --> 00:18:26,710
Ці, мы маглі б зрабіць 3, то 6, то 9, то 7.

249
00:18:26,710 --> 00:18:35,020
Ці, мы маглі б зрабіць 3, затым 7, потым 6, потым 9.

250
00:18:35,020 --> 00:18:40,950
Ці, 3, 7 - на самай справе няма, мы не можам зрабіць 7 больш.

251
00:18:40,950 --> 00:18:43,330
Гэта наша адно там.

252
00:18:43,330 --> 00:18:54,710
Мы можам зрабіць 9, а затым з 9 мы можам зрабіць 6, а затым 7.

253
00:18:54,710 --> 00:19:06,980
Або, што мы можам зрабіць 3, то 9, то 7, а затым 6.

254
00:19:06,980 --> 00:19:12,490
>> Адна рэч, каб звярнуць вашу ўвагу на тут

255
00:19:12,490 --> 00:19:14,510
што гэтыя дрэвы трохі дзіўны выгляд.

256
00:19:14,510 --> 00:19:17,840
У прыватнасці, калі мы глядзім на 4 дрэва на правай баку -

257
00:19:17,840 --> 00:19:20,930
Я іх кола, тут -

258
00:19:20,930 --> 00:19:28,410
гэтыя дрэвы выглядаюць амаль гэтак жа, як звязаны спіс.

259
00:19:28,410 --> 00:19:32,670
Кожны вузел мае толькі адно дзіця,

260
00:19:32,670 --> 00:19:38,950
і таму мы не павінны ўсё гэта дрэвападобная структура, якую мы бачым, напрыклад,

261
00:19:38,950 --> 00:19:44,720
 У гэтым самотнае дрэва тут на ніжняй левай.

262
00:19:44,720 --> 00:19:52,490
Гэтыя дрэвы на самай справе называецца звод, бінарныя дрэвы,

263
00:19:52,490 --> 00:19:54,170
і мы пагаворым аб гэтым падрабязней у будучыні -

264
00:19:54,170 --> 00:19:56,730
Асабліва калі вы ідзяце на прыняцце іншых курсаў па інфарматыцы.

265
00:19:56,730 --> 00:19:59,670
Гэтыя дрэвы з'яўляюцца звод.

266
00:19:59,670 --> 00:20:03,780
Яны не вельмі карысна, таму што, сапраўды, гэтая структура паддаецца

267
00:20:03,780 --> 00:20:08,060
 для пошуку разы падобны на звязаны спіс.

268
00:20:08,060 --> 00:20:13,050
Мы не атрымліваем, каб скарыстацца дадатковай памяці - гэта дадатковы паказальнік -

269
00:20:13,050 --> 00:20:18,840
таму што нашы структуры дрэнных такім чынам.

270
00:20:18,840 --> 00:20:24,700
Замест таго, каб ісці далей і зрабіць з бінарных дрэў, якія маюць 9 на пні,

271
00:20:24,700 --> 00:20:27,220
якая з'яўляецца апошні выпадак, што мы павінны,

272
00:20:27,220 --> 00:20:32,380
мы замест гэтага, на дадзены момант, пагаворым крыху аб гэтым іншым тэрмінам

273
00:20:32,380 --> 00:20:36,150
, Якія мы выкарыстоўваем, калі гаворым аб дрэвах, якія называюць вышынёй.

274
00:20:36,150 --> 00:20:45,460
>> Вышыня дрэва гэта адлегласць ад кораня да самых аддаленых вузлоў,

275
00:20:45,460 --> 00:20:48,370
ці, дакладней, колькасць скачкоў, што вы павінны зрабіць для таго, каб

276
00:20:48,370 --> 00:20:53,750
пачынаецца з кораня і затым у канчатковым выніку на самым аддаленым вузел у дрэве.

277
00:20:53,750 --> 00:20:57,330
Калі мы паглядзім на некаторыя з гэтых дрэў, якія мы намалявалі прама тут,

278
00:20:57,330 --> 00:21:07,870
мы бачым, што калі мы возьмем гэта дрэва ў левым верхнім куце, і мы пачынаем на 3,

279
00:21:07,870 --> 00:21:14,510
Затым мы павінны зрабіць 1-хопа, каб дабрацца да 6, другога скачка, каб дабрацца да 7,

280
00:21:14,510 --> 00:21:20,560
і трэці хоп, каб дабрацца да 9.

281
00:21:20,560 --> 00:21:26,120
Такім чынам, вышыня гэтага дрэва 3.

282
00:21:26,120 --> 00:21:30,640
Мы можам зрабіць тое ж самае практыкаванне для іншых дрэў, выкладзеныя з гэтай зялёнай,

283
00:21:30,640 --> 00:21:40,100
і мы бачым, што вышыня ўсіх гэтых дрэў таксама сапраўды 3.

284
00:21:40,100 --> 00:21:45,230
Гэта частка таго, што робіць іх звод -

285
00:21:45,230 --> 00:21:53,750
што іх вышыня складае ўсяго адзін менш, чым колькасць вузлоў па ўсім дрэве.

286
00:21:53,750 --> 00:21:58,400
Калі мы паглядзім на гэтай другой дрэва, што гэта асяроддзе з чырвоным, з другога боку,

287
00:21:58,400 --> 00:22:03,920
мы бачым, што найбольш аддаленых вузлоў лісця 6 і 9 -

288
00:22:03,920 --> 00:22:06,940
лісце аказваюцца тыя вузлы, якія не маюць дзяцей.

289
00:22:06,940 --> 00:22:11,760
Такім чынам, для таго, каб атрымаць ад каранёвага вузла альбо 6 або 9,

290
00:22:11,760 --> 00:22:17,840
мы павінны зрабіць адно-хопа, каб дабрацца да 7, а затым другім скачку, каб дабрацца да 9,

291
00:22:17,840 --> 00:22:21,240
і аналагічна, толькі другога скачка з 7, каб дабрацца да 6.

292
00:22:21,240 --> 00:22:29,080
Такім чынам, вышыня гэтага дрэва тут толькі 2.

293
00:22:29,080 --> 00:22:35,330
Вы можаце вярнуцца назад і зрабіць гэта для ўсіх іншых дрэў, якія мы раней абмяркоўвалі

294
00:22:35,330 --> 00:22:37,380
пачынаючы з 7 і 6,

295
00:22:37,480 --> 00:22:42,500
і вы ўбачыце, што вышыня ўсіх гэтых дрэў таксама 2.

296
00:22:42,500 --> 00:22:46,320
>> Таму мы гаварылі пра загадаў бінарныя дрэвы

297
00:22:46,320 --> 00:22:50,250
і чаму яны стромкія, таму што вы можаце шукаць праз іх у

298
00:22:50,250 --> 00:22:53,810
вельмі падобна на пошукі больш спарадкаваны масіў.

299
00:22:53,810 --> 00:22:58,720
Тут мы гаворым пра тое, што паляпшэнне час пошуку

300
00:22:58,720 --> 00:23:02,730
над просты звязаны спіс.

301
00:23:02,730 --> 00:23:05,010
З звязаны спіс - калі вы хочаце знайсці канкрэтны элемент -

302
00:23:05,010 --> 00:23:07,470
Вы ў лепшым выпадку збіраецца зрабіць нейкі лінейны пошук

303
00:23:07,470 --> 00:23:10,920
дзе вы пачынаеце ў пачатку спісу і хмеля адзін-на-адзін -

304
00:23:10,920 --> 00:23:12,620
аднаго вузла на адзін вузел -

305
00:23:12,620 --> 00:23:16,060
ўвесь спіс, пакуль не знойдзеце тое, што вы шукаеце.

306
00:23:16,060 --> 00:23:19,440
Прымаючы пад увагу, калі ў вас ёсць бінарнае дрэва, якое захоўваецца ў гэтым добрым фармаце,

307
00:23:19,440 --> 00:23:23,300
Вы можаце фактычна атрымаць больш бінарны пошук працягваецца

308
00:23:23,300 --> 00:23:25,160
дзе вы падзяляй і ўладар

309
00:23:25,160 --> 00:23:29,490
і пошуку пры дапамозе адпаведных паловы дрэў на кожным кроку.

310
00:23:29,490 --> 00:23:32,840
Давайце паглядзім, як гэта працуе.

311
00:23:32,840 --> 00:23:38,850
>> Калі ў нас ёсць - зноў жа, вяртаючыся да нашай першапачатковай дрэва -

312
00:23:38,850 --> 00:23:46,710
мы пачынаем у 7, у нас ёсць 3 злева, 9 справа,

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

314
00:23:51,740 --> 00:24:01,880
Калі мы хочам, каб знайсці нумар 6 у гэтым дрэве, мы б пачалі ў корані.

315
00:24:01,880 --> 00:24:08,910
Мы б параўнаць значэнне мы шукаем, скажам, 6,

316
00:24:08,910 --> 00:24:12,320
са значэннем, якія захоўваюцца ў вузле, які мы ў цяперашні час глядзім, 7,

317
00:24:12,320 --> 00:24:21,200
выявіце, што 6 з'яўляецца сапраўды менш, чым 7, так што мы б рухацца налева.

318
00:24:21,200 --> 00:24:25,530
Калі значэнне 6 было больш, чым 7, мы б замест перамяшчаецца направа.

319
00:24:25,530 --> 00:24:29,770
Паколькі мы ведаем, што - дзякуючы структуры нашай загадаў бінарным дрэве -

320
00:24:29,770 --> 00:24:33,910
усе значэння менш 7 будуць захоўвацца злева ад 7,

321
00:24:33,910 --> 00:24:40,520
няма неабходнасці нават турбавацца, гледзячы праз правы бок дрэва.

322
00:24:40,520 --> 00:24:43,780
Як толькі мы пераходзім да левай, і мы зараз на вузел, які змяшчае 3,

323
00:24:43,780 --> 00:24:48,110
мы можам зрабіць тое ж параўнанне яшчэ раз, дзе мы параўноўваем 3 і 6.

324
00:24:48,110 --> 00:24:52,430
І мы бачым, што ў той час як 6 - каштоўнасць, якую мы шукаем, - гэта больш, чым 3,

325
00:24:52,430 --> 00:24:58,580
мы можам перайсці да правай баку вузел, які змяшчае 3.

326
00:24:58,580 --> 00:25:02,670
Там няма левай баку тут, так што мы маглі б праігнараваў.

327
00:25:02,670 --> 00:25:06,510
Але мы ведаем толькі, што, паколькі мы глядзім на само дрэва,

328
00:25:06,510 --> 00:25:08,660
і мы бачым, што дрэва не мае дзяцей.

329
00:25:08,660 --> 00:25:13,640
>> Гэта таксама даволі лёгка знайсці 6 у гэтым дрэве, калі мы робім гэта самі, як людзі,

330
00:25:13,640 --> 00:25:16,890
Але давайце сачыць за гэтым працэсам механічна, як кампутар будзе рабіць

331
00:25:16,890 --> 00:25:18,620
каб зразумець алгарытм.

332
00:25:18,620 --> 00:25:26,200
На дадзены момант, мы зараз глядзім на вузел, які змяшчае 6,

333
00:25:26,200 --> 00:25:29,180
і мы шукаем значэнне 6,

334
00:25:29,180 --> 00:25:31,740
так, сапраўды, мы знайшлі патрэбны вузел.

335
00:25:31,740 --> 00:25:35,070
Мы выявілі, што значэнне 6 у нашым дрэве, і мы можам спыніць нашы пошукі.

336
00:25:35,070 --> 00:25:37,330
На дадзены момант, у залежнасці ад таго, што адбываецца,

337
00:25:37,330 --> 00:25:41,870
мы можам сказаць, так, мы знайшлі значэння 6, яна існуе ў нашым дрэве.

338
00:25:41,870 --> 00:25:47,640
Ці, калі мы плануем ўставіць вузел ці зрабіць нешта, што мы можам зрабіць, што ў гэтай кропцы.

339
00:25:47,640 --> 00:25:53,010
>> Давайце зробім яшчэ пару пошуку, каб паглядзець, як гэта працуе.

340
00:25:53,010 --> 00:25:59,390
Давайце паглядзім, што адбудзецца, калі мы павінны былі паспрабаваць і паглядзець значэнне 10.

341
00:25:59,390 --> 00:26:02,970
Калі б мы шукаць значэнне 10, мы хацелі б пачаць з кораня.

342
00:26:02,970 --> 00:26:07,070
Мы бачым, што 10 больш, чым 7, таму мы будзем рухацца направа.

343
00:26:07,070 --> 00:26:13,640
Мы хацелі патрапіць на 9 і параўнайце 9 да 10 і бачым, што 9 з'яўляецца сапраўды менш, чым 10.

344
00:26:13,640 --> 00:26:16,210
Такім чынам, яшчэ раз, мы будзем спрабаваць рухацца направа.

345
00:26:16,210 --> 00:26:20,350
Але на дадзены момант, мы б заўважылі, што мы знаходзімся на нулявы вузел.

346
00:26:20,350 --> 00:26:23,080
Там нічога няма. Там няма нічога, дзе 10 павінна быць.

347
00:26:23,080 --> 00:26:29,360
Гэта тое, дзе мы можам паведаміць няўдача - што там на самой справе няма 10 у дрэва.

348
00:26:29,360 --> 00:26:35,420
І, нарэшце, давайце пройдзем выпадку, калі мы спрабуем знайсці 1 у дрэва.

349
00:26:35,420 --> 00:26:38,790
Гэта падобна на тое, што адбываецца, калі мы паглядзім на 10, толькі замест таго, каб ісці направа,

350
00:26:38,790 --> 00:26:41,260
Мы збіраемся пайсці налева.

351
00:26:41,260 --> 00:26:46,170
Мы пачынаем у 7 і бачым, што 1 менш 7, таму мы рухаемся налева.

352
00:26:46,170 --> 00:26:51,750
Мы дабіраемся да 3 і бачым, што 1 менш, чым 3, таму зноў мы спрабуем рухацца налева.

353
00:26:51,750 --> 00:26:59,080
На дадзены момант мы маем нулявы вузел, так што зноў мы можам паведаміць пра няўдачу.

354
00:26:59,080 --> 00:27:10,260
>> Калі вы хочаце даведацца больш аб бінарных дрэў,

355
00:27:10,260 --> 00:27:14,420
Ёсць цэлая куча весялосці мала праблем, якія вы можаце зрабіць з імі.

356
00:27:14,420 --> 00:27:19,450
Я прапаную практыкаваць малюнак з гэтых дыяграмах адзін-на-адзін

357
00:27:19,450 --> 00:27:21,910
і наступныя праз усе розныя крокі,

358
00:27:21,910 --> 00:27:25,060
таму што гэта прыйдзе ў супер-зручная

359
00:27:25,060 --> 00:27:27,480
Не толькі тады, калі вы робіце праблема Huffman кадавання набору

360
00:27:27,480 --> 00:27:29,390
але і ў будучых курсаў -

361
00:27:29,390 --> 00:27:32,220
проста навучыцца маляваць гэтыя структуры дадзеных і думаю, праз праблемы

362
00:27:32,220 --> 00:27:38,000
з ручкай і паперай, ці, у дадзеным выпадку, IPad і стылусам.

363
00:27:38,000 --> 00:27:41,000
>> На дадзены момант, аднак, мы збіраемся рухацца далей, каб зрабіць некаторыя практыкі кадавання

364
00:27:41,000 --> 00:27:44,870
а на самай справе гуляць з гэтымі бінарныя дрэвы і паглядзець.

365
00:27:44,870 --> 00:27:52,150
Я збіраюся вярнуцца да майго кампутара.

366
00:27:52,150 --> 00:27:58,480
Для гэтай частцы разрэзу, замест выкарыстання CS50 або CS50 Run прасторы,

367
00:27:58,480 --> 00:28:01,500
Я збіраюся выкарыстоўваць прыбор.

368
00:28:01,500 --> 00:28:04,950
>> Пасля разам з спецыфікацыяй пастаўленай задачы,

369
00:28:04,950 --> 00:28:07,740
Я бачу, што я павінен адкрыць прыбор,

370
00:28:07,740 --> 00:28:11,020
іду ў тэчку Dropbox, стварыць тэчку з імем Раздзел 7,

371
00:28:11,020 --> 00:28:15,730
, А затым стварыць файл з імем binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Тут мы ідзем. У мяне ёсць прыбор ўжо адкрыты.

373
00:28:22,050 --> 00:28:25,910
Я збіраюся цягнуць да тэрмінала.

374
00:28:25,910 --> 00:28:38,250
Я збіраюся пайсці ў тэчку Dropbox, стварыце каталог называецца section7,

375
00:28:38,250 --> 00:28:42,230
і ўбачыць яго зусім пустым.

376
00:28:42,230 --> 00:28:48,860
Цяпер я збіраюся адкрыць binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Добра. Тут мы ідзем - пусты файл.

378
00:28:51,750 --> 00:28:54,330
>> Давайце вернемся да спецыфікацыі.

379
00:28:54,330 --> 00:28:59,850
Спецыфікацыя просіць, каб стварыць новае вызначэнне тыпу

380
00:28:59,850 --> 00:29:03,080
для двайковага дрэва вузлоў якія змяшчаюць Int значэння -

381
00:29:03,080 --> 00:29:07,110
так жа як і каштоўнасці, якія мы звярнулі ў нашай дыяграм раней.

382
00:29:07,110 --> 00:29:11,740
Мы збіраемся выкарыстаць гэты шаблонны ЬурейеЕ, што мы зрабілі тут

383
00:29:11,740 --> 00:29:14,420
што вы павінны даведацца з задач 5 -

384
00:29:14,420 --> 00:29:19,190
калі вы зрабілі хэш-табліцы шляхам заваёвы правапісу праграмы.

385
00:29:19,190 --> 00:29:22,540
Вы павінны таксама прызнаць, што ў раздзеле мінулым тыдні

386
00:29:22,540 --> 00:29:23,890
дзе мы казалі аб звязаных спісаў.

387
00:29:23,890 --> 00:29:27,870
У нас гэта ЬурейеЕ з структуры вузла,

388
00:29:27,870 --> 00:29:34,430
і мы далі гэтай структуры вузла гэта назва структуры вузла загадзя

389
00:29:34,430 --> 00:29:39,350
так што мы можам спасылацца на яго, так як мы хочам мець паказальнікі структуры вузла

390
00:29:39,350 --> 00:29:45,740
як частка нашай структуры, але мы тады атачылі гэтую -

391
00:29:45,740 --> 00:29:47,700
ці, хутчэй, заключаны гэтым - у ЬурейеЕ

392
00:29:47,700 --> 00:29:54,600
так што, у канцы кода, мы можам звярнуцца да гэтай структуры, як толькі вузел, а структура вузла.

393
00:29:54,600 --> 00:30:03,120
>> Гэта будзе вельмі падобны на односвязный вызначэнне спісу, які мы бачылі на мінулым тыдні.

394
00:30:03,120 --> 00:30:20,070
Каб зрабіць гэта, давайце пачнем з выпісваючы шаблону.

395
00:30:20,070 --> 00:30:23,840
Мы ведаем, што мы павінны мець цэлае значэнне,

396
00:30:23,840 --> 00:30:32,170
так што мы трапілі ў цэлалікавых значэнне, а затым замест таго, каб толькі адзін паказальнік на наступны элемент -

397
00:30:32,170 --> 00:30:33,970
як мы зрабілі з односвязный спісаў -

398
00:30:33,970 --> 00:30:38,110
Мы збіраемся мець левы і правы паказальнікі дзіцяці.

399
00:30:38,110 --> 00:30:42,880
Гэта даволі простая таксама - структура вузла * левы дзіцяці;

400
00:30:42,880 --> 00:30:51,190
і структура вузла * Права дзіцяці;. Cool.

401
00:30:51,190 --> 00:30:54,740
Гэта выглядае як вельмі добры старт.

402
00:30:54,740 --> 00:30:58,530
Давайце вернемся да спецыфікацыі.

403
00:30:58,530 --> 00:31:05,030
>> Цяпер нам трэба абвясціць глабальную зменную * вузел каранёвага дрэва.

404
00:31:05,030 --> 00:31:10,590
Мы збіраемся зрабіць гэта глабальны так жа, як мы зрабілі першы паказальнік у нашым спісе таксама звязана глабальным.

405
00:31:10,590 --> 00:31:12,690
Гэта было так, што ў функцыях, якія мы пішам

406
00:31:12,690 --> 00:31:16,180
мы не павінны трымаць праходзіць вакол гэтага кораня -

407
00:31:16,180 --> 00:31:19,620
хоць мы ўбачым, што, калі вы хочаце напісаць гэтыя функцыі рэкурсіўна,

408
00:31:19,620 --> 00:31:22,830
што можа быць лепш нават не перадаваць яго ў якасці глабальнай, у першую чаргу

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

410
00:31:28,090 --> 00:31:31,960
Але, мы зробім гэта ў глабальным маштабе для пачатку.

411
00:31:31,960 --> 00:31:39,920
Зноў жа, мы дамо пару прастор, і я збіраюся абвясціць каранёвай вузел *.

412
00:31:39,920 --> 00:31:46,770
Проста каб пераканацца, што я не пакідаю гэтай неинициализированные, я збіраюся ўсталяваць яго роўным нулю.

413
00:31:46,770 --> 00:31:52,210
Зараз, у асноўнай функцыі - якія мы будзем пісаць вельмі хутка, прама тут -

414
00:31:52,210 --> 00:32:00,450
Int асноўных (Int агдс, сопзЬ сЬаг * ARGV []) -

415
00:32:00,450 --> 00:32:10,640
і я збіраюся пачаць дэклараванне мой ARGV масіва як константного проста так, што я ведаю,

416
00:32:10,640 --> 00:32:14,550
што тыя аргументы аргументамі, якія я, верагодна, не хочуць змяніць.

417
00:32:14,550 --> 00:32:18,390
Калі я хачу змяніць іх, я, верагодна, варта рабіць іх копіі.

418
00:32:18,390 --> 00:32:21,740
Вы ўбачыце гэта шмат кода.

419
00:32:21,740 --> 00:32:25,440
Гэта добра ў любым выпадку. Гэта выдатна, каб пакінуць усё як - апусціць сопзЬ, калі вы хочаце.

420
00:32:25,440 --> 00:32:28,630
Як правіла, я паклаў яго ў проста так, што я нагадваю сабе,

421
00:32:28,630 --> 00:32:33,650
 што я, верагодна, не хочаце змяняць гэтыя аргументы.

422
00:32:33,650 --> 00:32:39,240
>> Як заўсёды, я збіраюся ўключыць гэта вяртанне 0 лінію ў канцы асноўнага.

423
00:32:39,240 --> 00:32:45,730
Тут я ініцыялізацыі майго каранёвага вузла.

424
00:32:45,730 --> 00:32:48,900
Як яна каштуе зараз, у мяне ёсць паказальнік, які ўсталяваны ў нуль,

425
00:32:48,900 --> 00:32:52,970
такім чынам, гэта паказвае на нічога.

426
00:32:52,970 --> 00:32:57,480
Для таго каб сапраўды пачаць будаўніцтва вузла,

427
00:32:57,480 --> 00:32:59,250
Я ў першую чаргу неабходна вылучыць памяць для яго.

428
00:32:59,250 --> 00:33:05,910
Я збіраюся зрабіць гэта, зрабіўшы памяці кучы з дапамогай таНос.

429
00:33:05,910 --> 00:33:10,660
Я збіраюся ўсталяваць корань, роўны вынік таНос,

430
00:33:10,660 --> 00:33:19,550
і я збіраюся выкарыстоўваць SizeOf аператара для разліку памеру вузла.

431
00:33:19,550 --> 00:33:24,990
Прычына, па якой я выкарыстоўваю SizeOf вузла, у адрозненне ад, скажам,

432
00:33:24,990 --> 00:33:37,020
рабіць нешта накшталт гэтага - таНос (4 + 4 +4) або таНос 12 -

433
00:33:37,020 --> 00:33:40,820
таму што я хачу, каб мой код, каб быць сумяшчальным наколькі гэта магчыма.

434
00:33:40,820 --> 00:33:44,540
Я хачу быць у стане прыняць гэта. З файлам, скампіляваць яго на прыбор,

435
00:33:44,540 --> 00:33:48,820
, А затым кампіляваць яго на маім 64-разрадны Mac -

436
00:33:48,820 --> 00:33:52,040
або на зусім іншы архітэктуры -

437
00:33:52,040 --> 00:33:54,640
і я хачу гэта ўсё будзе працаваць так жа.

438
00:33:54,640 --> 00:33:59,510
>> Калі я раблю здагадкі адносна памеру зменных -

439
00:33:59,510 --> 00:34:02,070
Памер Int або памер паказальніка -

440
00:34:02,070 --> 00:34:06,070
Затым я таксама робіць здагадкі аб відах архітэктуры

441
00:34:06,070 --> 00:34:10,440
, На якім мой код можа паспяхова скампіляваць пры запуску.

442
00:34:10,440 --> 00:34:15,030
Заўсёды выкарыстоўвайце SizeOf, у адрозненне ад ручной сумавання структура палёў.

443
00:34:15,030 --> 00:34:20,500
Іншая прычына ў тым, што там можа быць таксама абіўка, што кампілятар змяшчае ў структуру.

444
00:34:20,500 --> 00:34:26,570
Нават проста сумаванне асобных палёў не тое, што вы звычайна хочуць рабіць,

445
00:34:26,570 --> 00:34:30,340
так, выдаліце ​​гэтую радок.

446
00:34:30,340 --> 00:34:33,090
Цяпер, каб сапраўды ініцыялізацыі гэтага каранёвага вузла,

447
00:34:33,090 --> 00:34:36,489
Я хачу, каб падключыць значэння для кожнага з сваіх розных галінах.

448
00:34:36,489 --> 00:34:41,400
Напрыклад, для значэння Я ведаю, я хачу, каб ініцыялізаваць да 7,

449
00:34:41,400 --> 00:34:46,920
і цяпер я збіраюся ўсталяваць левы дзіця будзе нулявым

450
00:34:46,920 --> 00:34:55,820
і права дзіцяці быць нулявым. Выдатна!

451
00:34:55,820 --> 00:35:02,670
Мы зрабілі гэта частка спектру.

452
00:35:02,670 --> 00:35:07,390
>> Спецыфікацыя ўніз ў ніжняй частцы старонкі 3 пытаецца мяне на стварэнне яшчэ трох вузлоў -

453
00:35:07,390 --> 00:35:10,600
адна з якіх 3, адна з якіх 6, і адзін з 9 -

454
00:35:10,600 --> 00:35:14,210
, А затым падлучыць іх так, што выглядае сапраўды гэтак жа, як наша дрэва схема

455
00:35:14,210 --> 00:35:17,120
што гаворка ішла аб раней.

456
00:35:17,120 --> 00:35:20,450
Давайце зробім гэта вельмі хутка тут.

457
00:35:20,450 --> 00:35:26,270
Вы ўбачыце вельмі хутка, што я збіраюся пачаць пісаць кучу паўтаральнага кода.

458
00:35:26,270 --> 00:35:32,100
Я збіраюся стварыць вузел *, і я збіраюся называць гэта тры.

459
00:35:32,100 --> 00:35:36,000
Я збіраюся ўсталяваць яго роўным таНос (SizeOf (вузла)).

460
00:35:36,000 --> 00:35:41,070
Я збіраюся ўсталяваць тры-> значэнне = 3.

461
00:35:41,070 --> 00:35:54,780
Тры -> left_child = NULL; трох -> правай _child = NULL; таксама.

462
00:35:54,780 --> 00:36:01,150
Гэта выглядае вельмі падобна на ініцыялізацыю корань, і гэта менавіта тое, што

463
00:36:01,150 --> 00:36:05,760
Я збіраюся трэба зрабіць, калі я пачну ініцыялізацыі 6 і 9, а таксама.

464
00:36:05,760 --> 00:36:20,720
Я зраблю гэта вельмі хутка тут - на самай справе, я збіраюся зрабіць невялікі капіявання і ўстаўкі,

465
00:36:20,720 --> 00:36:46,140
і пераканацца, што я - усё ў парадку.

466
00:36:46,470 --> 00:37:09,900
 Зараз, я атрымаў яго скапіяваць, і я магу пайсці далей і ўсталяваць роўным 6.

467
00:37:09,900 --> 00:37:14,670
Вы бачыце, што гэта займае некаторы час, і не супер-эфектыўным.

468
00:37:14,670 --> 00:37:22,610
У зусім крыху, мы напішам функцыю, якая будзе рабіць гэта за нас.

469
00:37:22,610 --> 00:37:32,890
Я хачу, каб замяніць гэтым з 9, замяніць, што з 6.

470
00:37:32,890 --> 00:37:37,360
>> Цяпер у нас ёсць усе нашы вузлы створаны і ініцыялізаваць.

471
00:37:37,360 --> 00:37:41,200
У нас ёсць наш корань роўным 7, або якія змяшчаюць значэнне 7,

472
00:37:41,200 --> 00:37:46,510
наш вузел, які змяшчае 3, наш вузел, які змяшчае 6, і наш вузел, які змяшчае 9.

473
00:37:46,510 --> 00:37:50,390
На дадзены момант, усё, што нам трэба зрабіць, гэта правады ўсё дагары.

474
00:37:50,390 --> 00:37:53,020
Таму я ініцыялізуецца ўсе паказальнікі да нуля, гэта проста так, што я пераканацца, што

475
00:37:53,020 --> 00:37:56,260
Я не ёсць нейкія неинициализированных паказальнікаў там выпадкова.

476
00:37:56,260 --> 00:38:02,290
А таксама, паколькі, на дадзены момант, у мяне толькі ёсць на самой справе злучэння вузлоў адзін з адным -

477
00:38:02,290 --> 00:38:04,750
з тымі, што яны на самой справе звязаны з - я не павінен ісці да канца і зрабіць

478
00:38:04,750 --> 00:38:08,240
Пераканайцеся, што ўсе нулі знаходзяцца там у адпаведных месцах.

479
00:38:08,240 --> 00:38:15,630
>> Пачынаючы з коранем, я ведаю, што левая дзіцяці кораня роўная 3.

480
00:38:15,630 --> 00:38:21,250
Я ведаю, што правы дзіцяці кораня роўная 9.

481
00:38:21,250 --> 00:38:24,880
Пасля гэтага, толькі іншы дзіця, што я пакінуў для турботы

482
00:38:24,880 --> 00:38:39,080
гэта права дзіцяці 3, якая з'яўляецца 6.

483
00:38:39,080 --> 00:38:44,670
На дадзены момант, усё гэта выглядае даволі добра.

484
00:38:44,670 --> 00:38:54,210
Мы выдалім некаторыя з гэтых ліній.

485
00:38:54,210 --> 00:38:59,540
Цяпер усё выглядае даволі добра.

486
00:38:59,540 --> 00:39:04,240
Давайце вернемся да нашай спецыфікацыі і паглядзець, што мы павінны рабіць далей.

487
00:39:04,240 --> 00:39:07,610
>> На дадзены момант, мы павінны напісаць функцыю, званую 'змяшчае'

488
00:39:07,610 --> 00:39:14,150
з прататыпам "BOOL ўтрымоўвае (цэлалікавых значэнне).

489
00:39:14,150 --> 00:39:17,060
І гэта змяшчае функцыю збіраецца вярнуць сапраўдны

490
00:39:17,060 --> 00:39:21,200
 калі дрэва на якое паказвае наша глабальная пераменная каранёвай

491
00:39:21,200 --> 00:39:26,950
 утрымоўвае значэнне перадаецца ў функцыю і хлусня ў адваротным выпадку.

492
00:39:26,950 --> 00:39:29,000
Давайце пойдзем далей і што рабіць.

493
00:39:29,000 --> 00:39:35,380
Гэта будзе так жа, як пошук, што мы зрабілі ўручную на IPad проста трохі назад.

494
00:39:35,380 --> 00:39:40,130
Давайце маштаб ў трохі, і пракрутка ўверх.

495
00:39:40,130 --> 00:39:43,130
Мы збіраемся паставіць гэтую функцыю прама над нашай асноўнай функцыяй

496
00:39:43,130 --> 00:39:48,990
так што мы не павінны рабіць ніякіх прататыпаў.

497
00:39:48,990 --> 00:39:55,960
Такім чынам, лагічны ўтрымоўвае (цэлалікавых значэнне).

498
00:39:55,960 --> 00:40:00,330
Там мы ідзем. Там наш шаблонны дэкларацыі.

499
00:40:00,330 --> 00:40:02,900
Проста каб пераканацца, што гэта будзе кампіляваць,

500
00:40:02,900 --> 00:40:06,820
Я збіраюся ісці наперад і проста ўсталяваць яго роўным вярнуцца ілжывым.

501
00:40:06,820 --> 00:40:09,980
Цяпер гэтая функцыя проста не будзе рабіць нічога, і заўсёды паведамляюць, што

502
00:40:09,980 --> 00:40:14,010
значэнне, якое мы шукаем не ў дрэве.

503
00:40:14,010 --> 00:40:16,280
>> У гэты момант, верагодна, гэта добрая ідэя -

504
00:40:16,280 --> 00:40:19,600
так як мы напісалі цэлую кучу кода, і мы нават не спрабавалі тэставанне яшчэ -

505
00:40:19,600 --> 00:40:22,590
каб пераканацца, што ўсе кампілюецца.

506
00:40:22,590 --> 00:40:27,460
Ёсць некалькі рэчаў, якія мы павінны зрабіць, каб пераканацца, што гэта будзе на самой справе кампіляцыі.

507
00:40:27,460 --> 00:40:33,530
Па-першае, убачыць, калі мы выкарыстоўваем любыя функцыі ў любой бібліятэкі, якія мы яшчэ не ўключаны.

508
00:40:33,530 --> 00:40:37,940
Функцыі, якія мы выкарысталі да гэтага часу, таНос,

509
00:40:37,940 --> 00:40:43,310
і мы таксама выкарысталі гэты тып - гэта нестандартны тып, званы "bool '-

510
00:40:43,310 --> 00:40:45,750
якая ўваходзіць у стандартную BOOL загалоўка файла.

511
00:40:45,750 --> 00:40:53,250
Мы дакладна хочам ўключаць у сябе стандартныя bool.h для лагічнага тыпу,

512
00:40:53,250 --> 00:40:59,230
і мы таксама хочам # ўключаюць у сябе стандартныя lib.h для стандартных бібліятэк

513
00:40:59,230 --> 00:41:03,530
, Якія ўключаюць таНос, і свабодныя, і ўсё такое.

514
00:41:03,530 --> 00:41:08,660
Такім чынам, маштаб, мы збіраемся кінуць паліць.

515
00:41:08,660 --> 00:41:14,190
Давайце паспрабуем і пераканацца, што гэта на самай справе зрабіў кампіляцыю.

516
00:41:14,190 --> 00:41:18,150
Мы бачым, што ён робіць, так што мы на правільным шляху.

517
00:41:18,150 --> 00:41:22,990
>> Давайце адкрываць binary_tree.c зноў.

518
00:41:22,990 --> 00:41:34,530
Ён кампілюе. Давайце спусцімся і пераканацца, што мы ўстаўляем некалькі званкоў, каб наша функцыя змяшчае -

519
00:41:34,530 --> 00:41:40,130
проста каб пераканацца, што ўсё добра.

520
00:41:40,130 --> 00:41:43,170
Напрыклад, калі мы зрабілі некаторыя пошуку ў нашым дрэве раней,

521
00:41:43,170 --> 00:41:48,500
Мы спрабавалі знайсці значэння 6, 10 і 1, і мы ведалі, што 6 было ў дрэве,

522
00:41:48,500 --> 00:41:52,220
10 быў не ў дрэве, і 1 не быў у дрэва альбо.

523
00:41:52,220 --> 00:41:57,230
Давайце выкарыстоўваць гэтыя ўзоры званкі як спосаб высветліць, ці з'яўляецца ці не

524
00:41:57,230 --> 00:41:59,880
нашы ўтрымлівае функцыю працуе.

525
00:41:59,880 --> 00:42:05,210
Для таго, каб зрабіць гэта, я збіраюся выкарыстоўваць Е функцыя,

526
00:42:05,210 --> 00:42:10,280
і мы збіраемся, каб раздрукаваць вынік выкліку ўтрымлівае.

527
00:42:10,280 --> 00:42:13,280
Я збіраюся паставіць у радок "змяшчае (% D) = таму што

528
00:42:13,280 --> 00:42:20,470
 мы збіраемся падлучыць значэнне, што мы збіраемся шукаць,

529
00:42:20,470 --> 00:42:27,130
і% = з \ п "і выкарыстаць яго ў якасці нашага фармату радка.

530
00:42:27,130 --> 00:42:30,720
Мы проста збіраемся, каб убачыць - у літаральным сэнсе раздрукаваць на экране -

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

532
00:42:32,060 --> 00:42:33,580
Гэта на самай справе не выклік функцыі.

533
00:42:33,580 --> 00:42:36,760
 Гэта проста радок прызначана для выглядаць як выклік функцыі.

534
00:42:36,760 --> 00:42:41,140
>> Зараз, мы збіраемся падлучыць значэння.

535
00:42:41,140 --> 00:42:43,580
Мы збіраемся паспрабаваць змяшчае 6,

536
00:42:43,580 --> 00:42:48,340
і тое, што мы збіраемся зрабіць, так гэта выкарыстоўваць, што патройны аператар.

537
00:42:48,340 --> 00:42:56,340
Давайце паглядзім, - утрымоўвае 6 - так, цяпер я утрымліваў 6 і калі змяшчае 6 праўда,

538
00:42:56,340 --> 00:43:01,850
Радок, што мы збіраемся адправіць у фармаце характар% з

539
00:43:01,850 --> 00:43:04,850
будзе радок "ісціна".

540
00:43:04,850 --> 00:43:07,690
Давайце вылучыце на трохі.

541
00:43:07,690 --> 00:43:16,210
У адваротным выпадку, мы хочам даслаць радок "ілжывай", калі змяшчае 6 вяртае хлусня.

542
00:43:16,210 --> 00:43:19,730
Гэта крыху бесталковы з выгляду, але я думаю, я мог бы таксама ілюструюць

543
00:43:19,730 --> 00:43:23,780
што патройны аператар выглядае так як мы не бачылі яго на некаторы час.

544
00:43:23,780 --> 00:43:27,670
Гэта будзе добры, зручны спосаб высветліць, калі нашы ўтрымлівае функцыю працуе.

545
00:43:27,670 --> 00:43:30,040
Я буду пракручваць назад на левую,

546
00:43:30,040 --> 00:43:39,900
і я збіраюся скапіяваць і ўставіць гэты радок некалькі разоў.

547
00:43:39,900 --> 00:43:44,910
Ён змяніў некаторыя з гэтых каштоўнасцяў па ўсім,

548
00:43:44,910 --> 00:43:59,380
так што гэта будзе 1, а гэта будзе 10.

549
00:43:59,380 --> 00:44:02,480
>> На дадзены момант у нас ёсць добрая функцыя ўтрымлівае.

550
00:44:02,480 --> 00:44:06,080
У нас ёсць некалькі тэстаў, і мы ўбачым, калі ўсё гэта працуе.

551
00:44:06,080 --> 00:44:08,120
На дадзены момант мы напісалі яшчэ некалькі кодзе.

552
00:44:08,120 --> 00:44:13,160
Час, каб выйсці, і пераканайцеся, што ўсё яшчэ кампілюе.

553
00:44:13,160 --> 00:44:20,360
Выйсці, і цяпер давайце паспрабуем рабіць бінарнае дрэва зноў.

554
00:44:20,360 --> 00:44:22,260
Што ж, падобна, у нас ёсць памылкі,

555
00:44:22,260 --> 00:44:26,930
І ў нас ёсць гэтая відавочнага аб'явы бібліятэчныя функцыі Printf.

556
00:44:26,930 --> 00:44:39,350
Падобна на тое, што мы павінны пайсці і # ўключыць standardio.h.

557
00:44:39,350 --> 00:44:45,350
І з гэтым, усё павінна кампілявацца. Мы ўсе добра.

558
00:44:45,350 --> 00:44:50,420
Зараз паспрабуйце запусціць бінарнае дрэва і паглядзець, што адбываецца.

559
00:44:50,420 --> 00:44:53,520
Вось і мы,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
і мы бачым, што, як мы і чакалі -

561
00:44:55,190 --> 00:44:56,910
таму што мы не рэалізавалі змяшчае яшчэ,

562
00:44:56,910 --> 00:44:59,800
ці, хутчэй, мы проста пакласці ў сваю чаргу ілжывымі -

563
00:44:59,800 --> 00:45:03,300
мы бачым, што гэта проста вяртанне ілжывым для ўсіх з іх,

564
00:45:03,300 --> 00:45:06,180
Так што ўсе працоўныя, па большай частцы даволі добра.

565
00:45:06,180 --> 00:45:11,860
>> Давайце вернемся ў справе ажыццяўлення і ўтрымліваецца ў гэтай кропцы.

566
00:45:11,860 --> 00:45:17,490
Я хачу, каб пракруціць ўніз, павялічваць, і -

567
00:45:17,490 --> 00:45:22,330
Памятаеце, што алгарытм, які мы выкарыстоўвалі ў тым, што мы пачалі ў каранёвай вузел

568
00:45:22,330 --> 00:45:28,010
, А затым у кожным вузле з якімі мы сутыкаемся, мы робім для параўнання,

569
00:45:28,010 --> 00:45:32,380
і на аснове гэтага параўнання мы альбо рухацца налева дзіцяці або правы дзіцяці.

570
00:45:32,380 --> 00:45:39,670
Гэта будзе выглядаць вельмі падобна на двайковы код пошуку, які мы пісалі раней у тэрмін.

571
00:45:39,670 --> 00:45:47,810
Калі мы пачынаем, мы ведаем, што мы хочам правесці на бягучы вузел

572
00:45:47,810 --> 00:45:54,050
што мы глядзім, і бягучы вузел будзе ініцыялізаваны на каранёвай вузел.

573
00:45:54,050 --> 00:45:56,260
І зараз, мы збіраемся працягваць ісці па дрэве,

574
00:45:56,260 --> 00:45:58,140
і памятайце, што нашы прыпынку стане -

575
00:45:58,140 --> 00:46:01,870
 Калі мы фактычна працавалі на прыкладзе ўручную -

576
00:46:01,870 --> 00:46:03,960
быў, калі мы сутыкнуліся з нулявой вузел,

577
00:46:03,960 --> 00:46:05,480
не тады, калі мы глядзелі на нулявы дзіцяці,

578
00:46:05,480 --> 00:46:09,620
а калі мы сапраўды пераехалі ў вузел у дрэве

579
00:46:09,620 --> 00:46:12,640
і выявіў, што мы знаходзімся на нулявы вузел.

580
00:46:12,640 --> 00:46:20,720
Мы збіраемся паўтараць, пакуль току не роўная нулю.

581
00:46:20,720 --> 00:46:22,920
І што мы будзем рабіць?

582
00:46:22,920 --> 00:46:31,610
Мы збіраемся праверыць, калі (з актуальн -> значэнне == значэнне),

583
00:46:31,610 --> 00:46:35,160
Затым мы ведаем, што мы на самай справе знайшлі вузел, які мы шукаем.

584
00:46:35,160 --> 00:46:40,450
Дык вось, мы можам вярнуцца дакладна.

585
00:46:40,450 --> 00:46:49,830
У адваротным выпадку, мы хочам бачыць ці не значэнне менш, чым значэнне.

586
00:46:49,830 --> 00:46:53,850
Калі значэнне бягучага вузла менш, чым значэнне, якое мы шукаем,

587
00:46:53,850 --> 00:46:57,280
мы будзем рухацца направа.

588
00:46:57,280 --> 00:47:10,600
Такім чынам, з актуальн. = З актуальн. -> Right_child, а ў адваротным выпадку, мы будзем рухацца налева.

589
00:47:10,600 --> 00:47:17,480
актуальн. = з актуальн. -> left_child;. Даволі проста.

590
00:47:17,480 --> 00:47:22,830
>> Вы, напэўна, прызнаць цыкл, які вельмі падобны на гэтага ад

591
00:47:22,830 --> 00:47:27,580
бінарны пошук у пачатку тэрміну, за выключэннем то мы маем справу з нізкай, сярэдняй і высокай.

592
00:47:27,580 --> 00:47:30,000
Тут мы проста павінны паглядзець на бягучае значэнне,

593
00:47:30,000 --> 00:47:31,930
так што гэта проста і прыгожа.

594
00:47:31,930 --> 00:47:34,960
Давайце пераканацца, што гэты код працуе.

595
00:47:34,960 --> 00:47:42,780
Па-першае, пераканайцеся, што ён кампілюе. Падобна на тое, што ён робіць.

596
00:47:42,780 --> 00:47:47,920
Давайце паспрабуем запусціць яго.

597
00:47:47,920 --> 00:47:50,160
І сапраўды, ён друкуе ўсё, што мы чакалі.

598
00:47:50,160 --> 00:47:54,320
Ён знаходзіць 6 у дрэве, не знайсці 10, таму што 10 не ў дрэве,

599
00:47:54,320 --> 00:47:57,740
і не знаходзіць 1, альбо таму, што 1 таксама не ў дрэве.

600
00:47:57,740 --> 00:48:01,420
Прышпільных рэчаў.

601
00:48:01,420 --> 00:48:04,470
>> Добра. Давайце вернемся да нашай спецыфікацыі і паглядзець, што будзе далей.

602
00:48:04,470 --> 00:48:07,990
Цяпер ён хоча дадаць яшчэ некалькі вузлоў для нашага дрэва.

603
00:48:07,990 --> 00:48:11,690
Яна хоча дадаць 5, 2 і 8, і пераканацца, што нашы змяшчае код

604
00:48:11,690 --> 00:48:13,570
па-ранейшаму працуе, як чакалася.

605
00:48:13,570 --> 00:48:14,900
Давайце рабіць гэта.

606
00:48:14,900 --> 00:48:19,430
На дадзены момант, а не рабіць тое, што раздражняе капіяваць і ўстаўляць зноў,

607
00:48:19,430 --> 00:48:23,770
давайце напішам функцыю, каб фактычна стварыць вузел.

608
00:48:23,770 --> 00:48:27,740
Калі пракруціць ўвесь шлях да галоўнага, мы бачым, што мы рабілі гэта

609
00:48:27,740 --> 00:48:31,210
вельмі падобны код зноў і зноў, кожны раз, калі мы хочам стварыць вузел.

610
00:48:31,210 --> 00:48:39,540
>> Давайце напішам функцыю, якая будзе рэальна пабудаваць вузел для нас, і вярнуць яго.

611
00:48:39,540 --> 00:48:41,960
Я буду называць яго build_node.

612
00:48:41,960 --> 00:48:45,130
Я збіраюся пабудаваць вузел з пэўным значэннем.

613
00:48:45,130 --> 00:48:51,040
Павялічыць тут.

614
00:48:51,040 --> 00:48:56,600
Першае, што я збіраюся зрабіць, гэта на самай справе стварыць прастору для вузла ў кучы.

615
00:48:56,600 --> 00:49:05,400
Такім чынам, вузел * п = таНос (SizeOf (вузла)), п -> значэнне = значэнне;

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

617
00:49:14,960 --> 00:49:22,500
І ў самым канцы, мы вернем наш вузел.

618
00:49:22,500 --> 00:49:28,690
Добра. Адзінае, што варта адзначыць, што гэтая функцыя тут

619
00:49:28,690 --> 00:49:34,320
збіраецца вярнуць паказальнік на вобласць памяці, якая была кучы.

620
00:49:34,320 --> 00:49:38,880
Што прыемна аб гэтым з'яўляецца тое, што гэты вузел цяпер -

621
00:49:38,880 --> 00:49:42,420
мы павінны аб'явіць яго ў кучы, таму што калі мы абвясцілі яго ў стэк

622
00:49:42,420 --> 00:49:45,050
мы не былі б у стане зрабіць гэта ў гэтай функцыі, як гэта.

623
00:49:45,050 --> 00:49:47,690
Гэтая памяць будзе выйсці з сферы

624
00:49:47,690 --> 00:49:51,590
і былі б несапраўднымі, калі мы паспрабавалі атрымаць доступ да яго ў далейшым.

625
00:49:51,590 --> 00:49:53,500
Паколькі мы аб'яўляем кучы памяці,

626
00:49:53,500 --> 00:49:55,830
мы будзем мець, каб клапаціцца аб вызваляючы яго пазней

627
00:49:55,830 --> 00:49:58,530
для нашай праграмы не ўцечка любой памяці.

628
00:49:58,530 --> 00:50:01,270
Мы понтировавшего на што на ўсё астатняе ў кодзе

629
00:50:01,270 --> 00:50:02,880
толькі для прастаты ў той час,

630
00:50:02,880 --> 00:50:05,610
але калі вы калі-небудзь напісаць функцыю, якая выглядае наступным чынам

631
00:50:05,610 --> 00:50:10,370
дзе ў вас ёсць - некаторыя называюць гэта таНос або пераразмеркаваць ўсярэдзіне -

632
00:50:10,370 --> 00:50:14,330
Вы хочаце, каб пераканацца, што вы паклалі нейкі каментар тут, які кажа:

633
00:50:14,330 --> 00:50:29,970
эй, вы ведаеце, вяртае кучы вузлоў ініцыялізуецца перададзены ў кошце.

634
00:50:29,970 --> 00:50:33,600
І тады вы хочаце, каб пераканацца, што вы паклалі ў нейкі ўвагу, што кажа

635
00:50:33,600 --> 00:50:41,720
Выклікае павінен вызваліць вярнулася памяць.

636
00:50:41,720 --> 00:50:45,450
Такім чынам, калі хто-то ніколі не ідзе, і выкарыстоўвае гэтую функцыю,

637
00:50:45,450 --> 00:50:48,150
яны ведаюць, што ўсё, што яны вернуцца з гэтай функцыі

638
00:50:48,150 --> 00:50:50,870
ў нейкі момант трэба будзе вызвалены.

639
00:50:50,870 --> 00:50:53,940
>> Калі выказаць здагадку, што ўсё добра, і тут добра,

640
00:50:53,940 --> 00:51:02,300
мы можам спусціцца ў наш код і замяніць усе гэтыя радкі прама тут

641
00:51:02,300 --> 00:51:05,410
з заклікамі да нашай функцыі вузла зборкі.

642
00:51:05,410 --> 00:51:08,170
Давайце зробім гэта вельмі хутка.

643
00:51:08,170 --> 00:51:15,840
Адна частка, што мы не збіраемся замяніць гэтая частка тут

644
00:51:15,840 --> 00:51:18,520
на дно, дзе мы на самай справе злучаць вузлы, каб паказваць адзін на аднаго,

645
00:51:18,520 --> 00:51:21,030
таму што мы не можам зрабіць у нашых функцый.

646
00:51:21,030 --> 00:51:37,400
Але, давайце зробім корань = build_node (7); вузел * 3 = build_node (3);

647
00:51:37,400 --> 00:51:47,980
вузел * 6 = build_node (6); вузел * 9 = build_node (9),.

648
00:51:47,980 --> 00:51:52,590
І зараз, мы таксама хацелі б дадаць вузлы -

649
00:51:52,590 --> 00:52:03,530
вузел * 5 = build_node (5); вузел * = build_node 8 (8);

650
00:52:03,530 --> 00:52:09,760
і тое, што было на другі вузел? Давайце паглядзім тут. Мы хацелі б таксама дадаць 2 -

651
00:52:09,760 --> 00:52:20,280
* Два клункі = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Добра. На дадзены момант, мы ведаем, што ў нас ёсць 7, 3, 9, і 6

653
00:52:26,850 --> 00:52:30,320
Усе правадныя адпаведным чынам, але як наконт 5, 8 і 2?

654
00:52:30,320 --> 00:52:33,550
Каб захаваць усё ў належны парадак,

655
00:52:33,550 --> 00:52:39,230
Мы ведаем, што права дзіцяці 3 з'яўляецца 6.

656
00:52:39,230 --> 00:52:40,890
Такім чынам, калі мы збіраемся дадаць 5,

657
00:52:40,890 --> 00:52:46,670
5 таксама належыць да правага боку дрэў, з якіх 3 з'яўляецца коранем,

658
00:52:46,670 --> 00:52:50,440
5 належыць так як левая дзіцяці 6.

659
00:52:50,440 --> 00:52:58,650
Мы можам зрабіць гэта, сказаўшы, шэсць -> left_child = пяць;

660
00:52:58,650 --> 00:53:10,790
, А затым 8 належыць як левая дзіцем з 9, такім чынам, дзевяць -> left_child = восем;

661
00:53:10,790 --> 00:53:22,190
, А затым 2 з'яўляецца левым дзіцем 3, так што мы можам зрабіць гэта тут - Цябе -> left_child = два,.

662
00:53:22,190 --> 00:53:27,730
Калі вы не зусім разумею разам з тым, я прапаную вам зрабіць гэта самастойна.

663
00:53:27,730 --> 00:53:35,660
>> Добра. Давайце захаваем гэта. Давайце выходзіць на вуліцу і пераканайцеся, што ён збірае,

664
00:53:35,660 --> 00:53:40,760
і тады мы можам дадаць у нашу змяшчае выклікі.

665
00:53:40,760 --> 00:53:44,120
Падобна на тое, усё яшчэ кампілюе.

666
00:53:44,120 --> 00:53:51,790
Давайце і дадаць у некаторых змяшчае выклікі.

667
00:53:51,790 --> 00:53:59,640
Зноў жа, я збіраюся зрабіць трохі капіявання і ўстаўкі.

668
00:53:59,640 --> 00:54:15,860
Зараз давайце шукаць 5, 8, і 2. Добра.

669
00:54:15,860 --> 00:54:28,330
Давайце пераканаемся, што гэта ўсё выглядае добра да гэтага часу. Выдатна! Захаваць і выйсці.

670
00:54:28,330 --> 00:54:33,220
Зараз давайце зробім, кампіляцыі, а цяпер давайце працаваць.

671
00:54:33,220 --> 00:54:37,540
З вынікаў, падобна, усё працуе проста прыемна і добра.

672
00:54:37,540 --> 00:54:41,780
Выдатна! Так што цяпер у нас ёсць нашы ўтрымлівае функцыю напісана.

673
00:54:41,780 --> 00:54:46,160
Давайце рухацца далей і пачаць працаваць на тым, як ўставіць вузлы ў дрэва

674
00:54:46,160 --> 00:54:50,000
, Паколькі, як мы робім гэта цяпер, усё не вельмі прыгожа.

675
00:54:50,000 --> 00:54:52,280
>> Калі мы вернемся да спецыфікацыі,

676
00:54:52,280 --> 00:55:00,540
ён просіць, каб мы напісалі функцыю пад назвай ўставіць - зноў, вяртаючыся лагічнае

677
00:55:00,540 --> 00:55:04,400
для таго ці не, мы маглі фактычна ўстаўкі вузла ў дрэва -

678
00:55:04,400 --> 00:55:07,710
, А затым значэнне для ўстаўкі ў дрэва вызначаецца як

679
00:55:07,710 --> 00:55:11,060
Адзіны аргумент, каб нашы функцыі ўстаўкі.

680
00:55:11,060 --> 00:55:18,180
Мы вернемся дакладна, калі мы маглі б сапраўды ўставіць вузел, які змяшчае значэнне ў дрэве,

681
00:55:18,180 --> 00:55:20,930
Гэта азначае, што мы, адзін, меў досыць памяці,

682
00:55:20,930 --> 00:55:24,840
, А затым два, то гэты вузел ўжо не існуюць у дрэве, так -

683
00:55:24,840 --> 00:55:32,170
Памятаеце, што мы не будзем мець аднолькавыя значэння ў дрэве, проста каб зрабіць рэчы простымі.

684
00:55:32,170 --> 00:55:35,590
Добра. Перайсці да коду.

685
00:55:35,590 --> 00:55:44,240
Адкрыйце яго. Павялічыць трохі, а потым пракруціць ўніз.

686
00:55:44,240 --> 00:55:47,220
Скажам функцыі ўстаўкі прама над ўтрымлівае.

687
00:55:47,220 --> 00:55:56,360
Зноў жа, гэта будзе называцца BOOL ўстаўкі (цэлалікавых значэнне).

688
00:55:56,360 --> 00:56:01,840
Дайце яму трохі больш прасторы, а затым, па змаўчанні,

689
00:56:01,840 --> 00:56:08,870
давайце наўзамен ілжывага ў самым канцы.

690
00:56:08,870 --> 00:56:22,620
Цяпер ўніз, на дно, давайце ісці наперад і замест таго, каб ўручную ствараць вузлы

691
00:56:22,620 --> 00:56:27,900
У асноўнай сабе і праводка іх да ўказваць адзін на аднаго, як мы робім,

692
00:56:27,900 --> 00:56:30,600
мы належым на нашыя функцыі ўстаўкі, каб зрабіць гэта.

693
00:56:30,600 --> 00:56:35,510
Мы не будзем спадзявацца на нашы функцыі ўстаўкі для зборкі за ўсё дрэва з нуля, толькі ўсё ж,

694
00:56:35,510 --> 00:56:39,970
а мы пазбавіцца ад гэтых ліній - МЫ закомментируйте гэтыя радкі -

695
00:56:39,970 --> 00:56:43,430
што будаваць вузлы 5, 8 і 2.

696
00:56:43,430 --> 00:56:55,740
А замест гэтага, мы уставім званкі на наш функцыі ўстаўкі

697
00:56:55,740 --> 00:57:01,280
каб пераканацца, што гэта сапраўды працуе.

698
00:57:01,280 --> 00:57:05,840
Тут мы ідзем.

699
00:57:05,840 --> 00:57:09,300
>> Цяпер мы закаментаваць гэтыя радкі.

700
00:57:09,300 --> 00:57:13,700
У нас ёсць толькі 7, 3, 9 і 6 у нашай дрэва ў гэтай кропцы.

701
00:57:13,700 --> 00:57:18,870
Каб пераканацца ў тым, што ўсё гэта працуе,

702
00:57:18,870 --> 00:57:25,050
мы можам паменшыць маштаб, каб нашы бінарнае дрэва,

703
00:57:25,050 --> 00:57:30,750
запусціць яго, і мы бачым, што ўтрымліваецца ў цяперашні час кажа нам, што мы цалкам правы -

704
00:57:30,750 --> 00:57:33,110
5, 8, і 2 ужо не ў дрэве.

705
00:57:33,110 --> 00:57:37,960
Вярніцеся ў кодзе,

706
00:57:37,960 --> 00:57:41,070
і як мы збіраемся ўставіць?

707
00:57:41,070 --> 00:57:46,290
Памятаеце, што мы рабілі, калі мы былі на самай справе ўстаўка 5, 8, і 2 раней.

708
00:57:46,290 --> 00:57:50,100
Мы гулялі ў гэтую гульню Plinko, дзе мы пачалі ў корані,

709
00:57:50,100 --> 00:57:52,780
спусціўся па дрэве адзін на адзін за адным

710
00:57:52,780 --> 00:57:54,980
пакуль мы не знайшлі адпаведную шчыліну,

711
00:57:54,980 --> 00:57:57,570
і тады мы падлучаныя вузла ў адпаведным месцы.

712
00:57:57,570 --> 00:57:59,480
Мы збіраемся зрабіць тое ж самае.

713
00:57:59,480 --> 00:58:04,070
Гэта, у асноўным, як напісанне кода, які мы выкарыстоўвалі ў ўтрымлівае функцыю

714
00:58:04,070 --> 00:58:05,910
Каб знайсці месца, дзе вузел павінен быць,

715
00:58:05,910 --> 00:58:10,560
а потым мы толькі збіраемся, каб ўставіць вузел прама там.

716
00:58:10,560 --> 00:58:17,000
Давайце пачнем гэта рабіць.

717
00:58:17,000 --> 00:58:24,200
>> Такім чынам, мы маем вузел * з актуальн. = Корань; мы толькі збіраемся прытрымлівацца код змяшчае

718
00:58:24,200 --> 00:58:26,850
пакуль мы не знойдзем, што гэта не зусім праца для нас.

719
00:58:26,850 --> 00:58:32,390
Мы збіраемся прайсці праз дрэва ў той час як бягучы элемент не з'яўляецца нулявым,

720
00:58:32,390 --> 00:58:45,280
і калі мы выявім, што значэнне току, роўная значэнню, што мы спрабуем ўставіць -

721
00:58:45,280 --> 00:58:49,600
Ну, гэта адзін з выпадкаў, у якіх мы не маглі фактычна ўстаўкі вузла

722
00:58:49,600 --> 00:58:52,730
ў дрэва, таму што гэта азначае, што ў нас ёсць паўтараюцца значэння.

723
00:58:52,730 --> 00:58:59,010
Тут мы на самай справе збіраемся вярнуцца ілжывым.

724
00:58:59,010 --> 00:59:08,440
Цяпер, інакш, калі значэнне току складае менш значэння,

725
00:59:08,440 --> 00:59:10,930
Цяпер мы ведаем, што мы рухаемся направа

726
00:59:10,930 --> 00:59:17,190
 таму што значэнне належыць у правай палове з актуальн. дрэва.

727
00:59:17,190 --> 00:59:30,110
У адваротным выпадку, мы будзем рухацца налева.

728
00:59:30,110 --> 00:59:37,980
Гэта ў асноўным нашы ўтрымлівае функцыю прама там.

729
00:59:37,980 --> 00:59:41,820
>> На дадзены момант, як толькі мы скончылі гэта ў той час цыклу,

730
00:59:41,820 --> 00:59:47,350
шему паказальнік будзе паказваць на нуль

731
00:59:47,350 --> 00:59:51,540
калі функцыя ўжо не вярнуўся.

732
00:59:51,540 --> 00:59:58,710
Мы таму маюць з актуальн. Ў тым месцы, дзе мы хочам, каб ўставіць новы вузел.

733
00:59:58,710 --> 01:00:05,210
Тое, што застаецца зрабіць, гэта на самай справе пабудаваць новы вузел,

734
01:00:05,210 --> 01:00:08,480
што мы можам зрабіць даволі лёгка.

735
01:00:08,480 --> 01:00:14,930
Мы можам выкарыстоўваць нашы супер-зручная зборка вузлоў функцыі,

736
01:00:14,930 --> 01:00:17,210
і тое, што мы не рабілі раней -

737
01:00:17,210 --> 01:00:21,400
мы проста нейкая лічылі само сабой якія разумеюцца, але зараз мы будзем рабіць проста каб пераканацца -

738
01:00:21,400 --> 01:00:27,130
мы будзем праверыць, каб пераканацца, што значэнне вяртаецца новы вузел быў на самай справе

739
01:00:27,130 --> 01:00:33,410
не нулявы, таму што мы не хочам, каб пачаць доступ да гэтай памяці, калі яна не з'яўляецца несапраўдным.

740
01:00:33,410 --> 01:00:39,910
Мы можам праверыць, каб пераканацца, што новы вузел не роўная нулю.

741
01:00:39,910 --> 01:00:42,910
Або замест гэтага, мы можам проста паглядзець, калі ён на самай справе з'яўляецца пустым,

742
01:00:42,910 --> 01:00:52,120
і калі ён роўны нулю, то мы можам проста вярнуцца ілжывым рана.

743
01:00:52,120 --> 01:00:59,090
>> На дадзены момант, мы павінны падлучыць новы вузел у сваю адпаведнае месца ў дрэве.

744
01:00:59,090 --> 01:01:03,510
Калі мы паглядзім на асноўныя і дзе мы былі на самай справе праводкі ў значэннях раней,

745
01:01:03,510 --> 01:01:08,470
мы бачым, што тое, як мы гэта рабілі, калі мы хацелі паставіць 3 у дрэва

746
01:01:08,470 --> 01:01:11,750
Мы былі даступныя левым дзіцяці кораня.

747
01:01:11,750 --> 01:01:14,920
Калі мы ставім 9 у дрэва, мы павінны былі атрымаць доступ да права дзіцяці на пні.

748
01:01:14,920 --> 01:01:21,030
Мы павінны былі мець паказальнік на аднаго з бацькоў для таго, каб пакласці новае значэнне ў дрэва.

749
01:01:21,030 --> 01:01:24,430
Пракрутка назад уставіць, што не збіраецца працаваць тут цалкам

750
01:01:24,430 --> 01:01:27,550
таму што ў нас няма продка.

751
01:01:27,550 --> 01:01:31,650
Што мы хочам быць у стане рабіць гэта, на дадзены момант,

752
01:01:31,650 --> 01:01:37,080
праверце значэнне бацькоў і паглядзець - ну, чорт вазьмі,

753
01:01:37,080 --> 01:01:41,990
калі значэнне аднаго з бацькоў менш, чым бягучае значэнне,

754
01:01:41,990 --> 01:01:54,440
Затым права дзіцяці бацька павінен быць новы вузел;

755
01:01:54,440 --> 01:02:07,280
У адваротным выпадку левая дзіцяці бацька павінен быць новы вузел.

756
01:02:07,280 --> 01:02:10,290
Але мы не павінны гэтага аднаго з бацькоў паказальнік зусім яшчэ.

757
01:02:10,290 --> 01:02:15,010
>> Для таго, каб атрымаць яго, мы фактычна прыйдзецца адсочваць яго, як мы ідзем па дрэве

758
01:02:15,010 --> 01:02:18,440
і знайсці адпаведнае месца ў нашым цыкле вышэй.

759
01:02:18,440 --> 01:02:26,840
Мы можам зрабіць гэта з дапамогай пракруткі назад да вяршыні нашай функцыі ўстаўкі

760
01:02:26,840 --> 01:02:32,350
і адсочвання іншы паказальнік зменнай бацькоў.

761
01:02:32,350 --> 01:02:39,340
Мы збіраемся ўсталяваць яго роўным нулю на пачатковым этапе,

762
01:02:39,340 --> 01:02:43,640
, А затым кожны раз, калі мы ідзем па дрэве,

763
01:02:43,640 --> 01:02:51,540
Мы збіраемся ўсталяваць аднаго з бацькоў, каб адпавядаць бягучых паказальнікам.

764
01:02:51,540 --> 01:02:59,140
Ўсталяваць бацькоўскі роўна з актуальн ..

765
01:02:59,140 --> 01:03:02,260
Такім чынам, кожны раз, калі мы прайсці,

766
01:03:02,260 --> 01:03:05,550
Мы збіраемся пераканацца, што ў якасці бягучага паказальніка павялічваецца на адзінку

767
01:03:05,550 --> 01:03:12,640
бацькоўскага паказальнік варта за ім - проста на адзін узровень вышэй бягучага паказальніка ў дрэве.

768
01:03:12,640 --> 01:03:17,370
Гэта ўсё выглядае даволі добра.

769
01:03:17,370 --> 01:03:22,380
>> Я думаю, што адна рэч, якую мы хочам наладзіць гэта пабудаваць вузел вяртаецца NULL.

770
01:03:22,380 --> 01:03:25,380
Для таго, каб пабудаваць вузел на самай справе паспяхова вяртаюць NULL,

771
01:03:25,380 --> 01:03:31,060
мы павінны змяніць гэты код,

772
01:03:31,060 --> 01:03:37,270
таму што тут, мы ніколі не правяралі, каб пераканацца, што таНос вярнуўся сапраўдны паказальнік.

773
01:03:37,270 --> 01:03:53,390
Так што, калі (п = NULL!), Затым -

774
01:03:53,390 --> 01:03:55,250
калі таНос вярнуўся сапраўдны паказальнік, то мы яго ініцыялізацыі;

775
01:03:55,250 --> 01:04:02,540
У адваротным выпадку мы будзем проста вярнуць, і што ў канчатковым выніку вяртаецца NULL для нас.

776
01:04:02,540 --> 01:04:13,050
Цяпер усё выглядае даволі добра. Давайце пераканацца, што гэта на самай справе кампілюе.

777
01:04:13,050 --> 01:04:22,240
Зрабіць бінарнае дрэва, і ах, у нас ёсць некаторыя рэчы тут адбываецца.

778
01:04:22,240 --> 01:04:29,230
>> У нас ёсць няяўнай дэкларацыя функцыі стварэння вузла.

779
01:04:29,230 --> 01:04:31,950
Зноў жа, гэтыя кампілятары, мы збіраемся пачаць з самага верху.

780
01:04:31,950 --> 01:04:36,380
Што гэта павінна азначаць, што я тэлефаную пабудаваць вузел, перш чым я на самой справе аб'яўлена.

781
01:04:36,380 --> 01:04:37,730
Давайце вернемся да коду вельмі хутка.

782
01:04:37,730 --> 01:04:43,510
Пракруціць ўніз, і, вядома ж, мая ўстаўка функцыя аб'яўлена

783
01:04:43,510 --> 01:04:47,400
вышэй функцыі вузла зборкі,

784
01:04:47,400 --> 01:04:50,070
Але я спрабую выкарыстоўваць пабудаваць вузел ўнутры ўстаўкі.

785
01:04:50,070 --> 01:05:06,610
Я збіраюся пайсці і копію - а затым устаўце функцыю зборкі вузлоў шлях тут, на самым версе.

786
01:05:06,610 --> 01:05:11,750
Такім чынам, мы спадзяемся, што будзе працаваць. Давайце дамо гэтага яшчэ адзін шанец.

787
01:05:11,750 --> 01:05:18,920
Цяпер усё кампілюецца. Усё гэта добра.

788
01:05:18,920 --> 01:05:21,640
>> Але на дадзены момант, мы на самай справе не называлі нашы функцыі ўстаўкі.

789
01:05:21,640 --> 01:05:26,510
Мы проста ведаем, што ён збірае, так што давайце пойдзем і пакласці некалькі званкоў цалі

790
01:05:26,510 --> 01:05:28,240
Давайце зробім, што ў нашых асноўных функцый.

791
01:05:28,240 --> 01:05:32,390
Тут мы закаментаваны 5, 8 і 2,

792
01:05:32,390 --> 01:05:36,680
і тады мы не падключыць іх сюды.

793
01:05:36,680 --> 01:05:41,640
Давайце зробім некалькі званкоў, каб ўставіць,

794
01:05:41,640 --> 01:05:46,440
і давайце таксама выкарыстоўваць такія ж рэчы, якія мы выкарыстоўвалі

795
01:05:46,440 --> 01:05:52,810
Калі мы зрабілі гэтыя Printf званкоў, каб пераканацца, што ўсё сапраўды станавіліся адсутнічае правільна.

796
01:05:52,810 --> 01:06:00,550
Я збіраюся капіяваць і ўстаўляць,

797
01:06:00,550 --> 01:06:12,450
і замест таго, утрымлівае мы збіраемся зрабіць ўстаўку.

798
01:06:12,450 --> 01:06:30,140
І замест таго, 6, 10 і 1, мы збіраемся выкарыстаць 5, 8 і 2.

799
01:06:30,140 --> 01:06:37,320
Гэта павінна, мы спадзяемся, уставіць 5, 8, і 2 у дрэва.

800
01:06:37,320 --> 01:06:44,050
Кампіляцыя. Усё гэта добра. Цяпер мы будзем рэальна працаваць наша праграма.

801
01:06:44,050 --> 01:06:47,330
>> Усе вярнуліся ілжывай.

802
01:06:47,330 --> 01:06:53,830
Так, 5, 8 і 2 не пайшоў, і гэта выглядае як Утрымоўвае не знайшлі іх альбо.

803
01:06:53,830 --> 01:06:58,890
Што адбываецца? Давайце маштабу.

804
01:06:58,890 --> 01:07:02,160
Першай праблемай было тое, што, здавалася ўстаўкі, каб вярнуцца ілжывым,

805
01:07:02,160 --> 01:07:08,750
і, падобна, гэта таму, што мы пакінулі ў нашым вяртанні ілжывы выклік,

806
01:07:08,750 --> 01:07:14,590
і мы ніколі не вярнуліся праўда.

807
01:07:14,590 --> 01:07:17,880
Мы можам ўсталяваць, што.

808
01:07:17,880 --> 01:07:25,290
Другая праблема ў тым, зараз, нават калі мы робім - захаваць гэта, кінуць гэта,

809
01:07:25,290 --> 01:07:34,530
запусціць зрабіць зноў, хай ён скампіляваць, а затым запусціць яго -

810
01:07:34,530 --> 01:07:37,670
мы бачым, што нешта яшчэ адбылося.

811
01:07:37,670 --> 01:07:42,980
5, 8, і 2 яшчэ не знайшоў у дрэве.

812
01:07:42,980 --> 01:07:44,350
Такім чынам, што адбываецца?

813
01:07:44,350 --> 01:07:45,700
>> Давайце паглядзім на гэта ў кодзе.

814
01:07:45,700 --> 01:07:49,790
Давайце паглядзім, ці зможам мы зразумець гэта.

815
01:07:49,790 --> 01:07:57,940
Пачнем з бацькамі не быць нулявым.

816
01:07:57,940 --> 01:07:59,510
Мы ўсталёўваем паказальнік бягучай роўных у каранёвай паказальнік,

817
01:07:59,510 --> 01:08:04,280
і мы збіраемся працаваць наш шлях ўніз па дрэве.

818
01:08:04,280 --> 01:08:08,650
Калі бягучы вузел не з'яўляецца нулявым, то мы ведаем, што мы можам рухацца ўніз трохі.

819
01:08:08,650 --> 01:08:12,330
Мы ўсталёўваем нашы бацькі паказальнік роўным бягучаму паказальніку,

820
01:08:12,330 --> 01:08:15,420
праверыць значэнне - калі значэння супадаюць, мы вярнуліся ілжывай.

821
01:08:15,420 --> 01:08:17,540
Калі значэнні менш мы пераехалі ў правую;

822
01:08:17,540 --> 01:08:20,399
У адваротным выпадку мы пераехалі на левы.

823
01:08:20,399 --> 01:08:24,220
Затым мы будуем вузла. Я павялічыць няшмат.

824
01:08:24,220 --> 01:08:31,410
І вось, мы збіраемся, каб паспрабаваць падлучыць да значэнняў, тое ж самае.

825
01:08:31,410 --> 01:08:37,250
Што адбываецца? Давайце паглядзім, калі магчыма Valgrind можа даць нам падказку.

826
01:08:37,250 --> 01:08:43,910
>> Мне падабаецца выкарыстоўваць Valgrind Valgrind толькі таму, што вельмі хутка бяжыць

827
01:08:43,910 --> 01:08:46,729
і кажа вам, калі ёсць якія-небудзь памылкі памяці.

828
01:08:46,729 --> 01:08:48,300
Калі мы запускаем Valgrind на код,

829
01:08:48,300 --> 01:08:55,859
як вы можаце бачыць правы ўдар here--Valgrind./binary_tree--and ўваходу.

830
01:08:55,859 --> 01:09:03,640
Вы бачыце, што ў нас не было ніякіх памылак памяці, так што падобна, усё ў парадку да гэтага часу.

831
01:09:03,640 --> 01:09:07,529
У нас ёсць некаторыя ўцечкі памяці, якія мы ведаем, таму што мы не

832
01:09:07,529 --> 01:09:08,910
адбываецца, каб вызваліць любога з нашых вузлоў.

833
01:09:08,910 --> 01:09:13,050
Давайце паспрабуем працуе GDB, каб паглядзець, што адбываецца на самай справе.

834
01:09:13,050 --> 01:09:20,010
Мы зробім GDB. / Binary_tree. Ён загрузіўся нармальна.

835
01:09:20,010 --> 01:09:23,670
Давайце ўсталюем кропку супыну на ўстаўку.

836
01:09:23,670 --> 01:09:28,600
Давайце запусцім.

837
01:09:28,600 --> 01:09:31,200
Падобна на тое, мы ніколі не называлі ўстаўкі.

838
01:09:31,200 --> 01:09:39,410
Падобна на тое, праблема была толькі што, калі я змяніў тут, у галоўным -

839
01:09:39,410 --> 01:09:44,279
Усе гэтыя Printf званкі з ўтрымлівае -

840
01:09:44,279 --> 01:09:56,430
Я ніколі на самай справе змянілася гэтых патэлефанаваць ўстаўкі.

841
01:09:56,430 --> 01:10:01,660
Зараз давайце даць яму паспрабаваць. Давайце кампіляцыі.

842
01:10:01,660 --> 01:10:09,130
Усё выглядае добра там. Зараз давайце паспрабуем запусціць яго, паглядзець, што адбываецца.

843
01:10:09,130 --> 01:10:13,320
Добра! Усё выглядае даволі добра там.

844
01:10:13,320 --> 01:10:18,130
>> Апошняя рэч, каб думаць пра тое, ці ёсць нейкія крайнія выпадкі гэтай ўстаўкі?

845
01:10:18,130 --> 01:10:23,170
І атрымліваецца, што, маўляў, адно рабро выпадку гэта заўсёды цікава думаць пра

846
01:10:23,170 --> 01:10:26,250
у тым, што адбудзецца, калі ваша дрэва пуста, і вы называеце гэта ўстаўка функцыі?

847
01:10:26,250 --> 01:10:30,330
Ці будзе яна працаваць? Што ж, давайце паспрабуем.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree с. -

849
01:10:32,110 --> 01:10:35,810
Тое, як мы збіраемся праверыць гэта, мы збіраемся спусціцца да нашай асноўнай функцыі,

850
01:10:35,810 --> 01:10:41,690
і замест праводкі гэтых вузлах вось так,

851
01:10:41,690 --> 01:10:56,730
мы толькі збіраемся, каб закаментаваць ўсю рэч,

852
01:10:56,730 --> 01:11:02,620
і замест праводкі да вузлы сабе,

853
01:11:02,620 --> 01:11:09,400
мы сапраўды можам проста ісці наперад і выдаліць усё гэта.

854
01:11:09,400 --> 01:11:17,560
Мы збіраемся зрабіць усё выклік для ўстаўкі.

855
01:11:17,560 --> 01:11:49,020
Такім чынам, давайце рабіць - замест 5, 8 і 2, мы збіраемся, каб ўставіць 7, 3 і 9.

856
01:11:49,020 --> 01:11:58,440
І тады мы таксама хочам, каб ўставіць 6, а.

857
01:11:58,440 --> 01:12:05,190
Захаваць. Выйсці. Зрабіць бінарнае дрэва.

858
01:12:05,190 --> 01:12:08,540
Гэта ўсё кампілюецца.

859
01:12:08,540 --> 01:12:10,320
Мы можам проста запусціце яго як ёсць і паглядзець, што адбываецца,

860
01:12:10,320 --> 01:12:12,770
але гэта таксама будзе вельмі важна, каб пераканацца, што

861
01:12:12,770 --> 01:12:14,740
Мы не маюць ніякіх памылак памяці,

862
01:12:14,740 --> 01:12:16,840
так як гэта з'яўляецца адным з нашых крайніх выпадках, што мы ведаем пра.

863
01:12:16,840 --> 01:12:20,150
>> Давайце пераканаемся, што ён добра працуе пад Valgrind,

864
01:12:20,150 --> 01:12:28,310
якія мы будзем рабіць, проста выдаўшы Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Падобна на тое, у нас сапраўды адна памылка з аднаго кантэксту -

866
01:12:31,110 --> 01:12:33,790
у нас ёсць гэтая памылка сегментацыі.

867
01:12:33,790 --> 01:12:36,690
Што здарылася?

868
01:12:36,690 --> 01:12:41,650
Valgrind на самай справе кажа нам, дзе ён знаходзіцца.

869
01:12:41,650 --> 01:12:43,050
Паменшыць трохі.

870
01:12:43,050 --> 01:12:46,040
Падобна на тое, што адбываецца ў нашай функцыі ўстаўкі,

871
01:12:46,040 --> 01:12:53,420
дзе ў нас ёсць несапраўдным чытання памерам 4 на ўстаўку, радок 60.

872
01:12:53,420 --> 01:13:03,590
Давайце вернемся і паглядзім, што тут адбываецца.

873
01:13:03,590 --> 01:13:05,350
Паменшыць вельмі хутка.

874
01:13:05,350 --> 01:13:14,230
Я хачу, каб пераканацца, што ён не ідзе да краю экрана, каб мы маглі бачыць усё.

875
01:13:14,230 --> 01:13:18,760
Пацягніце, што ў няшмат. Добра.

876
01:13:18,760 --> 01:13:35,030
Пракруціць ўніз, і праблема прама тут.

877
01:13:35,030 --> 01:13:40,120
Што адбудзецца, калі мы спускаемся і наш бягучы вузел ўжо нулявыя,

878
01:13:40,120 --> 01:13:44,010
наш бацькоўскі вузел з'яўляецца нулявым, таму, калі мы глядзім на самым версе, прама тут -

879
01:13:44,010 --> 01:13:47,340
Калі гэта час цыклу ніколі не выконваецца

880
01:13:47,340 --> 01:13:52,330
таму што наша бягучае значэнне роўна нулю - наш корань нулявы так з актуальн. з'яўляецца несапраўдным -

881
01:13:52,330 --> 01:13:57,810
Затым нашы бацькі ніколі не будзе ўсталяваны ў актуальн. Або дапушчальнае значэнне,

882
01:13:57,810 --> 01:14:00,580
Такім чынам, бацькі таксама будзе нулявы.

883
01:14:00,580 --> 01:14:03,700
Мы павінны памятаць, каб праверыць, што

884
01:14:03,700 --> 01:14:08,750
Да таго часу мы прыступім тут, і мы пачынаем доступ да значэння бацькоў.

885
01:14:08,750 --> 01:14:13,190
Такім чынам, што адбываецца? Ну, калі бацька з'яўляецца нуль -

886
01:14:13,190 --> 01:14:17,990
калі (== NULL аднаго з бацькоў), - то мы ведаем, што

887
01:14:17,990 --> 01:14:19,530
не павінна быць нічога ў дрэва.

888
01:14:19,530 --> 01:14:22,030
Мы павінны спрабаваць ўставіць яго ў корані.

889
01:14:22,030 --> 01:14:32,570
Мы можам зрабіць гэта, проста задаўшы корань, роўны новы вузел.

890
01:14:32,570 --> 01:14:40,010
Тады ў гэтай кропцы мы на самай справе не хочуць, каб прайсці праз гэтыя іншыя рэчы.

891
01:14:40,010 --> 01:14:44,780
Замест гэтага, прама тут, мы можам зрабіць альбо іншае-калі-іншаму,

892
01:14:44,780 --> 01:14:47,610
ці мы маглі б аб'яднаць усе тут у іншым,

893
01:14:47,610 --> 01:14:56,300
але тут мы будзем выкарыстоўваць яшчэ і зрабіць гэта такім чынам.

894
01:14:56,300 --> 01:14:59,030
Зараз, мы збіраемся праверыць, каб пераканацца, што нашы бацькі не нулявы

895
01:14:59,030 --> 01:15:02,160
да гэтага на самай справе спрабуе атрымаць доступ да яго палях.

896
01:15:02,160 --> 01:15:05,330
Гэта дапаможа нам пазбегнуць памылкі сегментацыі.

897
01:15:05,330 --> 01:15:14,740
Такім чынам, мы кінуць паліць, паменшыць маштаб, кампіляваць, запускаць.

898
01:15:14,740 --> 01:15:18,130
>> Няма памылкі, але ў нас яшчэ ёсць куча уцечак памяці

899
01:15:18,130 --> 01:15:20,650
таму што мы не вызваліць любога з нашых вузлоў.

900
01:15:20,650 --> 01:15:24,350
Але, калі мы ідзем сюды, і мы глядзім на нашу раздрукоўку,

901
01:15:24,350 --> 01:15:30,880
мы бачым, што, ну, падобна, што ўсе нашы ўстаўкамі вярталіся праўда, і гэта добра.

902
01:15:30,880 --> 01:15:33,050
Устаўкі усё правільна,

903
01:15:33,050 --> 01:15:36,670
, А затым адпаведныя выклікі змяшчае, таксама дакладна.

904
01:15:36,670 --> 01:15:41,510
>> Добрая праца! Падобна на тое, мы паспяхова напісана ўстаўкі.

905
01:15:41,510 --> 01:15:47,430
Гэта ўсё, што ў нас ёсць праблемы спецыфікацыі для набору на гэтым тыдні.

906
01:15:47,430 --> 01:15:51,720
Адна пацешная магчымасць падумаць аб тым, як бы вы на самой справе ідуць у

907
01:15:51,720 --> 01:15:55,340
і бясплатна усе вузлы ў гэтым дрэве.

908
01:15:55,340 --> 01:15:58,830
Мы можам зрабіць гэта рознымі спосабамі,

909
01:15:58,830 --> 01:16:01,930
але я пакіну гэта да вас, каб эксперымент,

910
01:16:01,930 --> 01:16:06,080
і як весела задачай, паспрабуйце і пераканайцеся, што вы можаце пераканацца,

911
01:16:06,080 --> 01:16:09,490
што гэты даклад Valgrind не вяртае памылкі і ўцечкі.

912
01:16:09,490 --> 01:16:12,880
>> Поспехі на Хафман гэтым тыдні пастаўленай задачы кадавання,

913
01:16:12,880 --> 01:16:14,380
і мы будзем бачыць вас на наступным тыдні!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]