Tutorial für Baumdatenstruktur für Anfänger

Einführung

Ein Baum in Software ist wie ein biologischer Baum, aber mit den folgenden Unterschieden:

• Es wird verkehrt herum gezogen.
• Es hat nur eine Wurzel und keinen Stiel.
• Die Zweige entstehen aus der Wurzel.
• Ein Punkt, an dem ein Zweig von einem anderen Zweig abzieht oder die Wurzel als Knoten bezeichnet wird.
• Jeder Knoten hat einen Wert.

Die Zweige des Softwarebaums werden durch gerade Linien dargestellt. Ein gutes Beispiel für einen Softwarebaum, den Sie möglicherweise verwendet haben, ist der Verzeichnisbaum der Festplatte Ihres Computers.

Es gibt verschiedene Arten von Bäumen. Da ist der allgemeine Baum, von dem andere Bäume abgeleitet werden. Andere Bäume werden durch Einführung von Einschränkungen in den allgemeinen Baum abgeleitet. Zum Beispiel möchten Sie möglicherweise einen Baum, bei dem nicht mehr als zwei Zweige von einem Knoten ausgehen. Ein solcher Baum würde als binärer Baum bezeichnet. Dieser Artikel beschreibt den allgemeinen Baum und wie man auf alle seine Knoten zugreift.

Der Hyperlink zum Herunterladen des Codes ist am Ende dieses Artikels angegeben.

Um die Code -Beispiele in diesem Artikel zu verstehen, müssen Sie grundlegende Kenntnisse in JavaScript (ECMascript) haben. Wenn Sie dieses Wissen nicht haben, können Sie es von http: // www erhalten.breites Netzwerk.com/chrysanthusforcha-1/ecmascript-2015-Gänge.htm

Das allgemeine Baumdiagramm

'A' ist der Wurzelknoten; Es ist der Knoten erster Stufe. B, C, D sind in der zweiten Zeile; Dies sind Knoten der zweiten Ebene. E, F, G, H, I, J, K sind in der dritten Zeile und sie sind Knoten auf der dritten Stufe. Eine vierte Zeile hätte Knoten der vierten Ebene erzeugt und so weiter.

Baumeigenschaften

- Alle Zweige für alle Stufen von Knoten haben eine Quelle, die der Wurzelknoten ist.

- Ein Baum hat n - 1 Zweige, wobei n die Gesamtzahl der Knoten ist. Das obige Diagramm für den allgemeinen Baum hat 11 Knoten und 10 Zweige.

- Anders als bei Menschen, bei denen jedes Kind zwei Eltern hat, hat jedes Kind nur ein Elternteil. Der Wurzelknoten ist der größte Vorfahrer Elternteil. Ein Elternteil kann mehr als ein Kind haben. Jeder Knoten außer dem Wurzelknoten ist ein Kind.

Baumvokabular

• Wurzelknoten: Dies ist der höchste Knoten im Baum, und er hat keinen Elternteil. Jeder andere Knoten hat einen Elternteil.
• Blattknoten: Ein Blattknoten ist ein Knoten, der kein Kind hat. Sie befinden sich normalerweise am Boden des Baumes und sind manchmal links und/oder rechte Seiten des Baumes.
• Taste: Dies ist der Wert eines Baumes. Es kann eine Zahl sein; Es kann eine Zeichenfolge sein; Es kann sogar ein Bediener wie + oder - oder x sein.
• Ebenen: Der Stammknoten befindet sich auf der ersten Ebene. Die Kinder sind auf der zweiten Ebene; Die Kinder der Knoten der zweiten Ebene sind auf der dritten Ebene und so weiter.
• Elternknoten: Jeder Knoten mit Ausnahme des Stammknoten. Jeder Knoten mit Ausnahme des Stammknotens ist ein untergeordneter Knoten.
• Geschwisterknoten: Geschwisterknoten sind Knoten mit demselben Elternteil.
• Weg: Die Zweige (gerade Linien), die einen Knoten mit anderen Knoten anschließen, bilden einen Pfad. Die Zweige können Pfeile sein oder nicht.
• Vorfahrknoten: Alle höheren Knoten, die mit einem Kind verbunden sind, einschließlich des Elternteils und des Wurzelknotens, sind Vorfahrknoten.
• Nachkommenknoten: Alle unteren Knoten, die mit einem Knoten verbunden sind, sind bis nach unten mit verbundenen Blättern nachkommensfeste Knoten. Der fragliche Knoten ist nicht Teil der Nachkommenknoten. Der fragliche Knoten muss nicht der Stammknoten sein.
• Subtree: Ein Knoten plus alle seine Nachkommen bis hin zu den verwandten Blättern, bilden Sie einen Unterbaum. Der Startknoten ist enthalten und muss nicht die Wurzel sein; Ansonsten wäre es der ganze Baum.
• Grad: Die Anzahl der Kinder, die ein Knoten hat, wird als Grad des Knotens bezeichnet.

Alle Knoten eines Baumes durchqueren

Alle Knoten eines Baumes können zugegriffen werden, um einen beliebigen Wert des Knotens zu lesen oder zu ändern. Dies wird jedoch nicht willkürlich gemacht. Es gibt drei Möglichkeiten, dies zu tun, was alle wie folgt die Tiefe-First-Durchquerung beinhaltet:

1) In-Ordnung: Einfach ausgedrückt wird in diesem Schema der linke Subtree zuerst durchquert. Dann wird auf den Stammknoten zugegriffen. Dann wird der richtige Subtree durchquert. Dieses Schema wird als links> Wurzel-> rechts symbolisiert. Abb. 1 wird hier als einfache Referenz neu gespielt:

Unter der Annahme, dass es zwei Geschwister pro Knoten gibt; Dann bedeutet links> root-> rechts, Sie zuerst auf den niedrigsten und linken Knoten zugreifen, dann auf das Elternteil des Knotens und dann auf das rechte Geschwister. Wenn es mehr als zwei Geschwister gibt, nehmen Sie den ersten als links und den Rest der rechten Knoten als rechte. Für den allgemeinen Baum oben ist auf den unteren linken Subtree zugegriffen, um zu haben, [EBF]. Dies ist ein Subtree. Der Elternteil dieses Subtree ist a; Als nächstes wird auf A zugegriffen, um [EBF] a zu haben. Als nächstes wird auf das Subtree [GCHI] zugegriffen, um einen größeren Subtree zu haben, [[EBF] A [GCHI]]. Sie können das linke Stammprofil sehen, das sich selbst darstellt. Dieser große linke Subtree hat den Unterbaum [JDK] nach dem Recht, das Durchqueren zu vervollständigen, um zu erhalten, [[EBF] A [GCHI]] [JDK].

2) Vorbestellung: Einfach ausgedrückt, in diesem Schema wird der Stammknoten zuerst zugegriffen, dann wird das linke Subtree als nächst. Dieses Schema wird als root-> links> rechts symbolisiert. Fig. 1 ist hier als einfache Referenz neu gespielt.

Unter der Annahme, dass es zwei Geschwister pro Knoten gibt; Dann bedeutet Wurzel-> links> rechts, Sie zuerst auf die Wurzel, dann auf das linke unmittelbare Kind und dann auf das rechte unmittelbare Kind. Wenn es mehr als zwei Geschwister gibt, nehmen Sie den ersten als links und den Rest der rechten Knoten als rechte. Das linke Kind des linken Kindes ist der nächste, der zugegriffen wird. Für den allgemeinen Baum oben ist der Wurzel -Subtree [ABCD]. Links von diesem Subtree haben Sie den Subtree [EF], der die Zugriffssequenz [ABCD] [EF] angibt, [EF]. Rechts von diesem größeren Teilbaum haben Sie zwei Teilbäume, [Ghi] und [jk], die die vollständige Sequenz geben, [ABCD] [EF] [GHI] [JK]. Sie können sehen, dass das rechte Profil von root-> links-> das rechte Profil selbst dargestellt wird.

3) Nachbestellung: Einfach ausgedrückt, in diesem Schema wird der linke Subtree zuerst durchquert, dann wird der rechte Subtree durchquert und dann wird auf die Wurzel zugegriffen. Dieses Schema wird als links> rechts-> Wurzel symbolisiert. Fig. 1 ist hier als einfache Referenz neu gespielt.

Für diesen Baum sind die Teilbälle [EFB], [Ghic], [jkd] und [a] die Sequenz bilden, [EFB], [Ghic], [jkd] [a]. Sie können das links-> rechts-> Root-Profil sehen, das sich selbst darstellt.

Den Baum erstellen

Der obige Baum wird mit ECMascript erstellt, das wie die neueste Version von JavaScript ist. Jeder Knoten ist ein Array. Das erste Element jedes Knotenarrays ist das übergeordnete Elternteil, ein anderes Array. Der Rest der Elemente des Knotens sind die Kinder des Knoten. Es gibt eine ECMascript -Karte, die jedes Array mit seiner entsprechenden Zeichenfolge (Buchstaben) bezieht. Das erste Codesegment ist:

O = new Array ();
A = new Array ();
B = new Array ();
C = new Array ();
D = new Array ();
//Blätter
E = Neuarray (B); F = Neuarray (B); G = Neuarray (c); H = Neuarray (c);
I = Neuarray (c); J = Neuarray (d); K = Neuarray (d);
// Hinzufügen des Inhalts
O [0] = undefiniert; O [1] = a;
A [0] = o; A [1] = b; A [2] = c; A [3] = D;
B [0] = A; B [1] = e; B [2] = F;
C [0] = a; C [1] = g; C [2] = H; C [3] = i;
D [0] = A; D [1] = j; D [2] = k;
// Zuordnung von Objekten auf Buchstaben
Paare = [[A, 'A'], [B, 'B'], [C, 'C'], [D, 'D'], [E, 'E'], [F, 'F'] , [G, 'g'],
[H, 'h'], [i, 'i'], [j, 'j'], [k, 'k']];
MAPOBJ = New Map (Paare);

In ECMascript können Sie auf eine Funktion zugreifen, die im Programm niedriger definiert ist. Mit Variablen können Sie das jedoch nicht tun. Sie können nicht auf eine Variable zugreifen, die im Programm niedriger definiert ist. Dies ist der Grund, warum die obigen Variablen wie gezeigt entwickelt wurden.

Beachten Sie auch, dass über dem Stammknoten A ein weiterer Knoten O (nicht Null) vorhanden ist (nicht Null). Das erste Element dieses Arrays (Knoten) ist undefiniert, was bedeutet, dass sein eigener übergeordneter Elternteil undefiniert ist. Der zusätzliche Knoten O wurde hinzugefügt, um den Traversing -Code einfach zu machen.

Es gibt auch eine Karte. Die Karte bezieht jedes Array von Ein-Buchstaben-Namen auf den entsprechenden Zeichenfolgennamen eines Buchstabens.

Rekursive Funktion

Um auf alle Elemente eines Baumes zuzugreifen, benötigen Sie eine rekursive Funktion. Eine rekursive Funktion ist eine Funktion, die sich immer wieder aufruft, bis eine Bedingung erfüllt ist.

Der Besuch eines Knotens bedeutet nicht unbedingt den Zugriff auf den Knoten. Um auf einen Knoten zuzugreifen, bedeutet der Wert, der entweder gelesen oder geändert wird. In den Code -Beispielen dieses Artikels bedeutet auf einen Knoten zuzugreifen und den Wert (Schlüssel) des Knotens zu lesen und anzuzeigen. In den Codeproben kann ein Knoten mehr als einmal besucht werden, aber auf seinen Wert wird nur einmal zugegriffen.

Algorithmus und Programmierung

Es gibt ein Programm für jede der drei Traversing -Techniken.

In-Ordnung-Algorithmus und Programmierung

Hier wird zuerst der niedrigste und liegste Knoten besucht. Die [EBF], [[EBF] A [GCHI]] und [JDK] -Uterbaum werden entwickelt, um die vollständige Sequenz zu ergeben, [[EBF] A [GCHI]] [JDK].

Es gibt zwei rekursive Funktionen für dieses Programm, bei denen jeder den anderen anruft. Die Hauptsache heißt FN (Knoten). Das Programm (Code) ist kurz. Laden Sie die kombinierte Datei unten herunter, um die Detail -Codierung zu erhalten.

Die drei Programme haben den gleichen Array Tree (Knode) -Setup.

Vorbestellungsalgorithmus und Programmierung

Hier gibt es nur eine rekursive Funktion. Es heißt Fn (Knoten). Hier werden die Unterbaume [ABCD], [EF], [GHI] und [JK] entwickelt, um die vollständige Sequenz zu ergeben, [ABCD] [EF] [GHI] [JK]. Das Programm dafür ist auch kurz.

Die drei Programme haben den gleichen Array Tree (Knode) -Setup.

Nachbestellungsalgorithmus und Programmierung

Hier wird zuerst der niedrigste und liegste Knoten besucht. Die [EFB], [GHIC], [JKD] und [A] Subtrees werden entwickelt, um die vollständige Sequenz zu ergeben, [EFB], [Ghic], [JKD] [a] .

Es gibt zwei rekursive Funktionen für dieses Programm, bei denen jeder den anderen anruft. Die Hauptsache heißt FN (Knoten). Das Programm dafür ist auch kurz. Laden Sie die kombinierte Datei unten für die detaillierte Codierung herunter.

Die drei Programme haben den gleichen Array Tree (Knode) -Setup.

Arten von Bäumen

Computerprogrammierbäume sind in der Tat nichtlineare Datenstrukturen. Lineare Datenstrukturen sind Listen, Arrays, Stapel, Warteschlangen, Stapel usw. Ein Baum mit N-Knoten hat N-1-Zweige. Wenn die Anzahl der Zweige gleich oder größer ist als die Anzahl der Knoten, wird ein Diagramm erhalten. Eine Grafik ist nicht wirklich ein Baum.

Es gibt Softwarebäume, die Layouts wie den Verzeichnisbaum in der Festplatte eines Computers beschreiben. Viele Bäume beschreiben bestehende Layouts überhaupt nicht. Tatsächlich beschreiben sie Algorithmen. Zum Beispiel wird der mathematische Algorithmus (x + y) x (x -y) durch einen Baum beschrieben. x und y sind Kinderknoten von +. x und y sind wieder Kinderknoten von -. Ein solcher Baum ist als Ausdrucksbaum bekannt.

Viele verschiedene Arten von Bäumen können in verschiedene Überschriften eingeteilt werden. wie binärer Baum, B-Tree, Ausdrucksbaum usw. Alle von ihnen werden vom allgemeinen Baum abgeleitet.

Einige der Baumkategorien sind in weitere Kategorien unterteilt. Der binäre Baum zum Beispiel hat mindestens den binären Suchbaum, den AVL -Baum und den kartesischen Baum.

wird heruntergeladen

Für diesen Artikel wurden drei Programme bereitgestellt. Es gibt ein Programm für die in Ordnungstechnik (Algorithmus), ein weiteres für die Vorbestellungstechnik und eine weitere für die Post-Order-Technik. Alle von ihnen wurden in eine Zip -Datei mit dem Namen Traversing gesteckt. Die ZIP -Datei kann heruntergeladen werden unter: GitHub.

Abschluss

Ein Softwarebaum ist wie ein normaler Baum im Park oder im Wald. Der Computerprogrammierbaum ist jedoch auf dem Kopf. Es gibt verschiedene Arten von Bäumen. Andere Bäume werden durch Einführung von Einschränkungen in den allgemeinen Baum abgeleitet. Alle Knoten eines Baumes können mit einem in Ordnung, vorbestellten oder nach der Bestellung Algorithmus zugegriffen werden. Ein Softwarebaum kann von jeder Computersprache erstellt werden. Hier wurde ECMascript ausgewählt, weil es die einfachste Computersprache ist. Die nächste Art von Baum, die Sie studieren sollten, ist der binäre Baum, da es sich um die beliebteste Baumdatenstruktur handelt.