[Powered by Google Translate] [Abschnitt 7: Mehr Komfort] [Rob Bowden] [Harvard University] [Dies ist CS50] [CS50.TV] Gut. So wie ich in meinem E-Mail, dies wird eine binäre-tree-intensive Abschnitt sein. Aber es gibt nicht so viele Fragen. Also werden wir versuchen, und ziehen Sie jede Frage und in schmerzhaften Einzelheiten detailliert von allen die besten Möglichkeiten, Dinge zu tun zu gehen. So ganz am Anfang, wir gehen durch die Probe Zeichnungen von binären Bäumen und so. So hier "Beachten Sie, dass ein Binärbaum Knoten ähnlich denen von einer verknüpften Liste hat, außer statt einen Zeiger gibt es zwei: eines für das linke "Kind" und eines für das rechte Kind '. " So ein binärer Baum ist wie eine verkettete Liste, mit Ausnahme der struct wird zwei Zeigern. Es gibt trinary Bäume, die Umstellung auf drei Zeigern sind, gibt es N-ary Bäume, die nur noch einen generischen Zeiger Sie müssen dann malloc groß genug sein zu müssen genug Hinweise auf alle möglichen Kinder. So Binärbaum nur zufällig eine konstante Anzahl von zwei haben. Wenn Sie möchten, können Sie geben eine verknüpfte Liste als unäre Baum, aber ich glaube nicht, dass jemand anruft, dass. "Zeichnen Sie ein Kästchen-und-Pfeile Darstellung eines binären Baumknoten mit Nates Lieblings-Nummer, 7, wo jedes Kind Zeiger null ist. " So iPad-Modus. 

Es wird ziemlich einfach sein. Wir stehen noch gehen, um einen Knoten habe, werde ich es als ein Quadrat zu zeichnen. Und ich werde die Werte hier zu ziehen. So wird der Wert hier gehen, und dann hier unten müssen wir die linke Zeiger auf der linken und der rechten Zeiger auf der rechten Seite. Und es ist sehr viel, so Konvention nennen es links und rechts, der Zeiger Namen. Beide gehen zu null sein. Das wird nur null sein, und das wird nur null sein. Okay. So, hier zu sichern. "Mit einer verketteten Liste, wir hatten nur einen Zeiger speichern an den ersten Knoten in der Liste, um den gesamten verketteten Liste, oder die gesamte Liste zu erinnern. Ebenso mit Bäumen, wir haben nur einen Zeiger speichern auf einen einzelnen Knoten, um den ganzen Baum erinnern. Dieser Knoten ist calle das 'root' des Baumes. Bauen Sie auf Ihrem Diagramm aus der Zeit vor oder zeichnen Sie einen neuen so dass Sie ein Kästchen-und-Pfeile Darstellung eines binären Baum haben mit dem der Wert 7, dann 3 in der linken, dann 9 auf der rechten Seite, und dann 6 auf der rechten Seite der 3 ". Lasst uns sehen, ob ich das alles in meinem Kopf denken kann. Also das wird unsere Wurzel bis hier zu sein. Wir werden einige Zeiger irgendwo haben, etwas, das wir root nenne, und es ist zu diesem Kerl zeigt. Jetzt einen neuen Knoten zu machen, was haben wir, 3 auf der linken Seite? So wird ein neuer Knoten mit 3, und es zunächst darauf null. Ich werde gerade auf N. Jetzt wollen wir zu machen, dass auf der linken Seite 7 fort. So ändern wir diesen Zeiger nun auf diesen Kerl zu zeigen. Und wir tun das gleiche. Wir wollen eine 9 hier die zunächst nur sagt null. Wir werden diese Zeiger auf 9 zu ändern, und jetzt wollen wir bis 6 auf der rechten Seite von 3 setzen. So, es wird - einen 6. Und dieser Kerl wird darauf gibt. Okay. Also das ist alles was man bittet uns zu tun. 

Lassen Sie uns nun über einige Begriffe gehen. Wir haben bereits darüber gesprochen, wie die Wurzel des Baumes ist der oberste Knoten in der Baumstruktur. Die eine, die 7. Die Knoten im unteren Bereich des Baumes nennt man die Blätter. Jeder Knoten, der hat einfach null als seine Kinder ist ein Blatt. So ist es möglich, wenn unsere binären Baum ist nur ein einzelner Knoten, dass ein Baum ist ein Blatt, und das ist es. "Die 'height' des Baumes ist die Anzahl der Hops Sie müssen sicherstellen, um von der Spitze zu einem Blatt zu erhalten. " Wir werden in zu erhalten, in einer zweiten, den Unterschied zwischen symmetrischen und unsymmetrischen binären Bäumen, aber für jetzt, die Gesamthöhe des Baumes Ich würde sagen, ist 3, aber wenn man die Anzahl der Hops Sie müssen sicherstellen, um auf 9 zu bekommen, dann ist es wirklich nur eine Höhe von 2. Im Moment ist dies eine unausgewogene binären Baum, aber wir werden über ausgewogene sprach, wenn es relevant sein wird. So, jetzt können wir über Knoten in einem Baum in Begriffen zu sprechen relativ zu den anderen Knoten in dem Baum. So jetzt haben wir Eltern, Kinder, Geschwister, Vorfahren und Nachkommen. Sie sind ziemlich gesunden Menschenverstand, was sie bedeuten. Wenn wir uns fragen - es ist Eltern. Also, was ist die Muttergesellschaft von 3? [Studenten] 7. >> Ja. Die Muttergesellschaft ist nur das sein, was zeigt auf Sie. Und was sind die Kinder von 7? [Studenten] 3 und 9. >> Ja. Beachten Sie, dass "Kinder" bedeutet wörtlich Kinder, so 6 nicht gelten würde, weil es wie ein Enkelkind ist. Aber dann, wenn wir Nachfahren gehen, so was sind die Nachkommen von 7? [Studenten] 3, 6 und 9. >> Ja. Die Nachkommen des Root-Knotens wird alles sein, im Baum, außer vielleicht der Wurzelknoten selbst, wenn Sie nicht wollen, zu bedenken, dass ein Nachkomme. Und schließlich, Vorfahren, so dass es in die entgegengesetzte Richtung. Also, was sind die Vorfahren von 6? [Studenten] 3 und 7. >> Ja. 9 ist nicht inbegriffen. Es ist nur die direkte Linie zurück zur Wurzel wird Ihre Vorfahren. 

"Wir sagen, dass ein binärer Baum ist 'bestellt', wenn für jeden Knoten im Baum, alle seine Nachkommen auf der linken Seite haben kleinere Werte und alle die, die auf der rechten Seite eine größere Werte. Zum Beispiel wird der Baum oben bestellte, aber es ist nicht die einzig mögliche geordnete Anordnung. " Bevor wir dazu kommen, eine geordnete binäre Baum wird auch als binäre Suchbaum bekannt. Hier passieren zu nennen es eine geordnete binäre Baum, aber ich habe nie gehört, dass es als eine geordnete binäre Baum vor, und einem Quiz wir sind viel eher zu binären Suchbaum setzen. Sie sind ein und dasselbe, und es ist wichtig, dass Sie erkennen den Unterschied zwischen binären Baum und binären Suchbaum. Ein binärer Baum ist nur ein Baum, der auf zwei Dinge. Jeder Knoten weist auf zwei Dinge. Es gibt keine Überlegungen über die Werte, die sie verweist. So wie hier, da es ein binärer Suchbaum ist, wir wissen, dass, wenn wir gehen von 7 links dann werden alle Werte, die wir möglicherweise erreichen kann nach links geht von 7 haben sich als weniger als 7 aufweist. Bemerken, dass alle Werte kleiner als 7 3 und 6 sind. Diese sind alle links von 7. Wenn wir auf der rechten Seite 7 gehen, hat alles, was größer als 7, so 9 ist auf der rechten Seite 7, so sind wir gut. Dies ist nicht der Fall für einen Binärbaum, für eine reguläre Binärbaum können wir einfach 3 oben, 7 nach links, 9 auf der linken Seite von 7, es gibt keine Reihenfolge der Werte überhaupt. Jetzt werden wir nicht wirklich tun dies, weil es langweilig und unnötig ist, aber "versuchen, so viele bestellt Bäume zeichnen, wie Sie denken können Verwendung der Ziffern 7, 3, 9 und 6. Wie viele verschiedene Anordnungen gibt es? Wie ist die Höhe jedes eine? " 

Wir machen ein paar, aber die Grundidee ist, dies ist in keiner Weise eine eindeutige Darstellung eines binären Baumes mit diesen Werten. Alles, was wir brauchen, ist eine binäre Baum, 7 enthält, 3, 6 und 9. Ein weiterer möglicher gültigen man die Wurzel 3 sein, gehen Sie nach links und es ist 6, gehen Sie nach links und es ist 7, gehen Sie nach links und es ist 9. Das ist eine absolut gültige binären Suchbaum. Es ist nicht sehr hilfreich, weil es wie eine verkettete Liste ist und alle diese Zeiger sind gerade null. Aber es ist eine gültige Baum. Yeah? [Student] Haben nicht die Werte müssen größer auf der rechten Seite? Oder ist das -? >> Das meinte ich, den anderen Weg zu gehen. Es gibt auch - ja, wir schalten, dass. 9, 7, 6, 3. Guter Fang. Es hat immer noch zu gehorchen, was ein binärer Suchbaum tun soll. Also alles auf der linken Seite muss kleiner sein als jeder gegebenen Knoten. Wir könnten einfach zu bewegen, sagen wir, diese 6 und legen Sie sie hier. Nein, können wir nicht. Warum halte ich tun? Lassen Sie uns - hier ist 6, hier ist 7, 6 Punkte 3. Dies ist immer noch eine gültige binären Suchbaum. Was ist falsch, wenn ich - mal sehen, ob ich kommen kann mit einer Anordnung. Ja, okay. Also, was ist los mit diesem Baum? Ich denke, ich habe schon gegeben Ihnen einen Hinweis, dass es etwas falsch mit ihm. Warum halte ich tun? Okay. Das sieht vernünftig. Wenn wir an jedem Knoten, wie 7, dann auf der linken Seite 7 zu sehen ist ein 3. So haben wir 3 haben, ist das, was auf der rechten Seite von 3 a 6. Und wenn Sie bei 6 zu sehen, ist die Sache auf der rechten Seite 6 a 9. Also, warum ist dies nicht eine gültige Suchbaum? [Studenten] 9 ist noch auf der linken Seite 7. >> Ja. Es muss wahr, dass alle Werte ggf. durch, die nach links von 7 erreichen weniger als 7 sind. Wenn wir gehen links von 7 haben wir um 3 zu erhalten und wir können noch bis 6 zu erhalten, wir können noch bis 9 zu erhalten, aber indem er gegangen weniger als 7, sollten wir nicht in der Lage sein, um eine Zahl, die größer als 7 ist zu bekommen. Das ist also nicht eine gültige binären Suchbaum. 

Mein Bruder hatte tatsächlich ein Interview Frage das war im Grunde ist dies nur Code bis etwas zu validieren ob ein Baum ist ein binärer Suchbaum, und so das erste, was er tat, war nur um zu sehen, wenn die linken und rechten korrekt sind, und dann durchlaufen dort unten. Aber man kann nicht einfach tun, Sie haben den Überblick zu behalten der Tatsache, dass jetzt, dass ich links von 7 weg, alles in diesem Teilbaum muss weniger als 7. Die richtige Algorithmus muss den Überblick zu behalten der Grenzen, dass die Werte möglicherweise fallen kann in. Wir werden nicht durch alle von ihnen gehen. Es ist ein schöner Rekursionsformel, obwohl wir nicht auf diejenigen bekommen, oder wir werden nicht auf diejenigen zu bekommen, definiert, wie viele es tatsächlich sind. So gibt es 14 von ihnen. Die Idee, wie Sie es tun würde rechnerisch ist wie, Sie können eine beliebige einzelne der Root-Knoten sein, und dann, wenn ich wähle 7 bis der Wurzelknoten sein, dann gibt es, sagen wir, ein paar Zahlen, die gehen meiner linken Knoten, und es gibt einige Zahlen, die meinen rechten Knoten sein kann, aber wenn ich n Gesamtzahlen, dann ist die Menge, die nach links gehen kann plus dem Betrag, der nach rechts gehen kann, ist n - 1. Also der verbleibenden Zahlen, müssen sie in der Lage, entweder zu der linken oder der rechten Seite. Es scheint schwierig, dass, wenn ich 3 die erste Stelle setzen dann alles auf der linken Seite gehen muss, aber wenn ich 7 setzen, dann können manche Dinge gehen die die linke und einige Dinge können nach rechts gehen. Und von '3 erste "meinte ich alles kann auf der rechten Seite gehen. Es ist wirklich, man muss nur darüber, wie denken, wie viele Dinge auf die nächste Ebene des Baumes gehen. Und es kommt zu 14 sein, oder Sie können alle von ihnen zu ziehen, und dann bekommen Sie 14. 

Wieder hier, "Bestellt binäre Bäume sind cool, weil wir durch sie suchen können in einer sehr ähnlichen Weise mit der Suche über einen sortierten Array. Um dies zu tun, haben wir an der Wurzel beginnen und uns auf den Weg nach unten den Baum Richtung Blätter, die Überprüfung der einzelnen Knoten Werte mit den Werten, die wir für suchst. Wenn der aktuelle Knoten den Wert geringer ist als der Wert, den wir suchen, Sie gehen neben dem Knoten rechte Kind. Andernfalls fahren Sie den Knoten der linken Kind. An einem gewissen Punkt, werden Sie finden, entweder den Wert, den du suchst, oder du wirst in eine null laufen, die den Wert nicht in dem Baum. " Ich habe den Baum hatten wir vor Neuzeichnen; das wird eine Sekunde dauern. Aber wir wollen schauen, ob 6, 10 und 1 in dem Baum sind. Also, was war es, 7, 9, 3, 6. Okay. Die Zahlen, die Sie nachschlagen möchten, wollen wir schauen 6. Wie funktioniert dieser Algorithmus funktioniert? Nun, wir haben auch einige root Zeiger auf unserem Baum. Und wir würden an die Wurzel gehen und sagen, ist dieser Wert gleich dem Wert, nach dem gesucht? So sind wir für 6 suchen, so ist es nicht gleich. So halten wir gehen, und jetzt sagen wir, okay, so 6 weniger als 7 ist. Heißt das, wir wollen nach links zu gehen, oder wollen wir nach rechts gehen? [Student] Links. >> Ja. Es ist wesentlich einfacher, alles, was Sie zu tun haben, ziehen eine mögliche Knoten des Baumes und dann tun nicht - anstatt zu versuchen, in Ihrem Kopf zu denken, okay, wenn es weniger ist, weiß ich auf der linken Seite gehen oder sich das Recht vor, bei einem Blick auf dieses Bild, ist es sehr klar, dass ich auf der linken Seite gehen wenn dieser Knoten größer ist als der Wert, den ich suche. Also nach links gehen, jetzt habe ich bei 3 bin. Ich möchte - 3 geringer ist als der Wert, den ich benötige, die 6 ist. Also haben wir nach rechts gehen, und jetzt habe ich am Ende bei 6, das ist der Wert, den ich benötige, so dass ich true zurückgeben. Der nächste Wert werde ich zu suchen habe, ist 10. Okay. So 10, jetzt wird - abgeschnitten, dass - würde die Wurzel folgen. Nun wird 10 werde größer sein als 7, so will ich nach rechts zu schauen. Ich werde hierher zu kommen, wird 10 sein wird größer als 9, so bin ich gehen zu wollen, nach rechts zu schauen. Ich komme hierher, aber hier jetzt bin ich an null. Was muss ich tun, wenn ich null schlagen? [Student] Zurück falsch? >> Ja. Ich habe nicht finden 10. 1 wird ein nahezu identischer Fall sein, Ausnahme ist es nur geht, um umgedreht werden, statt suchen auf der rechten Seite, ich werde schauen hinunter auf die linke Seite. 

Jetzt denke ich, wir tatsächlich den Code zu bekommen. Hier ist, wo - eröffnen den CS50 Gerät und navigieren Sie Ihren Weg dorthin Sie können aber auch einfach tun im Raum. Es ist wahrscheinlich ideal, um es in dem Raum zu tun, weil wir in dem Raum arbeiten. "Zuerst werden wir brauchen eine neue Art Definition für einen binären Baum Knoten mit int-Werten. Mit dem Textvorschlag typedef unten Erstellen eines neuen Typdefinition für einen Knoten in einem binären Baum. Wenn Sie nicht weiterkommen. . . "Blah, blah, blah. Okay. So lasst uns den Textvorschlag hier typedef struct Knoten und Knoten. Ja, okay. Also, was sind die Felder wir in unserem Knoten möchten sind? [Student] Int und dann zwei Zeigern? >> Int-Wert, zwei Zeiger? Wie schreibe ich die Zeiger? [Student] Struct. >> Ich sollte zu vergrößern in. Ja, so struct node * links, und struct node * rechts. Und denken Sie daran, die Diskussion vom letzten Mal, dass dies keinen Sinn macht, macht dies keinen Sinn, das macht keinen Sinn. Sie müssen alles, was es um diese rekursive struct definieren. Okay, so dass das, was unser Baum wird wie folgt aussehen. Wenn wir eine trinäre Baums ja, dann einen Knoten könnte wie b1, b2, b3 * struct Knoten betrachten, wobei b ein Zweig ist - eigentlich habe ich mehr hörte es links, mitte, rechts, aber egal. Wir haben nur über binäre kümmern, so rechts, links. "Jetzt erkläre eine globale node * Variable für die Wurzel des Baumes." So werden wir nicht zu tun. Um die Dinge etwas schwieriger und verallgemeinert, wir werden nicht einen globalen Knoten variabel. Stattdessen in main wir erklären alle unsere Knoten Dinge, und das bedeutet, dass unter, wenn wir laufen beginnen unserer Funktion CONTAINS und unsere Insert-Funktion, statt unserer Funktion CONTAINS nur mit diesen globalen Knoten variabel, wir gehen zu müssen, als Argument nehmen den Baum, dass wir es verarbeiten möchten. Mit der globalen Variablen sollte Dinge einfacher zu machen. Wir werden die Dinge schwieriger. Nun nehmen Sie eine Minute oder so genau das zu tun diese Art der Sache, wo innerhalb der wichtigsten Sie diesen Baum erstellen wollen, und das ist alles, was Sie tun möchten. Versuchen Sie und bauen diesen Baum in Ihrem Haupt-Funktion. 

Okay. So müssen Sie nicht einmal gebaut dem Baum haben den ganzen Weg noch. Aber jemand etwas, das ich ziehen konnte zu zeigen, wie man vielleicht beginnen Aufbau einer solchen Baum? [Student] Jemand hämmern, versuchen, aus. [Bowden] Wer bequem mit ihren Baum-Konstruktion? [Student] Sure. Es ist noch nicht fertig. >> Es ist in Ordnung. Wir können nur beendet - oh, können Sie es speichern? Hooray. Also hier haben wir - oh, ich bin leicht abgeschnitten. Bin ich in gezoomt? Zoomen, Scrollen aus. >> Ich habe eine Frage. >> Yeah? [Student] Wenn Sie struct definieren, sind Dinge wie initialisiert etwas? [Bowden] Nein >> Okay. So müsste man zu initialisieren - [Bowden] Nein Wenn Sie definieren oder wenn Sie erklären, eine Struktur, es ist nicht standardmäßig initialisiert, es ist einfach so, wenn Sie einen int deklarieren. Es ist genau das gleiche. Es ist wie jeder seiner Einzelfelder kann eine Garbage-Wert in ihm haben. >> Und ist es möglich zu definieren - oder zu erklären, eine Struktur in einer Weise, dass es funktioniert initialisieren? [Bowden] Ja. Also, Verknüpfung Initialisierungssyntax wird wie folgt aussehen - Es gibt zwei Möglichkeiten, wie wir dies tun können. Ich denke, wir sollten es kompilieren um sicherzustellen, dass Clang machen tut dies auch. Die Reihenfolge der Argumente, die in der Struktur kommt, Sie setzen wie die Reihenfolge der Argumente innerhalb dieser geschweiften Klammern. Also, wenn Sie es bis 9 initialisieren möchten und links werden null und dann rechts null sein, es 9 sein, null, null. Die Alternative ist, und der Editor nicht mag diese Syntax, und es denkt, ich will einen neuen Block, aber die Alternative ist so etwas wie - hier, ich werde es auf einer neuen Zeile setzen. Sie können explizit sagen, vergesse ich die genaue Syntax. So können Sie explizit beim Namen, und sagen: . C oder. Wert = 9,. Links = NULL. Ich vermute, diese Notwendigkeit Komma sein. . Rechts = NULL, so diese Weise können Sie nicht tatsächlich benötigen, um die Reihenfolge der struct wissen, und wenn Sie diese Zeilen lesen, ist es viel deutlicher über das, was der Wert ist initialisiert, um. 

Dies geschieht, um eines der Dinge sein, dass - so ist, zum größten Teil, C + + ist eine Obermenge von C. Sie können C-Code, kopieren Sie ihn in C + +, und es sollte zu kompilieren. Dies ist eines der Dinge, dass C + + nicht unterstützt, so dass die Leute eher nicht, es zu tun. Ich weiß nicht, ob das ist der einzige Grund, warum Menschen dazu neigen, es nicht zu tun, aber der Fall, wo ich gebraucht, es zu benutzen benötigt, um mit C + + und so konnte ich nicht daran arbeiten. Ein weiteres Beispiel für etwas, das nicht mit C + + ist die Arbeit wie malloc liefert einen "void *", technisch, aber man konnte nur sagen, char * x = malloc was auch immer, und es wird automatisch zu einem char * gegossen werden. Das automatische Besetzung nicht geschieht in C + +. Das wäre nicht zu kompilieren, und Sie würden ausdrücklich sagen müssen, char *, malloc, was auch immer, es zu einem char * gegossen. Es gibt nicht viele Dinge, die C-und C + + auf nicht einverstanden sind, aber das sind zwei. Also werden wir mit dieser Syntax gehen. Aber selbst wenn wir nicht mit dieser Syntax gehen, was ist - könnte daran falsch? [Student] Ich brauche nicht zu dereferenzieren es? >> Ja. Beachten Sie, dass der Pfeil eine implizite Dereferenzierung hat, und so, wenn wir nur den Umgang mit einer Struktur, wollen wir nutzen. zu einem Feld innerhalb der Struktur zu erhalten. Und das einzige Mal, dass wir mit der Pfeil ist, wenn wir wollen - gut, ist Pfeils entspricht - das ist, was es bedeutete, wenn ich arrow verwendet haben. All arrow Mittel, Dereferenzierung dieses, jetzt bin ich an einem struct, und ich kann das Feld zu bekommen. Entweder bekommen Sie das Feld direkt oder dereferenzieren und erhalten das Feld - Ich denke, dies sollte Wert sein. Aber hier bin ich mit nur einem struct, nicht ein Zeiger auf eine struct zu tun haben, und so kann ich nicht verwenden, den Pfeil. Aber diese Art der Sache können wir für alle Knoten zu tun. Oh mein Gott. Dies ist 6, 7 und 3. Dann können wir Einrichten der Niederlassungen in unserem Baum, können wir 7 - wir haben, sollte seine linke Punkt 3. Also, wie machen wir das? [Studenten, unverständlich] >> Ja. Die Adresse des node3, und wenn Sie nicht über Adresse, dann es wäre einfach nicht kompilieren. Aber denken Sie daran, dass diese Zeiger auf den nächsten Knoten. Dieses Recht sollte bis 9 zeigen, und 3 sollte auf der rechten Seite bis 6 zeigen. Ich denke, das wird ganz eingestellt. Irgendwelche Fragen oder Anmerkungen? [Student, unverständlich] Die Wurzel wird 7 sein. Wir können nur sagen, node * ptr = oder Wurzel = & node7. 

Für unsere Zwecke werden wir mit Einsatz zu tun, so dass wir gehen zu wollen, um eine Funktion in dieser binären Baum einzufügen schreiben und Einsatz wird unweigerlich malloc anrufen, um einen neuen Knoten für diesen Baum zu schaffen. So die Dinge laufen, um sich mit der Tatsache, chaotisch, dass einige Knoten sind derzeit auf dem Stapel und andere Knoten gehen, um am Ende auf dem Heap, wenn wir sie einsetzen. Dies ist durchaus möglich, aber der einzige Grund, Wir sind in der Lage, dies auf dem Stack zu tun ist, weil es wie ein konstruiertes Beispiel, dass wir wissen, ist der Baum soll als 7, 3, 6, 9 ausgebildet sein. Wenn wir nicht diese, dann würden wir nicht malloc haben den ersten Platz. Als wir ein wenig später sehen werden, sollten wir malloc'ing. Im Moment ist es durchaus sinnvoll, auf den Stapel gelegt, aber wir dies ändern, um eine malloc-Implementierung. So hat jeder von ihnen wird jetzt so etwas wie node * node9 = malloc (sizeof (Knoten)). Und jetzt sind wir zu haben, um unsere Prüfung zu tun. if (node9 == NULL) - Ich wollte nicht, dass - 1 zurück, und dann können wir node9-> zu tun, weil es jetzt ein Zeiger ist, Wert = 6, node9-> links = NULL, node9-> rechts = NULL, und wir gehen zu müssen, dass für jeden dieser Knoten zu tun. Anstatt also, sagen wir es innerhalb von einer separaten Funktion. Nennen wir es node * build_node, und dies ist ähnlich dem APIs wir für Huffman-Kodierung. Wir geben Ihnen initializer Funktionen für einen Baum und Deconstructor "Funktionen" für die Bäume und die gleichen für die Wälder. 

Also hier werden wir eine Initialisierung Funktion haben nur bauen einen Knoten für uns. Und es wird so ziemlich genauso aussehen wie diese. Und ich ging sogar faul zu sein und nicht die Namen der Variablen, obwohl node9 macht keinen Sinn mehr. Oh, ich denke, node9 der Wert sollte nicht 6 haben. Jetzt können wir wieder node9. Und hier sollten wir null zurück. Jeder einig Build-a-Knoten-Funktion? So, jetzt können wir nur nennen, um jeden Knoten mit einem bestimmten Wert und Null-Pointer zu bauen. Jetzt können wir so nennen, können wir tun, node * node9 = build_node (9). Und lassen Sie uns tun. . . 6, 3, 7, 6, 3, 7. Und nun wollen wir die Einrichtung der gleichen Zeiger, außer jetzt alles ist schon im Hinblick auf die Zeiger so müssen nicht mehr die Adresse. Okay. Also, was ist das letzte, was ich tun will? Es gibt einen Fehler-checking, dass ich nicht tun. Was bedeutet bauen Knoten zurück? [Student, unverständlich] >> Ja. Wenn malloc nicht, wird es null zurück. So werde ich faul put it down hier anstatt eine Bedingung für jede. Wenn (node9 == NULL, oder - noch einfacher, dies entspricht gerade wenn nicht node9. Also, wenn nicht node9 oder nicht node6 oder nicht node3 oder nicht node7, 1 zurück. Vielleicht sollten wir drucken malloc fehlgeschlagen, oder so etwas. [Student] Ist falsche gleich wie auch null? [Bowden] Jeder Wert Null ist falsch. So null ist ein Nullwert. Zero ist ein Nullwert. Falsch ist ein Nullwert. Any - so ziemlich die einzigen 2 Null-Werte sind null und null, falsch ist nur Hash definiert als Null. Das gilt auch, wenn wir die globale Variable deklarieren müssen. Wenn wir hatten node * root hier oben, dann - die nette Sache über globale Variablen ist, dass sie immer einen Ausgangswert. Das ist nicht von Funktionen wahr, wie im Inneren von hier, wenn wir, wie der Knoten * oder Knoten x. Wir haben keine Ahnung, was x.Value, x.whatever, oder wir könnten ausdrucken und sie konnten beliebig sein. Das ist nicht wahr von globalen Variablen. So Knoten root oder Knoten x. Standardmäßig alles, was global ist, wenn nicht ausdrücklich auf einen Wert initialisiert, einen Nullwert als Wert. Also hier, Knoten * root, wissen wir nicht explizit initialisieren es nichts, so ihren Standardwert ist null, das ist die Null-Wert von Zeigern. Der Standardwert von x wird bedeuten, dass x.Value Null ist, x.left ist null und x.right null ist. Zumal es sich um eine Struktur ist, wird alle Felder der Struktur Null-Werte sein. Wir brauchen nicht zu, dass hier verwenden, though. [Student] Die Strukturen unterscheiden sich von anderen Variablen, und die anderen Variablen sind Müll-Werte, das sind Nullen? [Bowden] Andere Werte zu. So in x wird x gleich Null sein. Wenn es im globalen Bereich ist, hat es einen Anfangswert. >> Okay. [Bowden] Entweder der Ausgangswert du hast es oder Null. Ich denke, das kümmert sich all dies. 

Okay. Also das nächste Teil der Frage stellt, "Jetzt wollen wir eine Funktion namens enthält schreiben mit einem Prototyp bool enthält int-Wert. " Wir werden nicht zu tun bool enthält int-Wert. Unser Prototyp wird aussehen bool enthält (int-Wert. Und dann werden wir auch passieren sie den Baum daß sie sollten prüfen, ob es diesen Wert hat. So Knoten *-Baum). Okay. Und dann können wir es mit so etwas wie nennen, Vielleicht werden wir zu printf oder etwas wollen. Enthält 6, unsere Wurzel. Das sollte wieder ein, oder wahr, wohingegen enthält 5 root sollte false zurück. So nehmen Sie einen zweiten, um diese umzusetzen. Sie können es entweder iterativ oder rekursiv tun. Die nette Sache über die Art, wie wir die Dinge eingerichtet haben ist, dass bietet es sich an unseren rekursive Lösung viel einfacher als die globalen Variablen so tat. Denn wenn wir nur noch enthält int-Wert, dann haben wir keine Möglichkeit, rekursiv nach unten Teilbäume. Wir müssten einen separaten Hilfsfunktion, die sich rekursiv die Teilbäume für uns haben. Aber da haben wir geändert hat, um den Baum als Argument nehmen, die sollte es immer in erster Linie gewesen, jetzt können wir recurse leichter. So iterative oder rekursive, werden wir über beide gehen, aber wir, die rekursive endet als ganz einfach sehen. Okay. Hat jemand etwas mit dem wir arbeiten können? 

[Student] Ich habe eine iterative Lösung. >> Alles klar, iterativ. Okay, das sieht gut aus. Also, wollen uns durch sie gehen? [Student] Sure. Also machte ich mich eine temporäre Variable, um den ersten Knoten des Baumes. Und dann habe ich einfach durchgeschleift, während Temperatur nicht gleich null, also, während noch in den Baum, schätze ich. Und wenn der Wert gleich dem Wert, Temp zeigt auf, dann ist dieser Wert zurückgegeben. Andernfalls wird geprüft, ob es auf der rechten Seite oder der linken Seite ist. Wenn Sie jemals eine Situation, wo es nicht mehr Baum, dann kehrt - es verlässt die Schleife und false zurückgegeben. [Bowden] Okay. Also das scheint gut. Wer noch keine Kommentare zu irgendetwas? Ich habe keine Richtigkeit Kommentare überhaupt. Das Einzige, was wir tun können, ist dieser Kerl. Oh, es geht um eine kleine längliche gehen. Ich mache diese auf. Okay. 

Jeder sollte daran erinnern, wie ternären funktioniert. Es haben definitiv in der Vergangenheit Quiz das Ihnen eine Funktion mit einem ternären Operator, und sagen, übersetzen diese, tun Sie etwas, das nicht verwendet ternären. Also das ist eine sehr häufige Fall, wenn ich denken würde, ternäre verwenden, wo, wenn eine bestimmte Bedingung eine Variable auf etwas, anderes festgelegt dieselbe Variable auf etwas anderes. Das ist etwas, das sehr häufig in diese Art der Sache umgewandelt werden wo gesetzt diese Variable dazu - oder, na ja, ist das wahr? Dann ist dieses, sonst dies. [Student] Die erste ist, wenn wahr, nicht wahr? [Bowden] Yeah. So wie ich das lese immer es ist, gleich Temp Wert größer als Temp-Wert, dann, sonst diese. Es ist eine Frage stellen. Ist es größer? Dann tun Sie das erste, was. Anderes tun die zweite Sache. Ich bin fast immer - der Doppelpunkt, ich - in meinem Kopf, ich lese, wie andere. 

Hat jemand eine rekursive Lösung? Okay. Dieser wir gehst - es könnte schon groß sein, aber wir werden es noch besser machen. Das ist so ziemlich genau die gleiche Idee. Es ist nur gut, wollen Sie das erklären? [Student] Sure. Also werden wir darauf achten, dass der Baum nicht in erster null, denn wenn der Baum ist null dann wird es zur Rückkehr falsch, weil wir es nicht gefunden. Und wenn es noch ein Baum, wir in gehen - wir zunächst prüfen, ob der Wert ist der aktuelle Knoten. Return true, wenn es ist, und wenn wir nicht recurse auf der linken oder rechten Seite. Klingt das sinnvoll? >> Mm-hmm. (Vereinbarung) So bemerken, dass dieses fast - strukturell sehr ähnlich zu der iterativen Lösung. Es ist nur, dass anstelle der rekursiv wir eine while-Schleife hatte. Und die Base-Case hier, wo Baum nicht gleich null war die Bedingung, unter denen wir brach der while-Schleife. Sie sind sehr ähnlich. Aber wir werden noch einen Schritt weiter zu gehen. Jetzt machen wir dasselbe hier. Beachten wir wieder die gleiche Sache in diesen beiden Linien, ausgenommen ein Argument ist anders. So werden wir, dass in einem ternären machen. Ich traf Option etwas, und es machte ein Symbol. Okay. So werden wir zurückkehren enthält,. Dies ist immer auf mehrere Zeilen sein, gut, vergrößert es. Normalerweise als stilistische Sache, ich glaube nicht, viele Menschen ein Leerzeichen nach dem Pfeil, aber ich denke, wenn Sie im Einklang sind, ist es in Ordnung. Wenn der Wert weniger als Baum-Wert wollen wir recurse auf Baum links, Wir wollen also recurse auf Baum rechts. Das war also Schritt eins machen diesen Look kleiner. Schritt zwei machen diesen Look kleiner - Wir können diese auf mehrere Leitungen zu trennen. Okay. Schritt zwei ist damit kleiner aussehen ist hier, so Rückgabewert gleich Baum Wert, oder enthält whatever. 

Dies ist eine wichtige Sache. Ich bin mir nicht sicher, ob er sagte es explizit in der Klasse, aber es heißt Kurzschluss Auswertung. Die Idee hier ist value == Baum Wert. Wenn das wahr ist, dann ist dies wahr, und wir wollen "oder" dass mit dem, was ist hier. So ohne überhaupt darüber nachzudenken, was ist hier drüben, was ist der gesamte Ausdruck geht zurück? [Student] True? >> Ja, weil gilt für alles, verküpft - oder wahre verküpft mit etwas unbedingt wahr. So sobald wir Rückgabewert = Baum Wert sehen, wir gerade dabei, true zurückgeben. Nicht einmal zu recurse enthält ferner auf der ganzen Linie. Wir können noch einen Schritt weiter zu gehen. Zurück Baum nicht gleich null und das alles. Das machte es eine einzeilige Funktion. Dies ist auch ein Beispiel für Kurzschluss Auswertung. Aber jetzt ist es die gleiche Idee - statt - so wenn Baum nicht gleich null - oder, na ja, wenn Baum macht gleich null, das ist der schlimmen Fall, wenn Baum gleich null, dann ist die erste Bedingung wird falsch sein. So falsch mit etwas anded wird was? [Student] False. >> Ja. Das ist die andere Hälfte der Kurzschluss Evaluierung, wo, wenn Baum nicht gleich null, dann werden wir nicht gehen, um selbst zu gehen - oder wenn Baum macht gleich null, dann werden wir nicht auf den Wert == Baum Wert zu tun. Wir gehen nur sofort false zurück. Was ist wichtig, da, wenn es nicht Kurzschluss evaluate, dann, wenn Baum macht gleich null ist, wird diese zweite Bedingung seg Fehler gehen, weil tree-> Wert wird Dereferenzierung null. So basta. Kann dies zu machen - zu verlagern einmal über. Dies ist eine sehr gewöhnliche Sache auch nicht machen diese eine Zeile mit diesem, aber es ist eine gemeinsame Sache in den Bedingungen, vielleicht stimmt hier nicht, aber wenn (Baum! = NULL und tree-> value == Wert), zu tun was auch immer. Dies ist eine sehr häufige Erkrankung, wo anstatt dies in zwei ifs zu brechen, wo mögen, ist der Baum null? Okay, es ist nicht null, so ist jetzt der Baum, der gleich Wert? Tun Sie dies. Stattdessen diese Bedingung, wird dies nie seg Fehler weil sie ausbrechen wird, wenn dies geschieht, um null sein. Nun, ich, wenn Ihr Baum ist ein komplett ungültigen Zeiger schätze, kann es noch seg Fehler, aber es kann nicht seg Schuld, wenn Baum ist null. Wenn es null wäre, wäre es zu brechen, bevor Sie den Mauszeiger immer in erster Linie dereferenziert. [Student] Ist das sogenannte Lazy Evaluation? 

[Bowden] Lazy Evaluation ist eine separate Sache. Lazy Evaluation ist mehr wie Sie für einen Wert zu fragen, Sie bitten, einen Wert, der Art der Berechnung, aber Sie brauchen es nicht sofort. So, bis Sie wirklich brauchen, ist es nicht ausgewertet. Dies ist nicht genau das gleiche, aber in der Huffman pset, er sagt, dass wir "faul" zu schreiben. Der Grund, warum wir das tun, weil wir eigentlich Pufferung sind die Schreib - wir wollen nicht auf einzelne Bits in einer Zeit zu schreiben, oder einzelne Bytes auf einmal, sondern wir wollen einen Chunk von Bytes zu erhalten. Dann, wenn wir ein Stück von Bytes haben, dann schreiben wir es heraus. Auch wenn Sie fragen, es zu schreiben - und fwrite und fread tun die gleiche Art von Ding. Sie puffern Ihren liest und schreibt. Auch wenn Sie darum bitten, sofort zu schreiben, ist es wahrscheinlich nicht. Und man kann nicht sicher sein, dass sich die Dinge geschrieben werden bis Sie hfclose oder rufen Sie, was es ist, was sagt dann, okay, ich schließe meine Datei, das heißt, ich würde besser schreiben, was ich nicht geschrieben noch. Es ist nicht nötig, alles zu schreiben, bis Sie die Datei zu schließen sind, und dann muss es. Also das ist genau das, was faul - er wartet, bis es zu geschehen hat. Diese - nehmen 51 und du wirst in es mehr ins Detail gehen, weil OCaml und alles in 51, ist alles Rekursion. Es wurden noch keine iterativen Lösungen, im Grunde. Alles ist Rekursion und lazy evaluation sein wird für eine Menge von Umständen wichtig wo, wenn Sie nicht faul zu bewerten hat, würde das bedeuten, - Das Beispiel ist Bäche, die unendlich lang sind. In der Theorie kann man der natürlichen Zahlen als ein Strom von 1-2-3-4-5-6-7 denken, So lässig beurteilt die Dinge sind in Ordnung. Wenn ich sage, ich will das zehnte Nummer, dann kann ich beurteilen bis zum zehnten Nummer. Wenn ich das hundertste Zahl wollen, dann kann ich beurteilen bis zum hundertsten Nummer. Ohne lazy evaluation, dann wird es zu versuchen, alle Nummern sofort auszuwerten. Du bist Auswertung unendlich viele Zahlen, und das ist einfach nicht möglich. So gibt es eine Menge von Fällen, in denen lazy evaluation ist nur wichtig, dass die Dinge funktionieren. 

Jetzt wollen wir insert schreiben, wo Einsatz sein wird ähnlich Änderung in seiner Definition. So jetzt ist es bool insert (int value). Wir werden, dass die bool insert (int value, Knoten *-Baum) zu ändern. Wir tatsächlich zu, dass wieder ändern in ein bisschen, wir werden sehen warum. Und lassen Sie uns zu bewegen build_node, nur für das Heck von ihm, oben legen, damit wir nicht haben, um einen Funktionsprototyp schreiben. Was ist ein Hinweis, dass du gehst zu sein mit build_node in Einsatz. Okay. Nehmen Sie eine Minute dafür. Ich glaube, ich rettete die Revision, wenn Sie von dem ziehen wollen, oder zumindest habe ich jetzt. Ich wollte eine leichte Pause, um über die Logik des Einsatzes denken, wenn man nicht daran zu denken. Grundsätzlich werden Sie immer nur an Blättern, hinzugefügt. Wie, wenn ich 1 einzulegen, dann bin ich unweigerlich zu Einfügen 1 - Ich werde in Schwarz zu ändern - ich werde sein Einsetzen 1 hier. Oder wenn ich 4 einzufügen, möchte ich sein Einsetzen 4 über hier. Also egal, was du tust, wirst du auf ein Blatt, hinzugefügt. Alles, was Sie tun müssen, ist zu durchlaufen den Baum, bis Sie auf den Knoten zu erhalten das sollte dem Knoten übergeordneten, des neuen Knotens Elternteil zu sein, und ändern ihre linken oder rechten Zeiger, je nachdem, ob es größer oder kleiner als der aktuelle Knoten. Ändern Sie den Zeiger, um Ihre neuen Knoten zeigen. So durchlaufen den Baum, um das Blatt auf den neuen Knoten. Auch darüber, warum, dass verbietet die Art von Situation, bevor denken, wo ich baute die binären Baum, wo es richtig war wenn Sie sah nur an einem einzigen Knoten aber 9 war auf der linken Seite 7, wenn Sie unten iteriert den ganzen Weg. Damit ist unmöglich in diesem Szenario, da - denken über das Einfügen von 9 oder etwas, auf den ersten Knoten Ich werde bis 7 zu sehen und ich werde einfach nach rechts zu gehen. Also egal, was ich tue, wenn ich, indem Sie auf ein Blatt einfügen, und zu einem Blatt mit dem entsprechenden Algorithmus, es wird unmöglich sein, für mich 9 auf der linken Seite 7 einsetzen, um denn sobald ich 7 getroffen werde ich nach rechts gehen. Hat jemand etwas mit anfangen? [Student] ich. >> Sure. [Student, unverständlich] [Other Student, unverständlich] [Bowden] Es ist geschätzt. Okay. Möchten Sie das erklären? 

[Student] Da wir wissen, dass wir das Einfügen neue Knoten am Ende des Baums, Ich durchgeschleift Baum iterativ bis ich zu einem Knoten, auf null hingewiesen. Und dann habe ich beschlossen, es entweder man auf der rechten Seite oder der linken Seite dieses Recht in variable, es hat mir gesagt, wohin damit. Und dann, im Wesentlichen, Ich habe gerade das letzte - daß temporäre Knotenpunkt an den neuen Knoten, die es wurde schaffen, entweder auf der linken oder auf der rechten Seite, je nachdem, was der Wert richtig war. Schließlich habe ich den neuen Knoten auf den Wert ihrer Prüfung. [Bowden] Okay, so sehe ich ein Problem hier. Das ist wie 95% der Weg dorthin. Das einzige Problem, das ich sehe, na ja, hat jemand anderes sehen ein Problem? Was ist der Umstand, unter dem sie brechen aus der Schleife? [Student] Wenn temp ist null? >> Ja. So, wie Sie brechen aus der Schleife ist, wenn temp ist null. Aber was soll ich tun hier richtig? Ich dereference temp, die zwangsläufig null ist. So die andere Sache, die Sie tun müssen, ist nicht nur behalten, bis temp ist null, Sie wollen den Überblick über die Muttergesellschaft halten zu allen Zeiten. Wir wollen auch Knoten * parent, ich denke, wir können das bei null auf den ersten zu halten. Das wird seltsame Verhalten für die Wurzel des Baumes haben, aber wir werden dazu kommen. Wenn der Wert größer ist als was auch immer, dann temp: = temp rechts. Doch bevor wir das tun, parent = temp. Oder sind die Eltern immer zu gleicher temp? Ist das der Fall? Wenn Temp nicht null ist, dann werde ich nach unten zu bewegen, egal was, zu einem Knoten, für die temp ist die Muttergesellschaft. So Muttergesellschaft geht zu temp, und dann bewege ich mich Temp unten. Jetzt temp ist null, aber Mutter verweist auf die Muttergesellschaft der Sache, die null ist. So hier unten, ich will nicht um rechts gleich 1 ist. Also zog ich nach rechts, so dass, wenn rechts = 1, und ich denke, Sie wollen auch zu tun - wenn Sie an der linken Seite, Sie wollen richtig eingestellt gleich 0 ist. Oder wenn Sie jemals nach rechts zu bewegen. So rechts = 0. Wenn rechts = 1, Jetzt wollen wir das übergeordnete Recht Zeiger newNode machen, Wir wollen also das übergeordnete linken Zeiger newNode machen. Fragen dazu? Okay. Das ist also die Art, wie wir - na ja, eigentlich, anstatt dies zu tun, wir die Hälfte erwartet, dass du build_node verwenden. Und dann, wenn newNode gleich null, false zurück. Basta. Nun, dies ist, was wir Ihnen zu tun erwartet. 

Dies ist, was die Mitarbeiter Lösungen zu tun. Ich bin nicht einverstanden mit diesem als der "richtigen" Weg zu gehen darüber aber das ist völlig in Ordnung, und es wird funktionieren. Eine Sache, die ein wenig seltsam stimmt ist jetzt wenn der Baum beginnt als null, wir in einer null Baum passieren. Ich denke, es hängt davon ab, wie definieren Sie das Verhalten der Übergabe eines null Baum. Ich würde denken, dass, wenn Sie in einem null Baum übergeben, dann Einsetzen des Wertes in einem Null-Baum sollte einfach einen Baum, wo der einzige Wert ist, dass einzelne Knoten. Haben die Leute stimmen dem zu? Man könnte, wenn man wollte, Übergeben Sie in einem null Baum und Sie einen Wert in sie einfügen möchten, false zurück. Es ist an Ihnen, daß definieren. Um das erste, was ich sagte und dann - gut, wirst du Schwierigkeiten damit, dass zu haben, weil Es wäre einfacher, wenn wir einen globalen Zeiger zu der Sache hatte, aber wir wissen nicht, also, wenn Baum ist null, es gibt nichts, was wir dagegen tun können. Wir können nur false zurück. So werde ich einfügen ändern. Wir technisch könnte nur ändern Sie diese hier, wie es über die Dinge Iteration, aber ich werde Einsatz verändern Werfen Sie einen Knoten ** Baum. Doppel-Zeiger. Was bedeutet das? Statt sich mit Zeigern auf Knoten, das, was ich gehen zu manipulieren bin ist dieser Zeiger. Ich werde zu manipulieren diesen Zeiger. Ich werde zu manipulieren Pointer direkt. Dies macht Sinn, da über sich denken - gut, jetzt deutet dies auf null. Was ich tun möchte, ist zu manipulieren diesen Zeiger verweisen auf nicht null. Ich will es auf meine neuen Knoten zeigen. Wenn ich nur verfolgen Zeiger auf meiner Zeiger, dann brauche ich nicht den Überblick eines Elternteils Zeiger zu halten. Ich kann nur verfolgen, um zu sehen, ob der Zeiger zeigt auf null und wenn der Zeiger zeigt auf null ändern, um den Knoten Ich möchte darauf hinweisen. Und ich kann es ändern, da ich einen Zeiger auf den Zeiger haben. Lassen Sie uns dieses Recht jetzt zu sehen. Sie können tatsächlich tun es rekursiv ziemlich leicht. Wollen wir das? Ja, das tun wir. 

Mal sehen, es rekursiv. Zunächst wird, was unserem Basisszenario gehen zu sein? Fast immer unser Basisszenario, aber eigentlich ist diese Art von tricky. First things first, if (baum == NULL) Ich denke, wir sind gerade dabei, false zurück. Dies unterscheidet sich von Ihrem Baum ist null. Dies ist der Zeiger auf Ihr Root-Zeiger ist null was bedeutet, dass Ihr Root-Zeiger existiert nicht. So hier unten, wenn ich node * - lasst uns einfach wiederverwenden dies. Node * root = NULL, und dann werde ich einfügen, indem Sie etwas wie nennen, legen Sie 4 in & root. So & Root, wenn root ein Knoten * ist dann & root wird ein Knoten ** sein. Dies ist gültig. In diesem Fall, Baum, hier oben, Baum ist nicht null - oder Beilage. Here. Baum ist nicht null; * Baum ist null, was in Ordnung ist denn wenn *-Baum null ist, dann kann ich manipulieren jetzt, was ich will es Punkt zu Punkt. Aber wenn Baum ist null, dh ich kam gerade hier unten und sagte: null. Das macht keinen Sinn. Ich kann nicht alles tun, damit. Wenn Baum ist null, false zurück. So habe ich im Grunde schon gesagt, was unsere wirkliche Basis Fall ist. Und was ist das denn sein? [Student, unverständlich] [Bowden] Ja. So if (* baum == NULL). Dies bezieht sich auf den Fall hier wo, wenn meine roten Zeiger ist der Zeiger Ich bin auf konzentriert, so wie ich auf dieses Zeigers bin konzentriert, jetzt bin ich auf dieser Zeiger konzentriert. Jetzt bin ich auf dieses Zeigers konzentriert. Also, wenn meine roten Zeiger, die mein Knoten ** ist, ist immer - wenn *, mein roter Zeiger, ist immer null, das bedeutet, dass ich in dem Fall, dass ich auf einem Zeiger, der Schwerpunkt werde Uhr - dies ist ein Zeiger, der zu einem Blatt gehört. Ich möchte dieses Zeigers zu ändern, um zu meinem neuen Knoten zeigen. Komm zurück hierher. Meine newNode werden nur Knoten * n = build_node (Wert) Dann n, wenn n = NULL, false zurück. Else wollen wir ändern, was der Zeiger derzeit zeigt jetzt unseren neu gebauten Knoten zeigen. Wir können tatsächlich das hier tun. Anstatt zu sagen, n, sagen wir *-Baum = if *-Baum. Jeder verstehen? Das durch den Umgang mit Zeigern auf Zeiger, wir ändern können Null-Pointer, um Dinge, die wir wollen, dass sie darauf hinweisen. Das ist unser Basis-Szenario. 

Jetzt ist unsere Wiederkehr, oder unsere Rekursion wird sehr ähnlich sein zu allen anderen Rekursionen wir getan haben. Wir gehen zu wollen, Wert legen, und jetzt werde ich ternären wieder zu verwenden, sondern das, was unsere Lage sein wird? Was ist es wir nach, um zu entscheiden, ob wir links oder rechts gehen möchten suchen? Lasst es uns in getrennten Schritten. If (value <), was? [Student] Der Baum der Wert? [Bowden] Also denken Sie daran, dass ich derzeit bin - [Studenten, unverständlich] [Bowden] Yeah, so hier, sagen wir mal, dass diese grünen Pfeil ist ein Beispiel dafür, was Baum derzeit ist, ist ein Zeiger auf diesen Zeiger. Das heißt also Ich bin ein Zeiger auf einen Zeiger auf 3. Die Dereferenzierung zweimal klang gut. Was muss ich - wie mache ich das? [Student] Dereference einmal, und dann tun arrow so? [Bowden] So (*-Baum) ist die Dereferenzierung einmal -> Wert wird mir den Wert des Knotens, dass ich indirekt wies auf. So kann ich auch schreiben, ** tree.value, wenn Sie das bevorzugen. Entweder funktioniert. Wenn das der Fall ist, dann möchte ich nennen einfügen mit dem Wert. Und was meine aktualisierte Knoten ** sein wird? Ich will nach links gehen, so ** baum.links wird zu meiner Linken sein. Und ich will den Zeiger auf diese Sache so daß, wenn der linke endet als der Null-Zeiger, Ich kann es ändern, um meine neuen Knoten zeigen. 

Und der andere Fall können sehr ähnlich. Lasst uns eigentlich, dass meine ternären jetzt machen. Legen Sie Wert, wenn Wert <(** Baum). Wert. Dann wollen wir unsere ** auf der linken Seite zu aktualisieren, was wir wollen unsere ** auf der rechten Seite zu aktualisieren. [Student] Heißt das bekommen Sie den Zeiger auf den Zeiger? [Bowden] Beachten Sie, dass - ** baum.rechts ein Knoten Stern ist. [Student, unverständlich] >> Ja. ** Baum.rechts ist wie dieses Zeigers oder so etwas. So, indem sie einen Zeiger auf, dass, das gibt mir, was ich will der Zeiger auf diesen Kerl. [Student] Könnten wir gehen immer wieder, warum wir mit den beiden Zeiger werden? [Bowden] Yeah. Also - nein, man kann, und diese Lösung vor war ein Weg, es zu tun, ohne dabei zwei Zeigern. Sie müssen in der Lage sein zu verstehen, mit zwei Zeigern, und dies ist eine saubere Lösung. Beachten Sie auch, dass, wenn mein Baum geschieht - Was passiert, wenn meine Wurzel war null? Was passiert, wenn ich diesen Fall hier zu tun? So node * root = NULL, legen Sie 4 in & root. Was ist root werde nach sein? [Student, unverständlich] >> Ja. Wurzelwert wird 4 sein. Root links sein wird null, wird root rechten werde null sein. In dem Fall, wo man nicht bestanden Wurzel nach Adressen, konnten wir nicht ändern root. In dem Fall, wo der Baum - wo Wurzel war null, wir mussten nur false zurück. Es gibt nichts, was wir tun konnten. Wir können nicht einfügen einen Knoten in einen leeren Baum. Aber jetzt können wir, wir machen nur eine leere Baum in einem Ein-Knoten-Baum. Welches ist in der Regel die erwarteten, dass es angenommen hat, um zu arbeiten. 

Darüber hinaus ist diese deutlich kürzer als Auch die Verfolgung der Eltern, und so durchlaufen Sie alle den Weg. Jetzt habe ich meine Eltern, und ich habe nur meine Eltern rechten Zeiger auf das was auch immer. Stattdessen, wenn wir dies taten iterativ, wäre es die gleiche Idee mit einer while-Schleife. Aber anstatt mit meinen Eltern Zeiger umzugehen, Statt meiner aktuellen Zeiger wäre die Sache dass ich direkt ändern zu meinem neuen Knoten zeigen. Ich habe nicht mit, ob es nach links zeigt umzugehen. Ich habe nicht mit, ob es nach rechts zeigt umzugehen. Es ist nur, was dieser Zeiger ist, ich werde es auf meine neuen Knoten zeigen. Jeder verstehen, wie es funktioniert? Wenn nicht, warum wollen wir es auf diese Weise, aber zumindest, dass dies funktioniert als Lösung? [Student] Wo stehen wir return true? [Bowden] Das ist wahrscheinlich genau hier. Wenn wir richtig eingesetzt ist, true zurückgeben. Else, hier unten sind wir gehen zu wollen, was auch immer Insert Returns zurückzukehren. 

Und was ist das Besondere an diesem rekursive Funktion? Es ist endrekursiv, so lange, wie wir mit einigen Optimierungen zu kompilieren, es wird erkennen, dass und du wirst nie einen Stack-Überlauf davon auch wenn unser Baum hat eine Höhe von 10.000 oder 10 Millionen. [Student, unverständlich] [Bowden] Ich denke, es tut bei Dash - oder was Optimierungsstufe ist für einen Endrekursion zu erkennenden erforderlich. Ich denke, es erkennt - GCC und Clang auch unterschiedliche Bedeutung für deren Optimierung Ebenen. Ich möchte sagen, es ist DashO 2, für sicher, dass es Endrekursion erkennen. Aber wir - man konnte wie ein Fibonocci Beispiel oder etwas zu bauen. Es ist nicht leicht, mit diesem Test, da es schwierig ist, zu konstruieren ein binärer Baum, der so groß ist. Aber ja, ich denke es ist DashO 2, dass wenn Sie kompilieren mit DashO 2, wird es für Endrekursion aussehen und optimieren, dass aus. Gehen wir zurück zu - einzufügen ist buchstäblich das letzte, was er braucht. Gehen wir zurück zu dem Einsatz hier wohin wir gehen, um die gleiche Idee zu tun. Es wird immer noch den Fehler nicht in der Lage vollständig zu behandeln wenn die Wurzel selbst ist null, oder die Vergangenheit Eintrag ist null, aber anstatt den Umgang mit einem Elternteil Zeiger, Wenden Sie das gleiche Logik zu halten Zeiger auf Zeiger. Wenn hier halten wir unsere Knoten ** Aktuell, und wir brauchen nicht zu verfolgen mehr richtig, aber Knoten ** cur = & Baum. Und nun unsere while-Schleife sein wird, während * Aktuell nicht gleich null. Brauchen Sie nicht den Überblick über die Eltern mehr zu halten. Brauchen Sie nicht den Überblick über links und rechts halten. Und ich nenne es temp, weil wir bereits sind temp. Okay. So if (Wert> * temp) dann & (* temp) -> rechts else temp = & (* temp) -> links. Und jetzt, an diesem Punkt, nach dieser while-Schleife, Ich mache nur das, weil es vielleicht einfacher ist, zu iterativ als rekursiv denken, aber nach dieser while-Schleife, * Temp ist der Zeiger wollen wir ändern. 

Vorher hatten wir Eltern, und wir wollten ein Elternteil nach links oder rechts ändern Muttergesellschaft, aber wenn wir wollen Eltern Recht zu ändern, dann * temp Muttergesellschaft rechts, und wir können es direkt zu ändern. So hier unten können wir tun * temp = newNode, und das ist es. So Ankündigung war alles, was wir in dies tat nehmen Sie Zeilen Code. Um den Überblick über die Muttergesellschaft in allem, was zusätzlichen Aufwand ist zu halten. Hier wird, wenn wir nur den Überblick über die Zeiger auf den Zeiger, und selbst wenn wir wollten, um loszuwerden, alle diese geschweiften Klammern jetzt lassen es so aussehen kürzer. Das ist nun genau die gleiche Lösung, aber weniger Zeilen Code. Sobald Sie anfangen, erkennen dies als eine gültige Lösung, Es ist auch einfacher, über Grund, als wie, okay, warum habe ich dieses Flag bei int. Recht? Was bedeutet das? Oh, es bedeutet, dass jedes Mal, wenn ich nach rechts, ich brauche, um es einrichten, else if gehe ich nach links muss ich es auf Null gesetzt. Hier habe ich nicht an die Vernunft über das, es ist einfacher zu denken. Haben Sie Fragen? [Student, unverständlich] >> Ja. Okay, so im letzten Bit - Ich denke, eine schnelle und einfache Funktion, die wir tun können, ist, let's - zusammen, glaube ich, zu versuchen und zu schreiben eine Funktion contains was nicht egal, ob es ein binärer Suchbaum ist. Diese enthält Funktion sollte true zurückgeben wenn irgendwo in dieser allgemeinen Binary Tree ist der Wert, den wir suchen. Also lasst uns zuerst tun es rekursiv und dann werden wir es iterativ zu tun. Wir können eigentlich nur tun es gemeinsam, weil dies wird sehr kurz sein. 

Was ist meine Basis Falle gehen werden? [Student, unverständlich] [Bowden] So if (baum == NULL), was dann? [Student] Zurück falsch. [Bowden] Else, gut, ich brauche den anderen. Wenn war meine andere base case. [Student] Tree Wert? >> Ja. So if (tree-> value == Wert. Beachten Sie, dass wir zurück auf Knoten *, nicht Knotens ** s? Enthält sie nie brauchen, um einen Knoten ** verwenden, da wir nicht ändern Zeigern. Wir stehen noch durchqueren sie. Wenn das passiert, dann wollen wir true zurück. Else wollen wir die Kinder zu durchqueren. So können wir nicht, ob alles nach links ist weniger Grund und alles, was auf der rechten Seite größer ist. Also, was ist unsere Bedingung hier sein - oder, was sollen wir tun? [Student, unverständlich] >> Ja. Rückgabe enthält (Wert, tree-> links) oder enthält (Wert, tree-> rechts). Und das ist es. Und bemerken es gibt einige Kurzschluss Evaluierung wo, wenn wir den Wert in der linken Baum zu finden passieren, brauchen wir nicht auf dem richtigen Baum zu suchen. Das ist die ganze Funktion. Jetzt machen wir es iterativ was sein wird, weniger schön. Wir nehmen die üblichen Start des Knotens * cur = Baum. Während (Aktuell! = NULL). Schnell gehen, um ein Problem zu sehen. Wenn Aktuell - hier draußen, wenn wir jemals brechen aus diesem, dann haben wir aus der Dinge laufen zu sehen, so false zurück. Wenn (Aktuell-> value == Wert), true zurückgeben. So, jetzt sind wir an einem Ort - wir wissen nicht, ob wir links oder rechts gehen soll. So willkürlich, lasst uns einfach links gehen. Ich habe natürlich in ein Problem, wo ich komplett alles habe aufgegeben laufen - Ich werde immer nur überprüfen, die linke Seite eines Baumes. Ich werde nie überprüfen alles, was ein rechtes Kind von etwas ist. Wie kann ich dieses Problem beheben? [Student] Sie haben den Überblick über die links und rechts in einem Stapel zu halten. [Bowden] Yeah. So machen wir es struct Liste Knoten * n, und dann Knoten ** nächste? Ich denke, das funktioniert gut. Wir wollen gehen über die linke oder let's - hier oben. Struct Liste list =, wird es beginnen an dieser struct Liste. * List = NULL. Also das wird unser verlinkten Liste sein von Teilbäumen, dass wir übersprungen. Wir werden jetzt links überqueren, aber da wir unweigerlich müssen kommen wieder nach rechts, Wir werden auf der rechten Seite innerhalb unserer struct Liste zu halten. Dann müssen wir new_list oder Struktur, struct list *, new_list = malloc (sizeof (list)). Ich werde zu ignorieren Fehlerprüfung, aber Sie sollten überprüfen, ob es null zu sehen. New_list den Knoten es geht um Point - oh, das ist, warum ich es wollte hier oben. Es wird zu einer zweiten struct Liste verweist. Das ist, wie verkettete Listen Arbeit. Dies ist das gleiche wie ein int verkettete Liste außer wir nur ersetzen int mit Knoten *. Es ist genau das gleiche. So new_list, der Wert unserer new_list Knoten, sein wird, Aktuell-> rechts. Der Wert unserer new_list-> next wird unsere ursprüngliche Liste zu sein, und dann werden wir unsere Liste aktualisieren, um new_list zeigen. 

Jetzt brauchen wir eine Art und Weise zu ziehen Dinge, wie wir es die ganze linke Teilbaum durchlaufen. Jetzt brauchen wir, um Sachen zu ziehen aus ihm heraus, wie Aktuell ist null, wir wollen nicht nur false zurück. Wir wollen nun außerhalb ziehen an unserem neuen Liste. Ein bequemer Weg, dies zu tun - na ja, eigentlich gibt es mehrere Möglichkeiten, dies zu tun. Jemand einen Vorschlag? Wo sollte ich dies tun oder wie soll ich das tun? Wir haben nur ein paar Minuten, aber irgendwelche Vorschläge? Statt - ein Weg, anstatt unsere Bedingung ist, während was wir derzeit auf der Suche auf nicht null ist, sondern wir gehen weiter zu gehen, bis unsere Liste selbst ist null. Also, wenn unsere Liste endet als null, dann haben wir aus der Dinge laufen zu suchen, zur Suche vorbei. Aber das bedeutet, dass das erste, was in unserer Liste ist gerade dabei, den ersten Knoten sein. Das allererste, was sein wird - wir müssen nicht mehr sorgen. So list-> n wird unser Baum. list-> next wird null sein. Und jetzt, während Liste ist nicht gleich null. Aktuell wird etwas aus unserer Liste zu ziehen. So Aktuell wird gleich list-> n gehen. Und dann Liste wird gleich list-> n, oder list-> next. Also, wenn Aktuell Wert gleich Wert. Jetzt können wir hinzufügen, sowohl unser Recht Zeiger und unsere linke Zeiger Solange sie es nicht sind null. Hier unten, denke ich, sollten wir das getan haben, in den ersten Platz. Wenn (Aktuell-> right! = NULL) dann werden wir diesen Knoten in unsere Liste einzufügen. Wenn (Aktuell-> links), das ist ein wenig zusätzliche Arbeit, aber es ist in Ordnung. Wenn (Aktuell-> left! = NULL), und wir gehen nach links in unseren verketteten Liste einzufügen, und dass es sein sollte. Wir durchlaufen - so lange wir etwas haben in unserer Liste Wir haben einen anderen Knoten zu betrachten. Also schauen wir an diesem Knoten, Wir entwickeln unsere Liste auf der nächsten. Wenn dieser Knoten ist der Wert, den wir suchen, können wir true zurück. Else legen unsere beiden linken und rechten Teilbäume, Solange sie es nicht sind null, in unsere Liste so dass wir unweigerlich über sie gehen. Also, wenn sie nicht null, wenn unsere root Zeiger wies auf zwei Dinge, dann wir zunächst zog etwas aus, damit unsere Liste endet als null. Und dann haben wir zwei Dinge zurück, so dass nun unserer Liste ist der Größe 2. Dann sind wir in einer Schleife zurück und wir werden einfach nur zu ziehen, sagen wir mal, die linke Zeiger unserer Wurzelknoten. Und das werde einfach weiter passiert, wir werden am Ende eine Schleife über alles. 

Beachten Sie, dass dies wesentlich komplizierter war im rekursiven Lösung. Und ich habe gesagt, mehrfach dass die rekursive Lösung hat in der Regel viel gemeinsam mit der iterativen Lösung. Hier ist dies genau das, was die rekursive Lösung tut. Die einzige Änderung ist, dass anstelle der implizit mit den Stapel, der Programm-Stack, wie Sie Ihren Weg im Auge zu behalten, was Knoten müssen Sie noch besuchen, jetzt müssen Sie explizit eine verkettete Liste. In beiden Fällen sind die Verfolgung von welcher Knoten muss noch besichtigt werden. In der rekursiven Fall ist es einfach leichter, weil ein Stapel ist für Sie als Programm-Stack implementiert. Beachten Sie, dass diese verketteten Liste, es ist ein Stack ist. Was auch immer wir haben gerade auf dem Stack ist ab sofort, was wir zu ziehen aus dem Stapel zum nächsten zu besuchen. Wir haben keine Zeit mehr, aber noch Fragen? [Student, unverständlich] [Bowden] Yeah. Also, wenn wir unsere verketteten Liste, Strom werde diesen Kerl zeigen, und jetzt sind wir gerade Weiterentwicklung unserer verketteten Liste auf diesen Kerl zu konzentrieren. Wir über den verketteten Liste in dieser Linie durchquert. Und dann habe ich denke, wir sollten unsere verketteten Liste und Sachen befreien einmal vor der Rückkehr wahr oder falsch, müssen wir iterieren unserer verketteten Liste und immer hier unten, ich denke, wenn wir Aktuell Recht ist nicht gleich, fügen Sie es, so jetzt müssen wir befreien wollen Aktuell weil, na ja, wir haben komplett über die Liste vergessen? Yeah. Also das ist, was wir hier tun wollen. Wo ist der Zeiger? Aktuell war damals - wir wollen eine struct list * 10 entspricht Liste neben. Freie Liste, Liste = temp. Und in dem Fall, wo wir true zurückgeben, müssen wir iterieren über den Rest unserer verketteten Liste befreien Dinge. Die nette Sache über die rekursive Lösung ist befreiend Dinge bedeutet nur knallen factorings vom Stapel, der für euch geschehen wird. So haben wir von etwas, das wie 3 Zeilen hard-to-think-zu-Code ist weg etwas, das deutlich viel mehr ist schwer zu glauben, zu Zeilen Code. Noch Fragen? Gut. Wir sind gut. Bye! [CS50.TV]