1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Sekcja 7: More Comfortable]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[To jest CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Dobrze. Tak jak powiedziałem w moim e-mail,

5
00:00:10,110 --> 00:00:14,060
to będzie binary-tree-intensywny sekcji.

6
00:00:14,060 --> 00:00:16,820
Ale nie ma, że ​​wiele pytań.

7
00:00:16,820 --> 00:00:18,920
Więc będziemy próbować wyciągać na każde pytanie

8
00:00:18,920 --> 00:00:25,430
i idź do bolesnego szczegółowo wszystkich najlepszych sposobów robienia rzeczy.

9
00:00:25,430 --> 00:00:31,200
Tak więc na samym początku, idziemy poprzez rysunki próbkowania drzew binarnych i rzeczy.

10
00:00:31,200 --> 00:00:35,970
Więc tutaj, "Pamiętaj, że drzewo binarne ma węzły podobne do tych z połączonej listy,

11
00:00:35,970 --> 00:00:38,150
chyba zamiast jednego wskaźnika są dwa: jeden dla lewego "dziecko"

12
00:00:38,150 --> 00:00:41,950
i jeden dla dziecka "prawej". "

13
00:00:41,950 --> 00:00:45,630
Więc drzewo binarne jest jak połączonej listy,

14
00:00:45,630 --> 00:00:47,910
z wyjątkiem struktury będzie miał dwa wskaźniki.

15
00:00:47,910 --> 00:00:51,390
Jest trójkowy drzewa, które będą mieć trzy wskaźniki,

16
00:00:51,390 --> 00:00:56,540
są N-ary drzew, które po prostu mają ogólny wskaźnik

17
00:00:56,540 --> 00:01:00,320
że musieli malloc być wystarczająco duże, aby

18
00:01:00,320 --> 00:01:04,840
tyle wskaźniki do wszystkich możliwych dzieci.

19
00:01:04,840 --> 00:01:08,200
Więc drzewo binarne okazuje się mieć stałą liczbę dwóch.

20
00:01:08,200 --> 00:01:11,260
Jeśli chcesz, możesz podać połączonej listy jako jednoargumentowej drzewa,

21
00:01:11,260 --> 00:01:15,360
ale nie sądzę, że ktoś nazywa go.

22
00:01:15,360 --> 00:01:18,060
"Narysuj pola-i-strzałki schemat węzła drzewa binarnego

23
00:01:18,060 --> 00:01:24,110
zawierającą ulubiony numer Nate'a, 7, gdzie każdy wskaźnik dziecko jest null. "

24
00:01:24,110 --> 00:01:27,780
Więc iPad mode.

25
00:01:27,780 --> 00:01:30,280
>> To będzie bardzo proste.

26
00:01:30,280 --> 00:01:36,150
My tylko będziemy mieć węzeł, narysuję go jako plac.

27
00:01:36,150 --> 00:01:38,730
A ja będę czerpać wartości tutaj.

28
00:01:38,730 --> 00:01:41,090
Więc wartość pójdzie tu,

29
00:01:41,090 --> 00:01:44,770
i tu będziemy mieć lewy wskaźnik na lewo i prawo wskaźnik po prawej stronie.

30
00:01:44,770 --> 00:01:50,430
I to jest bardzo wiele, więc konwencja nazwać to po lewej i prawej stronie, nazwy wskaźnika.

31
00:01:50,430 --> 00:01:52,460
Obie te będą nieważne.

32
00:01:52,460 --> 00:01:57,870
To będzie po prostu pusty, i że będzie po prostu null.

33
00:01:57,870 --> 00:02:03,630
Okay. Więc z powrotem tutaj.

34
00:02:03,630 --> 00:02:05,700
"Dzięki połączonej listy, mieliśmy tylko do przechowywania wskaźnika

35
00:02:05,700 --> 00:02:09,639
do pierwszego węzła na liście, aby zapamiętać całą listę, lub całą listę.

36
00:02:09,639 --> 00:02:11,650
Podobnie, z drzew, tylko do przechowywania wskaźnik

37
00:02:11,650 --> 00:02:13,420
w pojedynczym węźle, aby pamiętać całego drzewa.

38
00:02:13,420 --> 00:02:15,980
Ten węzeł jest calle 'root' z drzewa.

39
00:02:15,980 --> 00:02:18,320
Opierać się na diagramie z przed lub narysować nową

40
00:02:18,320 --> 00:02:21,690
takie, że masz skrzynie-i-strzałki Przedstawienie binarne drzewo

41
00:02:21,690 --> 00:02:25,730
o wartość 7, a następnie w 3 w lewo

42
00:02:25,730 --> 00:02:32,760
, a następnie 9 na prawo, a następnie 6 na prawo od 3 ".

43
00:02:32,760 --> 00:02:34,810
Zobaczmy, czy dobrze pamiętam to wszystko w mojej głowie.

44
00:02:34,810 --> 00:02:37,670
Więc to będzie nasz główny tutaj.

45
00:02:37,670 --> 00:02:41,600
Zjemy wskaźnik gdzieś, coś, co my nazywamy pierwiastek

46
00:02:41,600 --> 00:02:45,140
i to wskazuje na tego faceta.

47
00:02:45,140 --> 00:02:48,490
Teraz, aby utworzyć nowy węzeł,

48
00:02:48,490 --> 00:02:52,870
co mamy, 3 na lewo?

49
00:02:52,870 --> 00:02:57,140
Więc nowy węzeł z 3, i to początkowo wskazuje null.

50
00:02:57,140 --> 00:02:59,190
Ja po prostu postawić N.

51
00:02:59,190 --> 00:03:02,250
Teraz chcemy, aby to przejść z lewej 7.

52
00:03:02,250 --> 00:03:06,840
Więc zmienić ten wskaźnik do teraz wskazywać na tego faceta.

53
00:03:06,840 --> 00:03:12,420
I robimy to samo. Chcemy 9 tutaj

54
00:03:12,420 --> 00:03:14,620
które początkowo po prostu mówi null.

55
00:03:14,620 --> 00:03:19,600
Mamy zamiar zmienić ten wskaźnik, punkt do 9,

56
00:03:19,600 --> 00:03:23,310
i chcemy obecnie umieścić 6 do 3 prawa.

57
00:03:23,310 --> 00:03:32,170
Więc to będzie - zrób 6.

58
00:03:32,170 --> 00:03:34,310
I że facet będzie wskazywać tam.

59
00:03:34,310 --> 00:03:38,320
Okay. Więc to wszystko wymaga od nas uwagi.

60
00:03:38,320 --> 00:03:42,770
>> A teraz chodźmy na niektóre terminologii.

61
00:03:42,770 --> 00:03:46,690
Już rozmawialiśmy o tym, jak korzeń drzewa jest najwyżej położony węzeł w drzewie.

62
00:03:46,690 --> 00:03:54,720
Jeden zawierający 7. Węzły na dole drzewa nazywane są liście.

63
00:03:54,720 --> 00:04:01,240
Każdy węzeł, który ma tylko null jako jego dzieci jest liść.

64
00:04:01,240 --> 00:04:03,680
Tak to jest możliwe, jeśli nasze drzewo binarne jest tylko jeden węzeł,

65
00:04:03,680 --> 00:04:10,130
że drzewo jest liść, i to jest to.

66
00:04:10,130 --> 00:04:12,060
"'Height' z drzewa jest liczba przeskoków musisz dokonać

67
00:04:12,060 --> 00:04:16,620
aby dostać się z góry na liściu ".

68
00:04:16,620 --> 00:04:18,640
Zajmiemy się w sekundy, różnica

69
00:04:18,640 --> 00:04:21,940
między symetrycznych i niesymetrycznych drzew binarnych,

70
00:04:21,940 --> 00:04:29,470
ale teraz, całkowita wysokość tego drzewa

71
00:04:29,470 --> 00:04:34,520
Chciałbym powiedzieć, to 3, chociaż jeśli policzyć ilość chmielu

72
00:04:34,520 --> 00:04:39,710
trzeba zrobić, aby dostać się do 9, to jest to naprawdę tylko wysokość 2.

73
00:04:39,710 --> 00:04:43,340
Teraz jest to niesymetryczne drzewo binarne,

74
00:04:43,340 --> 00:04:49,840
ale my rozmawialiśmy o zrównoważony, gdy robi się istotne.

75
00:04:49,840 --> 00:04:52,040
Więc teraz możemy mówić o węzły w drzewie w kategoriach

76
00:04:52,040 --> 00:04:54,700
w stosunku do innych węzłów w drzewie.

77
00:04:54,700 --> 00:04:59,730
Więc mamy teraz rodzice, dzieci, rodzeństwo, przodków i potomków.

78
00:04:59,730 --> 00:05:05,650
Są one dość zdrowego rozsądku, co one oznaczają.

79
00:05:05,650 --> 00:05:09,610
Jeśli pytamy - to rodziców.

80
00:05:09,610 --> 00:05:12,830
Więc co jest rodzicem 3?

81
00:05:12,830 --> 00:05:16,090
[Studenci] 7. >> Tak. Rodzic jest po prostu będzie, co wskazuje na ciebie.

82
00:05:16,090 --> 00:05:20,510
Więc co to dzieci 7?

83
00:05:20,510 --> 00:05:23,860
[Studenci] 3 i 9. >> Tak.

84
00:05:23,860 --> 00:05:26,460
Zauważ, że "dzieci" oznacza dosłownie dzieci,

85
00:05:26,460 --> 00:05:31,010
tak 6 nie stosuje się, bo to jak wnuka.

86
00:05:31,010 --> 00:05:35,540
Ale potem, jeśli pójdziemy potomków, więc co to potomkowie 7?

87
00:05:35,540 --> 00:05:37,500
[Studenci] 3, 6 i 9. >> Tak.

88
00:05:37,500 --> 00:05:42,330
Potomkami węzła głównego będzie wszystko w drzewie,

89
00:05:42,330 --> 00:05:47,950
wyjątkiem może sam węzeł główny, jeśli nie chcesz, aby uznać, że potomek.

90
00:05:47,950 --> 00:05:50,750
I wreszcie, przodkowie, więc jest to w przeciwnym kierunku.

91
00:05:50,750 --> 00:05:55,740
Więc jakie są przodkowie 6?

92
00:05:55,740 --> 00:05:58,920
[Studenci] 3 i 7. >> Tak. 9 nie jest włączony.

93
00:05:58,920 --> 00:06:02,520
To jest po prostu bezpośredni rodowód powrotem do korzeni

94
00:06:02,520 --> 00:06:13,230
będzie wasi przodkowie.

95
00:06:13,230 --> 00:06:16,300
>> "Mówimy, że drzewo binarne jest" uporządkowane ", jeśli dla każdego węzła w drzewie,

96
00:06:16,300 --> 00:06:19,530
wszystkich jego potomków po lewej mają mniejsze wartości

97
00:06:19,530 --> 00:06:22,890
i wszystkie te na prawo mają większe wartości.

98
00:06:22,890 --> 00:06:27,060
Na przykład, wyżej drzewa zarządza, ale to nie jest możliwe tylko uporządkowanym ułożeniem. "

99
00:06:27,060 --> 00:06:30,180
Zanim przejdziemy do tego,

100
00:06:30,180 --> 00:06:36,420
sortowane Drzewo binarne jest również znany jako binarne drzewo wyszukiwania.

101
00:06:36,420 --> 00:06:38,660
Tu zdarzyć się nazywając ją uporządkowaną drzewa binarnego,

102
00:06:38,660 --> 00:06:41,850
ale nigdy nie słyszałem, że nazywa zamówić drzewo binarne przed,

103
00:06:41,850 --> 00:06:46,650
oraz quiz jesteśmy znacznie bardziej prawdopodobne umieścić drzewo binarne wyszukiwania.

104
00:06:46,650 --> 00:06:49,250
Oni są jednym i tym samym,

105
00:06:49,250 --> 00:06:54,580
i to jest ważne, aby rozpoznać różnicę między drzewa binarnego i drzewa wyszukiwania binarnego.

106
00:06:54,580 --> 00:06:58,830
Drzewo binarne jest tylko drzewo, które wskazuje na dwie rzeczy.

107
00:06:58,830 --> 00:07:02,120
Każdy węzeł wskazuje na dwie rzeczy.

108
00:07:02,120 --> 00:07:06,310
Nie ma żadnego uzasadnienia o wartościach, że wskazuje.

109
00:07:06,310 --> 00:07:11,370
Tak jak tutaj, ponieważ jest to drzewo binarne wyszukiwanie,

110
00:07:11,370 --> 00:07:14,030
Wiemy, że jeśli pójdziemy na lewo od 7,

111
00:07:14,030 --> 00:07:16,670
następnie wszystkie wartości, które możemy ewentualnie dotrzeć

112
00:07:16,670 --> 00:07:19,310
przechodząc lewej 7 musi być mniejsza niż 7.

113
00:07:19,310 --> 00:07:24,070
Należy zauważyć, że wszystkie wartości są mniejsze niż 7 3 i 6.

114
00:07:24,070 --> 00:07:26,040
Te są po lewej stronie 7.

115
00:07:26,040 --> 00:07:29,020
Jeśli idziemy na prawo od 7, wszystko musi być większa niż 7,

116
00:07:29,020 --> 00:07:33,220
tak 9 jest na prawo od 7, więc jesteśmy dobrzy.

117
00:07:33,220 --> 00:07:36,150
To nie przypadek binarne drzewo jest

118
00:07:36,150 --> 00:07:40,020
dla zwykłego drzewa binarny może po prostu mieć 3 na górze, 7 w lewo,

119
00:07:40,020 --> 00:07:47,630
9 do 7 w lewo, nie ma uporządkowania wartości ogóle.

120
00:07:47,630 --> 00:07:56,140
Teraz, nie będzie faktycznie to zrobić, bo to nudne i niepotrzebne,

121
00:07:56,140 --> 00:07:59,400
ale "staramy się wyciągnąć tyle zamówionych drzew jak można myśleć

122
00:07:59,400 --> 00:08:01,900
za pomocą numerów 7, 3, 9, i 6.

123
00:08:01,900 --> 00:08:06,800
Ile odrębne ustalenia są tam? Co jest wysokość każdego? "

124
00:08:06,800 --> 00:08:10,480
>> Zrobimy kilka, ale główną ideą jest,

125
00:08:10,480 --> 00:08:16,530
jest to w żaden sposób wyjątkowy reprezentacji drzewa binarnego zawierającego te wartości.

126
00:08:16,530 --> 00:08:22,760
Wszystko, czego potrzebujesz to trochę drzewo binarne, które zawiera 7, 3, 6 i 9.

127
00:08:22,760 --> 00:08:25,960
Inny możliwy będzie ważne jeden korzeń 3

128
00:08:25,960 --> 00:08:30,260
iść w lewo i to jest 6, idź w lewo i to jest 7,

129
00:08:30,260 --> 00:08:32,730
iść w lewo i to jest 9.

130
00:08:32,730 --> 00:08:36,169
To jest całkowicie poprawny drzewo wyszukiwania binarnego.

131
00:08:36,169 --> 00:08:39,570
To nie jest bardzo przydatne, bo to jest jak połączonej listy

132
00:08:39,570 --> 00:08:43,750
i wszystkie te wskaźniki są po prostu null.

133
00:08:43,750 --> 00:08:48,900
Ale to jest ważne drzewo. Tak?

134
00:08:48,900 --> 00:08:51,310
[Student] Czy nie wartości muszą być większe z prawej strony?

135
00:08:51,310 --> 00:08:56,700
Czy jest to -? >> To chciałem przejść na inny sposób.

136
00:08:56,700 --> 00:09:00,960
Jest też - tak, niech przełączyć to.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Dobry chwyt.

138
00:09:07,770 --> 00:09:11,730
Nadal ma słuchać co search drzewo binarne ma robić.

139
00:09:11,730 --> 00:09:15,650
Tak więc na lewo Wszystko musi być mniejsza niż w danym węźle.

140
00:09:15,650 --> 00:09:23,180
Moglibyśmy po prostu przenieść, powiedzmy, ten 6 i umieścić go tutaj.

141
00:09:23,180 --> 00:09:26,880
Nie, nie możemy. Dlaczego wciąż to robi?

142
00:09:26,880 --> 00:09:35,350
Zróbmy - tutaj jest 6, tutaj jest 7, 6 punktów do 3.

143
00:09:35,350 --> 00:09:39,290
To jest nadal ważne drzewo wyszukiwania binarnego.

144
00:09:39,290 --> 00:09:49,260
Co jest nie tak jeśli ja - zobaczymy czy uda mi się wymyślić rozwiązania.

145
00:09:49,260 --> 00:09:52,280
Tak, w porządku. Więc co jest nie tak z tego drzewa?

146
00:09:52,280 --> 00:10:08,920
Chyba już wam wskazówkę, że coś jest nie tak z nim.

147
00:10:08,920 --> 00:10:14,430
Dlaczego wciąż to robi?

148
00:10:14,430 --> 00:10:18,510
Okay. Wygląda to rozsądne.

149
00:10:18,510 --> 00:10:22,590
Jeśli przyjrzeć się każdego węzła, jak 7, a następnie w lewo 7 jest 3.

150
00:10:22,590 --> 00:10:24,960
Więc mamy 3, rzecz z prawej 3 jest 6.

151
00:10:24,960 --> 00:10:27,750
I jeśli patrzeć na 6, w prawo, co 6 jest 9.

152
00:10:27,750 --> 00:10:30,910
Więc dlaczego nie jest to ważne drzewo wyszukiwania binarnego?

153
00:10:30,910 --> 00:10:36,330
[Studentów] 9 ciągle do lewej 7. >> Tak.

154
00:10:36,330 --> 00:10:43,710
To musi być prawda, że ​​wszystkie wartości można ewentualnie dotrzeć idąc z lewej 7 mniej niż 7.

155
00:10:43,710 --> 00:10:49,120
Jeśli idziemy na lewo od 7, mamy do 3 i możemy jeszcze dostać się do 6,

156
00:10:49,120 --> 00:10:52,520
można jeszcze dostać się do 9, ale już po mniej niż 7,

157
00:10:52,520 --> 00:10:55,070
nie powinniśmy być w stanie dotrzeć do wielu, które jest większe niż 7.

158
00:10:55,070 --> 00:10:59,830
Więc to nie ważne jest drzewo binarne wyszukiwania.

159
00:10:59,830 --> 00:11:02,330
>> Mój brat miał w rzeczywistości pytanie wywiad

160
00:11:02,330 --> 00:11:07,760
że był w zasadzie, po prostu kod do czegoś w celu weryfikacji

161
00:11:07,760 --> 00:11:10,500
czy drzewo to drzewo binarne wyszukiwanie,

162
00:11:10,500 --> 00:11:13,580
więc pierwszą rzeczą, jaką zrobił, było po prostu sprawdzić

163
00:11:13,580 --> 00:11:17,020
jeśli lewy i prawy są poprawne, a następnie iteracyjne tam.

164
00:11:17,020 --> 00:11:19,700
Ale nie możesz po prostu zrobić, masz do śledzenia

165
00:11:19,700 --> 00:11:22,550
z faktu, że teraz, kiedy już odszedł na lewo od 7,

166
00:11:22,550 --> 00:11:26,340
wszystko w tym poddrzewie musi być mniejsza niż 7.

167
00:11:26,340 --> 00:11:28,430
Algorytm poprawne musi śledzić

168
00:11:28,430 --> 00:11:35,970
w granicach, które może ewentualnie wartości mieszczą w.

169
00:11:35,970 --> 00:11:38,360
Nie będzie przejść przez wszystkie z nich.

170
00:11:38,360 --> 00:11:41,630
Jest miły stosunek nawrót,

171
00:11:41,630 --> 00:11:44,810
mimo, że nie dostał się do tych, czy nie będą się do nich,

172
00:11:44,810 --> 00:11:47,030
określenie, ile faktycznie istnieją.

173
00:11:47,030 --> 00:11:53,180
Tak więc istnieje 14 z nich.

174
00:11:53,180 --> 00:11:56,020
Pomysł w jaki sposób to zrobić matematycznie jest jak,

175
00:11:56,020 --> 00:11:59,770
można wybrać dowolny pojedynczy jeden, który będzie głównym węzłem,

176
00:11:59,770 --> 00:12:03,160
a następnie, jeśli wybiorę 7 jest węzeł główny,

177
00:12:03,160 --> 00:12:08,150
to nie są, powiedzmy, niektóre numery, które mogą go mieć mój lewy węzeł,

178
00:12:08,150 --> 00:12:10,440
i jest kilka numerów, które mogą być moje prawo węzeł

179
00:12:10,440 --> 00:12:15,090
Ale jeśli mam całkowitą liczbę n, to kwota, która może iść w lewo

180
00:12:15,090 --> 00:12:18,820
plus kwota, która może iść w prawo jest n - 1.

181
00:12:18,820 --> 00:12:26,130
Tak liczb pozostałych, muszą być w stanie przejść albo w lewo lub w prawo.

182
00:12:26,130 --> 00:12:31,580
Trudno, że jeśli mogę umieścić 3 pierwszy wtedy wszystko musi iść w lewo,

183
00:12:31,580 --> 00:12:35,080
ale jeśli mogę umieścić 7, to niektóre rzeczy mogą pójść w lewo i niektóre rzeczy mogą iść w prawo.

184
00:12:35,080 --> 00:12:39,570
Oraz '3 pierwszy "Chciałem wszystko może iść w prawo.

185
00:12:39,570 --> 00:12:42,350
To naprawdę, po prostu trzeba myśleć o tym, jak,

186
00:12:42,350 --> 00:12:47,980
jak wiele rzeczy może pójść na następnym poziomie drzewa.

187
00:12:47,980 --> 00:12:50,420
I to wychodzi się 14, lub można wyciągnąć wszystkich z nich,

188
00:12:50,420 --> 00:12:54,650
a dostaniesz 14.

189
00:12:54,650 --> 00:13:01,120
>> Wracając tu,

190
00:13:01,120 --> 00:13:03,510
"Zamówione binarne drzewa są fajne, bo można je przeglądać

191
00:13:03,510 --> 00:13:06,910
w bardzo podobny sposób do poszukiwania na posortowanej tablicy.

192
00:13:06,910 --> 00:13:10,120
Aby to zrobić, możemy zacząć od korzenia i wypracować sobie drogę w dół drzewa

193
00:13:10,120 --> 00:13:13,440
na liściach, sprawdzając każdy węzeł systemu wartości w odniesieniu do wartości mamy poszukujących.

194
00:13:13,440 --> 00:13:15,810
Jeśli bieżący węzeł wartość jest mniejsza od wartości szukamy,

195
00:13:15,810 --> 00:13:18,050
przejść obok węzła prawego dziecka.

196
00:13:18,050 --> 00:13:20,030
W przeciwnym razie przejdź do węzła lewego dziecka.

197
00:13:20,030 --> 00:13:22,800
W pewnym momencie, to albo będzie wartość, której szukasz, lub będziesz uruchomić do null,

198
00:13:22,800 --> 00:13:28,520
wskazując wartość nie jest w drzewie. "

199
00:13:28,520 --> 00:13:32,450
Muszę przerysować drzewo mieliśmy wcześniej, to zajmie chwilę.

200
00:13:32,450 --> 00:13:38,280
Ale chcemy patrzeć, czy 6, 10, i 1 są w drzewie.

201
00:13:38,280 --> 00:13:49,180
Więc co to było, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Numery, które chcesz wyszukać, chcemy spojrzeć 6.

203
00:13:52,730 --> 00:13:55,440
Jak to działa algorytm?

204
00:13:55,440 --> 00:14:03,040
Cóż, mamy też trochę wskaźnik roota do naszego drzewa.

205
00:14:03,040 --> 00:14:12,460
I pójdziemy do korzenia i powiedzieć, czy jest to wartość równa wartości jesteśmy w poszukiwaniu?

206
00:14:12,460 --> 00:14:15,000
Więc szukamy 6, więc to nie jest równe.

207
00:14:15,000 --> 00:14:20,140
Więc wracamy, i teraz możemy powiedzieć, ok, więc 6 jest mniejsza niż 7.

208
00:14:20,140 --> 00:14:23,940
Czy to znaczy, że chcemy, aby przejść w lewo, czy chcemy iść na prawo?

209
00:14:23,940 --> 00:14:27,340
[Student] Lewy. >> Tak.

210
00:14:27,340 --> 00:14:33,340
Jest to znacznie łatwiejsze, wszystko co musisz zrobić, to wyciągnąć jedną możliwą węzła drzewa

211
00:14:33,340 --> 00:14:37,760
a następnie don't - zamiast starać się myśleć w głowie,

212
00:14:37,760 --> 00:14:40,020
dobrze, jeśli jest mniejsza, mam iść na lewo lub przejdź prawo,

213
00:14:40,020 --> 00:14:43,030
po prostu patrząc na to zdjęcie, to jest jasne, że muszę iść na lewo

214
00:14:43,030 --> 00:14:47,700
jeśli węzeł jest większy niż wartość szukam.

215
00:14:47,700 --> 00:14:52,600
Więc idź na lewo, teraz jestem w 3.

216
00:14:52,600 --> 00:14:57,770
Chcę - 3 jest mniejsza niż wartość Szukam, który jest 6.

217
00:14:57,770 --> 00:15:03,420
Idziemy więc w prawo, a teraz kończy się na 6,

218
00:15:03,420 --> 00:15:07,380
która jest wartością Szuka, więc zwróci true.

219
00:15:07,380 --> 00:15:15,760
Następna wartość Idę szukać jest 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Więc 10, teraz będzie - obciąć, że - podąży korzenia.

221
00:15:23,230 --> 00:15:27,670
Teraz, 10 będzie większa niż 7, więc chcę spojrzeć w prawo.

222
00:15:27,670 --> 00:15:31,660
Mam zamiar przyjechać tu, 10 będzie większa niż 9,

223
00:15:31,660 --> 00:15:34,520
więc będę chciał spojrzeć w prawo.

224
00:15:34,520 --> 00:15:42,100
Przychodzę tutaj, ale tutaj teraz jestem na null.

225
00:15:42,100 --> 00:15:44,170
Co mam zrobić, jeśli uderzę null?

226
00:15:44,170 --> 00:15:47,440
[Student] Powrót fałsz? >> Tak. Nie mogę znaleźć 10.

227
00:15:47,440 --> 00:15:49,800
1 będzie niemal identyczny przypadek,

228
00:15:49,800 --> 00:15:51,950
oprócz tego, że po prostu będzie odwrócony; zamiast szukać

229
00:15:51,950 --> 00:15:56,540
w dół z prawej strony, mam zamiar spojrzeć na lewą stronę.

230
00:15:56,540 --> 00:16:00,430
>> Teraz myślę, że rzeczywiście dostać się do kodu.

231
00:16:00,430 --> 00:16:04,070
Oto, gdzie - otwarcie CS50 urządzenie i nawigować drogę tam,

232
00:16:04,070 --> 00:16:07,010
ale możesz też zrobić to w przestrzeni.

233
00:16:07,010 --> 00:16:09,170
To chyba idealny to zrobić w przestrzeni,

234
00:16:09,170 --> 00:16:13,760
, ponieważ można pracować w przestrzeni.

235
00:16:13,760 --> 00:16:19,170
"Najpierw musimy nową definicję typu dla węzła drzewa binarnego zawierającego wartości int.

236
00:16:19,170 --> 00:16:21,400
Korzystanie boilerplate typedef poniżej

237
00:16:21,400 --> 00:16:24,510
utworzyć nową definicję typu dla węzła w drzewa binarnego.

238
00:16:24,510 --> 00:16:27,930
Jeśli utkniesz. . . "Bla, bla, bla. Okay.

239
00:16:27,930 --> 00:16:30,380
Więc postawmy boilerplate tutaj

240
00:16:30,380 --> 00:16:41,630
typedef struct node, i węzeł. Tak, w porządku.

241
00:16:41,630 --> 00:16:44,270
Więc jakie są pola Będziemy chcieli w naszym węźle?

242
00:16:44,270 --> 00:16:46,520
[Student] Int a następnie dwa wskaźniki?

243
00:16:46,520 --> 00:16:49,700
Int >> wartość, dwa wskaźniki? Jak napisać wskaźniki?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Należy powiększyć Tak, więc węzeł struct * w lewo,

245
00:16:58,440 --> 00:17:01,320
i struct node * prawo.

246
00:17:01,320 --> 00:17:03,460
I pamiętam dyskusję z ostatniej chwili

247
00:17:03,460 --> 00:17:15,290
że to nie ma sensu, to nie ma sensu,

248
00:17:15,290 --> 00:17:18,270
to nie ma sensu.

249
00:17:18,270 --> 00:17:25,000
Musisz tam wszystko w celu zdefiniowania tego rekursywnego struct.

250
00:17:25,000 --> 00:17:27,970
Ok, więc to co nasze drzewo będzie wyglądać.

251
00:17:27,970 --> 00:17:37,670
Jeśli zrobiliśmy trinary drzewo, wówczas węzeł może wyglądać jak B1, B2, struct node * B3,

252
00:17:37,670 --> 00:17:43,470
gdzie b jest oddział - faktycznie, mam więcej to słyszeli, lewy, środkowy, prawy, ale nieważne.

253
00:17:43,470 --> 00:17:55,610
Interesują nas tylko binarne, więc w prawo, w lewo.

254
00:17:55,610 --> 00:17:59,110
"Teraz zadeklarować zmienną globalną * węzła do korzenia drzewa."

255
00:17:59,110 --> 00:18:01,510
Więc nie będziemy tego robić.

256
00:18:01,510 --> 00:18:08,950
W celu rzeczy nieco trudniejsze i bardziej uogólnione,

257
00:18:08,950 --> 00:18:11,570
nie będziemy mieć zmienną globalną węzła.

258
00:18:11,570 --> 00:18:16,710
Zamiast tego, w głównym będziemy deklarować wszystkie węzłów rzeczy,

259
00:18:16,710 --> 00:18:20,500
a to oznacza, że ​​poniżej, kiedy zaczną

260
00:18:20,500 --> 00:18:23,130
nasza funkcja zawiera i nasza funkcja insert,

261
00:18:23,130 --> 00:18:27,410
zamiast naszych obejmuje funkcje, tylko przy użyciu tej zmiennej globalnej węzła,

262
00:18:27,410 --> 00:18:34,280
będziemy mieć to przyjąć jako argument na drzewo, że chcemy go przetworzyć.

263
00:18:34,280 --> 00:18:36,650
Mając zmienną globalną miało to łatwiejsze.

264
00:18:36,650 --> 00:18:42,310
Wracamy do rzeczy trudniejsze.

265
00:18:42,310 --> 00:18:51,210
Teraz weź minut lub tak po prostu zrobić coś takiego,

266
00:18:51,210 --> 00:18:57,690
gdzie wewnątrz Głównym chcesz stworzyć z tego drzewa, i to wszystko, co chcę zrobić.

267
00:18:57,690 --> 00:19:04,530
Spróbuj zbudować to drzewo w głównej funkcji.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Więc nie trzeba nawet skonstruowali drzewie przez całą drogę jeszcze.

269
00:19:47,610 --> 00:19:49,840
Ale każdy ma coś mogłem podciągnąć

270
00:19:49,840 --> 00:20:03,130
pokazać, jak można by rozpocząć budowę taką choinkę?

271
00:20:03,130 --> 00:20:08,080
[Student] Ktoś banging, próbując się wydostać.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Każdy komfortowo z ich budowy drzewa?

273
00:20:13,100 --> 00:20:15,520
[Student] Jasne. To nie jest zrobione. >> Jest dobrze. Możemy po prostu skończyć -

274
00:20:15,520 --> 00:20:26,860
oh, można go zapisać? Brawo.

275
00:20:26,860 --> 00:20:32,020
Więc tutaj mamy - Och, jestem nieco obcięte.

276
00:20:32,020 --> 00:20:34,770
Mam powiększony?

277
00:20:34,770 --> 00:20:37,730
Powiększyć, przewinąć się. >> Mam pytanie. >> Tak?

278
00:20:37,730 --> 00:20:44,410
[Student] Po zdefiniowaniu struktury, są takie rzeczy jak inicjowany do niczego?

279
00:20:44,410 --> 00:20:47,160
[Bowden] L. >> Okay. Więc trzeba by zainicjować -

280
00:20:47,160 --> 00:20:50,450
[Bowden] L. Podczas definiowania lub podczas deklarowania struct,

281
00:20:50,450 --> 00:20:55,600
to nie jest inicjowany domyślnie to tylko jak jeśli zadeklarować int.

282
00:20:55,600 --> 00:20:59,020
To jest dokładnie to samo. To tak, jakby każdego z poszczególnych pól

283
00:20:59,020 --> 00:21:04,460
może mieć wartość śmieci w nim. >> I to jest możliwe do zdefiniowania - lub zadeklarować struct

284
00:21:04,460 --> 00:21:07,740
w sposób, który to robi zainicjować je?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Tak. Więc, składnia inicjalizacji skrót

286
00:21:13,200 --> 00:21:18,660
będzie wyglądać -

287
00:21:18,660 --> 00:21:22,200
Są dwa sposoby, możemy to zrobić. Myślę, że powinniśmy go skompilować

288
00:21:22,200 --> 00:21:25,840
aby upewnić się, dzyń również to robi.

289
00:21:25,840 --> 00:21:28,510
Kolejność argumentów, że jest w tej struktury,

290
00:21:28,510 --> 00:21:32,170
umieścić jak kolejność argumentów wewnątrz tych klamrach.

291
00:21:32,170 --> 00:21:35,690
Więc jeśli chcesz zainicjować go 9 i lewo jest nieważna i następnie w prawo być null,

292
00:21:35,690 --> 00:21:41,570
byłoby 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternatywą jest, a redaktor nie lubi tej składni,

294
00:21:47,890 --> 00:21:50,300
i myśli, chcę nowy blok,

295
00:21:50,300 --> 00:22:01,800
ale alternatywą jest coś takiego jak -

296
00:22:01,800 --> 00:22:04,190
tutaj, włożę go na nowej linii.

297
00:22:04,190 --> 00:22:09,140
Można jawnie powiedzieć, nie pamiętam dokładnej składni.

298
00:22:09,140 --> 00:22:13,110
Więc można wyraźnie uwzględnią je po imieniu i powiedzieć,

299
00:22:13,110 --> 00:22:21,570
. Wartość c lub. = 9,. Lewy = NULL.

300
00:22:21,570 --> 00:22:24,540
Zgaduję, te muszą być przecinki.

301
00:22:24,540 --> 00:22:29,110
. Prawo = NULL, więc w ten sposób nie zrobić

302
00:22:29,110 --> 00:22:33,780
rzeczywiście trzeba znać kolejność struct,

303
00:22:33,780 --> 00:22:36,650
i kiedy to czytasz, jest dużo bardziej wyraźne

304
00:22:36,650 --> 00:22:41,920
o tym, co jest wartością jest inicjowany.

305
00:22:41,920 --> 00:22:44,080
>> Dzieje się to za jedną z rzeczy, które -

306
00:22:44,080 --> 00:22:49,100
tak, w przeważającej części, C + + jest rozszerzeniem C

307
00:22:49,100 --> 00:22:54,160
Możesz wziąć kod C, przenieść go do C + +, i powinno się skompilować.

308
00:22:54,160 --> 00:22:59,570
To jest jedna z tych rzeczy, że C + + nie obsługują, więc ludzie starają się nie robić.

309
00:22:59,570 --> 00:23:01,850
Nie wiem czy to tylko dlatego ludzie starają się nie robić,

310
00:23:01,850 --> 00:23:10,540
ale w przypadku, gdy potrzebowałem go używać potrzebny do pracy z C + + i tak nie mogę tego użyć.

311
00:23:10,540 --> 00:23:14,000
Innym przykładem, że coś nie działa w C + + jest

312
00:23:14,000 --> 00:23:16,940
jak malloc zwraca "void *," technicznie,

313
00:23:16,940 --> 00:23:20,200
, ale można po prostu powiedzieć, char * x = malloc cokolwiek,

314
00:23:20,200 --> 00:23:22,840
i zostanie ona automatycznie rzutować na char *.

315
00:23:22,840 --> 00:23:25,450
Że automatyczne cast nie zdarza się w C + +.

316
00:23:25,450 --> 00:23:28,150
To nie byłoby skompilować, i jawnie trzeba powiedzieć

317
00:23:28,150 --> 00:23:34,510
char *, malloc, cokolwiek, by rzucić go na char *.

318
00:23:34,510 --> 00:23:37,270
Nie ma zbyt wielu rzeczy, C i C + + nie zgadzają się,

319
00:23:37,270 --> 00:23:40,620
ale to są dwa.

320
00:23:40,620 --> 00:23:43,120
Więc idziemy z tym składni.

321
00:23:43,120 --> 00:23:46,150
Ale nawet jeśli nie byliśmy z tym składni

322
00:23:46,150 --> 00:23:49,470
co to jest - może być w tym złego?

323
00:23:49,470 --> 00:23:52,170
[Student] I nie trzeba dereference go? >> Tak.

324
00:23:52,170 --> 00:23:55,110
Pamiętaj, że strzałka jest niejawna dereference,

325
00:23:55,110 --> 00:23:58,230
a więc gdy jesteśmy po prostu do czynienia z struct,

326
00:23:58,230 --> 00:24:04,300
chcemy wykorzystać. aby dostać się w środku pola struktury.

327
00:24:04,300 --> 00:24:07,200
I tylko raz używamy strzałki jest wtedy, gdy chcemy zrobić -

328
00:24:07,200 --> 00:24:13,450
dobrze, strzałka jest równoważne -

329
00:24:13,450 --> 00:24:17,020
to co by to oznaczało, gdyby kiedyś strzałkę.

330
00:24:17,020 --> 00:24:24,600
Wszystkie środki strzałka, dereference to, teraz jestem w struct, i mogę to pole.

331
00:24:24,600 --> 00:24:28,040
Albo dostać pole bezpośrednio lub nieprawidłowego i inne pola -

332
00:24:28,040 --> 00:24:30,380
Myślę, że to powinno być napięcie.

333
00:24:30,380 --> 00:24:33,910
Ale tutaj mam do czynienia tylko z struct, a nie wskaźnik do struktury,

334
00:24:33,910 --> 00:24:38,780
a więc nie można użyć strzałki.

335
00:24:38,780 --> 00:24:47,510
Ale takie rzeczy możemy zrobić dla wszystkich węzłów.

336
00:24:47,510 --> 00:24:55,790
O mój Boże.

337
00:24:55,790 --> 00:25:09,540
Jest 6, 7, i 3.

338
00:25:09,540 --> 00:25:16,470
Następnie możemy skonfigurować oddziały w naszym drzewie, możemy mieć 7 -

339
00:25:16,470 --> 00:25:21,650
Możemy mieć, jego lewy powinien wskazywać na 3.

340
00:25:21,650 --> 00:25:25,130
Więc jak to zrobić?

341
00:25:25,130 --> 00:25:29,320
[Studenci, niezrozumiały] >> Tak. Adres node3,

342
00:25:29,320 --> 00:25:34,170
a jeśli nie ma adresu, to po prostu nie skompilować.

343
00:25:34,170 --> 00:25:38,190
Ale pamiętaj, że są to wskaźniki do kolejnych węzłów.

344
00:25:38,190 --> 00:25:44,930
Prawo to powinno wskazywać na 9,

345
00:25:44,930 --> 00:25:53,330
i 3 powinny być skierowane na prawo do 6.

346
00:25:53,330 --> 00:25:58,480
Myślę, że to wszystko. Wszelkie uwagi lub pytania?

347
00:25:58,480 --> 00:26:02,060
[Student, niezrozumiały] korzeń będzie 7.

348
00:26:02,060 --> 00:26:08,210
Możemy tylko powiedzieć węzeł * ptr =

349
00:26:08,210 --> 00:26:14,160
lub root = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Dla naszych celów, będziemy mieć do czynienia z wkładką,

351
00:26:20,730 --> 00:26:25,490
więc będziemy chcieli napisać funkcję, aby dodać do tego drzewa binarnego

352
00:26:25,490 --> 00:26:34,230
i wkładka jest nieuchronnie zamiar zadzwonić malloc utworzyć nowy węzeł tego drzewa.

353
00:26:34,230 --> 00:26:36,590
Więc wszystko się bałagan z tym, że niektóre węzły

354
00:26:36,590 --> 00:26:38,590
Obecnie na stosie

355
00:26:38,590 --> 00:26:43,680
i pozostałe węzły są skończy się na stercie kiedy włożyć.

356
00:26:43,680 --> 00:26:47,640
Jest to całkowicie prawidłowy, ale jedynym powodem

357
00:26:47,640 --> 00:26:49,600
jesteśmy w stanie to zrobić na stosie

358
00:26:49,600 --> 00:26:51,840
ponieważ jest to taki dobry przykład, że wiemy

359
00:26:51,840 --> 00:26:56,360
drzewa ma być wykonane, 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Jeżeli nie są w tym, że to nie ma malloc w pierwszej kolejności.

361
00:27:02,970 --> 00:27:06,160
Jak zobaczymy nieco później, powinniśmy malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Teraz jest to całkowicie uzasadnione umieścić na stosie,

363
00:27:08,570 --> 00:27:14,750
ale zmieńmy to do wykonania malloc.

364
00:27:14,750 --> 00:27:17,160
Tak więc każdy z nich jest teraz będzie coś jak

365
00:27:17,160 --> 00:27:24,240
node * node9 = malloc (sizeof (node)).

366
00:27:24,240 --> 00:27:28,040
A teraz będziemy musieli zrobić naszą kontrolę.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - nie chcę, że -

368
00:27:34,010 --> 00:27:40,950
zwraca 1, a następnie możemy zrobić node9-> bo teraz to jest wskaźnik,

369
00:27:40,950 --> 00:27:45,300
wartość = 6, node9-> lewy = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> prawy = NULL,

371
00:27:48,930 --> 00:27:51,410
i będziemy musieli zrobić, że dla każdego z tych węzłów.

372
00:27:51,410 --> 00:27:57,490
Zamiast więc, postawmy go wewnątrz osobnej funkcji.

373
00:27:57,490 --> 00:28:00,620
Nazwijmy to węzeł * build_node,

374
00:28:00,620 --> 00:28:09,050
i jest nieco podobny do API Zapewniamy Huffmana.

375
00:28:09,050 --> 00:28:12,730
Dajemy Ci funkcje inicjatora dla drewna

376
00:28:12,730 --> 00:28:20,520
i Deconstructor "funkcje" w odniesieniu do tych samych drzew i do lasów.

377
00:28:20,520 --> 00:28:22,570
>> Więc będziemy mieć funkcję inicjatora

378
00:28:22,570 --> 00:28:25,170
wystarczy zbudować węzeł dla nas.

379
00:28:25,170 --> 00:28:29,320
I to będzie wyglądało prawie dokładnie tak, jak to.

380
00:28:29,320 --> 00:28:32,230
A ja nawet będzie leniwy i nie zmieniać nazwy zmiennej,

381
00:28:32,230 --> 00:28:34,380
chociaż node9 ma sensu już.

382
00:28:34,380 --> 00:28:38,610
Och, myślę, że jego wartość node9 nie powinno było 6.

383
00:28:38,610 --> 00:28:42,800
Teraz możemy wrócić node9.

384
00:28:42,800 --> 00:28:49,550
I tu powinniśmy wrócić null.

385
00:28:49,550 --> 00:28:52,690
Wszyscy zgadzają się, że funkcja build-węzłów?

386
00:28:52,690 --> 00:28:59,780
Więc teraz możemy po prostu zadzwonić, że aby zbudować dowolny węzeł o podanej wartości i wskazówki null.

387
00:28:59,780 --> 00:29:09,750
Teraz możemy wywołać, że możemy zrobić węzeł * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
I zróbmy. . .

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

390
00:29:33,980 --> 00:29:39,330
A teraz chcemy ustawić te same wskaźniki,

391
00:29:39,330 --> 00:29:42,470
chyba teraz wszystko jest już w zakresie wskaźników

392
00:29:42,470 --> 00:29:48,480
więc nie trzeba już adres.

393
00:29:48,480 --> 00:29:56,300
Okay. Więc co jest ostatnią rzeczą jaką chcesz zrobić?

394
00:29:56,300 --> 00:30:03,850
Jest sprawdzania błędów, że nie robię.

395
00:30:03,850 --> 00:30:06,800
Co zbudować powrót węzła?

396
00:30:06,800 --> 00:30:11,660
[Student, niezrozumiały] >> Tak. Jeśli malloc nie, powróci, null.

397
00:30:11,660 --> 00:30:16,460
Więc mam zamiar umieścić go leniwie tu zamiast z tym warunek dla każdego.

398
00:30:16,460 --> 00:30:22,320
Jeśli (node9 == NULL, lub - jeszcze prostsze,

399
00:30:22,320 --> 00:30:28,020
odpowiada to tylko jeśli nie node9.

400
00:30:28,020 --> 00:30:38,310
Więc jeśli nie node9 lub nie node6 lub nie node3 lub nie node7, powrót 1.

401
00:30:38,310 --> 00:30:42,850
Może powinniśmy wydrukować malloc nie powiodło się, czy coś takiego.

402
00:30:42,850 --> 00:30:46,680
[Student] Czy false równa null, jak również?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Każda wartość zerowa jest fałszywa.

404
00:30:51,290 --> 00:30:53,920
Więc null jest wartość zerowa.

405
00:30:53,920 --> 00:30:56,780
Zero to zero. False jest wartość zerowa.

406
00:30:56,780 --> 00:31:02,130
Wszelkie - dość dużo tylko 2 wartości zerowe są nieważne i zero,

407
00:31:02,130 --> 00:31:07,900
false jest tylko hash definiowana jako zero.

408
00:31:07,900 --> 00:31:13,030
Dotyczy to również, jeśli nie deklarują zmienną globalną.

409
00:31:13,030 --> 00:31:17,890
Jeśli mieliśmy rdzenia * węzła tu,

410
00:31:17,890 --> 00:31:24,150
następnie - Ciekawą rzeczą jest to, że zmienne globalne zawsze mają wartość początkową.

411
00:31:24,150 --> 00:31:27,500
To nie prawda funkcji, jak wewnątrz tutaj

412
00:31:27,500 --> 00:31:34,870
jeśli mamy, na przykład, node * lub x węzła.

413
00:31:34,870 --> 00:31:37,380
Nie mamy pojęcia, co x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
albo możemy je wydrukować i mogą być dowolne.

415
00:31:40,700 --> 00:31:44,980
To nie prawda ze zmiennych globalnych.

416
00:31:44,980 --> 00:31:47,450
Więc węzeł główny lub x węzła.

417
00:31:47,450 --> 00:31:53,410
Domyślnie, wszystko to jest globalne, jeśli nie jawnie zainicjowane pewną wartość,

418
00:31:53,410 --> 00:31:57,390
ma wartość zero, jako wartości.

419
00:31:57,390 --> 00:32:01,150
Więc tutaj, root * węzeł, nie jawnie zainicjować go do niczego,

420
00:32:01,150 --> 00:32:06,350
więc jego wartość domyślna będzie wartość null, która jest zerowa wartość wskaźników.

421
00:32:06,350 --> 00:32:11,870
Domyślna wartość x będzie oznaczać, że x.value jest zero,

422
00:32:11,870 --> 00:32:14,260
x.left jest null, a x.right jest null.

423
00:32:14,260 --> 00:32:21,070
Tak, ponieważ jest to struct, wszystkie pola tej struktury będą wartości zerowe.

424
00:32:21,070 --> 00:32:24,410
Nie trzeba używać, że tutaj, choć.

425
00:32:24,410 --> 00:32:27,320
[Ilustracja] elemencie są różne od innych zmiennych, a inne zmienne są

426
00:32:27,320 --> 00:32:31,400
wartości śmieci; są zer?

427
00:32:31,400 --> 00:32:36,220
[Bowdena] Inne wartości też. Więc w x, x będzie równa zeru.

428
00:32:36,220 --> 00:32:40,070
Jeśli to jest w zakresie globalnym, ma wartość początkową. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Albo wartość początkowa dałeś go lub zero.

430
00:32:48,950 --> 00:32:53,260
Myślę, że zajmuje się tym wszystkim.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Więc następnym część pytania pyta

432
00:32:58,390 --> 00:33:01,260
"Teraz chcemy napisać funkcję o nazwie zawiera

433
00:33:01,260 --> 00:33:04,930
z prototypem bool zawiera wartość typu int. "

434
00:33:04,930 --> 00:33:08,340
Nie będziemy robić bool zawiera wartość typu int.

435
00:33:08,340 --> 00:33:15,110
Nasz prototyp będzie wyglądać

436
00:33:15,110 --> 00:33:22,380
bool zawiera (wartość typu int.

437
00:33:22,380 --> 00:33:24,490
A potem mamy również zamiar przekazać go na drzewo

438
00:33:24,490 --> 00:33:28,870
że należy sprawdzanie, czy ma tę wartość.

439
00:33:28,870 --> 00:33:38,290
Więc node * drzewo). Okay.

440
00:33:38,290 --> 00:33:44,440
I wtedy możemy nazwać to coś w stylu:

441
00:33:44,440 --> 00:33:46,090
być może będziemy chcieli printf lub czegoś.

442
00:33:46,090 --> 00:33:51,040
Zawiera 6, nasz główny.

443
00:33:51,040 --> 00:33:54,300
To powinno zwrócić jeden lub prawdziwe,

444
00:33:54,300 --> 00:33:59,390
natomiast zawiera 5 root powinien return false.

445
00:33:59,390 --> 00:34:02,690
Więc weź sekund do realizacji tego.

446
00:34:02,690 --> 00:34:06,780
Można to zrobić albo iteracyjnie lub rekurencyjnie.

447
00:34:06,780 --> 00:34:09,739
Zaletą sposobu mamy ustawić rzeczy jest to, że

448
00:34:09,739 --> 00:34:12,300
to nadaje się do naszego rekurencyjnego rozwiązania jest znacznie łatwiejsze

449
00:34:12,300 --> 00:34:14,719
niż globalna zmienna sposób zrobił.

450
00:34:14,719 --> 00:34:19,750
Bo jeśli mamy tylko wartości int zawiera, to nie mają możliwości rekurencji dół poddrzewa.

451
00:34:19,750 --> 00:34:24,130
Musielibyśmy mieć oddzielną funkcję pomocnika, który recurses dół poddrzewa dla nas.

452
00:34:24,130 --> 00:34:29,610
Ale od kiedy zmienił go do podjęcia drzewo jako argument,

453
00:34:29,610 --> 00:34:32,760
które należy zawsze w pierwszej kolejności,

454
00:34:32,760 --> 00:34:35,710
teraz możemy recurse łatwiej.

455
00:34:35,710 --> 00:34:38,960
Więc iteracyjne lub rekurencyjne, pójdziemy na obu,

456
00:34:38,960 --> 00:34:46,139
ale zobaczymy, że cykliczne kończy się całkiem proste.

457
00:34:59,140 --> 00:35:02,480
Okay. Czy ktoś ma coś, co możemy pracować?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Mam iteracyjne rozwiązanie. >> Dobra, wielokrotnie.

459
00:35:12,000 --> 00:35:16,030
Dobra, to wygląda dobrze.

460
00:35:16,030 --> 00:35:18,920
Więc, chcesz iść z nami przez to?

461
00:35:18,920 --> 00:35:25,780
[Student] Jasne. Tak ustawić zmienną temp zdobyć pierwszy węzeł drzewa.

462
00:35:25,780 --> 00:35:28,330
A potem po prostu zapętlone podczas temp nie równa null,

463
00:35:28,330 --> 00:35:31,700
więc gdy był jeszcze w drzewie, tak myślę.

464
00:35:31,700 --> 00:35:35,710
I jeśli wartość jest równa wartości, że temperatura jest wskazanie,

465
00:35:35,710 --> 00:35:37,640
następnie zwraca tę wartość.

466
00:35:37,640 --> 00:35:40,210
W innym przypadku, to sprawdza czy nie jest po prawej lub lewej stronie.

467
00:35:40,210 --> 00:35:43,400
Jeśli kiedykolwiek sytuacji, w której nie ma już drzewa,

468
00:35:43,400 --> 00:35:47,330
wówczas zwraca - wychodzący z pętli i zwraca false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Dobra. Tak, że wydaje się być dobra.

470
00:35:52,190 --> 00:35:58,470
Ktoś ma jakieś uwagi na temat czegokolwiek?

471
00:35:58,470 --> 00:36:02,400
Nie mam żadnych uwag poprawności w ogóle.

472
00:36:02,400 --> 00:36:11,020
Jedna rzecz, którą możemy zrobić, to ten facet.

473
00:36:11,020 --> 00:36:21,660
Oh, to się go trochę wydłużone.

474
00:36:21,660 --> 00:36:33,460
Zrobię to w górę. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Każdy powinien pamiętać, jak potrójny działa.

476
00:36:37,150 --> 00:36:38,610
Istnieją na pewno zostały quizy w przeszłości

477
00:36:38,610 --> 00:36:41,170
że ci funkcji z operatora trójskładnikowych

478
00:36:41,170 --> 00:36:45,750
i powiedzieć, przetłumaczyć, zrobić coś, co nie używa trójskładnikowych.

479
00:36:45,750 --> 00:36:49,140
Więc to jest bardzo częstym przypadkiem, kiedy Myślę korzystać trójskładnikowych

480
00:36:49,140 --> 00:36:54,610
gdzie jeśli jakiś warunek ustawić zmienną do czegoś,

481
00:36:54,610 --> 00:36:58,580
jeszcze ustawić tą samą zmienną, do czegoś innego.

482
00:36:58,580 --> 00:37:03,390
To coś, co bardzo często może być przekształcony w tego rodzaju rzeczy

483
00:37:03,390 --> 00:37:14,420
gdzie ustawić zmienną do tego - czy dobrze, czy to prawda? Wtedy to, jeszcze to.

484
00:37:14,420 --> 00:37:18,550
[Student] Pierwszy to czy prawda, prawda?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Tak. Sposób zawsze czytać to, temp. wynosi wartość większą niż wartość temp,

486
00:37:25,570 --> 00:37:30,680
wtedy to jeszcze to. To zadaje pytanie.

487
00:37:30,680 --> 00:37:35,200
Czy jest większy? Następnie wykonaj pierwszą rzeczą. Jeszcze zrobić drugą rzeczą.

488
00:37:35,200 --> 00:37:41,670
I prawie zawsze - dwukropek, po prostu - w mojej głowie, czytałem jak jeszcze.

489
00:37:41,670 --> 00:37:47,180
>> Czy ktoś ma rekurencyjne rozwiązanie?

490
00:37:47,180 --> 00:37:49,670
Okay. Ten będziemy - może być już wielki,

491
00:37:49,670 --> 00:37:53,990
ale mamy zamiar zrobić to jeszcze lepiej.

492
00:37:53,990 --> 00:37:58,720
To jest prawie tak samo dokładny pomysł.

493
00:37:58,720 --> 00:38:03,060
To jest po prostu, no, chcesz wyjaśnić?

494
00:38:03,060 --> 00:38:08,340
[Student] Jasne. Jesteśmy więc upewnić się, że drzewo nie jest null pierwsze,

495
00:38:08,340 --> 00:38:13,380
bo jeśli drzewo jest null, a następnie to się zwróci false, ponieważ nie znalazłem.

496
00:38:13,380 --> 00:38:19,200
A jeśli jest jeszcze drzewo, wchodzimy - musimy najpierw sprawdzić, czy wartość bieżącego węzła.

497
00:38:19,200 --> 00:38:23,740
Zwraca true, jeśli jest, a jeśli nie mamy recurse na lewo lub prawo.

498
00:38:23,740 --> 00:38:25,970
Czy nie brzmi to właściwe? >> Mm-hmm. (Umowa)

499
00:38:25,970 --> 00:38:33,880
Tak więc zauważyć, że jest to praktycznie - strukturalnie bardzo podobne do rozwiązania iteracyjnego.

500
00:38:33,880 --> 00:38:38,200
Tyle, że zamiast rekurencji, mieliśmy pętli while.

501
00:38:38,200 --> 00:38:40,840
I bazowym tutaj gdzie drzewa nie równa wartości null

502
00:38:40,840 --> 00:38:44,850
był stan, w którym rozstaliśmy się z pętli while.

503
00:38:44,850 --> 00:38:50,200
Są bardzo podobne. Ale idziemy do pójścia krok dalej.

504
00:38:50,200 --> 00:38:54,190
Teraz możemy zrobić to samo tutaj.

505
00:38:54,190 --> 00:38:57,680
Wskazówka Wracamy samo w obu tych liniach,

506
00:38:57,680 --> 00:39:00,220
wyjątkiem jeden argument jest inny.

507
00:39:00,220 --> 00:39:07,950
Więc mamy zamiar sprawić, że w trójskładnikowych.

508
00:39:07,950 --> 00:39:13,790
I coś uderzyć opcji, i to symbol. Okay.

509
00:39:13,790 --> 00:39:21,720
Więc mamy zamiar wrócić zawiera tego.

510
00:39:21,720 --> 00:39:28,030
To zaczyna być wiele linii, dobrze, powiększony jest.

511
00:39:28,030 --> 00:39:31,060
Zazwyczaj, pod względem stylistycznym rzeczy, nie sądzę, wielu ludzi

512
00:39:31,060 --> 00:39:38,640
postawić spację po strzałki, ale myślę, że jeśli jesteś konsekwentny, to dobrze.

513
00:39:38,640 --> 00:39:44,320
Jeżeli wartość jest mniejsza od wartości drzewa, chcemy recurse na lewej drzewa,

514
00:39:44,320 --> 00:39:53,890
else chcemy rekursja po prawej drzewa.

515
00:39:53,890 --> 00:39:58,610
Tak, że był jednym z krokiem co to wygląda mniejsze.

516
00:39:58,610 --> 00:40:02,660
Kroku drugiego co to wygląda mniejsze -

517
00:40:02,660 --> 00:40:09,150
możemy oddzielić to na wielu liniach.

518
00:40:09,150 --> 00:40:16,500
Okay. Krok drugi z co wyglądają mniejsze jest tutaj,

519
00:40:16,500 --> 00:40:25,860
więc wartość zwracana równa wartości drzewa, lub zawiera cokolwiek.

520
00:40:25,860 --> 00:40:28,340
>> To jest ważne.

521
00:40:28,340 --> 00:40:30,860
Nie jestem pewien, czy powiedział to wyraźnie w swojej klasie,

522
00:40:30,860 --> 00:40:34,740
ale to się nazywa zwarcie oceny.

523
00:40:34,740 --> 00:40:41,060
Chodzi o to, wartość == wartość drzewa.

524
00:40:41,060 --> 00:40:49,960
Jeśli to prawda, to jest prawda, a my chcemy "albo" że z tym, co jest tutaj.

525
00:40:49,960 --> 00:40:52,520
Więc nawet nie myśląc o to, co jest tutaj,

526
00:40:52,520 --> 00:40:55,070
co jest całe wyrażenie zamiar wrócić?

527
00:40:55,070 --> 00:40:59,430
[Student] True? >> Tak, bo prawda o niczym,

528
00:40:59,430 --> 00:41:04,990
or'd - czy prawdziwe or'd z niczego jest to prawda.

529
00:41:04,990 --> 00:41:08,150
Tak szybko, jak widzimy wartości zwracanej = wartość drzewa,

530
00:41:08,150 --> 00:41:10,140
jesteśmy po prostu wrócą prawdziwe.

531
00:41:10,140 --> 00:41:15,710
Nawet nie będzie rekursja zawiera ponadto wzdłuż linii.

532
00:41:15,710 --> 00:41:20,980
Możemy podjąć ten jeden krok dalej.

533
00:41:20,980 --> 00:41:29,490
Drzewo powrót nie równy null, a wszystko to robi.

534
00:41:29,490 --> 00:41:32,650
To sprawiło, że jedna linia funkcji.

535
00:41:32,650 --> 00:41:36,790
Jest to również przykład oceny zwarcia.

536
00:41:36,790 --> 00:41:40,680
Ale teraz jest sam pomysł -

537
00:41:40,680 --> 00:41:47,320
zamiast - więc jeśli drzewo nie jest równa null - ani dobrze,

538
00:41:47,320 --> 00:41:49,580
jeśli drzewo jest równa null, który jest zły przypadek,

539
00:41:49,580 --> 00:41:54,790
jeśli drzewo jest równy null, a następnie pierwszy warunek będzie fałszywy.

540
00:41:54,790 --> 00:42:00,550
Tak fałszywe anded z czymkolwiek będzie, co?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Tak. To jest druga połowa oceny zwarcia,

542
00:42:04,640 --> 00:42:10,710
gdzie jeśli drzewo nie jest równa null, wówczas nie będziemy nawet iść -

543
00:42:10,710 --> 00:42:14,930
lub jeśli drzewo nie równe NULL, to nie będziemy robić wartość == wartość drzewa.

544
00:42:14,930 --> 00:42:17,010
Jesteśmy po prostu się do natychmiastowego zwrotu false.

545
00:42:17,010 --> 00:42:20,970
Co jest ważne, ponieważ jeśli nie zrobił zwarcie oceny,

546
00:42:20,970 --> 00:42:25,860
następnie, jeśli drzewo jest równa null, to drugi warunek będzie winy seg,

547
00:42:25,860 --> 00:42:32,510
bo drzewo-> wartość dereferencji null.

548
00:42:32,510 --> 00:42:40,490
Więc to jest to. Może to - zmieniać raz na.

549
00:42:40,490 --> 00:42:44,840
To jest bardzo często rzeczą także, nie czyniąc tę ​​jedną linię z tego,

550
00:42:44,840 --> 00:42:49,000
ale to jest coś wspólnego w warunkach, może nie tu,

551
00:42:49,000 --> 00:42:59,380
ale jeśli (drzewo! = NULL, a tree-> wartość value ==), zrobić cokolwiek.

552
00:42:59,380 --> 00:43:01,560
Jest to bardzo częste schorzenie, gdzie zamiast

553
00:43:01,560 --> 00:43:06,770
podzielenie na dwie ifs, gdzie chce, jest zerowy drzewo?

554
00:43:06,770 --> 00:43:11,780
Ok, to nie jest null, to teraz jest to wartość równa wartości drzewo? To zrobić.

555
00:43:11,780 --> 00:43:17,300
Zamiast tego, ten stan, to nigdy nie seg winy

556
00:43:17,300 --> 00:43:21,220
ponieważ będzie to przebić, czy to dzieje się null.

557
00:43:21,220 --> 00:43:24,000
Cóż, myślę, że jeśli drzewo jest całkowicie nieprawidłowy wskaźnik, to może jeszcze seg winy,

558
00:43:24,000 --> 00:43:26,620
ale nie może seg błędu, jeśli drzewo jest null.

559
00:43:26,620 --> 00:43:32,900
Gdyby to był zerowy, to wybuchnie przed kiedykolwiek dereferencjonowane wskaźnik w pierwszej kolejności.

560
00:43:32,900 --> 00:43:35,000
[Student] Czy to tzw leniwy ocena?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy ocena jest osobna sprawa.

562
00:43:40,770 --> 00:43:49,880
Lazy ocena jest bardziej jak poprosić o wartości,

563
00:43:49,880 --> 00:43:54,270
poprosić, aby obliczyć wartość, rodzaj, ale nie trzeba go natychmiast.

564
00:43:54,270 --> 00:43:59,040
Więc dopóki rzeczywiście trzeba, to nie jest oceniany.

565
00:43:59,040 --> 00:44:03,920
To nie jest dokładnie to samo, ale w Huffman PSET,

566
00:44:03,920 --> 00:44:06,520
mówi, że my "leniwie" pisać.

567
00:44:06,520 --> 00:44:08,670
Powodem robimy to dlatego, że jesteśmy faktycznie buforowanie zapisu -

568
00:44:08,670 --> 00:44:11,820
Nie chcemy pisać poszczególnych bitów na raz,

569
00:44:11,820 --> 00:44:15,450
lub pojedynczych bajtów na raz, zamiast tego chce się kawałek bajtów.

570
00:44:15,450 --> 00:44:19,270
Następnie raz mamy kawałek bajtów, wtedy piszemy go.

571
00:44:19,270 --> 00:44:22,640
Nawet jeśli zapytać go napisać - i fwrite i fread zrobić tego samego rodzaju rzeczy.

572
00:44:22,640 --> 00:44:26,260
Oni buforować Twój czyta i pisze.

573
00:44:26,260 --> 00:44:31,610
Nawet jeśli prosi ją napisać od razu, to prawdopodobnie nie będzie.

574
00:44:31,610 --> 00:44:34,540
I nie możesz być pewien, że wszystko będzie napisane

575
00:44:34,540 --> 00:44:37,540
czasu wywołania hfclose czy cokolwiek to jest,

576
00:44:37,540 --> 00:44:39,620
która następnie mówi, dobrze, jestem zamykania mój plik,

577
00:44:39,620 --> 00:44:43,450
to oznacza, że ​​lepiej napisać wszystko, że nie pisałem jeszcze.

578
00:44:43,450 --> 00:44:45,770
To nie ma potrzeby pisania wszystkiego

579
00:44:45,770 --> 00:44:49,010
aż zamykamy plik, a następnie musi.

580
00:44:49,010 --> 00:44:56,220
Tak, że tylko to, co leniwy - to czeka, aż ma się wydarzyć.

581
00:44:56,220 --> 00:44:59,990
To - podejmuje 51, a dojdziesz do niego w sposób bardziej szczegółowy,

582
00:44:59,990 --> 00:45:05,470
bo OCaml i wszystko w 51, wszystko jest rekurencja.

583
00:45:05,470 --> 00:45:08,890
Nie ma iteracyjnego rozwiązania, w zasadzie.

584
00:45:08,890 --> 00:45:11,550
Wszystko jest rekurencja i leniwa ewaluacja

585
00:45:11,550 --> 00:45:14,790
będzie ważne dla wielu okolicznościach

586
00:45:14,790 --> 00:45:19,920
gdzie, jeśli nie leniwie ocenia, że ​​myśli -

587
00:45:19,920 --> 00:45:24,760
Przykład strumienie, które są nieskończenie długo.

588
00:45:24,760 --> 00:45:30,990
W teorii można myśleć liczb naturalnych jako strumień 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Tak leniwie ocenianych rzeczy są w porządku.

590
00:45:33,090 --> 00:45:37,210
Jeśli powiem, że chcę dziesiątą cyfrę, wtedy mogę ocenić do dziesiątego numeru.

591
00:45:37,210 --> 00:45:40,300
Jeśli chcę setnej numer, to mogę ocenić do setnej liczby.

592
00:45:40,300 --> 00:45:46,290
Bez leniwej ewaluacji, to jest to postaram się ocenić wszystkie numery natychmiast.

593
00:45:46,290 --> 00:45:50,000
Jesteś oceny nieskończenie wiele liczb, i to nie tylko możliwe.

594
00:45:50,000 --> 00:45:52,080
Tak więc istnieje wiele sytuacji, w której ocena leniwy

595
00:45:52,080 --> 00:45:57,840
jest po prostu konieczne do uzyskania rzeczy do pracy.

596
00:45:57,840 --> 00:46:05,260
>> Teraz chcemy napisać wkładkę gdzie wkładka będzie

597
00:46:05,260 --> 00:46:08,430
Podobnie zmieniają się w jego definicji.

598
00:46:08,430 --> 00:46:10,470
Więc teraz to bool insert (int value).

599
00:46:10,470 --> 00:46:23,850
Mamy zamiar zmienić na bool wkładką (wartość int, node * drzewo).

600
00:46:23,850 --> 00:46:29,120
Jesteśmy rzeczywiście się zmieni, że ponownie w nieco, zobaczymy dlaczego.

601
00:46:29,120 --> 00:46:32,210
I przejdźmy build_node, tylko dla heck tego,

602
00:46:32,210 --> 00:46:36,730
powyżej wstawić więc nie mamy napisać prototyp funkcji.

603
00:46:36,730 --> 00:46:42,450
Która jest znak, że masz zamiar używać build_node w płytki.

604
00:46:42,450 --> 00:46:49,590
Okay. Poświęć chwilę na to.

605
00:46:49,590 --> 00:46:52,130
Myślę, że uratował rewizję, jeśli chcesz wyciągnąć z tego,

606
00:46:52,130 --> 00:47:00,240
lub, przynajmniej, ja teraz.

607
00:47:00,240 --> 00:47:04,190
Chciałem nieznaczne przerwy myśleć o logice wkładką,

608
00:47:04,190 --> 00:47:08,750
jeśli nie można myśleć.

609
00:47:08,750 --> 00:47:12,860
Zasadniczo będzie tylko kiedykolwiek wkładając w liściach.

610
00:47:12,860 --> 00:47:18,640
Podoba Ci się, jeśli mogę wstawić 1, to się nieuchronnie będzie wstawienie 1 -

611
00:47:18,640 --> 00:47:21,820
Zmienię na czarno - ll być wstawienie 1 tutaj.

612
00:47:21,820 --> 00:47:28,070
Albo jeśli wstawić 4, chcę być wstawienie 4 tutaj.

613
00:47:28,070 --> 00:47:32,180
Więc nie ma znaczenia, co robisz, masz zamiar być wstawienie na liściu.

614
00:47:32,180 --> 00:47:36,130
Wszystko co musisz zrobić, to iteracyjne w dół drzewa, aż dojdziesz do węzła

615
00:47:36,130 --> 00:47:40,890
To powinno być węzła rodzica, nowy węzła rodzica,

616
00:47:40,890 --> 00:47:44,560
a następnie zmienić jego lewego lub prawego kursora, w zależności od tego, czy

617
00:47:44,560 --> 00:47:47,060
jest większa lub mniejsza od bieżącego węzła.

618
00:47:47,060 --> 00:47:51,180
Zmienić ten wskaźnik do punktu do nowego węzła.

619
00:47:51,180 --> 00:48:05,490
Więc iteracyjne dół drzewa sprawiają, że punkt skrzydła do nowego węzła.

620
00:48:05,490 --> 00:48:09,810
Także myślę, że o tym, dlaczego zabrania typu sytuacji przed,

621
00:48:09,810 --> 00:48:17,990
gdzie zbudował drzewo binarne, gdzie to było prawidłowe

622
00:48:17,990 --> 00:48:19,920
jeśli tylko spojrzał na jednym węźle,

623
00:48:19,920 --> 00:48:24,830
ale 9 było z lewej 7 jeśli powtórzyć w dół do oporu.

624
00:48:24,830 --> 00:48:29,770
Tak, że to niemożliwe w tym scenariuszu, ponieważ -

625
00:48:29,770 --> 00:48:32,530
myślę o włożeniu 9 lub coś; w węźle pierwszy,

626
00:48:32,530 --> 00:48:35,350
Idę zobaczyć 7 i mam zamiar iść na prawo.

627
00:48:35,350 --> 00:48:38,490
Więc nie ma znaczenia, co zrobić, jeśli mam wstawienie przechodząc do liścia,

628
00:48:38,490 --> 00:48:40,790
liścia i za pomocą odpowiedniego algorytmu

629
00:48:40,790 --> 00:48:43,130
to będzie dla mnie niemożliwe włóż 9 z lewej 7

630
00:48:43,130 --> 00:48:48,250
bo jak tylko uderzyć 7 mam zamiar iść na prawo.

631
00:48:59,740 --> 00:49:02,070
Czy ktoś ma coś na początek?

632
00:49:02,070 --> 00:49:05,480
[Student] ja. >> Jasne.

633
00:49:05,480 --> 00:49:09,200
[Student, niezrozumiały]

634
00:49:09,200 --> 00:49:14,390
[Inny student, niezrozumiały]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Jest doceniana. Okay. Chcesz wyjaśnić?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Ponieważ wiemy, że były wstawianie

637
00:49:20,690 --> 00:49:24,060
nowych węzłów na koniec, drzewa

638
00:49:24,060 --> 00:49:28,070
I przelotowe drzewie iteracyjnie

639
00:49:28,070 --> 00:49:31,360
dopóki nie wróciłem do węzła, który wskazał na null.

640
00:49:31,360 --> 00:49:34,220
A następnie postanowiłem umieścić albo na prawej lub lewej

641
00:49:34,220 --> 00:49:37,420
zastosowaniem właściwej zmiennej, to powiedział mi, gdzie go umieścić.

642
00:49:37,420 --> 00:49:41,850
A potem, w istocie, Zrobiłem że ostatni -

643
00:49:41,850 --> 00:49:47,520
które wskazują temperatury węzła do nowego węzła tworzącego go,

644
00:49:47,520 --> 00:49:50,770
albo z lewej strony lub z prawej strony, w zależności od tego, co było w prawo wartość.

645
00:49:50,770 --> 00:49:56,530
Wreszcie mogę ustawić nową wartość węzła do wartości jego testowania.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okay, więc widzę jeden problem tutaj.

647
00:49:59,550 --> 00:50:02,050
Jest to 95%, jak na drodze.

648
00:50:02,050 --> 00:50:07,550
Jeden problem, że widzę, dobrze, czy ktoś jeszcze zobaczyć jakiś problem?

649
00:50:07,550 --> 00:50:18,400
Co to jest okoliczność, w ramach którego wyrwać się z pętli?

650
00:50:18,400 --> 00:50:22,100
[Student] Jeśli temperatura jest null? >> Tak. Więc jak wyrwać się z pętli, jeśli temperatura jest null.

651
00:50:22,100 --> 00:50:30,220
Ale co mam zrobić tutaj?

652
00:50:30,220 --> 00:50:35,410
I temp dereference, który jest nieunikniony null.

653
00:50:35,410 --> 00:50:39,840
Tak więc inne rzeczy trzeba zrobić, to nie tylko śledzić aż temp jest null,

654
00:50:39,840 --> 00:50:45,590
chcesz śledzić dominującej w każdej chwili.

655
00:50:45,590 --> 00:50:52,190
Chcemy również rodzica * węzła, myślę, że możemy zachować na NULL na początku.

656
00:50:52,190 --> 00:50:55,480
To będzie mieć dziwne zachowanie dla korzenia drzewa,

657
00:50:55,480 --> 00:50:59,210
ale dojdziemy do tego.

658
00:50:59,210 --> 00:51:03,950
Jeśli wartość jest większa niż cokolwiek, to temp = temp prawo.

659
00:51:03,950 --> 00:51:07,910
Ale zanim to zrobimy, rodzic temp =.

660
00:51:07,910 --> 00:51:14,500
A rodzice zawsze będzie równy temp? Czy to przypadek?

661
00:51:14,500 --> 00:51:19,560
Jeśli temperatura nie jest pusta, to mam zamiar przejść w dół, nie wiem co,

662
00:51:19,560 --> 00:51:24,030
do węzła, dla którego temperatura jest rodzicem.

663
00:51:24,030 --> 00:51:27,500
Więc rodzic będzie temp, a następnie przenieść temp dół.

664
00:51:27,500 --> 00:51:32,410
Teraz temperatura jest null, ale zwraca rodzica do rodzica z rzeczy, która jest null.

665
00:51:32,410 --> 00:51:39,110
Więc tu, nie chcę, aby ustawić prawa równa 1.

666
00:51:39,110 --> 00:51:41,300
Więc przeniosłem się w prawo, więc jeśli prawo = 1,

667
00:51:41,300 --> 00:51:45,130
i myślę, że również chcesz zrobić -

668
00:51:45,130 --> 00:51:48,530
Jeśli przeniesiesz się w lewo, chcesz ustawić prawa równe 0.

669
00:51:48,530 --> 00:51:55,950
Albo jeśli kiedykolwiek przesunąć w prawo.

670
00:51:55,950 --> 00:51:58,590
Więc prawo = 0. Jeśli prawo = 1,

671
00:51:58,590 --> 00:52:04,260
Teraz chcemy, aby nadrzędny prawą newnode wskaźnika,

672
00:52:04,260 --> 00:52:08,520
else chcemy macierzysty lewy newnode wskaźnika.

673
00:52:08,520 --> 00:52:16,850
Pytania na temat tego?

674
00:52:16,850 --> 00:52:24,880
Okay. Więc to jest sposób - dobrze, właściwie, zamiast robić to,

675
00:52:24,880 --> 00:52:29,630
my pół spodziewać korzystanie build_node.

676
00:52:29,630 --> 00:52:40,450
A jeśli newnode równa null, zwraca fałsz.

677
00:52:40,450 --> 00:52:44,170
To jest to. Teraz, to jest to, czego spodziewaliśmy Ci zrobić.

678
00:52:44,170 --> 00:52:47,690
>> To właśnie pracownicy rozwiązują zrobić.

679
00:52:47,690 --> 00:52:52,360
Nie zgadzam się z tym, jak "prawo" sposób będzie o nim

680
00:52:52,360 --> 00:52:57,820
ale to jest w porządku i będzie działać.

681
00:52:57,820 --> 00:53:02,840
Jedna rzecz, że to trochę dziwne, teraz jest

682
00:53:02,840 --> 00:53:08,310
jeśli drzewo zaczyna się za nieważną, przekazujemy w pustym drzewie.

683
00:53:08,310 --> 00:53:12,650
Myślę, że to zależy od tego, w jaki sposób zdefiniować zachowanie przechodzącą w pustym drzewie.

684
00:53:12,650 --> 00:53:15,490
Myślę, że jeśli przejdą w pustym drzewie,

685
00:53:15,490 --> 00:53:17,520
następnie wpisując wartość w pustym drzewie

686
00:53:17,520 --> 00:53:23,030
Należy po prostu wrócić na drzewo, gdzie jedyną wartością jest to, że jeden węzeł.

687
00:53:23,030 --> 00:53:25,830
Czy ludzie się z tym zgodzić? Można, jeśli chcesz,

688
00:53:25,830 --> 00:53:28,050
jeśli przejdą w pustym drzewie

689
00:53:28,050 --> 00:53:31,320
i chcesz wstawić wartość do niego, return false.

690
00:53:31,320 --> 00:53:33,830
To do ciebie, aby określić, że.

691
00:53:33,830 --> 00:53:38,320
Aby to zrobić, pierwszą rzeczą, powiedziałem, a następnie -

692
00:53:38,320 --> 00:53:40,720
dobrze, będziesz mieć problemy robi, że ze względu

693
00:53:40,720 --> 00:53:44,090
byłoby łatwiej, gdybyśmy mieli globalny wskaźnik do rzeczy,

694
00:53:44,090 --> 00:53:48,570
ale nie, więc jeśli drzewo jest pusty, nic nie możemy zrobić.

695
00:53:48,570 --> 00:53:50,960
Możemy po prostu return false.

696
00:53:50,960 --> 00:53:52,840
Więc mam zamiar zmienić wkładkę.

697
00:53:52,840 --> 00:53:56,540
Jesteśmy technicznie może po prostu zmienić to właśnie tutaj,

698
00:53:56,540 --> 00:53:58,400
jak to jest iteracja rzeczy,

699
00:53:58,400 --> 00:54:04,530
ale mam zamiar zmienić wkładkę do podjęcia węzeł drzewa **.

700
00:54:04,530 --> 00:54:07,510
Podwójne wskaźniki.

701
00:54:07,510 --> 00:54:09,710
Co to znaczy?

702
00:54:09,710 --> 00:54:12,330
Zamiast zajmować się wskaźniki do węzłów

703
00:54:12,330 --> 00:54:16,690
co mam zamiar manipulować to jest wskaźnik.

704
00:54:16,690 --> 00:54:18,790
Mam zamiar manipulować ten wskaźnik.

705
00:54:18,790 --> 00:54:21,770
Idę do manipulowania wskaźniki bezpośrednio.

706
00:54:21,770 --> 00:54:25,760
Ma to sens, ponieważ myślę o dół -

707
00:54:25,760 --> 00:54:33,340
no, teraz to wskazuje na null.

708
00:54:33,340 --> 00:54:38,130
Co chcę zrobić jest manipulować ten wskaźnik, aby wskazywał nie null.

709
00:54:38,130 --> 00:54:40,970
Chcę zwrócić do mojego nowego węzła.

710
00:54:40,970 --> 00:54:44,870
Jeżeli po prostu śledzić wskaźniki do moich wskazówek,

711
00:54:44,870 --> 00:54:47,840
wtedy nie trzeba śledzić wskaźnik dominującej.

712
00:54:47,840 --> 00:54:52,640
Mogę tylko śledzić, czy wskaźnik wskazuje na null,

713
00:54:52,640 --> 00:54:54,580
i jeśli wskaźnik wskazuje na null,

714
00:54:54,580 --> 00:54:57,370
zmienić, aby wskazać węzeł chcę.

715
00:54:57,370 --> 00:55:00,070
I mogę to zmienić, ponieważ mam wskaźnik do wskaźnika.

716
00:55:00,070 --> 00:55:02,040
Zobaczmy tego teraz.

717
00:55:02,040 --> 00:55:05,470
Rzeczywiście można to zrobić rekurencyjnie dość łatwo.

718
00:55:05,470 --> 00:55:08,080
Czy chcemy, aby to zrobić?

719
00:55:08,080 --> 00:55:10,980
Tak, wiemy.

720
00:55:10,980 --> 00:55:16,790
>> Zobaczmy to rekurencyjnie.

721
00:55:16,790 --> 00:55:24,070
Po pierwsze, co jest naszym bazowym będzie?

722
00:55:24,070 --> 00:55:29,140
Prawie zawsze naszym bazowym, ale faktycznie, jest to rodzaj trudne.

723
00:55:29,140 --> 00:55:34,370
First things first, if (drzewo == NULL)

724
00:55:34,370 --> 00:55:37,550
Myślę, że jesteśmy po prostu będzie return false.

725
00:55:37,550 --> 00:55:40,460
To różni się od drzewa puste.

726
00:55:40,460 --> 00:55:44,510
Jest to wskaźnik wskaźnikiem głównym rygorem

727
00:55:44,510 --> 00:55:48,360
co oznacza, że ​​wskaźnik root nie istnieje.

728
00:55:48,360 --> 00:55:52,390
Tak więc i tutaj, jeśli mam zrobić

729
00:55:52,390 --> 00:55:55,760
* node - niech tylko ponownie to.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
i mam zamiar zadzwonić wkładkę wykonując coś jak,

732
00:56:00,730 --> 00:56:04,540
wstaw 4 w & korzenia.

733
00:56:04,540 --> 00:56:06,560
Więc i root, jeśli korzeń jest * node

734
00:56:06,560 --> 00:56:11,170
wtedy i korzeń będzie ** węzła.

735
00:56:11,170 --> 00:56:15,120
To jest ważne. W tym przypadku, drzewo, tutaj,

736
00:56:15,120 --> 00:56:20,120
drzewo nie jest null - lub wkładka.

737
00:56:20,120 --> 00:56:24,630
Tutaj. Drzewo nie jest null; drzewo * jest null, co jest w porządku

738
00:56:24,630 --> 00:56:26,680
bo jeśli drzewo * jest null, a następnie można manipulować

739
00:56:26,680 --> 00:56:29,210
do teraz wskazać co chcę wskazać.

740
00:56:29,210 --> 00:56:34,750
Ale jeśli drzewo jest null, co oznacza, że ​​po prostu przyszedł tutaj i powiedział null.

741
00:56:34,750 --> 00:56:42,710
To nie ma sensu. Nie mogę nic zrobić z tym.

742
00:56:42,710 --> 00:56:45,540
Jeśli drzewo jest null, zwraca fałsz.

743
00:56:45,540 --> 00:56:48,220
Więc w zasadzie już powiedział, co nasza prawdziwa bazowym jest.

744
00:56:48,220 --> 00:56:50,580
A co to będzie?

745
00:56:50,580 --> 00:56:55,030
[Student, niezrozumiały]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Tak. Więc jeśli (* drzewo == NULL).

747
00:57:00,000 --> 00:57:04,520
To odnosi się do przypadku tutaj

748
00:57:04,520 --> 00:57:09,640
gdzie jeśli mój czerwony wskaźnik jest wskaźnikiem Ja koncentruje się na,

749
00:57:09,640 --> 00:57:12,960
tak jakbym koncentrowały się na tym wskaźniku, teraz jestem koncentruje się na tym wskaźniku.

750
00:57:12,960 --> 00:57:15,150
Teraz jestem skoncentrowany na tym wskaźnikiem.

751
00:57:15,150 --> 00:57:18,160
Więc jeśli mój czerwony wskaźnik, który jest moim ** węzłów,

752
00:57:18,160 --> 00:57:22,880
jest zawsze - jeśli *, mój czerwony wskaźnik, jest zawsze pusty,

753
00:57:22,880 --> 00:57:28,470
to oznacza, że ​​jestem w przypadku gdy jestem koncentrując się na wskaźnik, który wskazuje -

754
00:57:28,470 --> 00:57:32,530
jest to wskaźnik, że należy do liści.

755
00:57:32,530 --> 00:57:41,090
Chcę zmienić ten wskaźnik do punktu do nowego węzła.

756
00:57:41,090 --> 00:57:45,230
Wracaj tutaj.

757
00:57:45,230 --> 00:57:56,490
Mój newnode będzie tylko węzeł * n = build_node (wartość)

758
00:57:56,490 --> 00:58:07,300
następnie n, jeśli n = NULL, zwraca fałsz.

759
00:58:07,300 --> 00:58:12,600
Else chcemy zmienić to, co jest obecnie wskaźnik wskazując

760
00:58:12,600 --> 00:58:17,830
do teraz zwrócić do naszego nowo wybudowanego węzła.

761
00:58:17,830 --> 00:58:20,280
Rzeczywiście możemy zrobić tutaj.

762
00:58:20,280 --> 00:58:30,660
Zamiast mówić n mówimy * drzewo = jeśli drzewa *.

763
00:58:30,660 --> 00:58:35,450
Wszyscy rozumieją, że? Że zajmując się wskaźniki do wskaźników,

764
00:58:35,450 --> 00:58:40,750
możemy zmienić zerowe wskaźniki wskazać na rzeczy, które chcemy im wskazać.

765
00:58:40,750 --> 00:58:42,820
To nasza sprawa bazy.

766
00:58:42,820 --> 00:58:45,740
>> Teraz nasz nawrotu, lub nasz rekursji,

767
00:58:45,740 --> 00:58:51,430
będzie bardzo podobny do wszystkich innych rekursji robiliśmy.

768
00:58:51,430 --> 00:58:55,830
Będziemy chcieli, aby wstawić wartość,

769
00:58:55,830 --> 00:58:59,040
i teraz mam zamiar używać trójskładnikowej ponownie, ale to, co jest nasz stan będzie?

770
00:58:59,040 --> 00:59:05,180
Co to jest to, czego szukamy, aby zdecydować, czy chcemy iść w lewo czy w prawo?

771
00:59:05,180 --> 00:59:07,760
Zróbmy to w oddzielnych etapach.

772
00:59:07,760 --> 00:59:18,850
Jeśli (wartość <) co?

773
00:59:18,850 --> 00:59:23,200
[Student] drzewie jego wartość?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Więc pamiętaj, że jestem obecnie -

775
00:59:27,490 --> 00:59:31,260
[Studenci, niezrozumiały]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Tak, tak, właśnie tutaj, powiedzmy, że ta zielona strzałka

777
00:59:34,140 --> 00:59:39,050
przykład, co obecnie jest drzewo, jest wskaźnik do wskaźnika.

778
00:59:39,050 --> 00:59:46,610
To znaczy, że jestem wskaźnik do wskaźnika do 3.

779
00:59:46,610 --> 00:59:48,800
Dereference dwukrotnie brzmi dobrze.

780
00:59:48,800 --> 00:59:51,010
Co ja - jak to zrobić?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference raz, a następnie do arrow ten sposób?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Tak (drzewo *) jest dereference raz -> wartość

783
00:59:58,420 --> 01:00:05,960
ma dać mi wartość węzła, że ​​jestem pośrednio wskazując.

784
01:00:05,960 --> 01:00:11,980
Więc mogę też napisać to ** tree.value jeśli wolisz.

785
01:00:11,980 --> 01:00:18,490
Albo działa.

786
01:00:18,490 --> 01:00:26,190
Jeśli tak jest, to chcę zadzwonić wstawić z wartością.

787
01:00:26,190 --> 01:00:32,590
A jakie jest moje aktualizowane node ** będzie?

788
01:00:32,590 --> 01:00:39,440
Chcę iść na lewo, więc tree.left ** będzie moja lewa.

789
01:00:39,440 --> 01:00:41,900
I chcę, wskaźnik do tej rzeczy

790
01:00:41,900 --> 01:00:44,930
tak, że jeśli w lewo kończy się pusty wskaźnik,

791
01:00:44,930 --> 01:00:48,360
Można zmodyfikować go zwrócić do mojego nowego węzła.

792
01:00:48,360 --> 01:00:51,460
>> I innym przypadku może być bardzo podobne.

793
01:00:51,460 --> 01:00:55,600
Miejmy faktycznie sprawiają, że mój trójskładnikowych teraz.

794
01:00:55,600 --> 01:01:04,480
Wstawianie wartości, jeśli wartość <(drzewo. **) Wartość.

795
01:01:04,480 --> 01:01:11,040
Następnie chcemy zaktualizować nasze ** w lewo,

796
01:01:11,040 --> 01:01:17,030
else chcemy zaktualizować nasze ** w prawo.

797
01:01:17,030 --> 01:01:22,540
[Student] Czy aby uzyskać wskaźnik do wskaźnika?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Pamiętaj, że - ** tree.right jest węzeł star.

799
01:01:30,940 --> 01:01:35,040
[Student, niezrozumiały] >> Tak.

800
01:01:35,040 --> 01:01:41,140
** Tree.right jest jak ten wskaźnik, czy coś.

801
01:01:41,140 --> 01:01:45,140
Więc biorąc wskaźnik do tego, że daje mi to, co chcę

802
01:01:45,140 --> 01:01:50,090
wskaźnika do tego faceta.

803
01:01:50,090 --> 01:01:54,260
[Student] Czy możemy wrócić jeszcze raz, dlaczego są za pomocą dwóch wskaźników?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Tak. Tak więc - nie można, i że przed rozwiązaniem

805
01:01:58,220 --> 01:02:04,540
był sposób z tym nie robiąc dwa wskaźniki.

806
01:02:04,540 --> 01:02:08,740
Musisz być w stanie zrozumieć, przy użyciu dwóch wskaźników,

807
01:02:08,740 --> 01:02:11,660
i jest to rozwiązanie do czyszczenia.

808
01:02:11,660 --> 01:02:16,090
Zauważ też, że to, co się stanie, gdy drzewo -

809
01:02:16,090 --> 01:02:24,480
co się stanie, jeśli mój korzeń null? Co się dzieje, jeśli mam zrobić w tej sprawie tutaj?

810
01:02:24,480 --> 01:02:30,540
Więc node * root = NULL, włóż 4 do & korzenia.

811
01:02:30,540 --> 01:02:35,110
Co to jest korzeń będzie po tym?

812
01:02:35,110 --> 01:02:37,470
[Student, niezrozumiały] >> Tak.

813
01:02:37,470 --> 01:02:41,710
Wartość korzeń będzie 4.

814
01:02:41,710 --> 01:02:45,510
Lewy korzeń będzie null, prawy korzeń będzie null.

815
01:02:45,510 --> 01:02:49,490
W przypadku, gdy nie graniowej według adresu,

816
01:02:49,490 --> 01:02:52,490
nie możemy modyfikować korzeń.

817
01:02:52,490 --> 01:02:56,020
W przypadku, gdy drzewa - gdzie korzeń null

818
01:02:56,020 --> 01:02:58,410
po prostu musieliśmy wrócić false. Nic nie mogliśmy zrobić.

819
01:02:58,410 --> 01:03:01,520
Nie możemy wstawić do pustego węzła drzewa.

820
01:03:01,520 --> 01:03:06,810
Ale teraz możemy, my po prostu zrobić pustą drzewa do drzewa jeden-węzła.

821
01:03:06,810 --> 01:03:13,400
Który jest zwykle oczekiwany sposób, to powinno działać.

822
01:03:13,400 --> 01:03:21,610
>> Ponadto, jest to znacznie krótszy niż

823
01:03:21,610 --> 01:03:26,240
również śledzenie rodzica i tak iteracyjne dół całą drogę.

824
01:03:26,240 --> 01:03:30,140
Teraz mam rodziców, a ja po prostu mam wskaźnik właściwej nadrzędnego do cokolwiek.

825
01:03:30,140 --> 01:03:35,640
Zamiast tego, jeśli zrobiliśmy to iteracyjnie, to będzie ten sam pomysł z pętlą while.

826
01:03:35,640 --> 01:03:38,100
Ale zamiast do czynienia z moim wskaźnikiem dominującej,

827
01:03:38,100 --> 01:03:40,600
zamiast mój obecny wskaźnik byłoby rzeczą

828
01:03:40,600 --> 01:03:43,790
że jestem bezpośrednią modyfikację zwrócić do mojego nowego węzła.

829
01:03:43,790 --> 01:03:46,090
Nie mam do czynienia z tym, czy to, wskazując na lewo.

830
01:03:46,090 --> 01:03:48,810
Nie mam do czynienia z tym, czy to, wskazując na prawo.

831
01:03:48,810 --> 01:04:00,860
To tylko, co to jest wskaźnik, mam zamiar ustawić go zwrócić do mojego nowego węzła.

832
01:04:00,860 --> 01:04:05,740
Wszyscy rozumieją, jak to działa?

833
01:04:05,740 --> 01:04:09,460
Jeśli nie, dlaczego chcemy to zrobić w ten sposób,

834
01:04:09,460 --> 01:04:14,920
ale przynajmniej, że to działa jak rozwiązanie?

835
01:04:14,920 --> 01:04:17,110
[Student] Gdzie wrócimy prawda?

836
01:04:17,110 --> 01:04:21,550
[Bowden] To chyba tu.

837
01:04:21,550 --> 01:04:26,690
Jeśli poprawnie włożyć, zwróci true.

838
01:04:26,690 --> 01:04:32,010
Indziej, tu będziemy chcieli zwrotu tego, co wraca wsadowych.

839
01:04:32,010 --> 01:04:35,950
>> A co jest szczególnego w tej funkcji rekurencyjnej?

840
01:04:35,950 --> 01:04:43,010
To jest ogon recursive, tak długo, jak skompilować z niektórych optymalizacji,

841
01:04:43,010 --> 01:04:48,060
będzie uznać, że i nigdy nie dostanie przepełnienie stosu z tego,

842
01:04:48,060 --> 01:04:53,230
nawet jeśli nasze drzewo ma wysokość 10.000 lub 10 mln euro.

843
01:04:53,230 --> 01:04:55,630
[Student, niezrozumiały]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Myślę, że robi to w Dash - lub co poziom optymalizacji

845
01:05:00,310 --> 01:05:03,820
jest wymagane dla rekursji ogonowej uznawane.

846
01:05:03,820 --> 01:05:09,350
Myślę, że uznaje - GCC i Clang

847
01:05:09,350 --> 01:05:12,610
mieć różne znaczenia dla ich poziomu optymalizacji.

848
01:05:12,610 --> 01:05:17,870
Chcę powiedzieć, że to Dasho 2, na pewno, że będzie rozpoznawać ogon rekursji.

849
01:05:17,870 --> 01:05:27,880
Ale - można skonstruować jak przykład Fibonocci czy coś.

850
01:05:27,880 --> 01:05:30,030
To nie jest łatwe do sprawdzenia się z tym, bo to jest trudne do skonstruowania

851
01:05:30,030 --> 01:05:32,600
drzewo binarne, które jest tak duże.

852
01:05:32,600 --> 01:05:37,140
Ale tak, myślę, że to Dasho 2, że

853
01:05:37,140 --> 01:05:40,580
jeśli skompilować Dasho 2, trafi ona do rekursji ogonowej

854
01:05:40,580 --> 01:05:54,030
i optymalizacji, które obecnie.

855
01:05:54,030 --> 01:05:58,190
Wróćmy do - włożyć dosłownie ostatnią rzeczą, potrzebuje.

856
01:05:58,190 --> 01:06:04,900
Wróćmy do wkładki tutaj

857
01:06:04,900 --> 01:06:07,840
gdzie mamy zamiar zrobić ten sam pomysł.

858
01:06:07,840 --> 01:06:14,340
Będzie nadal mają wadę, nie jest w stanie w pełni obsługiwać

859
01:06:14,340 --> 01:06:17,940
gdy korzeń sam jest null lub obok wejścia jest null,

860
01:06:17,940 --> 01:06:20,060
ale zamiast postępowania z wskaźnika macierzystego

861
01:06:20,060 --> 01:06:27,430
niech stosować tę samą logikę wskazówek prowadzących do wskaźników.

862
01:06:27,430 --> 01:06:35,580
Jeśli tu utrzymać nasz węzeł ** dyskusja,

863
01:06:35,580 --> 01:06:37,860
i nie musimy śledzić prawo już,

864
01:06:37,860 --> 01:06:47,190
ale node ** bież = & drzewo.

865
01:06:47,190 --> 01:06:54,800
A teraz nasza pętla będzie natomiast dyskusja * nie jest równa null.

866
01:06:54,800 --> 01:07:00,270
Nie trzeba śledzić rodziców już.

867
01:07:00,270 --> 01:07:04,180
Nie trzeba śledzić lewo i prawo.

868
01:07:04,180 --> 01:07:10,190
I nazwijmy go temp, ponieważ jesteśmy już przy użyciu temperatury.

869
01:07:10,190 --> 01:07:17,200
Okay. Więc jeśli (wartość> * temp)

870
01:07:17,200 --> 01:07:24,010
następnie & (* temp) -> prawy

871
01:07:24,010 --> 01:07:29,250
else temp = & (* temp) -> w lewo.

872
01:07:29,250 --> 01:07:32,730
Teraz, w tym momencie, po tej pętli,

873
01:07:32,730 --> 01:07:36,380
Robię tylko to, bo być może łatwiej jest myśleć o iteracyjnie niż rekurencyjnie,

874
01:07:36,380 --> 01:07:39,010
ale po tej pętli while,

875
01:07:39,010 --> 01:07:43,820
* Temp jest wskaźnik chcemy zmienić.

876
01:07:43,820 --> 01:07:48,960
>> Zanim mieliśmy rodziców, i chcieliśmy zmienić albo lewo dominującą bądź rodzica w prawo,

877
01:07:48,960 --> 01:07:51,310
ale jeśli chcemy zmienić prawo rodzica,

878
01:07:51,310 --> 01:07:54,550
następnie * temp jest prawo rodzica, i możemy ją zmienić bezpośrednio.

879
01:07:54,550 --> 01:08:05,860
Więc tu, możemy zrobić * temp = newnode, i to jest to.

880
01:08:05,860 --> 01:08:09,540
Więc wypowiedzenia, wszystko zrobiliśmy w to wykupienie linii kodu.

881
01:08:09,540 --> 01:08:14,770
Aby śledzić dominującej we wszystkim, co jest dodatkowym wysiłkiem.

882
01:08:14,770 --> 01:08:18,689
Tutaj, jeśli tylko śledzić wskaźnik do wskaźnika,

883
01:08:18,689 --> 01:08:22,990
i nawet gdybyśmy chcieli pozbyć się wszystkich tych nawiasach klamrowych teraz

884
01:08:22,990 --> 01:08:27,170
sprawiają, że wygląda krótszy.

885
01:08:27,170 --> 01:08:32,529
To teraz jest dokładnie to samo rozwiązanie,

886
01:08:32,529 --> 01:08:38,210
ale mniej linii kodu.

887
01:08:38,210 --> 01:08:41,229
Po uruchomieniu uznając to jako ważnego rozwiązania,

888
01:08:41,229 --> 01:08:43,529
jest to także łatwiejsze do rozumu o niż jak, dobrze,

889
01:08:43,529 --> 01:08:45,779
dlaczego mam tę flagę na int prawo?

890
01:08:45,779 --> 01:08:49,290
Co to znaczy? Och, to co oznacza, że

891
01:08:49,290 --> 01:08:51,370
za każdym razem, idź w prawo, trzeba ustawić go,

892
01:08:51,370 --> 01:08:53,819
else if I idź w lewo trzeba ustawić go na zero.

893
01:08:53,819 --> 01:09:04,060
Tutaj, nie mam powodu, aby o tym, to po prostu łatwiej myśleć.

894
01:09:04,060 --> 01:09:06,710
Pytania?

895
01:09:06,710 --> 01:09:16,290
[Student, niezrozumiały] >> Tak.

896
01:09:16,290 --> 01:09:23,359
Ok, więc w ostatnim bit -

897
01:09:23,359 --> 01:09:28,080
Chyba jeden szybki i łatwy funkcji możemy zrobić to,

898
01:09:28,080 --> 01:09:34,910
let's - razem, myślę, spróbuj pisać zawiera funkcję

899
01:09:34,910 --> 01:09:38,899
co nie obchodzi mnie, czy to jest drzewo binarne wyszukiwania.

900
01:09:38,899 --> 01:09:43,770
Zawiera funkcja powinna zwrócić wartość true

901
01:09:43,770 --> 01:09:58,330
jeśli gdziekolwiek w tym ogólnym drzewa binarnego jest wartość szukamy.

902
01:09:58,330 --> 01:10:02,520
Więc najpierw zrobić go rekurencyjnie i zrobimy to iteracyjnie.

903
01:10:02,520 --> 01:10:07,300
Rzeczywiście możemy tylko robić to razem, bo to będzie bardzo krótki.

904
01:10:07,300 --> 01:10:11,510
>> Co to jest moja sprawa baza będzie?

905
01:10:11,510 --> 01:10:13,890
[Student, niezrozumiały]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Więc jeśli (drzewo == NULL), to co?

907
01:10:18,230 --> 01:10:22,740
[Student] Return false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, dobrze, nie potrzebują innego.

909
01:10:26,160 --> 01:10:30,250
Jeśli był mój drugi wariant podstawowy.

910
01:10:30,250 --> 01:10:32,450
[Animacja] Drzewa wartość? >> Tak.

911
01:10:32,450 --> 01:10:36,430
Więc jeśli (tree-> wartość wartość. ==

912
01:10:36,430 --> 01:10:39,920
Wskazówka wracamy do węzła * nie, węzeł ** s?

913
01:10:39,920 --> 01:10:42,990
Zawiera nie będzie trzeba używać A ** węzłów,

914
01:10:42,990 --> 01:10:45,480
ponieważ nie modyfikujemy wskaźniki.

915
01:10:45,480 --> 01:10:50,540
My tylko przemierzając je.

916
01:10:50,540 --> 01:10:53,830
Jeśli tak się stanie, to chcemy, aby powrócić true.

917
01:10:53,830 --> 01:10:58,270
Else chcemy przechodzić dzieci.

918
01:10:58,270 --> 01:11:02,620
Więc nie możemy rozumować, czy wszystko z lewej jest mniejsza

919
01:11:02,620 --> 01:11:05,390
i wszystko, co po prawej stronie jest większa.

920
01:11:05,390 --> 01:11:09,590
Więc co jest nasz stan będzie tutaj - lub, co my teraz zrobimy?

921
01:11:09,590 --> 01:11:11,840
[Student, niezrozumiały] >> Tak.

922
01:11:11,840 --> 01:11:17,400
Powrót zawiera (wartość, drzewo-> lewy)

923
01:11:17,400 --> 01:11:26,860
lub zawiera (wartość, drzewo-> prawy). I to jest to.

924
01:11:26,860 --> 01:11:29,080
I zauważyć jest jakaś zwarcie oceny,

925
01:11:29,080 --> 01:11:32,520
gdzie, jeśli zdarzy nam się znaleźć wartość w lewym drzewie

926
01:11:32,520 --> 01:11:36,820
nigdy nie trzeba szukać w odpowiednim drzewie.

927
01:11:36,820 --> 01:11:40,430
To jest cała funkcja.

928
01:11:40,430 --> 01:11:43,690
Teraz zróbmy to iteracyjnie,

929
01:11:43,690 --> 01:11:48,060
który będzie mniej miły.

930
01:11:48,060 --> 01:11:54,750
Weźmiemy zwykły początek węzła * cur drzewa =.

931
01:11:54,750 --> 01:12:03,250
Chociaż (bież! = NULL).

932
01:12:03,250 --> 01:12:08,600
Szybko żeby zobaczyć problem.

933
01:12:08,600 --> 01:12:12,250
Jeśli cur - tu, jeśli kiedykolwiek wyrwać się z tego,

934
01:12:12,250 --> 01:12:16,020
następnie mamy zabrakło rzeczy do obejrzenia, więc return false.

935
01:12:16,020 --> 01:12:24,810
Jeśli (bież-> wartość value ==) zwraca true.

936
01:12:24,810 --> 01:12:32,910
Więc teraz, jesteśmy na miejscu -

937
01:12:32,910 --> 01:12:36,250
nie wiemy, czy chcemy, aby przejść w lewo lub w prawo.

938
01:12:36,250 --> 01:12:44,590
Tak arbitralnie, po prostu idź w lewo.

939
01:12:44,590 --> 01:12:47,910
Mam oczywiście uruchomić do problemu gdzie byłem całkowicie opuszczonego wszystko -

940
01:12:47,910 --> 01:12:50,760
Ja zawsze tylko sprawdzić lewą stronę drzewa.

941
01:12:50,760 --> 01:12:56,050
I nigdy nie będzie sprawdzać wszystko, co jest prawo dziecka do wszystkiego.

942
01:12:56,050 --> 01:13:00,910
Jak mogę to naprawić?

943
01:13:00,910 --> 01:13:05,260
[Student] Musisz śledzić na lewo i prawo w stosie.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Tak. Więc zróbmy to

945
01:13:13,710 --> 01:13:32,360
struct lista, node * n, a następnie węzeł ** dalej?

946
01:13:32,360 --> 01:13:40,240
Myślę, że działa dobrze.

947
01:13:40,240 --> 01:13:45,940
Chcemy iść na lewo, lub let's - tutaj.

948
01:13:45,940 --> 01:13:54,350
Struct lista = lista, będzie to początek

949
01:13:54,350 --> 01:13:58,170
się na tej liście struktury.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Tak, że będzie naszej listy

951
01:14:04,040 --> 01:14:08,430
z poddrzew że mamy pomijane.

952
01:14:08,430 --> 01:14:13,800
Będziemy przechodzić w lewo teraz,

953
01:14:13,800 --> 01:14:17,870
ale ponieważ nieuchronnie muszą wrócić do prawej,

954
01:14:17,870 --> 01:14:26,140
Będziemy trzymać prawej strony wewnątrz naszej liście struktury.

955
01:14:26,140 --> 01:14:32,620
Wtedy będziemy mieć new_list lub struct,

956
01:14:32,620 --> 01:14:41,080
struct lista * new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Zamierzam ignorować błędów sprawdzania, ale trzeba sprawdzić, czy jest to null.

958
01:14:44,920 --> 01:14:50,540
New_list węzeł to będzie wskazywać na -

959
01:14:50,540 --> 01:14:56,890
oh, dlatego chciałem się tutaj. To będzie wskazywać na drugiej liście struktury.

960
01:14:56,890 --> 01:15:02,380
To jest po prostu, jak związane pracę list.

961
01:15:02,380 --> 01:15:04,810
Jest takie samo jak związane listy int

962
01:15:04,810 --> 01:15:06,960
chyba my tylko z węzła wymiany int *.

963
01:15:06,960 --> 01:15:11,040
To jest dokładnie to samo.

964
01:15:11,040 --> 01:15:15,100
Więc new_list, wartość naszego węzła new_list,

965
01:15:15,100 --> 01:15:19,120
będzie bież-> prawo.

966
01:15:19,120 --> 01:15:24,280
Wartość naszej new_list-> next będzie nasz pierwszy list,

967
01:15:24,280 --> 01:15:30,760
a następnie będziemy aktualizować naszą listę, aby wskazać new_list.

968
01:15:30,760 --> 01:15:33,650
>> Teraz musimy jakiś sposób rzeczy ciągnie,

969
01:15:33,650 --> 01:15:37,020
jak mamy ruch cała lewica poddrzewa.

970
01:15:37,020 --> 01:15:40,480
Teraz trzeba wyciągnąć rzeczy z niego,

971
01:15:40,480 --> 01:15:43,850
jak dyskusja jest null, a my nie chcemy po prostu return false.

972
01:15:43,850 --> 01:15:50,370
Chcemy teraz wyciągnąć na zewnątrz w naszej nowej listy.

973
01:15:50,370 --> 01:15:53,690
Wygodny sposób to zrobić - no, rzeczywiście, jest wiele sposobów na zrobienie tego.

974
01:15:53,690 --> 01:15:56,680
Ktoś ma pomysł?

975
01:15:56,680 --> 01:15:58,790
Gdzie należy zrobić lub jak mam to zrobić?

976
01:15:58,790 --> 01:16:08,010
Mamy tylko kilka minut, ale wszelkie sugestie?

977
01:16:08,010 --> 01:16:14,750
Zamiast - w jeden sposób, a nie jest warunkiem naszego a,

978
01:16:14,750 --> 01:16:17,090
co mamy obecnie, patrząc na nie jest zerowa,

979
01:16:17,090 --> 01:16:22,340
zamiast będziemy nadal iść aż nasza lista sama w sobie jest null.

980
01:16:22,340 --> 01:16:25,680
Jeśli więc nasza lista kończy się null,

981
01:16:25,680 --> 01:16:30,680
wtedy mamy zabrakło rzeczy szukać, przeszukiwać.

982
01:16:30,680 --> 01:16:39,860
Ale to oznacza, że ​​pierwszą rzeczą, na naszej liście jest tylko będzie pierwszy węzeł.

983
01:16:39,860 --> 01:16:49,730
Pierwszą rzeczą będzie - już nie trzeba zobaczyć.

984
01:16:49,730 --> 01:16:58,710
Więc list-> n będzie naszym drzewem.

985
01:16:58,710 --> 01:17:02,860
list-> next będzie null.

986
01:17:02,860 --> 01:17:07,580
A teraz, gdy lista nie równa NULL robi.

987
01:17:07,580 --> 01:17:11,610
Cur będzie wyciągnąć coś z naszej listy.

988
01:17:11,610 --> 01:17:13,500
Tak więc dyskusja będzie równego lista-> n.

989
01:17:13,500 --> 01:17:20,850
I wtedy lista będzie równego list-> n, lub list-> next.

990
01:17:20,850 --> 01:17:23,480
Więc jeśli wartość bież równa wartość.

991
01:17:23,480 --> 01:17:28,790
Teraz możemy dodać zarówno nasze prawo i nasz wskaźnik lewy wskaźnik

992
01:17:28,790 --> 01:17:32,900
tak długo, jak nie są one nieważne.

993
01:17:32,900 --> 01:17:36,390
Tu, chyba powinniśmy byli zrobić, że w pierwszej kolejności.

994
01:17:36,390 --> 01:17:44,080
Jeśli (bież-> right! = NULL)

995
01:17:44,080 --> 01:17:56,380
wtedy będziemy wkładać tego węzła do naszej listy.

996
01:17:56,380 --> 01:17:59,290
Jeśli (bież-> left), jest to trochę dodatkowej pracy, ale to jest w porządku.

997
01:17:59,290 --> 01:18:02,690
Jeśli (bież-> left! = NULL),

998
01:18:02,690 --> 01:18:14,310
i mamy zamiar włożyć w lewo do naszej listy,

999
01:18:14,310 --> 01:18:19,700
i to powinno być to.

1000
01:18:19,700 --> 01:18:22,670
Mamy iteracyjne - tak długo, jak mamy coś w naszej liście,

1001
01:18:22,670 --> 01:18:26,640
mamy kolejny węzeł, aby przyjrzeć.

1002
01:18:26,640 --> 01:18:28,920
Więc patrzymy na tym węźle,

1003
01:18:28,920 --> 01:18:31,390
możemy przejść na naszą listę do następnego.

1004
01:18:31,390 --> 01:18:34,060
Jeśli ten węzeł to wartość, której szukamy, możemy powrócić true.

1005
01:18:34,060 --> 01:18:37,640
Else wstawić zarówno nasze lewego i prawego poddrzewa,

1006
01:18:37,640 --> 01:18:40,510
tak długo, jak nie jesteś null, na naszej liście

1007
01:18:40,510 --> 01:18:43,120
tak, że nieuchronnie nad nimi.

1008
01:18:43,120 --> 01:18:45,160
Tak więc, jeśli nie były one null,

1009
01:18:45,160 --> 01:18:47,950
jeśli nasz wskaźnik główny wskazał na dwie rzeczy,

1010
01:18:47,950 --> 01:18:51,670
następnie na pierwszy wjechaliśmy coś więc nasza lista kończy się null.

1011
01:18:51,670 --> 01:18:56,890
A następnie kładziemy dwie rzeczy z powrotem, więc teraz nasza lista jest wielkości 2.

1012
01:18:56,890 --> 01:19:00,030
Następnie jedziemy do pętli z powrotem, a my po prostu się do ciągnięcia,

1013
01:19:00,030 --> 01:19:04,250
powiedzmy, lewy wskaźnik naszego węzła głównego.

1014
01:19:04,250 --> 01:19:07,730
I to po prostu zachować dzieje; skończymy pętli na wszystko.

1015
01:19:07,730 --> 01:19:11,280
>> Należy zauważyć, że jest to znacznie trudniejsze

1016
01:19:11,280 --> 01:19:14,160
w rekurencyjnego rozwiązania.

1017
01:19:14,160 --> 01:19:17,260
I mówiłem wiele razy

1018
01:19:17,260 --> 01:19:25,120
że recursive rozwiązanie ma zazwyczaj wiele wspólnego z iteracyjnego rozwiązania.

1019
01:19:25,120 --> 01:19:30,820
Tutaj jest to dokładnie to, co recursive rozwiązanie robi.

1020
01:19:30,820 --> 01:19:36,740
Jedyną zmianą, że zamiast pośrednio użyciu stosu, stos programu,

1021
01:19:36,740 --> 01:19:40,840
jako sposób śledzenie co węzły nadal trzeba odwiedzić,

1022
01:19:40,840 --> 01:19:45,430
teraz trzeba jawnie użyć połączonej listy.

1023
01:19:45,430 --> 01:19:49,070
W obu przypadkach są śledzenie co węzeł musi być jeszcze odwiedził.

1024
01:19:49,070 --> 01:19:51,790
W cyklicznej przypadku jest to po prostu łatwiejsze, ponieważ stos

1025
01:19:51,790 --> 01:19:57,100
realizowane jest dla Ciebie, jak na stosie programu.

1026
01:19:57,100 --> 01:19:59,550
Należy zauważyć, że w tym związane z wykazu, stos.

1027
01:19:59,550 --> 01:20:01,580
Cokolwiek po prostu umieścić na stosie

1028
01:20:01,580 --> 01:20:09,960
jest natychmiast, co będziemy ściągać stos odwiedzić następny.

1029
01:20:09,960 --> 01:20:14,380
Jesteśmy poza czasem, ale jakieś pytania?

1030
01:20:14,380 --> 01:20:23,530
[Student, niezrozumiały]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Tak. Więc jeśli mamy listę,

1032
01:20:27,790 --> 01:20:30,150
Prąd będzie wskazywać na tego faceta,

1033
01:20:30,150 --> 01:20:34,690
a teraz jesteśmy po prostu pogłębianie połączonej listy skupić się na tego faceta.

1034
01:20:34,690 --> 01:20:44,200
Jesteśmy przemierzając ponad połączonej listy w tej linii.

1035
01:20:44,200 --> 01:20:51,200
I wtedy myślę, powinniśmy uwolnić naszej listy i rzeczy

1036
01:20:51,200 --> 01:20:53,880
raz przed powrotem prawdziwe lub fałszywe, musimy

1037
01:20:53,880 --> 01:20:57,360
iterować naszej listy i zawsze tu, jak sądzę,

1038
01:20:57,360 --> 01:21:03,900
jeśli bież prawo nie jest równe, dodaj go, więc teraz chcemy uwolnić

1039
01:21:03,900 --> 01:21:09,600
dyskusja, ponieważ dobrze, nie mieliśmy zupełnie zapomnieć o tej liście? Tak.

1040
01:21:09,600 --> 01:21:12,880
Więc to jest to, co chcemy zrobić.

1041
01:21:12,880 --> 01:21:16,730
Gdzie jest wskaźnik?

1042
01:21:16,730 --> 01:21:23,320
Cur wtedy - chcemy listy struct * 10 równa listę następny.

1043
01:21:23,320 --> 01:21:29,240
Darmowa lista list = temp.

1044
01:21:29,240 --> 01:21:32,820
A w przypadku, gdy wrócimy prawda, musimy iteracyjne

1045
01:21:32,820 --> 01:21:37,050
w pozostałej części naszej listy uwolnienie rzeczy.

1046
01:21:37,050 --> 01:21:39,700
Zaletą rozwiązania jest rekurencyjnej uwalniając rzeczy

1047
01:21:39,700 --> 01:21:44,930
oznacza tylko popping factorings ze stosu, który wydarzy się na Ciebie.

1048
01:21:44,930 --> 01:21:50,720
Tak zaszliśmy z czymś, co jest jak 3 liniach trudno myśleć-o kodzie

1049
01:21:50,720 --> 01:21:57,520
do czegoś, co jest znacznie wiele więcej trudno myśleć-o linii kodu.

1050
01:21:57,520 --> 01:22:00,620
Więcej pytań?

1051
01:22:00,620 --> 01:22:08,760
Dobrze. Jesteśmy dobrzy. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]