1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Rozdział 7] [mniej wygodne]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[To jest CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Witamy w sekcji 7.

5
00:00:09,080 --> 00:00:11,330
Dzięki huraganu Sandy,

6
00:00:11,330 --> 00:00:13,440
zamiast tego normalnie punkt tygodniu

7
00:00:13,440 --> 00:00:17,650
robimy to walk-through, przez sekcję pytań.

8
00:00:17,650 --> 00:00:22,830
Idę się podążać wraz z problemem Zestaw 6 specyfikacji,

9
00:00:22,830 --> 00:00:25,650
i przechodząc przez wszystkie pytania

10
00:00:25,650 --> 00:00:27,770
Sekcja części pytania.

11
00:00:27,770 --> 00:00:30,940
Jeśli są jakieś pytania,

12
00:00:30,940 --> 00:00:32,960
proszę umieszczać je na CS50 dyskutować.

13
00:00:32,960 --> 00:00:35,480
>> Dobrze. Zaczynajmy.

14
00:00:35,480 --> 00:00:40,780
Teraz patrzę na stronie 3 specyfikacji podanej problem.

15
00:00:40,780 --> 00:00:44,110
Idziemy najpierw zacząć mówić o drzew binarnych

16
00:00:44,110 --> 00:00:47,850
gdyż te mają wiele istotnych dla tego tygodnia zestaw problemów -

17
00:00:47,850 --> 00:00:49,950
kodowanie Drzewo Huffman.

18
00:00:49,950 --> 00:00:55,000
Jednym z pierwszych struktur danych rozmawialiśmy na CS50 była tablica.

19
00:00:55,000 --> 00:01:00,170
Pamiętaj, że tablica jest kolejność elementów -

20
00:01:00,170 --> 00:01:04,019
wszystkie tego samego rodzaju przechowywanych w prawo - obok siebie w pamięci.

21
00:01:04,019 --> 00:01:14,420
Jeśli mam tablicę liczb całkowitych, które można rysować za pomocą tego pola-numbers-liczby całkowite styl -

22
00:01:14,420 --> 00:01:20,290
Powiedzmy, że mam 5 w pierwszym polu, mam 7 w drugim,

23
00:01:20,290 --> 00:01:27,760
wtedy mam 8, 10 i 20 w końcowym polu.

24
00:01:27,760 --> 00:01:33,000
Pamiętaj, dwa naprawdę dobre rzeczy o tej tablicy

25
00:01:33,000 --> 00:01:38,800
jest to, że mamy ten stały dostęp w czasie do konkretnego elementu

26
00:01:38,800 --> 00:01:40,500
 w tablicy, jeśli znamy jego indeks.

27
00:01:40,500 --> 00:01:44,670
Na przykład, jeśli chcę złapać trzeci element w tablicy -

28
00:01:44,670 --> 00:01:47,870
o indeksie 2 za pomocą naszego zera system indeksowania -

29
00:01:47,870 --> 00:01:52,220
I dosłownie po prostu zrobić prosty matematyczny obliczeń

30
00:01:52,220 --> 00:01:56,170
wskoczyć do tej pozycji w tablicy,

31
00:01:56,170 --> 00:01:57,840
wyciągnij 8, który jest przechowywany tam,

32
00:01:57,840 --> 00:01:59,260
a ja jestem dobry, aby przejść.

33
00:01:59,260 --> 00:02:03,350
>> Jednym ze złych rzeczy o tej tablicy - że rozmawialiśmy o

34
00:02:03,350 --> 00:02:05,010
kiedy rozmawialiśmy związane list -

35
00:02:05,010 --> 00:02:09,120
to, że jeśli chcę wstawić element w tej tablicy

36
00:02:09,120 --> 00:02:11,090
Będę musiał zrobić kilka przesuwanie się.

37
00:02:11,090 --> 00:02:12,940
Na przykład, ta tablica tutaj

38
00:02:12,940 --> 00:02:16,850
jest w posortowanych - sortowane w porządku rosnącym -

39
00:02:16,850 --> 00:02:19,440
5, a następnie 7, a następnie 8, a następnie 10, a następnie 20 -

40
00:02:19,440 --> 00:02:23,100
ale jeśli chcę wstawić numer 9 na tej tablicy

41
00:02:23,100 --> 00:02:27,460
Będę musiał przenieść niektóre elementy w celu miejsca.

42
00:02:27,460 --> 00:02:30,440
Możemy zwrócić na to tutaj.

43
00:02:30,440 --> 00:02:35,650
Będę musiał przenieść 5, 7, a następnie 8;

44
00:02:35,650 --> 00:02:38,720
stworzyć lukę, gdzie mogę umieścić 9,

45
00:02:38,720 --> 00:02:45,910
, a następnie 10 do 20 może przejść do prawej na 9.

46
00:02:45,910 --> 00:02:49,450
Jest to rodzaj bólu, bo w najgorszym przypadku -

47
00:02:49,450 --> 00:02:54,350
kiedy masz wstawić albo na początku lub na końcu

48
00:02:54,350 --> 00:02:56,040
w tablicy, w zależności jak mamy przesunięcie -

49
00:02:56,040 --> 00:02:58,850
może się w końcu o przesunięcie wszystkich elementów

50
00:02:58,850 --> 00:03:00,750
że jesteśmy obecnie przechowywania w tablicy.

51
00:03:00,750 --> 00:03:03,810
>> Więc, co było sposobem obejścia tego?

52
00:03:03,810 --> 00:03:09,260
Odwrotnie było to, aby przejść do naszej linked-list metody, gdzie -

53
00:03:09,260 --> 00:03:19,820
zamiast przechowywania elementów 5, 7, 8, 10 i 20, wszystkie obok siebie w pamięci -

54
00:03:19,820 --> 00:03:25,630
czego nie było, zamiast przechowywać je rodzaj gdziekolwiek chcieliśmy je przechowywać

55
00:03:25,630 --> 00:03:32,470
w tych linked-list węzłów, które mam tu rysunek, rodzaj ad hoc.

56
00:03:32,470 --> 00:03:42,060
A potem podłączyć je ze sobą za pomocą tych kolejnych wskaźników.

57
00:03:42,060 --> 00:03:44,370
Mogę mieć wskaźnik od 5 do 7,

58
00:03:44,370 --> 00:03:46,420
Wskaźnik od 7 do 8,

59
00:03:46,420 --> 00:03:47,770
Wskaźnik od 8 do 10,

60
00:03:47,770 --> 00:03:51,220
i wreszcie, wskaźnik z 10 do 20,

61
00:03:51,220 --> 00:03:54,880
a następnie pusty wskaźnik na 20 wskazując, że nie ma nic.

62
00:03:54,880 --> 00:03:59,690
Trade-off, że mamy tu

63
00:03:59,690 --> 00:04:05,360
jest to, że teraz, jeśli chcemy wstawić numer 9 w naszym sortowanie listy,

64
00:04:05,360 --> 00:04:08,270
wszystko, co musimy zrobić, to stworzyć nowy węzeł z 9,

65
00:04:08,270 --> 00:04:12,290
podłączyć go do wskazywać na odpowiednim miejscu,

66
00:04:12,290 --> 00:04:20,630
, a następnie ponownie do przewodu 8 w dół do punktu 9.

67
00:04:20,630 --> 00:04:25,660
To dość szybko, zakładając dokładnie wiemy, gdzie chcemy wstawić 9.

68
00:04:25,660 --> 00:04:32,610
Ale kompromis w zamian za to, że mamy teraz stracił stały dostęp w czasie

69
00:04:32,610 --> 00:04:36,230
w jeden z elementów w naszej struktury danych.

70
00:04:36,230 --> 00:04:40,950
Na przykład, jeśli chcę znaleźć czwarty element w tej połączonej listy,

71
00:04:40,950 --> 00:04:43,510
Mam zamiar zacząć na samym początku listy

72
00:04:43,510 --> 00:04:48,930
i mój sposób pracy poprzez liczenie węzła-by-węzeł, aż znajdę czwartą.

73
00:04:48,930 --> 00:04:55,870
>> W celu uzyskania lepszej wydajności dostępu niż połączonej listy -

74
00:04:55,870 --> 00:04:59,360
ale również zachować niektóre z korzyści, które mieliśmy

75
00:04:59,360 --> 00:05:01,800
w zakresie podawania czasie z połączonej listy -

76
00:05:01,800 --> 00:05:05,750
Drzewo binarne będzie trzeba użyć trochę więcej pamięci.

77
00:05:05,750 --> 00:05:11,460
W szczególności, a nie tylko o jeden wskaźnik w binarnym węzeł drzewa -

78
00:05:11,460 --> 00:05:13,350
jak linked-list node robi -

79
00:05:13,350 --> 00:05:16,950
mamy zamiar dodać drugi wskaźnik do węzła drzewa binarnego.

80
00:05:16,950 --> 00:05:19,950
Zamiast tylko o jeden wskaźnik do następnego elementu,

81
00:05:19,950 --> 00:05:24,420
będziemy mieć wskaźnik do lewego dziecka i dziecka w prawo.

82
00:05:24,420 --> 00:05:26,560
>> Miejmy narysować obrazek, aby zobaczyć, co to rzeczywiście wygląda.

83
00:05:26,560 --> 00:05:31,350
Ponownie, mam zamiar wykorzystać te pola i strzały.

84
00:05:31,350 --> 00:05:37,150
Binarnym węzeł drzewo zacząć od pudełka jest proste.

85
00:05:37,150 --> 00:05:40,940
To będzie mieć miejsca na wartości,

86
00:05:40,940 --> 00:05:47,280
a to też będzie mieć miejsce na lewej dziecka i prawo.

87
00:05:47,280 --> 00:05:49,280
Mam zamiar opisać je tutaj.

88
00:05:49,280 --> 00:05:57,560
Będziemy mieć lewe dziecko, a potem będziemy mieć prawo dziecka.

89
00:05:57,560 --> 00:05:59,920
Istnieje wiele różnych sposobów, aby to zrobić.

90
00:05:59,920 --> 00:06:02,050
Czasami o przestrzeń i wygodę,

91
00:06:02,050 --> 00:06:06,460
Ja rzeczywiście wyciągnąć to jak robię na dole

92
00:06:06,460 --> 00:06:10,910
gdzie będę mieć wartość w górę,

93
00:06:10,910 --> 00:06:14,060
a następnie w prawo dziecka na prawej dolnej,

94
00:06:14,060 --> 00:06:16,060
a lewa dziecko na dole po lewej stronie.

95
00:06:16,060 --> 00:06:20,250
Wracając do tej góry diagramu

96
00:06:20,250 --> 00:06:22,560
mamy wartość na samym szczycie

97
00:06:22,560 --> 00:06:25,560
wtedy mamy lewej dzieci wskaźnik, a wtedy mamy prawo-dziecko wskaźnik.

98
00:06:25,560 --> 00:06:30,110
>> W specyfikacji podanej Problem,

99
00:06:30,110 --> 00:06:33,110
mówimy o rysunku węzeł, który ma wartość 7,

100
00:06:33,110 --> 00:06:39,750
a następnie w lewo-dziecko wskaźnik, który jest pusty, i prawym dzieckiem wskaźnik, który jest pusty.

101
00:06:39,750 --> 00:06:46,040
Możemy napisać NULL kapitału w miejsca do

102
00:06:46,040 --> 00:06:51,610
zarówno po lewej i prawej dziecko dziecko lub możemy wyciągnąć ten przekątnej slash

103
00:06:51,610 --> 00:06:53,750
w ramach każdego z pól, aby wskazać, że jest null.

104
00:06:53,750 --> 00:06:57,560
Mam zamiar to zrobić tylko dlatego, że to prostsze.

105
00:06:57,560 --> 00:07:03,700
Co można zobaczyć tutaj są dwa sposoby tworzenia diagramów bardzo prosty węzeł drzewa binarnego

106
00:07:03,700 --> 00:07:07,960
gdzie mamy wartość 7 i null odnośniki podrzędne.

107
00:07:07,960 --> 00:07:15,220
>> Druga część naszych rozmów o tym, jak w specyfikacji z powiązanych list -

108
00:07:15,220 --> 00:07:18,270
pamiętaj, że mieliśmy tylko trzymać się pierwszego elementu na liście

109
00:07:18,270 --> 00:07:20,270
zapamiętać całą listę -

110
00:07:20,270 --> 00:07:26,140
i podobnie, z drzewa binarnego, tylko musi trzymać jeden wskaźnik do drzewa

111
00:07:26,140 --> 00:07:31,120
W celu zachowania kontroli nad całej struktury danych.

112
00:07:31,120 --> 00:07:36,150
Ten specjalny element drzewa nazywa Korzeń z drzewa.

113
00:07:36,150 --> 00:07:43,360
Na przykład, jeśli jeden węzeł - węzeł zawierający wartość 7

114
00:07:43,360 --> 00:07:45,500
przy zerowych wskaźników lewej i prawej dziecko -

115
00:07:45,500 --> 00:07:47,360
były tylko wartości w naszym drzewie,

116
00:07:47,360 --> 00:07:50,390
wówczas byłby to nasz węzeł główny.

117
00:07:50,390 --> 00:07:52,240
To sam początek naszego drzewa.

118
00:07:52,240 --> 00:07:58,530
Widzimy to trochę jaśniej raz zaczniemy dodawać kolejne węzły naszego drzewa.

119
00:07:58,530 --> 00:08:01,510
Pozwól mi wyciągnąć nową stronę.

120
00:08:01,510 --> 00:08:05,000
>> Teraz idziemy narysować drzewo, które ma 7 u nasady,

121
00:08:05,000 --> 00:08:10,920
i 3 wewnątrz lewej dziecka i 9 wnętrzem prawej dziecka.

122
00:08:10,920 --> 00:08:13,500
Ponownie, jest to całkiem proste.

123
00:08:13,500 --> 00:08:26,510
Mamy 7, narysować węzeł 3, 9, do węzła

124
00:08:26,510 --> 00:08:32,150
i mam zamiar ustawić lewy wskaźnik dzieci z 7 do punktu do węzła zawierającego 3,

125
00:08:32,150 --> 00:08:37,850
i prawym dziecko wskaźnik węzła zawierających 7 do węzła zawierających 9.

126
00:08:37,850 --> 00:08:42,419
Teraz, od 3 i 9 nie mają dzieci,

127
00:08:42,419 --> 00:08:48,500
zamierzamy ustawić wszystkie swoje wskaźniki dzieci będą puste.

128
00:08:48,500 --> 00:08:56,060
Tutaj, korzeń naszego drzewa odpowiada węzeł zawierający numer 7.

129
00:08:56,060 --> 00:09:02,440
Można zobaczyć, że jeśli wszystko mamy, to wskaźnik do tego korzenia,

130
00:09:02,440 --> 00:09:07,330
możemy następnie przejść przez naszego drzewa i dostęp zarówno węzły -

131
00:09:07,330 --> 00:09:10,630
zarówno 3 i 9.

132
00:09:10,630 --> 00:09:14,820
Nie trzeba się utrzymać wskaźniki do każdego węzła w drzewie.

133
00:09:14,820 --> 00:09:22,080
Dobrze. Teraz mamy zamiar dodać kolejny węzeł na tym schemacie.

134
00:09:22,080 --> 00:09:25,370
Mamy zamiar dodać węzeł zawierający 6,

135
00:09:25,370 --> 00:09:34,140
i mamy zamiar dodać to jako prawego dziecka węzła zawierającego 3.

136
00:09:34,140 --> 00:09:41,850
Aby to zrobić, mam zamiar usunąć tego pustego wskaźnika w 3-węzeł

137
00:09:41,850 --> 00:09:47,750
i połączyć go zwrócić do węzła zawierającego 6. Dobrze.

138
00:09:47,750 --> 00:09:53,800
>> W tym momencie, idziemy na trochę terminologii.

139
00:09:53,800 --> 00:09:58,230
Aby rozpocząć, powód, dla którego jest to tzw drzewo binarne, w szczególności

140
00:09:58,230 --> 00:10:00,460
jest to, że składa się z dwóch podrzędnych wskaźniki.

141
00:10:00,460 --> 00:10:06,020
Istnieją inne gatunki drzew, które mają więcej wskaźników podrzędnych.

142
00:10:06,020 --> 00:10:10,930
W szczególności, nie ", spróbuj" w secie Problem 5.

143
00:10:10,930 --> 00:10:19,310
Można zauważyć, że w tym razem, trzeba było 27 różne wskaźniki do różnych dzieci -

144
00:10:19,310 --> 00:10:22,410
jednym dla każdej z 26 liter alfabetu angielskiego,

145
00:10:22,410 --> 00:10:25,410
, a następnie w 27 do apostrofu -

146
00:10:25,410 --> 00:10:28,900
Tak więc, jest to podobne do rodzaju drzewa.

147
00:10:28,900 --> 00:10:34,070
Ale tutaj, ponieważ jest to binarny, mamy tylko dwa podrzędne wskaźniki.

148
00:10:34,070 --> 00:10:37,880
>> Oprócz tego korzenia, że ​​mówiliśmy,

149
00:10:37,880 --> 00:10:41,470
mamy także rzucając wokół tego pojęcia "dziecko".

150
00:10:41,470 --> 00:10:44,470
Co to oznacza dla jednego węzła na dziecko z innego węzła?

151
00:10:44,470 --> 00:10:54,060
Dosłownie oznacza to, że węzeł dziecko jest dzieckiem innego węzła

152
00:10:54,060 --> 00:10:58,760
jeśli inny węzeł ma jeden z jego wskazówkami dzieci określonych wskazać na tym węźle.

153
00:10:58,760 --> 00:11:01,230
Aby umieścić to w bardziej konkretny sposób

154
00:11:01,230 --> 00:11:11,170
jeśli 3 jest wskazywany przez jeden z wskaźników podrzędnych 7, a następnie 3 jest dzieckiem 7.

155
00:11:11,170 --> 00:11:14,510
Gdybyśmy mieli się dowiedzieć, co dzieci 7 są -

156
00:11:14,510 --> 00:11:18,510
dobrze, zobaczymy, że 7 ma wskaźnik do 3 i odnośnik, 9,

157
00:11:18,510 --> 00:11:22,190
tak 9 i 3 to dzieci 7.

158
00:11:22,190 --> 00:11:26,650
Dziewiątka nie ma dzieci, ponieważ jego wskaźniki dzieci są null,

159
00:11:26,650 --> 00:11:30,940
i 3 ma tylko jedno dziecko, 6.

160
00:11:30,940 --> 00:11:37,430
Six też nie ma dzieci, ponieważ zarówno jego wskaźniki są nieważne, co będziemy rysować teraz.

161
00:11:37,430 --> 00:11:45,010
>> Dodatkowo, również o rodziców danego węzła,

162
00:11:45,010 --> 00:11:51,100
i jest to, jak można się spodziewać, odwrotnością tego opisu dziecka.

163
00:11:51,100 --> 00:11:58,620
Każdy węzeł ma tylko jednego rodzica - zamiast dwóch jak można się spodziewać z ludźmi.

164
00:11:58,620 --> 00:12:03,390
Na przykład, macierzysty 3 jest 7.

165
00:12:03,390 --> 00:12:10,800
Macierzysty 9 również 7 i dominującą 6 wynosi 3. Nie wiele.

166
00:12:10,800 --> 00:12:15,720
Mamy również warunki do rozmowy o dziadków i wnuków,

167
00:12:15,720 --> 00:12:18,210
i ogólnie mówimy o przodkach

168
00:12:18,210 --> 00:12:20,960
i potomków danego węzła.

169
00:12:20,960 --> 00:12:25,710
Przodkiem węzła - albo przodkowie raczej węzła -

170
00:12:25,710 --> 00:12:32,730
są wszystkie węzły leżących na drodze od korzenia do tego węzła.

171
00:12:32,730 --> 00:12:36,640
Na przykład, jeśli patrzę na węźle 6,

172
00:12:36,640 --> 00:12:46,430
następnie przodkowie będą zarówno 3 i 7.

173
00:12:46,430 --> 00:12:55,310
Przodkowie 9, na przykład, są - jeśli patrzę na węźle 9 -

174
00:12:55,310 --> 00:12:59,990
następnie przodek 9 tylko 7.

175
00:12:59,990 --> 00:13:01,940
I potomkowie są dokładnie odwrotne.

176
00:13:01,940 --> 00:13:05,430
Jeśli chcesz spojrzeć na wszystko z potomków 7,

177
00:13:05,430 --> 00:13:11,020
wtedy trzeba patrzeć na wszystkie węzły pod nim.

178
00:13:11,020 --> 00:13:16,950
Tak, mam 3, 9 i 6 wszystko jako potomków 7.

179
00:13:16,950 --> 00:13:24,170
>> Ostateczny termin, będziemy rozmawiać o to pojęcie jako rodzeństwo.

180
00:13:24,170 --> 00:13:27,980
Rodzeństwo - Rodzaju po wzdłuż na tych warunkach rodzinnych -

181
00:13:27,980 --> 00:13:33,150
są węzły są na tym samym poziomie w drzewie.

182
00:13:33,150 --> 00:13:42,230
Więc, 3 i 9 są rodzeństwem Ponieważ są na tym samym poziomie, w drzewie.

183
00:13:42,230 --> 00:13:46,190
Obaj mają tego samego rodzica, 7.

184
00:13:46,190 --> 00:13:51,400
6 nie ma rodzeństwa, bo 9 nie mają dzieci.

185
00:13:51,400 --> 00:13:55,540
I 7 nie mają rodzeństwa, ponieważ jest źródłem naszego drzewa,

186
00:13:55,540 --> 00:13:59,010
i jest zawsze tylko 1 root.

187
00:13:59,010 --> 00:14:02,260
Na 7 mieć rodzeństwa musiałaby być powyżej 7 węzła.

188
00:14:02,260 --> 00:14:07,480
Nie musiałby być rodzicem 7, w tym przypadku 7 nie będzie już korzeniem drzewa.

189
00:14:07,480 --> 00:14:10,480
Następnie, że nowa jednostka dominująca z 7 musiałby również mieć dziecko,

190
00:14:10,480 --> 00:14:16,480
i to dziecko będzie wówczas rodzeństwo 7.

191
00:14:16,480 --> 00:14:21,040
>> Dobrze. Idziemy dalej.

192
00:14:21,040 --> 00:14:24,930
Kiedy zaczynaliśmy naszą dyskusję drzew binarnych,

193
00:14:24,930 --> 00:14:28,790
Rozmawialiśmy o tym, jak mieliśmy zamiar wykorzystać je do

194
00:14:28,790 --> 00:14:32,800
zyskać przewagę na obu tablicach i listach linked.

195
00:14:32,800 --> 00:14:37,220
A sposób, w jaki zamierzamy zrobić to jest z tym zamawiającego.

196
00:14:37,220 --> 00:14:41,080
Możemy powiedzieć, że drzewo binarne jest uporządkowane, zgodnie ze specyfikacją,

197
00:14:41,080 --> 00:14:45,740
jeśli dla każdego węzła w naszym drzewie, wszystkie jego potomków po lewej -

198
00:14:45,740 --> 00:14:48,670
lewa dziecko i wszystkie lewego dziecka potomków -

199
00:14:48,670 --> 00:14:54,510
mają mniejsze wartości, i wszystkie węzły w prawo -

200
00:14:54,510 --> 00:14:57,770
prawa dziecka i wszystko z prawa dziecka potomków -

201
00:14:57,770 --> 00:15:02,800
mają węzły większe niż wartość bieżącego węzła, że ​​mamy do czynienia.

202
00:15:02,800 --> 00:15:07,850
Tylko dla uproszczenia, będziemy zakładać, że nie ma żadnych zduplikowanych węzły naszego drzewa.

203
00:15:07,850 --> 00:15:11,180
Na przykład, w tym drzewie nie będziemy zajmować się sprawą

204
00:15:11,180 --> 00:15:13,680
gdzie mamy wartość 7 w katalogu głównym

205
00:15:13,680 --> 00:15:16,720
 a także mają wartość 7 w innych częściach drzewa.

206
00:15:16,720 --> 00:15:24,390
W tym przypadku, można zauważyć, że to drzewo jest rzeczywiście zamówiłem.

207
00:15:24,390 --> 00:15:26,510
Mamy wartość 7 w katalogu głównym.

208
00:15:26,510 --> 00:15:29,720
Wszystko na lewo 7 -

209
00:15:29,720 --> 00:15:35,310
jeśli cofnąć wszystkie z tych małych znaków tutaj -

210
00:15:35,310 --> 00:15:40,450
Wszystko na lewo 7 - 3 i 6 -

211
00:15:40,450 --> 00:15:49,410
wartości te są zarówno mniej niż 7, a wszystko w prawo - co jest właśnie to 9 -

212
00:15:49,410 --> 00:15:53,450
jest większa niż 7.

213
00:15:53,450 --> 00:15:58,650
>> To nie tylko zamówić drzewo zawierające tych wartości jest

214
00:15:58,650 --> 00:16:03,120
ale narysujmy kilka więcej z nich.

215
00:16:03,120 --> 00:16:05,030
Tu jest rzeczywiście cała masa sposobów, że możemy to zrobić.

216
00:16:05,030 --> 00:16:09,380
Mam zamiar używać skrótów tylko zachować rzeczy proste, gdzie -

217
00:16:09,380 --> 00:16:11,520
niż wyciągając całość pudełka-i-strzałki -

218
00:16:11,520 --> 00:16:14,220
Idę wyciągnąć numery i dodać strzałki łączące je.

219
00:16:14,220 --> 00:16:22,920
Aby rozpocząć, po prostu napisz do naszego oryginalnego drzewa ponownie gdzie mieliśmy 7, a następnie 3,

220
00:16:22,920 --> 00:16:25,590
, a następnie 3 wskazał na prawo do 6,

221
00:16:25,590 --> 00:16:30,890
i 7 miał prawo dziecka, które było 9.

222
00:16:30,890 --> 00:16:33,860
Dobrze. Co znajduje się w inny sposób, że możemy napisać to drzewo?

223
00:16:33,860 --> 00:16:38,800
Zamiast 3 być lewa dziecko 7,

224
00:16:38,800 --> 00:16:41,360
moglibyśmy mieć 6 będzie lewo dziecko 7,

225
00:16:41,360 --> 00:16:44,470
i 3 z lewej strony: z 6 dzieci.

226
00:16:44,470 --> 00:16:48,520
To będzie wyglądać tego drzewa tu gdzie mam 7,

227
00:16:48,520 --> 00:16:57,860
niż 6, a 3 i 9 na prawo.

228
00:16:57,860 --> 00:17:01,490
My również nie mieć 7 jako naszego węzła głównego.

229
00:17:01,490 --> 00:17:03,860
Możemy również 6 jako naszego węzła głównego.

230
00:17:03,860 --> 00:17:06,470
Co by to wyglądało?

231
00:17:06,470 --> 00:17:09,230
Jeśli chcemy utrzymać tę uporządkowaną nieruchomości,

232
00:17:09,230 --> 00:17:12,970
Wszystko do lewej 6 musi być mniejsza niż.

233
00:17:12,970 --> 00:17:16,540
Jest tylko jedna możliwość, a to 3.

234
00:17:16,540 --> 00:17:19,869
Ale potem, jak po prawej dziecka 6, mamy dwie możliwości.

235
00:17:19,869 --> 00:17:25,380
Po pierwsze, może to mieć na 7, a następnie 9

236
00:17:25,380 --> 00:17:28,850
albo możemy wyciągnąć go - jak mam do zrobienia -

237
00:17:28,850 --> 00:17:34,790
gdzie mamy 9 jako prawy podrzędny 6,

238
00:17:34,790 --> 00:17:39,050
i 7, jak lewej dziecka z 9.

239
00:17:39,050 --> 00:17:44,240
>> Teraz, 7 i 6, nie tylko są możliwe wartości korzenia.

240
00:17:44,240 --> 00:17:50,200
Możemy mieć również 3 być w katalogu głównym.

241
00:17:50,200 --> 00:17:52,240
Co się stanie, jeśli 3 jest źródłem?

242
00:17:52,240 --> 00:17:54,390
Tutaj robi się trochę interesujące.

243
00:17:54,390 --> 00:17:58,440
Trzy nie ma żadnych wartości, które są mniejsze niż to,

244
00:17:58,440 --> 00:18:02,070
tak, że cała lewa strona drzewa jest tylko będzie null.

245
00:18:02,070 --> 00:18:03,230
Nie będzie to coś tam.

246
00:18:03,230 --> 00:18:07,220
W prawo, moglibyśmy wymienić rzeczy w porządku rosnącym.

247
00:18:07,220 --> 00:18:15,530
Moglibyśmy mieć 3, potem 6, potem 7, potem 9.

248
00:18:15,530 --> 00:18:26,710
Albo, możemy zrobić 3, potem 6, potem 9, potem 7.

249
00:18:26,710 --> 00:18:35,020
Albo, możemy zrobić 3, potem 7, potem 6, potem 9.

250
00:18:35,020 --> 00:18:40,950
Albo, 3, 7 - w rzeczywistości nie, nie możemy zrobić 7 więcej.

251
00:18:40,950 --> 00:18:43,330
To nasza jedno tam.

252
00:18:43,330 --> 00:18:54,710
Możemy zrobić, 9, a następnie od 9 możemy zrobić 6 i 7.

253
00:18:54,710 --> 00:19:06,980
Albo, możemy zrobić 3, potem 9, potem 7, a następnie 6.

254
00:19:06,980 --> 00:19:12,490
>> Jedną z rzeczy, zwrócić uwagę na o to

255
00:19:12,490 --> 00:19:14,510
że te drzewa są trochę dziwnie wyglądające.

256
00:19:14,510 --> 00:19:17,840
W szczególności, jeśli spojrzymy na 4 drzew po prawej stronie -

257
00:19:17,840 --> 00:19:20,930
Będę krążyć je tutaj -

258
00:19:20,930 --> 00:19:28,410
drzewa te wyglądają niemal identycznie jak połączonej listy.

259
00:19:28,410 --> 00:19:32,670
Każdy węzeł ma tylko jedno dziecko,

260
00:19:32,670 --> 00:19:38,950
i tak, że nie ma żadnych tego strukturę drzewa widzimy, że, na przykład,

261
00:19:38,950 --> 00:19:44,720
 w tym jednego drzewa samotny tu w lewym dolnym rogu.

262
00:19:44,720 --> 00:19:52,490
Drzewa te są w rzeczywistości nazywa się zdegenerowanym drzew binarnych,

263
00:19:52,490 --> 00:19:54,170
i porozmawiamy o nich więcej w przyszłości -

264
00:19:54,170 --> 00:19:56,730
szczególnie jeśli pójdziesz na podjęcie innych kursów informatycznych.

265
00:19:56,730 --> 00:19:59,670
Drzewa te są zdegenerowane.

266
00:19:59,670 --> 00:20:03,780
Nie są one bardzo użyteczne, ponieważ rzeczywiście, struktura ta nadaje się

267
00:20:03,780 --> 00:20:08,060
 do wyszukiwania razy podobną do połączonej listy.

268
00:20:08,060 --> 00:20:13,050
Nie mamy do skorzystania z dodatkowej pamięci - ten dodatkowy wskaźnik -

269
00:20:13,050 --> 00:20:18,840
struktury, ponieważ są naszego Bad w ten sposób.

270
00:20:18,840 --> 00:20:24,700
Zamiast iść i wyciągnąć binarne drzew, które mają 9 u nasady,

271
00:20:24,700 --> 00:20:27,220
która jest ostateczna sprawa, że ​​mamy,

272
00:20:27,220 --> 00:20:32,380
Jesteśmy natomiast w tym momencie, będziemy mówić trochę o tej drugiej kadencji

273
00:20:32,380 --> 00:20:36,150
którego używamy, gdy mówimy o drzewach, co nazywa wysokość.

274
00:20:36,150 --> 00:20:45,460
>> Wysokość drzewa jest odległość od korzenia do węzła najbardziej odległej,

275
00:20:45,460 --> 00:20:48,370
lub raczej liczba przeskoków, które trzeba zrobić, aby

276
00:20:48,370 --> 00:20:53,750
rozpocząć od korzenia, a następnie kończy się w najbardziej odległej węzła w drzewie.

277
00:20:53,750 --> 00:20:57,330
Jeśli spojrzymy na niektóre z tych drzew, które mamy wyciągnąć tutaj,

278
00:20:57,330 --> 00:21:07,870
widzimy, że jeśli weźmiemy to drzewo w lewym górnym rogu i zacząć na 3,

279
00:21:07,870 --> 00:21:14,510
wtedy mamy do 1 hop aby dostać się do 6, drugi hop aby dostać się do 7,

280
00:21:14,510 --> 00:21:20,560
a trzeci hop aby dostać się do 9.

281
00:21:20,560 --> 00:21:26,120
Tak więc, to wysokość wynosi 3 drzewa.

282
00:21:26,120 --> 00:21:30,640
Możemy zrobić to samo ćwiczenie dla innych drzew wymienionych z tym zielonym,

283
00:21:30,640 --> 00:21:40,100
widzimy, że wysokość tych wszystkich drzew jest nawet 3.

284
00:21:40,100 --> 00:21:45,230
To część tego, co sprawia, że ​​zdegenerowany -

285
00:21:45,230 --> 00:21:53,750
ich wysokość jest mniejsza niż jednym liczby węzłów w całym drzewie.

286
00:21:53,750 --> 00:21:58,400
Jeśli przyjrzymy się tym drugim drzewie, które jest otoczone z czerwonym, z drugiej strony,

287
00:21:58,400 --> 00:22:03,920
widzimy, że najbardziej odległe węzły liściowe 6 i 9 -

288
00:22:03,920 --> 00:22:06,940
pozostawia będąc te węzły, które nie mają dzieci.

289
00:22:06,940 --> 00:22:11,760
Tak więc, w celu uzyskania z korzenia albo do 6, lub 9,

290
00:22:11,760 --> 00:22:17,840
musimy mieć jeden węzeł, aby przejść do 7 sekund, a następnie hop aby dostać się do 9,

291
00:22:17,840 --> 00:22:21,240
i również tylko drugiego węzła z 7, aby do 6.

292
00:22:21,240 --> 00:22:29,080
Tak, wysokość tego drzewa tu jest tylko 2.

293
00:22:29,080 --> 00:22:35,330
Możesz wrócić i zrobić to dla wszystkich innych drzew, które już wcześniej wspomniano

294
00:22:35,330 --> 00:22:37,380
począwszy od 7 i 6,

295
00:22:37,480 --> 00:22:42,500
a przekonasz się, że wysokość wszystkich tych drzew jest również 2.

296
00:22:42,500 --> 00:22:46,320
>> Powodem rozmawialiśmy o nakazał drzewa binarne

297
00:22:46,320 --> 00:22:50,250
i dlaczego są fajne, ponieważ możesz przeglądać je w

298
00:22:50,250 --> 00:22:53,810
bardzo podobny sposób do poszukiwania na posortowanej tablicy.

299
00:22:53,810 --> 00:22:58,720
To jest, gdy mówimy o coraz to lepszy czas odnośnika

300
00:22:58,720 --> 00:23:02,730
na prostej listy powiązane.

301
00:23:02,730 --> 00:23:05,010
Dzięki połączonej listy - jeśli chcesz, aby znaleźć konkretny element -

302
00:23:05,010 --> 00:23:07,470
jesteś w najlepszym zrobić jakąś liniowej wyszukiwanie

303
00:23:07,470 --> 00:23:10,920
gdzie zaczyna się na początku listy i hip jeden po drugim -

304
00:23:10,920 --> 00:23:12,620
jeden węzeł przez jednego węzła -

305
00:23:12,620 --> 00:23:16,060
całą listę, aż znajdziesz cokolwiek, czego szukasz.

306
00:23:16,060 --> 00:23:19,440
Mając na uwadze, jeśli masz drzewo binarne, które jest zapisane w tej miłej formacie

307
00:23:19,440 --> 00:23:23,300
rzeczywiście można dostać więcej binarnego wyszukiwania dzieje

308
00:23:23,300 --> 00:23:25,160
gdzie dziel i rządź

309
00:23:25,160 --> 00:23:29,490
i wyszukiwania odpowiedniej połowie drzewa w każdym kroku.

310
00:23:29,490 --> 00:23:32,840
Zobaczmy, jak to działa.

311
00:23:32,840 --> 00:23:38,850
>> Jeśli mamy - znów wrócić do naszego pierwotnego drzewa -

312
00:23:38,850 --> 00:23:46,710
zaczynamy na 7, mamy 3 na lewo, 9 po prawej stronie,

313
00:23:46,710 --> 00:23:51,740
i poniżej 3 mamy 6.

314
00:23:51,740 --> 00:24:01,880
Jeśli chcemy wyszukać numer 6 w tym drzewie, chcemy rozpocząć w katalogu głównym.

315
00:24:01,880 --> 00:24:08,910
Chcemy porównać wartość szukamy, powiedzmy 6,

316
00:24:08,910 --> 00:24:12,320
do wartości przechowywanej w węźle, który mamy obecnie, patrząc na, 7,

317
00:24:12,320 --> 00:24:21,200
okaże się, że 6 jest rzeczywiście mniej niż 7, tak, że możemy przenieść się w lewo.

318
00:24:21,200 --> 00:24:25,530
Jeśli wartości 6 było większe niż 7, a nie będzie się już przesunięty w prawo.

319
00:24:25,530 --> 00:24:29,770
Ponieważ wiadomo, że - z uwagi na strukturę drzewa naszego zamówionej binarnych -

320
00:24:29,770 --> 00:24:33,910
wszystkie wartości poniżej 7 będą przechowywane w lewo 7,

321
00:24:33,910 --> 00:24:40,520
nie ma potrzeby, aby niepokoić nawet przeglądając prawej stronie drzewa.

322
00:24:40,520 --> 00:24:43,780
Gdy poruszamy się w lewo i jesteśmy teraz w węźle zawierającym 3,

323
00:24:43,780 --> 00:24:48,110
możemy zrobić tego samego porównania ponownie gdy porównamy 3 i 6.

324
00:24:48,110 --> 00:24:52,430
I okazuje się, że podczas 6 - wartość szukamy - jest większy niż 3,

325
00:24:52,430 --> 00:24:58,580
można go do prawej strony węzła zawierającej 3.

326
00:24:58,580 --> 00:25:02,670
Nie ma po lewej stronie tutaj, więc mogliśmy zignorować tego.

327
00:25:02,670 --> 00:25:06,510
Ale my wiemy, że tylko dlatego, że patrzysz na samo drzewo,

328
00:25:06,510 --> 00:25:08,660
i widzimy, że drzewo nie ma dzieci.

329
00:25:08,660 --> 00:25:13,640
>> Jest również dość łatwe do wyszukania 6 w tym drzewie, jeśli robimy to sami jako ludzie,

330
00:25:13,640 --> 00:25:16,890
ale niech śledzić ten proces mechanicznie jak komputer zrobi

331
00:25:16,890 --> 00:25:18,620
naprawdę zrozumieć algorytm.

332
00:25:18,620 --> 00:25:26,200
W tym momencie, jesteśmy teraz patrząc na węźle zawiera 6,

333
00:25:26,200 --> 00:25:29,180
i szukamy wartości 6,

334
00:25:29,180 --> 00:25:31,740
tak, rzeczywiście, znaleźliśmy odpowiedni węzeł.

335
00:25:31,740 --> 00:25:35,070
Okazało się, że wartość 6 w naszym drzewie, a my możemy zatrzymać nasze poszukiwania.

336
00:25:35,070 --> 00:25:37,330
W tym miejscu, w zależności od tego, co dzieje się,

337
00:25:37,330 --> 00:25:41,870
możemy powiedzieć, tak, udało nam się znaleźć wartość 6, istnieje w naszym drzewie.

338
00:25:41,870 --> 00:25:47,640
Lub, jeśli planujemy wstawić węzeł lub coś zrobić, możemy to zrobić w tym momencie.

339
00:25:47,640 --> 00:25:53,010
>> Zróbmy kilka więcej odnośników, by zobaczyć jak to działa.

340
00:25:53,010 --> 00:25:59,390
Spójrzmy na to, co się stanie, jeśli były, aby spróbować spojrzeć na wartość 10.

341
00:25:59,390 --> 00:26:02,970
Gdybyśmy mieli patrzeć na wartość 10, moglibyśmy zacząć od korzenia.

342
00:26:02,970 --> 00:26:07,070
Chcemy zobaczyć, że 10 jest większa niż 7, tak, że możemy przenieść się w prawo.

343
00:26:07,070 --> 00:26:13,640
Chcemy dostać się do 9 i porównaj 9 do 10 i zobaczyć, że 9 jest rzeczywiście mniej niż 10.

344
00:26:13,640 --> 00:26:16,210
Więc jeszcze raz, chcemy spróbować przenieść do prawej.

345
00:26:16,210 --> 00:26:20,350
Ale w tym momencie, to zauważymy, że jesteśmy na pustym węzłem.

346
00:26:20,350 --> 00:26:23,080
Nic tam nie ma. Nie ma nic, gdzie 10 powinno być.

347
00:26:23,080 --> 00:26:29,360
To jest, gdzie można zgłosić awarię - że w istocie nie istnieje 10 w drzewie.

348
00:26:29,360 --> 00:26:35,420
I w końcu, idziemy przez przypadku, gdy chcemy zajrzeć do 1 w drzewie.

349
00:26:35,420 --> 00:26:38,790
Jest to podobne do tego, co się dzieje, jeśli przyjrzymy się 10, z wyjątkiem zamiast iść na prawo,

350
00:26:38,790 --> 00:26:41,260
mamy zamiar iść w lewo.

351
00:26:41,260 --> 00:26:46,170
Zacząć w 7 i zobaczyć, że 1 jest mniejsza niż 7, tak, że przesuwają się w lewo.

352
00:26:46,170 --> 00:26:51,750
Docieramy do 3 i widzę, że 1 jest mniejsza niż 3, więc znów staramy się poruszać w lewo.

353
00:26:51,750 --> 00:26:59,080
W tym momencie mamy zerowy węzła, więc ponownie możemy zgłosić awarię.

354
00:26:59,080 --> 00:27:10,260
>> Jeśli chcesz dowiedzieć się więcej o drzew binarnych,

355
00:27:10,260 --> 00:27:14,420
istnieje cała masa zabawnych małych problemów, które możesz zrobić z nimi.

356
00:27:14,420 --> 00:27:19,450
Proponuję ćwiczenia rysunek z tych schematów jeden po drugim

357
00:27:19,450 --> 00:27:21,910
i po przez wszystkich różnych etapów,

358
00:27:21,910 --> 00:27:25,060
bo to przyjdzie w super-poręczny

359
00:27:25,060 --> 00:27:27,480
nie tylko wtedy, gdy robisz się kodowania Huffmana zestaw problemów

360
00:27:27,480 --> 00:27:29,390
ale także w przyszłych kursów -

361
00:27:29,390 --> 00:27:32,220
tylko uczenie się, jak wyciągnąć te struktury danych i przemyśleć problemy

362
00:27:32,220 --> 00:27:38,000
z pióra i papieru lub, w tym przypadku, iPad i rysik.

363
00:27:38,000 --> 00:27:41,000
>> W tym momencie chociaż, mamy zamiar przenieść się do niektórych praktyk kodowania

364
00:27:41,000 --> 00:27:44,870
i rzeczywiście grać z tych drzew binarnych i zobaczyć.

365
00:27:44,870 --> 00:27:52,150
Mam zamiar wrócić do mojego komputera.

366
00:27:52,150 --> 00:27:58,480
Dla tej części sekcji, zamiast uruchomić lub CS50 CS50 spacje,

367
00:27:58,480 --> 00:28:01,500
Mam zamiar korzystać z urządzenia.

368
00:28:01,500 --> 00:28:04,950
>> Po wraz z specyfikacją zestawu Problem,

369
00:28:04,950 --> 00:28:07,740
Widzę, że mam do otwarcia urządzenia,

370
00:28:07,740 --> 00:28:11,020
przejdź do folderu Dropbox, utwórz folder o nazwie Sekcja 7,

371
00:28:11,020 --> 00:28:15,730
a następnie utworzyć plik o nazwie binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Jedziemy. Mam urządzenie już otwarty.

373
00:28:22,050 --> 00:28:25,910
Zamierzam wyciągnąć terminal.

374
00:28:25,910 --> 00:28:38,250
Mam zamiar przejść do folderu Dropbox, utwórz katalog o nazwie section7,

375
00:28:38,250 --> 00:28:42,230
i widzę, że jest zupełnie pusta.

376
00:28:42,230 --> 00:28:48,860
Teraz mam zamiar otworzyć binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Dobrze. Zaczynamy - pusty plik.

378
00:28:51,750 --> 00:28:54,330
>> Wróćmy do specyfikacji.

379
00:28:54,330 --> 00:28:59,850
Specyfikacja prosi, aby utworzyć nową definicję typu

380
00:28:59,850 --> 00:29:03,080
dla węzła drzewa binarnego zawierającego wartości int -

381
00:29:03,080 --> 00:29:07,110
podobnie jak wartości, które zbierało się w naszych diagramów wcześniej.

382
00:29:07,110 --> 00:29:11,740
Zamierzamy to wykorzystać boilerplate typedef że zrobiliśmy tutaj

383
00:29:11,740 --> 00:29:14,420
że należy uznać ze zbioru Problem 5 -

384
00:29:14,420 --> 00:29:19,190
jeśli nie hash sposób stołowego podboju programu ortografii.

385
00:29:19,190 --> 00:29:22,540
Należy również rozpoznać z zeszłotygodniowej sekcji

386
00:29:22,540 --> 00:29:23,890
gdzie rozmawialiśmy o połączonych listach.

387
00:29:23,890 --> 00:29:27,870
Mamy to typedef węzła struct,

388
00:29:27,870 --> 00:29:34,430
i daliśmy tego węzła struct tę nazwę węzła struct uprzednią

389
00:29:34,430 --> 00:29:39,350
tak, że możemy odwoływać się do niego, ponieważ my chcemy mieć wskaźniki węzła struct

390
00:29:39,350 --> 00:29:45,740
w ramach naszej struktury, ale my wtedy otoczony to -

391
00:29:45,740 --> 00:29:47,700
czy raczej zamknięty to - w typedef

392
00:29:47,700 --> 00:29:54,600
tak, że później w kodzie, można odnieść się do tej struktury w danym węźle, a nie tylko z węzła struktury.

393
00:29:54,600 --> 00:30:03,120
>> To ma być bardzo podobny do pojedynczo-linked definicji listy, które widzieliśmy w zeszłym tygodniu.

394
00:30:03,120 --> 00:30:20,070
Aby to zrobić, po prostu zacząć od wypisując szablonowe.

395
00:30:20,070 --> 00:30:23,840
Wiemy, że musimy mieć wartość całkowitą,

396
00:30:23,840 --> 00:30:32,170
będziemy więc umieścić w wartość int, a następnie, zamiast tylko jeden wskaźnik do następnego elementu -

397
00:30:32,170 --> 00:30:33,970
jak my z listy pojedynczo powiązanych -

398
00:30:33,970 --> 00:30:38,110
będziemy mieć lewe i prawe wskaźniki podrzędne.

399
00:30:38,110 --> 00:30:42,880
To całkiem proste, zbyt - struct node * lewy dziecko;

400
00:30:42,880 --> 00:30:51,190
i węzeł struct * prawo dziecka;. Cool.

401
00:30:51,190 --> 00:30:54,740
To wygląda na początek całkiem nieźle.

402
00:30:54,740 --> 00:30:58,530
Wróćmy do specyfikacji.

403
00:30:58,530 --> 00:31:05,030
>> Teraz musimy zadeklarować zmienną globalną * węzła do korzenia drzewa.

404
00:31:05,030 --> 00:31:10,590
Jedziemy, aby ten globalny, tak jak my miał pierwszy wskaźnik w naszej listy również globalnej.

405
00:31:10,590 --> 00:31:12,690
Tym, że w tak, że funkcje zapisu

406
00:31:12,690 --> 00:31:16,180
nie mamy zachować przechodząc wokół tego korzenia -

407
00:31:16,180 --> 00:31:19,620
jeśli zobaczymy, że jeśli nie chcę pisać tych funkcji rekurencyjnie,

408
00:31:19,620 --> 00:31:22,830
to może być lepiej nawet przechodzi wokół jako globalne przede

409
00:31:22,830 --> 00:31:28,090
i zamiast zainicjować go lokalnie w głównej funkcji.

410
00:31:28,090 --> 00:31:31,960
Ale zrobimy to na całym świecie, aby rozpocząć.

411
00:31:31,960 --> 00:31:39,920
Znowu damy kilka miejsc, i mam zamiar zadeklarować węzła głównego *.

412
00:31:39,920 --> 00:31:46,770
Wystarczy upewnić się, że nie pozostawić niezainicjowanych, zamierzam go ustawić równy null.

413
00:31:46,770 --> 00:31:52,210
Teraz, w głównej funkcji - co będziemy pisać naprawdę szybko tu -

414
00:31:52,210 --> 00:32:00,450
int main (int argc, char * argv []) -

415
00:32:00,450 --> 00:32:10,640
i mam zamiar rozpocząć deklarując mój argv tablicy jako const po prostu tak, że wiem,

416
00:32:10,640 --> 00:32:14,550
, że te argumenty są argumentami, że prawdopodobnie nie chcesz zmodyfikować.

417
00:32:14,550 --> 00:32:18,390
Jeśli chcę je zmodyfikować chyba powinienem być co ich kopii.

418
00:32:18,390 --> 00:32:21,740
Zobaczysz, to dużo w kodzie.

419
00:32:21,740 --> 00:32:25,440
Jest w porządku albo sposób. Dobrze jest pozostawić ją jako - pominąć const jeśli chcesz.

420
00:32:25,440 --> 00:32:28,630
I zazwyczaj umieścić go w właśnie tak, że przypominam sobie

421
00:32:28,630 --> 00:32:33,650
 że chyba nie chcesz modyfikować te argumenty.

422
00:32:33,650 --> 00:32:39,240
>> Jak zawsze, mam zamiar dołączenia zwrotny 0 wiersz na koniec main.

423
00:32:39,240 --> 00:32:45,730
Tutaj będą zainicjować mój węzeł główny.

424
00:32:45,730 --> 00:32:48,900
W obecnej chwili, mam wskaźnik, który jest ustawiony na null,

425
00:32:48,900 --> 00:32:52,970
więc to wskazuje na nic.

426
00:32:52,970 --> 00:32:57,480
Aby zacząć budować węzeł,

427
00:32:57,480 --> 00:32:59,250
I najpierw trzeba przydzielić pamięci dla niego.

428
00:32:59,250 --> 00:33:05,910
Mam zamiar to zrobić poprzez pamięć na stercie przy użyciu malloc.

429
00:33:05,910 --> 00:33:10,660
Mam zamiar ustawić pierwiastek równy wynikowi malloc,

430
00:33:10,660 --> 00:33:19,550
i mam zamiar użyć operatora sizeof do obliczenia wielkości węzła.

431
00:33:19,550 --> 00:33:24,990
Powodem tego, że używam węzła sizeof w przeciwieństwie do, powiedzmy,

432
00:33:24,990 --> 00:33:37,020
robi coś takiego - malloc (4 + 4 +4) lub malloc 12 -

433
00:33:37,020 --> 00:33:40,820
to dlatego, że chcę moje kodu być możliwie zgodne.

434
00:33:40,820 --> 00:33:44,540
Chcę być w stanie odebrać. Plik C, skompilować go na urządzeniu,

435
00:33:44,540 --> 00:33:48,820
a następnie skompilować go na moim Macu 64-bitowym -

436
00:33:48,820 --> 00:33:52,040
lub na zupełnie innej architektury -

437
00:33:52,040 --> 00:33:54,640
i chcę to wszystko działać same.

438
00:33:54,640 --> 00:33:59,510
>> Jeśli robię założenia dotyczące wielkości zmiennych -

439
00:33:59,510 --> 00:34:02,070
rozmiar int lub wielkość wskaźnika -

440
00:34:02,070 --> 00:34:06,070
to ja jestem również tworzenia założeń o rodzaju architektur

441
00:34:06,070 --> 00:34:10,440
na którym mój kod może pomyślnie skompilować podczas uruchamiania.

442
00:34:10,440 --> 00:34:15,030
Zawsze należy używać sizeof w przeciwieństwie do ręcznie zsumowanie pól struktury.

443
00:34:15,030 --> 00:34:20,500
Innym powodem jest to, że może również być wyściółka że kompilator wprowadza do struktury.

444
00:34:20,500 --> 00:34:26,570
Nawet zwykłe zsumowanie poszczególnych pól nie jest coś, zazwyczaj chcą robić to,

445
00:34:26,570 --> 00:34:30,340
tak, usuń ten wiersz.

446
00:34:30,340 --> 00:34:33,090
Teraz naprawdę zainicjować ten węzeł główny,

447
00:34:33,090 --> 00:34:36,489
Będę musiał podłączyć wartości dla każdego z różnych dziedzin.

448
00:34:36,489 --> 00:34:41,400
Na przykład, do wartości wiem Aby zainicjować do 7,

449
00:34:41,400 --> 00:34:46,920
i teraz mam zamiar ustawić lewy dziecko być null

450
00:34:46,920 --> 00:34:55,820
oraz prawo dziecka do być null. Great!

451
00:34:55,820 --> 00:35:02,670
Zrobiliśmy tę część specyfikacji.

452
00:35:02,670 --> 00:35:07,390
>> Specyfikacja w dół na dole strony 3 prosi mnie do stworzenia jeszcze trzy węzły -

453
00:35:07,390 --> 00:35:10,600
jeden zawierający 3, jeden zawierający 6, a jeden z 9 -

454
00:35:10,600 --> 00:35:14,210
a następnie podłączyć je tak, że wygląda dokładnie tak, jak naszym diagramie drzewa

455
00:35:14,210 --> 00:35:17,120
że rozmawialiśmy wcześniej.

456
00:35:17,120 --> 00:35:20,450
Zróbmy to dość szybko tutaj.

457
00:35:20,450 --> 00:35:26,270
Zobaczysz, naprawdę szybko, że mam zamiar zacząć pisać kilka duplikatu kodu.

458
00:35:26,270 --> 00:35:32,100
Zamierzam utworzyć węzeł * i będę nazywać trzy.

459
00:35:32,100 --> 00:35:36,000
Mam zamiar ustawić go równa malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Mam zamiar ustawić trzy-> value = 3.

461
00:35:41,070 --> 00:35:54,780
Trzy -> left_child = NULL; trzy -> prawy _child = NULL; również.

462
00:35:54,780 --> 00:36:01,150
To wygląda bardzo podobne do inicjowania korzenie, i to jest dokładnie to, co

463
00:36:01,150 --> 00:36:05,760
Mam zamiar zrobić jeśli zacznę inicjowanie 6 i 9, jak również.

464
00:36:05,760 --> 00:36:20,720
Zrobię to bardzo szybko tutaj - faktycznie, mam zamiar zrobić trochę kopiowania i wklejania,

465
00:36:20,720 --> 00:36:46,140
i upewnić się, że - w porządku.

466
00:36:46,470 --> 00:37:09,900
 Teraz mam to skopiowane i mogę śmiało i ustawić to równe 6.

467
00:37:09,900 --> 00:37:14,670
Widać, że to zajmuje trochę czasu i nie jest super-wydajny.

468
00:37:14,670 --> 00:37:22,610
W tylko trochę, będziemy napisać funkcję, która zrobi to za nas.

469
00:37:22,610 --> 00:37:32,890
Chcę, aby zastąpić to z 9, wymienić, że z 6.

470
00:37:32,890 --> 00:37:37,360
>> Teraz mamy wszystkie nasze węzły tworzone i inicjalizowane.

471
00:37:37,360 --> 00:37:41,200
Mamy nasz główny równy 7, lub zawierający wartość 7,

472
00:37:41,200 --> 00:37:46,510
nasz węzeł zawierający 3, nasz węzeł zawierający 6, a nasz węzeł zawierający 9.

473
00:37:46,510 --> 00:37:50,390
W tym momencie wszystko, co musimy zrobić, to wszystko drut.

474
00:37:50,390 --> 00:37:53,020
Powodem, dla którego inicjowane wszystkie wskaźniki na null jest tak, że ja się upewnić, że

475
00:37:53,020 --> 00:37:56,260
Nie mam żadnych niezainicjowane wskaźniki w tam przez przypadek.

476
00:37:56,260 --> 00:38:02,290
A także, ponieważ w tym momencie mam tylko rzeczywiście połączyć węzły do ​​siebie -

477
00:38:02,290 --> 00:38:04,750
do tych, które w rzeczywistości są one połączone - nie mam przejść i zrobić

478
00:38:04,750 --> 00:38:08,240
się, że wszystkie wartości null są tam w odpowiednich miejscach.

479
00:38:08,240 --> 00:38:15,630
>> Zaczynając od podstaw, wiem, że korzeń jest lewa dziecko jest 3.

480
00:38:15,630 --> 00:38:21,250
Wiem, że korzeń prawo dziecko jest 9.

481
00:38:21,250 --> 00:38:24,880
Po tym, tylko inne dziecko, które mi zostało martwić

482
00:38:24,880 --> 00:38:39,080
Dziecko 3 jest w prawo, w odległości 6.

483
00:38:39,080 --> 00:38:44,670
W tym momencie, to wszystko wygląda całkiem nieźle.

484
00:38:44,670 --> 00:38:54,210
Będziemy usunąć niektóre z tych linii.

485
00:38:54,210 --> 00:38:59,540
Teraz wszystko wygląda całkiem nieźle.

486
00:38:59,540 --> 00:39:04,240
Wróćmy do naszych specyfikacji i zobaczyć, co mamy dalej robić.

487
00:39:04,240 --> 00:39:07,610
>> W tym momencie musimy napisać wywołana funkcja "zawiera"

488
00:39:07,610 --> 00:39:14,150
z prototypem "bool zawiera (wartość int)".

489
00:39:14,150 --> 00:39:17,060
I ta zawiera funkcja będzie zwracać wartość true

490
00:39:17,060 --> 00:39:21,200
 jeśli drzewo wskazał nasz zmiennej globalnej głównym

491
00:39:21,200 --> 00:39:26,950
 zawiera wartość przekazywana do funkcji, a false w przeciwnym przypadku.

492
00:39:26,950 --> 00:39:29,000
Idziemy do przodu i zrobić.

493
00:39:29,000 --> 00:39:35,380
To będzie dokładnie tak, jak wyszukiwanie, że zrobiliśmy ręcznie na iPada tylko trochę wcześniej.

494
00:39:35,380 --> 00:39:40,130
Zróbmy Powiększ w trochę i przewiń w górę.

495
00:39:40,130 --> 00:39:43,130
Mamy zamiar umieścić tę funkcję tuż powyżej naszej głównej funkcji

496
00:39:43,130 --> 00:39:48,990
tak, że nie trzeba robić jakichkolwiek prototypowania.

497
00:39:48,990 --> 00:39:55,960
Więc, bool zawiera (wartość int).

498
00:39:55,960 --> 00:40:00,330
Proszę bardzo. Jest nasza deklaracja boilerplate.

499
00:40:00,330 --> 00:40:02,900
Wystarczy upewnić się, że będzie to skompilować,

500
00:40:02,900 --> 00:40:06,820
Mam zamiar iść do przodu i po prostu ustawić go równe return false.

501
00:40:06,820 --> 00:40:09,980
Teraz ta funkcja po prostu nie robić nic i zawsze podają, że

502
00:40:09,980 --> 00:40:14,010
wartość, którą szukasz nie jest w drzewie.

503
00:40:14,010 --> 00:40:16,280
>> W tym momencie, to chyba dobry pomysł -

504
00:40:16,280 --> 00:40:19,600
ponieważ napisaliśmy całą masę kodu, a my nawet nie próbował go jeszcze badania -

505
00:40:19,600 --> 00:40:22,590
aby upewnić się, że wszystko kompiluje.

506
00:40:22,590 --> 00:40:27,460
Istnieje kilka rzeczy, które musimy zrobić, aby upewnić się, że będzie to naprawdę skompilować.

507
00:40:27,460 --> 00:40:33,530
Najpierw sprawdź, czy używaliśmy żadnych funkcji w jakichkolwiek bibliotek, które nie zostały jeszcze zawarte.

508
00:40:33,530 --> 00:40:37,940
Funkcje używaliśmy do tej pory są malloc,

509
00:40:37,940 --> 00:40:43,310
a potem my także za pomocą tego typu - w ten niestandardowy typ zwany "bool' -

510
00:40:43,310 --> 00:40:45,750
który znajduje się w standardowym pliku bool nagłówka.

511
00:40:45,750 --> 00:40:53,250
Na pewno chcemy obejmują standardowe bool.h dla bool typu,

512
00:40:53,250 --> 00:40:59,230
i chcemy też # include standardowy lib.h dla standardowych bibliotek

513
00:40:59,230 --> 00:41:03,530
które obejmują malloc i wolne, i to wszystko.

514
00:41:03,530 --> 00:41:08,660
Więc, pomniejszyć, zamierzamy zamknąć.

515
00:41:08,660 --> 00:41:14,190
Spróbujmy i upewnić się, że to rzeczywiście nie kompilacji.

516
00:41:14,190 --> 00:41:18,150
Widzimy, że to robi, więc jesteśmy na dobrej drodze.

517
00:41:18,150 --> 00:41:22,990
>> Otwórzmy się binary_tree.c ponownie.

518
00:41:22,990 --> 00:41:34,530
Kompiluje. Chodźmy na dół i upewnij się, że możemy wstawić kilka telefonów do naszej funkcji zawiera -

519
00:41:34,530 --> 00:41:40,130
by upewnić się, że to jest wszystko dobrze.

520
00:41:40,130 --> 00:41:43,170
Na przykład, niektóre nie kiedy w naszym drzewie wyszukiwań wcześniej

521
00:41:43,170 --> 00:41:48,500
staraliśmy się spojrzeć wartości 6, 10 i 1, i wiedzieliśmy, że 6 było w drzewie,

522
00:41:48,500 --> 00:41:52,220
10 nie był w drzewie, i 1 w nie albo drzewa.

523
00:41:52,220 --> 00:41:57,230
Użyjmy te rozmowy przykładowe jako sposób, aby dowiedzieć się, czy

524
00:41:57,230 --> 00:41:59,880
Nasza funkcja zawiera działa.

525
00:41:59,880 --> 00:42:05,210
Aby to zrobić, zamierzam wykorzystać funkcję printf,

526
00:42:05,210 --> 00:42:10,280
i zamierzamy wydrukować wynik wywołania zawiera.

527
00:42:10,280 --> 00:42:13,280
Mam zamiar umieścić w ciąg "zawiera (% d) = bo

528
00:42:13,280 --> 00:42:20,470
 jedziemy do wtyczki w wartości, które będziemy szukać,

529
00:42:20,470 --> 00:42:27,130
i =% s \ n "i użyć jej jako naszego łańcucha formatu.

530
00:42:27,130 --> 00:42:30,720
Jesteśmy po prostu żeby zobaczyć - dosłownie wydrukować na ekranie -

531
00:42:30,720 --> 00:42:32,060
co wygląda jak wywołanie funkcji.

532
00:42:32,060 --> 00:42:33,580
W rzeczywistości nie jest to wywołanie funkcji.

533
00:42:33,580 --> 00:42:36,760
 To jest po prostu ciąg wyglądać jak wywołania funkcji.

534
00:42:36,760 --> 00:42:41,140
>> Teraz mamy zamiar podłączyć wartości.

535
00:42:41,140 --> 00:42:43,580
Będziemy próbować zawiera 6,

536
00:42:43,580 --> 00:42:48,340
i co wtedy będziemy robić tutaj jest użyć tego operatora trójskładnikowych.

537
00:42:48,340 --> 00:42:56,340
Zobaczmy - zawiera 6 - tak, teraz już zawarte 6 i jeśli zawiera 6 jest prawdziwe,

538
00:42:56,340 --> 00:43:01,850
Ciąg, który mamy zamiar wysłać do% s znak formatu

539
00:43:01,850 --> 00:43:04,850
będzie ciąg "true".

540
00:43:04,850 --> 00:43:07,690
Miejmy przewijania nad trochę.

541
00:43:07,690 --> 00:43:16,210
W przeciwnym razie, chcemy wysłać ciąg znaków "false", jeśli zawiera 6 zwraca false.

542
00:43:16,210 --> 00:43:19,730
To jest trochę głupkowaty wygląd, ale I rysunek Równie dobrze ilustrują

543
00:43:19,730 --> 00:43:23,780
co operator trójskładnikowych wygląda ponieważ nie widziałem go na chwilę.

544
00:43:23,780 --> 00:43:27,670
To będzie ładny, wygodny sposób, aby dowiedzieć się, czy nasza funkcja zawiera działa.

545
00:43:27,670 --> 00:43:30,040
Zamierzam przejść z powrotem na lewo,

546
00:43:30,040 --> 00:43:39,900
i mam zamiar skopiować i wkleić ten wiersz kilka razy.

547
00:43:39,900 --> 00:43:44,910
To zmieniło niektóre z tych wartości wokół,

548
00:43:44,910 --> 00:43:59,380
więc będzie 1, i to będzie 10.

549
00:43:59,380 --> 00:44:02,480
>> W tym momencie mamy ładny funkcja zawiera.

550
00:44:02,480 --> 00:44:06,080
Mamy kilka testów i zobaczymy czy to wszystko działa.

551
00:44:06,080 --> 00:44:08,120
W tym momencie mamy napisane trochę więcej kodu.

552
00:44:08,120 --> 00:44:13,160
Czas rzucić się i upewnić się, że wszystko nadal kompiluje.

553
00:44:13,160 --> 00:44:20,360
Zamknij się, a teraz niech spróbuj drzewo binarne ponownie.

554
00:44:20,360 --> 00:44:22,260
Cóż, wygląda na to, że mamy błąd,

555
00:44:22,260 --> 00:44:26,930
I mamy to wyraźnie deklarując funkcję biblioteczną printf.

556
00:44:26,930 --> 00:44:39,350
Wygląda na to, musimy iść i # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
A z tym, wszystko powinno się skompilować. Jesteśmy dobrze.

558
00:44:45,350 --> 00:44:50,420
Teraz spróbuj uruchomić binarne drzewo i zobaczyć, co się dzieje.

559
00:44:50,420 --> 00:44:53,520
Oto jesteśmy. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
i widzimy, że, jak się spodziewaliśmy -

561
00:44:55,190 --> 00:44:56,910
ponieważ nie zawiera jeszcze wdrożone,

562
00:44:56,910 --> 00:44:59,800
lub raczej, mamy po prostu w zamian fałszywe -

563
00:44:59,800 --> 00:45:03,300
widzimy, że to jest po prostu powrót false dla wszystkich z nich,

564
00:45:03,300 --> 00:45:06,180
tak, że wszystko pracuje na ogół dość dobrze.

565
00:45:06,180 --> 00:45:11,860
>> Wróćmy i rzeczywiście wdrożyć zawiera w tym momencie.

566
00:45:11,860 --> 00:45:17,490
Idę do przewijania, powiększania i -

567
00:45:17,490 --> 00:45:22,330
pamiętaj, że algorytm stosowany było to, że rozpoczął się korzenia

568
00:45:22,330 --> 00:45:28,010
, a następnie w każdym węźle spotykamy, mamy porównanie,

569
00:45:28,010 --> 00:45:32,380
i na podstawie tego porównania, że ​​albo w lewo przejść dziecka lub prawej dziecka.

570
00:45:32,380 --> 00:45:39,670
To będzie bardzo podobny do kodu binarnego wyszukiwania, które pisaliśmy wcześniej w tym okresie.

571
00:45:39,670 --> 00:45:47,810
Kiedy zaczynamy, wiemy, że chcemy trzymać się aktualnego węzła

572
00:45:47,810 --> 00:45:54,050
że mamy do czynienia, a bieżący węzeł ma być inicjowane węzła głównego.

573
00:45:54,050 --> 00:45:56,260
A teraz mamy zamiar iść dalej w drzewie,

574
00:45:56,260 --> 00:45:58,140
i pamiętaj, że nasz stan zatrzymania -

575
00:45:58,140 --> 00:46:01,870
 kiedy faktycznie przepracowanych poprzez przykład ręcznie -

576
00:46:01,870 --> 00:46:03,960
było, gdy spotkaliśmy null węzła

577
00:46:03,960 --> 00:46:05,480
nie wtedy, gdy patrzyliśmy na pustym dzieckiem

578
00:46:05,480 --> 00:46:09,620
ale kiedy faktycznie przeniósł się do węzła w drzewie

579
00:46:09,620 --> 00:46:12,640
i stwierdził, że jesteśmy na pustym węzłem.

580
00:46:12,640 --> 00:46:20,720
Jedziemy do iteracji, aż dyskusja nie jest równa null.

581
00:46:20,720 --> 00:46:22,920
I co my teraz zrobimy?

582
00:46:22,920 --> 00:46:31,610
Będziemy sprawdzać, czy (bież -> wartość value ==)

583
00:46:31,610 --> 00:46:35,160
to wiemy, że mamy rzeczywiście znaleźć węzeł, że szukasz.

584
00:46:35,160 --> 00:46:40,450
Więc tutaj, możemy powrócić true.

585
00:46:40,450 --> 00:46:49,830
W przeciwnym razie, chcemy zobaczyć, czy jest mniejsza niż wartość.

586
00:46:49,830 --> 00:46:53,850
Jeśli bieżący węzeł wartość jest mniejsza od wartości szukamy,

587
00:46:53,850 --> 00:46:57,280
będziemy poruszać się w prawo.

588
00:46:57,280 --> 00:47:10,600
Więc dyskusja dyskusja = -> right_child, a inaczej, będziemy poruszać się w lewo.

589
00:47:10,600 --> 00:47:17,480
poprz = cur -> left_child;. Całkiem proste.

590
00:47:17,480 --> 00:47:22,830
>> Prawdopodobnie rozpoznaje pętlę, która wygląda bardzo podobnie do tego z

591
00:47:22,830 --> 00:47:27,580
Wyszukiwanie binarne wcześniej w okresie, z wyjątkiem wtedy mamy do czynienia z niskim, średnim i wysokim.

592
00:47:27,580 --> 00:47:30,000
Tutaj po prostu trzeba spojrzeć na wartości bieżącej,

593
00:47:30,000 --> 00:47:31,930
więc jest ładne i proste.

594
00:47:31,930 --> 00:47:34,960
Upewnijmy ten kod działa.

595
00:47:34,960 --> 00:47:42,780
Po pierwsze, upewnij się, że kompiluje. Wygląda tak, jak to robi.

596
00:47:42,780 --> 00:47:47,920
Spróbujmy uruchomić.

597
00:47:47,920 --> 00:47:50,160
I rzeczywiście, drukuje się wszystko, czego oczekiwać.

598
00:47:50,160 --> 00:47:54,320
Okazuje 6 w drzewie, nie znajdzie 10 bo 10 nie jest w drzewie,

599
00:47:54,320 --> 00:47:57,740
i nie znajdzie 1 albo ponieważ 1 nie jest również w drzewie.

600
00:47:57,740 --> 00:48:01,420
Fajnych rzeczy.

601
00:48:01,420 --> 00:48:04,470
>> Dobrze. Wróćmy do naszych specyfikacji i zobaczyć co dalej.

602
00:48:04,470 --> 00:48:07,990
Teraz chce dodać trochę więcej węzłów naszego drzewa.

603
00:48:07,990 --> 00:48:11,690
Chce dodać 5, 2 i 8, i upewnij się, że nasza zawiera kod

604
00:48:11,690 --> 00:48:13,570
nadal działa zgodnie z oczekiwaniami.

605
00:48:13,570 --> 00:48:14,900
Chodźmy zrobić.

606
00:48:14,900 --> 00:48:19,430
W tym miejscu, zamiast robić to irytujące kopiuj i wklej ponownie

607
00:48:19,430 --> 00:48:23,770
niech napisać funkcję, aby rzeczywiście utworzyć węzeł.

608
00:48:23,770 --> 00:48:27,740
Jeśli będziemy przewijać całą drogę do main, widzimy, że robiliśmy to

609
00:48:27,740 --> 00:48:31,210
bardzo podobny kod w kółko za każdym razem, że chcemy utworzyć węzeł.

610
00:48:31,210 --> 00:48:39,540
>> Miejmy napisać funkcję, która będzie faktycznie zbudować węzeł dla nas i zwrócić.

611
00:48:39,540 --> 00:48:41,960
Mam zamiar nazwać build_node.

612
00:48:41,960 --> 00:48:45,130
Zamierzam zbudować węzeł o określonej wartości.

613
00:48:45,130 --> 00:48:51,040
Powiększanie tutaj.

614
00:48:51,040 --> 00:48:56,600
Pierwszą rzeczą, jaką zrobię faktycznie stworzyć przestrzeń dla węzła na stercie.

615
00:48:56,600 --> 00:49:05,400
Tak więc, węzeł * n = malloc (sizeof (node)); n - wartość> = wartość;

616
00:49:05,400 --> 00:49:14,960
i tu mam zamiar zainicjować wszystkie pola się odpowiednie wartości.

617
00:49:14,960 --> 00:49:22,500
A na samym końcu, ponownie nasz węzeł.

618
00:49:22,500 --> 00:49:28,690
Dobrze. Należy zwrócić uwagę, że ta funkcja jest tu

619
00:49:28,690 --> 00:49:34,320
będzie zwracają wskaźnik do pamięci, która została przydzielona sterty.

620
00:49:34,320 --> 00:49:38,880
Co jest ładne o to, że ten węzeł już teraz -

621
00:49:38,880 --> 00:49:42,420
musimy zadeklarować ją na stercie, ponieważ jeśli zadeklarował go na stos

622
00:49:42,420 --> 00:49:45,050
nie będzie w stanie to zrobić w funkcji takich jak to.

623
00:49:45,050 --> 00:49:47,690
Że pamięć wypadnie z zakresu

624
00:49:47,690 --> 00:49:51,590
i będzie nieważna w przypadku próby dostępu do go później.

625
00:49:51,590 --> 00:49:53,500
Ponieważ jesteśmy deklarowania sterty przydzielonej pamięci,

626
00:49:53,500 --> 00:49:55,830
będziemy musieli zadbać o uwolnienie go później

627
00:49:55,830 --> 00:49:58,530
dla naszego programu nie przeciekać żadnej pamięci.

628
00:49:58,530 --> 00:50:01,270
Byliśmy punting na to wszystko inne w kodzie

629
00:50:01,270 --> 00:50:02,880
tylko dla uproszczenia w momencie,

630
00:50:02,880 --> 00:50:05,610
ale jeśli kiedykolwiek napisać funkcję, który wygląda tak

631
00:50:05,610 --> 00:50:10,370
gdzie masz - niektórzy nazywają to malloc lub realloc wewnątrz -

632
00:50:10,370 --> 00:50:14,330
Aby upewnić się, że można umieścić jakiś komentarz tutaj, który mówi

633
00:50:14,330 --> 00:50:29,970
Hej, wiesz, zwraca sterty przydzielone węzeł zainicjowany z wartością Przekazana-in.

634
00:50:29,970 --> 00:50:33,600
A potem chcesz się upewnić, że można umieścić w jakiejś notatce, która mówi

635
00:50:33,600 --> 00:50:41,720
Rozmówca musi uwolnić zwrócony pamięć.

636
00:50:41,720 --> 00:50:45,450
W ten sposób, jeśli ktoś kiedykolwiek idzie i korzysta z tej funkcji,

637
00:50:45,450 --> 00:50:48,150
oni wiedzą, że to co oni wrócić z tej funkcji

638
00:50:48,150 --> 00:50:50,870
w pewnym momencie musi być uwolniony.

639
00:50:50,870 --> 00:50:53,940
>> Zakładając, że wszystko jest dobrze i dobre tutaj,

640
00:50:53,940 --> 00:51:02,300
możemy iść w dół do naszego kodu i zastąpić wszystkie z tych linii tutaj

641
00:51:02,300 --> 00:51:05,410
z połączeniami z naszej funkcji budowania węzła.

642
00:51:05,410 --> 00:51:08,170
Zróbmy to naprawdę szybko.

643
00:51:08,170 --> 00:51:15,840
Jedna część, że nie idziemy do zastąpienia jest ta część na dole

644
00:51:15,840 --> 00:51:18,520
na dnie, gdzie rzeczywiście DRUTU węzły wskazać siebie

645
00:51:18,520 --> 00:51:21,030
dlatego, że nie możemy zrobić w naszej funkcji.

646
00:51:21,030 --> 00:51:37,400
Ale zróbmy root = build_node (7); node * trzy = build_node (3);

647
00:51:37,400 --> 00:51:47,980
node * sześć = build_node (6); node * dziewięć = build_node (9),.

648
00:51:47,980 --> 00:51:52,590
A teraz, chcieliśmy również dodać węzły do ​​-

649
00:51:52,590 --> 00:52:03,530
node * pięć = build_node (5); node * osiem = build_node (8);

650
00:52:03,530 --> 00:52:09,760
i to, co było drugim węźle? Zobaczymy tutaj. Chcieliśmy również dodać 2 -

651
00:52:09,760 --> 00:52:20,280
node * dwa = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Dobrze. W tym momencie wiemy, że mamy do 7, 3, 9 oraz 6

653
00:52:26,850 --> 00:52:30,320
wszystkie podłączane odpowiednio, ale co 5, 8, a 2?

654
00:52:30,320 --> 00:52:33,550
Aby utrzymać wszystko w odpowiedniej kolejności,

655
00:52:33,550 --> 00:52:39,230
wiemy, że prawo dziecka trzy jest 6.

656
00:52:39,230 --> 00:52:40,890
Tak więc, jeśli mamy zamiar dodać 5,

657
00:52:40,890 --> 00:52:46,670
5 należy również po prawej stronie z drzewa, które jest źródłem 3,

658
00:52:46,670 --> 00:52:50,440
tak 5 należy jak lewy dziecka 6.

659
00:52:50,440 --> 00:52:58,650
Możemy to zrobić, mówiąc, sześć -> left_child = pięć;

660
00:52:58,650 --> 00:53:10,790
, a następnie, jak 8 należy lewej dziecko 9, więc dziewięć -> left_child = osiem;

661
00:53:10,790 --> 00:53:22,190
a następnie 2 jest lewym dzieckiem 3, więc możemy to zrobić tutaj - ci -> left_child = dwa,.

662
00:53:22,190 --> 00:53:27,730
Jeśli nie nadążam wraz z tym, proponuję wyciągnąć go z siebie.

663
00:53:27,730 --> 00:53:35,660
>> Dobrze. Ratujmy to. Wyjdźmy i upewnij się kompiluje,

664
00:53:35,660 --> 00:53:40,760
a następnie możemy dodać w naszych zawiera połączeń.

665
00:53:40,760 --> 00:53:44,120
Wygląda na to wszystko nadal kompiluje.

666
00:53:44,120 --> 00:53:51,790
Chodźmy i dodać niektóre zawiera połączeń.

667
00:53:51,790 --> 00:53:59,640
Ponownie, mam zamiar zrobić trochę kopiowania i wklejania.

668
00:53:59,640 --> 00:54:15,860
Teraz szukać 5, 8 i 2. Dobrze.

669
00:54:15,860 --> 00:54:28,330
Upewnijmy się, że to wszystko wygląda dobrze, spokojnie. Great! Zapisz i zamknij.

670
00:54:28,330 --> 00:54:33,220
Teraz zróbmy, kompilacji i teraz niech uruchomić.

671
00:54:33,220 --> 00:54:37,540
Z wyników, wygląda to wszystko działa po prostu miło i dobrze.

672
00:54:37,540 --> 00:54:41,780
Great! Więc teraz mamy nasze obejmuje funkcje napisane.

673
00:54:41,780 --> 00:54:46,160
Idźmy dalej i rozpocząć pracę na jak wstawić węzły w drzewie

674
00:54:46,160 --> 00:54:50,000
ponieważ, jak robimy to teraz, rzeczy nie są bardzo ładne.

675
00:54:50,000 --> 00:54:52,280
>> Jeśli wrócimy do specyfikacji,

676
00:54:52,280 --> 00:55:00,540
prosi nas napisać funkcję o nazwie wstawić - znowu, wracając bool

677
00:55:00,540 --> 00:55:04,400
do tego, czy moglibyśmy wstawić węzeł na drzewie -

678
00:55:04,400 --> 00:55:07,710
a następnie wartość wstawić do drzewa jest określona jako

679
00:55:07,710 --> 00:55:11,060
Jedynym argumentem dla naszej funkcji wstawiania.

680
00:55:11,060 --> 00:55:18,180
Wrócimy prawda czy możemy rzeczywiście wstawić wartość węzła zawierającego do drzewa,

681
00:55:18,180 --> 00:55:20,930
co oznacza, że ​​jeden, miał mało pamięci

682
00:55:20,930 --> 00:55:24,840
a dwa, że ​​węzeł nie istnieje w drzewie, ponieważ -

683
00:55:24,840 --> 00:55:32,170
pamiętaj, że nie będziemy mieć zduplikowane wartości w drzewie, tak aby rzeczy proste.

684
00:55:32,170 --> 00:55:35,590
Dobrze. Powrót do kodu.

685
00:55:35,590 --> 00:55:44,240
Otwórz. Powiększyć trochę, a następnie przewiń w dół.

686
00:55:44,240 --> 00:55:47,220
Postawmy funkcję wstawić tuż nad zawiera.

687
00:55:47,220 --> 00:55:56,360
Ponownie, to będzie się nazywać bool insert (wartość int).

688
00:55:56,360 --> 00:56:01,840
Daj mu trochę więcej miejsca, a następnie, jako domyślny,

689
00:56:01,840 --> 00:56:08,870
postawmy w zamian fałszywe na samym końcu.

690
00:56:08,870 --> 00:56:22,620
Teraz na dnie, idziemy dalej i zamiast ręcznie budowy węzłów

691
00:56:22,620 --> 00:56:27,900
w głównym sami i okablowanie je wskazać na siebie jak robimy,

692
00:56:27,900 --> 00:56:30,600
będziemy polegać na naszej funkcji insert to zrobić.

693
00:56:30,600 --> 00:56:35,510
Nie będzie polegać na naszej funkcji insert zbudować całe drzewo od podstaw jeszcze,

694
00:56:35,510 --> 00:56:39,970
ale raczej będziemy się pozbyć tych linii - we'll zakomentować tych linii -

695
00:56:39,970 --> 00:56:43,430
które budują węzły 5, 8 i 2.

696
00:56:43,430 --> 00:56:55,740
I zamiast, będziemy wstawiać połączenia do naszej funkcji płytek

697
00:56:55,740 --> 00:57:01,280
aby upewnić się, że to faktycznie działa.

698
00:57:01,280 --> 00:57:05,840
Jedziemy.

699
00:57:05,840 --> 00:57:09,300
>> Teraz mamy wykomentowane te linie.

700
00:57:09,300 --> 00:57:13,700
Mamy tylko 7, 3, 9 i 6 w naszym drzewie w tym momencie.

701
00:57:13,700 --> 00:57:18,870
Aby upewnić się, że to wszystko działa,

702
00:57:18,870 --> 00:57:25,050
możemy pomniejszyć, aby nasze drzewa binarnego,

703
00:57:25,050 --> 00:57:30,750
uruchom go, a widzimy, że zawiera teraz nam mówi, że jesteśmy całkowicie w prawo -

704
00:57:30,750 --> 00:57:33,110
5, 8 i 2 nie są już w drzewie.

705
00:57:33,110 --> 00:57:37,960
Wróć do kodu,

706
00:57:37,960 --> 00:57:41,070
i jak mamy zamiar włożyć?

707
00:57:41,070 --> 00:57:46,290
Pamiętaj, co robiliśmy, kiedy byliśmy naprawdę wstawienie 5, 8 i 2 wcześniej.

708
00:57:46,290 --> 00:57:50,100
Graliśmy w tę grę Plinko gdzie zaczęliśmy u nasady,

709
00:57:50,100 --> 00:57:52,780
zszedł jednego drzewa przez jeden po drugim

710
00:57:52,780 --> 00:57:54,980
aż znaleźliśmy odpowiednią lukę,

711
00:57:54,980 --> 00:57:57,570
a następnie połączone w węźle w odpowiednim miejscu.

712
00:57:57,570 --> 00:57:59,480
Mamy zamiar zrobić to samo.

713
00:57:59,480 --> 00:58:04,070
Jest to w zasadzie jak pisanie kodu, który użyliśmy w zawiera funkcję

714
00:58:04,070 --> 00:58:05,910
w miejsce, gdzie znajduje się węzeł powinny być,

715
00:58:05,910 --> 00:58:10,560
i jesteśmy po prostu będzie wstawić węzeł tam.

716
00:58:10,560 --> 00:58:17,000
Zacznijmy robić.

717
00:58:17,000 --> 00:58:24,200
>> Więc mamy węzeł * Cur = root, jesteśmy po prostu będzie śledzić zawiera kod

718
00:58:24,200 --> 00:58:26,850
dopóki nie okaże się, że nie całkiem dla nas pracować.

719
00:58:26,850 --> 00:58:32,390
Mamy zamiar przejść przez drzewa, podczas gdy bieżący element nie jest pusty,

720
00:58:32,390 --> 00:58:45,280
i jeśli okaże się, że dyskusja ma wartość równą wartości, które staramy się wprowadzić -

721
00:58:45,280 --> 00:58:49,600
także, to jest jeden z tych przypadków, w których nie można faktycznie wprowadzić węzeł

722
00:58:49,600 --> 00:58:52,730
do drzewa, bo to oznacza, że ​​mamy duplikaty wartości.

723
00:58:52,730 --> 00:58:59,010
Tutaj jesteśmy rzeczywiście będzie return false.

724
00:58:59,010 --> 00:59:08,440
Teraz też, jeżeli bież wartość jest mniejsza niż wartość

725
00:59:08,440 --> 00:59:10,930
teraz wiemy, że możemy przejść do prawej

726
00:59:10,930 --> 00:59:17,190
 ponieważ wartość należy w prawej połowie drzewa Cur.

727
00:59:17,190 --> 00:59:30,110
W przeciwnym razie, będziemy poruszać się w lewo.

728
00:59:30,110 --> 00:59:37,980
To w zasadzie nasze obejmuje funkcje tam.

729
00:59:37,980 --> 00:59:41,820
>> W tym momencie, po zakończeniu tego pętlę while,

730
00:59:41,820 --> 00:59:47,350
nasz wskaźnik bież zostanie skierowany na null

731
00:59:47,350 --> 00:59:51,540
Jeśli funkcja nie została już zwrócona.

732
00:59:51,540 --> 00:59:58,710
Mamy w związku z tym o CUR w miejscu, gdzie chcemy wstawić nowy węzeł.

733
00:59:58,710 --> 01:00:05,210
Co pozostaje do zrobienia jest faktycznie zbudować nowy węzeł,

734
01:00:05,210 --> 01:00:08,480
co możemy zrobić dość łatwo.

735
01:00:08,480 --> 01:00:14,930
Możemy użyć naszej super przydatną funkcję węzła kompilacji,

736
01:00:14,930 --> 01:00:17,210
i coś, czego nie zrobiliśmy wcześniej -

737
01:00:17,210 --> 01:00:21,400
po prostu rodzaj uznał za pewnik, ale teraz będziemy robić, żeby upewnić się -

738
01:00:21,400 --> 01:00:27,130
będziemy przetestować, aby upewnić się, że wartość zwracana przez nowego węzła był rzeczywiście

739
01:00:27,130 --> 01:00:33,410
not null, ponieważ nie chcemy, aby uruchomić dostęp do tej pamięci, jeśli jest null.

740
01:00:33,410 --> 01:00:39,910
Możemy sprawdzić, aby upewnić się, że nowy węzeł nie jest równa null.

741
01:00:39,910 --> 01:00:42,910
Albo zamiast tego możemy po prostu sprawdzić, czy to rzeczywiście jest pusta,

742
01:00:42,910 --> 01:00:52,120
i jeśli jest pusta, to możemy po prostu return false wcześnie.

743
01:00:52,120 --> 01:00:59,090
>> W tym momencie musimy podłączyć nowy węzeł w jego odpowiednim miejscu w drzewie.

744
01:00:59,090 --> 01:01:03,510
Jeśli spojrzymy na główne i gdzie byliśmy faktycznie okablowanie w wartościach przed,

745
01:01:03,510 --> 01:01:08,470
widzimy, że sposób, w jaki to robimy, kiedy chcieliśmy umieścić 3 w drzewie

746
01:01:08,470 --> 01:01:11,750
został nam dostęp lewego dziecka korzenia.

747
01:01:11,750 --> 01:01:14,920
Kiedy przygotowaliśmy 9 w drzewie, mieliśmy dostęp do odpowiedniego dziecka korzenia.

748
01:01:14,920 --> 01:01:21,030
Musieliśmy mieć wskaźnik do rodzica, aby umieścić nową wartość do drzewa.

749
01:01:21,030 --> 01:01:24,430
Przewijanie z powrotem włożyć, że nie będzie dość pracy tutaj

750
01:01:24,430 --> 01:01:27,550
ponieważ nie mamy wskaźnik nadrzędny.

751
01:01:27,550 --> 01:01:31,650
Co chcemy w stanie nie jest, w tym momencie,

752
01:01:31,650 --> 01:01:37,080
sprawdzić wartość rodziców i zobaczyć - dobrze, Boże,

753
01:01:37,080 --> 01:01:41,990
Jeśli rodzic ma wartość mniejszą od aktualnej wartości,

754
01:01:41,990 --> 01:01:54,440
to rodzic ma rację dziecko powinno być nowy węzeł;

755
01:01:54,440 --> 01:02:07,280
inaczej, wniosek rodziców lewej dziecko powinno być nowy węzeł.

756
01:02:07,280 --> 01:02:10,290
Ale nie mamy ten wskaźnik nadrzędny dość jeszcze.

757
01:02:10,290 --> 01:02:15,010
>> Aby je zdobyć, jesteśmy rzeczywiście będzie musiał śledzić go jak przejść przez drzewa

758
01:02:15,010 --> 01:02:18,440
i znaleźć odpowiednie miejsce w naszej pętli powyżej.

759
01:02:18,440 --> 01:02:26,840
Możemy to zrobić poprzez przewijanie z powrotem do początku naszej funkcji płytek

760
01:02:26,840 --> 01:02:32,350
i śledzenie innej zmiennej wskaźnik zwany rodzica.

761
01:02:32,350 --> 01:02:39,340
Mamy zamiar ustawić go równa null początkowo

762
01:02:39,340 --> 01:02:43,640
, a następnie za każdym razem przejść przez drzewa,

763
01:02:43,640 --> 01:02:51,540
zamierzamy ustawić wskaźnik nadrzędny dopasować bieżący wskaźnik.

764
01:02:51,540 --> 01:02:59,140
Ustaw rodzica równe Cur.

765
01:02:59,140 --> 01:03:02,260
W ten sposób, za każdym razem przejść,

766
01:03:02,260 --> 01:03:05,550
jedziemy do zapewnienia, że ​​prąd pobiera wskaźnik zwiększany

767
01:03:05,550 --> 01:03:12,640
wskaźnik rodzic następująco - po prostu o jeden poziom wyżej niż obecny wskaźnik w drzewie.

768
01:03:12,640 --> 01:03:17,370
Że wszystko wygląda całkiem nieźle.

769
01:03:17,370 --> 01:03:22,380
>> Myślę, że jedyną rzeczą, która będziemy chcieli ustawić to budować węzła powracającego null.

770
01:03:22,380 --> 01:03:25,380
W celu uzyskania zbudować węzeł faktycznie pomyślnie powrócić null,

771
01:03:25,380 --> 01:03:31,060
musimy zmodyfikować ten kod,

772
01:03:31,060 --> 01:03:37,270
bo tu, nigdy nie testowane, aby upewnić się, że malloc zwróciło ważny wskaźnik.

773
01:03:37,270 --> 01:03:53,390
Tak więc, jeśli (n = NULL!), A następnie -

774
01:03:53,390 --> 01:03:55,250
jeśli malloc zwróciło ważny wskaźnik, wtedy będziemy go zainicjować;

775
01:03:55,250 --> 01:04:02,540
inaczej, po prostu wrócić i że zakończy się powrotem null dla nas.

776
01:04:02,540 --> 01:04:13,050
Teraz wszystko wygląda całkiem nieźle. Upewnijmy się, to rzeczywiście kompiluje.

777
01:04:13,050 --> 01:04:22,240
Producent drzewa binarnego, i oh, mamy pewne rzeczy się dzieje.

778
01:04:22,240 --> 01:04:29,230
>> Mamy niejawna deklaracja funkcji zbudować węzeł.

779
01:04:29,230 --> 01:04:31,950
Ponownie, z tych kompilatorów, mamy zamiar rozpocząć na szczycie.

780
01:04:31,950 --> 01:04:36,380
Co to może oznaczać to, że dzwonię zbudować węzeł przed mam faktycznie zadeklarował go.

781
01:04:36,380 --> 01:04:37,730
Wróćmy do kodu bardzo szybko.

782
01:04:37,730 --> 01:04:43,510
Przewiń w dół, a na pewno wystarczy, moja funkcja insert jest zadeklarowana

783
01:04:43,510 --> 01:04:47,400
powyżej funkcji budowania węzła

784
01:04:47,400 --> 01:04:50,070
ale staram się używać zbudować węzeł wewnątrz wkładki.

785
01:04:50,070 --> 01:05:06,610
Mam zamiar iść i skopiuj - a następnie wklej węzła drogi Funkcja budowania tu na górze.

786
01:05:06,610 --> 01:05:11,750
W ten sposób, mam nadzieję, że będzie działać. Dajmy to jeszcze raz.

787
01:05:11,750 --> 01:05:18,920
Teraz wszystko kompiluje. Wszystko jest dobrze.

788
01:05:18,920 --> 01:05:21,640
>> Ale w tym momencie, nie mamy naprawdę nazywa naszą funkcję wstawiania.

789
01:05:21,640 --> 01:05:26,510
Wiemy tylko, że kompiluje, więc chodźmy i umieścić kilka połączeń w.

790
01:05:26,510 --> 01:05:28,240
Zróbmy to w naszej głównej funkcji.

791
01:05:28,240 --> 01:05:32,390
Tutaj, wypowiedziało się 5, 8 i 2,

792
01:05:32,390 --> 01:05:36,680
a następnie nie podłączać je tutaj.

793
01:05:36,680 --> 01:05:41,640
Zróbmy niektóre zaproszenia wstawić,

794
01:05:41,640 --> 01:05:46,440
i niech to też używał tego rodzaju rzeczy, które używane

795
01:05:46,440 --> 01:05:52,810
kiedy zrobiliśmy te printf połączeń, aby upewnić się, że wszystko udało się prawidłowo włożona.

796
01:05:52,810 --> 01:06:00,550
Mam zamiar skopiować i wkleić,

797
01:06:00,550 --> 01:06:12,450
i zamiast zawiera zamierzamy zrobić wkładkę.

798
01:06:12,450 --> 01:06:30,140
I zamiast 6, 10 i 1, będziemy używać 5, 8 i 2.

799
01:06:30,140 --> 01:06:37,320
Powinno to wstawić 5, 8 i 2 do drzewa.

800
01:06:37,320 --> 01:06:44,050
Skompilować. Wszystko jest dobrze. Teraz będziemy faktycznie uruchomić nasz program.

801
01:06:44,050 --> 01:06:47,330
>> Wszystko wróciło false.

802
01:06:47,330 --> 01:06:53,830
Tak, 5, 8 i 2 nie wychodzi, i wygląda na to zawiera nie znaleźli ich albo.

803
01:06:53,830 --> 01:06:58,890
Co się dzieje? Miejmy pomniejszyć.

804
01:06:58,890 --> 01:07:02,160
Pierwszym problemem było to, że wydawało się, insert return false,

805
01:07:02,160 --> 01:07:08,750
i wygląda na to, że to dlatego, że zostawiliśmy w naszym powrocie rozmowy fałszywej

806
01:07:08,750 --> 01:07:14,590
i nigdy tak naprawdę zwróciło true.

807
01:07:14,590 --> 01:07:17,880
Możemy ustawić, że w górę.

808
01:07:17,880 --> 01:07:25,290
Drugim problemem jest to, teraz, nawet jeśli robimy - zapisać to, zamknij to

809
01:07:25,290 --> 01:07:34,530
uruchom make znowu nie skompilować, a następnie uruchomić go -

810
01:07:34,530 --> 01:07:37,670
widzimy, że coś tu się stało.

811
01:07:37,670 --> 01:07:42,980
5, 8 i 2 nie zostały nadal obecny w drzewie.

812
01:07:42,980 --> 01:07:44,350
Więc, co się dzieje?

813
01:07:44,350 --> 01:07:45,700
>> Rzućmy okiem na to w kodzie.

814
01:07:45,700 --> 01:07:49,790
Zobaczymy, czy uda nam się to.

815
01:07:49,790 --> 01:07:57,940
Zaczynamy rodzic nie jest null.

816
01:07:57,940 --> 01:07:59,510
Ustawiamy aktualny wskaźnik równy wskaźnika głównego,

817
01:07:59,510 --> 01:08:04,280
i będziemy pracować naszą drogę w dół drzewa.

818
01:08:04,280 --> 01:08:08,650
Jeśli bieżący węzeł nie jest pusta, to wiemy, że możemy przenieść w dół trochę.

819
01:08:08,650 --> 01:08:12,330
Wyznaczamy naszą wskaźnik nadrzędny równa obecnej wskaźnik,

820
01:08:12,330 --> 01:08:15,420
Sprawdziłem wartość - jeśli wartości są takie same, wróciliśmy false.

821
01:08:15,420 --> 01:08:17,540
Jeśli wartości są mniej przenieśliśmy się do prawa;

822
01:08:17,540 --> 01:08:20,399
inaczej, przesunął się na lewo.

823
01:08:20,399 --> 01:08:24,220
Następnie budujemy węzeł. Będę powiększyć trochę.

824
01:08:24,220 --> 01:08:31,410
I tutaj mamy zamiar spróbować podłączyć się wartości na ten sam.

825
01:08:31,410 --> 01:08:37,250
Co się dzieje? Zobaczmy, czy ewentualnie Valgrind może dać nam wskazówkę.

826
01:08:37,250 --> 01:08:43,910
>> Lubię używać tylko dlatego Valgrind Valgrind naprawdę szybko biegnie

827
01:08:43,910 --> 01:08:46,729
oraz informuje, czy są jakieś błędy pamięci.

828
01:08:46,729 --> 01:08:48,300
Kiedy uruchomić Valgrind na kodzie,

829
01:08:48,300 --> 01:08:55,859
jak widać prawo hit here--Valgrind./binary_tree--and wejść.

830
01:08:55,859 --> 01:09:03,640
Widać, że nie ma żadnego błędu pamięci, więc wygląda na to, że wszystko jest w porządku, tak daleko.

831
01:09:03,640 --> 01:09:07,529
Mamy pewne przecieki pamięci, którą znamy, bo nie jesteśmy

832
01:09:07,529 --> 01:09:08,910
dzieje się uwolnić żadnego z naszych węzłów.

833
01:09:08,910 --> 01:09:13,050
Spróbujmy uruchomiony GDB zobaczyć, co się właściwie dzieje.

834
01:09:13,050 --> 01:09:20,010
Zrobimy gdb. / Binary_tree. To zyski w górze dobrze.

835
01:09:20,010 --> 01:09:23,670
Ustawmy punkt załamania na wkładce.

836
01:09:23,670 --> 01:09:28,600
Przyjrzyjmy się.

837
01:09:28,600 --> 01:09:31,200
Wygląda na to, nigdy tak naprawdę nazywa się wkładka.

838
01:09:31,200 --> 01:09:39,410
To wygląda jak problem był tak, że gdy zmienił tutaj w main -

839
01:09:39,410 --> 01:09:44,279
wszystkie z tych połączeń od printf zawiera -

840
01:09:44,279 --> 01:09:56,430
Nigdy nie zmieniły one wywołać wkładkę.

841
01:09:56,430 --> 01:10:01,660
Teraz spróbować. Miejmy skompilować.

842
01:10:01,660 --> 01:10:09,130
Wszystko wygląda dobrze tam. Teraz spróbuj uruchomić go, zobacz co się dzieje.

843
01:10:09,130 --> 01:10:13,320
W porządku! Wszystko wygląda całkiem dobre.

844
01:10:13,320 --> 01:10:18,130
>> Ostatnią rzeczą, aby myśleć o to, czy są jakieś przypadki krawędzi do tej wstawki?

845
01:10:18,130 --> 01:10:23,170
I okazuje się, że dobrze, że jeden przypadek krawędź jest zawsze ciekawe, aby myśleć o

846
01:10:23,170 --> 01:10:26,250
jest, co się dzieje, jeśli drzewo jest puste i wywołać tę funkcję wstawić?

847
01:10:26,250 --> 01:10:30,330
To będzie działać? Cóż, spróbować.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Sposób będziemy testować to, idziemy na dół do naszej głównej funkcji,

850
01:10:35,810 --> 01:10:41,690
i zamiast okablowania tych węzłów aż takiego,

851
01:10:41,690 --> 01:10:56,730
jesteśmy po prostu będzie do ustosunkowania się całą rzecz,

852
01:10:56,730 --> 01:11:02,620
i zamiast okablowanie węzłów siebie,

853
01:11:02,620 --> 01:11:09,400
rzeczywiście możemy pójść dalej i usunąć wszystko.

854
01:11:09,400 --> 01:11:17,560
Będziemy robić wszystko wezwanie do wstawienia.

855
01:11:17,560 --> 01:11:49,020
Więc zróbmy - zamiast 5, 8 i 2, idziemy wstawić 7, 3 i 9.

856
01:11:49,020 --> 01:11:58,440
A potem my także chcemy wstawić 6, jak również.

857
01:11:58,440 --> 01:12:05,190
Zapisz. Quit. Producent drzewa binarnego.

858
01:12:05,190 --> 01:12:08,540
To wszystko kompiluje.

859
01:12:08,540 --> 01:12:10,320
Możemy po prostu uruchomić go jak jest i zobaczyć, co się dzieje,

860
01:12:10,320 --> 01:12:12,770
ale to również będzie bardzo ważne, aby upewnić się, że

861
01:12:12,770 --> 01:12:14,740
nie mamy żadnych błędów pamięci,

862
01:12:14,740 --> 01:12:16,840
ponieważ jest to jeden z naszych przypadków krawędzi, które znamy temat.

863
01:12:16,840 --> 01:12:20,150
>> Upewnijmy się, że działa dobrze pod Valgrind,

864
01:12:20,150 --> 01:12:28,310
co będziemy robić po prostu działa Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Wygląda na to, że rzeczywiście posiada jeden błąd z jednym kontekście -

866
01:12:31,110 --> 01:12:33,790
mamy ten segmentation fault.

867
01:12:33,790 --> 01:12:36,690
Co się stało?

868
01:12:36,690 --> 01:12:41,650
Valgrind rzeczywiście mówi nam gdzie to jest.

869
01:12:41,650 --> 01:12:43,050
Pomniejszyć trochę.

870
01:12:43,050 --> 01:12:46,040
Wygląda, że ​​to się dzieje w naszej funkcji wstawiania

871
01:12:46,040 --> 01:12:53,420
gdzie mamy nieprawidłowy odczytu wielkości 4 na wkładce, line 60.

872
01:12:53,420 --> 01:13:03,590
Wróćmy i zobaczyć, co się tu dzieje.

873
01:13:03,590 --> 01:13:05,350
Pomniejsz naprawdę szybkie.

874
01:13:05,350 --> 01:13:14,230
Chcę się upewnić, że to nie idzie się do krawędzi ekranu, dzięki czemu możemy zobaczyć wszystko.

875
01:13:14,230 --> 01:13:18,760
Wyciągnij, że w trochę. Dobrze.

876
01:13:18,760 --> 01:13:35,030
Przewiń w dół, a problem jest tutaj.

877
01:13:35,030 --> 01:13:40,120
Co się dzieje, jeśli mamy w dół, a nasz aktualny węzeł jest już pusty,

878
01:13:40,120 --> 01:13:44,010
nasz węzeł nadrzędny jest zerowy, więc jeśli przyjrzymy się na samej górze, tu -

879
01:13:44,010 --> 01:13:47,340
jeśli nie to pętla faktycznie wykonuje

880
01:13:47,340 --> 01:13:52,330
ponieważ nasza obecna wartość jest null - nasz korzeń jest zerowy, więc dyskusja jest null -

881
01:13:52,330 --> 01:13:57,810
potem nie nasz rodzic pobiera ustawiony na cur lub do prawidłowej wartości,

882
01:13:57,810 --> 01:14:00,580
tak, to rodzic będzie też null.

883
01:14:00,580 --> 01:14:03,700
Musimy pamiętać, aby sprawdzić, że

884
01:14:03,700 --> 01:14:08,750
przez czas mamy tu i zaczynamy dostęp rodzica wartość.

885
01:14:08,750 --> 01:14:13,190
Więc co się dzieje? Cóż, jeśli rodzic jest null -

886
01:14:13,190 --> 01:14:17,990
if (NULL == rodzic) - to wiemy, że

887
01:14:17,990 --> 01:14:19,530
nie musi być wszystko w drzewie.

888
01:14:19,530 --> 01:14:22,030
Musimy się starać, aby wstawić go w katalogu głównym.

889
01:14:22,030 --> 01:14:32,570
Możemy to zrobić, po prostu ustawiając korzeń równą nowego węzła.

890
01:14:32,570 --> 01:14:40,010
Potem w tym miejscu, że w rzeczywistości nie chcą przejść przez te inne rzeczy.

891
01:14:40,010 --> 01:14:44,780
Zamiast tu, możemy zrobić albo else-if-else,

892
01:14:44,780 --> 01:14:47,610
albo możemy połączyć wszystko tutaj w inny,

893
01:14:47,610 --> 01:14:56,300
ale tu będziemy po prostu użyć innego i zrobić to w ten sposób.

894
01:14:56,300 --> 01:14:59,030
Teraz mamy zamiar przetestować, aby upewnić się, że nasz rodzic nie jest null

895
01:14:59,030 --> 01:15:02,160
wcześniej faktycznie próbuje uzyskać dostęp do swoich pól.

896
01:15:02,160 --> 01:15:05,330
To pomoże nam uniknąć błędu segmentacji.

897
01:15:05,330 --> 01:15:14,740
Więc zamknąć, pomniejszyć, skompilować, uruchomić.

898
01:15:14,740 --> 01:15:18,130
>> Żadnych błędów, ale nadal mamy kilka wycieków pamięci

899
01:15:18,130 --> 01:15:20,650
ponieważ nie wszystkich naszych uwolnić węzłów.

900
01:15:20,650 --> 01:15:24,350
Ale, jeśli idziemy tu i patrzymy na naszego wydruku

901
01:15:24,350 --> 01:15:30,880
widzimy, że dobrze, wygląda jak wszystkie nasze wkładki wracali true, co jest dobre.

902
01:15:30,880 --> 01:15:33,050
Wkładki są prawdziwe,

903
01:15:33,050 --> 01:15:36,670
a następnie odpowiednie zawiera rozmowy są prawdziwe.

904
01:15:36,670 --> 01:15:41,510
>> Dobra robota! To wygląda tak, jakbyśmy pomyślnie zapisane wkładkę.

905
01:15:41,510 --> 01:15:47,430
To wszystko mamy na ten tydzień specyfikacji określone problem.

906
01:15:47,430 --> 01:15:51,720
One zabawa wyzwanie aby myśleć o to jak można faktycznie przejść w

907
01:15:51,720 --> 01:15:55,340
i wolne wszystkie węzły w tym drzewie.

908
01:15:55,340 --> 01:15:58,830
Można to zrobić na wiele różnych sposobów,

909
01:15:58,830 --> 01:16:01,930
ale ja zostawiam to do ciebie, aby eksperymentować,

910
01:16:01,930 --> 01:16:06,080
i jako wyzwanie zabawy, spróbuj i upewnić się, że można mieć pewność,

911
01:16:06,080 --> 01:16:09,490
że sprawozdanie to Valgrind nie zwraca żadnych błędów i nie ma wycieków.

912
01:16:09,490 --> 01:16:12,880
>> Powodzenia w tym tygodniu zestaw kodowania Huffmana problemu,

913
01:16:12,880 --> 01:16:14,380
i do zobaczenia w przyszłym tygodniu!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]