[Powered by Google Translate] [§ 7] [weniger komfortabel]
[Nate Hardison] [Harvard University]
[Dies ist CS50.] [CS50.TV]
>> Willkommen in Abschnitt 7.
Dank Hurrikan Sandy,
Statt mit einem normalen Abschnitt dieser Woche,
wir tun dies walk-through, durch den Abschnitt von Fragen.
Ich werde zu folgen zusammen mit dem Problem Set 6-Spezifikation,
und gehen durch alle Fragen in der
Ein Abschnitt der Fragen Abschnitt.
Wenn es irgendwelche Fragen,
bitte posten diese auf CS50 diskutieren.
>> Alright. Lasst uns loslegen.
Im Moment bin ich auf Seite 3 des Problem Set Spezifikation suchen.
Wir werden zum ersten Mal starten reden binären Bäumen
da diese eine Menge von Bedeutung in dieser Woche das Problem set -
die Huffman-Baum-Codierung.
Einer der ersten Datenstrukturen über die wir gesprochen am CS50 war die Array.
Beachten Sie, dass ein Array aus einer Folge von Elementen -
alle vom gleichen Typ - in unmittelbarer Nähe zueinander in Speicher gespeichert.
Wenn ich ein Integer-Array, dass ich zeichnen kann mit dieser Boxen-Nummern-Zahlen-Stil -
Lassen Sie uns sagen, ich habe 5 in der ersten Box, ich habe 7 in der zweiten,
dann habe ich 8, 10 und 20 in der letzten Box.
Denken Sie daran, die beiden wirklich gute Dinge über dieses Array
sind, dass wir diese Konstante-time Zugang zu einem bestimmten Element haben
im Array, wenn wir wissen, seinen Index.
Zum Beispiel, wenn ich das dritte Element im Array greifen wollen -
bei Index 2 mit unserer Null-basierte Indizierung System -
Ich habe buchstäblich nur noch eine einfache mathematische Berechnung zu tun,
hop in diese Position in der Anordnung,
Ziehen Sie die 8, die dort gespeichert sind,
und ich bin gut zu gehen.
>> Einer der schlechte Dinge über dieses Array -, dass wir darüber gesprochen,
wenn wir diskutiert verkettete Listen -
ist, dass, wenn ich ein Element in diesem Array einfügen möchten,
Ich werde zu müssen, einige Verschiebung um zu tun.
Zum Beispiel kann diese Anordnung direkt hier
ist in sortierter Reihenfolge - in aufsteigender Reihenfolge sortiert -
5, dann 7, dann 8, dann 10, dann 20 -
aber wenn ich die Nummer 9 in diesem Array einzufügen,
Ich bin zu haben, um einige der Elemente zu verschieben, um Platz zu schaffen.
Wir ziehen kann dies hier.
Ich bin zu haben, um die 5, die 7 zu bewegen, und dann die 8;
eine Lücke, wo ich die 9 setzen können,
und dann der 10 und der 20 auf der rechten Seite der 9 gehen.
Dies ist eine Art von Schmerz, weil im schlimmsten Fall -
wenn wir mit Einsetzen entweder am Anfang oder am Ende
des Arrays, je nachdem, wie wir verschieben -
könnten wir am Ende mit all den Elementen verschieben
dass wir derzeit die Speicherung im Array.
>> Also, was war der Weg, um dieses?
Der Weg um dies zu unserem linked-list-Methode, wohin sie gehen -
Statt des Speicherns der Elemente 5, 7, 8, 10 und 20 alle nebeneinander im Speicher -
Was wir stattdessen tat, war lagern Art von wo wir wollten um sie zu speichern
in diesen verlinkten Liste Knoten denen zeichne ich hier, eine Art ad hoc.
Und dann haben wir sie miteinander verbunden sind mit diesen nächsten Zeiger.
Ich kann einen Zeiger von 5 zu der 7,
ein Zeiger von der 7 auf die 8,
ein Zeiger von der 8 bis zur 10,
und schließlich ein Zeiger aus der 10 zu der 20,
und dann ein Null-Zeiger auf der 20 darauf hinweist, dass es nichts mehr übrig.
Die Trade-off, die wir hier haben,
ist, dass jetzt, wenn wir die Zahl 9 in unsere sortierte Liste einfügen möchten,
alles, was wir tun müssen, ist einen neuen Knoten mit 9,
verdrahten, um an die entsprechende Stelle darauf hinweisen,
und dann neu verkabeln 8 bis unten, um die 9.
Das ist ziemlich schnell, vorausgesetzt, wir wissen genau, wo wir die 9 einfügen möchten.
Aber der Trade-off im Austausch dafür ist, dass wir jetzt die Konstante-Zugang verloren
auf ein bestimmtes Element in unserer Datenstruktur.
Zum Beispiel, wenn ich will, um das vierte Element in dieser verketteten Liste zu finden,
Ich werde zu müssen, ganz am Anfang der Liste zu starten
und meinen Weg durch das Zählen node-by-Knoten, bis ich die vierte zu finden.
>> Um einen besseren Zugang Leistung als einer verketteten Liste -
sondern behalten auch einige der Vorteile, die wir hatten
in Bezug auf die Insertion-Zeit von einer verketteten Liste -
ein binärer Baum ist gehen zu müssen, ein wenig mehr Speicher zu verwenden.
Insbesondere, statt nur mit einem Zeiger in einem binären Baum Knoten -
wie der linked-list node tut -
werden wir eine zweite Zeiger auf die binären Baum Knoten hinzuzufügen.
Anstatt nur mit einem Zeiger auf das nächste Element,
werden wir einen Zeiger auf eine linke Kind und einem rechten Kind zu haben.
>> Lassen Sie uns ein Bild zeichnen, um zu sehen, was das tatsächlich aussieht.
Wieder werde ich diese Boxen und Pfeile verwenden.
Ein Binärbaum Knoten startet mit nur einem einfachen Box.
Es wird eine Fläche für den Wert haben,
und dann ist es auch gehen, um einen Raum für die linke und die rechte Kind Kind.
Ich werde sie hier zu beschriften.
Wir werden das linke Kind haben, und dann werden wir das rechte Kind haben.
Es gibt viele verschiedene Möglichkeiten zur Verfügung.
Manchmal für Raum und Komfort,
Ich werde tatsächlich ziehen Sie es wie ich hier mache auf der Unterseite
wohin ich gehe, um den Wert an der Spitze haben,
und dann die rechte Kind auf der unteren rechten,
und das linke Kind auf der unteren linken.
Gehen wir zurück zu diesem Top-Diagramm
haben wir den Wert an der Spitze,
dann haben wir die linke Kind-Zeiger, und dann haben wir das Recht, Kind-Zeiger.
>> Im Problem Set Spezifikation,
wir reden über das Zeichnen eines Knotens, der einen Wert 7 hat,
und dann ein linkes Kind-Zeiger, der null ist, und ein rechtes Kind-Zeiger, der den Wert null.
Wir können entweder schreiben Hauptstadt NULL in den Raum für
sowohl die linke als Kind und das rechte Kind, oder wir ziehen können dieses Schrägstrich
durch jedes der Felder, um anzuzeigen, dass es null ist.
Ich werde tun, dass, nur weil das einfacher ist.
Was Sie hier sehen, sind zwei Möglichkeiten zur Diagrammerstellung einen sehr einfachen binären Baumknoten
wo wir den Wert 7 und null Kind Zeigern.
>> Der zweite Teil unserer Spezifikation spricht darüber, wie mit verknüpften Listen -
Denken Sie daran, wir hatten nur zu halten, um die allererste Element in einer Liste
um die gesamte Liste erinnern -
und ebenfalls mit einem binären Baum, wir haben nur zu halten, um einen Zeiger auf den Baum
Um die Kontrolle über die gesamte Datenstruktur beizubehalten.
Diese besondere Element des Baumes wird als Stammknoten des Baums.
Zum Beispiel, wenn dieses einen Knotens - dieser Knoten mit dem Wert 7
mit null links und rechts-Kind-Zeiger -
waren der einzige Wert im Baum,
dann würde dies unseren Root-Knoten sein.
Es ist der Anfang unserer Baum.
Wir können diese ein wenig klarer zu sehen, wenn wir das Hinzufügen von mehr Knoten zu unserem Baum starten.
Lassen Sie mich nach oben ziehen eine neue Seite.
>> Jetzt werden wir einen Baum, 7 hat an der Wurzel zu ziehen,
und 3 im Inneren des linken Kindes und 9 innerhalb des rechten Kindes.
Auch dies ist ziemlich einfach.
Wir haben 7 haben, ziehen Sie einen Knoten für die 3, ein Knoten für 9,
und ich werde das linke Kind-Zeiger 7, um den Knoten mit Punkt 3 gesetzt,
und das rechte Kind Zeiger des Knotens mit dem Knoten 7 bis 9 enthält.
Nun, seit 3 ​​und 9 haben keine Kinder,
werden wir alle ihr Kind Zeiger auf null sein.
Hier entspricht die Wurzel unserer Baum zu dem Knoten, der die Anzahl 7.
Sie können sehen, dass, wenn alles, was wir haben, ist ein Zeiger auf die Root-Knoten,
können wir dann durch unseren Baum gehen und auf beide Kindknoten -
beide 3 und 9.
Keine Notwendigkeit, Zeiger auf jedem einzelnen Knoten im Baum zu halten.
Alright. Jetzt werden wir einen anderen Knoten zu diesem Diagramm hinzuzufügen.
Wir werden einen Knoten mit 6 hinzuzufügen,
und wir werden dies als die rechte Kind des Knotens mit 3 hinzuzufügen.
Um dies zu tun, werde ich diese Null-Zeiger in der 3-Knoten löschen
und verdrahten bis zum Knoten mit 6 zeigen. Alright.
>> An dieser Stelle wollen wir über ein wenig Terminologie gehen.
Um zu beginnen, den Grund, dass diese aufgerufen wird ein Binärbaum insbesondere
ist, dass es zwei untergeordnete Zeiger hat.
Es gibt noch andere Arten von Bäumen, die mehr Kinder Zeigern.
Insbesondere haben Sie ein 'versuchen' in Problem Set 5.
Sie, dass in diesem Versuch bemerken, musste man 27 verschiedene Verweise auf andere Kinder -
eine für jedes der 26 Buchstaben des englischen Alphabets,
und dann die 27. für den Apostroph -
so, das ist wie eine Art von Baum.
Aber auch hier, denn es ist binär, haben wir nur zwei Kinder Zeigern.
>> Zusätzlich zu diesem Wurzelknoten, dass wir darüber gesprochen,
Wir haben auch um dieser Begriff geworfen 'Kind. "
Was bedeutet es für einen Knoten ein Kind einem anderen Knoten zu sein?
Es bedeutet wörtlich, dass ein Kind-Knoten ein Kind von einem anderen Knoten
wenn dieser andere Knoten hat einem seiner untergeordneten Zeiger auf diesen Knoten zeigen.
Um dies in konkreter,
wenn 3 ist, um durch eines der untergeordneten Zeigern von 7 hingewiesen, dann 3 ist ein Kind von 7.
Wenn wir herausfinden, was die Kinder von 7 sind -
gut sehen wir, dass 7 einen Zeiger auf 3 und einen Zeiger auf 9 hat,
so 9 und 3 sind die Kinder von 7.
Nine hat keine Kinder, weil ihre Kinder Zeiger null sind,
und 3 nur ein Kind hat, 6.
Six hat auch keine Kinder, weil ihre beiden Zeiger null, die wir jetzt ziehen werde sind.
>> Darüber hinaus haben wir auch über die Eltern von einem bestimmten Knoten zu sprechen,
und das ist, wie man es erwarten würde, das Gegenteil von diesem Kind Beschreibung.
Jeder Knoten hat nur ein Elternteil - statt zwei, wie Sie vielleicht mit Menschen erwarten.
Zum Beispiel ist die Muttergesellschaft von 3 7.
Die Muttergesellschaft von 9 ist auch 7, und die Eltern von 6 ist 3. Nicht viel zu tun.
Wir haben auch Bedingungen über Großeltern und Enkel zu sprechen,
und ganz allgemein sprechen wir über die Vorfahren
und Nachkommen von einem bestimmten Knoten.
Der Vorfahre eines Knotens - oder Vorfahren, sondern eines Knotens -
sind alle Knoten, die auf dem Weg von der Wurzel zu dem Knoten liegen.
Zum Beispiel, wenn ich an dem Knoten 6 suchen,
dann die Vorfahren gehen, um beide 3 und 7 liegen.
Die Vorfahren von 9, zum Beispiel, sind - wenn ich am Knoten 9 suchen -
dann die Vorfahren von 9 ist nur 7.
Und Nachkommen sind genau das Gegenteil.
Wenn ich an all die Nachkommen von 7 aussehen soll,
dann habe ich auf allen Knoten unter ihm zu suchen.
Also, ich habe 3, 9 und 6 alle als Nachkommen von 7.
>> Der letzte Begriff, dass wir darüber reden ist diese Vorstellung ein Geschwister.
Geschwister - Art nach zusammen auf diesen Familien Begriffe -
sind Knoten, die auf der gleichen Ebene in der Baumstruktur sind.
So sind 3 und 9 Geschwistern, weil sie auf der gleichen Ebene in der Baumstruktur sind.
Beide haben die gleichen Eltern, 7.
Die 6 hat keine Geschwister, weil 9 der keine Kinder.
Und 7 hat keine Geschwister, weil sie die Wurzel unserer Baum ist,
und es gibt immer nur 1 root.
Für 7 Geschwister haben dort müsste ein Knoten über 7 liegen.
Es müsste ein Elternteil von 7, in welchem ​​Fall 7 nicht mehr die Wurzel des Baumes sein würde.
Dann, dass neue Muttergesellschaft von 7 hätte auch ein Kind haben,
und das Kind wäre dann die Geschwister von 7 sein.
>> Alright. Umzug auf.
Wenn wir unsere Diskussion von binären Bäumen begonnen,
Wir sprachen darüber, wie wir wollten, um sie zu bedienen
sich einen Vorteil gegenüber den beiden Arrays und verkettete Listen.
Und die Art und Weise wir, dass tun, ist mit dieser Bestellung Eigentum.
Wir sagen, dass ein binärer Baum geordnet ist, gemäß der Spezifikation,
wenn für jeden Knoten in unserem Baum, alle seine Nachkommen auf der linken Seite -
das linke Kind und all die linke Kind Nachkommen -
haben geringere Werte, und alle der Knoten auf der rechten Seite -
das rechte Kind und alle das rechte Kind Nachkommen -
haben Knoten größer als der Wert des aktuellen Knotens, dass wir auf der Suche.
Nur der Einfachheit halber werden wir davon ausgehen, dass es keine doppelten Knoten in unserem Baum.
Zum Beispiel, in diesem Baum werden wir nicht mit dem Fall zu befassen
wo wir den Wert 7 an der Wurzel
und dann haben wir auch den Wert 7 an anderer Stelle im Baum.
In diesem Fall, werden Sie feststellen, dass dieser Baum tatsächlich bestellt wird.
Wir haben den Wert 7 an der Wurzel.
Alles links von 7 -
wenn ich rückgängig all diese kleinen Zeichen hier -
alles links von 7 - die 3 und die 6 -
diese Werte sind beide weniger als 7, und alles, was auf der rechten Seite - das ist nur auf 9 -
größer als 7 ist.
>> Dies ist nicht die einzige geordneten Baum mit diesen Werten,
aber wir ziehen ein paar mehr von ihnen.
Es gibt tatsächlich eine ganze Reihe von Möglichkeiten, dass wir dies tun können.
Ich werde eine Abkürzung verwenden, nur um die Dinge einfach halten, wo -
anstatt Herausziehen des ganzen Boxen-und-Pfeile -
Ich werde einfach die Zahlen zu ziehen und fügen Pfeile miteinander verbinden.
Um zu beginnen, wir schreiben einfach unsere ursprüngliche Baum wieder, wo wir 7 hatte, und dann ein 3,
und dann 3 zeigte wieder nach rechts auf die 6,
und 7 hatte ein Recht Kind, 9 war.
Alright. Was ist eine andere Möglichkeit, dass wir diesen Baum zu schreiben?
Anstatt mit 3 das linke Kind 7 sein,
Wir konnten auch die 6 der linke Kind 7 sein,
und dann 3 das linke Kind des 6 sein.
Das wäre wie dieser Baum hier schauen, wo ich 7 bin,
dann 6, dann 3 ist, und ein 9 auf der rechten Seite.
Wir haben auch nicht bis 7 als unseren Root-Knoten haben.
Wir könnten auch 6 als unsere Wurzel.
Was würde das aussehen?
Wenn wir gehen, um dieses bestellt Immobilie zu erhalten,
alles links der 6 muss kleiner sein als dieser.
Es gibt nur eine Möglichkeit, und das ist 3.
Aber dann, als der rechte Kind von 6, haben wir zwei Möglichkeiten.
Erstens könnten wir die 7 und dann die 9,
oder wir ziehen konnte sie - wie ich bin zu tun -
wo wir die 9 haben wie die rechte Kind der 6,
und dann wird das 7 als linke Kind der 9.
>> Nun sind 7 und 6, die nicht die einzig möglichen Werte für die Wurzel.
Wir könnten auch 3 an der Wurzel.
Was passiert, wenn 3 ist an der Wurzel?
Hier werden die Dinge ein wenig interessanter.
Drei hat keine Werte, die kleiner als es ist,
so dass ganze linke Seite des Baumes wird nur noch zu null.
Es ist gar nichts da sein.
Auf der rechten Seite können wir die Dinge in aufsteigender Reihenfolge aufzulisten.
Wir hätten 3, dann 6, dann 7, dann 9.
Oder könnten wir tun, 3, dann 6, dann 9, dann 7.
Oder könnten wir tun, 3, dann 7, dann 6, dann 9.
Oder, 3, 7 - eigentlich nicht, können wir nicht tun, ein 7 nicht mehr.
Das ist unser eins gibt.
Wir können tun, 9, und dann von der 9 können wir 6 zu tun und dann 7.
Oder können wir tun, 3, dann 9, dann 7, dann 6.
>> Eine Sache, die Ihre Aufmerksamkeit hier zu zeichnen
dass diese Bäume sind ein wenig seltsam aussehenden.
Insbesondere dann, wenn wir uns mit den 4 Bäume auf der rechten Seite -
Ich werde umkreisen sie hier -
diese Bäume sehen fast genauso aus wie einer verketteten Liste.
Jeder Knoten hat nur ein Kind,
und so haben wir nicht jede dieser baumartigen Struktur, die wir sehen, zum Beispiel,
in diesem ein einsamer Baum hier in der unteren linken.
Diese Bäume werden tatsächlich aufgerufen entarteten binären Bäumen,
und wir werden über diese mehr in die Zukunft zu reden -
vor allem, wenn du gehst zu anderen Informatik teilzunehmen.
Diese Bäume sind entartet.
Sie sind nicht sehr nützlich, weil, ja, verleiht diese Struktur selbst
zu Zeiten ähnlich einer verketteten Liste Lookup.
Wir bekommen nicht den Vorteil der zusätzlichen Speicher zu nehmen - diese zusätzliche Zeiger -
aufgrund unserer Struktur ist auf diese Weise schlecht.
Anstatt sich auf und ziehen Sie die binären Bäumen, 9 haben an der Wurzel,
das ist der letzte Fall, dass wir hätten,
Wir sind stattdessen an dieser Stelle geht ein wenig über diese andere Sicht sprechen
, die wir verwenden, wenn es um Bäume, die als die Höhe ist.
>> Die Höhe eines Baumes ist der Abstand von der Wurzel bis zur höchstwertigen entfernten Knoten,
oder vielmehr die Anzahl der Hops, dass Sie müssten zu machen, um
Ausgehend von der Wurzel und dann am Ende am meisten entfernten Knoten im Baum.
Wenn wir einen Blick auf einige dieser Bäume, die wir hier gezeichnet,
können wir sehen, dass, wenn wir diesen Baum in der linken oberen Ecke, und wir beginnen an der 3,
dann müssen wir 1 Hop bis zum 6 zu erhalten, eine zweite Hop bis zum 7 zu bekommen machen,
und eine dritte Hop bis an die 9 zu bekommen.
So ist die Höhe des Baumes 3.
Wir können die gleiche Übung für die anderen Bäume mit dieser grün umrandet,
und man sieht, dass die Höhe aller dieser Bäume auch tatsächlich 3.
Das ist ein Teil dessen, was sie degenerieren -
dass ihre Höhe ist nur eine weniger als die Anzahl von Knoten in dem gesamten Baum.
Wenn wir uns an diesem anderen Baum, umgeben mit rot ist, auf der anderen Seite,
sehen wir, dass die meisten entfernten Blattknoten die 6 und die 9 sind -
die Blätter sind die Knoten, die keine Kinder haben.
So, um von dem Wurzelknoten entweder der 6 oder der 9 zu erhalten,
Wir müssen einen Hop machen, um zu der 7 erhalten und dann ein zweites Hop zu dem 9 zu erhalten,
und ebenfalls, um nur eine aus der zweiten Sprungperiode 7 zur 6 erhalten.
So ist die Höhe des Baumes hier nur 2.
Sie können zurück gehen und tun, dass für alle anderen Bäume, die wir zuvor besprochen
beginnend mit dem der 7 und 6,
und Sie werden feststellen, dass die Höhe der all diese Bäume auch gleich 2 ist.
>> Der Grund, über die wir gesprochen haben geordnete binäre Bäume
und warum sie cool ist, weil man durch sie in suchen
eine sehr ähnliche Weise mit der Suche über einen sortierten Array.
Dies ist, wo wir darum, dass eine verbesserte Lookup Zeit sprechen
gegenüber dem einfachen verketteten Liste.
Mit einer verketteten Liste - wenn Sie möchten ein bestimmtes Element zu finden -
Sie sind am besten gehen, um irgendeine Art von linearen Suche zu tun
wo Sie beginnen am Anfang einer Liste und hop one-by-one -
ein Knoten von einem Knoten -
durch die gesamte Liste, bis Sie finden, was Sie suchen.
Während, wenn Sie einen binären Baum, der in diesem schönen Format gespeichert ist haben,
können Sie tatsächlich mehr von einem binären Suche geht
wo man teile und herrsche
und die Suche durch die entsprechende Hälfte des Baumes bei jedem Schritt.
Mal sehen, wie das funktioniert.
>> Wenn wir - wieder zurück zu unserer ursprünglichen Baum -
Wir beginnen bei 7, haben wir 3 auf der linken Seite 9 auf der rechten Seite,
und unterhalb der 3 haben wir die 6.
Wenn wir für die Zahl 6 in diesem Baum suchen möchten, würden wir an der Wurzel beginnen.
Wir würden vergleichen Sie den Wert wir für, sagen wir 6 suchen,
auf den Wert des Knotens, dass wir derzeit auf der Suche an, 7 gespeichert,
feststellen, dass 6 ist in der Tat weniger als 7, so würden wir nach links zu bewegen.
Wenn der Wert von 6 war größer als 7 würden wir stattdessen nach rechts verschoben wurden.
Da wir wissen, dass - bedingt durch die Struktur unserer geordnete binäre Baum -
alle Werte kleiner als 7 gehen, um nach links von 7 gespeichert werden,
es gibt keine Notwendigkeit, um einmal die Mühe, durch die rechte Seite des Baumes.
Sobald wir nach links zu bewegen, und wir sind jetzt an dem Knoten mit 3,
können wir die gleiche Vergleich wieder tun, wo wir die 3 und die 6 vergleichen.
Und wir finden, dass während 6 - der Wert, die wir suchen - größer als 3 ist,
man an der rechten Seite des Knotens, die 3 gehen.
Es gibt keine linken Seite hier, so konnten wir ignoriert, dass haben.
Aber wir wissen nur, dass, weil wir auf den Baum selbst suchen,
und wir können sehen, dass der Baum keine Kinder hat.
>> Es ist auch recht einfach zum Nachschlagen 6 in diesem Baum, wenn wir es tun uns als Menschen,
aber wir folgen diesen Prozess mechanisch wie ein Computer tun würde
um wirklich zu verstehen den Algorithmus.
An diesem Punkt sind wir nun auf der Suche an einem Knoten, der 6 enthält,
und wir sind für den Wert 6 suchen,
ja, ja, haben wir die entsprechenden Knoten gefunden.
Wir fanden den Wert 6 in unserem Baum, und wir können unsere Suche zu beenden.
An diesem Punkt, je nachdem, was los ist,
können wir sagen, ja, wir haben den Wert 6 zu finden, gibt es in unserem Baum.
Oder, wenn wir planen, einen Knoten einzufügen oder etwas tun wollen, können wir das an dieser Stelle tun.
>> Lassen Sie uns ein paar mehr Lookups nur, wie das funktioniert.
Lassen Sie uns an, was passiert, wenn wir versuchen, und schauen Sie den Wert 10 waren zu sehen.
Wenn wir schauen den Wert 10, so würden wir an der Wurzel beginnen.
Wir würden sehen, dass 10 größer als 7 ist, so würden wir nach rechts zu bewegen.
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.
Also noch einmal, wir würden versuchen, nach rechts zu bewegen.
Aber an diesem Punkt, würden wir feststellen, dass wir in einem null Knoten sind.
Da ist nichts. Es gibt nichts, wo die 10 sein sollte.
Dies ist, wo wir Fehler melden können -, dass es in der Tat keine 10 in den Baum.
Und schließlich wollen wir durch den Fall, wo wir versuchen, schauen 1 in dem Baum sind zu gehen.
Dies ist ähnlich dem, was passiert, wenn wir bis 10 zu sehen, außer anstatt nach rechts,
werden wir nach links gehen.
Wir starten an der 7 und sehen, dass ein weniger als 7, so dass wir nach links zu bewegen.
Wir bekommen die 3 und sehen, dass 1 kleiner als 3 ist, so wir wieder versuchen, nach links zu bewegen.
An diesem Punkt haben wir eine Null-Knoten haben, so können wir wieder berichten Scheitern.
>> Wenn Sie möchten mehr über binären Bäumen lernen,
Es gibt eine ganze Reihe von lustigen kleinen Probleme, die man mit ihnen machen kann.
I alleinigen Ausübung der Zeichnung aus diesen Diagrammen ein-by-one
und im Anschluss durch alle der verschiedenen Schritte,
denn dies wird in super-praktisch,
nicht nur, wenn du tust das Huffman-Kodierung Problem set
sondern auch in Zukunft Kurse -
nur zu lernen, wie man ziehen diese Datenstrukturen und denken über die Probleme
mit Stift und Papier oder in diesem Fall, iPad und Stift.
>> An diesem Punkt aber, wir gehen auf dem Weg zu etwas Codierung der Praxis zu tun
und tatsächlich mit diesen binären Bäumen zu spielen und zu sehen.
Ich werde, um wieder zu meinem Computer.
Für diesen Teil des Abschnitts, anstatt CS50 Run oder CS50 Spaces,
Ich werde das Gerät zu benutzen.
>> Nach zusammen mit dem Problem Set Spezifikation
Ich sehe, dass ich soll die Öffnung des Gerätes,
gehen, um meine Dropbox Ordner einen Ordner namens Section 7,
und erstellen Sie dann eine Datei namens binary_tree.c.
Here we go. Ich habe das Gerät bereits geöffnet.
Ich werde nach oben ziehen ein Terminal.
Ich werde an den Dropbox-Ordner gehen, stellen ein Verzeichnis namens Abschnitt 7,
und sehen, es ist völlig leer.
Jetzt werde ich zu eröffnen binary_tree.c.
Alright. Hier gehen wir - leere Datei.
>> Gehen wir zurück zu der Spezifikation.
Die Spezifikation fordert eine neue Typdefinition erstellen
für einen Binärbaum Knoten mit int-Werten -
ebenso wie die Werte, die wir zogen in unserem Diagrammen vor.
Wir gehen zur Nutzung dieser Textvorschlag typedef, dass wir hier getan
Sie sollten von Problem Set 5 zu erkennen -
wenn Sie taten die Hash-Tabelle Art der Eroberung des Speller Programm.
Sie sollten auch erkennen aus der vergangenen Woche Abschnitt
wo wir sprachen über verkettete Listen.
Wir haben dieses typedef eines struct Knoten
und wir haben angesichts dieser struct node diesen Namen struct node vorab
so dass wir dann zu beziehen, da wir wollen, werde mit struct node Zeigern
als Teil unserer struct, aber wir haben dann umkreist diese -
oder vielmehr, eingeschlossen das - in einem typedef
so dass später im Code, können wir diese Struktur als nur einem Knoten anstelle eines struct Knoten verweisen.
>> Das wird sehr ähnlich sein der einfach verknüpfte Liste Definition, dass wir letzte Woche gesehen haben.
Um dies zu tun, lasst uns einfach, indem Sie den Textvorschlag starten.
Wir wissen, dass wir einen ganzzahligen Wert haben müssen,
so dass wir in int Wert legen, und dann statt mit nur einem Zeiger auf das nächste Element -
wie wir es mit einfach-verkettete Listen -
wir gehen nach links und rechts Kind Zeigern.
Das ist ziemlich einfach zu - struct node * linke Kind;
und struct node * rechtes Kind;. Cool.
Das sieht wie ein ziemlich guter Anfang.
Gehen wir zurück zu der Spezifikation.
>> Jetzt brauchen wir eine globale node * Variable für die Wurzel eines Baumes zu erklären.
Wir gehen, um diese globale genauso wie wir erste Zeiger machte in unserem verketteten Liste auch global.
Dies war, so dass in den Funktionen, die wir schreiben
wir haben nicht zu halten, das um diese Wurzel -
wenn wir sehen, dass, wenn Sie tun, um diese Funktionen rekursiv schreiben wollen,
es wäre besser, gar nicht geben sie herum, als ein globales in erster Linie
und stattdessen initialisieren lokal in Ihrem Hauptfunktion.
Aber, werden wir es weltweit zu tun, um zu starten.
Auch geben wir ein paar Plätze, und ich werde einen Knoten * Wurzel zu erklären.
Nur um sicherzugehen, dass ich nicht lassen Sie dieses nicht initialisiert, werde ich es gleich auf null gesetzt.
Jetzt, in der Hauptfunktion - die wir sehr schnell hier schreiben -
int main (int argc, char * argv []) -
und ich werde anfangen erklärte meinem argv Array als const nur so, dass ich weiß,
dass diese Argumente sind Argumente, die ich wahrscheinlich nicht ändern möchten.
Wenn ich sie ändern möchten Ich sollte wahrscheinlich werden die Anfertigung von Kopien von ihnen.
Du wirst sehen, das eine Menge im Code.
Es ist in Ordnung so oder so. Es ist in Ordnung, um sie als verlassen - weglassen const, wenn Sie möchten.
I in der Regel legen Sie sie in nur so, dass ich mich daran erinnern,
dass ich wahrscheinlich nicht wollen, dass diese Argumente ändern.
>> Wie immer werde ich dieses return 0 Zeile am Ende der wichtigsten gehören.
Hier werde ich zu initialisieren mein Root-Knoten.
Wie es jetzt steht, habe ich einen Zeiger, der auf Null gesetzt ist,
so ist es an nichts zeigen.
Um tatsächlich mit dem Bau des Knotens
Ich muss zuerst in den Speicher für sie bereitzustellen.
Ich werde das, indem Speicher auf dem Heap mit malloc tun.
Ich werde root gleich dem Ergebnis von malloc gesetzt,
und ich werde den sizeof-Operator verwenden, um die Größe eines Knotens zu berechnen.
Der Grund, dass ich sizeof Knoten verwenden, im Gegensatz zu, sagen wir,
etwas zu tun, wie diese - malloc (4 + 4 +4) oder malloc 12 -
ist, weil ich meinen Code so kompatibel wie möglich wollen.
Ich möchte in der Lage sein, diese. C-Datei zu nehmen, kompiliert es auf dem Gerät,
und kompilieren Sie es auf meinem 64-Bit-Mac -
oder auf einer völlig anderen Architektur -
und ich möchte das alles, um die gleiche Arbeit.
>> Wenn ich mache Annahmen über die Größe von Variablen -
die Größe eines int oder die Größe eines Zeigers -
dann bin ich auch Annahmen über die Arten von Architekturen
, auf dem mein Code erfolgreich kompilieren, wenn laufen.
Immer sizeof zur manuellen Summieren der struct Bereichen entgegen.
Der andere Grund ist, dass es vielleicht auch padding, dass der Compiler in der Struktur setzt sein.
Auch nur die Summierung der einzelnen Felder ist nicht etwas, dass Sie in der Regel tun wollen,
ja, löschen Sie diese Zeile.
Nun, um wirklich zu initialisieren dieses Root-Knoten,
Ich bin zu haben, um in den Werten für jedes seiner verschiedenen Bereichen stecken.
Zum Beispiel für den Wert Ich weiß, ich will bis 7 zu initialisieren,
und jetzt werde ich um das linke Kind zu sein null
und das rechte Kind auch null sein. Great!
Wir haben diesen Teil des spec getan.
>> Die Spezifikation, die an der Unterseite von Seite 3 bittet mich, noch drei weitere Knoten zu erstellen -
ein mit 3, ein mit 6 und eines mit 9 -
und dann verdrahten so genau wie unsere Baumdiagramm sieht
dass wir redeten zuvor.
Lassen Sie uns das ziemlich schnell hier.
Du wirst sehr schnell sehen, dass ich gehe mit dem Schreiben beginnen eine Reihe von doppelten Code.
Ich werde einen Knoten * schaffen und ich werde nennen es drei.
Ich werde um sie gleich malloc (sizeof (Knoten)).
Ich werde um drei-> value = 3.
Drei -> left_child = NULL; drei -> rechts _child = NULL; als gut.
Das sieht ziemlich ähnlich wie die Initialisierung der Wurzel, und das ist genau das, was
Ich werde zu tun haben, wenn ich die Initialisierung 6 und 9 sowie beginnen.
Das werde ich ganz schnell hier zu tun - eigentlich, ich werde ein wenig copy and paste zu tun,
und stellen Sie sicher, dass ich - in Ordnung.
Nun, ich habe es kopiert und ich kann gehen Sie vor und setzen Sie diese gleich 6 ist.
Sie können sehen, dass dies eine Weile dauert und ist nicht super-effizient.
In nur ein wenig, dann schreiben wir eine Funktion, die das für uns tun wird.
Ich möchte dies mit einem 9 zu ersetzen, ersetzen, die mit einem 6.
>> Jetzt haben wir alle unsere Knoten erstellt und initialisiert.
Wir haben unsere Wurzel gleich 7 oder mit dem Wert 7,
unseren Knoten mit 3, unser Knoten mit 6, und unsere Knoten mit 9.
An diesem Punkt ist alles, was wir zu tun haben, wire alles durcheinander.
Der Grund warum ich initialisiert alle Zeiger auf null ist einfach so, dass ich mir sicher, dass zu machen
Ich habe noch keine initialisierte Zeiger dort durch Zufall.
Und auch da, an diesem Punkt, ich habe nur tatsächlich verbinden die Knoten miteinander -
um diejenigen, die sie tatsächlich sind angeschlossen - ich weiß nicht zu durchlaufen haben und machen
sicher, dass alle Nullen in gibt es an den entsprechenden Stellen.
>> Beginnend an der Wurzel, ich weiß, dass die Wurzel des linken Kind 3 ist.
Ich weiß, dass der Root-rechte Kind 9 ist.
Danach wird das einzige andere Kind, das ich verlassen haben Grund zur Sorge
3 ist das rechte Kind, die 6 ist.
An diesem Punkt, es sieht alles ziemlich gut.
Wir löschen Sie einige dieser Zeilen.
Jetzt sieht alles ziemlich gut.
Gehen wir zurück zu unserer Spezifikation und sehen, was wir als nächstes zu tun haben.
>> An diesem Punkt müssen wir schreiben eine Funktion namens 'enthält'
mit einem Prototyp des 'bool contains (int value)'.
Und diese Funktion contains wird return true
wenn der Baum auf die durch unsere globale root variable
enthält den Wert in die Funktion und andernfalls false übergeben.
Lasst uns weitermachen und tun.
Das wird genau wie der Lookup, dass wir mit der Hand auf dem iPad nur ein bisschen vor getan haben.
Lassen Sie uns zurück vergrößern ein wenig und nach oben.
Wir werden diese Funktion oben rechts unsere Funktion setzen
so dass wir nicht jede Art von Prototyping tun.
So enthält bool (int value).
Dort gehen wir. Es ist unser Textvorschlag Erklärung.
Nur um sicherzugehen, dass dies zu kompilieren,
Ich werde weitermachen und nur setzen Sie ihn gleich false zurück.
Gerade jetzt diese Funktion einfach nicht tun und immer berichten, dass
der Wert, den wir suchen, ist nicht in den Baum.
>> An dieser Stelle ist es wahrscheinlich eine gute Idee -
da haben wir eine ganze Reihe von Code geschrieben, und wir haben nicht einmal versucht testet es noch -
um sicherzustellen, dass alles kompiliert.
Es gibt ein paar Dinge, die wir tun müssen, um sicherzustellen, dass dies auch tatsächlich zu kompilieren.
Zunächst sehen, ob wir verwendet haben alle Funktionen in allen Bibliotheken, die wir noch nicht berücksichtigt.
Die Funktionen, die wir bisher verwendet werden, malloc,
und dann haben wir auch mit dieser Art - dieses standardmäßige Typ namens 'bool' -
die in der Standard-bool Header-Datei enthalten.
Wir wollen auf jeden Standard-bool.h für den bool-Typ gehören,
und wir wollen auch # include standard lib.h für die Standard-Bibliotheken
das sind malloc, und frei, und das alles.
So, Verkleinern, werden wir beenden.
Lassen Sie uns versuchen und sicherstellen, dass diese tatsächlich kompilieren.
Wir sehen, dass es funktioniert, so dass wir auf dem richtigen Weg.
>> Lasst uns eröffnen binary_tree.c wieder.
Es kompiliert. Lasst uns nach unten gehen und sicherstellen, dass wir ein paar Anrufe einsetzen, um unseren contains-Funktion -
nur um sicherzugehen, dass alles schön und gut ist.
Zum Beispiel, wenn wir einige Lookups haben in unserem Baum zuvor
haben wir versucht, um die Werte 6, 10 und 1, und wir wussten, dass 6 in dem Baum war,
10 war nicht in dem Baum, und 1 war nicht in dem Baum nicht.
Lassen Sie uns diese Probe Anrufe als einen Weg, um herauszufinden, ob
unserer contains Funktion aktiviert ist.
Um das zu tun, werde ich die printf Funktion zu nutzen,
und wir gehen zum Ausdrucken das Ergebnis des Aufrufs enthält.
Ich werde in einem String setzen "enthält (% d) =, weil
wir steckerfertig gehen in den Wert, den wir gehen, um zu sehen,
und =% s \ n "und verwenden Sie diese als Format-String.
Wir stehen noch gehen, um zu sehen - buchstäblich drucken auf dem Bildschirm -
was aussieht wie ein Funktionsaufruf.
Dies ist nicht wirklich die Funktion Anruf.
Dies ist nur ein String ausgelegt, wie ein Aufruf der Funktion zu suchen.
>> Nun, wir gehen in den Werten anschließen.
Wir gehen enthält auf 6 versuchen,
und dann, was wir hier tun, ist zu verwenden, dass ternäre Operator.
Mal sehen - enthält 6 - so, jetzt habe ich 6 enthalten und wenn enthält 6 wahr ist,
die Zeichenfolge, werden wir auf die% s-Format Zeichen gesendet
wird die Zeichenfolge "true" sein.
Lassen Sie uns rollen über ein wenig.
Ansonsten wollen wir senden die Zeichenfolge "false", wenn enthält 6 false zurück.
Dies ist ein wenig doof aus, aber ich denke, ich könnte genauso gut veranschaulichen,
was der ternäre Operator aussieht, da haben wir es nicht für eine Weile gesehen.
Das wird ein schöner, praktischer Weg, um herauszufinden, ob unsere contains-Funktion arbeitet sein.
Ich werde zurück blättern nach links,
und ich werde zu kopieren und diese Linie ein paar mal.
Es änderte einige dieser Werte um,
so das wird 1 sein, und dies wird zu 10 betragen.
>> An diesem Punkt haben wir eine nette Funktion CONTAINS.
Wir haben einige Tests, und wir werden sehen, ob das alles funktioniert.
An dieser Stelle haben wir einige mehr Code geschrieben.
Zeit zu beenden heraus und stellen Sie sicher, dass alles noch kompiliert.
Beenden Sie, und jetzt versuchen wir es machen binären Baum wieder.
Nun, es sieht aus wie wir einen Fehler haben,
Und wir haben dies ausdrücklich erklärt die Library-Funktion printf.
Es sieht aus wie wir zu gehen und # include standardio.h müssen.
Und damit sollte alles kompilieren. Wir sind alle gut.
Lassen Sie uns nun versuchen Sie Binärbaum und sehen was passiert.
Hier sind wir. / Binary_tree,
und wir sehen, dass, wie wir erwartet hatten -
weil wir nicht umgesetzt haben, enthält noch
oder besser gesagt, haben wir gerade in return false setzen -
sehen wir, dass es nur wieder falsch für alle von ihnen,
Also das ist, arbeiten alle zum größten Teil recht gut.
>> Gehen wir zurück gehen und tatsächlich umzusetzen enthält an dieser Stelle.
Ich werde nach unten scrollen, zoomen und -
erinnere, war der Algorithmus, dass wir gewöhnt, dass wir an der Wurzel Knoten gestartet
und dann an jedem Knoten, denen wir begegnen, machen wir einen Vergleich,
und auf der Grundlage dieses Vergleichs haben wir entweder nach links Kind oder nach rechts Kindes zu bewegen.
Das wird sehr ähnlich aussehen, um die binäre Suche Code, schrieben wir früher in der Laufzeit.
Als wir beginnen, wissen wir, dass wir halten Sie auf dem aktuellen Knoten möchten
dass wir auf der Suche, und der aktuelle Knoten wird zum Wurzelknoten initialisiert werden.
Und jetzt werden wir weitermachen durch den Baum,
und denken Sie daran, dass unsere Stoppbedingung -
wenn wir tatsächlich geleisteten Arbeitsstunden durch das Beispiel von Hand -
war, als wir eine Null-Knoten auftreten,
nicht, wenn wir an einem null Kind sah,
sondern wenn wir tatsächlich bewegt, um einen Knoten in der Baumstruktur
und festgestellt, dass wir an einem null Knoten sind.
Wir werden durchlaufen, bis Aktuell ist nicht gleich null.
Und was sollen wir jetzt tun?
Wir werden prüfen, ob (Aktuell -> value == Wert),
dann wissen wir, dass wir tatsächlich den Knoten, den wir suchen, gefunden.
Also hier können wir wieder wahr.
Ansonsten wollen wir sehen, ob der Wert kleiner als der Wert ist.
Wenn der aktuelle Knoten den Wert geringer ist als der Wert, den wir suchen,
werden wir nach rechts zu bewegen.
Also, cur = Aktuell -> right_child und ansonsten werden wir nach links zu bewegen.
cur = Aktuell -> left_child;. Ganz einfach.
>> Wahrscheinlich erkennen die Schleife, die sehr ähnlich zu dieser aus sieht
binäre Suche früher im Begriff, außer dann wurden wir mit niedriger, mittlerer und hoher tun.
Hier müssen wir nur noch auf einen aktuellen Wert suchen,
so ist es schön und einfach.
Lassen Sie uns sicherstellen, dass diese Code funktioniert.
Erstens, stellen Sie sicher, dass es kompiliert. Sieht aus wie es funktioniert.
Lassen Sie uns versuchen es läuft.
Und in der Tat, gibt es alles, was wir erwartet haben.
Es findet 6 in den Baum, nicht finden 10, weil 10 ist nicht im Baum,
und nicht über 1 entweder weil 1 ist auch nicht in den Baum.
Cool stuff.
>> Alright. Gehen wir zurück zu unserer Spezifikation und sehen, was als nächstes kommt.
Jetzt will sie noch mehr Knoten zu unserem Baum hinzuzufügen.
Er will 5, 2 und 8 hinzuzufügen, und stellen Sie sicher, dass unser Code enthält
funktioniert immer noch wie erwartet.
Lasst uns das tun.
An dieser Stelle, anstatt sich das lästige Kopieren und Einfügen wieder
schreiben wir eine Funktion, um tatsächlich einen Knoten.
Wenn wir den ganzen Weg zu blättern main, sehen wir, dass wir machen das schon
sehr ähnlichen Code immer und immer wieder jedes Mal, wenn wir wollen, um einen Knoten zu schaffen.
>> Lassen Sie eine Funktion schreiben, die tatsächlich bauen einen Knoten für uns und gibt es zurück.
Ich werde es nennen build_node.
Ich werde einen Knoten mit einem bestimmten Wert zu bauen.
Vergrößern hier.
Das erste, was ich tun werde tatsächlich schaffen Raum für den Knoten auf dem Heap.
Also, Knoten * n = malloc (sizeof (Knoten)); n -> value = Wert;
und dann hier, ich bin gerade dabei, alle Felder zu initialisieren entsprechenden Werte sein.
Und ganz am Ende, wir kehren unsere Knoten.
Alright. Eine Sache zu beachten ist, dass diese Funktion hier
wird um einen Zeiger auf Speicher, der seit Heap zugewiesen hat zurückzukehren.
Was ist schön daran ist, dass dieser Knoten jetzt -
wir müssen es auf dem Heap zu erklären, denn wenn wir es erklärt auf dem Stack
wir nicht in der Lage, sie in dieser Funktion wie dies zu tun.
Dass der Speicher würde out of scope
und wäre ungültig, wenn wir es später zuzugreifen versucht.
Da wir erklären Heap zugewiesenen Speicher,
werden wir haben dafür Sorge zu befreien später nehmen
für unser Programm nicht auslaufen jede Erinnerung.
Wir haben uns auf, dass seit punting für alles andere im Code
nur der Einfachheit halber an der Zeit,
aber wenn Sie jemals eine Funktion schreiben, die wie folgt aussieht
wo hast du - manche nennen es ein malloc oder realloc innen -
Sie wollen sicherstellen, dass Sie irgendeine Art von Kommentar hier aufgestellt, die besagt,
hey, du weißt, gibt einen Heap-zugewiesenen Knoten mit dem übergebenen Wert initialisiert.
Und dann wollen Sie sicherstellen, dass Sie in irgendeiner Art von Notiz, die sagt, setzen
muss der Anrufer befreien die zurückgegebenen Speicher.
Auf diese Weise, wenn jemand überhaupt geht und nutzt diese Funktion,
sie wissen, dass, was sie wieder aus dieser Funktion
an einem gewissen Punkt müssen befreit werden.
>> Vorausgesetzt, dass alles gut und schön ist hier,
wir gehen in unseren Code und ersetzen alle diese Zeilen hier
mit Aufrufen an unser Build-Knoten-Funktion.
Lasst uns das wirklich schnell.
Der eine Teil, dass wir nicht zu ersetzen ist dieser Teil hier unten
an der Unterseite, wo wir eigentlich verdrahten die Knoten miteinander zu verweisen,
denn das können wir nicht in unserer Funktion tun.
Aber lasst uns root = build_node (7); node * drei = build_node (3);
node * sechs = build_node (6); node * neun = build_node (9);.
Und jetzt wollten wir auch Knoten für Add -
node * fünf = build_node (5); node * acht = build_node (8);
und was der andere Knoten? Lasst uns hier zu sehen. Wir wollten auch einen 2 -
node * zwei = build_node (2);.
Alright. An diesem Punkt wissen wir, dass wir haben die 7, die 3, die 9 und die 6
Alle verdrahtet angemessen, aber was ist mit der 5, der 8 und der 2?
Um alles in der richtigen Reihenfolge zu halten,
wir wissen, dass drei der rechten Kind 6 ist.
Also, wenn wir gehen, um die 5 hinzuzufügen,
das 5 gehört auch in der rechten Seite des Baumes, von denen drei die Wurzel ist,
so 5 gehört wie der linke Kind von 6 Jahren.
Wir können dies mit den Worten: sechs zu tun -> left_child = fünf;
und dann die 8 gehört wie das linke Kind von 9, so neun -> left_child = acht;
und dann 2 ist das linke Kind von 3, so können wir das hier tun - dich -> left_child = zwei;.
Wenn Sie nicht ganz folgen hat zusammen mit dem schlage ich vor, Sie ziehen es selbst heraus.
>> Alright. Retten wir dies. Lasst uns gehen und sicherstellen, dass es kompiliert,
und dann können wir in unserem contains Anrufe hinzuzufügen.
Sieht aus wie alles noch kompiliert.
Lasst uns gehen und fügen Sie in einigen enthält Anrufe.
Wieder werde ich ein wenig copy and paste zu tun.
Lassen Sie uns nun für 5, 8 und 2 zu suchen. Alright.
Lassen Sie uns sicherstellen, dass dies alles gut aussieht still. Great! Speichern und beenden.
Nun wollen wir, kompilieren, und nun lasst uns laufen.
Aus den Ergebnissen, es sieht aus wie alles funktioniert einfach schön und gut.
Great! So jetzt haben wir unseren contains geschrieben funktionieren.
Lasst uns weitermachen und anfangen zu arbeiten, wie Sie Knoten in den Baum einfügen
da, wie wir es tun gerade jetzt, sind die Dinge nicht sehr hübsch.
>> Wenn wir zurück auf die Spezifikation,
Es fordert uns auf, eine Funktion namens einzufügen schreiben - wieder und gibt einen bool
für, ob wir tatsächlich fügen Sie den Knoten in den Baum -
und dann der Wert in den Baum einzufügen wie angegeben
das einzige Argument für unsere Insert-Funktion.
Wir werden true zurückgeben, wenn wir in der Tat könnte einzufügen den Knoten enthält den Wert in den Baum,
was bedeutet, dass wir ein, genügend Speicher hatten,
und dann zwei hat, dass der Knoten nicht bereits in dem Baum seit bestehen -
Denken Sie daran, wir sind nicht zu doppelten Werten im Baum haben, nur um die Dinge einfach.
Alright. Sichern, um den Code.
Öffnen Sie es. Zoom ein bisschen, dann nach unten scrollen.
Lasst uns den Insert-Funktion direkt über den enthält.
Wieder, es wird genannt bool insert (int value).
Geben Sie es ein wenig mehr Platz, und dann, als Standard,
Lassen Sie uns in return false ganz am Ende zu setzen.
Jetzt unten am Boden, lassen Sie vor und statt der manuellen Aufbau der Knoten gehen
in main uns und Verkabelung sie bis zu jedem anderen Punkt, wie wir tust,
wir auf unserer Insert-Funktion verlassen, um das zu tun.
Wir werden uns nicht auf unseren Insert-Funktion verlassen, um den gesamten Baum von vorne nur noch bauen,
sondern wir loswerden dieser Zeilen - wir werden aus diesen Zeilen Kommentar -
das bauen die Knoten 5, 8 und 2.
Und anstatt, wir Anrufe bei unserem Einsatz Funktion einfügen
um sicherzustellen, dass das tatsächlich funktioniert.
Here we go.
>> Jetzt haben wir auskommentiert diese Zeilen.
Wir haben nur 7, 3, 9 und 6 in unserem Baum an dieser Stelle.
Um sicherzustellen, dass dies alles funktioniert,
können wir verkleinern, um unsere binären Baum,
führen Sie es, und wir können sehen, dass enthält, wird jetzt sagen uns, dass wir völlig recht -
5, 8, und 2 sind nicht mehr in der Baumstruktur.
Gehen Sie zurück in den Code,
und wie sollen wir setzen?
Erinnere dich, was wir meinen, wenn wir tatsächlich wurden Einfügen 5, 8 und 2 zuvor.
Wir spielten, dass Plinko Spiel, wo wir an der Wurzel gestartet,
ging den Baum einzeln durch ein
bis wir die entsprechende Lücke,
und dann werden wir verkabelt im Knoten an der entsprechenden Stelle.
Wir werden das gleiche tun.
Dies ist im Grunde wie das Schreiben des Codes, die wir verwendet in der Funktion contains
um die Stelle, wo der Knoten sollte finden,
und dann sind wir gerade dabei, den Knoten genau dort einzufügen.
Beginnen wir tun.
>> So haben wir einen Knoten * cur = root; wir gerade dabei, folgen Sie den Code enthält,
bis wir feststellen, dass es nicht ganz für uns arbeiten.
Wir gehen durch den Baum gehen, während das aktuelle Element ist nicht null,
und wenn wir feststellen, dass Aktuell Wert ist gleich dem Wert, den wir versuchen zu legen -
gut, das ist einer der Fälle, in denen wir nicht wirklich konnte legen den Knoten
in den Baum da dies bedeutet, dass wir einen doppelten Wert.
Hier sind wir tatsächlich zu false zurück.
Nun else if Aktuell Wert ist kleiner als der Wert,
Jetzt wissen wir, dass wir nach rechts zu bewegen
weil der Wert gehört in der rechten Hälfte des laufenden Baum.
Sonst werden wir nach links zu bewegen.
Das ist im Grunde unsere Funktion CONTAINS recht.
>> An diesem Punkt, wenn wir diese while-Schleife abgeschlossen,
unserer Aktuell-Zeiger wird zeigen, um null
wenn die Funktion nicht bereits zurückgegeben.
Wir freuen uns daher mit Aktuell an der Stelle, wo wir den neuen Knoten einfügen möchten.
Was bleibt noch zu tun ist, um tatsächlich bauen die neuen Knoten
die können wir ziemlich leicht tun.
Wir können unsere super-praktisch, Build-Knoten-Funktion,
und etwas, was wir nicht schon früher zu tun -
wir nur irgendwie für selbstverständlich hielt, aber jetzt werden wir tun, nur um sicherzugehen -
wir testen, um sicherzustellen, dass der Wert von neuen Knoten zurückgegeben eigentlich
nicht null ist, weil wir nicht starten wollen Zugriff auf diesen Speicher, wenn es null ist.
Wir können testen, um sicherzustellen, dass neue Knoten nicht gleich null.
Oder statt dessen können wir nur sehen, wenn es tatsächlich null,
und wenn es null ist, dann können wir nur false zurück früh.
>> An dieser Stelle müssen wir neue Knoten in die entsprechende Stelle in dem Baum zu verdrahten.
Wenn wir zurück an Haupt aussehen und wo wir waren eigentlich Verdrahtung Werte vor,
sehen wir, dass die Art und Weise tun wir es waren, wenn wir 3 in den Baum setzen wollte
war, dass wir die linke Kind von root abgerufen.
Wenn wir 9 legte im Baum, mussten wir das rechte Kind des Root-Zugriff.
Wir mussten einen Zeiger auf das übergeordnete haben, um einen neuen Wert in den Baum setzen.
Scrollen wieder einfügen, ist das nicht ganz hier arbeiten
weil wir nicht ein Elternteil Zeiger.
Was wollen wir tun können, ist, an diesem Punkt,
überprüfen Sie die Eltern Wert und sehen - na ja, Gott,
wenn die Eltern Wert kleiner als der aktuelle Wert,
dann die Eltern das Recht Kind sollte der neue Knoten sein;
Ansonsten sollten die Eltern linke Kind der neue Knoten sein.
Aber wir haben nicht dieses übergeordneten Zeiger noch nicht.
>> Um es zu bekommen, sind wir eigentlich gehen zu müssen, um es aufzuspüren, wie wir durch den Baum gehen
und finden Sie die entsprechende Stelle in unserem Schleife oben.
Wir können das durch Scrollen wieder tun, um ganz oben auf unserer Insert-Funktion
und Tracking andere Zeigervariable genannt Elternteil.
Wir werden es gleich auf zunächst null,
und dann jedes Mal, wenn wir durch den Baum,
wir gehen, um den übergeordneten Zeiger auf den aktuellen Zeiger entsprechen.
Stellen Eltern gleich Aktuell.
Auf diese Weise wird jedes Mal gehen wir durch,
wir gehen, um sicherzustellen, dass der aktuelle Zeiger erhält inkrementiert
die Muttergesellschaft Mauszeiger folgt - nur eine Ebene höher als der aktuelle Zeiger im Baum.
Das sieht alles ziemlich gut.
>> Ich denke, das einzige, was wir wollen, zu justieren müssen, ist dieses Build-Knoten wieder null.
Um get build Knoten tatsächlich erfolgreich null zurück,
wir müssen diesen Code zu ändern,
denn hier haben wir nie getestet, um sicherzustellen, dass malloc einen gültigen Zeiger zurückgegeben.
Also, wenn (n = NULL), dann -
wenn malloc zurückgegeben einen gültigen Zeiger, dann werden wir initialisieren;
sonst werden wir nur zurück, und das wird am Ende wieder null für uns.
Jetzt sieht alles ziemlich gut. Lassen Sie uns sicherstellen, dass diese tatsächlich kompiliert.
Machen binären Baum, und oh, wir haben ein paar Sachen hier los ist.
>> Wir haben eine implizite Deklaration der Funktion bauen Knoten.
Auch mit diesen Compilern, werden wir an der Spitze beginnen.
Was das bedeuten muss, dass ich rufe aufbauen Knoten, bevor ich es tatsächlich deklariert haben.
Gehen wir zurück zu dem Code wirklich schnell.
Blättern Sie nach unten, und sicher genug, mein Einsatz Funktion deklariert
über dem Build-Knoten-Funktion,
aber ich versuche zu verwenden bauen Knoten innerhalb des Einsatzes.
Ich werde in und kopieren gehen - und fügen Sie den Build Knotenfunktion Weg bis hier an der Spitze.
So, hoffentlich das funktionieren wird. Lassen wir dies anderen zu gehen.
Jetzt alles kompiliert. Alles ist gut.
>> Aber an diesem Punkt haben wir nicht eigentlich unser Einsatz aufgerufen.
Wir wissen nur, dass es kompiliert, also lasst uns in zu gehen und ein paar Anrufe in.
Lasst uns, dass in unserer Hauptfunktion.
Hier, kommentierte wir 5, 8 und 2,
und dann haben wir nicht verdrahten hier unten.
Lassen Sie uns einige Anrufe einfügen,
und lassen Sie uns auch die gleiche Art von Sachen, die wir verwendet
wenn wir diese printf Anrufe, um sicherzustellen, dass alles richtig war eingefügt werden.
Ich werde zu kopieren und einzufügen,
und statt enthält werden wir insert tun.
Und anstelle von 6, 10 und 1, werden wir bis 5, 8 und 2 zu verwenden.
Dies sollte hoffentlich legen 5, 8 und 2 in den Baum.
Kompilieren. Alles ist gut. Jetzt werden wir tatsächlich ausgeführt unserem Programm.
>> Alles false zurückgegeben.
Also, 5, 8 und 2 nicht gehen, und es sieht aus wie contains nicht das finden sie auch nicht.
Was ist los? Lassen Sie vergrößern oder verkleinern.
Das erste Problem war, dass Einlage return false schien,
und es sieht aus wie das ist, weil wir in unserer return false Anruf verlassen,
und wir eigentlich nie wieder wahr.
Wir können einstellen, dass bis.
Das zweite Problem ist, jetzt, auch wenn wir tun - speichern Sie diese, beenden Sie diese,
make erneut ausführen, haben es zu kompilieren, führen Sie es dann -
sehen wir, dass etwas anderes ist hier passiert.
Die 5, 8, und 2 wurden noch nie in der Baumstruktur vorhanden.
Also, was geht hier vor?
>> Werfen wir einen Blick auf diese im Code.
Mal sehen, ob wir dies herausfinden können.
Wir beginnen mit der Muttergesellschaft nicht in der null.
Wir setzen den aktuellen Zeiger gleich der Wurzel Zeiger,
und wir werden unseren Weg arbeiten nach unten durch den Baum.
Wenn der aktuelle Knoten nicht null ist, dann wissen wir, dass wir nach unten ein wenig.
Wir setzen unsere Muttergesellschaft Zeiger auf gleich dem aktuellen Zeiger,
überprüft den Wert - wenn die Werte gleich sind wir wieder falsch.
Wenn die Werte kleiner sind wir nach rechts;
sonst, zogen wir nach links.
Dann bauen wir einen Knoten. Ich werde in ein wenig vergrößern.
Und hier werden wir versuchen, verkabeln Sie die Werte in die gleiche sein.
Was ist los? Mal sehen, ob möglicherweise Valgrind kann uns einen Hinweis geben.
>> Ich mag zum Valgrind benutzen, nur weil wirklich schnell Valgrind läuft
und sagt Ihnen, ob es irgendwelche Speicherfehler sind.
Wenn wir laufen Valgrind auf dem Code,
wie Sie sehen können rechten here--Valgrind./binary_tree--and drücken Sie Enter.
Sie sehen, wir hatten keine Speicher-Fehler, so wie es aussieht ist alles okay so weit.
Wir haben einige Speicherlecks, die wir kennen, weil wir nicht
geschieht zu einem unserer Knoten befreien.
Lassen Sie uns versuchen laufenden GDB zu sehen, was eigentlich los ist.
Wir tun gdb. / Binary_tree. Es hochgefahren just fine.
Lassen Sie uns einen Haltepunkt auf Einsatz.
Lasst uns laufen.
Es sieht aus wie wir eigentlich nie aufgerufen Einsatz.
Es sieht aus wie das Problem war nur, dass wenn ich mich verändert hier in main -
alle diese printf Anrufe aus enthält -
Ich habe eigentlich nie diese geändert Einsatz nennen.
Nun wollen wir es versuchen. Wir kompilieren.
Alles sieht gut dort. Lassen Sie uns nun versuchen Sie es, zu sehen, was passiert.
Alright! Alles sieht ziemlich gut da.
>> Das letzte, was zu denken ist, gibt es keine Grenzfälle zu diesem Einsatz?
Und es stellt sich heraus, dass, na ja, die eine Kante Fall, immer interessant zu denken
ist, was passiert, wenn Sie Ihren Baum leer ist und Sie nennen das Insert-Funktion?
Wird es funktionieren? Nun, lassen Sie give it a try.
- Binary_tree c. -
Die Art und Weise wir dies zu testen sind, so werden wir zu gehen, um unsere Funktion,
und statt verdrahten diese Knoten up wie diese,
wir gerade dabei, kommentieren Sie die ganze Sache,
und statt der Verkabelung der Knoten selbst,
Wir können eigentlich nur voran gehen und löschen Sie alle dafür.
Wir werden alles machen einen Aufruf an einzufügen.
Also, lass es uns tun - statt 5, 8 und 2, werden wir 7 einzufügen, 3 und 9.
Und dann werden wir wollen auch 6 sowie einzufügen.
Speichern. Beenden. Machen binären Baum.
Alles kompiliert.
Wir können nur ausgeführt werden, wie es ist und sehen, was passiert,
aber es ist auch sein wird wirklich wichtig, um sicherzustellen, dass
Wir haben noch keine Speicher-Fehler,
denn dies ist einer unserer Grenzfälle, die wir kennen.
>> Lassen Sie uns dafür sorgen, dass es gut funktioniert unter Valgrind,
die wir nur durch Laufen Valgrind. / binary_tree tun.
Es sieht aus wie wir in der Tat ein Fehler von einem Kontext -
haben wir diese Segmentation Fault.
Was ist passiert?
Valgrind tatsächlich sagt uns, wo es ist.
Verkleinern ein wenig.
Es sieht so aus, wie es in unserem Insert-Funktion passiert,
wo wir einen ungültigen Lese der Größe 4 sind am Einsatz, Zeile 60.
Gehen wir zurück und sehen, was hier vor sich geht.
Verkleinern wirklich schnell.
Ich möchte sicherstellen, dass es nicht an den Rand des Bildschirms gehen, damit wir alles sehen können.
Ziehen Sie, dass in einer wenig. Alright.
Blättern Sie nach unten, und das Problem ist hier richtig.
Was passiert, wenn wir nach unten zu bekommen und unseren aktuellen Knoten bereits null,
unserer übergeordneten Knoten null ist, so dass, wenn wir an der Spitze, hier schauen -
wenn diese while-Schleife nie ausgeführt
weil unsere aktuelle Wert ist null - unsere Wurzel ist null, so Aktuell ist null -
dann ist unsere Muttergesellschaft nie zu cur oder auf einen gültigen Wert gesetzt,
so wird Elternteil auch null sein.
Wir müssen daran denken, für dass der Check
durch die Zeit, die wir hier unten, und wir beginnen den Zugriff auf die Eltern Wert.
Also, was passiert? Nun, wenn der Elternteil ist null -
if (Eltern == NULL) - dann wissen wir, dass
Es muss nicht alles in der Baum.
Wir müssen versuchen, sie an der Wurzel einzufügen.
Wir können als nur durch Einstellen der Wurzel gleich dem neuen Knoten zu tun.
Dann an diesem Punkt haben wir nicht wirklich wollen, durch diese anderen Dinge.
Stattdessen hier, können wir entweder eine else-if-else,
oder wir könnten alles kombinieren hier in einem anderen,
aber hier werden wir nur anderes zu verwenden und tun es auf diese Weise.
Nun, wir gehen, um zu testen, um sicherzustellen, dass unsere Eltern nicht null ist
bevor dann tatsächlich versucht, ihre Felder zugreifen.
Dies wird uns helfen vermeiden Segmentation Fault.
Also, wir beenden, Verkleinern, kompilieren, führen.
>> Keine Fehler, aber wir haben noch eine Reihe von Speicherlecks
weil wir nicht befreien alle unsere Knoten.
Aber wenn wir hier gehen, und wir schauen Sie sich unsere Ausdruck,
sehen wir, dass, na ja, sieht aus wie alle unsere Einsätze wurden wieder wahr, was gut ist.
Die Einsätze sind alle wahr,
und dann die entsprechenden contains Anrufe sind auch wahr.
>> Good job! Es sieht aus wie wir erfolgreich Insert geschrieben habe.
Das ist alles, was wir für diese Woche Problem Set Spezifikation.
Eine lustige Herausforderung zu denken ist, wie würden Sie tatsächlich gehen
und frei alle Knoten in diesem Baum.
Das können wir eine Reihe von verschiedenen Möglichkeiten,
aber ich überlasse, dass bis zu Ihnen, zu experimentieren,
und als lustige Herausforderung, zu versuchen und sicherzustellen, dass Sie sicherstellen können,
dass diese Valgrind Bericht gibt keine Fehler und keine Lecks.
>> Viel Glück auf dieser Woche Huffman-Kodierung Problem Set,
und wir sehen uns nächste Woche!
[CS50.TV]