1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [§ 7] [weniger komfortabel]

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

3
00:00:04,890 --> 00:00:07,000
[Dies ist CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Willkommen in Abschnitt 7.

5
00:00:09,080 --> 00:00:11,330
Dank Hurrikan Sandy,

6
00:00:11,330 --> 00:00:13,440
Statt mit einem normalen Abschnitt dieser Woche,

7
00:00:13,440 --> 00:00:17,650
wir tun dies walk-through, durch den Abschnitt von Fragen.

8
00:00:17,650 --> 00:00:22,830
Ich werde zu folgen zusammen mit dem Problem Set 6-Spezifikation,

9
00:00:22,830 --> 00:00:25,650
und gehen durch alle Fragen in der

10
00:00:25,650 --> 00:00:27,770
Ein Abschnitt der Fragen Abschnitt.

11
00:00:27,770 --> 00:00:30,940
Wenn es irgendwelche Fragen,

12
00:00:30,940 --> 00:00:32,960
bitte posten diese auf CS50 diskutieren.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Lasst uns loslegen.

14
00:00:35,480 --> 00:00:40,780
Im Moment bin ich auf Seite 3 des Problem Set Spezifikation suchen.

15
00:00:40,780 --> 00:00:44,110
Wir werden zum ersten Mal starten reden binären Bäumen

16
00:00:44,110 --> 00:00:47,850
da diese eine Menge von Bedeutung in dieser Woche das Problem set -

17
00:00:47,850 --> 00:00:49,950
die Huffman-Baum-Codierung.

18
00:00:49,950 --> 00:00:55,000
Einer der ersten Datenstrukturen über die wir gesprochen am CS50 war die Array.

19
00:00:55,000 --> 00:01:00,170
Beachten Sie, dass ein Array aus einer Folge von Elementen -

20
00:01:00,170 --> 00:01:04,019
alle vom gleichen Typ - in unmittelbarer Nähe zueinander in Speicher gespeichert.

21
00:01:04,019 --> 00:01:14,420
Wenn ich ein Integer-Array, dass ich zeichnen kann mit dieser Boxen-Nummern-Zahlen-Stil -

22
00:01:14,420 --> 00:01:20,290
Lassen Sie uns sagen, ich habe 5 in der ersten Box, ich habe 7 in der zweiten,

23
00:01:20,290 --> 00:01:27,760
dann habe ich 8, 10 und 20 in der letzten Box.

24
00:01:27,760 --> 00:01:33,000
Denken Sie daran, die beiden wirklich gute Dinge über dieses Array

25
00:01:33,000 --> 00:01:38,800
sind, dass wir diese Konstante-time Zugang zu einem bestimmten Element haben

26
00:01:38,800 --> 00:01:40,500
 im Array, wenn wir wissen, seinen Index.

27
00:01:40,500 --> 00:01:44,670
Zum Beispiel, wenn ich das dritte Element im Array greifen wollen -

28
00:01:44,670 --> 00:01:47,870
bei Index 2 mit unserer Null-basierte Indizierung System -

29
00:01:47,870 --> 00:01:52,220
Ich habe buchstäblich nur noch eine einfache mathematische Berechnung zu tun,

30
00:01:52,220 --> 00:01:56,170
hop in diese Position in der Anordnung,

31
00:01:56,170 --> 00:01:57,840
Ziehen Sie die 8, die dort gespeichert sind,

32
00:01:57,840 --> 00:01:59,260
und ich bin gut zu gehen.

33
00:01:59,260 --> 00:02:03,350
>> Einer der schlechte Dinge über dieses Array -, dass wir darüber gesprochen,

34
00:02:03,350 --> 00:02:05,010
wenn wir diskutiert verkettete Listen -

35
00:02:05,010 --> 00:02:09,120
ist, dass, wenn ich ein Element in diesem Array einfügen möchten,

36
00:02:09,120 --> 00:02:11,090
Ich werde zu müssen, einige Verschiebung um zu tun.

37
00:02:11,090 --> 00:02:12,940
Zum Beispiel kann diese Anordnung direkt hier

38
00:02:12,940 --> 00:02:16,850
ist in sortierter Reihenfolge - in aufsteigender Reihenfolge sortiert -

39
00:02:16,850 --> 00:02:19,440
5, dann 7, dann 8, dann 10, dann 20 -

40
00:02:19,440 --> 00:02:23,100
aber wenn ich die Nummer 9 in diesem Array einzufügen,

41
00:02:23,100 --> 00:02:27,460
Ich bin zu haben, um einige der Elemente zu verschieben, um Platz zu schaffen.

42
00:02:27,460 --> 00:02:30,440
Wir ziehen kann dies hier.

43
00:02:30,440 --> 00:02:35,650
Ich bin zu haben, um die 5, die 7 zu bewegen, und dann die 8;

44
00:02:35,650 --> 00:02:38,720
eine Lücke, wo ich die 9 setzen können,

45
00:02:38,720 --> 00:02:45,910
und dann der 10 und der 20 auf der rechten Seite der 9 gehen.

46
00:02:45,910 --> 00:02:49,450
Dies ist eine Art von Schmerz, weil im schlimmsten Fall -

47
00:02:49,450 --> 00:02:54,350
wenn wir mit Einsetzen entweder am Anfang oder am Ende

48
00:02:54,350 --> 00:02:56,040
des Arrays, je nachdem, wie wir verschieben -

49
00:02:56,040 --> 00:02:58,850
könnten wir am Ende mit all den Elementen verschieben

50
00:02:58,850 --> 00:03:00,750
dass wir derzeit die Speicherung im Array.

51
00:03:00,750 --> 00:03:03,810
>> Also, was war der Weg, um dieses?

52
00:03:03,810 --> 00:03:09,260
Der Weg um dies zu unserem linked-list-Methode, wohin sie gehen -

53
00:03:09,260 --> 00:03:19,820
Statt des Speicherns der Elemente 5, 7, 8, 10 und 20 alle nebeneinander im Speicher -

54
00:03:19,820 --> 00:03:25,630
Was wir stattdessen tat, war lagern Art von wo wir wollten um sie zu speichern

55
00:03:25,630 --> 00:03:32,470
in diesen verlinkten Liste Knoten denen zeichne ich hier, eine Art ad hoc.

56
00:03:32,470 --> 00:03:42,060
Und dann haben wir sie miteinander verbunden sind mit diesen nächsten Zeiger.

57
00:03:42,060 --> 00:03:44,370
Ich kann einen Zeiger von 5 zu der 7,

58
00:03:44,370 --> 00:03:46,420
ein Zeiger von der 7 auf die 8,

59
00:03:46,420 --> 00:03:47,770
ein Zeiger von der 8 bis zur 10,

60
00:03:47,770 --> 00:03:51,220
und schließlich ein Zeiger aus der 10 zu der 20,

61
00:03:51,220 --> 00:03:54,880
und dann ein Null-Zeiger auf der 20 darauf hinweist, dass es nichts mehr übrig.

62
00:03:54,880 --> 00:03:59,690
Die Trade-off, die wir hier haben,

63
00:03:59,690 --> 00:04:05,360
ist, dass jetzt, wenn wir die Zahl 9 in unsere sortierte Liste einfügen möchten,

64
00:04:05,360 --> 00:04:08,270
alles, was wir tun müssen, ist einen neuen Knoten mit 9,

65
00:04:08,270 --> 00:04:12,290
verdrahten, um an die entsprechende Stelle darauf hinweisen,

66
00:04:12,290 --> 00:04:20,630
und dann neu verkabeln 8 bis unten, um die 9.

67
00:04:20,630 --> 00:04:25,660
Das ist ziemlich schnell, vorausgesetzt, wir wissen genau, wo wir die 9 einfügen möchten.

68
00:04:25,660 --> 00:04:32,610
Aber der Trade-off im Austausch dafür ist, dass wir jetzt die Konstante-Zugang verloren

69
00:04:32,610 --> 00:04:36,230
auf ein bestimmtes Element in unserer Datenstruktur.

70
00:04:36,230 --> 00:04:40,950
Zum Beispiel, wenn ich will, um das vierte Element in dieser verketteten Liste zu finden,

71
00:04:40,950 --> 00:04:43,510
Ich werde zu müssen, ganz am Anfang der Liste zu starten

72
00:04:43,510 --> 00:04:48,930
und meinen Weg durch das Zählen node-by-Knoten, bis ich die vierte zu finden.

73
00:04:48,930 --> 00:04:55,870
>> Um einen besseren Zugang Leistung als einer verketteten Liste -

74
00:04:55,870 --> 00:04:59,360
sondern behalten auch einige der Vorteile, die wir hatten

75
00:04:59,360 --> 00:05:01,800
in Bezug auf die Insertion-Zeit von einer verketteten Liste -

76
00:05:01,800 --> 00:05:05,750
ein binärer Baum ist gehen zu müssen, ein wenig mehr Speicher zu verwenden.

77
00:05:05,750 --> 00:05:11,460
Insbesondere, statt nur mit einem Zeiger in einem binären Baum Knoten -

78
00:05:11,460 --> 00:05:13,350
wie der linked-list node tut -

79
00:05:13,350 --> 00:05:16,950
werden wir eine zweite Zeiger auf die binären Baum Knoten hinzuzufügen.

80
00:05:16,950 --> 00:05:19,950
Anstatt nur mit einem Zeiger auf das nächste Element,

81
00:05:19,950 --> 00:05:24,420
werden wir einen Zeiger auf eine linke Kind und einem rechten Kind zu haben.

82
00:05:24,420 --> 00:05:26,560
>> Lassen Sie uns ein Bild zeichnen, um zu sehen, was das tatsächlich aussieht.

83
00:05:26,560 --> 00:05:31,350
Wieder werde ich diese Boxen und Pfeile verwenden.

84
00:05:31,350 --> 00:05:37,150
Ein Binärbaum Knoten startet mit nur einem einfachen Box.

85
00:05:37,150 --> 00:05:40,940
Es wird eine Fläche für den Wert haben,

86
00:05:40,940 --> 00:05:47,280
und dann ist es auch gehen, um einen Raum für die linke und die rechte Kind Kind.

87
00:05:47,280 --> 00:05:49,280
Ich werde sie hier zu beschriften.

88
00:05:49,280 --> 00:05:57,560
Wir werden das linke Kind haben, und dann werden wir das rechte Kind haben.

89
00:05:57,560 --> 00:05:59,920
Es gibt viele verschiedene Möglichkeiten zur Verfügung.

90
00:05:59,920 --> 00:06:02,050
Manchmal für Raum und Komfort,

91
00:06:02,050 --> 00:06:06,460
Ich werde tatsächlich ziehen Sie es wie ich hier mache auf der Unterseite

92
00:06:06,460 --> 00:06:10,910
wohin ich gehe, um den Wert an der Spitze haben,

93
00:06:10,910 --> 00:06:14,060
und dann die rechte Kind auf der unteren rechten,

94
00:06:14,060 --> 00:06:16,060
und das linke Kind auf der unteren linken.

95
00:06:16,060 --> 00:06:20,250
Gehen wir zurück zu diesem Top-Diagramm

96
00:06:20,250 --> 00:06:22,560
haben wir den Wert an der Spitze,

97
00:06:22,560 --> 00:06:25,560
dann haben wir die linke Kind-Zeiger, und dann haben wir das Recht, Kind-Zeiger.

98
00:06:25,560 --> 00:06:30,110
>> Im Problem Set Spezifikation,

99
00:06:30,110 --> 00:06:33,110
wir reden über das Zeichnen eines Knotens, der einen Wert 7 hat,

100
00:06:33,110 --> 00:06:39,750
und dann ein linkes Kind-Zeiger, der null ist, und ein rechtes Kind-Zeiger, der den Wert null.

101
00:06:39,750 --> 00:06:46,040
Wir können entweder schreiben Hauptstadt NULL in den Raum für

102
00:06:46,040 --> 00:06:51,610
sowohl die linke als Kind und das rechte Kind, oder wir ziehen können dieses Schrägstrich

103
00:06:51,610 --> 00:06:53,750
durch jedes der Felder, um anzuzeigen, dass es null ist.

104
00:06:53,750 --> 00:06:57,560
Ich werde tun, dass, nur weil das einfacher ist.

105
00:06:57,560 --> 00:07:03,700
Was Sie hier sehen, sind zwei Möglichkeiten zur Diagrammerstellung einen sehr einfachen binären Baumknoten

106
00:07:03,700 --> 00:07:07,960
wo wir den Wert 7 und null Kind Zeigern.

107
00:07:07,960 --> 00:07:15,220
>> Der zweite Teil unserer Spezifikation spricht darüber, wie mit verknüpften Listen -

108
00:07:15,220 --> 00:07:18,270
Denken Sie daran, wir hatten nur zu halten, um die allererste Element in einer Liste

109
00:07:18,270 --> 00:07:20,270
um die gesamte Liste erinnern -

110
00:07:20,270 --> 00:07:26,140
und ebenfalls mit einem binären Baum, wir haben nur zu halten, um einen Zeiger auf den Baum

111
00:07:26,140 --> 00:07:31,120
Um die Kontrolle über die gesamte Datenstruktur beizubehalten.

112
00:07:31,120 --> 00:07:36,150
Diese besondere Element des Baumes wird als Stammknoten des Baums.

113
00:07:36,150 --> 00:07:43,360
Zum Beispiel, wenn dieses einen Knotens - dieser Knoten mit dem Wert 7

114
00:07:43,360 --> 00:07:45,500
mit null links und rechts-Kind-Zeiger -

115
00:07:45,500 --> 00:07:47,360
waren der einzige Wert im Baum,

116
00:07:47,360 --> 00:07:50,390
dann würde dies unseren Root-Knoten sein.

117
00:07:50,390 --> 00:07:52,240
Es ist der Anfang unserer Baum.

118
00:07:52,240 --> 00:07:58,530
Wir können diese ein wenig klarer zu sehen, wenn wir das Hinzufügen von mehr Knoten zu unserem Baum starten.

119
00:07:58,530 --> 00:08:01,510
Lassen Sie mich nach oben ziehen eine neue Seite.

120
00:08:01,510 --> 00:08:05,000
>> Jetzt werden wir einen Baum, 7 hat an der Wurzel zu ziehen,

121
00:08:05,000 --> 00:08:10,920
und 3 im Inneren des linken Kindes und 9 innerhalb des rechten Kindes.

122
00:08:10,920 --> 00:08:13,500
Auch dies ist ziemlich einfach.

123
00:08:13,500 --> 00:08:26,510
Wir haben 7 haben, ziehen Sie einen Knoten für die 3, ein Knoten für 9,

124
00:08:26,510 --> 00:08:32,150
und ich werde das linke Kind-Zeiger 7, um den Knoten mit Punkt 3 gesetzt,

125
00:08:32,150 --> 00:08:37,850
und das rechte Kind Zeiger des Knotens mit dem Knoten 7 bis 9 enthält.

126
00:08:37,850 --> 00:08:42,419
Nun, seit 3 ​​und 9 haben keine Kinder,

127
00:08:42,419 --> 00:08:48,500
werden wir alle ihr Kind Zeiger auf null sein.

128
00:08:48,500 --> 00:08:56,060
Hier entspricht die Wurzel unserer Baum zu dem Knoten, der die Anzahl 7.

129
00:08:56,060 --> 00:09:02,440
Sie können sehen, dass, wenn alles, was wir haben, ist ein Zeiger auf die Root-Knoten,

130
00:09:02,440 --> 00:09:07,330
können wir dann durch unseren Baum gehen und auf beide Kindknoten -

131
00:09:07,330 --> 00:09:10,630
beide 3 und 9.

132
00:09:10,630 --> 00:09:14,820
Keine Notwendigkeit, Zeiger auf jedem einzelnen Knoten im Baum zu halten.

133
00:09:14,820 --> 00:09:22,080
Alright. Jetzt werden wir einen anderen Knoten zu diesem Diagramm hinzuzufügen.

134
00:09:22,080 --> 00:09:25,370
Wir werden einen Knoten mit 6 hinzuzufügen,

135
00:09:25,370 --> 00:09:34,140
und wir werden dies als die rechte Kind des Knotens mit 3 hinzuzufügen.

136
00:09:34,140 --> 00:09:41,850
Um dies zu tun, werde ich diese Null-Zeiger in der 3-Knoten löschen

137
00:09:41,850 --> 00:09:47,750
und verdrahten bis zum Knoten mit 6 zeigen. Alright.

138
00:09:47,750 --> 00:09:53,800
>> An dieser Stelle wollen wir über ein wenig Terminologie gehen.

139
00:09:53,800 --> 00:09:58,230
Um zu beginnen, den Grund, dass diese aufgerufen wird ein Binärbaum insbesondere

140
00:09:58,230 --> 00:10:00,460
ist, dass es zwei untergeordnete Zeiger hat.

141
00:10:00,460 --> 00:10:06,020
Es gibt noch andere Arten von Bäumen, die mehr Kinder Zeigern.

142
00:10:06,020 --> 00:10:10,930
Insbesondere haben Sie ein 'versuchen' in Problem Set 5.

143
00:10:10,930 --> 00:10:19,310
Sie, dass in diesem Versuch bemerken, musste man 27 verschiedene Verweise auf andere Kinder -

144
00:10:19,310 --> 00:10:22,410
eine für jedes der 26 Buchstaben des englischen Alphabets,

145
00:10:22,410 --> 00:10:25,410
und dann die 27. für den Apostroph -

146
00:10:25,410 --> 00:10:28,900
so, das ist wie eine Art von Baum.

147
00:10:28,900 --> 00:10:34,070
Aber auch hier, denn es ist binär, haben wir nur zwei Kinder Zeigern.

148
00:10:34,070 --> 00:10:37,880
>> Zusätzlich zu diesem Wurzelknoten, dass wir darüber gesprochen,

149
00:10:37,880 --> 00:10:41,470
Wir haben auch um dieser Begriff geworfen 'Kind. "

150
00:10:41,470 --> 00:10:44,470
Was bedeutet es für einen Knoten ein Kind einem anderen Knoten zu sein?

151
00:10:44,470 --> 00:10:54,060
Es bedeutet wörtlich, dass ein Kind-Knoten ein Kind von einem anderen Knoten

152
00:10:54,060 --> 00:10:58,760
wenn dieser andere Knoten hat einem seiner untergeordneten Zeiger auf diesen Knoten zeigen.

153
00:10:58,760 --> 00:11:01,230
Um dies in konkreter,

154
00:11:01,230 --> 00:11:11,170
wenn 3 ist, um durch eines der untergeordneten Zeigern von 7 hingewiesen, dann 3 ist ein Kind von 7.

155
00:11:11,170 --> 00:11:14,510
Wenn wir herausfinden, was die Kinder von 7 sind -

156
00:11:14,510 --> 00:11:18,510
gut sehen wir, dass 7 einen Zeiger auf 3 und einen Zeiger auf 9 hat,

157
00:11:18,510 --> 00:11:22,190
so 9 und 3 sind die Kinder von 7.

158
00:11:22,190 --> 00:11:26,650
Nine hat keine Kinder, weil ihre Kinder Zeiger null sind,

159
00:11:26,650 --> 00:11:30,940
und 3 nur ein Kind hat, 6.

160
00:11:30,940 --> 00:11:37,430
Six hat auch keine Kinder, weil ihre beiden Zeiger null, die wir jetzt ziehen werde sind.

161
00:11:37,430 --> 00:11:45,010
>> Darüber hinaus haben wir auch über die Eltern von einem bestimmten Knoten zu sprechen,

162
00:11:45,010 --> 00:11:51,100
und das ist, wie man es erwarten würde, das Gegenteil von diesem Kind Beschreibung.

163
00:11:51,100 --> 00:11:58,620
Jeder Knoten hat nur ein Elternteil - statt zwei, wie Sie vielleicht mit Menschen erwarten.

164
00:11:58,620 --> 00:12:03,390
Zum Beispiel ist die Muttergesellschaft von 3 7.

165
00:12:03,390 --> 00:12:10,800
Die Muttergesellschaft von 9 ist auch 7, und die Eltern von 6 ist 3. Nicht viel zu tun.

166
00:12:10,800 --> 00:12:15,720
Wir haben auch Bedingungen über Großeltern und Enkel zu sprechen,

167
00:12:15,720 --> 00:12:18,210
und ganz allgemein sprechen wir über die Vorfahren

168
00:12:18,210 --> 00:12:20,960
und Nachkommen von einem bestimmten Knoten.

169
00:12:20,960 --> 00:12:25,710
Der Vorfahre eines Knotens - oder Vorfahren, sondern eines Knotens -

170
00:12:25,710 --> 00:12:32,730
sind alle Knoten, die auf dem Weg von der Wurzel zu dem Knoten liegen.

171
00:12:32,730 --> 00:12:36,640
Zum Beispiel, wenn ich an dem Knoten 6 suchen,

172
00:12:36,640 --> 00:12:46,430
dann die Vorfahren gehen, um beide 3 und 7 liegen.

173
00:12:46,430 --> 00:12:55,310
Die Vorfahren von 9, zum Beispiel, sind - wenn ich am Knoten 9 suchen -

174
00:12:55,310 --> 00:12:59,990
dann die Vorfahren von 9 ist nur 7.

175
00:12:59,990 --> 00:13:01,940
Und Nachkommen sind genau das Gegenteil.

176
00:13:01,940 --> 00:13:05,430
Wenn ich an all die Nachkommen von 7 aussehen soll,

177
00:13:05,430 --> 00:13:11,020
dann habe ich auf allen Knoten unter ihm zu suchen.

178
00:13:11,020 --> 00:13:16,950
Also, ich habe 3, 9 und 6 alle als Nachkommen von 7.

179
00:13:16,950 --> 00:13:24,170
>> Der letzte Begriff, dass wir darüber reden ist diese Vorstellung ein Geschwister.

180
00:13:24,170 --> 00:13:27,980
Geschwister - Art nach zusammen auf diesen Familien Begriffe -

181
00:13:27,980 --> 00:13:33,150
sind Knoten, die auf der gleichen Ebene in der Baumstruktur sind.

182
00:13:33,150 --> 00:13:42,230
So sind 3 und 9 Geschwistern, weil sie auf der gleichen Ebene in der Baumstruktur sind.

183
00:13:42,230 --> 00:13:46,190
Beide haben die gleichen Eltern, 7.

184
00:13:46,190 --> 00:13:51,400
Die 6 hat keine Geschwister, weil 9 der keine Kinder.

185
00:13:51,400 --> 00:13:55,540
Und 7 hat keine Geschwister, weil sie die Wurzel unserer Baum ist,

186
00:13:55,540 --> 00:13:59,010
und es gibt immer nur 1 root.

187
00:13:59,010 --> 00:14:02,260
Für 7 Geschwister haben dort müsste ein Knoten über 7 liegen.

188
00:14:02,260 --> 00:14:07,480
Es müsste ein Elternteil von 7, in welchem ​​Fall 7 nicht mehr die Wurzel des Baumes sein würde.

189
00:14:07,480 --> 00:14:10,480
Dann, dass neue Muttergesellschaft von 7 hätte auch ein Kind haben,

190
00:14:10,480 --> 00:14:16,480
und das Kind wäre dann die Geschwister von 7 sein.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Umzug auf.

192
00:14:21,040 --> 00:14:24,930
Wenn wir unsere Diskussion von binären Bäumen begonnen,

193
00:14:24,930 --> 00:14:28,790
Wir sprachen darüber, wie wir wollten, um sie zu bedienen

194
00:14:28,790 --> 00:14:32,800
sich einen Vorteil gegenüber den beiden Arrays und verkettete Listen.

195
00:14:32,800 --> 00:14:37,220
Und die Art und Weise wir, dass tun, ist mit dieser Bestellung Eigentum.

196
00:14:37,220 --> 00:14:41,080
Wir sagen, dass ein binärer Baum geordnet ist, gemäß der Spezifikation,

197
00:14:41,080 --> 00:14:45,740
wenn für jeden Knoten in unserem Baum, alle seine Nachkommen auf der linken Seite -

198
00:14:45,740 --> 00:14:48,670
das linke Kind und all die linke Kind Nachkommen -

199
00:14:48,670 --> 00:14:54,510
haben geringere Werte, und alle der Knoten auf der rechten Seite -

200
00:14:54,510 --> 00:14:57,770
das rechte Kind und alle das rechte Kind Nachkommen -

201
00:14:57,770 --> 00:15:02,800
haben Knoten größer als der Wert des aktuellen Knotens, dass wir auf der Suche.

202
00:15:02,800 --> 00:15:07,850
Nur der Einfachheit halber werden wir davon ausgehen, dass es keine doppelten Knoten in unserem Baum.

203
00:15:07,850 --> 00:15:11,180
Zum Beispiel, in diesem Baum werden wir nicht mit dem Fall zu befassen

204
00:15:11,180 --> 00:15:13,680
wo wir den Wert 7 an der Wurzel

205
00:15:13,680 --> 00:15:16,720
 und dann haben wir auch den Wert 7 an anderer Stelle im Baum.

206
00:15:16,720 --> 00:15:24,390
In diesem Fall, werden Sie feststellen, dass dieser Baum tatsächlich bestellt wird.

207
00:15:24,390 --> 00:15:26,510
Wir haben den Wert 7 an der Wurzel.

208
00:15:26,510 --> 00:15:29,720
Alles links von 7 -

209
00:15:29,720 --> 00:15:35,310
wenn ich rückgängig all diese kleinen Zeichen hier -

210
00:15:35,310 --> 00:15:40,450
alles links von 7 - die 3 und die 6 -

211
00:15:40,450 --> 00:15:49,410
diese Werte sind beide weniger als 7, und alles, was auf der rechten Seite - das ist nur auf 9 -

212
00:15:49,410 --> 00:15:53,450
größer als 7 ist.

213
00:15:53,450 --> 00:15:58,650
>> Dies ist nicht die einzige geordneten Baum mit diesen Werten,

214
00:15:58,650 --> 00:16:03,120
aber wir ziehen ein paar mehr von ihnen.

215
00:16:03,120 --> 00:16:05,030
Es gibt tatsächlich eine ganze Reihe von Möglichkeiten, dass wir dies tun können.

216
00:16:05,030 --> 00:16:09,380
Ich werde eine Abkürzung verwenden, nur um die Dinge einfach halten, wo -

217
00:16:09,380 --> 00:16:11,520
anstatt Herausziehen des ganzen Boxen-und-Pfeile -

218
00:16:11,520 --> 00:16:14,220
Ich werde einfach die Zahlen zu ziehen und fügen Pfeile miteinander verbinden.

219
00:16:14,220 --> 00:16:22,920
Um zu beginnen, wir schreiben einfach unsere ursprüngliche Baum wieder, wo wir 7 hatte, und dann ein 3,

220
00:16:22,920 --> 00:16:25,590
und dann 3 zeigte wieder nach rechts auf die 6,

221
00:16:25,590 --> 00:16:30,890
und 7 hatte ein Recht Kind, 9 war.

222
00:16:30,890 --> 00:16:33,860
Alright. Was ist eine andere Möglichkeit, dass wir diesen Baum zu schreiben?

223
00:16:33,860 --> 00:16:38,800
Anstatt mit 3 das linke Kind 7 sein,

224
00:16:38,800 --> 00:16:41,360
Wir konnten auch die 6 der linke Kind 7 sein,

225
00:16:41,360 --> 00:16:44,470
und dann 3 das linke Kind des 6 sein.

226
00:16:44,470 --> 00:16:48,520
Das wäre wie dieser Baum hier schauen, wo ich 7 bin,

227
00:16:48,520 --> 00:16:57,860
dann 6, dann 3 ist, und ein 9 auf der rechten Seite.

228
00:16:57,860 --> 00:17:01,490
Wir haben auch nicht bis 7 als unseren Root-Knoten haben.

229
00:17:01,490 --> 00:17:03,860
Wir könnten auch 6 als unsere Wurzel.

230
00:17:03,860 --> 00:17:06,470
Was würde das aussehen?

231
00:17:06,470 --> 00:17:09,230
Wenn wir gehen, um dieses bestellt Immobilie zu erhalten,

232
00:17:09,230 --> 00:17:12,970
alles links der 6 muss kleiner sein als dieser.

233
00:17:12,970 --> 00:17:16,540
Es gibt nur eine Möglichkeit, und das ist 3.

234
00:17:16,540 --> 00:17:19,869
Aber dann, als der rechte Kind von 6, haben wir zwei Möglichkeiten.

235
00:17:19,869 --> 00:17:25,380
Erstens könnten wir die 7 und dann die 9,

236
00:17:25,380 --> 00:17:28,850
oder wir ziehen konnte sie - wie ich bin zu tun -

237
00:17:28,850 --> 00:17:34,790
wo wir die 9 haben wie die rechte Kind der 6,

238
00:17:34,790 --> 00:17:39,050
und dann wird das 7 als linke Kind der 9.

239
00:17:39,050 --> 00:17:44,240
>> Nun sind 7 und 6, die nicht die einzig möglichen Werte für die Wurzel.

240
00:17:44,240 --> 00:17:50,200
Wir könnten auch 3 an der Wurzel.

241
00:17:50,200 --> 00:17:52,240
Was passiert, wenn 3 ist an der Wurzel?

242
00:17:52,240 --> 00:17:54,390
Hier werden die Dinge ein wenig interessanter.

243
00:17:54,390 --> 00:17:58,440
Drei hat keine Werte, die kleiner als es ist,

244
00:17:58,440 --> 00:18:02,070
so dass ganze linke Seite des Baumes wird nur noch zu null.

245
00:18:02,070 --> 00:18:03,230
Es ist gar nichts da sein.

246
00:18:03,230 --> 00:18:07,220
Auf der rechten Seite können wir die Dinge in aufsteigender Reihenfolge aufzulisten.

247
00:18:07,220 --> 00:18:15,530
Wir hätten 3, dann 6, dann 7, dann 9.

248
00:18:15,530 --> 00:18:26,710
Oder könnten wir tun, 3, dann 6, dann 9, dann 7.

249
00:18:26,710 --> 00:18:35,020
Oder könnten wir tun, 3, dann 7, dann 6, dann 9.

250
00:18:35,020 --> 00:18:40,950
Oder, 3, 7 - eigentlich nicht, können wir nicht tun, ein 7 nicht mehr.

251
00:18:40,950 --> 00:18:43,330
Das ist unser eins gibt.

252
00:18:43,330 --> 00:18:54,710
Wir können tun, 9, und dann von der 9 können wir 6 zu tun und dann 7.

253
00:18:54,710 --> 00:19:06,980
Oder können wir tun, 3, dann 9, dann 7, dann 6.

254
00:19:06,980 --> 00:19:12,490
>> Eine Sache, die Ihre Aufmerksamkeit hier zu zeichnen

255
00:19:12,490 --> 00:19:14,510
dass diese Bäume sind ein wenig seltsam aussehenden.

256
00:19:14,510 --> 00:19:17,840
Insbesondere dann, wenn wir uns mit den 4 Bäume auf der rechten Seite -

257
00:19:17,840 --> 00:19:20,930
Ich werde umkreisen sie hier -

258
00:19:20,930 --> 00:19:28,410
diese Bäume sehen fast genauso aus wie einer verketteten Liste.

259
00:19:28,410 --> 00:19:32,670
Jeder Knoten hat nur ein Kind,

260
00:19:32,670 --> 00:19:38,950
und so haben wir nicht jede dieser baumartigen Struktur, die wir sehen, zum Beispiel,

261
00:19:38,950 --> 00:19:44,720
 in diesem ein einsamer Baum hier in der unteren linken.

262
00:19:44,720 --> 00:19:52,490
Diese Bäume werden tatsächlich aufgerufen entarteten binären Bäumen,

263
00:19:52,490 --> 00:19:54,170
und wir werden über diese mehr in die Zukunft zu reden -

264
00:19:54,170 --> 00:19:56,730
vor allem, wenn du gehst zu anderen Informatik teilzunehmen.

265
00:19:56,730 --> 00:19:59,670
Diese Bäume sind entartet.

266
00:19:59,670 --> 00:20:03,780
Sie sind nicht sehr nützlich, weil, ja, verleiht diese Struktur selbst

267
00:20:03,780 --> 00:20:08,060
 zu Zeiten ähnlich einer verketteten Liste Lookup.

268
00:20:08,060 --> 00:20:13,050
Wir bekommen nicht den Vorteil der zusätzlichen Speicher zu nehmen - diese zusätzliche Zeiger -

269
00:20:13,050 --> 00:20:18,840
aufgrund unserer Struktur ist auf diese Weise schlecht.

270
00:20:18,840 --> 00:20:24,700
Anstatt sich auf und ziehen Sie die binären Bäumen, 9 haben an der Wurzel,

271
00:20:24,700 --> 00:20:27,220
das ist der letzte Fall, dass wir hätten,

272
00:20:27,220 --> 00:20:32,380
Wir sind stattdessen an dieser Stelle geht ein wenig über diese andere Sicht sprechen

273
00:20:32,380 --> 00:20:36,150
, die wir verwenden, wenn es um Bäume, die als die Höhe ist.

274
00:20:36,150 --> 00:20:45,460
>> Die Höhe eines Baumes ist der Abstand von der Wurzel bis zur höchstwertigen entfernten Knoten,

275
00:20:45,460 --> 00:20:48,370
oder vielmehr die Anzahl der Hops, dass Sie müssten zu machen, um

276
00:20:48,370 --> 00:20:53,750
Ausgehend von der Wurzel und dann am Ende am meisten entfernten Knoten im Baum.

277
00:20:53,750 --> 00:20:57,330
Wenn wir einen Blick auf einige dieser Bäume, die wir hier gezeichnet,

278
00:20:57,330 --> 00:21:07,870
können wir sehen, dass, wenn wir diesen Baum in der linken oberen Ecke, und wir beginnen an der 3,

279
00:21:07,870 --> 00:21:14,510
dann müssen wir 1 Hop bis zum 6 zu erhalten, eine zweite Hop bis zum 7 zu bekommen machen,

280
00:21:14,510 --> 00:21:20,560
und eine dritte Hop bis an die 9 zu bekommen.

281
00:21:20,560 --> 00:21:26,120
So ist die Höhe des Baumes 3.

282
00:21:26,120 --> 00:21:30,640
Wir können die gleiche Übung für die anderen Bäume mit dieser grün umrandet,

283
00:21:30,640 --> 00:21:40,100
und man sieht, dass die Höhe aller dieser Bäume auch tatsächlich 3.

284
00:21:40,100 --> 00:21:45,230
Das ist ein Teil dessen, was sie degenerieren -

285
00:21:45,230 --> 00:21:53,750
dass ihre Höhe ist nur eine weniger als die Anzahl von Knoten in dem gesamten Baum.

286
00:21:53,750 --> 00:21:58,400
Wenn wir uns an diesem anderen Baum, umgeben mit rot ist, auf der anderen Seite,

287
00:21:58,400 --> 00:22:03,920
sehen wir, dass die meisten entfernten Blattknoten die 6 und die 9 sind -

288
00:22:03,920 --> 00:22:06,940
die Blätter sind die Knoten, die keine Kinder haben.

289
00:22:06,940 --> 00:22:11,760
So, um von dem Wurzelknoten entweder der 6 oder der 9 zu erhalten,

290
00:22:11,760 --> 00:22:17,840
Wir müssen einen Hop machen, um zu der 7 erhalten und dann ein zweites Hop zu dem 9 zu erhalten,

291
00:22:17,840 --> 00:22:21,240
und ebenfalls, um nur eine aus der zweiten Sprungperiode 7 zur 6 erhalten.

292
00:22:21,240 --> 00:22:29,080
So ist die Höhe des Baumes hier nur 2.

293
00:22:29,080 --> 00:22:35,330
Sie können zurück gehen und tun, dass für alle anderen Bäume, die wir zuvor besprochen

294
00:22:35,330 --> 00:22:37,380
beginnend mit dem der 7 und 6,

295
00:22:37,480 --> 00:22:42,500
und Sie werden feststellen, dass die Höhe der all diese Bäume auch gleich 2 ist.

296
00:22:42,500 --> 00:22:46,320
>> Der Grund, über die wir gesprochen haben geordnete binäre Bäume

297
00:22:46,320 --> 00:22:50,250
und warum sie cool ist, weil man durch sie in suchen

298
00:22:50,250 --> 00:22:53,810
eine sehr ähnliche Weise mit der Suche über einen sortierten Array.

299
00:22:53,810 --> 00:22:58,720
Dies ist, wo wir darum, dass eine verbesserte Lookup Zeit sprechen

300
00:22:58,720 --> 00:23:02,730
gegenüber dem einfachen verketteten Liste.

301
00:23:02,730 --> 00:23:05,010
Mit einer verketteten Liste - wenn Sie möchten ein bestimmtes Element zu finden -

302
00:23:05,010 --> 00:23:07,470
Sie sind am besten gehen, um irgendeine Art von linearen Suche zu tun

303
00:23:07,470 --> 00:23:10,920
wo Sie beginnen am Anfang einer Liste und hop one-by-one -

304
00:23:10,920 --> 00:23:12,620
ein Knoten von einem Knoten -

305
00:23:12,620 --> 00:23:16,060
durch die gesamte Liste, bis Sie finden, was Sie suchen.

306
00:23:16,060 --> 00:23:19,440
Während, wenn Sie einen binären Baum, der in diesem schönen Format gespeichert ist haben,

307
00:23:19,440 --> 00:23:23,300
können Sie tatsächlich mehr von einem binären Suche geht

308
00:23:23,300 --> 00:23:25,160
wo man teile und herrsche

309
00:23:25,160 --> 00:23:29,490
und die Suche durch die entsprechende Hälfte des Baumes bei jedem Schritt.

310
00:23:29,490 --> 00:23:32,840
Mal sehen, wie das funktioniert.

311
00:23:32,840 --> 00:23:38,850
>> Wenn wir - wieder zurück zu unserer ursprünglichen Baum -

312
00:23:38,850 --> 00:23:46,710
Wir beginnen bei 7, haben wir 3 auf der linken Seite 9 auf der rechten Seite,

313
00:23:46,710 --> 00:23:51,740
und unterhalb der 3 haben wir die 6.

314
00:23:51,740 --> 00:24:01,880
Wenn wir für die Zahl 6 in diesem Baum suchen möchten, würden wir an der Wurzel beginnen.

315
00:24:01,880 --> 00:24:08,910
Wir würden vergleichen Sie den Wert wir für, sagen wir 6 suchen,

316
00:24:08,910 --> 00:24:12,320
auf den Wert des Knotens, dass wir derzeit auf der Suche an, 7 gespeichert,

317
00:24:12,320 --> 00:24:21,200
feststellen, dass 6 ist in der Tat weniger als 7, so würden wir nach links zu bewegen.

318
00:24:21,200 --> 00:24:25,530
Wenn der Wert von 6 war größer als 7 würden wir stattdessen nach rechts verschoben wurden.

319
00:24:25,530 --> 00:24:29,770
Da wir wissen, dass - bedingt durch die Struktur unserer geordnete binäre Baum -

320
00:24:29,770 --> 00:24:33,910
alle Werte kleiner als 7 gehen, um nach links von 7 gespeichert werden,

321
00:24:33,910 --> 00:24:40,520
es gibt keine Notwendigkeit, um einmal die Mühe, durch die rechte Seite des Baumes.

322
00:24:40,520 --> 00:24:43,780
Sobald wir nach links zu bewegen, und wir sind jetzt an dem Knoten mit 3,

323
00:24:43,780 --> 00:24:48,110
können wir die gleiche Vergleich wieder tun, wo wir die 3 und die 6 vergleichen.

324
00:24:48,110 --> 00:24:52,430
Und wir finden, dass während 6 - der Wert, die wir suchen - größer als 3 ist,

325
00:24:52,430 --> 00:24:58,580
man an der rechten Seite des Knotens, die 3 gehen.

326
00:24:58,580 --> 00:25:02,670
Es gibt keine linken Seite hier, so konnten wir ignoriert, dass haben.

327
00:25:02,670 --> 00:25:06,510
Aber wir wissen nur, dass, weil wir auf den Baum selbst suchen,

328
00:25:06,510 --> 00:25:08,660
und wir können sehen, dass der Baum keine Kinder hat.

329
00:25:08,660 --> 00:25:13,640
>> Es ist auch recht einfach zum Nachschlagen 6 in diesem Baum, wenn wir es tun uns als Menschen,

330
00:25:13,640 --> 00:25:16,890
aber wir folgen diesen Prozess mechanisch wie ein Computer tun würde

331
00:25:16,890 --> 00:25:18,620
um wirklich zu verstehen den Algorithmus.

332
00:25:18,620 --> 00:25:26,200
An diesem Punkt sind wir nun auf der Suche an einem Knoten, der 6 enthält,

333
00:25:26,200 --> 00:25:29,180
und wir sind für den Wert 6 suchen,

334
00:25:29,180 --> 00:25:31,740
ja, ja, haben wir die entsprechenden Knoten gefunden.

335
00:25:31,740 --> 00:25:35,070
Wir fanden den Wert 6 in unserem Baum, und wir können unsere Suche zu beenden.

336
00:25:35,070 --> 00:25:37,330
An diesem Punkt, je nachdem, was los ist,

337
00:25:37,330 --> 00:25:41,870
können wir sagen, ja, wir haben den Wert 6 zu finden, gibt es in unserem Baum.

338
00:25:41,870 --> 00:25:47,640
Oder, wenn wir planen, einen Knoten einzufügen oder etwas tun wollen, können wir das an dieser Stelle tun.

339
00:25:47,640 --> 00:25:53,010
>> Lassen Sie uns ein paar mehr Lookups nur, wie das funktioniert.

340
00:25:53,010 --> 00:25:59,390
Lassen Sie uns an, was passiert, wenn wir versuchen, und schauen Sie den Wert 10 waren zu sehen.

341
00:25:59,390 --> 00:26:02,970
Wenn wir schauen den Wert 10, so würden wir an der Wurzel beginnen.

342
00:26:02,970 --> 00:26:07,070
Wir würden sehen, dass 10 größer als 7 ist, so würden wir nach rechts zu bewegen.

343
00:26:07,070 --> 00:26:13,640
Wir würden auf die 9 erhalten und zu vergleichen 9 bis 10 und der 9 zu sehen, dass in der Tat weniger als 10 ist.

344
00:26:13,640 --> 00:26:16,210
Also noch einmal, wir würden versuchen, nach rechts zu bewegen.

345
00:26:16,210 --> 00:26:20,350
Aber an diesem Punkt, würden wir feststellen, dass wir in einem null Knoten sind.

346
00:26:20,350 --> 00:26:23,080
Da ist nichts. Es gibt nichts, wo die 10 sein sollte.

347
00:26:23,080 --> 00:26:29,360
Dies ist, wo wir Fehler melden können -, dass es in der Tat keine 10 in den Baum.

348
00:26:29,360 --> 00:26:35,420
Und schließlich wollen wir durch den Fall, wo wir versuchen, schauen 1 in dem Baum sind zu gehen.

349
00:26:35,420 --> 00:26:38,790
Dies ist ähnlich dem, was passiert, wenn wir bis 10 zu sehen, außer anstatt nach rechts,

350
00:26:38,790 --> 00:26:41,260
werden wir nach links gehen.

351
00:26:41,260 --> 00:26:46,170
Wir starten an der 7 und sehen, dass ein weniger als 7, so dass wir nach links zu bewegen.

352
00:26:46,170 --> 00:26:51,750
Wir bekommen die 3 und sehen, dass 1 kleiner als 3 ist, so wir wieder versuchen, nach links zu bewegen.

353
00:26:51,750 --> 00:26:59,080
An diesem Punkt haben wir eine Null-Knoten haben, so können wir wieder berichten Scheitern.

354
00:26:59,080 --> 00:27:10,260
>> Wenn Sie möchten mehr über binären Bäumen lernen,

355
00:27:10,260 --> 00:27:14,420
Es gibt eine ganze Reihe von lustigen kleinen Probleme, die man mit ihnen machen kann.

356
00:27:14,420 --> 00:27:19,450
I alleinigen Ausübung der Zeichnung aus diesen Diagrammen ein-by-one

357
00:27:19,450 --> 00:27:21,910
und im Anschluss durch alle der verschiedenen Schritte,

358
00:27:21,910 --> 00:27:25,060
denn dies wird in super-praktisch,

359
00:27:25,060 --> 00:27:27,480
nicht nur, wenn du tust das Huffman-Kodierung Problem set

360
00:27:27,480 --> 00:27:29,390
sondern auch in Zukunft Kurse -

361
00:27:29,390 --> 00:27:32,220
nur zu lernen, wie man ziehen diese Datenstrukturen und denken über die Probleme

362
00:27:32,220 --> 00:27:38,000
mit Stift und Papier oder in diesem Fall, iPad und Stift.

363
00:27:38,000 --> 00:27:41,000
>> An diesem Punkt aber, wir gehen auf dem Weg zu etwas Codierung der Praxis zu tun

364
00:27:41,000 --> 00:27:44,870
und tatsächlich mit diesen binären Bäumen zu spielen und zu sehen.

365
00:27:44,870 --> 00:27:52,150
Ich werde, um wieder zu meinem Computer.

366
00:27:52,150 --> 00:27:58,480
Für diesen Teil des Abschnitts, anstatt CS50 Run oder CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Ich werde das Gerät zu benutzen.

368
00:28:01,500 --> 00:28:04,950
>> Nach zusammen mit dem Problem Set Spezifikation

369
00:28:04,950 --> 00:28:07,740
Ich sehe, dass ich soll die Öffnung des Gerätes,

370
00:28:07,740 --> 00:28:11,020
gehen, um meine Dropbox Ordner einen Ordner namens Section 7,

371
00:28:11,020 --> 00:28:15,730
und erstellen Sie dann eine Datei namens binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Here we go. Ich habe das Gerät bereits geöffnet.

373
00:28:22,050 --> 00:28:25,910
Ich werde nach oben ziehen ein Terminal.

374
00:28:25,910 --> 00:28:38,250
Ich werde an den Dropbox-Ordner gehen, stellen ein Verzeichnis namens Abschnitt 7,

375
00:28:38,250 --> 00:28:42,230
und sehen, es ist völlig leer.

376
00:28:42,230 --> 00:28:48,860
Jetzt werde ich zu eröffnen binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Hier gehen wir - leere Datei.

378
00:28:51,750 --> 00:28:54,330
>> Gehen wir zurück zu der Spezifikation.

379
00:28:54,330 --> 00:28:59,850
Die Spezifikation fordert eine neue Typdefinition erstellen

380
00:28:59,850 --> 00:29:03,080
für einen Binärbaum Knoten mit int-Werten -

381
00:29:03,080 --> 00:29:07,110
ebenso wie die Werte, die wir zogen in unserem Diagrammen vor.

382
00:29:07,110 --> 00:29:11,740
Wir gehen zur Nutzung dieser Textvorschlag typedef, dass wir hier getan

383
00:29:11,740 --> 00:29:14,420
Sie sollten von Problem Set 5 zu erkennen -

384
00:29:14,420 --> 00:29:19,190
wenn Sie taten die Hash-Tabelle Art der Eroberung des Speller Programm.

385
00:29:19,190 --> 00:29:22,540
Sie sollten auch erkennen aus der vergangenen Woche Abschnitt

386
00:29:22,540 --> 00:29:23,890
wo wir sprachen über verkettete Listen.

387
00:29:23,890 --> 00:29:27,870
Wir haben dieses typedef eines struct Knoten

388
00:29:27,870 --> 00:29:34,430
und wir haben angesichts dieser struct node diesen Namen struct node vorab

389
00:29:34,430 --> 00:29:39,350
so dass wir dann zu beziehen, da wir wollen, werde mit struct node Zeigern

390
00:29:39,350 --> 00:29:45,740
als Teil unserer struct, aber wir haben dann umkreist diese -

391
00:29:45,740 --> 00:29:47,700
oder vielmehr, eingeschlossen das - in einem typedef

392
00:29:47,700 --> 00:29:54,600
so dass später im Code, können wir diese Struktur als nur einem Knoten anstelle eines struct Knoten verweisen.

393
00:29:54,600 --> 00:30:03,120
>> Das wird sehr ähnlich sein der einfach verknüpfte Liste Definition, dass wir letzte Woche gesehen haben.

394
00:30:03,120 --> 00:30:20,070
Um dies zu tun, lasst uns einfach, indem Sie den Textvorschlag starten.

395
00:30:20,070 --> 00:30:23,840
Wir wissen, dass wir einen ganzzahligen Wert haben müssen,

396
00:30:23,840 --> 00:30:32,170
so dass wir in int Wert legen, und dann statt mit nur einem Zeiger auf das nächste Element -

397
00:30:32,170 --> 00:30:33,970
wie wir es mit einfach-verkettete Listen -

398
00:30:33,970 --> 00:30:38,110
wir gehen nach links und rechts Kind Zeigern.

399
00:30:38,110 --> 00:30:42,880
Das ist ziemlich einfach zu - struct node * linke Kind;

400
00:30:42,880 --> 00:30:51,190
und struct node * rechtes Kind;. Cool.

401
00:30:51,190 --> 00:30:54,740
Das sieht wie ein ziemlich guter Anfang.

402
00:30:54,740 --> 00:30:58,530
Gehen wir zurück zu der Spezifikation.

403
00:30:58,530 --> 00:31:05,030
>> Jetzt brauchen wir eine globale node * Variable für die Wurzel eines Baumes zu erklären.

404
00:31:05,030 --> 00:31:10,590
Wir gehen, um diese globale genauso wie wir erste Zeiger machte in unserem verketteten Liste auch global.

405
00:31:10,590 --> 00:31:12,690
Dies war, so dass in den Funktionen, die wir schreiben

406
00:31:12,690 --> 00:31:16,180
wir haben nicht zu halten, das um diese Wurzel -

407
00:31:16,180 --> 00:31:19,620
wenn wir sehen, dass, wenn Sie tun, um diese Funktionen rekursiv schreiben wollen,

408
00:31:19,620 --> 00:31:22,830
es wäre besser, gar nicht geben sie herum, als ein globales in erster Linie

409
00:31:22,830 --> 00:31:28,090
und stattdessen initialisieren lokal in Ihrem Hauptfunktion.

410
00:31:28,090 --> 00:31:31,960
Aber, werden wir es weltweit zu tun, um zu starten.

411
00:31:31,960 --> 00:31:39,920
Auch geben wir ein paar Plätze, und ich werde einen Knoten * Wurzel zu erklären.

412
00:31:39,920 --> 00:31:46,770
Nur um sicherzugehen, dass ich nicht lassen Sie dieses nicht initialisiert, werde ich es gleich auf null gesetzt.

413
00:31:46,770 --> 00:31:52,210
Jetzt, in der Hauptfunktion - die wir sehr schnell hier schreiben -

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

415
00:32:00,450 --> 00:32:10,640
und ich werde anfangen erklärte meinem argv Array als const nur so, dass ich weiß,

416
00:32:10,640 --> 00:32:14,550
dass diese Argumente sind Argumente, die ich wahrscheinlich nicht ändern möchten.

417
00:32:14,550 --> 00:32:18,390
Wenn ich sie ändern möchten Ich sollte wahrscheinlich werden die Anfertigung von Kopien von ihnen.

418
00:32:18,390 --> 00:32:21,740
Du wirst sehen, das eine Menge im Code.

419
00:32:21,740 --> 00:32:25,440
Es ist in Ordnung so oder so. Es ist in Ordnung, um sie als verlassen - weglassen const, wenn Sie möchten.

420
00:32:25,440 --> 00:32:28,630
I in der Regel legen Sie sie in nur so, dass ich mich daran erinnern,

421
00:32:28,630 --> 00:32:33,650
 dass ich wahrscheinlich nicht wollen, dass diese Argumente ändern.

422
00:32:33,650 --> 00:32:39,240
>> Wie immer werde ich dieses return 0 Zeile am Ende der wichtigsten gehören.

423
00:32:39,240 --> 00:32:45,730
Hier werde ich zu initialisieren mein Root-Knoten.

424
00:32:45,730 --> 00:32:48,900
Wie es jetzt steht, habe ich einen Zeiger, der auf Null gesetzt ist,

425
00:32:48,900 --> 00:32:52,970
so ist es an nichts zeigen.

426
00:32:52,970 --> 00:32:57,480
Um tatsächlich mit dem Bau des Knotens

427
00:32:57,480 --> 00:32:59,250
Ich muss zuerst in den Speicher für sie bereitzustellen.

428
00:32:59,250 --> 00:33:05,910
Ich werde das, indem Speicher auf dem Heap mit malloc tun.

429
00:33:05,910 --> 00:33:10,660
Ich werde root gleich dem Ergebnis von malloc gesetzt,

430
00:33:10,660 --> 00:33:19,550
und ich werde den sizeof-Operator verwenden, um die Größe eines Knotens zu berechnen.

431
00:33:19,550 --> 00:33:24,990
Der Grund, dass ich sizeof Knoten verwenden, im Gegensatz zu, sagen wir,

432
00:33:24,990 --> 00:33:37,020
etwas zu tun, wie diese - malloc (4 + 4 +4) oder malloc 12 -

433
00:33:37,020 --> 00:33:40,820
ist, weil ich meinen Code so kompatibel wie möglich wollen.

434
00:33:40,820 --> 00:33:44,540
Ich möchte in der Lage sein, diese. C-Datei zu nehmen, kompiliert es auf dem Gerät,

435
00:33:44,540 --> 00:33:48,820
und kompilieren Sie es auf meinem 64-Bit-Mac -

436
00:33:48,820 --> 00:33:52,040
oder auf einer völlig anderen Architektur -

437
00:33:52,040 --> 00:33:54,640
und ich möchte das alles, um die gleiche Arbeit.

438
00:33:54,640 --> 00:33:59,510
>> Wenn ich mache Annahmen über die Größe von Variablen -

439
00:33:59,510 --> 00:34:02,070
die Größe eines int oder die Größe eines Zeigers -

440
00:34:02,070 --> 00:34:06,070
dann bin ich auch Annahmen über die Arten von Architekturen

441
00:34:06,070 --> 00:34:10,440
, auf dem mein Code erfolgreich kompilieren, wenn laufen.

442
00:34:10,440 --> 00:34:15,030
Immer sizeof zur manuellen Summieren der struct Bereichen entgegen.

443
00:34:15,030 --> 00:34:20,500
Der andere Grund ist, dass es vielleicht auch padding, dass der Compiler in der Struktur setzt sein.

444
00:34:20,500 --> 00:34:26,570
Auch nur die Summierung der einzelnen Felder ist nicht etwas, dass Sie in der Regel tun wollen,

445
00:34:26,570 --> 00:34:30,340
ja, löschen Sie diese Zeile.

446
00:34:30,340 --> 00:34:33,090
Nun, um wirklich zu initialisieren dieses Root-Knoten,

447
00:34:33,090 --> 00:34:36,489
Ich bin zu haben, um in den Werten für jedes seiner verschiedenen Bereichen stecken.

448
00:34:36,489 --> 00:34:41,400
Zum Beispiel für den Wert Ich weiß, ich will bis 7 zu initialisieren,

449
00:34:41,400 --> 00:34:46,920
und jetzt werde ich um das linke Kind zu sein null

450
00:34:46,920 --> 00:34:55,820
und das rechte Kind auch null sein. Great!

451
00:34:55,820 --> 00:35:02,670
Wir haben diesen Teil des spec getan.

452
00:35:02,670 --> 00:35:07,390
>> Die Spezifikation, die an der Unterseite von Seite 3 bittet mich, noch drei weitere Knoten zu erstellen -

453
00:35:07,390 --> 00:35:10,600
ein mit 3, ein mit 6 und eines mit 9 -

454
00:35:10,600 --> 00:35:14,210
und dann verdrahten so genau wie unsere Baumdiagramm sieht

455
00:35:14,210 --> 00:35:17,120
dass wir redeten zuvor.

456
00:35:17,120 --> 00:35:20,450
Lassen Sie uns das ziemlich schnell hier.

457
00:35:20,450 --> 00:35:26,270
Du wirst sehr schnell sehen, dass ich gehe mit dem Schreiben beginnen eine Reihe von doppelten Code.

458
00:35:26,270 --> 00:35:32,100
Ich werde einen Knoten * schaffen und ich werde nennen es drei.

459
00:35:32,100 --> 00:35:36,000
Ich werde um sie gleich malloc (sizeof (Knoten)).

460
00:35:36,000 --> 00:35:41,070
Ich werde um drei-> value = 3.

461
00:35:41,070 --> 00:35:54,780
Drei -> left_child = NULL; drei -> rechts _child = NULL; als gut.

462
00:35:54,780 --> 00:36:01,150
Das sieht ziemlich ähnlich wie die Initialisierung der Wurzel, und das ist genau das, was

463
00:36:01,150 --> 00:36:05,760
Ich werde zu tun haben, wenn ich die Initialisierung 6 und 9 sowie beginnen.

464
00:36:05,760 --> 00:36:20,720
Das werde ich ganz schnell hier zu tun - eigentlich, ich werde ein wenig copy and paste zu tun,

465
00:36:20,720 --> 00:36:46,140
und stellen Sie sicher, dass ich - in Ordnung.

466
00:36:46,470 --> 00:37:09,900
 Nun, ich habe es kopiert und ich kann gehen Sie vor und setzen Sie diese gleich 6 ist.

467
00:37:09,900 --> 00:37:14,670
Sie können sehen, dass dies eine Weile dauert und ist nicht super-effizient.

468
00:37:14,670 --> 00:37:22,610
In nur ein wenig, dann schreiben wir eine Funktion, die das für uns tun wird.

469
00:37:22,610 --> 00:37:32,890
Ich möchte dies mit einem 9 zu ersetzen, ersetzen, die mit einem 6.

470
00:37:32,890 --> 00:37:37,360
>> Jetzt haben wir alle unsere Knoten erstellt und initialisiert.

471
00:37:37,360 --> 00:37:41,200
Wir haben unsere Wurzel gleich 7 oder mit dem Wert 7,

472
00:37:41,200 --> 00:37:46,510
unseren Knoten mit 3, unser Knoten mit 6, und unsere Knoten mit 9.

473
00:37:46,510 --> 00:37:50,390
An diesem Punkt ist alles, was wir zu tun haben, wire alles durcheinander.

474
00:37:50,390 --> 00:37:53,020
Der Grund warum ich initialisiert alle Zeiger auf null ist einfach so, dass ich mir sicher, dass zu machen

475
00:37:53,020 --> 00:37:56,260
Ich habe noch keine initialisierte Zeiger dort durch Zufall.

476
00:37:56,260 --> 00:38:02,290
Und auch da, an diesem Punkt, ich habe nur tatsächlich verbinden die Knoten miteinander -

477
00:38:02,290 --> 00:38:04,750
um diejenigen, die sie tatsächlich sind angeschlossen - ich weiß nicht zu durchlaufen haben und machen

478
00:38:04,750 --> 00:38:08,240
sicher, dass alle Nullen in gibt es an den entsprechenden Stellen.

479
00:38:08,240 --> 00:38:15,630
>> Beginnend an der Wurzel, ich weiß, dass die Wurzel des linken Kind 3 ist.

480
00:38:15,630 --> 00:38:21,250
Ich weiß, dass der Root-rechte Kind 9 ist.

481
00:38:21,250 --> 00:38:24,880
Danach wird das einzige andere Kind, das ich verlassen haben Grund zur Sorge

482
00:38:24,880 --> 00:38:39,080
3 ist das rechte Kind, die 6 ist.

483
00:38:39,080 --> 00:38:44,670
An diesem Punkt, es sieht alles ziemlich gut.

484
00:38:44,670 --> 00:38:54,210
Wir löschen Sie einige dieser Zeilen.

485
00:38:54,210 --> 00:38:59,540
Jetzt sieht alles ziemlich gut.

486
00:38:59,540 --> 00:39:04,240
Gehen wir zurück zu unserer Spezifikation und sehen, was wir als nächstes zu tun haben.

487
00:39:04,240 --> 00:39:07,610
>> An diesem Punkt müssen wir schreiben eine Funktion namens 'enthält'

488
00:39:07,610 --> 00:39:14,150
mit einem Prototyp des 'bool contains (int value)'.

489
00:39:14,150 --> 00:39:17,060
Und diese Funktion contains wird return true

490
00:39:17,060 --> 00:39:21,200
 wenn der Baum auf die durch unsere globale root variable

491
00:39:21,200 --> 00:39:26,950
 enthält den Wert in die Funktion und andernfalls false übergeben.

492
00:39:26,950 --> 00:39:29,000
Lasst uns weitermachen und tun.

493
00:39:29,000 --> 00:39:35,380
Das wird genau wie der Lookup, dass wir mit der Hand auf dem iPad nur ein bisschen vor getan haben.

494
00:39:35,380 --> 00:39:40,130
Lassen Sie uns zurück vergrößern ein wenig und nach oben.

495
00:39:40,130 --> 00:39:43,130
Wir werden diese Funktion oben rechts unsere Funktion setzen

496
00:39:43,130 --> 00:39:48,990
so dass wir nicht jede Art von Prototyping tun.

497
00:39:48,990 --> 00:39:55,960
So enthält bool (int value).

498
00:39:55,960 --> 00:40:00,330
Dort gehen wir. Es ist unser Textvorschlag Erklärung.

499
00:40:00,330 --> 00:40:02,900
Nur um sicherzugehen, dass dies zu kompilieren,

500
00:40:02,900 --> 00:40:06,820
Ich werde weitermachen und nur setzen Sie ihn gleich false zurück.

501
00:40:06,820 --> 00:40:09,980
Gerade jetzt diese Funktion einfach nicht tun und immer berichten, dass

502
00:40:09,980 --> 00:40:14,010
der Wert, den wir suchen, ist nicht in den Baum.

503
00:40:14,010 --> 00:40:16,280
>> An dieser Stelle ist es wahrscheinlich eine gute Idee -

504
00:40:16,280 --> 00:40:19,600
da haben wir eine ganze Reihe von Code geschrieben, und wir haben nicht einmal versucht testet es noch -

505
00:40:19,600 --> 00:40:22,590
um sicherzustellen, dass alles kompiliert.

506
00:40:22,590 --> 00:40:27,460
Es gibt ein paar Dinge, die wir tun müssen, um sicherzustellen, dass dies auch tatsächlich zu kompilieren.

507
00:40:27,460 --> 00:40:33,530
Zunächst sehen, ob wir verwendet haben alle Funktionen in allen Bibliotheken, die wir noch nicht berücksichtigt.

508
00:40:33,530 --> 00:40:37,940
Die Funktionen, die wir bisher verwendet werden, malloc,

509
00:40:37,940 --> 00:40:43,310
und dann haben wir auch mit dieser Art - dieses standardmäßige Typ namens 'bool' -

510
00:40:43,310 --> 00:40:45,750
die in der Standard-bool Header-Datei enthalten.

511
00:40:45,750 --> 00:40:53,250
Wir wollen auf jeden Standard-bool.h für den bool-Typ gehören,

512
00:40:53,250 --> 00:40:59,230
und wir wollen auch # include standard lib.h für die Standard-Bibliotheken

513
00:40:59,230 --> 00:41:03,530
das sind malloc, und frei, und das alles.

514
00:41:03,530 --> 00:41:08,660
So, Verkleinern, werden wir beenden.

515
00:41:08,660 --> 00:41:14,190
Lassen Sie uns versuchen und sicherstellen, dass diese tatsächlich kompilieren.

516
00:41:14,190 --> 00:41:18,150
Wir sehen, dass es funktioniert, so dass wir auf dem richtigen Weg.

517
00:41:18,150 --> 00:41:22,990
>> Lasst uns eröffnen binary_tree.c wieder.

518
00:41:22,990 --> 00:41:34,530
Es kompiliert. Lasst uns nach unten gehen und sicherstellen, dass wir ein paar Anrufe einsetzen, um unseren contains-Funktion -

519
00:41:34,530 --> 00:41:40,130
nur um sicherzugehen, dass alles schön und gut ist.

520
00:41:40,130 --> 00:41:43,170
Zum Beispiel, wenn wir einige Lookups haben in unserem Baum zuvor

521
00:41:43,170 --> 00:41:48,500
haben wir versucht, um die Werte 6, 10 und 1, und wir wussten, dass 6 in dem Baum war,

522
00:41:48,500 --> 00:41:52,220
10 war nicht in dem Baum, und 1 war nicht in dem Baum nicht.

523
00:41:52,220 --> 00:41:57,230
Lassen Sie uns diese Probe Anrufe als einen Weg, um herauszufinden, ob

524
00:41:57,230 --> 00:41:59,880
unserer contains Funktion aktiviert ist.

525
00:41:59,880 --> 00:42:05,210
Um das zu tun, werde ich die printf Funktion zu nutzen,

526
00:42:05,210 --> 00:42:10,280
und wir gehen zum Ausdrucken das Ergebnis des Aufrufs enthält.

527
00:42:10,280 --> 00:42:13,280
Ich werde in einem String setzen "enthält (% d) =, weil

528
00:42:13,280 --> 00:42:20,470
 wir steckerfertig gehen in den Wert, den wir gehen, um zu sehen,

529
00:42:20,470 --> 00:42:27,130
und =% s \ n "und verwenden Sie diese als Format-String.

530
00:42:27,130 --> 00:42:30,720
Wir stehen noch gehen, um zu sehen - buchstäblich drucken auf dem Bildschirm -

531
00:42:30,720 --> 00:42:32,060
was aussieht wie ein Funktionsaufruf.

532
00:42:32,060 --> 00:42:33,580
Dies ist nicht wirklich die Funktion Anruf.

533
00:42:33,580 --> 00:42:36,760
 Dies ist nur ein String ausgelegt, wie ein Aufruf der Funktion zu suchen.

534
00:42:36,760 --> 00:42:41,140
>> Nun, wir gehen in den Werten anschließen.

535
00:42:41,140 --> 00:42:43,580
Wir gehen enthält auf 6 versuchen,

536
00:42:43,580 --> 00:42:48,340
und dann, was wir hier tun, ist zu verwenden, dass ternäre Operator.

537
00:42:48,340 --> 00:42:56,340
Mal sehen - enthält 6 - so, jetzt habe ich 6 enthalten und wenn enthält 6 wahr ist,

538
00:42:56,340 --> 00:43:01,850
die Zeichenfolge, werden wir auf die% s-Format Zeichen gesendet

539
00:43:01,850 --> 00:43:04,850
wird die Zeichenfolge "true" sein.

540
00:43:04,850 --> 00:43:07,690
Lassen Sie uns rollen über ein wenig.

541
00:43:07,690 --> 00:43:16,210
Ansonsten wollen wir senden die Zeichenfolge "false", wenn enthält 6 false zurück.

542
00:43:16,210 --> 00:43:19,730
Dies ist ein wenig doof aus, aber ich denke, ich könnte genauso gut veranschaulichen,

543
00:43:19,730 --> 00:43:23,780
was der ternäre Operator aussieht, da haben wir es nicht für eine Weile gesehen.

544
00:43:23,780 --> 00:43:27,670
Das wird ein schöner, praktischer Weg, um herauszufinden, ob unsere contains-Funktion arbeitet sein.

545
00:43:27,670 --> 00:43:30,040
Ich werde zurück blättern nach links,

546
00:43:30,040 --> 00:43:39,900
und ich werde zu kopieren und diese Linie ein paar mal.

547
00:43:39,900 --> 00:43:44,910
Es änderte einige dieser Werte um,

548
00:43:44,910 --> 00:43:59,380
so das wird 1 sein, und dies wird zu 10 betragen.

549
00:43:59,380 --> 00:44:02,480
>> An diesem Punkt haben wir eine nette Funktion CONTAINS.

550
00:44:02,480 --> 00:44:06,080
Wir haben einige Tests, und wir werden sehen, ob das alles funktioniert.

551
00:44:06,080 --> 00:44:08,120
An dieser Stelle haben wir einige mehr Code geschrieben.

552
00:44:08,120 --> 00:44:13,160
Zeit zu beenden heraus und stellen Sie sicher, dass alles noch kompiliert.

553
00:44:13,160 --> 00:44:20,360
Beenden Sie, und jetzt versuchen wir es machen binären Baum wieder.

554
00:44:20,360 --> 00:44:22,260
Nun, es sieht aus wie wir einen Fehler haben,

555
00:44:22,260 --> 00:44:26,930
Und wir haben dies ausdrücklich erklärt die Library-Funktion printf.

556
00:44:26,930 --> 00:44:39,350
Es sieht aus wie wir zu gehen und # include standardio.h müssen.

557
00:44:39,350 --> 00:44:45,350
Und damit sollte alles kompilieren. Wir sind alle gut.

558
00:44:45,350 --> 00:44:50,420
Lassen Sie uns nun versuchen Sie Binärbaum und sehen was passiert.

559
00:44:50,420 --> 00:44:53,520
Hier sind wir. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
und wir sehen, dass, wie wir erwartet hatten -

561
00:44:55,190 --> 00:44:56,910
weil wir nicht umgesetzt haben, enthält noch

562
00:44:56,910 --> 00:44:59,800
oder besser gesagt, haben wir gerade in return false setzen -

563
00:44:59,800 --> 00:45:03,300
sehen wir, dass es nur wieder falsch für alle von ihnen,

564
00:45:03,300 --> 00:45:06,180
Also das ist, arbeiten alle zum größten Teil recht gut.

565
00:45:06,180 --> 00:45:11,860
>> Gehen wir zurück gehen und tatsächlich umzusetzen enthält an dieser Stelle.

566
00:45:11,860 --> 00:45:17,490
Ich werde nach unten scrollen, zoomen und -

567
00:45:17,490 --> 00:45:22,330
erinnere, war der Algorithmus, dass wir gewöhnt, dass wir an der Wurzel Knoten gestartet

568
00:45:22,330 --> 00:45:28,010
und dann an jedem Knoten, denen wir begegnen, machen wir einen Vergleich,

569
00:45:28,010 --> 00:45:32,380
und auf der Grundlage dieses Vergleichs haben wir entweder nach links Kind oder nach rechts Kindes zu bewegen.

570
00:45:32,380 --> 00:45:39,670
Das wird sehr ähnlich aussehen, um die binäre Suche Code, schrieben wir früher in der Laufzeit.

571
00:45:39,670 --> 00:45:47,810
Als wir beginnen, wissen wir, dass wir halten Sie auf dem aktuellen Knoten möchten

572
00:45:47,810 --> 00:45:54,050
dass wir auf der Suche, und der aktuelle Knoten wird zum Wurzelknoten initialisiert werden.

573
00:45:54,050 --> 00:45:56,260
Und jetzt werden wir weitermachen durch den Baum,

574
00:45:56,260 --> 00:45:58,140
und denken Sie daran, dass unsere Stoppbedingung -

575
00:45:58,140 --> 00:46:01,870
 wenn wir tatsächlich geleisteten Arbeitsstunden durch das Beispiel von Hand -

576
00:46:01,870 --> 00:46:03,960
war, als wir eine Null-Knoten auftreten,

577
00:46:03,960 --> 00:46:05,480
nicht, wenn wir an einem null Kind sah,

578
00:46:05,480 --> 00:46:09,620
sondern wenn wir tatsächlich bewegt, um einen Knoten in der Baumstruktur

579
00:46:09,620 --> 00:46:12,640
und festgestellt, dass wir an einem null Knoten sind.

580
00:46:12,640 --> 00:46:20,720
Wir werden durchlaufen, bis Aktuell ist nicht gleich null.

581
00:46:20,720 --> 00:46:22,920
Und was sollen wir jetzt tun?

582
00:46:22,920 --> 00:46:31,610
Wir werden prüfen, ob (Aktuell -> value == Wert),

583
00:46:31,610 --> 00:46:35,160
dann wissen wir, dass wir tatsächlich den Knoten, den wir suchen, gefunden.

584
00:46:35,160 --> 00:46:40,450
Also hier können wir wieder wahr.

585
00:46:40,450 --> 00:46:49,830
Ansonsten wollen wir sehen, ob der Wert kleiner als der Wert ist.

586
00:46:49,830 --> 00:46:53,850
Wenn der aktuelle Knoten den Wert geringer ist als der Wert, den wir suchen,

587
00:46:53,850 --> 00:46:57,280
werden wir nach rechts zu bewegen.

588
00:46:57,280 --> 00:47:10,600
Also, cur = Aktuell -> right_child und ansonsten werden wir nach links zu bewegen.

589
00:47:10,600 --> 00:47:17,480
cur = Aktuell -> left_child;. Ganz einfach.

590
00:47:17,480 --> 00:47:22,830
>> Wahrscheinlich erkennen die Schleife, die sehr ähnlich zu dieser aus sieht

591
00:47:22,830 --> 00:47:27,580
binäre Suche früher im Begriff, außer dann wurden wir mit niedriger, mittlerer und hoher tun.

592
00:47:27,580 --> 00:47:30,000
Hier müssen wir nur noch auf einen aktuellen Wert suchen,

593
00:47:30,000 --> 00:47:31,930
so ist es schön und einfach.

594
00:47:31,930 --> 00:47:34,960
Lassen Sie uns sicherstellen, dass diese Code funktioniert.

595
00:47:34,960 --> 00:47:42,780
Erstens, stellen Sie sicher, dass es kompiliert. Sieht aus wie es funktioniert.

596
00:47:42,780 --> 00:47:47,920
Lassen Sie uns versuchen es läuft.

597
00:47:47,920 --> 00:47:50,160
Und in der Tat, gibt es alles, was wir erwartet haben.

598
00:47:50,160 --> 00:47:54,320
Es findet 6 in den Baum, nicht finden 10, weil 10 ist nicht im Baum,

599
00:47:54,320 --> 00:47:57,740
und nicht über 1 entweder weil 1 ist auch nicht in den Baum.

600
00:47:57,740 --> 00:48:01,420
Cool stuff.

601
00:48:01,420 --> 00:48:04,470
>> Alright. Gehen wir zurück zu unserer Spezifikation und sehen, was als nächstes kommt.

602
00:48:04,470 --> 00:48:07,990
Jetzt will sie noch mehr Knoten zu unserem Baum hinzuzufügen.

603
00:48:07,990 --> 00:48:11,690
Er will 5, 2 und 8 hinzuzufügen, und stellen Sie sicher, dass unser Code enthält

604
00:48:11,690 --> 00:48:13,570
funktioniert immer noch wie erwartet.

605
00:48:13,570 --> 00:48:14,900
Lasst uns das tun.

606
00:48:14,900 --> 00:48:19,430
An dieser Stelle, anstatt sich das lästige Kopieren und Einfügen wieder

607
00:48:19,430 --> 00:48:23,770
schreiben wir eine Funktion, um tatsächlich einen Knoten.

608
00:48:23,770 --> 00:48:27,740
Wenn wir den ganzen Weg zu blättern main, sehen wir, dass wir machen das schon

609
00:48:27,740 --> 00:48:31,210
sehr ähnlichen Code immer und immer wieder jedes Mal, wenn wir wollen, um einen Knoten zu schaffen.

610
00:48:31,210 --> 00:48:39,540
>> Lassen Sie eine Funktion schreiben, die tatsächlich bauen einen Knoten für uns und gibt es zurück.

611
00:48:39,540 --> 00:48:41,960
Ich werde es nennen build_node.

612
00:48:41,960 --> 00:48:45,130
Ich werde einen Knoten mit einem bestimmten Wert zu bauen.

613
00:48:45,130 --> 00:48:51,040
Vergrößern hier.

614
00:48:51,040 --> 00:48:56,600
Das erste, was ich tun werde tatsächlich schaffen Raum für den Knoten auf dem Heap.

615
00:48:56,600 --> 00:49:05,400
Also, Knoten * n = malloc (sizeof (Knoten)); n -> value = Wert;

616
00:49:05,400 --> 00:49:14,960
und dann hier, ich bin gerade dabei, alle Felder zu initialisieren entsprechenden Werte sein.

617
00:49:14,960 --> 00:49:22,500
Und ganz am Ende, wir kehren unsere Knoten.

618
00:49:22,500 --> 00:49:28,690
Alright. Eine Sache zu beachten ist, dass diese Funktion hier

619
00:49:28,690 --> 00:49:34,320
wird um einen Zeiger auf Speicher, der seit Heap zugewiesen hat zurückzukehren.

620
00:49:34,320 --> 00:49:38,880
Was ist schön daran ist, dass dieser Knoten jetzt -

621
00:49:38,880 --> 00:49:42,420
wir müssen es auf dem Heap zu erklären, denn wenn wir es erklärt auf dem Stack

622
00:49:42,420 --> 00:49:45,050
wir nicht in der Lage, sie in dieser Funktion wie dies zu tun.

623
00:49:45,050 --> 00:49:47,690
Dass der Speicher würde out of scope

624
00:49:47,690 --> 00:49:51,590
und wäre ungültig, wenn wir es später zuzugreifen versucht.

625
00:49:51,590 --> 00:49:53,500
Da wir erklären Heap zugewiesenen Speicher,

626
00:49:53,500 --> 00:49:55,830
werden wir haben dafür Sorge zu befreien später nehmen

627
00:49:55,830 --> 00:49:58,530
für unser Programm nicht auslaufen jede Erinnerung.

628
00:49:58,530 --> 00:50:01,270
Wir haben uns auf, dass seit punting für alles andere im Code

629
00:50:01,270 --> 00:50:02,880
nur der Einfachheit halber an der Zeit,

630
00:50:02,880 --> 00:50:05,610
aber wenn Sie jemals eine Funktion schreiben, die wie folgt aussieht

631
00:50:05,610 --> 00:50:10,370
wo hast du - manche nennen es ein malloc oder realloc innen -

632
00:50:10,370 --> 00:50:14,330
Sie wollen sicherstellen, dass Sie irgendeine Art von Kommentar hier aufgestellt, die besagt,

633
00:50:14,330 --> 00:50:29,970
hey, du weißt, gibt einen Heap-zugewiesenen Knoten mit dem übergebenen Wert initialisiert.

634
00:50:29,970 --> 00:50:33,600
Und dann wollen Sie sicherstellen, dass Sie in irgendeiner Art von Notiz, die sagt, setzen

635
00:50:33,600 --> 00:50:41,720
muss der Anrufer befreien die zurückgegebenen Speicher.

636
00:50:41,720 --> 00:50:45,450
Auf diese Weise, wenn jemand überhaupt geht und nutzt diese Funktion,

637
00:50:45,450 --> 00:50:48,150
sie wissen, dass, was sie wieder aus dieser Funktion

638
00:50:48,150 --> 00:50:50,870
an einem gewissen Punkt müssen befreit werden.

639
00:50:50,870 --> 00:50:53,940
>> Vorausgesetzt, dass alles gut und schön ist hier,

640
00:50:53,940 --> 00:51:02,300
wir gehen in unseren Code und ersetzen alle diese Zeilen hier

641
00:51:02,300 --> 00:51:05,410
mit Aufrufen an unser Build-Knoten-Funktion.

642
00:51:05,410 --> 00:51:08,170
Lasst uns das wirklich schnell.

643
00:51:08,170 --> 00:51:15,840
Der eine Teil, dass wir nicht zu ersetzen ist dieser Teil hier unten

644
00:51:15,840 --> 00:51:18,520
an der Unterseite, wo wir eigentlich verdrahten die Knoten miteinander zu verweisen,

645
00:51:18,520 --> 00:51:21,030
denn das können wir nicht in unserer Funktion tun.

646
00:51:21,030 --> 00:51:37,400
Aber lasst uns root = build_node (7); node * drei = build_node (3);

647
00:51:37,400 --> 00:51:47,980
node * sechs = build_node (6); node * neun = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
Und jetzt wollten wir auch Knoten für Add -

649
00:51:52,590 --> 00:52:03,530
node * fünf = build_node (5); node * acht = build_node (8);

650
00:52:03,530 --> 00:52:09,760
und was der andere Knoten? Lasst uns hier zu sehen. Wir wollten auch einen 2 -

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

652
00:52:20,280 --> 00:52:26,850
Alright. An diesem Punkt wissen wir, dass wir haben die 7, die 3, die 9 und die 6

653
00:52:26,850 --> 00:52:30,320
Alle verdrahtet angemessen, aber was ist mit der 5, der 8 und der 2?

654
00:52:30,320 --> 00:52:33,550
Um alles in der richtigen Reihenfolge zu halten,

655
00:52:33,550 --> 00:52:39,230
wir wissen, dass drei der rechten Kind 6 ist.

656
00:52:39,230 --> 00:52:40,890
Also, wenn wir gehen, um die 5 hinzuzufügen,

657
00:52:40,890 --> 00:52:46,670
das 5 gehört auch in der rechten Seite des Baumes, von denen drei die Wurzel ist,

658
00:52:46,670 --> 00:52:50,440
so 5 gehört wie der linke Kind von 6 Jahren.

659
00:52:50,440 --> 00:52:58,650
Wir können dies mit den Worten: sechs zu tun -> left_child = fünf;

660
00:52:58,650 --> 00:53:10,790
und dann die 8 gehört wie das linke Kind von 9, so neun -> left_child = acht;

661
00:53:10,790 --> 00:53:22,190
und dann 2 ist das linke Kind von 3, so können wir das hier tun - dich -> left_child = zwei;.

662
00:53:22,190 --> 00:53:27,730
Wenn Sie nicht ganz folgen hat zusammen mit dem schlage ich vor, Sie ziehen es selbst heraus.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Retten wir dies. Lasst uns gehen und sicherstellen, dass es kompiliert,

664
00:53:35,660 --> 00:53:40,760
und dann können wir in unserem contains Anrufe hinzuzufügen.

665
00:53:40,760 --> 00:53:44,120
Sieht aus wie alles noch kompiliert.

666
00:53:44,120 --> 00:53:51,790
Lasst uns gehen und fügen Sie in einigen enthält Anrufe.

667
00:53:51,790 --> 00:53:59,640
Wieder werde ich ein wenig copy and paste zu tun.

668
00:53:59,640 --> 00:54:15,860
Lassen Sie uns nun für 5, 8 und 2 zu suchen. Alright.

669
00:54:15,860 --> 00:54:28,330
Lassen Sie uns sicherstellen, dass dies alles gut aussieht still. Great! Speichern und beenden.

670
00:54:28,330 --> 00:54:33,220
Nun wollen wir, kompilieren, und nun lasst uns laufen.

671
00:54:33,220 --> 00:54:37,540
Aus den Ergebnissen, es sieht aus wie alles funktioniert einfach schön und gut.

672
00:54:37,540 --> 00:54:41,780
Great! So jetzt haben wir unseren contains geschrieben funktionieren.

673
00:54:41,780 --> 00:54:46,160
Lasst uns weitermachen und anfangen zu arbeiten, wie Sie Knoten in den Baum einfügen

674
00:54:46,160 --> 00:54:50,000
da, wie wir es tun gerade jetzt, sind die Dinge nicht sehr hübsch.

675
00:54:50,000 --> 00:54:52,280
>> Wenn wir zurück auf die Spezifikation,

676
00:54:52,280 --> 00:55:00,540
Es fordert uns auf, eine Funktion namens einzufügen schreiben - wieder und gibt einen bool

677
00:55:00,540 --> 00:55:04,400
für, ob wir tatsächlich fügen Sie den Knoten in den Baum -

678
00:55:04,400 --> 00:55:07,710
und dann der Wert in den Baum einzufügen wie angegeben

679
00:55:07,710 --> 00:55:11,060
das einzige Argument für unsere Insert-Funktion.

680
00:55:11,060 --> 00:55:18,180
Wir werden true zurückgeben, wenn wir in der Tat könnte einzufügen den Knoten enthält den Wert in den Baum,

681
00:55:18,180 --> 00:55:20,930
was bedeutet, dass wir ein, genügend Speicher hatten,

682
00:55:20,930 --> 00:55:24,840
und dann zwei hat, dass der Knoten nicht bereits in dem Baum seit bestehen -

683
00:55:24,840 --> 00:55:32,170
Denken Sie daran, wir sind nicht zu doppelten Werten im Baum haben, nur um die Dinge einfach.

684
00:55:32,170 --> 00:55:35,590
Alright. Sichern, um den Code.

685
00:55:35,590 --> 00:55:44,240
Öffnen Sie es. Zoom ein bisschen, dann nach unten scrollen.

686
00:55:44,240 --> 00:55:47,220
Lasst uns den Insert-Funktion direkt über den enthält.

687
00:55:47,220 --> 00:55:56,360
Wieder, es wird genannt bool insert (int value).

688
00:55:56,360 --> 00:56:01,840
Geben Sie es ein wenig mehr Platz, und dann, als Standard,

689
00:56:01,840 --> 00:56:08,870
Lassen Sie uns in return false ganz am Ende zu setzen.

690
00:56:08,870 --> 00:56:22,620
Jetzt unten am Boden, lassen Sie vor und statt der manuellen Aufbau der Knoten gehen

691
00:56:22,620 --> 00:56:27,900
in main uns und Verkabelung sie bis zu jedem anderen Punkt, wie wir tust,

692
00:56:27,900 --> 00:56:30,600
wir auf unserer Insert-Funktion verlassen, um das zu tun.

693
00:56:30,600 --> 00:56:35,510
Wir werden uns nicht auf unseren Insert-Funktion verlassen, um den gesamten Baum von vorne nur noch bauen,

694
00:56:35,510 --> 00:56:39,970
sondern wir loswerden dieser Zeilen - wir werden aus diesen Zeilen Kommentar -

695
00:56:39,970 --> 00:56:43,430
das bauen die Knoten 5, 8 und 2.

696
00:56:43,430 --> 00:56:55,740
Und anstatt, wir Anrufe bei unserem Einsatz Funktion einfügen

697
00:56:55,740 --> 00:57:01,280
um sicherzustellen, dass das tatsächlich funktioniert.

698
00:57:01,280 --> 00:57:05,840
Here we go.

699
00:57:05,840 --> 00:57:09,300
>> Jetzt haben wir auskommentiert diese Zeilen.

700
00:57:09,300 --> 00:57:13,700
Wir haben nur 7, 3, 9 und 6 in unserem Baum an dieser Stelle.

701
00:57:13,700 --> 00:57:18,870
Um sicherzustellen, dass dies alles funktioniert,

702
00:57:18,870 --> 00:57:25,050
können wir verkleinern, um unsere binären Baum,

703
00:57:25,050 --> 00:57:30,750
führen Sie es, und wir können sehen, dass enthält, wird jetzt sagen uns, dass wir völlig recht -

704
00:57:30,750 --> 00:57:33,110
5, 8, und 2 sind nicht mehr in der Baumstruktur.

705
00:57:33,110 --> 00:57:37,960
Gehen Sie zurück in den Code,

706
00:57:37,960 --> 00:57:41,070
und wie sollen wir setzen?

707
00:57:41,070 --> 00:57:46,290
Erinnere dich, was wir meinen, wenn wir tatsächlich wurden Einfügen 5, 8 und 2 zuvor.

708
00:57:46,290 --> 00:57:50,100
Wir spielten, dass Plinko Spiel, wo wir an der Wurzel gestartet,

709
00:57:50,100 --> 00:57:52,780
ging den Baum einzeln durch ein

710
00:57:52,780 --> 00:57:54,980
bis wir die entsprechende Lücke,

711
00:57:54,980 --> 00:57:57,570
und dann werden wir verkabelt im Knoten an der entsprechenden Stelle.

712
00:57:57,570 --> 00:57:59,480
Wir werden das gleiche tun.

713
00:57:59,480 --> 00:58:04,070
Dies ist im Grunde wie das Schreiben des Codes, die wir verwendet in der Funktion contains

714
00:58:04,070 --> 00:58:05,910
um die Stelle, wo der Knoten sollte finden,

715
00:58:05,910 --> 00:58:10,560
und dann sind wir gerade dabei, den Knoten genau dort einzufügen.

716
00:58:10,560 --> 00:58:17,000
Beginnen wir tun.

717
00:58:17,000 --> 00:58:24,200
>> So haben wir einen Knoten * cur = root; wir gerade dabei, folgen Sie den Code enthält,

718
00:58:24,200 --> 00:58:26,850
bis wir feststellen, dass es nicht ganz für uns arbeiten.

719
00:58:26,850 --> 00:58:32,390
Wir gehen durch den Baum gehen, während das aktuelle Element ist nicht null,

720
00:58:32,390 --> 00:58:45,280
und wenn wir feststellen, dass Aktuell Wert ist gleich dem Wert, den wir versuchen zu legen -

721
00:58:45,280 --> 00:58:49,600
gut, das ist einer der Fälle, in denen wir nicht wirklich konnte legen den Knoten

722
00:58:49,600 --> 00:58:52,730
in den Baum da dies bedeutet, dass wir einen doppelten Wert.

723
00:58:52,730 --> 00:58:59,010
Hier sind wir tatsächlich zu false zurück.

724
00:58:59,010 --> 00:59:08,440
Nun else if Aktuell Wert ist kleiner als der Wert,

725
00:59:08,440 --> 00:59:10,930
Jetzt wissen wir, dass wir nach rechts zu bewegen

726
00:59:10,930 --> 00:59:17,190
 weil der Wert gehört in der rechten Hälfte des laufenden Baum.

727
00:59:17,190 --> 00:59:30,110
Sonst werden wir nach links zu bewegen.

728
00:59:30,110 --> 00:59:37,980
Das ist im Grunde unsere Funktion CONTAINS recht.

729
00:59:37,980 --> 00:59:41,820
>> An diesem Punkt, wenn wir diese while-Schleife abgeschlossen,

730
00:59:41,820 --> 00:59:47,350
unserer Aktuell-Zeiger wird zeigen, um null

731
00:59:47,350 --> 00:59:51,540
wenn die Funktion nicht bereits zurückgegeben.

732
00:59:51,540 --> 00:59:58,710
Wir freuen uns daher mit Aktuell an der Stelle, wo wir den neuen Knoten einfügen möchten.

733
00:59:58,710 --> 01:00:05,210
Was bleibt noch zu tun ist, um tatsächlich bauen die neuen Knoten

734
01:00:05,210 --> 01:00:08,480
die können wir ziemlich leicht tun.

735
01:00:08,480 --> 01:00:14,930
Wir können unsere super-praktisch, Build-Knoten-Funktion,

736
01:00:14,930 --> 01:00:17,210
und etwas, was wir nicht schon früher zu tun -

737
01:00:17,210 --> 01:00:21,400
wir nur irgendwie für selbstverständlich hielt, aber jetzt werden wir tun, nur um sicherzugehen -

738
01:00:21,400 --> 01:00:27,130
wir testen, um sicherzustellen, dass der Wert von neuen Knoten zurückgegeben eigentlich

739
01:00:27,130 --> 01:00:33,410
nicht null ist, weil wir nicht starten wollen Zugriff auf diesen Speicher, wenn es null ist.

740
01:00:33,410 --> 01:00:39,910
Wir können testen, um sicherzustellen, dass neue Knoten nicht gleich null.

741
01:00:39,910 --> 01:00:42,910
Oder statt dessen können wir nur sehen, wenn es tatsächlich null,

742
01:00:42,910 --> 01:00:52,120
und wenn es null ist, dann können wir nur false zurück früh.

743
01:00:52,120 --> 01:00:59,090
>> An dieser Stelle müssen wir neue Knoten in die entsprechende Stelle in dem Baum zu verdrahten.

744
01:00:59,090 --> 01:01:03,510
Wenn wir zurück an Haupt aussehen und wo wir waren eigentlich Verdrahtung Werte vor,

745
01:01:03,510 --> 01:01:08,470
sehen wir, dass die Art und Weise tun wir es waren, wenn wir 3 in den Baum setzen wollte

746
01:01:08,470 --> 01:01:11,750
war, dass wir die linke Kind von root abgerufen.

747
01:01:11,750 --> 01:01:14,920
Wenn wir 9 legte im Baum, mussten wir das rechte Kind des Root-Zugriff.

748
01:01:14,920 --> 01:01:21,030
Wir mussten einen Zeiger auf das übergeordnete haben, um einen neuen Wert in den Baum setzen.

749
01:01:21,030 --> 01:01:24,430
Scrollen wieder einfügen, ist das nicht ganz hier arbeiten

750
01:01:24,430 --> 01:01:27,550
weil wir nicht ein Elternteil Zeiger.

751
01:01:27,550 --> 01:01:31,650
Was wollen wir tun können, ist, an diesem Punkt,

752
01:01:31,650 --> 01:01:37,080
überprüfen Sie die Eltern Wert und sehen - na ja, Gott,

753
01:01:37,080 --> 01:01:41,990
wenn die Eltern Wert kleiner als der aktuelle Wert,

754
01:01:41,990 --> 01:01:54,440
dann die Eltern das Recht Kind sollte der neue Knoten sein;

755
01:01:54,440 --> 01:02:07,280
Ansonsten sollten die Eltern linke Kind der neue Knoten sein.

756
01:02:07,280 --> 01:02:10,290
Aber wir haben nicht dieses übergeordneten Zeiger noch nicht.

757
01:02:10,290 --> 01:02:15,010
>> Um es zu bekommen, sind wir eigentlich gehen zu müssen, um es aufzuspüren, wie wir durch den Baum gehen

758
01:02:15,010 --> 01:02:18,440
und finden Sie die entsprechende Stelle in unserem Schleife oben.

759
01:02:18,440 --> 01:02:26,840
Wir können das durch Scrollen wieder tun, um ganz oben auf unserer Insert-Funktion

760
01:02:26,840 --> 01:02:32,350
und Tracking andere Zeigervariable genannt Elternteil.

761
01:02:32,350 --> 01:02:39,340
Wir werden es gleich auf zunächst null,

762
01:02:39,340 --> 01:02:43,640
und dann jedes Mal, wenn wir durch den Baum,

763
01:02:43,640 --> 01:02:51,540
wir gehen, um den übergeordneten Zeiger auf den aktuellen Zeiger entsprechen.

764
01:02:51,540 --> 01:02:59,140
Stellen Eltern gleich Aktuell.

765
01:02:59,140 --> 01:03:02,260
Auf diese Weise wird jedes Mal gehen wir durch,

766
01:03:02,260 --> 01:03:05,550
wir gehen, um sicherzustellen, dass der aktuelle Zeiger erhält inkrementiert

767
01:03:05,550 --> 01:03:12,640
die Muttergesellschaft Mauszeiger folgt - nur eine Ebene höher als der aktuelle Zeiger im Baum.

768
01:03:12,640 --> 01:03:17,370
Das sieht alles ziemlich gut.

769
01:03:17,370 --> 01:03:22,380
>> Ich denke, das einzige, was wir wollen, zu justieren müssen, ist dieses Build-Knoten wieder null.

770
01:03:22,380 --> 01:03:25,380
Um get build Knoten tatsächlich erfolgreich null zurück,

771
01:03:25,380 --> 01:03:31,060
wir müssen diesen Code zu ändern,

772
01:03:31,060 --> 01:03:37,270
denn hier haben wir nie getestet, um sicherzustellen, dass malloc einen gültigen Zeiger zurückgegeben.

773
01:03:37,270 --> 01:03:53,390
Also, wenn (n = NULL), dann -

774
01:03:53,390 --> 01:03:55,250
wenn malloc zurückgegeben einen gültigen Zeiger, dann werden wir initialisieren;

775
01:03:55,250 --> 01:04:02,540
sonst werden wir nur zurück, und das wird am Ende wieder null für uns.

776
01:04:02,540 --> 01:04:13,050
Jetzt sieht alles ziemlich gut. Lassen Sie uns sicherstellen, dass diese tatsächlich kompiliert.

777
01:04:13,050 --> 01:04:22,240
Machen binären Baum, und oh, wir haben ein paar Sachen hier los ist.

778
01:04:22,240 --> 01:04:29,230
>> Wir haben eine implizite Deklaration der Funktion bauen Knoten.

779
01:04:29,230 --> 01:04:31,950
Auch mit diesen Compilern, werden wir an der Spitze beginnen.

780
01:04:31,950 --> 01:04:36,380
Was das bedeuten muss, dass ich rufe aufbauen Knoten, bevor ich es tatsächlich deklariert haben.

781
01:04:36,380 --> 01:04:37,730
Gehen wir zurück zu dem Code wirklich schnell.

782
01:04:37,730 --> 01:04:43,510
Blättern Sie nach unten, und sicher genug, mein Einsatz Funktion deklariert

783
01:04:43,510 --> 01:04:47,400
über dem Build-Knoten-Funktion,

784
01:04:47,400 --> 01:04:50,070
aber ich versuche zu verwenden bauen Knoten innerhalb des Einsatzes.

785
01:04:50,070 --> 01:05:06,610
Ich werde in und kopieren gehen - und fügen Sie den Build Knotenfunktion Weg bis hier an der Spitze.

786
01:05:06,610 --> 01:05:11,750
So, hoffentlich das funktionieren wird. Lassen wir dies anderen zu gehen.

787
01:05:11,750 --> 01:05:18,920
Jetzt alles kompiliert. Alles ist gut.

788
01:05:18,920 --> 01:05:21,640
>> Aber an diesem Punkt haben wir nicht eigentlich unser Einsatz aufgerufen.

789
01:05:21,640 --> 01:05:26,510
Wir wissen nur, dass es kompiliert, also lasst uns in zu gehen und ein paar Anrufe in.

790
01:05:26,510 --> 01:05:28,240
Lasst uns, dass in unserer Hauptfunktion.

791
01:05:28,240 --> 01:05:32,390
Hier, kommentierte wir 5, 8 und 2,

792
01:05:32,390 --> 01:05:36,680
und dann haben wir nicht verdrahten hier unten.

793
01:05:36,680 --> 01:05:41,640
Lassen Sie uns einige Anrufe einfügen,

794
01:05:41,640 --> 01:05:46,440
und lassen Sie uns auch die gleiche Art von Sachen, die wir verwendet

795
01:05:46,440 --> 01:05:52,810
wenn wir diese printf Anrufe, um sicherzustellen, dass alles richtig war eingefügt werden.

796
01:05:52,810 --> 01:06:00,550
Ich werde zu kopieren und einzufügen,

797
01:06:00,550 --> 01:06:12,450
und statt enthält werden wir insert tun.

798
01:06:12,450 --> 01:06:30,140
Und anstelle von 6, 10 und 1, werden wir bis 5, 8 und 2 zu verwenden.

799
01:06:30,140 --> 01:06:37,320
Dies sollte hoffentlich legen 5, 8 und 2 in den Baum.

800
01:06:37,320 --> 01:06:44,050
Kompilieren. Alles ist gut. Jetzt werden wir tatsächlich ausgeführt unserem Programm.

801
01:06:44,050 --> 01:06:47,330
>> Alles false zurückgegeben.

802
01:06:47,330 --> 01:06:53,830
Also, 5, 8 und 2 nicht gehen, und es sieht aus wie contains nicht das finden sie auch nicht.

803
01:06:53,830 --> 01:06:58,890
Was ist los? Lassen Sie vergrößern oder verkleinern.

804
01:06:58,890 --> 01:07:02,160
Das erste Problem war, dass Einlage return false schien,

805
01:07:02,160 --> 01:07:08,750
und es sieht aus wie das ist, weil wir in unserer return false Anruf verlassen,

806
01:07:08,750 --> 01:07:14,590
und wir eigentlich nie wieder wahr.

807
01:07:14,590 --> 01:07:17,880
Wir können einstellen, dass bis.

808
01:07:17,880 --> 01:07:25,290
Das zweite Problem ist, jetzt, auch wenn wir tun - speichern Sie diese, beenden Sie diese,

809
01:07:25,290 --> 01:07:34,530
make erneut ausführen, haben es zu kompilieren, führen Sie es dann -

810
01:07:34,530 --> 01:07:37,670
sehen wir, dass etwas anderes ist hier passiert.

811
01:07:37,670 --> 01:07:42,980
Die 5, 8, und 2 wurden noch nie in der Baumstruktur vorhanden.

812
01:07:42,980 --> 01:07:44,350
Also, was geht hier vor?

813
01:07:44,350 --> 01:07:45,700
>> Werfen wir einen Blick auf diese im Code.

814
01:07:45,700 --> 01:07:49,790
Mal sehen, ob wir dies herausfinden können.

815
01:07:49,790 --> 01:07:57,940
Wir beginnen mit der Muttergesellschaft nicht in der null.

816
01:07:57,940 --> 01:07:59,510
Wir setzen den aktuellen Zeiger gleich der Wurzel Zeiger,

817
01:07:59,510 --> 01:08:04,280
und wir werden unseren Weg arbeiten nach unten durch den Baum.

818
01:08:04,280 --> 01:08:08,650
Wenn der aktuelle Knoten nicht null ist, dann wissen wir, dass wir nach unten ein wenig.

819
01:08:08,650 --> 01:08:12,330
Wir setzen unsere Muttergesellschaft Zeiger auf gleich dem aktuellen Zeiger,

820
01:08:12,330 --> 01:08:15,420
überprüft den Wert - wenn die Werte gleich sind wir wieder falsch.

821
01:08:15,420 --> 01:08:17,540
Wenn die Werte kleiner sind wir nach rechts;

822
01:08:17,540 --> 01:08:20,399
sonst, zogen wir nach links.

823
01:08:20,399 --> 01:08:24,220
Dann bauen wir einen Knoten. Ich werde in ein wenig vergrößern.

824
01:08:24,220 --> 01:08:31,410
Und hier werden wir versuchen, verkabeln Sie die Werte in die gleiche sein.

825
01:08:31,410 --> 01:08:37,250
Was ist los? Mal sehen, ob möglicherweise Valgrind kann uns einen Hinweis geben.

826
01:08:37,250 --> 01:08:43,910
>> Ich mag zum Valgrind benutzen, nur weil wirklich schnell Valgrind läuft

827
01:08:43,910 --> 01:08:46,729
und sagt Ihnen, ob es irgendwelche Speicherfehler sind.

828
01:08:46,729 --> 01:08:48,300
Wenn wir laufen Valgrind auf dem Code,

829
01:08:48,300 --> 01:08:55,859
wie Sie sehen können rechten here--Valgrind./binary_tree--and drücken Sie Enter.

830
01:08:55,859 --> 01:09:03,640
Sie sehen, wir hatten keine Speicher-Fehler, so wie es aussieht ist alles okay so weit.

831
01:09:03,640 --> 01:09:07,529
Wir haben einige Speicherlecks, die wir kennen, weil wir nicht

832
01:09:07,529 --> 01:09:08,910
geschieht zu einem unserer Knoten befreien.

833
01:09:08,910 --> 01:09:13,050
Lassen Sie uns versuchen laufenden GDB zu sehen, was eigentlich los ist.

834
01:09:13,050 --> 01:09:20,010
Wir tun gdb. / Binary_tree. Es hochgefahren just fine.

835
01:09:20,010 --> 01:09:23,670
Lassen Sie uns einen Haltepunkt auf Einsatz.

836
01:09:23,670 --> 01:09:28,600
Lasst uns laufen.

837
01:09:28,600 --> 01:09:31,200
Es sieht aus wie wir eigentlich nie aufgerufen Einsatz.

838
01:09:31,200 --> 01:09:39,410
Es sieht aus wie das Problem war nur, dass wenn ich mich verändert hier in main -

839
01:09:39,410 --> 01:09:44,279
alle diese printf Anrufe aus enthält -

840
01:09:44,279 --> 01:09:56,430
Ich habe eigentlich nie diese geändert Einsatz nennen.

841
01:09:56,430 --> 01:10:01,660
Nun wollen wir es versuchen. Wir kompilieren.

842
01:10:01,660 --> 01:10:09,130
Alles sieht gut dort. Lassen Sie uns nun versuchen Sie es, zu sehen, was passiert.

843
01:10:09,130 --> 01:10:13,320
Alright! Alles sieht ziemlich gut da.

844
01:10:13,320 --> 01:10:18,130
>> Das letzte, was zu denken ist, gibt es keine Grenzfälle zu diesem Einsatz?

845
01:10:18,130 --> 01:10:23,170
Und es stellt sich heraus, dass, na ja, die eine Kante Fall, immer interessant zu denken

846
01:10:23,170 --> 01:10:26,250
ist, was passiert, wenn Sie Ihren Baum leer ist und Sie nennen das Insert-Funktion?

847
01:10:26,250 --> 01:10:30,330
Wird es funktionieren? Nun, lassen Sie give it a try.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Die Art und Weise wir dies zu testen sind, so werden wir zu gehen, um unsere Funktion,

850
01:10:35,810 --> 01:10:41,690
und statt verdrahten diese Knoten up wie diese,

851
01:10:41,690 --> 01:10:56,730
wir gerade dabei, kommentieren Sie die ganze Sache,

852
01:10:56,730 --> 01:11:02,620
und statt der Verkabelung der Knoten selbst,

853
01:11:02,620 --> 01:11:09,400
Wir können eigentlich nur voran gehen und löschen Sie alle dafür.

854
01:11:09,400 --> 01:11:17,560
Wir werden alles machen einen Aufruf an einzufügen.

855
01:11:17,560 --> 01:11:49,020
Also, lass es uns tun - statt 5, 8 und 2, werden wir 7 einzufügen, 3 und 9.

856
01:11:49,020 --> 01:11:58,440
Und dann werden wir wollen auch 6 sowie einzufügen.

857
01:11:58,440 --> 01:12:05,190
Speichern. Beenden. Machen binären Baum.

858
01:12:05,190 --> 01:12:08,540
Alles kompiliert.

859
01:12:08,540 --> 01:12:10,320
Wir können nur ausgeführt werden, wie es ist und sehen, was passiert,

860
01:12:10,320 --> 01:12:12,770
aber es ist auch sein wird wirklich wichtig, um sicherzustellen, dass

861
01:12:12,770 --> 01:12:14,740
Wir haben noch keine Speicher-Fehler,

862
01:12:14,740 --> 01:12:16,840
denn dies ist einer unserer Grenzfälle, die wir kennen.

863
01:12:16,840 --> 01:12:20,150
>> Lassen Sie uns dafür sorgen, dass es gut funktioniert unter Valgrind,

864
01:12:20,150 --> 01:12:28,310
die wir nur durch Laufen Valgrind. / binary_tree tun.

865
01:12:28,310 --> 01:12:31,110
Es sieht aus wie wir in der Tat ein Fehler von einem Kontext -

866
01:12:31,110 --> 01:12:33,790
haben wir diese Segmentation Fault.

867
01:12:33,790 --> 01:12:36,690
Was ist passiert?

868
01:12:36,690 --> 01:12:41,650
Valgrind tatsächlich sagt uns, wo es ist.

869
01:12:41,650 --> 01:12:43,050
Verkleinern ein wenig.

870
01:12:43,050 --> 01:12:46,040
Es sieht so aus, wie es in unserem Insert-Funktion passiert,

871
01:12:46,040 --> 01:12:53,420
wo wir einen ungültigen Lese der Größe 4 sind am Einsatz, Zeile 60.

872
01:12:53,420 --> 01:13:03,590
Gehen wir zurück und sehen, was hier vor sich geht.

873
01:13:03,590 --> 01:13:05,350
Verkleinern wirklich schnell.

874
01:13:05,350 --> 01:13:14,230
Ich möchte sicherstellen, dass es nicht an den Rand des Bildschirms gehen, damit wir alles sehen können.

875
01:13:14,230 --> 01:13:18,760
Ziehen Sie, dass in einer wenig. Alright.

876
01:13:18,760 --> 01:13:35,030
Blättern Sie nach unten, und das Problem ist hier richtig.

877
01:13:35,030 --> 01:13:40,120
Was passiert, wenn wir nach unten zu bekommen und unseren aktuellen Knoten bereits null,

878
01:13:40,120 --> 01:13:44,010
unserer übergeordneten Knoten null ist, so dass, wenn wir an der Spitze, hier schauen -

879
01:13:44,010 --> 01:13:47,340
wenn diese while-Schleife nie ausgeführt

880
01:13:47,340 --> 01:13:52,330
weil unsere aktuelle Wert ist null - unsere Wurzel ist null, so Aktuell ist null -

881
01:13:52,330 --> 01:13:57,810
dann ist unsere Muttergesellschaft nie zu cur oder auf einen gültigen Wert gesetzt,

882
01:13:57,810 --> 01:14:00,580
so wird Elternteil auch null sein.

883
01:14:00,580 --> 01:14:03,700
Wir müssen daran denken, für dass der Check

884
01:14:03,700 --> 01:14:08,750
durch die Zeit, die wir hier unten, und wir beginnen den Zugriff auf die Eltern Wert.

885
01:14:08,750 --> 01:14:13,190
Also, was passiert? Nun, wenn der Elternteil ist null -

886
01:14:13,190 --> 01:14:17,990
if (Eltern == NULL) - dann wissen wir, dass

887
01:14:17,990 --> 01:14:19,530
Es muss nicht alles in der Baum.

888
01:14:19,530 --> 01:14:22,030
Wir müssen versuchen, sie an der Wurzel einzufügen.

889
01:14:22,030 --> 01:14:32,570
Wir können als nur durch Einstellen der Wurzel gleich dem neuen Knoten zu tun.

890
01:14:32,570 --> 01:14:40,010
Dann an diesem Punkt haben wir nicht wirklich wollen, durch diese anderen Dinge.

891
01:14:40,010 --> 01:14:44,780
Stattdessen hier, können wir entweder eine else-if-else,

892
01:14:44,780 --> 01:14:47,610
oder wir könnten alles kombinieren hier in einem anderen,

893
01:14:47,610 --> 01:14:56,300
aber hier werden wir nur anderes zu verwenden und tun es auf diese Weise.

894
01:14:56,300 --> 01:14:59,030
Nun, wir gehen, um zu testen, um sicherzustellen, dass unsere Eltern nicht null ist

895
01:14:59,030 --> 01:15:02,160
bevor dann tatsächlich versucht, ihre Felder zugreifen.

896
01:15:02,160 --> 01:15:05,330
Dies wird uns helfen vermeiden Segmentation Fault.

897
01:15:05,330 --> 01:15:14,740
Also, wir beenden, Verkleinern, kompilieren, führen.

898
01:15:14,740 --> 01:15:18,130
>> Keine Fehler, aber wir haben noch eine Reihe von Speicherlecks

899
01:15:18,130 --> 01:15:20,650
weil wir nicht befreien alle unsere Knoten.

900
01:15:20,650 --> 01:15:24,350
Aber wenn wir hier gehen, und wir schauen Sie sich unsere Ausdruck,

901
01:15:24,350 --> 01:15:30,880
sehen wir, dass, na ja, sieht aus wie alle unsere Einsätze wurden wieder wahr, was gut ist.

902
01:15:30,880 --> 01:15:33,050
Die Einsätze sind alle wahr,

903
01:15:33,050 --> 01:15:36,670
und dann die entsprechenden contains Anrufe sind auch wahr.

904
01:15:36,670 --> 01:15:41,510
>> Good job! Es sieht aus wie wir erfolgreich Insert geschrieben habe.

905
01:15:41,510 --> 01:15:47,430
Das ist alles, was wir für diese Woche Problem Set Spezifikation.

906
01:15:47,430 --> 01:15:51,720
Eine lustige Herausforderung zu denken ist, wie würden Sie tatsächlich gehen

907
01:15:51,720 --> 01:15:55,340
und frei alle Knoten in diesem Baum.

908
01:15:55,340 --> 01:15:58,830
Das können wir eine Reihe von verschiedenen Möglichkeiten,

909
01:15:58,830 --> 01:16:01,930
aber ich überlasse, dass bis zu Ihnen, zu experimentieren,

910
01:16:01,930 --> 01:16:06,080
und als lustige Herausforderung, zu versuchen und sicherzustellen, dass Sie sicherstellen können,

911
01:16:06,080 --> 01:16:09,490
dass diese Valgrind Bericht gibt keine Fehler und keine Lecks.

912
01:16:09,490 --> 01:16:12,880
>> Viel Glück auf dieser Woche Huffman-Kodierung Problem Set,

913
01:16:12,880 --> 01:16:14,380
und wir sehen uns nächste Woche!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]