1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Abschnitt 7: Mehr Komfort]

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

3
00:00:05,090 --> 00:00:07,930
[Dies ist CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Gut. So wie ich in meinem E-Mail,

5
00:00:10,110 --> 00:00:14,060
dies wird eine binäre-tree-intensive Abschnitt sein.

6
00:00:14,060 --> 00:00:16,820
Aber es gibt nicht so viele Fragen.

7
00:00:16,820 --> 00:00:18,920
Also werden wir versuchen, und ziehen Sie jede Frage

8
00:00:18,920 --> 00:00:25,430
und in schmerzhaften Einzelheiten detailliert von allen die besten Möglichkeiten, Dinge zu tun zu gehen.

9
00:00:25,430 --> 00:00:31,200
So ganz am Anfang, wir gehen durch die Probe Zeichnungen von binären Bäumen und so.

10
00:00:31,200 --> 00:00:35,970
So hier "Beachten Sie, dass ein Binärbaum Knoten ähnlich denen von einer verknüpften Liste hat,

11
00:00:35,970 --> 00:00:38,150
außer statt einen Zeiger gibt es zwei: eines für das linke "Kind"

12
00:00:38,150 --> 00:00:41,950
und eines für das rechte Kind '. "

13
00:00:41,950 --> 00:00:45,630
So ein binärer Baum ist wie eine verkettete Liste,

14
00:00:45,630 --> 00:00:47,910
mit Ausnahme der struct wird zwei Zeigern.

15
00:00:47,910 --> 00:00:51,390
Es gibt trinary Bäume, die Umstellung auf drei Zeigern sind,

16
00:00:51,390 --> 00:00:56,540
gibt es N-ary Bäume, die nur noch einen generischen Zeiger

17
00:00:56,540 --> 00:01:00,320
Sie müssen dann malloc groß genug sein zu müssen

18
00:01:00,320 --> 00:01:04,840
genug Hinweise auf alle möglichen Kinder.

19
00:01:04,840 --> 00:01:08,200
So Binärbaum nur zufällig eine konstante Anzahl von zwei haben.

20
00:01:08,200 --> 00:01:11,260
Wenn Sie möchten, können Sie geben eine verknüpfte Liste als unäre Baum,

21
00:01:11,260 --> 00:01:15,360
aber ich glaube nicht, dass jemand anruft, dass.

22
00:01:15,360 --> 00:01:18,060
"Zeichnen Sie ein Kästchen-und-Pfeile Darstellung eines binären Baumknoten

23
00:01:18,060 --> 00:01:24,110
mit Nates Lieblings-Nummer, 7, wo jedes Kind Zeiger null ist. "

24
00:01:24,110 --> 00:01:27,780
So iPad-Modus.

25
00:01:27,780 --> 00:01:30,280
>> Es wird ziemlich einfach sein.

26
00:01:30,280 --> 00:01:36,150
Wir stehen noch gehen, um einen Knoten habe, werde ich es als ein Quadrat zu zeichnen.

27
00:01:36,150 --> 00:01:38,730
Und ich werde die Werte hier zu ziehen.

28
00:01:38,730 --> 00:01:41,090
So wird der Wert hier gehen,

29
00:01:41,090 --> 00:01:44,770
und dann hier unten müssen wir die linke Zeiger auf der linken und der rechten Zeiger auf der rechten Seite.

30
00:01:44,770 --> 00:01:50,430
Und es ist sehr viel, so Konvention nennen es links und rechts, der Zeiger Namen.

31
00:01:50,430 --> 00:01:52,460
Beide gehen zu null sein.

32
00:01:52,460 --> 00:01:57,870
Das wird nur null sein, und das wird nur null sein.

33
00:01:57,870 --> 00:02:03,630
Okay. So, hier zu sichern.

34
00:02:03,630 --> 00:02:05,700
"Mit einer verketteten Liste, wir hatten nur einen Zeiger speichern

35
00:02:05,700 --> 00:02:09,639
an den ersten Knoten in der Liste, um den gesamten verketteten Liste, oder die gesamte Liste zu erinnern.

36
00:02:09,639 --> 00:02:11,650
Ebenso mit Bäumen, wir haben nur einen Zeiger speichern

37
00:02:11,650 --> 00:02:13,420
auf einen einzelnen Knoten, um den ganzen Baum erinnern.

38
00:02:13,420 --> 00:02:15,980
Dieser Knoten ist calle das 'root' des Baumes.

39
00:02:15,980 --> 00:02:18,320
Bauen Sie auf Ihrem Diagramm aus der Zeit vor oder zeichnen Sie einen neuen

40
00:02:18,320 --> 00:02:21,690
so dass Sie ein Kästchen-und-Pfeile Darstellung eines binären Baum haben

41
00:02:21,690 --> 00:02:25,730
mit dem der Wert 7, dann 3 in der linken,

42
00:02:25,730 --> 00:02:32,760
dann 9 auf der rechten Seite, und dann 6 auf der rechten Seite der 3 ".

43
00:02:32,760 --> 00:02:34,810
Lasst uns sehen, ob ich das alles in meinem Kopf denken kann.

44
00:02:34,810 --> 00:02:37,670
Also das wird unsere Wurzel bis hier zu sein.

45
00:02:37,670 --> 00:02:41,600
Wir werden einige Zeiger irgendwo haben, etwas, das wir root nenne,

46
00:02:41,600 --> 00:02:45,140
und es ist zu diesem Kerl zeigt.

47
00:02:45,140 --> 00:02:48,490
Jetzt einen neuen Knoten zu machen,

48
00:02:48,490 --> 00:02:52,870
was haben wir, 3 auf der linken Seite?

49
00:02:52,870 --> 00:02:57,140
So wird ein neuer Knoten mit 3, und es zunächst darauf null.

50
00:02:57,140 --> 00:02:59,190
Ich werde gerade auf N.

51
00:02:59,190 --> 00:03:02,250
Jetzt wollen wir zu machen, dass auf der linken Seite 7 fort.

52
00:03:02,250 --> 00:03:06,840
So ändern wir diesen Zeiger nun auf diesen Kerl zu zeigen.

53
00:03:06,840 --> 00:03:12,420
Und wir tun das gleiche. Wir wollen eine 9 hier

54
00:03:12,420 --> 00:03:14,620
die zunächst nur sagt null.

55
00:03:14,620 --> 00:03:19,600
Wir werden diese Zeiger auf 9 zu ändern,

56
00:03:19,600 --> 00:03:23,310
und jetzt wollen wir bis 6 auf der rechten Seite von 3 setzen.

57
00:03:23,310 --> 00:03:32,170
So, es wird - einen 6.

58
00:03:32,170 --> 00:03:34,310
Und dieser Kerl wird darauf gibt.

59
00:03:34,310 --> 00:03:38,320
Okay. Also das ist alles was man bittet uns zu tun.

60
00:03:38,320 --> 00:03:42,770
>> Lassen Sie uns nun über einige Begriffe gehen.

61
00:03:42,770 --> 00:03:46,690
Wir haben bereits darüber gesprochen, wie die Wurzel des Baumes ist der oberste Knoten in der Baumstruktur.

62
00:03:46,690 --> 00:03:54,720
Die eine, die 7. Die Knoten im unteren Bereich des Baumes nennt man die Blätter.

63
00:03:54,720 --> 00:04:01,240
Jeder Knoten, der hat einfach null als seine Kinder ist ein Blatt.

64
00:04:01,240 --> 00:04:03,680
So ist es möglich, wenn unsere binären Baum ist nur ein einzelner Knoten,

65
00:04:03,680 --> 00:04:10,130
dass ein Baum ist ein Blatt, und das ist es.

66
00:04:10,130 --> 00:04:12,060
"Die 'height' des Baumes ist die Anzahl der Hops Sie müssen sicherstellen,

67
00:04:12,060 --> 00:04:16,620
um von der Spitze zu einem Blatt zu erhalten. "

68
00:04:16,620 --> 00:04:18,640
Wir werden in zu erhalten, in einer zweiten, den Unterschied

69
00:04:18,640 --> 00:04:21,940
zwischen symmetrischen und unsymmetrischen binären Bäumen,

70
00:04:21,940 --> 00:04:29,470
aber für jetzt, die Gesamthöhe des Baumes

71
00:04:29,470 --> 00:04:34,520
Ich würde sagen, ist 3, aber wenn man die Anzahl der Hops

72
00:04:34,520 --> 00:04:39,710
Sie müssen sicherstellen, um auf 9 zu bekommen, dann ist es wirklich nur eine Höhe von 2.

73
00:04:39,710 --> 00:04:43,340
Im Moment ist dies eine unausgewogene binären Baum,

74
00:04:43,340 --> 00:04:49,840
aber wir werden über ausgewogene sprach, wenn es relevant sein wird.

75
00:04:49,840 --> 00:04:52,040
So, jetzt können wir über Knoten in einem Baum in Begriffen zu sprechen

76
00:04:52,040 --> 00:04:54,700
relativ zu den anderen Knoten in dem Baum.

77
00:04:54,700 --> 00:04:59,730
So jetzt haben wir Eltern, Kinder, Geschwister, Vorfahren und Nachkommen.

78
00:04:59,730 --> 00:05:05,650
Sie sind ziemlich gesunden Menschenverstand, was sie bedeuten.

79
00:05:05,650 --> 00:05:09,610
Wenn wir uns fragen - es ist Eltern.

80
00:05:09,610 --> 00:05:12,830
Also, was ist die Muttergesellschaft von 3?

81
00:05:12,830 --> 00:05:16,090
[Studenten] 7. >> Ja. Die Muttergesellschaft ist nur das sein, was zeigt auf Sie.

82
00:05:16,090 --> 00:05:20,510
Und was sind die Kinder von 7?

83
00:05:20,510 --> 00:05:23,860
[Studenten] 3 und 9. >> Ja.

84
00:05:23,860 --> 00:05:26,460
Beachten Sie, dass "Kinder" bedeutet wörtlich Kinder,

85
00:05:26,460 --> 00:05:31,010
so 6 nicht gelten würde, weil es wie ein Enkelkind ist.

86
00:05:31,010 --> 00:05:35,540
Aber dann, wenn wir Nachfahren gehen, so was sind die Nachkommen von 7?

87
00:05:35,540 --> 00:05:37,500
[Studenten] 3, 6 und 9. >> Ja.

88
00:05:37,500 --> 00:05:42,330
Die Nachkommen des Root-Knotens wird alles sein, im Baum,

89
00:05:42,330 --> 00:05:47,950
außer vielleicht der Wurzelknoten selbst, wenn Sie nicht wollen, zu bedenken, dass ein Nachkomme.

90
00:05:47,950 --> 00:05:50,750
Und schließlich, Vorfahren, so dass es in die entgegengesetzte Richtung.

91
00:05:50,750 --> 00:05:55,740
Also, was sind die Vorfahren von 6?

92
00:05:55,740 --> 00:05:58,920
[Studenten] 3 und 7. >> Ja. 9 ist nicht inbegriffen.

93
00:05:58,920 --> 00:06:02,520
Es ist nur die direkte Linie zurück zur Wurzel

94
00:06:02,520 --> 00:06:13,230
wird Ihre Vorfahren.

95
00:06:13,230 --> 00:06:16,300
>> "Wir sagen, dass ein binärer Baum ist 'bestellt', wenn für jeden Knoten im Baum,

96
00:06:16,300 --> 00:06:19,530
alle seine Nachkommen auf der linken Seite haben kleinere Werte

97
00:06:19,530 --> 00:06:22,890
und alle die, die auf der rechten Seite eine größere Werte.

98
00:06:22,890 --> 00:06:27,060
Zum Beispiel wird der Baum oben bestellte, aber es ist nicht die einzig mögliche geordnete Anordnung. "

99
00:06:27,060 --> 00:06:30,180
Bevor wir dazu kommen,

100
00:06:30,180 --> 00:06:36,420
eine geordnete binäre Baum wird auch als binäre Suchbaum bekannt.

101
00:06:36,420 --> 00:06:38,660
Hier passieren zu nennen es eine geordnete binäre Baum,

102
00:06:38,660 --> 00:06:41,850
aber ich habe nie gehört, dass es als eine geordnete binäre Baum vor,

103
00:06:41,850 --> 00:06:46,650
und einem Quiz wir sind viel eher zu binären Suchbaum setzen.

104
00:06:46,650 --> 00:06:49,250
Sie sind ein und dasselbe,

105
00:06:49,250 --> 00:06:54,580
und es ist wichtig, dass Sie erkennen den Unterschied zwischen binären Baum und binären Suchbaum.

106
00:06:54,580 --> 00:06:58,830
Ein binärer Baum ist nur ein Baum, der auf zwei Dinge.

107
00:06:58,830 --> 00:07:02,120
Jeder Knoten weist auf zwei Dinge.

108
00:07:02,120 --> 00:07:06,310
Es gibt keine Überlegungen über die Werte, die sie verweist.

109
00:07:06,310 --> 00:07:11,370
So wie hier, da es ein binärer Suchbaum ist,

110
00:07:11,370 --> 00:07:14,030
wir wissen, dass, wenn wir gehen von 7 links

111
00:07:14,030 --> 00:07:16,670
dann werden alle Werte, die wir möglicherweise erreichen kann

112
00:07:16,670 --> 00:07:19,310
nach links geht von 7 haben sich als weniger als 7 aufweist.

113
00:07:19,310 --> 00:07:24,070
Bemerken, dass alle Werte kleiner als 7 3 und 6 sind.

114
00:07:24,070 --> 00:07:26,040
Diese sind alle links von 7.

115
00:07:26,040 --> 00:07:29,020
Wenn wir auf der rechten Seite 7 gehen, hat alles, was größer als 7,

116
00:07:29,020 --> 00:07:33,220
so 9 ist auf der rechten Seite 7, so sind wir gut.

117
00:07:33,220 --> 00:07:36,150
Dies ist nicht der Fall für einen Binärbaum,

118
00:07:36,150 --> 00:07:40,020
für eine reguläre Binärbaum können wir einfach 3 oben, 7 nach links,

119
00:07:40,020 --> 00:07:47,630
9 auf der linken Seite von 7, es gibt keine Reihenfolge der Werte überhaupt.

120
00:07:47,630 --> 00:07:56,140
Jetzt werden wir nicht wirklich tun dies, weil es langweilig und unnötig ist,

121
00:07:56,140 --> 00:07:59,400
aber "versuchen, so viele bestellt Bäume zeichnen, wie Sie denken können

122
00:07:59,400 --> 00:08:01,900
Verwendung der Ziffern 7, 3, 9 und 6.

123
00:08:01,900 --> 00:08:06,800
Wie viele verschiedene Anordnungen gibt es? Wie ist die Höhe jedes eine? "

124
00:08:06,800 --> 00:08:10,480
>> Wir machen ein paar, aber die Grundidee ist,

125
00:08:10,480 --> 00:08:16,530
dies ist in keiner Weise eine eindeutige Darstellung eines binären Baumes mit diesen Werten.

126
00:08:16,530 --> 00:08:22,760
Alles, was wir brauchen, ist eine binäre Baum, 7 enthält, 3, 6 und 9.

127
00:08:22,760 --> 00:08:25,960
Ein weiterer möglicher gültigen man die Wurzel 3 sein,

128
00:08:25,960 --> 00:08:30,260
gehen Sie nach links und es ist 6, gehen Sie nach links und es ist 7,

129
00:08:30,260 --> 00:08:32,730
gehen Sie nach links und es ist 9.

130
00:08:32,730 --> 00:08:36,169
Das ist eine absolut gültige binären Suchbaum.

131
00:08:36,169 --> 00:08:39,570
Es ist nicht sehr hilfreich, weil es wie eine verkettete Liste ist

132
00:08:39,570 --> 00:08:43,750
und alle diese Zeiger sind gerade null.

133
00:08:43,750 --> 00:08:48,900
Aber es ist eine gültige Baum. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Student] Haben nicht die Werte müssen größer auf der rechten Seite?

135
00:08:51,310 --> 00:08:56,700
Oder ist das -? >> Das meinte ich, den anderen Weg zu gehen.

136
00:08:56,700 --> 00:09:00,960
Es gibt auch - ja, wir schalten, dass.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Guter Fang.

138
00:09:07,770 --> 00:09:11,730
Es hat immer noch zu gehorchen, was ein binärer Suchbaum tun soll.

139
00:09:11,730 --> 00:09:15,650
Also alles auf der linken Seite muss kleiner sein als jeder gegebenen Knoten.

140
00:09:15,650 --> 00:09:23,180
Wir könnten einfach zu bewegen, sagen wir, diese 6 und legen Sie sie hier.

141
00:09:23,180 --> 00:09:26,880
Nein, können wir nicht. Warum halte ich tun?

142
00:09:26,880 --> 00:09:35,350
Lassen Sie uns - hier ist 6, hier ist 7, 6 Punkte 3.

143
00:09:35,350 --> 00:09:39,290
Dies ist immer noch eine gültige binären Suchbaum.

144
00:09:39,290 --> 00:09:49,260
Was ist falsch, wenn ich - mal sehen, ob ich kommen kann mit einer Anordnung.

145
00:09:49,260 --> 00:09:52,280
Ja, okay. Also, was ist los mit diesem Baum?

146
00:09:52,280 --> 00:10:08,920
Ich denke, ich habe schon gegeben Ihnen einen Hinweis, dass es etwas falsch mit ihm.

147
00:10:08,920 --> 00:10:14,430
Warum halte ich tun?

148
00:10:14,430 --> 00:10:18,510
Okay. Das sieht vernünftig.

149
00:10:18,510 --> 00:10:22,590
Wenn wir an jedem Knoten, wie 7, dann auf der linken Seite 7 zu sehen ist ein 3.

150
00:10:22,590 --> 00:10:24,960
So haben wir 3 haben, ist das, was auf der rechten Seite von 3 a 6.

151
00:10:24,960 --> 00:10:27,750
Und wenn Sie bei 6 zu sehen, ist die Sache auf der rechten Seite 6 a 9.

152
00:10:27,750 --> 00:10:30,910
Also, warum ist dies nicht eine gültige Suchbaum?

153
00:10:30,910 --> 00:10:36,330
[Studenten] 9 ist noch auf der linken Seite 7. >> Ja.

154
00:10:36,330 --> 00:10:43,710
Es muss wahr, dass alle Werte ggf. durch, die nach links von 7 erreichen weniger als 7 sind.

155
00:10:43,710 --> 00:10:49,120
Wenn wir gehen links von 7 haben wir um 3 zu erhalten und wir können noch bis 6 zu erhalten,

156
00:10:49,120 --> 00:10:52,520
wir können noch bis 9 zu erhalten, aber indem er gegangen weniger als 7,

157
00:10:52,520 --> 00:10:55,070
sollten wir nicht in der Lage sein, um eine Zahl, die größer als 7 ist zu bekommen.

158
00:10:55,070 --> 00:10:59,830
Das ist also nicht eine gültige binären Suchbaum.

159
00:10:59,830 --> 00:11:02,330
>> Mein Bruder hatte tatsächlich ein Interview Frage

160
00:11:02,330 --> 00:11:07,760
das war im Grunde ist dies nur Code bis etwas zu validieren

161
00:11:07,760 --> 00:11:10,500
ob ein Baum ist ein binärer Suchbaum,

162
00:11:10,500 --> 00:11:13,580
und so das erste, was er tat, war nur um zu sehen,

163
00:11:13,580 --> 00:11:17,020
wenn die linken und rechten korrekt sind, und dann durchlaufen dort unten.

164
00:11:17,020 --> 00:11:19,700
Aber man kann nicht einfach tun, Sie haben den Überblick zu behalten

165
00:11:19,700 --> 00:11:22,550
der Tatsache, dass jetzt, dass ich links von 7 weg,

166
00:11:22,550 --> 00:11:26,340
alles in diesem Teilbaum muss weniger als 7.

167
00:11:26,340 --> 00:11:28,430
Die richtige Algorithmus muss den Überblick zu behalten

168
00:11:28,430 --> 00:11:35,970
der Grenzen, dass die Werte möglicherweise fallen kann in.

169
00:11:35,970 --> 00:11:38,360
Wir werden nicht durch alle von ihnen gehen.

170
00:11:38,360 --> 00:11:41,630
Es ist ein schöner Rekursionsformel,

171
00:11:41,630 --> 00:11:44,810
obwohl wir nicht auf diejenigen bekommen, oder wir werden nicht auf diejenigen zu bekommen,

172
00:11:44,810 --> 00:11:47,030
definiert, wie viele es tatsächlich sind.

173
00:11:47,030 --> 00:11:53,180
So gibt es 14 von ihnen.

174
00:11:53,180 --> 00:11:56,020
Die Idee, wie Sie es tun würde rechnerisch ist wie,

175
00:11:56,020 --> 00:11:59,770
Sie können eine beliebige einzelne der Root-Knoten sein,

176
00:11:59,770 --> 00:12:03,160
und dann, wenn ich wähle 7 bis der Wurzelknoten sein,

177
00:12:03,160 --> 00:12:08,150
dann gibt es, sagen wir, ein paar Zahlen, die gehen meiner linken Knoten,

178
00:12:08,150 --> 00:12:10,440
und es gibt einige Zahlen, die meinen rechten Knoten sein kann,

179
00:12:10,440 --> 00:12:15,090
aber wenn ich n Gesamtzahlen, dann ist die Menge, die nach links gehen kann

180
00:12:15,090 --> 00:12:18,820
plus dem Betrag, der nach rechts gehen kann, ist n - 1.

181
00:12:18,820 --> 00:12:26,130
Also der verbleibenden Zahlen, müssen sie in der Lage, entweder zu der linken oder der rechten Seite.

182
00:12:26,130 --> 00:12:31,580
Es scheint schwierig, dass, wenn ich 3 die erste Stelle setzen dann alles auf der linken Seite gehen muss,

183
00:12:31,580 --> 00:12:35,080
aber wenn ich 7 setzen, dann können manche Dinge gehen die die linke und einige Dinge können nach rechts gehen.

184
00:12:35,080 --> 00:12:39,570
Und von '3 erste "meinte ich alles kann auf der rechten Seite gehen.

185
00:12:39,570 --> 00:12:42,350
Es ist wirklich, man muss nur darüber, wie denken,

186
00:12:42,350 --> 00:12:47,980
wie viele Dinge auf die nächste Ebene des Baumes gehen.

187
00:12:47,980 --> 00:12:50,420
Und es kommt zu 14 sein, oder Sie können alle von ihnen zu ziehen,

188
00:12:50,420 --> 00:12:54,650
und dann bekommen Sie 14.

189
00:12:54,650 --> 00:13:01,120
>> Wieder hier,

190
00:13:01,120 --> 00:13:03,510
"Bestellt binäre Bäume sind cool, weil wir durch sie suchen können

191
00:13:03,510 --> 00:13:06,910
in einer sehr ähnlichen Weise mit der Suche über einen sortierten Array.

192
00:13:06,910 --> 00:13:10,120
Um dies zu tun, haben wir an der Wurzel beginnen und uns auf den Weg nach unten den Baum

193
00:13:10,120 --> 00:13:13,440
Richtung Blätter, die Überprüfung der einzelnen Knoten Werte mit den Werten, die wir für suchst.

194
00:13:13,440 --> 00:13:15,810
Wenn der aktuelle Knoten den Wert geringer ist als der Wert, den wir suchen,

195
00:13:15,810 --> 00:13:18,050
Sie gehen neben dem Knoten rechte Kind.

196
00:13:18,050 --> 00:13:20,030
Andernfalls fahren Sie den Knoten der linken Kind.

197
00:13:20,030 --> 00:13:22,800
An einem gewissen Punkt, werden Sie finden, entweder den Wert, den du suchst, oder du wirst in eine null laufen,

198
00:13:22,800 --> 00:13:28,520
die den Wert nicht in dem Baum. "

199
00:13:28,520 --> 00:13:32,450
Ich habe den Baum hatten wir vor Neuzeichnen; das wird eine Sekunde dauern.

200
00:13:32,450 --> 00:13:38,280
Aber wir wollen schauen, ob 6, 10 und 1 in dem Baum sind.

201
00:13:38,280 --> 00:13:49,180
Also, was war es, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Die Zahlen, die Sie nachschlagen möchten, wollen wir schauen 6.

203
00:13:52,730 --> 00:13:55,440
Wie funktioniert dieser Algorithmus funktioniert?

204
00:13:55,440 --> 00:14:03,040
Nun, wir haben auch einige root Zeiger auf unserem Baum.

205
00:14:03,040 --> 00:14:12,460
Und wir würden an die Wurzel gehen und sagen, ist dieser Wert gleich dem Wert, nach dem gesucht?

206
00:14:12,460 --> 00:14:15,000
So sind wir für 6 suchen, so ist es nicht gleich.

207
00:14:15,000 --> 00:14:20,140
So halten wir gehen, und jetzt sagen wir, okay, so 6 weniger als 7 ist.

208
00:14:20,140 --> 00:14:23,940
Heißt das, wir wollen nach links zu gehen, oder wollen wir nach rechts gehen?

209
00:14:23,940 --> 00:14:27,340
[Student] Links. >> Ja.

210
00:14:27,340 --> 00:14:33,340
Es ist wesentlich einfacher, alles, was Sie zu tun haben, ziehen eine mögliche Knoten des Baumes

211
00:14:33,340 --> 00:14:37,760
und dann tun nicht - anstatt zu versuchen, in Ihrem Kopf zu denken,

212
00:14:37,760 --> 00:14:40,020
okay, wenn es weniger ist, weiß ich auf der linken Seite gehen oder sich das Recht vor,

213
00:14:40,020 --> 00:14:43,030
bei einem Blick auf dieses Bild, ist es sehr klar, dass ich auf der linken Seite gehen

214
00:14:43,030 --> 00:14:47,700
wenn dieser Knoten größer ist als der Wert, den ich suche.

215
00:14:47,700 --> 00:14:52,600
Also nach links gehen, jetzt habe ich bei 3 bin.

216
00:14:52,600 --> 00:14:57,770
Ich möchte - 3 geringer ist als der Wert, den ich benötige, die 6 ist.

217
00:14:57,770 --> 00:15:03,420
Also haben wir nach rechts gehen, und jetzt habe ich am Ende bei 6,

218
00:15:03,420 --> 00:15:07,380
das ist der Wert, den ich benötige, so dass ich true zurückgeben.

219
00:15:07,380 --> 00:15:15,760
Der nächste Wert werde ich zu suchen habe, ist 10.

220
00:15:15,760 --> 00:15:23,230
Okay. So 10, jetzt wird - abgeschnitten, dass - würde die Wurzel folgen.

221
00:15:23,230 --> 00:15:27,670
Nun wird 10 werde größer sein als 7, so will ich nach rechts zu schauen.

222
00:15:27,670 --> 00:15:31,660
Ich werde hierher zu kommen, wird 10 sein wird größer als 9,

223
00:15:31,660 --> 00:15:34,520
so bin ich gehen zu wollen, nach rechts zu schauen.

224
00:15:34,520 --> 00:15:42,100
Ich komme hierher, aber hier jetzt bin ich an null.

225
00:15:42,100 --> 00:15:44,170
Was muss ich tun, wenn ich null schlagen?

226
00:15:44,170 --> 00:15:47,440
[Student] Zurück falsch? >> Ja. Ich habe nicht finden 10.

227
00:15:47,440 --> 00:15:49,800
1 wird ein nahezu identischer Fall sein,

228
00:15:49,800 --> 00:15:51,950
Ausnahme ist es nur geht, um umgedreht werden, statt suchen

229
00:15:51,950 --> 00:15:56,540
auf der rechten Seite, ich werde schauen hinunter auf die linke Seite.

230
00:15:56,540 --> 00:16:00,430
>> Jetzt denke ich, wir tatsächlich den Code zu bekommen.

231
00:16:00,430 --> 00:16:04,070
Hier ist, wo - eröffnen den CS50 Gerät und navigieren Sie Ihren Weg dorthin

232
00:16:04,070 --> 00:16:07,010
Sie können aber auch einfach tun im Raum.

233
00:16:07,010 --> 00:16:09,170
Es ist wahrscheinlich ideal, um es in dem Raum zu tun,

234
00:16:09,170 --> 00:16:13,760
weil wir in dem Raum arbeiten.

235
00:16:13,760 --> 00:16:19,170
"Zuerst werden wir brauchen eine neue Art Definition für einen binären Baum Knoten mit int-Werten.

236
00:16:19,170 --> 00:16:21,400
Mit dem Textvorschlag typedef unten

237
00:16:21,400 --> 00:16:24,510
Erstellen eines neuen Typdefinition für einen Knoten in einem binären Baum.

238
00:16:24,510 --> 00:16:27,930
Wenn Sie nicht weiterkommen. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
So lasst uns den Textvorschlag hier

240
00:16:30,380 --> 00:16:41,630
typedef struct Knoten und Knoten. Ja, okay.

241
00:16:41,630 --> 00:16:44,270
Also, was sind die Felder wir in unserem Knoten möchten sind?

242
00:16:44,270 --> 00:16:46,520
[Student] Int und dann zwei Zeigern?

243
00:16:46,520 --> 00:16:49,700
>> Int-Wert, zwei Zeiger? Wie schreibe ich die Zeiger?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Ich sollte zu vergrößern in. Ja, so struct node * links,

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

246
00:17:01,320 --> 00:17:03,460
Und denken Sie daran, die Diskussion vom letzten Mal,

247
00:17:03,460 --> 00:17:15,290
dass dies keinen Sinn macht, macht dies keinen Sinn,

248
00:17:15,290 --> 00:17:18,270
das macht keinen Sinn.

249
00:17:18,270 --> 00:17:25,000
Sie müssen alles, was es um diese rekursive struct definieren.

250
00:17:25,000 --> 00:17:27,970
Okay, so dass das, was unser Baum wird wie folgt aussehen.

251
00:17:27,970 --> 00:17:37,670
Wenn wir eine trinäre Baums ja, dann einen Knoten könnte wie b1, b2, b3 * struct Knoten betrachten,

252
00:17:37,670 --> 00:17:43,470
wobei b ein Zweig ist - eigentlich habe ich mehr hörte es links, mitte, rechts, aber egal.

253
00:17:43,470 --> 00:17:55,610
Wir haben nur über binäre kümmern, so rechts, links.

254
00:17:55,610 --> 00:17:59,110
"Jetzt erkläre eine globale node * Variable für die Wurzel des Baumes."

255
00:17:59,110 --> 00:18:01,510
So werden wir nicht zu tun.

256
00:18:01,510 --> 00:18:08,950
Um die Dinge etwas schwieriger und verallgemeinert,

257
00:18:08,950 --> 00:18:11,570
wir werden nicht einen globalen Knoten variabel.

258
00:18:11,570 --> 00:18:16,710
Stattdessen in main wir erklären alle unsere Knoten Dinge,

259
00:18:16,710 --> 00:18:20,500
und das bedeutet, dass unter, wenn wir laufen beginnen

260
00:18:20,500 --> 00:18:23,130
unserer Funktion CONTAINS und unsere Insert-Funktion,

261
00:18:23,130 --> 00:18:27,410
statt unserer Funktion CONTAINS nur mit diesen globalen Knoten variabel,

262
00:18:27,410 --> 00:18:34,280
wir gehen zu müssen, als Argument nehmen den Baum, dass wir es verarbeiten möchten.

263
00:18:34,280 --> 00:18:36,650
Mit der globalen Variablen sollte Dinge einfacher zu machen.

264
00:18:36,650 --> 00:18:42,310
Wir werden die Dinge schwieriger.

265
00:18:42,310 --> 00:18:51,210
Nun nehmen Sie eine Minute oder so genau das zu tun diese Art der Sache,

266
00:18:51,210 --> 00:18:57,690
wo innerhalb der wichtigsten Sie diesen Baum erstellen wollen, und das ist alles, was Sie tun möchten.

267
00:18:57,690 --> 00:19:04,530
Versuchen Sie und bauen diesen Baum in Ihrem Haupt-Funktion.

268
00:19:42,760 --> 00:19:47,610
>> Okay. So müssen Sie nicht einmal gebaut dem Baum haben den ganzen Weg noch.

269
00:19:47,610 --> 00:19:49,840
Aber jemand etwas, das ich ziehen konnte

270
00:19:49,840 --> 00:20:03,130
zu zeigen, wie man vielleicht beginnen Aufbau einer solchen Baum?

271
00:20:03,130 --> 00:20:08,080
[Student] Jemand hämmern, versuchen, aus.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Wer bequem mit ihren Baum-Konstruktion?

273
00:20:13,100 --> 00:20:15,520
[Student] Sure. Es ist noch nicht fertig. >> Es ist in Ordnung. Wir können nur beendet -

274
00:20:15,520 --> 00:20:26,860
oh, können Sie es speichern? Hooray.

275
00:20:26,860 --> 00:20:32,020
Also hier haben wir - oh, ich bin leicht abgeschnitten.

276
00:20:32,020 --> 00:20:34,770
Bin ich in gezoomt?

277
00:20:34,770 --> 00:20:37,730
Zoomen, Scrollen aus. >> Ich habe eine Frage. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Student] Wenn Sie struct definieren, sind Dinge wie initialisiert etwas?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nein >> Okay. So müsste man zu initialisieren -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nein Wenn Sie definieren oder wenn Sie erklären, eine Struktur,

281
00:20:50,450 --> 00:20:55,600
es ist nicht standardmäßig initialisiert, es ist einfach so, wenn Sie einen int deklarieren.

282
00:20:55,600 --> 00:20:59,020
Es ist genau das gleiche. Es ist wie jeder seiner Einzelfelder

283
00:20:59,020 --> 00:21:04,460
kann eine Garbage-Wert in ihm haben. >> Und ist es möglich zu definieren - oder zu erklären, eine Struktur

284
00:21:04,460 --> 00:21:07,740
in einer Weise, dass es funktioniert initialisieren?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ja. Also, Verknüpfung Initialisierungssyntax

286
00:21:13,200 --> 00:21:18,660
wird wie folgt aussehen -

287
00:21:18,660 --> 00:21:22,200
Es gibt zwei Möglichkeiten, wie wir dies tun können. Ich denke, wir sollten es kompilieren

288
00:21:22,200 --> 00:21:25,840
um sicherzustellen, dass Clang machen tut dies auch.

289
00:21:25,840 --> 00:21:28,510
Die Reihenfolge der Argumente, die in der Struktur kommt,

290
00:21:28,510 --> 00:21:32,170
Sie setzen wie die Reihenfolge der Argumente innerhalb dieser geschweiften Klammern.

291
00:21:32,170 --> 00:21:35,690
Also, wenn Sie es bis 9 initialisieren möchten und links werden null und dann rechts null sein,

292
00:21:35,690 --> 00:21:41,570
es 9 sein, null, null.

293
00:21:41,570 --> 00:21:47,890
Die Alternative ist, und der Editor nicht mag diese Syntax,

294
00:21:47,890 --> 00:21:50,300
und es denkt, ich will einen neuen Block,

295
00:21:50,300 --> 00:22:01,800
aber die Alternative ist so etwas wie -

296
00:22:01,800 --> 00:22:04,190
hier, ich werde es auf einer neuen Zeile setzen.

297
00:22:04,190 --> 00:22:09,140
Sie können explizit sagen, vergesse ich die genaue Syntax.

298
00:22:09,140 --> 00:22:13,110
So können Sie explizit beim Namen, und sagen:

299
00:22:13,110 --> 00:22:21,570
. C oder. Wert = 9,. Links = NULL.

300
00:22:21,570 --> 00:22:24,540
Ich vermute, diese Notwendigkeit Komma sein.

301
00:22:24,540 --> 00:22:29,110
. Rechts = NULL, so diese Weise können Sie nicht

302
00:22:29,110 --> 00:22:33,780
tatsächlich benötigen, um die Reihenfolge der struct wissen,

303
00:22:33,780 --> 00:22:36,650
und wenn Sie diese Zeilen lesen, ist es viel deutlicher

304
00:22:36,650 --> 00:22:41,920
über das, was der Wert ist initialisiert, um.

305
00:22:41,920 --> 00:22:44,080
>> Dies geschieht, um eines der Dinge sein, dass -

306
00:22:44,080 --> 00:22:49,100
so ist, zum größten Teil, C + + ist eine Obermenge von C.

307
00:22:49,100 --> 00:22:54,160
Sie können C-Code, kopieren Sie ihn in C + +, und es sollte zu kompilieren.

308
00:22:54,160 --> 00:22:59,570
Dies ist eines der Dinge, dass C + + nicht unterstützt, so dass die Leute eher nicht, es zu tun.

309
00:22:59,570 --> 00:23:01,850
Ich weiß nicht, ob das ist der einzige Grund, warum Menschen dazu neigen, es nicht zu tun,

310
00:23:01,850 --> 00:23:10,540
aber der Fall, wo ich gebraucht, es zu benutzen benötigt, um mit C + + und so konnte ich nicht daran arbeiten.

311
00:23:10,540 --> 00:23:14,000
Ein weiteres Beispiel für etwas, das nicht mit C + + ist die Arbeit

312
00:23:14,000 --> 00:23:16,940
wie malloc liefert einen "void *", technisch,

313
00:23:16,940 --> 00:23:20,200
aber man konnte nur sagen, char * x = malloc was auch immer,

314
00:23:20,200 --> 00:23:22,840
und es wird automatisch zu einem char * gegossen werden.

315
00:23:22,840 --> 00:23:25,450
Das automatische Besetzung nicht geschieht in C + +.

316
00:23:25,450 --> 00:23:28,150
Das wäre nicht zu kompilieren, und Sie würden ausdrücklich sagen müssen,

317
00:23:28,150 --> 00:23:34,510
char *, malloc, was auch immer, es zu einem char * gegossen.

318
00:23:34,510 --> 00:23:37,270
Es gibt nicht viele Dinge, die C-und C + + auf nicht einverstanden sind,

319
00:23:37,270 --> 00:23:40,620
aber das sind zwei.

320
00:23:40,620 --> 00:23:43,120
Also werden wir mit dieser Syntax gehen.

321
00:23:43,120 --> 00:23:46,150
Aber selbst wenn wir nicht mit dieser Syntax gehen,

322
00:23:46,150 --> 00:23:49,470
was ist - könnte daran falsch?

323
00:23:49,470 --> 00:23:52,170
[Student] Ich brauche nicht zu dereferenzieren es? >> Ja.

324
00:23:52,170 --> 00:23:55,110
Beachten Sie, dass der Pfeil eine implizite Dereferenzierung hat,

325
00:23:55,110 --> 00:23:58,230
und so, wenn wir nur den Umgang mit einer Struktur,

326
00:23:58,230 --> 00:24:04,300
wollen wir nutzen. zu einem Feld innerhalb der Struktur zu erhalten.

327
00:24:04,300 --> 00:24:07,200
Und das einzige Mal, dass wir mit der Pfeil ist, wenn wir wollen -

328
00:24:07,200 --> 00:24:13,450
gut, ist Pfeils entspricht -

329
00:24:13,450 --> 00:24:17,020
das ist, was es bedeutete, wenn ich arrow verwendet haben.

330
00:24:17,020 --> 00:24:24,600
All arrow Mittel, Dereferenzierung dieses, jetzt bin ich an einem struct, und ich kann das Feld zu bekommen.

331
00:24:24,600 --> 00:24:28,040
Entweder bekommen Sie das Feld direkt oder dereferenzieren und erhalten das Feld -

332
00:24:28,040 --> 00:24:30,380
Ich denke, dies sollte Wert sein.

333
00:24:30,380 --> 00:24:33,910
Aber hier bin ich mit nur einem struct, nicht ein Zeiger auf eine struct zu tun haben,

334
00:24:33,910 --> 00:24:38,780
und so kann ich nicht verwenden, den Pfeil.

335
00:24:38,780 --> 00:24:47,510
Aber diese Art der Sache können wir für alle Knoten zu tun.

336
00:24:47,510 --> 00:24:55,790
Oh mein Gott.

337
00:24:55,790 --> 00:25:09,540
Dies ist 6, 7 und 3.

338
00:25:09,540 --> 00:25:16,470
Dann können wir Einrichten der Niederlassungen in unserem Baum, können wir 7 -

339
00:25:16,470 --> 00:25:21,650
wir haben, sollte seine linke Punkt 3.

340
00:25:21,650 --> 00:25:25,130
Also, wie machen wir das?

341
00:25:25,130 --> 00:25:29,320
[Studenten, unverständlich] >> Ja. Die Adresse des node3,

342
00:25:29,320 --> 00:25:34,170
und wenn Sie nicht über Adresse, dann es wäre einfach nicht kompilieren.

343
00:25:34,170 --> 00:25:38,190
Aber denken Sie daran, dass diese Zeiger auf den nächsten Knoten.

344
00:25:38,190 --> 00:25:44,930
Dieses Recht sollte bis 9 zeigen,

345
00:25:44,930 --> 00:25:53,330
und 3 sollte auf der rechten Seite bis 6 zeigen.

346
00:25:53,330 --> 00:25:58,480
Ich denke, das wird ganz eingestellt. Irgendwelche Fragen oder Anmerkungen?

347
00:25:58,480 --> 00:26:02,060
[Student, unverständlich] Die Wurzel wird 7 sein.

348
00:26:02,060 --> 00:26:08,210
Wir können nur sagen, node * ptr =

349
00:26:08,210 --> 00:26:14,160
oder Wurzel = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Für unsere Zwecke werden wir mit Einsatz zu tun,

351
00:26:20,730 --> 00:26:25,490
so dass wir gehen zu wollen, um eine Funktion in dieser binären Baum einzufügen schreiben

352
00:26:25,490 --> 00:26:34,230
und Einsatz wird unweigerlich malloc anrufen, um einen neuen Knoten für diesen Baum zu schaffen.

353
00:26:34,230 --> 00:26:36,590
So die Dinge laufen, um sich mit der Tatsache, chaotisch, dass einige Knoten

354
00:26:36,590 --> 00:26:38,590
sind derzeit auf dem Stapel

355
00:26:38,590 --> 00:26:43,680
und andere Knoten gehen, um am Ende auf dem Heap, wenn wir sie einsetzen.

356
00:26:43,680 --> 00:26:47,640
Dies ist durchaus möglich, aber der einzige Grund,

357
00:26:47,640 --> 00:26:49,600
Wir sind in der Lage, dies auf dem Stack zu tun

358
00:26:49,600 --> 00:26:51,840
ist, weil es wie ein konstruiertes Beispiel, dass wir wissen, ist

359
00:26:51,840 --> 00:26:56,360
der Baum soll als 7, 3, 6, 9 ausgebildet sein.

360
00:26:56,360 --> 00:27:02,970
Wenn wir nicht diese, dann würden wir nicht malloc haben den ersten Platz.

361
00:27:02,970 --> 00:27:06,160
Als wir ein wenig später sehen werden, sollten wir malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Im Moment ist es durchaus sinnvoll, auf den Stapel gelegt,

363
00:27:08,570 --> 00:27:14,750
aber wir dies ändern, um eine malloc-Implementierung.

364
00:27:14,750 --> 00:27:17,160
So hat jeder von ihnen wird jetzt so etwas wie

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

366
00:27:24,240 --> 00:27:28,040
Und jetzt sind wir zu haben, um unsere Prüfung zu tun.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Ich wollte nicht, dass -

368
00:27:34,010 --> 00:27:40,950
1 zurück, und dann können wir node9-> zu tun, weil es jetzt ein Zeiger ist,

369
00:27:40,950 --> 00:27:45,300
Wert = 6, node9-> links = NULL,

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

371
00:27:48,930 --> 00:27:51,410
und wir gehen zu müssen, dass für jeden dieser Knoten zu tun.

372
00:27:51,410 --> 00:27:57,490
Anstatt also, sagen wir es innerhalb von einer separaten Funktion.

373
00:27:57,490 --> 00:28:00,620
Nennen wir es node * build_node,

374
00:28:00,620 --> 00:28:09,050
und dies ist ähnlich dem APIs wir für Huffman-Kodierung.

375
00:28:09,050 --> 00:28:12,730
Wir geben Ihnen initializer Funktionen für einen Baum

376
00:28:12,730 --> 00:28:20,520
und Deconstructor "Funktionen" für die Bäume und die gleichen für die Wälder.

377
00:28:20,520 --> 00:28:22,570
>> Also hier werden wir eine Initialisierung Funktion haben

378
00:28:22,570 --> 00:28:25,170
nur bauen einen Knoten für uns.

379
00:28:25,170 --> 00:28:29,320
Und es wird so ziemlich genauso aussehen wie diese.

380
00:28:29,320 --> 00:28:32,230
Und ich ging sogar faul zu sein und nicht die Namen der Variablen,

381
00:28:32,230 --> 00:28:34,380
obwohl node9 macht keinen Sinn mehr.

382
00:28:34,380 --> 00:28:38,610
Oh, ich denke, node9 der Wert sollte nicht 6 haben.

383
00:28:38,610 --> 00:28:42,800
Jetzt können wir wieder node9.

384
00:28:42,800 --> 00:28:49,550
Und hier sollten wir null zurück.

385
00:28:49,550 --> 00:28:52,690
Jeder einig Build-a-Knoten-Funktion?

386
00:28:52,690 --> 00:28:59,780
So, jetzt können wir nur nennen, um jeden Knoten mit einem bestimmten Wert und Null-Pointer zu bauen.

387
00:28:59,780 --> 00:29:09,750
Jetzt können wir so nennen, können wir tun, node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Und lassen Sie uns tun. . .

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

390
00:29:33,980 --> 00:29:39,330
Und nun wollen wir die Einrichtung der gleichen Zeiger,

391
00:29:39,330 --> 00:29:42,470
außer jetzt alles ist schon im Hinblick auf die Zeiger

392
00:29:42,470 --> 00:29:48,480
so müssen nicht mehr die Adresse.

393
00:29:48,480 --> 00:29:56,300
Okay. Also, was ist das letzte, was ich tun will?

394
00:29:56,300 --> 00:30:03,850
Es gibt einen Fehler-checking, dass ich nicht tun.

395
00:30:03,850 --> 00:30:06,800
Was bedeutet bauen Knoten zurück?

396
00:30:06,800 --> 00:30:11,660
[Student, unverständlich] >> Ja. Wenn malloc nicht, wird es null zurück.

397
00:30:11,660 --> 00:30:16,460
So werde ich faul put it down hier anstatt eine Bedingung für jede.

398
00:30:16,460 --> 00:30:22,320
Wenn (node9 == NULL, oder - noch einfacher,

399
00:30:22,320 --> 00:30:28,020
dies entspricht gerade wenn nicht node9.

400
00:30:28,020 --> 00:30:38,310
Also, wenn nicht node9 oder nicht node6 oder nicht node3 oder nicht node7, 1 zurück.

401
00:30:38,310 --> 00:30:42,850
Vielleicht sollten wir drucken malloc fehlgeschlagen, oder so etwas.

402
00:30:42,850 --> 00:30:46,680
[Student] Ist falsche gleich wie auch null?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Jeder Wert Null ist falsch.

404
00:30:51,290 --> 00:30:53,920
So null ist ein Nullwert.

405
00:30:53,920 --> 00:30:56,780
Zero ist ein Nullwert. Falsch ist ein Nullwert.

406
00:30:56,780 --> 00:31:02,130
Any - so ziemlich die einzigen 2 Null-Werte sind null und null,

407
00:31:02,130 --> 00:31:07,900
falsch ist nur Hash definiert als Null.

408
00:31:07,900 --> 00:31:13,030
Das gilt auch, wenn wir die globale Variable deklarieren müssen.

409
00:31:13,030 --> 00:31:17,890
Wenn wir hatten node * root hier oben,

410
00:31:17,890 --> 00:31:24,150
dann - die nette Sache über globale Variablen ist, dass sie immer einen Ausgangswert.

411
00:31:24,150 --> 00:31:27,500
Das ist nicht von Funktionen wahr, wie im Inneren von hier,

412
00:31:27,500 --> 00:31:34,870
wenn wir, wie der Knoten * oder Knoten x.

413
00:31:34,870 --> 00:31:37,380
Wir haben keine Ahnung, was x.Value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
oder wir könnten ausdrucken und sie konnten beliebig sein.

415
00:31:40,700 --> 00:31:44,980
Das ist nicht wahr von globalen Variablen.

416
00:31:44,980 --> 00:31:47,450
So Knoten root oder Knoten x.

417
00:31:47,450 --> 00:31:53,410
Standardmäßig alles, was global ist, wenn nicht ausdrücklich auf einen Wert initialisiert,

418
00:31:53,410 --> 00:31:57,390
einen Nullwert als Wert.

419
00:31:57,390 --> 00:32:01,150
Also hier, Knoten * root, wissen wir nicht explizit initialisieren es nichts,

420
00:32:01,150 --> 00:32:06,350
so ihren Standardwert ist null, das ist die Null-Wert von Zeigern.

421
00:32:06,350 --> 00:32:11,870
Der Standardwert von x wird bedeuten, dass x.Value Null ist,

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

423
00:32:14,260 --> 00:32:21,070
Zumal es sich um eine Struktur ist, wird alle Felder der Struktur Null-Werte sein.

424
00:32:21,070 --> 00:32:24,410
Wir brauchen nicht zu, dass hier verwenden, though.

425
00:32:24,410 --> 00:32:27,320
[Student] Die Strukturen unterscheiden sich von anderen Variablen, und die anderen Variablen sind

426
00:32:27,320 --> 00:32:31,400
Müll-Werte, das sind Nullen?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Andere Werte zu. So in x wird x gleich Null sein.

428
00:32:36,220 --> 00:32:40,070
Wenn es im globalen Bereich ist, hat es einen Anfangswert. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Entweder der Ausgangswert du hast es oder Null.

430
00:32:48,950 --> 00:32:53,260
Ich denke, das kümmert sich all dies.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Also das nächste Teil der Frage stellt,

432
00:32:58,390 --> 00:33:01,260
"Jetzt wollen wir eine Funktion namens enthält schreiben

433
00:33:01,260 --> 00:33:04,930
mit einem Prototyp bool enthält int-Wert. "

434
00:33:04,930 --> 00:33:08,340
Wir werden nicht zu tun bool enthält int-Wert.

435
00:33:08,340 --> 00:33:15,110
Unser Prototyp wird aussehen

436
00:33:15,110 --> 00:33:22,380
bool enthält (int-Wert.

437
00:33:22,380 --> 00:33:24,490
Und dann werden wir auch passieren sie den Baum

438
00:33:24,490 --> 00:33:28,870
daß sie sollten prüfen, ob es diesen Wert hat.

439
00:33:28,870 --> 00:33:38,290
So Knoten *-Baum). Okay.

440
00:33:38,290 --> 00:33:44,440
Und dann können wir es mit so etwas wie nennen,

441
00:33:44,440 --> 00:33:46,090
Vielleicht werden wir zu printf oder etwas wollen.

442
00:33:46,090 --> 00:33:51,040
Enthält 6, unsere Wurzel.

443
00:33:51,040 --> 00:33:54,300
Das sollte wieder ein, oder wahr,

444
00:33:54,300 --> 00:33:59,390
wohingegen enthält 5 root sollte false zurück.

445
00:33:59,390 --> 00:34:02,690
So nehmen Sie einen zweiten, um diese umzusetzen.

446
00:34:02,690 --> 00:34:06,780
Sie können es entweder iterativ oder rekursiv tun.

447
00:34:06,780 --> 00:34:09,739
Die nette Sache über die Art, wie wir die Dinge eingerichtet haben ist, dass

448
00:34:09,739 --> 00:34:12,300
bietet es sich an unseren rekursive Lösung viel einfacher

449
00:34:12,300 --> 00:34:14,719
als die globalen Variablen so tat.

450
00:34:14,719 --> 00:34:19,750
Denn wenn wir nur noch enthält int-Wert, dann haben wir keine Möglichkeit, rekursiv nach unten Teilbäume.

451
00:34:19,750 --> 00:34:24,130
Wir müssten einen separaten Hilfsfunktion, die sich rekursiv die Teilbäume für uns haben.

452
00:34:24,130 --> 00:34:29,610
Aber da haben wir geändert hat, um den Baum als Argument nehmen,

453
00:34:29,610 --> 00:34:32,760
die sollte es immer in erster Linie gewesen,

454
00:34:32,760 --> 00:34:35,710
jetzt können wir recurse leichter.

455
00:34:35,710 --> 00:34:38,960
So iterative oder rekursive, werden wir über beide gehen,

456
00:34:38,960 --> 00:34:46,139
aber wir, die rekursive endet als ganz einfach sehen.

457
00:34:59,140 --> 00:35:02,480
Okay. Hat jemand etwas mit dem wir arbeiten können?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Ich habe eine iterative Lösung. >> Alles klar, iterativ.

459
00:35:12,000 --> 00:35:16,030
Okay, das sieht gut aus.

460
00:35:16,030 --> 00:35:18,920
Also, wollen uns durch sie gehen?

461
00:35:18,920 --> 00:35:25,780
[Student] Sure. Also machte ich mich eine temporäre Variable, um den ersten Knoten des Baumes.

462
00:35:25,780 --> 00:35:28,330
Und dann habe ich einfach durchgeschleift, während Temperatur nicht gleich null,

463
00:35:28,330 --> 00:35:31,700
also, während noch in den Baum, schätze ich.

464
00:35:31,700 --> 00:35:35,710
Und wenn der Wert gleich dem Wert, Temp zeigt auf,

465
00:35:35,710 --> 00:35:37,640
dann ist dieser Wert zurückgegeben.

466
00:35:37,640 --> 00:35:40,210
Andernfalls wird geprüft, ob es auf der rechten Seite oder der linken Seite ist.

467
00:35:40,210 --> 00:35:43,400
Wenn Sie jemals eine Situation, wo es nicht mehr Baum,

468
00:35:43,400 --> 00:35:47,330
dann kehrt - es verlässt die Schleife und false zurückgegeben.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Also das scheint gut.

470
00:35:52,190 --> 00:35:58,470
Wer noch keine Kommentare zu irgendetwas?

471
00:35:58,470 --> 00:36:02,400
Ich habe keine Richtigkeit Kommentare überhaupt.

472
00:36:02,400 --> 00:36:11,020
Das Einzige, was wir tun können, ist dieser Kerl.

473
00:36:11,020 --> 00:36:21,660
Oh, es geht um eine kleine längliche gehen.

474
00:36:21,660 --> 00:36:33,460
Ich mache diese auf. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Jeder sollte daran erinnern, wie ternären funktioniert.

476
00:36:37,150 --> 00:36:38,610
Es haben definitiv in der Vergangenheit Quiz

477
00:36:38,610 --> 00:36:41,170
das Ihnen eine Funktion mit einem ternären Operator,

478
00:36:41,170 --> 00:36:45,750
und sagen, übersetzen diese, tun Sie etwas, das nicht verwendet ternären.

479
00:36:45,750 --> 00:36:49,140
Also das ist eine sehr häufige Fall, wenn ich denken würde, ternäre verwenden,

480
00:36:49,140 --> 00:36:54,610
wo, wenn eine bestimmte Bedingung eine Variable auf etwas,

481
00:36:54,610 --> 00:36:58,580
anderes festgelegt dieselbe Variable auf etwas anderes.

482
00:36:58,580 --> 00:37:03,390
Das ist etwas, das sehr häufig in diese Art der Sache umgewandelt werden

483
00:37:03,390 --> 00:37:14,420
wo gesetzt diese Variable dazu - oder, na ja, ist das wahr? Dann ist dieses, sonst dies.

484
00:37:14,420 --> 00:37:18,550
[Student] Die erste ist, wenn wahr, nicht wahr?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. So wie ich das lese immer es ist, gleich Temp Wert größer als Temp-Wert,

486
00:37:25,570 --> 00:37:30,680
dann, sonst diese. Es ist eine Frage stellen.

487
00:37:30,680 --> 00:37:35,200
Ist es größer? Dann tun Sie das erste, was. Anderes tun die zweite Sache.

488
00:37:35,200 --> 00:37:41,670
Ich bin fast immer - der Doppelpunkt, ich - in meinem Kopf, ich lese, wie andere.

489
00:37:41,670 --> 00:37:47,180
>> Hat jemand eine rekursive Lösung?

490
00:37:47,180 --> 00:37:49,670
Okay. Dieser wir gehst - es könnte schon groß sein,

491
00:37:49,670 --> 00:37:53,990
aber wir werden es noch besser machen.

492
00:37:53,990 --> 00:37:58,720
Das ist so ziemlich genau die gleiche Idee.

493
00:37:58,720 --> 00:38:03,060
Es ist nur gut, wollen Sie das erklären?

494
00:38:03,060 --> 00:38:08,340
[Student] Sure. Also werden wir darauf achten, dass der Baum nicht in erster null,

495
00:38:08,340 --> 00:38:13,380
denn wenn der Baum ist null dann wird es zur Rückkehr falsch, weil wir es nicht gefunden.

496
00:38:13,380 --> 00:38:19,200
Und wenn es noch ein Baum, wir in gehen - wir zunächst prüfen, ob der Wert ist der aktuelle Knoten.

497
00:38:19,200 --> 00:38:23,740
Return true, wenn es ist, und wenn wir nicht recurse auf der linken oder rechten Seite.

498
00:38:23,740 --> 00:38:25,970
Klingt das sinnvoll? >> Mm-hmm. (Vereinbarung)

499
00:38:25,970 --> 00:38:33,880
So bemerken, dass dieses fast - strukturell sehr ähnlich zu der iterativen Lösung.

500
00:38:33,880 --> 00:38:38,200
Es ist nur, dass anstelle der rekursiv wir eine while-Schleife hatte.

501
00:38:38,200 --> 00:38:40,840
Und die Base-Case hier, wo Baum nicht gleich null

502
00:38:40,840 --> 00:38:44,850
war die Bedingung, unter denen wir brach der while-Schleife.

503
00:38:44,850 --> 00:38:50,200
Sie sind sehr ähnlich. Aber wir werden noch einen Schritt weiter zu gehen.

504
00:38:50,200 --> 00:38:54,190
Jetzt machen wir dasselbe hier.

505
00:38:54,190 --> 00:38:57,680
Beachten wir wieder die gleiche Sache in diesen beiden Linien,

506
00:38:57,680 --> 00:39:00,220
ausgenommen ein Argument ist anders.

507
00:39:00,220 --> 00:39:07,950
So werden wir, dass in einem ternären machen.

508
00:39:07,950 --> 00:39:13,790
Ich traf Option etwas, und es machte ein Symbol. Okay.

509
00:39:13,790 --> 00:39:21,720
So werden wir zurückkehren enthält,.

510
00:39:21,720 --> 00:39:28,030
Dies ist immer auf mehrere Zeilen sein, gut, vergrößert es.

511
00:39:28,030 --> 00:39:31,060
Normalerweise als stilistische Sache, ich glaube nicht, viele Menschen

512
00:39:31,060 --> 00:39:38,640
ein Leerzeichen nach dem Pfeil, aber ich denke, wenn Sie im Einklang sind, ist es in Ordnung.

513
00:39:38,640 --> 00:39:44,320
Wenn der Wert weniger als Baum-Wert wollen wir recurse auf Baum links,

514
00:39:44,320 --> 00:39:53,890
Wir wollen also recurse auf Baum rechts.

515
00:39:53,890 --> 00:39:58,610
Das war also Schritt eins machen diesen Look kleiner.

516
00:39:58,610 --> 00:40:02,660
Schritt zwei machen diesen Look kleiner -

517
00:40:02,660 --> 00:40:09,150
Wir können diese auf mehrere Leitungen zu trennen.

518
00:40:09,150 --> 00:40:16,500
Okay. Schritt zwei ist damit kleiner aussehen ist hier,

519
00:40:16,500 --> 00:40:25,860
so Rückgabewert gleich Baum Wert, oder enthält whatever.

520
00:40:25,860 --> 00:40:28,340
>> Dies ist eine wichtige Sache.

521
00:40:28,340 --> 00:40:30,860
Ich bin mir nicht sicher, ob er sagte es explizit in der Klasse,

522
00:40:30,860 --> 00:40:34,740
aber es heißt Kurzschluss Auswertung.

523
00:40:34,740 --> 00:40:41,060
Die Idee hier ist value == Baum Wert.

524
00:40:41,060 --> 00:40:49,960
Wenn das wahr ist, dann ist dies wahr, und wir wollen "oder" dass mit dem, was ist hier.

525
00:40:49,960 --> 00:40:52,520
So ohne überhaupt darüber nachzudenken, was ist hier drüben,

526
00:40:52,520 --> 00:40:55,070
was ist der gesamte Ausdruck geht zurück?

527
00:40:55,070 --> 00:40:59,430
[Student] True? >> Ja, weil gilt für alles,

528
00:40:59,430 --> 00:41:04,990
verküpft - oder wahre verküpft mit etwas unbedingt wahr.

529
00:41:04,990 --> 00:41:08,150
So sobald wir Rückgabewert = Baum Wert sehen,

530
00:41:08,150 --> 00:41:10,140
wir gerade dabei, true zurückgeben.

531
00:41:10,140 --> 00:41:15,710
Nicht einmal zu recurse enthält ferner auf der ganzen Linie.

532
00:41:15,710 --> 00:41:20,980
Wir können noch einen Schritt weiter zu gehen.

533
00:41:20,980 --> 00:41:29,490
Zurück Baum nicht gleich null und das alles.

534
00:41:29,490 --> 00:41:32,650
Das machte es eine einzeilige Funktion.

535
00:41:32,650 --> 00:41:36,790
Dies ist auch ein Beispiel für Kurzschluss Auswertung.

536
00:41:36,790 --> 00:41:40,680
Aber jetzt ist es die gleiche Idee -

537
00:41:40,680 --> 00:41:47,320
statt - so wenn Baum nicht gleich null - oder, na ja,

538
00:41:47,320 --> 00:41:49,580
wenn Baum macht gleich null, das ist der schlimmen Fall,

539
00:41:49,580 --> 00:41:54,790
wenn Baum gleich null, dann ist die erste Bedingung wird falsch sein.

540
00:41:54,790 --> 00:42:00,550
So falsch mit etwas anded wird was?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Ja. Das ist die andere Hälfte der Kurzschluss Evaluierung,

542
00:42:04,640 --> 00:42:10,710
wo, wenn Baum nicht gleich null, dann werden wir nicht gehen, um selbst zu gehen -

543
00:42:10,710 --> 00:42:14,930
oder wenn Baum macht gleich null, dann werden wir nicht auf den Wert == Baum Wert zu tun.

544
00:42:14,930 --> 00:42:17,010
Wir gehen nur sofort false zurück.

545
00:42:17,010 --> 00:42:20,970
Was ist wichtig, da, wenn es nicht Kurzschluss evaluate,

546
00:42:20,970 --> 00:42:25,860
dann, wenn Baum macht gleich null ist, wird diese zweite Bedingung seg Fehler gehen,

547
00:42:25,860 --> 00:42:32,510
weil tree-> Wert wird Dereferenzierung null.

548
00:42:32,510 --> 00:42:40,490
So basta. Kann dies zu machen - zu verlagern einmal über.

549
00:42:40,490 --> 00:42:44,840
Dies ist eine sehr gewöhnliche Sache auch nicht machen diese eine Zeile mit diesem,

550
00:42:44,840 --> 00:42:49,000
aber es ist eine gemeinsame Sache in den Bedingungen, vielleicht stimmt hier nicht,

551
00:42:49,000 --> 00:42:59,380
aber wenn (Baum! = NULL und tree-> value == Wert), zu tun was auch immer.

552
00:42:59,380 --> 00:43:01,560
Dies ist eine sehr häufige Erkrankung, wo anstatt

553
00:43:01,560 --> 00:43:06,770
dies in zwei ifs zu brechen, wo mögen, ist der Baum null?

554
00:43:06,770 --> 00:43:11,780
Okay, es ist nicht null, so ist jetzt der Baum, der gleich Wert? Tun Sie dies.

555
00:43:11,780 --> 00:43:17,300
Stattdessen diese Bedingung, wird dies nie seg Fehler

556
00:43:17,300 --> 00:43:21,220
weil sie ausbrechen wird, wenn dies geschieht, um null sein.

557
00:43:21,220 --> 00:43:24,000
Nun, ich, wenn Ihr Baum ist ein komplett ungültigen Zeiger schätze, kann es noch seg Fehler,

558
00:43:24,000 --> 00:43:26,620
aber es kann nicht seg Schuld, wenn Baum ist null.

559
00:43:26,620 --> 00:43:32,900
Wenn es null wäre, wäre es zu brechen, bevor Sie den Mauszeiger immer in erster Linie dereferenziert.

560
00:43:32,900 --> 00:43:35,000
[Student] Ist das sogenannte Lazy Evaluation?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy Evaluation ist eine separate Sache.

562
00:43:40,770 --> 00:43:49,880
Lazy Evaluation ist mehr wie Sie für einen Wert zu fragen,

563
00:43:49,880 --> 00:43:54,270
Sie bitten, einen Wert, der Art der Berechnung, aber Sie brauchen es nicht sofort.

564
00:43:54,270 --> 00:43:59,040
So, bis Sie wirklich brauchen, ist es nicht ausgewertet.

565
00:43:59,040 --> 00:44:03,920
Dies ist nicht genau das gleiche, aber in der Huffman pset,

566
00:44:03,920 --> 00:44:06,520
er sagt, dass wir "faul" zu schreiben.

567
00:44:06,520 --> 00:44:08,670
Der Grund, warum wir das tun, weil wir eigentlich Pufferung sind die Schreib -

568
00:44:08,670 --> 00:44:11,820
wir wollen nicht auf einzelne Bits in einer Zeit zu schreiben,

569
00:44:11,820 --> 00:44:15,450
oder einzelne Bytes auf einmal, sondern wir wollen einen Chunk von Bytes zu erhalten.

570
00:44:15,450 --> 00:44:19,270
Dann, wenn wir ein Stück von Bytes haben, dann schreiben wir es heraus.

571
00:44:19,270 --> 00:44:22,640
Auch wenn Sie fragen, es zu schreiben - und fwrite und fread tun die gleiche Art von Ding.

572
00:44:22,640 --> 00:44:26,260
Sie puffern Ihren liest und schreibt.

573
00:44:26,260 --> 00:44:31,610
Auch wenn Sie darum bitten, sofort zu schreiben, ist es wahrscheinlich nicht.

574
00:44:31,610 --> 00:44:34,540
Und man kann nicht sicher sein, dass sich die Dinge geschrieben werden

575
00:44:34,540 --> 00:44:37,540
bis Sie hfclose oder rufen Sie, was es ist,

576
00:44:37,540 --> 00:44:39,620
was sagt dann, okay, ich schließe meine Datei,

577
00:44:39,620 --> 00:44:43,450
das heißt, ich würde besser schreiben, was ich nicht geschrieben noch.

578
00:44:43,450 --> 00:44:45,770
Es ist nicht nötig, alles zu schreiben,

579
00:44:45,770 --> 00:44:49,010
bis Sie die Datei zu schließen sind, und dann muss es.

580
00:44:49,010 --> 00:44:56,220
Also das ist genau das, was faul - er wartet, bis es zu geschehen hat.

581
00:44:56,220 --> 00:44:59,990
Diese - nehmen 51 und du wirst in es mehr ins Detail gehen,

582
00:44:59,990 --> 00:45:05,470
weil OCaml und alles in 51, ist alles Rekursion.

583
00:45:05,470 --> 00:45:08,890
Es wurden noch keine iterativen Lösungen, im Grunde.

584
00:45:08,890 --> 00:45:11,550
Alles ist Rekursion und lazy evaluation

585
00:45:11,550 --> 00:45:14,790
sein wird für eine Menge von Umständen wichtig

586
00:45:14,790 --> 00:45:19,920
wo, wenn Sie nicht faul zu bewerten hat, würde das bedeuten, -

587
00:45:19,920 --> 00:45:24,760
Das Beispiel ist Bäche, die unendlich lang sind.

588
00:45:24,760 --> 00:45:30,990
In der Theorie kann man der natürlichen Zahlen als ein Strom von 1-2-3-4-5-6-7 denken,

589
00:45:30,990 --> 00:45:33,090
So lässig beurteilt die Dinge sind in Ordnung.

590
00:45:33,090 --> 00:45:37,210
Wenn ich sage, ich will das zehnte Nummer, dann kann ich beurteilen bis zum zehnten Nummer.

591
00:45:37,210 --> 00:45:40,300
Wenn ich das hundertste Zahl wollen, dann kann ich beurteilen bis zum hundertsten Nummer.

592
00:45:40,300 --> 00:45:46,290
Ohne lazy evaluation, dann wird es zu versuchen, alle Nummern sofort auszuwerten.

593
00:45:46,290 --> 00:45:50,000
Du bist Auswertung unendlich viele Zahlen, und das ist einfach nicht möglich.

594
00:45:50,000 --> 00:45:52,080
So gibt es eine Menge von Fällen, in denen lazy evaluation

595
00:45:52,080 --> 00:45:57,840
ist nur wichtig, dass die Dinge funktionieren.

596
00:45:57,840 --> 00:46:05,260
>> Jetzt wollen wir insert schreiben, wo Einsatz sein wird

597
00:46:05,260 --> 00:46:08,430
ähnlich Änderung in seiner Definition.

598
00:46:08,430 --> 00:46:10,470
So jetzt ist es bool insert (int value).

599
00:46:10,470 --> 00:46:23,850
Wir werden, dass die bool insert (int value, Knoten *-Baum) zu ändern.

600
00:46:23,850 --> 00:46:29,120
Wir tatsächlich zu, dass wieder ändern in ein bisschen, wir werden sehen warum.

601
00:46:29,120 --> 00:46:32,210
Und lassen Sie uns zu bewegen build_node, nur für das Heck von ihm,

602
00:46:32,210 --> 00:46:36,730
oben legen, damit wir nicht haben, um einen Funktionsprototyp schreiben.

603
00:46:36,730 --> 00:46:42,450
Was ist ein Hinweis, dass du gehst zu sein mit build_node in Einsatz.

604
00:46:42,450 --> 00:46:49,590
Okay. Nehmen Sie eine Minute dafür.

605
00:46:49,590 --> 00:46:52,130
Ich glaube, ich rettete die Revision, wenn Sie von dem ziehen wollen,

606
00:46:52,130 --> 00:47:00,240
oder zumindest habe ich jetzt.

607
00:47:00,240 --> 00:47:04,190
Ich wollte eine leichte Pause, um über die Logik des Einsatzes denken,

608
00:47:04,190 --> 00:47:08,750
wenn man nicht daran zu denken.

609
00:47:08,750 --> 00:47:12,860
Grundsätzlich werden Sie immer nur an Blättern, hinzugefügt.

610
00:47:12,860 --> 00:47:18,640
Wie, wenn ich 1 einzulegen, dann bin ich unweigerlich zu Einfügen 1 -

611
00:47:18,640 --> 00:47:21,820
Ich werde in Schwarz zu ändern - ich werde sein Einsetzen 1 hier.

612
00:47:21,820 --> 00:47:28,070
Oder wenn ich 4 einzufügen, möchte ich sein Einsetzen 4 über hier.

613
00:47:28,070 --> 00:47:32,180
Also egal, was du tust, wirst du auf ein Blatt, hinzugefügt.

614
00:47:32,180 --> 00:47:36,130
Alles, was Sie tun müssen, ist zu durchlaufen den Baum, bis Sie auf den Knoten zu erhalten

615
00:47:36,130 --> 00:47:40,890
das sollte dem Knoten übergeordneten, des neuen Knotens Elternteil zu sein,

616
00:47:40,890 --> 00:47:44,560
und ändern ihre linken oder rechten Zeiger, je nachdem, ob

617
00:47:44,560 --> 00:47:47,060
es größer oder kleiner als der aktuelle Knoten.

618
00:47:47,060 --> 00:47:51,180
Ändern Sie den Zeiger, um Ihre neuen Knoten zeigen.

619
00:47:51,180 --> 00:48:05,490
So durchlaufen den Baum, um das Blatt auf den neuen Knoten.

620
00:48:05,490 --> 00:48:09,810
Auch darüber, warum, dass verbietet die Art von Situation, bevor denken,

621
00:48:09,810 --> 00:48:17,990
wo ich baute die binären Baum, wo es richtig war

622
00:48:17,990 --> 00:48:19,920
wenn Sie sah nur an einem einzigen Knoten

623
00:48:19,920 --> 00:48:24,830
aber 9 war auf der linken Seite 7, wenn Sie unten iteriert den ganzen Weg.

624
00:48:24,830 --> 00:48:29,770
Damit ist unmöglich in diesem Szenario, da -

625
00:48:29,770 --> 00:48:32,530
denken über das Einfügen von 9 oder etwas, auf den ersten Knoten

626
00:48:32,530 --> 00:48:35,350
Ich werde bis 7 zu sehen und ich werde einfach nach rechts zu gehen.

627
00:48:35,350 --> 00:48:38,490
Also egal, was ich tue, wenn ich, indem Sie auf ein Blatt einfügen,

628
00:48:38,490 --> 00:48:40,790
und zu einem Blatt mit dem entsprechenden Algorithmus,

629
00:48:40,790 --> 00:48:43,130
es wird unmöglich sein, für mich 9 auf der linken Seite 7 einsetzen, um

630
00:48:43,130 --> 00:48:48,250
denn sobald ich 7 getroffen werde ich nach rechts gehen.

631
00:48:59,740 --> 00:49:02,070
Hat jemand etwas mit anfangen?

632
00:49:02,070 --> 00:49:05,480
[Student] ich. >> Sure.

633
00:49:05,480 --> 00:49:09,200
[Student, unverständlich]

634
00:49:09,200 --> 00:49:14,390
[Other Student, unverständlich]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Es ist geschätzt. Okay. Möchten Sie das erklären?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Da wir wissen, dass wir das Einfügen

637
00:49:20,690 --> 00:49:24,060
neue Knoten am Ende des Baums,

638
00:49:24,060 --> 00:49:28,070
Ich durchgeschleift Baum iterativ

639
00:49:28,070 --> 00:49:31,360
bis ich zu einem Knoten, auf null hingewiesen.

640
00:49:31,360 --> 00:49:34,220
Und dann habe ich beschlossen, es entweder man auf der rechten Seite oder der linken Seite

641
00:49:34,220 --> 00:49:37,420
dieses Recht in variable, es hat mir gesagt, wohin damit.

642
00:49:37,420 --> 00:49:41,850
Und dann, im Wesentlichen, Ich habe gerade das letzte -

643
00:49:41,850 --> 00:49:47,520
daß temporäre Knotenpunkt an den neuen Knoten, die es wurde schaffen,

644
00:49:47,520 --> 00:49:50,770
entweder auf der linken oder auf der rechten Seite, je nachdem, was der Wert richtig war.

645
00:49:50,770 --> 00:49:56,530
Schließlich habe ich den neuen Knoten auf den Wert ihrer Prüfung.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okay, so sehe ich ein Problem hier.

647
00:49:59,550 --> 00:50:02,050
Das ist wie 95% der Weg dorthin.

648
00:50:02,050 --> 00:50:07,550
Das einzige Problem, das ich sehe, na ja, hat jemand anderes sehen ein Problem?

649
00:50:07,550 --> 00:50:18,400
Was ist der Umstand, unter dem sie brechen aus der Schleife?

650
00:50:18,400 --> 00:50:22,100
[Student] Wenn temp ist null? >> Ja. So, wie Sie brechen aus der Schleife ist, wenn temp ist null.

651
00:50:22,100 --> 00:50:30,220
Aber was soll ich tun hier richtig?

652
00:50:30,220 --> 00:50:35,410
Ich dereference temp, die zwangsläufig null ist.

653
00:50:35,410 --> 00:50:39,840
So die andere Sache, die Sie tun müssen, ist nicht nur behalten, bis temp ist null,

654
00:50:39,840 --> 00:50:45,590
Sie wollen den Überblick über die Muttergesellschaft halten zu allen Zeiten.

655
00:50:45,590 --> 00:50:52,190
Wir wollen auch Knoten * parent, ich denke, wir können das bei null auf den ersten zu halten.

656
00:50:52,190 --> 00:50:55,480
Das wird seltsame Verhalten für die Wurzel des Baumes haben,

657
00:50:55,480 --> 00:50:59,210
aber wir werden dazu kommen.

658
00:50:59,210 --> 00:51:03,950
Wenn der Wert größer ist als was auch immer, dann temp: = temp rechts.

659
00:51:03,950 --> 00:51:07,910
Doch bevor wir das tun, parent = temp.

660
00:51:07,910 --> 00:51:14,500
Oder sind die Eltern immer zu gleicher temp? Ist das der Fall?

661
00:51:14,500 --> 00:51:19,560
Wenn Temp nicht null ist, dann werde ich nach unten zu bewegen, egal was,

662
00:51:19,560 --> 00:51:24,030
zu einem Knoten, für die temp ist die Muttergesellschaft.

663
00:51:24,030 --> 00:51:27,500
So Muttergesellschaft geht zu temp, und dann bewege ich mich Temp unten.

664
00:51:27,500 --> 00:51:32,410
Jetzt temp ist null, aber Mutter verweist auf die Muttergesellschaft der Sache, die null ist.

665
00:51:32,410 --> 00:51:39,110
So hier unten, ich will nicht um rechts gleich 1 ist.

666
00:51:39,110 --> 00:51:41,300
Also zog ich nach rechts, so dass, wenn rechts = 1,

667
00:51:41,300 --> 00:51:45,130
und ich denke, Sie wollen auch zu tun -

668
00:51:45,130 --> 00:51:48,530
wenn Sie an der linken Seite, Sie wollen richtig eingestellt gleich 0 ist.

669
00:51:48,530 --> 00:51:55,950
Oder wenn Sie jemals nach rechts zu bewegen.

670
00:51:55,950 --> 00:51:58,590
So rechts = 0. Wenn rechts = 1,

671
00:51:58,590 --> 00:52:04,260
Jetzt wollen wir das übergeordnete Recht Zeiger newNode machen,

672
00:52:04,260 --> 00:52:08,520
Wir wollen also das übergeordnete linken Zeiger newNode machen.

673
00:52:08,520 --> 00:52:16,850
Fragen dazu?

674
00:52:16,850 --> 00:52:24,880
Okay. Das ist also die Art, wie wir - na ja, eigentlich, anstatt dies zu tun,

675
00:52:24,880 --> 00:52:29,630
wir die Hälfte erwartet, dass du build_node verwenden.

676
00:52:29,630 --> 00:52:40,450
Und dann, wenn newNode gleich null, false zurück.

677
00:52:40,450 --> 00:52:44,170
Basta. Nun, dies ist, was wir Ihnen zu tun erwartet.

678
00:52:44,170 --> 00:52:47,690
>> Dies ist, was die Mitarbeiter Lösungen zu tun.

679
00:52:47,690 --> 00:52:52,360
Ich bin nicht einverstanden mit diesem als der "richtigen" Weg zu gehen darüber

680
00:52:52,360 --> 00:52:57,820
aber das ist völlig in Ordnung, und es wird funktionieren.

681
00:52:57,820 --> 00:53:02,840
Eine Sache, die ein wenig seltsam stimmt ist jetzt

682
00:53:02,840 --> 00:53:08,310
wenn der Baum beginnt als null, wir in einer null Baum passieren.

683
00:53:08,310 --> 00:53:12,650
Ich denke, es hängt davon ab, wie definieren Sie das Verhalten der Übergabe eines null Baum.

684
00:53:12,650 --> 00:53:15,490
Ich würde denken, dass, wenn Sie in einem null Baum übergeben,

685
00:53:15,490 --> 00:53:17,520
dann Einsetzen des Wertes in einem Null-Baum

686
00:53:17,520 --> 00:53:23,030
sollte einfach einen Baum, wo der einzige Wert ist, dass einzelne Knoten.

687
00:53:23,030 --> 00:53:25,830
Haben die Leute stimmen dem zu? Man könnte, wenn man wollte,

688
00:53:25,830 --> 00:53:28,050
Übergeben Sie in einem null Baum

689
00:53:28,050 --> 00:53:31,320
und Sie einen Wert in sie einfügen möchten, false zurück.

690
00:53:31,320 --> 00:53:33,830
Es ist an Ihnen, daß definieren.

691
00:53:33,830 --> 00:53:38,320
Um das erste, was ich sagte und dann -

692
00:53:38,320 --> 00:53:40,720
gut, wirst du Schwierigkeiten damit, dass zu haben, weil

693
00:53:40,720 --> 00:53:44,090
Es wäre einfacher, wenn wir einen globalen Zeiger zu der Sache hatte,

694
00:53:44,090 --> 00:53:48,570
aber wir wissen nicht, also, wenn Baum ist null, es gibt nichts, was wir dagegen tun können.

695
00:53:48,570 --> 00:53:50,960
Wir können nur false zurück.

696
00:53:50,960 --> 00:53:52,840
So werde ich einfügen ändern.

697
00:53:52,840 --> 00:53:56,540
Wir technisch könnte nur ändern Sie diese hier,

698
00:53:56,540 --> 00:53:58,400
wie es über die Dinge Iteration,

699
00:53:58,400 --> 00:54:04,530
aber ich werde Einsatz verändern Werfen Sie einen Knoten ** Baum.

700
00:54:04,530 --> 00:54:07,510
Doppel-Zeiger.

701
00:54:07,510 --> 00:54:09,710
Was bedeutet das?

702
00:54:09,710 --> 00:54:12,330
Statt sich mit Zeigern auf Knoten,

703
00:54:12,330 --> 00:54:16,690
das, was ich gehen zu manipulieren bin ist dieser Zeiger.

704
00:54:16,690 --> 00:54:18,790
Ich werde zu manipulieren diesen Zeiger.

705
00:54:18,790 --> 00:54:21,770
Ich werde zu manipulieren Pointer direkt.

706
00:54:21,770 --> 00:54:25,760
Dies macht Sinn, da über sich denken -

707
00:54:25,760 --> 00:54:33,340
gut, jetzt deutet dies auf null.

708
00:54:33,340 --> 00:54:38,130
Was ich tun möchte, ist zu manipulieren diesen Zeiger verweisen auf nicht null.

709
00:54:38,130 --> 00:54:40,970
Ich will es auf meine neuen Knoten zeigen.

710
00:54:40,970 --> 00:54:44,870
Wenn ich nur verfolgen Zeiger auf meiner Zeiger,

711
00:54:44,870 --> 00:54:47,840
dann brauche ich nicht den Überblick eines Elternteils Zeiger zu halten.

712
00:54:47,840 --> 00:54:52,640
Ich kann nur verfolgen, um zu sehen, ob der Zeiger zeigt auf null

713
00:54:52,640 --> 00:54:54,580
und wenn der Zeiger zeigt auf null

714
00:54:54,580 --> 00:54:57,370
ändern, um den Knoten Ich möchte darauf hinweisen.

715
00:54:57,370 --> 00:55:00,070
Und ich kann es ändern, da ich einen Zeiger auf den Zeiger haben.

716
00:55:00,070 --> 00:55:02,040
Lassen Sie uns dieses Recht jetzt zu sehen.

717
00:55:02,040 --> 00:55:05,470
Sie können tatsächlich tun es rekursiv ziemlich leicht.

718
00:55:05,470 --> 00:55:08,080
Wollen wir das?

719
00:55:08,080 --> 00:55:10,980
Ja, das tun wir.

720
00:55:10,980 --> 00:55:16,790
>> Mal sehen, es rekursiv.

721
00:55:16,790 --> 00:55:24,070
Zunächst wird, was unserem Basisszenario gehen zu sein?

722
00:55:24,070 --> 00:55:29,140
Fast immer unser Basisszenario, aber eigentlich ist diese Art von tricky.

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

724
00:55:34,370 --> 00:55:37,550
Ich denke, wir sind gerade dabei, false zurück.

725
00:55:37,550 --> 00:55:40,460
Dies unterscheidet sich von Ihrem Baum ist null.

726
00:55:40,460 --> 00:55:44,510
Dies ist der Zeiger auf Ihr Root-Zeiger ist null

727
00:55:44,510 --> 00:55:48,360
was bedeutet, dass Ihr Root-Zeiger existiert nicht.

728
00:55:48,360 --> 00:55:52,390
So hier unten, wenn ich

729
00:55:52,390 --> 00:55:55,760
node * - lasst uns einfach wiederverwenden dies.

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

731
00:55:58,960 --> 00:56:00,730
und dann werde ich einfügen, indem Sie etwas wie nennen,

732
00:56:00,730 --> 00:56:04,540
legen Sie 4 in & root.

733
00:56:04,540 --> 00:56:06,560
So & Root, wenn root ein Knoten * ist

734
00:56:06,560 --> 00:56:11,170
dann & root wird ein Knoten ** sein.

735
00:56:11,170 --> 00:56:15,120
Dies ist gültig. In diesem Fall, Baum, hier oben,

736
00:56:15,120 --> 00:56:20,120
Baum ist nicht null - oder Beilage.

737
00:56:20,120 --> 00:56:24,630
Here. Baum ist nicht null; * Baum ist null, was in Ordnung ist

738
00:56:24,630 --> 00:56:26,680
denn wenn *-Baum null ist, dann kann ich manipulieren

739
00:56:26,680 --> 00:56:29,210
jetzt, was ich will es Punkt zu Punkt.

740
00:56:29,210 --> 00:56:34,750
Aber wenn Baum ist null, dh ich kam gerade hier unten und sagte: null.

741
00:56:34,750 --> 00:56:42,710
Das macht keinen Sinn. Ich kann nicht alles tun, damit.

742
00:56:42,710 --> 00:56:45,540
Wenn Baum ist null, false zurück.

743
00:56:45,540 --> 00:56:48,220
So habe ich im Grunde schon gesagt, was unsere wirkliche Basis Fall ist.

744
00:56:48,220 --> 00:56:50,580
Und was ist das denn sein?

745
00:56:50,580 --> 00:56:55,030
[Student, unverständlich]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ja. So if (* baum == NULL).

747
00:57:00,000 --> 00:57:04,520
Dies bezieht sich auf den Fall hier

748
00:57:04,520 --> 00:57:09,640
wo, wenn meine roten Zeiger ist der Zeiger Ich bin auf konzentriert,

749
00:57:09,640 --> 00:57:12,960
so wie ich auf dieses Zeigers bin konzentriert, jetzt bin ich auf dieser Zeiger konzentriert.

750
00:57:12,960 --> 00:57:15,150
Jetzt bin ich auf dieses Zeigers konzentriert.

751
00:57:15,150 --> 00:57:18,160
Also, wenn meine roten Zeiger, die mein Knoten ** ist,

752
00:57:18,160 --> 00:57:22,880
ist immer - wenn *, mein roter Zeiger, ist immer null,

753
00:57:22,880 --> 00:57:28,470
das bedeutet, dass ich in dem Fall, dass ich auf einem Zeiger, der Schwerpunkt werde Uhr -

754
00:57:28,470 --> 00:57:32,530
dies ist ein Zeiger, der zu einem Blatt gehört.

755
00:57:32,530 --> 00:57:41,090
Ich möchte dieses Zeigers zu ändern, um zu meinem neuen Knoten zeigen.

756
00:57:41,090 --> 00:57:45,230
Komm zurück hierher.

757
00:57:45,230 --> 00:57:56,490
Meine newNode werden nur Knoten * n = build_node (Wert)

758
00:57:56,490 --> 00:58:07,300
Dann n, wenn n = NULL, false zurück.

759
00:58:07,300 --> 00:58:12,600
Else wollen wir ändern, was der Zeiger derzeit zeigt

760
00:58:12,600 --> 00:58:17,830
jetzt unseren neu gebauten Knoten zeigen.

761
00:58:17,830 --> 00:58:20,280
Wir können tatsächlich das hier tun.

762
00:58:20,280 --> 00:58:30,660
Anstatt zu sagen, n, sagen wir *-Baum = if *-Baum.

763
00:58:30,660 --> 00:58:35,450
Jeder verstehen? Das durch den Umgang mit Zeigern auf Zeiger,

764
00:58:35,450 --> 00:58:40,750
wir ändern können Null-Pointer, um Dinge, die wir wollen, dass sie darauf hinweisen.

765
00:58:40,750 --> 00:58:42,820
Das ist unser Basis-Szenario.

766
00:58:42,820 --> 00:58:45,740
>> Jetzt ist unsere Wiederkehr, oder unsere Rekursion

767
00:58:45,740 --> 00:58:51,430
wird sehr ähnlich sein zu allen anderen Rekursionen wir getan haben.

768
00:58:51,430 --> 00:58:55,830
Wir gehen zu wollen, Wert legen,

769
00:58:55,830 --> 00:58:59,040
und jetzt werde ich ternären wieder zu verwenden, sondern das, was unsere Lage sein wird?

770
00:58:59,040 --> 00:59:05,180
Was ist es wir nach, um zu entscheiden, ob wir links oder rechts gehen möchten suchen?

771
00:59:05,180 --> 00:59:07,760
Lasst es uns in getrennten Schritten.

772
00:59:07,760 --> 00:59:18,850
If (value <), was?

773
00:59:18,850 --> 00:59:23,200
[Student] Der Baum der Wert?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Also denken Sie daran, dass ich derzeit bin -

775
00:59:27,490 --> 00:59:31,260
[Studenten, unverständlich]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, so hier, sagen wir mal, dass diese grünen Pfeil

777
00:59:34,140 --> 00:59:39,050
ist ein Beispiel dafür, was Baum derzeit ist, ist ein Zeiger auf diesen Zeiger.

778
00:59:39,050 --> 00:59:46,610
Das heißt also Ich bin ein Zeiger auf einen Zeiger auf 3.

779
00:59:46,610 --> 00:59:48,800
Die Dereferenzierung zweimal klang gut.

780
00:59:48,800 --> 00:59:51,010
Was muss ich - wie mache ich das?

781
00:59:51,010 --> 00:59:53,210
[Student] Dereference einmal, und dann tun arrow so?

782
00:59:53,210 --> 00:59:58,420
[Bowden] So (*-Baum) ist die Dereferenzierung einmal -> Wert

783
00:59:58,420 --> 01:00:05,960
wird mir den Wert des Knotens, dass ich indirekt wies auf.

784
01:00:05,960 --> 01:00:11,980
So kann ich auch schreiben, ** tree.value, wenn Sie das bevorzugen.

785
01:00:11,980 --> 01:00:18,490
Entweder funktioniert.

786
01:00:18,490 --> 01:00:26,190
Wenn das der Fall ist, dann möchte ich nennen einfügen mit dem Wert.

787
01:00:26,190 --> 01:00:32,590
Und was meine aktualisierte Knoten ** sein wird?

788
01:00:32,590 --> 01:00:39,440
Ich will nach links gehen, so ** baum.links wird zu meiner Linken sein.

789
01:00:39,440 --> 01:00:41,900
Und ich will den Zeiger auf diese Sache

790
01:00:41,900 --> 01:00:44,930
so daß, wenn der linke endet als der Null-Zeiger,

791
01:00:44,930 --> 01:00:48,360
Ich kann es ändern, um meine neuen Knoten zeigen.

792
01:00:48,360 --> 01:00:51,460
>> Und der andere Fall können sehr ähnlich.

793
01:00:51,460 --> 01:00:55,600
Lasst uns eigentlich, dass meine ternären jetzt machen.

794
01:00:55,600 --> 01:01:04,480
Legen Sie Wert, wenn Wert <(** Baum). Wert.

795
01:01:04,480 --> 01:01:11,040
Dann wollen wir unsere ** auf der linken Seite zu aktualisieren,

796
01:01:11,040 --> 01:01:17,030
was wir wollen unsere ** auf der rechten Seite zu aktualisieren.

797
01:01:17,030 --> 01:01:22,540
[Student] Heißt das bekommen Sie den Zeiger auf den Zeiger?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Beachten Sie, dass - ** baum.rechts ein Knoten Stern ist.

799
01:01:30,940 --> 01:01:35,040
[Student, unverständlich] >> Ja.

800
01:01:35,040 --> 01:01:41,140
** Baum.rechts ist wie dieses Zeigers oder so etwas.

801
01:01:41,140 --> 01:01:45,140
So, indem sie einen Zeiger auf, dass, das gibt mir, was ich will

802
01:01:45,140 --> 01:01:50,090
der Zeiger auf diesen Kerl.

803
01:01:50,090 --> 01:01:54,260
[Student] Könnten wir gehen immer wieder, warum wir mit den beiden Zeiger werden?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Also - nein, man kann, und diese Lösung vor

805
01:01:58,220 --> 01:02:04,540
war ein Weg, es zu tun, ohne dabei zwei Zeigern.

806
01:02:04,540 --> 01:02:08,740
Sie müssen in der Lage sein zu verstehen, mit zwei Zeigern,

807
01:02:08,740 --> 01:02:11,660
und dies ist eine saubere Lösung.

808
01:02:11,660 --> 01:02:16,090
Beachten Sie auch, dass, wenn mein Baum geschieht -

809
01:02:16,090 --> 01:02:24,480
Was passiert, wenn meine Wurzel war null? Was passiert, wenn ich diesen Fall hier zu tun?

810
01:02:24,480 --> 01:02:30,540
So node * root = NULL, legen Sie 4 in & root.

811
01:02:30,540 --> 01:02:35,110
Was ist root werde nach sein?

812
01:02:35,110 --> 01:02:37,470
[Student, unverständlich] >> Ja.

813
01:02:37,470 --> 01:02:41,710
Wurzelwert wird 4 sein.

814
01:02:41,710 --> 01:02:45,510
Root links sein wird null, wird root rechten werde null sein.

815
01:02:45,510 --> 01:02:49,490
In dem Fall, wo man nicht bestanden Wurzel nach Adressen,

816
01:02:49,490 --> 01:02:52,490
konnten wir nicht ändern root.

817
01:02:52,490 --> 01:02:56,020
In dem Fall, wo der Baum - wo Wurzel war null,

818
01:02:56,020 --> 01:02:58,410
wir mussten nur false zurück. Es gibt nichts, was wir tun konnten.

819
01:02:58,410 --> 01:03:01,520
Wir können nicht einfügen einen Knoten in einen leeren Baum.

820
01:03:01,520 --> 01:03:06,810
Aber jetzt können wir, wir machen nur eine leere Baum in einem Ein-Knoten-Baum.

821
01:03:06,810 --> 01:03:13,400
Welches ist in der Regel die erwarteten, dass es angenommen hat, um zu arbeiten.

822
01:03:13,400 --> 01:03:21,610
>> Darüber hinaus ist diese deutlich kürzer als

823
01:03:21,610 --> 01:03:26,240
Auch die Verfolgung der Eltern, und so durchlaufen Sie alle den Weg.

824
01:03:26,240 --> 01:03:30,140
Jetzt habe ich meine Eltern, und ich habe nur meine Eltern rechten Zeiger auf das was auch immer.

825
01:03:30,140 --> 01:03:35,640
Stattdessen, wenn wir dies taten iterativ, wäre es die gleiche Idee mit einer while-Schleife.

826
01:03:35,640 --> 01:03:38,100
Aber anstatt mit meinen Eltern Zeiger umzugehen,

827
01:03:38,100 --> 01:03:40,600
Statt meiner aktuellen Zeiger wäre die Sache

828
01:03:40,600 --> 01:03:43,790
dass ich direkt ändern zu meinem neuen Knoten zeigen.

829
01:03:43,790 --> 01:03:46,090
Ich habe nicht mit, ob es nach links zeigt umzugehen.

830
01:03:46,090 --> 01:03:48,810
Ich habe nicht mit, ob es nach rechts zeigt umzugehen.

831
01:03:48,810 --> 01:04:00,860
Es ist nur, was dieser Zeiger ist, ich werde es auf meine neuen Knoten zeigen.

832
01:04:00,860 --> 01:04:05,740
Jeder verstehen, wie es funktioniert?

833
01:04:05,740 --> 01:04:09,460
Wenn nicht, warum wollen wir es auf diese Weise,

834
01:04:09,460 --> 01:04:14,920
aber zumindest, dass dies funktioniert als Lösung?

835
01:04:14,920 --> 01:04:17,110
[Student] Wo stehen wir return true?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Das ist wahrscheinlich genau hier.

837
01:04:21,550 --> 01:04:26,690
Wenn wir richtig eingesetzt ist, true zurückgeben.

838
01:04:26,690 --> 01:04:32,010
Else, hier unten sind wir gehen zu wollen, was auch immer Insert Returns zurückzukehren.

839
01:04:32,010 --> 01:04:35,950
>> Und was ist das Besondere an diesem rekursive Funktion?

840
01:04:35,950 --> 01:04:43,010
Es ist endrekursiv, so lange, wie wir mit einigen Optimierungen zu kompilieren,

841
01:04:43,010 --> 01:04:48,060
es wird erkennen, dass und du wirst nie einen Stack-Überlauf davon

842
01:04:48,060 --> 01:04:53,230
auch wenn unser Baum hat eine Höhe von 10.000 oder 10 Millionen.

843
01:04:53,230 --> 01:04:55,630
[Student, unverständlich]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Ich denke, es tut bei Dash - oder was Optimierungsstufe

845
01:05:00,310 --> 01:05:03,820
ist für einen Endrekursion zu erkennenden erforderlich.

846
01:05:03,820 --> 01:05:09,350
Ich denke, es erkennt - GCC und Clang

847
01:05:09,350 --> 01:05:12,610
auch unterschiedliche Bedeutung für deren Optimierung Ebenen.

848
01:05:12,610 --> 01:05:17,870
Ich möchte sagen, es ist DashO 2, für sicher, dass es Endrekursion erkennen.

849
01:05:17,870 --> 01:05:27,880
Aber wir - man konnte wie ein Fibonocci Beispiel oder etwas zu bauen.

850
01:05:27,880 --> 01:05:30,030
Es ist nicht leicht, mit diesem Test, da es schwierig ist, zu konstruieren

851
01:05:30,030 --> 01:05:32,600
ein binärer Baum, der so groß ist.

852
01:05:32,600 --> 01:05:37,140
Aber ja, ich denke es ist DashO 2, dass

853
01:05:37,140 --> 01:05:40,580
wenn Sie kompilieren mit DashO 2, wird es für Endrekursion aussehen

854
01:05:40,580 --> 01:05:54,030
und optimieren, dass aus.

855
01:05:54,030 --> 01:05:58,190
Gehen wir zurück zu - einzufügen ist buchstäblich das letzte, was er braucht.

856
01:05:58,190 --> 01:06:04,900
Gehen wir zurück zu dem Einsatz hier

857
01:06:04,900 --> 01:06:07,840
wohin wir gehen, um die gleiche Idee zu tun.

858
01:06:07,840 --> 01:06:14,340
Es wird immer noch den Fehler nicht in der Lage vollständig zu behandeln

859
01:06:14,340 --> 01:06:17,940
wenn die Wurzel selbst ist null, oder die Vergangenheit Eintrag ist null,

860
01:06:17,940 --> 01:06:20,060
aber anstatt den Umgang mit einem Elternteil Zeiger,

861
01:06:20,060 --> 01:06:27,430
Wenden Sie das gleiche Logik zu halten Zeiger auf Zeiger.

862
01:06:27,430 --> 01:06:35,580
Wenn hier halten wir unsere Knoten ** Aktuell,

863
01:06:35,580 --> 01:06:37,860
und wir brauchen nicht zu verfolgen mehr richtig,

864
01:06:37,860 --> 01:06:47,190
aber Knoten ** cur = & Baum.

865
01:06:47,190 --> 01:06:54,800
Und nun unsere while-Schleife sein wird, während * Aktuell nicht gleich null.

866
01:06:54,800 --> 01:07:00,270
Brauchen Sie nicht den Überblick über die Eltern mehr zu halten.

867
01:07:00,270 --> 01:07:04,180
Brauchen Sie nicht den Überblick über links und rechts halten.

868
01:07:04,180 --> 01:07:10,190
Und ich nenne es temp, weil wir bereits sind temp.

869
01:07:10,190 --> 01:07:17,200
Okay. So if (Wert> * temp)

870
01:07:17,200 --> 01:07:24,010
dann & (* temp) -> rechts

871
01:07:24,010 --> 01:07:29,250
else temp = & (* temp) -> links.

872
01:07:29,250 --> 01:07:32,730
Und jetzt, an diesem Punkt, nach dieser while-Schleife,

873
01:07:32,730 --> 01:07:36,380
Ich mache nur das, weil es vielleicht einfacher ist, zu iterativ als rekursiv denken,

874
01:07:36,380 --> 01:07:39,010
aber nach dieser while-Schleife,

875
01:07:39,010 --> 01:07:43,820
* Temp ist der Zeiger wollen wir ändern.

876
01:07:43,820 --> 01:07:48,960
>> Vorher hatten wir Eltern, und wir wollten ein Elternteil nach links oder rechts ändern Muttergesellschaft,

877
01:07:48,960 --> 01:07:51,310
aber wenn wir wollen Eltern Recht zu ändern,

878
01:07:51,310 --> 01:07:54,550
dann * temp Muttergesellschaft rechts, und wir können es direkt zu ändern.

879
01:07:54,550 --> 01:08:05,860
So hier unten können wir tun * temp = newNode, und das ist es.

880
01:08:05,860 --> 01:08:09,540
So Ankündigung war alles, was wir in dies tat nehmen Sie Zeilen Code.

881
01:08:09,540 --> 01:08:14,770
Um den Überblick über die Muttergesellschaft in allem, was zusätzlichen Aufwand ist zu halten.

882
01:08:14,770 --> 01:08:18,689
Hier wird, wenn wir nur den Überblick über die Zeiger auf den Zeiger,

883
01:08:18,689 --> 01:08:22,990
und selbst wenn wir wollten, um loszuwerden, alle diese geschweiften Klammern jetzt

884
01:08:22,990 --> 01:08:27,170
lassen es so aussehen kürzer.

885
01:08:27,170 --> 01:08:32,529
Das ist nun genau die gleiche Lösung,

886
01:08:32,529 --> 01:08:38,210
aber weniger Zeilen Code.

887
01:08:38,210 --> 01:08:41,229
Sobald Sie anfangen, erkennen dies als eine gültige Lösung,

888
01:08:41,229 --> 01:08:43,529
Es ist auch einfacher, über Grund, als wie, okay,

889
01:08:43,529 --> 01:08:45,779
warum habe ich dieses Flag bei int. Recht?

890
01:08:45,779 --> 01:08:49,290
Was bedeutet das? Oh, es bedeutet, dass

891
01:08:49,290 --> 01:08:51,370
jedes Mal, wenn ich nach rechts, ich brauche, um es einrichten,

892
01:08:51,370 --> 01:08:53,819
else if gehe ich nach links muss ich es auf Null gesetzt.

893
01:08:53,819 --> 01:09:04,060
Hier habe ich nicht an die Vernunft über das, es ist einfacher zu denken.

894
01:09:04,060 --> 01:09:06,710
Haben Sie Fragen?

895
01:09:06,710 --> 01:09:16,290
[Student, unverständlich] >> Ja.

896
01:09:16,290 --> 01:09:23,359
Okay, so im letzten Bit -

897
01:09:23,359 --> 01:09:28,080
Ich denke, eine schnelle und einfache Funktion, die wir tun können, ist,

898
01:09:28,080 --> 01:09:34,910
let's - zusammen, glaube ich, zu versuchen und zu schreiben eine Funktion contains

899
01:09:34,910 --> 01:09:38,899
was nicht egal, ob es ein binärer Suchbaum ist.

900
01:09:38,899 --> 01:09:43,770
Diese enthält Funktion sollte true zurückgeben

901
01:09:43,770 --> 01:09:58,330
wenn irgendwo in dieser allgemeinen Binary Tree ist der Wert, den wir suchen.

902
01:09:58,330 --> 01:10:02,520
Also lasst uns zuerst tun es rekursiv und dann werden wir es iterativ zu tun.

903
01:10:02,520 --> 01:10:07,300
Wir können eigentlich nur tun es gemeinsam, weil dies wird sehr kurz sein.

904
01:10:07,300 --> 01:10:11,510
>> Was ist meine Basis Falle gehen werden?

905
01:10:11,510 --> 01:10:13,890
[Student, unverständlich]

906
01:10:13,890 --> 01:10:18,230
[Bowden] So if (baum == NULL), was dann?

907
01:10:18,230 --> 01:10:22,740
[Student] Zurück falsch.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, gut, ich brauche den anderen.

909
01:10:26,160 --> 01:10:30,250
Wenn war meine andere base case.

910
01:10:30,250 --> 01:10:32,450
[Student] Tree Wert? >> Ja.

911
01:10:32,450 --> 01:10:36,430
So if (tree-> value == Wert.

912
01:10:36,430 --> 01:10:39,920
Beachten Sie, dass wir zurück auf Knoten *, nicht Knotens ** s?

913
01:10:39,920 --> 01:10:42,990
Enthält sie nie brauchen, um einen Knoten ** verwenden,

914
01:10:42,990 --> 01:10:45,480
da wir nicht ändern Zeigern.

915
01:10:45,480 --> 01:10:50,540
Wir stehen noch durchqueren sie.

916
01:10:50,540 --> 01:10:53,830
Wenn das passiert, dann wollen wir true zurück.

917
01:10:53,830 --> 01:10:58,270
Else wollen wir die Kinder zu durchqueren.

918
01:10:58,270 --> 01:11:02,620
So können wir nicht, ob alles nach links ist weniger Grund

919
01:11:02,620 --> 01:11:05,390
und alles, was auf der rechten Seite größer ist.

920
01:11:05,390 --> 01:11:09,590
Also, was ist unsere Bedingung hier sein - oder, was sollen wir tun?

921
01:11:09,590 --> 01:11:11,840
[Student, unverständlich] >> Ja.

922
01:11:11,840 --> 01:11:17,400
Rückgabe enthält (Wert, tree-> links)

923
01:11:17,400 --> 01:11:26,860
oder enthält (Wert, tree-> rechts). Und das ist es.

924
01:11:26,860 --> 01:11:29,080
Und bemerken es gibt einige Kurzschluss Evaluierung

925
01:11:29,080 --> 01:11:32,520
wo, wenn wir den Wert in der linken Baum zu finden passieren,

926
01:11:32,520 --> 01:11:36,820
brauchen wir nicht auf dem richtigen Baum zu suchen.

927
01:11:36,820 --> 01:11:40,430
Das ist die ganze Funktion.

928
01:11:40,430 --> 01:11:43,690
Jetzt machen wir es iterativ

929
01:11:43,690 --> 01:11:48,060
was sein wird, weniger schön.

930
01:11:48,060 --> 01:11:54,750
Wir nehmen die üblichen Start des Knotens * cur = Baum.

931
01:11:54,750 --> 01:12:03,250
Während (Aktuell! = NULL).

932
01:12:03,250 --> 01:12:08,600
Schnell gehen, um ein Problem zu sehen.

933
01:12:08,600 --> 01:12:12,250
Wenn Aktuell - hier draußen, wenn wir jemals brechen aus diesem,

934
01:12:12,250 --> 01:12:16,020
dann haben wir aus der Dinge laufen zu sehen, so false zurück.

935
01:12:16,020 --> 01:12:24,810
Wenn (Aktuell-> value == Wert), true zurückgeben.

936
01:12:24,810 --> 01:12:32,910
So, jetzt sind wir an einem Ort -

937
01:12:32,910 --> 01:12:36,250
wir wissen nicht, ob wir links oder rechts gehen soll.

938
01:12:36,250 --> 01:12:44,590
So willkürlich, lasst uns einfach links gehen.

939
01:12:44,590 --> 01:12:47,910
Ich habe natürlich in ein Problem, wo ich komplett alles habe aufgegeben laufen -

940
01:12:47,910 --> 01:12:50,760
Ich werde immer nur überprüfen, die linke Seite eines Baumes.

941
01:12:50,760 --> 01:12:56,050
Ich werde nie überprüfen alles, was ein rechtes Kind von etwas ist.

942
01:12:56,050 --> 01:13:00,910
Wie kann ich dieses Problem beheben?

943
01:13:00,910 --> 01:13:05,260
[Student] Sie haben den Überblick über die links und rechts in einem Stapel zu halten.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. So machen wir es

945
01:13:13,710 --> 01:13:32,360
struct Liste Knoten * n, und dann Knoten ** nächste?

946
01:13:32,360 --> 01:13:40,240
Ich denke, das funktioniert gut.

947
01:13:40,240 --> 01:13:45,940
Wir wollen gehen über die linke oder let's - hier oben.

948
01:13:45,940 --> 01:13:54,350
Struct Liste list =, wird es beginnen

949
01:13:54,350 --> 01:13:58,170
an dieser struct Liste.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Also das wird unser verlinkten Liste sein

951
01:14:04,040 --> 01:14:08,430
von Teilbäumen, dass wir übersprungen.

952
01:14:08,430 --> 01:14:13,800
Wir werden jetzt links überqueren,

953
01:14:13,800 --> 01:14:17,870
aber da wir unweigerlich müssen kommen wieder nach rechts,

954
01:14:17,870 --> 01:14:26,140
Wir werden auf der rechten Seite innerhalb unserer struct Liste zu halten.

955
01:14:26,140 --> 01:14:32,620
Dann müssen wir new_list oder Struktur,

956
01:14:32,620 --> 01:14:41,080
struct list *, new_list = malloc (sizeof (list)).

957
01:14:41,080 --> 01:14:44,920
Ich werde zu ignorieren Fehlerprüfung, aber Sie sollten überprüfen, ob es null zu sehen.

958
01:14:44,920 --> 01:14:50,540
New_list den Knoten es geht um Point -

959
01:14:50,540 --> 01:14:56,890
oh, das ist, warum ich es wollte hier oben. Es wird zu einer zweiten struct Liste verweist.

960
01:14:56,890 --> 01:15:02,380
Das ist, wie verkettete Listen Arbeit.

961
01:15:02,380 --> 01:15:04,810
Dies ist das gleiche wie ein int verkettete Liste

962
01:15:04,810 --> 01:15:06,960
außer wir nur ersetzen int mit Knoten *.

963
01:15:06,960 --> 01:15:11,040
Es ist genau das gleiche.

964
01:15:11,040 --> 01:15:15,100
So new_list, der Wert unserer new_list Knoten,

965
01:15:15,100 --> 01:15:19,120
sein wird, Aktuell-> rechts.

966
01:15:19,120 --> 01:15:24,280
Der Wert unserer new_list-> next wird unsere ursprüngliche Liste zu sein,

967
01:15:24,280 --> 01:15:30,760
und dann werden wir unsere Liste aktualisieren, um new_list zeigen.

968
01:15:30,760 --> 01:15:33,650
>> Jetzt brauchen wir eine Art und Weise zu ziehen Dinge,

969
01:15:33,650 --> 01:15:37,020
wie wir es die ganze linke Teilbaum durchlaufen.

970
01:15:37,020 --> 01:15:40,480
Jetzt brauchen wir, um Sachen zu ziehen aus ihm heraus,

971
01:15:40,480 --> 01:15:43,850
wie Aktuell ist null, wir wollen nicht nur false zurück.

972
01:15:43,850 --> 01:15:50,370
Wir wollen nun außerhalb ziehen an unserem neuen Liste.

973
01:15:50,370 --> 01:15:53,690
Ein bequemer Weg, dies zu tun - na ja, eigentlich gibt es mehrere Möglichkeiten, dies zu tun.

974
01:15:53,690 --> 01:15:56,680
Jemand einen Vorschlag?

975
01:15:56,680 --> 01:15:58,790
Wo sollte ich dies tun oder wie soll ich das tun?

976
01:15:58,790 --> 01:16:08,010
Wir haben nur ein paar Minuten, aber irgendwelche Vorschläge?

977
01:16:08,010 --> 01:16:14,750
Statt - ein Weg, anstatt unsere Bedingung ist, während

978
01:16:14,750 --> 01:16:17,090
was wir derzeit auf der Suche auf nicht null ist,

979
01:16:17,090 --> 01:16:22,340
sondern wir gehen weiter zu gehen, bis unsere Liste selbst ist null.

980
01:16:22,340 --> 01:16:25,680
Also, wenn unsere Liste endet als null,

981
01:16:25,680 --> 01:16:30,680
dann haben wir aus der Dinge laufen zu suchen, zur Suche vorbei.

982
01:16:30,680 --> 01:16:39,860
Aber das bedeutet, dass das erste, was in unserer Liste ist gerade dabei, den ersten Knoten sein.

983
01:16:39,860 --> 01:16:49,730
Das allererste, was sein wird - wir müssen nicht mehr sorgen.

984
01:16:49,730 --> 01:16:58,710
So list-> n wird unser Baum.

985
01:16:58,710 --> 01:17:02,860
list-> next wird null sein.

986
01:17:02,860 --> 01:17:07,580
Und jetzt, während Liste ist nicht gleich null.

987
01:17:07,580 --> 01:17:11,610
Aktuell wird etwas aus unserer Liste zu ziehen.

988
01:17:11,610 --> 01:17:13,500
So Aktuell wird gleich list-> n gehen.

989
01:17:13,500 --> 01:17:20,850
Und dann Liste wird gleich list-> n, oder list-> next.

990
01:17:20,850 --> 01:17:23,480
Also, wenn Aktuell Wert gleich Wert.

991
01:17:23,480 --> 01:17:28,790
Jetzt können wir hinzufügen, sowohl unser Recht Zeiger und unsere linke Zeiger

992
01:17:28,790 --> 01:17:32,900
Solange sie es nicht sind null.

993
01:17:32,900 --> 01:17:36,390
Hier unten, denke ich, sollten wir das getan haben, in den ersten Platz.

994
01:17:36,390 --> 01:17:44,080
Wenn (Aktuell-> right! = NULL)

995
01:17:44,080 --> 01:17:56,380
dann werden wir diesen Knoten in unsere Liste einzufügen.

996
01:17:56,380 --> 01:17:59,290
Wenn (Aktuell-> links), das ist ein wenig zusätzliche Arbeit, aber es ist in Ordnung.

997
01:17:59,290 --> 01:18:02,690
Wenn (Aktuell-> left! = NULL),

998
01:18:02,690 --> 01:18:14,310
und wir gehen nach links in unseren verketteten Liste einzufügen,

999
01:18:14,310 --> 01:18:19,700
und dass es sein sollte.

1000
01:18:19,700 --> 01:18:22,670
Wir durchlaufen - so lange wir etwas haben in unserer Liste

1001
01:18:22,670 --> 01:18:26,640
Wir haben einen anderen Knoten zu betrachten.

1002
01:18:26,640 --> 01:18:28,920
Also schauen wir an diesem Knoten,

1003
01:18:28,920 --> 01:18:31,390
Wir entwickeln unsere Liste auf der nächsten.

1004
01:18:31,390 --> 01:18:34,060
Wenn dieser Knoten ist der Wert, den wir suchen, können wir true zurück.

1005
01:18:34,060 --> 01:18:37,640
Else legen unsere beiden linken und rechten Teilbäume,

1006
01:18:37,640 --> 01:18:40,510
Solange sie es nicht sind null, in unsere Liste

1007
01:18:40,510 --> 01:18:43,120
so dass wir unweigerlich über sie gehen.

1008
01:18:43,120 --> 01:18:45,160
Also, wenn sie nicht null,

1009
01:18:45,160 --> 01:18:47,950
wenn unsere root Zeiger wies auf zwei Dinge,

1010
01:18:47,950 --> 01:18:51,670
dann wir zunächst zog etwas aus, damit unsere Liste endet als null.

1011
01:18:51,670 --> 01:18:56,890
Und dann haben wir zwei Dinge zurück, so dass nun unserer Liste ist der Größe 2.

1012
01:18:56,890 --> 01:19:00,030
Dann sind wir in einer Schleife zurück und wir werden einfach nur zu ziehen,

1013
01:19:00,030 --> 01:19:04,250
sagen wir mal, die linke Zeiger unserer Wurzelknoten.

1014
01:19:04,250 --> 01:19:07,730
Und das werde einfach weiter passiert, wir werden am Ende eine Schleife über alles.

1015
01:19:07,730 --> 01:19:11,280
>> Beachten Sie, dass dies wesentlich komplizierter war

1016
01:19:11,280 --> 01:19:14,160
im rekursiven Lösung.

1017
01:19:14,160 --> 01:19:17,260
Und ich habe gesagt, mehrfach

1018
01:19:17,260 --> 01:19:25,120
dass die rekursive Lösung hat in der Regel viel gemeinsam mit der iterativen Lösung.

1019
01:19:25,120 --> 01:19:30,820
Hier ist dies genau das, was die rekursive Lösung tut.

1020
01:19:30,820 --> 01:19:36,740
Die einzige Änderung ist, dass anstelle der implizit mit den Stapel, der Programm-Stack,

1021
01:19:36,740 --> 01:19:40,840
wie Sie Ihren Weg im Auge zu behalten, was Knoten müssen Sie noch besuchen,

1022
01:19:40,840 --> 01:19:45,430
jetzt müssen Sie explizit eine verkettete Liste.

1023
01:19:45,430 --> 01:19:49,070
In beiden Fällen sind die Verfolgung von welcher Knoten muss noch besichtigt werden.

1024
01:19:49,070 --> 01:19:51,790
In der rekursiven Fall ist es einfach leichter, weil ein Stapel

1025
01:19:51,790 --> 01:19:57,100
ist für Sie als Programm-Stack implementiert.

1026
01:19:57,100 --> 01:19:59,550
Beachten Sie, dass diese verketteten Liste, es ist ein Stack ist.

1027
01:19:59,550 --> 01:20:01,580
Was auch immer wir haben gerade auf dem Stack

1028
01:20:01,580 --> 01:20:09,960
ist ab sofort, was wir zu ziehen aus dem Stapel zum nächsten zu besuchen.

1029
01:20:09,960 --> 01:20:14,380
Wir haben keine Zeit mehr, aber noch Fragen?

1030
01:20:14,380 --> 01:20:23,530
[Student, unverständlich]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Also, wenn wir unsere verketteten Liste,

1032
01:20:27,790 --> 01:20:30,150
Strom werde diesen Kerl zeigen,

1033
01:20:30,150 --> 01:20:34,690
und jetzt sind wir gerade Weiterentwicklung unserer verketteten Liste auf diesen Kerl zu konzentrieren.

1034
01:20:34,690 --> 01:20:44,200
Wir über den verketteten Liste in dieser Linie durchquert.

1035
01:20:44,200 --> 01:20:51,200
Und dann habe ich denke, wir sollten unsere verketteten Liste und Sachen befreien

1036
01:20:51,200 --> 01:20:53,880
einmal vor der Rückkehr wahr oder falsch, müssen wir

1037
01:20:53,880 --> 01:20:57,360
iterieren unserer verketteten Liste und immer hier unten, ich denke,

1038
01:20:57,360 --> 01:21:03,900
wenn wir Aktuell Recht ist nicht gleich, fügen Sie es, so jetzt müssen wir befreien wollen

1039
01:21:03,900 --> 01:21:09,600
Aktuell weil, na ja, wir haben komplett über die Liste vergessen? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Also das ist, was wir hier tun wollen.

1041
01:21:12,880 --> 01:21:16,730
Wo ist der Zeiger?

1042
01:21:16,730 --> 01:21:23,320
Aktuell war damals - wir wollen eine struct list * 10 entspricht Liste neben.

1043
01:21:23,320 --> 01:21:29,240
Freie Liste, Liste = temp.

1044
01:21:29,240 --> 01:21:32,820
Und in dem Fall, wo wir true zurückgeben, müssen wir iterieren

1045
01:21:32,820 --> 01:21:37,050
über den Rest unserer verketteten Liste befreien Dinge.

1046
01:21:37,050 --> 01:21:39,700
Die nette Sache über die rekursive Lösung ist befreiend Dinge

1047
01:21:39,700 --> 01:21:44,930
bedeutet nur knallen factorings vom Stapel, der für euch geschehen wird.

1048
01:21:44,930 --> 01:21:50,720
So haben wir von etwas, das wie 3 Zeilen hard-to-think-zu-Code ist weg

1049
01:21:50,720 --> 01:21:57,520
etwas, das deutlich viel mehr ist schwer zu glauben, zu Zeilen Code.

1050
01:21:57,520 --> 01:22:00,620
Noch Fragen?

1051
01:22:00,620 --> 01:22:08,760
Gut. Wir sind gut. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]