Share
Bisher haben wir uns Datenstrukturen angesehen, die Daten linear organisieren. Verknüpfte Listen enthalten Daten von einem einzelnen Startknoten zu einem einzelnen Zielknoten. Arrays halten Daten in zusammenhängenden eindimensionalen Blöcken.
In diesem Abschnitt werden wir sehen, wie durch das Hinzufügen einer weiteren Dimension eine neue Datenstruktur eingeführt werden kann: die Baumstruktur. Speziell betrachten wir einen Baumtyp, der als binärer Suchbaum bezeichnet wird. Binäre Suchbäume nehmen die allgemeine Baumstruktur an und wenden eine Reihe einfacher Regeln an, die die Struktur des Baums definieren.
Bevor wir etwas über diese Regeln erfahren, lernen wir, was ein Baum ist.
Eine Baumstruktur ist eine Datenstruktur, bei der jeder Knoten über null oder mehr Kinder verfügt. Zum Beispiel könnten wir einen Baum wie diesen haben:
Eine Organisationsbaumstruktur In diesem Baum können wir die Organisationsstruktur eines Unternehmens sehen. Die Blöcke repräsentieren Personen oder Abteilungen innerhalb des Unternehmens, und die Zeilen repräsentieren Berichtsbeziehungen. Ein Baum ist eine sehr effiziente, logische Art, diese Informationen zu präsentieren und zu speichern.
Der in der vorherigen Abbildung dargestellte Baum ist ein allgemeiner Baum. Es stellt Eltern-Kind-Beziehungen dar, aber es gibt keine Regeln für die Struktur. Der CEO hat einen direkten Bericht, könnte aber genauso gut keinen oder zwanzig haben. In der Abbildung wird Umsatz links von Marketing angezeigt, aber diese Reihenfolge hat keine Bedeutung. Tatsächlich ist die einzige beobachtbare Einschränkung, dass jeder Knoten höchstens einen Elternteil hat (und der oberste Knoten, der Verwaltungsrat, keinen Elternteil hat)..
Ein binärer Suchbaum verwendet dieselbe Grundstruktur wie der allgemeine Baum in der letzten Abbildung, jedoch mit einigen zusätzlichen Regeln. Diese Regeln sind:
Schauen wir uns einen Baum an, der nach diesen Regeln erstellt wird:
Binärer Suchbaum Beachten Sie, wie die von uns angegebenen Einschränkungen im Diagramm durchgesetzt werden. Jeder Wert links vom Wurzelknoten (acht) hat einen Wert von weniger als acht, und jeder Wert rechts ist größer oder gleich dem Wurzelknoten. Diese Regel gilt an jedem Knoten auf dem Weg rekursiv.
Lassen Sie uns mit diesem Baum über die Schritte nachdenken, die für den Aufbau des Baums erforderlich sind. Beim Start des Prozesses war der Baum leer und dann wurde ein Wert (acht) hinzugefügt. Da es sich um die erste Wertschöpfung handelte, wurde sie in die Root-Position (endgültige übergeordnete Position) versetzt.
Wir kennen nicht die genaue Reihenfolge, in der die restlichen Knoten hinzugefügt wurden, aber ich werde einen möglichen Pfad angeben. Werte werden mit einer Methode namens hinzugefügt Hinzufügen das akzeptiert den Wert.
BinaryTree-Baum = neuer BinaryTree (); Baum.Add (8); Baum.Add (4); Baum.Add (2); Baum. Hinzufügen (3); Baum. Hinzufügen (10); Baum. Hinzufügen (6); Baum.Add (7);
Lass uns durch die ersten Elemente gehen.
Acht wurde zuerst hinzugefügt und wurde die Wurzel. Als nächstes wurden vier hinzugefügt. Da vier weniger als acht ist, muss es gemäß Regel Nummer zwei links von acht gehen. Da acht kein Kind auf der linken Seite hat, wird vier zum unmittelbar linken Kind von acht.
Als nächstes werden zwei hinzugefügt. zwei ist weniger als acht, also geht es nach links. Links von acht befindet sich bereits ein Knoten, sodass die Vergleichslogik erneut ausgeführt wird. zwei ist weniger als vier, und vier hat kein linkes Kind, also werden zwei das linke Kind von vier.
Drei wird als nächstes hinzugefügt und geht links von acht und vier. Im Vergleich zu den beiden Knoten ist er größer, sodass drei gemäß Regel Nummer drei rechts von zwei hinzugefügt werden.
Dieser Zyklus, bei dem Werte an jedem Knoten verglichen werden und dann jedes Kind immer wieder überprüft wird, bis der richtige Steckplatz gefunden wird, wird für jeden Wert wiederholt, bis die endgültige Baumstruktur erstellt wird.
Das BinaryTreeNode repräsentiert einen einzelnen Knoten in der Baumstruktur. Es enthält Verweise auf die linken und rechten Kinder (null, wenn keine vorhanden sind), den Wert des Knotens und die IComparable.CompareTo Diese Methode ermöglicht den Vergleich der Knotenwerte, um zu bestimmen, ob der Wert nach links oder rechts vom aktuellen Knoten gehen soll. Das ist das Ganze BinaryTreeNode Klasse - wie Sie sehen können, ist es sehr einfach.
Klasse BinaryTreeNode: IComparable wobei TNode: IComparable public BinaryTreeNode (TNode-Wert) Value = value; public BinaryTreeNode Left get; einstellen; public BinaryTreeNode Right get; einstellen; public TNode Value get; privates Set; /// /// Vergleicht den aktuellen Knoten mit dem angegebenen Wert. /// /// Der mit /// zu vergleichende Knotenwert, wenn der Instanzwert größer als /// der bereitgestellte Wert ist, -1, falls kleiner, oder 0, wenn er gleich ist. public int CompareTo (TNode andere) return Value.CompareTo (andere);
Das BinaryTree Klasse bietet die grundlegenden Methoden, die Sie zum Bearbeiten des Baums benötigen: Hinzufügen, Löschen, ein Enthält Methode, um festzustellen, ob ein Element in der Baumstruktur vorhanden ist, mehrere Durchlauf- und Aufzählungsmethoden (dies sind Methoden, mit denen wir die Knoten in der Baumstruktur in verschiedenen genau definierten Reihenfolgen auflisten können) und die normale Anzahl und klar Methoden.
Um den Baum zu initialisieren, gibt es a BinaryTreeNode Eine Referenz, die den Kopfknoten (Stammknoten) der Baumstruktur darstellt, und es gibt eine Ganzzahl, die verfolgt, wie viele Elemente sich in der Baumstruktur befinden.
öffentliche Klasse BinaryTree: IEnumerable wobei T: IComparable private BinaryTreeNode _head; private int _count; public void Add (T-Wert) throw new NotImplementedException (); public bool Enthält (T-Wert) throw new NotImplementedException (); public bool Remove (T-Wert) throw new NotImplementedException (); public void PreOrderTraversal (Aktionsaktion) throw new NotImplementedException (); public void PostOrderTraversal (Aktionsaktion) throw new NotImplementedException (); public void InOrderTraversal (Aktionsaktion) throw new NotImplementedException (); public IEnumerator GetEnumerator () throw new NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () Neue NotImplementedException () auslösen; public void Clear () throw new NotImplementedException (); public int Count get;
| Verhalten | Fügt den angegebenen Wert zur korrekten Position innerhalb der Baumstruktur hinzu. |
| Performance | O (log n) im Durchschnitt; O (n) im schlimmsten Fall. |
Das Hinzufügen eines Knotens zum Baum ist nicht besonders komplex und wird noch einfacher, wenn das Problem zu einem rekursiven Algorithmus vereinfacht wird. Es gibt zwei Fälle, die berücksichtigt werden müssen:
Im ersten Fall ordnen wir einfach den neuen Knoten zu und fügen ihn dem Baum hinzu. Im zweiten Fall vergleichen wir den Wert mit dem Wert des Knotens. Wenn der Wert, den wir hinzufügen möchten, geringer ist als der Wert des Knotens, wird der Algorithmus für das linke Kind des Knotens wiederholt. Andernfalls wird es für das rechte Kind des Knotens wiederholt.
public void Add (T-Wert) // Fall 1: Der Baum ist leer. Weisen Sie den Kopf zu. if (_head == null) _head = new BinaryTreeNode (value); // Fall 2: Der Baum ist nicht leer, // also rekursiv die richtige Stelle zum Einfügen des Knotens finden. else AddTo (_head, value); _count ++; // Rekursiver Additionsalgorithmus. private void AddTo (BinaryTreeNode-Knoten, T-Wert) // Fall 1: Wert ist kleiner als der aktuelle Knotenwert if (value.CompareTo (node.Value) < 0) // If there is no left child, make this the new left, if (node.Left == null) node.Left = new BinaryTreeNode(value); else // else add it to the left node. AddTo(node.Left, value); // Case 2: Value is equal to or greater than the current value. else // If there is no right, add it to the right, if (node.Right == null) node.Right = new BinaryTreeNode(value); else // else add it to the right node. AddTo(node.Right, value);
| Verhalten | Entfernt die erste gefundene Nachricht mit dem angegebenen Wert. |
| Performance | O (log n) im Durchschnitt; O (n) im schlimmsten Fall. |
Das Entfernen eines Werts aus dem Baum ist eine konzeptionell einfache Operation, die in der Praxis überraschend komplex wird.
Auf hohem Niveau ist die Bedienung einfach:
Der erste Schritt ist einfach und wird, wie wir sehen werden, mit demselben Mechanismus ausgeführt, den auch die Contains-Methode verwendet. Sobald der zu entfernende Knoten identifiziert ist, kann die Operation jedoch einen von drei Pfaden annehmen, die vom Zustand des Baums um den zu entfernenden Knoten vorgegeben werden. Die drei Zustände werden in den folgenden drei Fällen beschrieben.
Fall eins: Der zu entfernende Knoten hat kein rechtes Kind.
Fall 1 Der zu entfernende Knoten hat kein rechtes Kind In diesem Fall kann der Entfernungsvorgang das linke untergeordnete Element einfach an die Stelle des entfernten Knotens verschieben. Der resultierende Baum würde so aussehen:
Fall 1 - Baumstatus nach dem Entfernen Fall zwei: Der zu entfernende Knoten hat ein rechtes Kind, das wiederum kein linkes Kind hat.
Fall zwei Der zu entfernende Knoten hat ein rechtes Kind, das kein übriges Kind hat In diesem Fall möchten wir das rechte Kind (sechs) des entfernten Knotens an die Stelle des entfernten Knotens verschieben. Der resultierende Baum wird folgendermaßen aussehen:
Baumstatus nach dem Entfernen Fall drei: Der zu entfernende Knoten hat ein rechtes Kind, das wiederum ein linkes Kind hat.
Fall 3 - Der zu entfernende Knoten hat ein rechtes Kind, das ein linkes Kind hat In diesem Fall muss das am weitesten links stehende Kind des rechten untergeordneten Knotens in den Steckplatz des entfernten Knotens platziert werden.
Nehmen wir uns eine Minute Zeit, um darüber nachzudenken, warum das so ist. Es gibt zwei Fakten, die wir über den Teilbaum wissen, der mit dem Entfernen des Knotens beginnt (z. B. der Teilbaum, dessen Wurzel der Knoten mit dem Wert fünf ist)..
Wir müssen einen Wert in den Schlitz des entfernten Knotens einfügen, der kleiner als oder gleich jedem Knoten auf der rechten Seite ist. Um dies zu erreichen, müssen wir den kleinsten Wert auf der rechten Seite erhalten. Deshalb brauchen wir den ganz linken Knoten des rechten Kindes.
Nach dem Entfernen des Knotens sieht der Baum so aus:
Fall 3 - Baum nach Knotenentfernung Nachdem wir nun die drei Entfernungsszenarien verstanden haben, wollen wir uns den Code ansehen, um dies zu ermöglichen.
Eine Sache zu beachten: Die FindWithParent method (siehe Abschnitt Enthält) gibt den zu entfernenden Knoten sowie den übergeordneten Knoten des zu entfernenden Knotens zurück. Dies geschieht, da beim Entfernen des Knotens der übergeordnete Knoten aktualisiert werden muss Links oder Recht Eigenschaft, die auf den neuen Knoten zeigt.
Dies könnte vermieden werden, wenn alle Knoten einen Verweis auf ihr übergeordnetes Element enthalten. Dies würde jedoch den Speicheraufwand pro Knoten und die Buchhaltungskosten verursachen, die nur in diesem einen Fall erforderlich sind.
public bool Remove (T-Wert) BinaryTreeNode aktuell, übergeordnet; // Finde den zu entfernenden Knoten. current = FindWithParent (value, out parent); if (aktuell == null) return false; _Anzahl--; // Fall 1: Wenn Strom kein rechtes Kind hat, ersetzt Strom links den Strom. if (current.Right == null) if (übergeordnetes == null) _head = current.Left; else int result = parent.CompareTo (aktueller.Wert); if (Ergebnis> 0) // Wenn der übergeordnete Wert größer als der aktuelle Wert ist, // muss das aktuelle linke Kind ein linkes Kind des Elternteils sein. parent.Left = aktuell.Links; else if (Ergebnis < 0) // If parent value is less than current value, // make the current left child a right child of parent. parent.Right = current.Left; // Case 2: If current's right child has no left child, current's right child // replaces current. else if (current.Right.Left == null) current.Right.Left = current.Left; if (parent == null) _head = current.Right; else int result = parent.CompareTo(current.Value); if (result > 0) // Wenn der übergeordnete Wert größer als der aktuelle Wert ist, // muss das aktuelle rechte untergeordnete Element ein übergeordnetes untergeordnetes Element sein. parent.Left = current.Right; else if (Ergebnis < 0) // If parent value is less than current value, // make the current right child a right child of parent. parent.Right = current.Right; // Case 3: If current's right child has a left child, replace current with current's // right child's left-most child. else // Find the right's left-most child. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left != null) leftmostParent = leftmost; leftmost = leftmost.Left; // The parent's left subtree becomes the leftmost's right subtree. leftmostParent.Left = leftmost.Right; // Assign leftmost's left and right to current's left and right children. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) _head = leftmost; else int result = parent.CompareTo(current.Value); if (result > 0) // Wenn der übergeordnete Wert größer als der aktuelle Wert ist, // machen Sie das linke Kind des übergeordneten Elements ganz links. parent.Left = ganz links; else if (Ergebnis < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Verhalten | Gibt "true" zurück, wenn der Baum den angegebenen Wert enthält. Andernfalls wird falsch zurückgegeben. |
| Performance | O (log n) im Durchschnitt; O (n) im schlimmsten Fall. |
Enthält verschiebt sich zu FindWithParent, der einen einfachen Tree-Walking-Algorithmus ausführt, der vom Kopfknoten aus die folgenden Schritte ausführt:
Schon seit Enthält kehrt zurück Boolean, Der zurückgegebene Wert hängt davon ab, ob FindWithParent gibt eine Nicht-NULL zurück BinaryTreeNode (wahr) oder null (falsch).
Das FindWithParent Die Methode wird auch von der Remove-Methode verwendet. Der Out-Parameter Parent wird nicht von verwendet Enthält.
public bool Enthält (T-Wert) // Auf die Knotensuchfunktion zurückgreifen. BinaryTreeNode-übergeordnetes Element; return FindWithParent (value, out parent)! = null; /// /// Sucht den ersten Knoten mit dem angegebenen Wert und gibt ihn zurück. Wenn der Wert /// nicht gefunden wird, wird null zurückgegeben. Gibt auch den übergeordneten Knoten des gefundenen Knotens (oder null) /// zurück, der in Remove verwendet wird. /// private BinaryTreeNode FindWithParent (T-Wert, außerhalb des übergeordneten BinaryTreeNode-Objekts) // Versuchen Sie nun, Daten in der Baumstruktur zu finden. BinaryTreeNode current = _head; Elternteil = Null; // Während wir keine Übereinstimmung haben ... while (current! = Null) int result = current.CompareTo (value); if (Ergebnis> 0) // Wenn der Wert unter dem aktuellen Wert liegt, gehen Sie nach links. Elternteil = aktuell; Strom = Strom.Links; else if (Ergebnis < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Verhalten | Gibt die Anzahl der Werte in der Baumstruktur zurück (0, wenn leer). |
| Performance | O (1) |
Das Zählfeld wird um den Wert erhöht Hinzufügen Methode und dekrementiert durch die Löschen Methode.
public int Count get return _count;
| Verhalten | Entfernt alle Knoten aus der Baumstruktur. |
| Performance | O (1) |
public void Clear () _head = null; _count = 0;
Baumdurchquerungen sind Algorithmen, mit denen jeder Wert in der Baumstruktur in einer genau definierten Reihenfolge verarbeitet werden kann. Für jeden der besprochenen Algorithmen wird der folgende Baum als Probeneingang verwendet.
Die folgenden Beispiele akzeptieren ein Aktion Parameter. Dieser Parameter definiert die Aktion, die auf jeden Knoten angewendet wird, wenn er vom Durchlauf verarbeitet wird.
Der Reihenfolge-Abschnitt für jede Durchquerung zeigt die Reihenfolge an, in der der folgende Baum durchlaufen würde.
Der Musterbaum für die Ergebnisse der Durchquerungsreihenfolge | Verhalten | Führt die bereitgestellte Aktion für jeden Wert in der Vorbestellung durch (siehe folgende Beschreibung).. |
| Performance | Auf) |
| Auftrag | 4, 2, 1, 3, 5, 7, 6, 8 |
Die Vorbestellung durchläuft den aktuellen Knoten, bevor er nach links und dann nach rechts wechselt. Ab dem Wurzelknoten vier wird die Aktion mit dem Wert vier ausgeführt. Dann werden der linke Knoten und alle seine Kinder verarbeitet, gefolgt vom rechten Knoten und allen seinen Kindern.
Eine übliche Verwendung der Vorbestellung ist das Erstellen einer Kopie des Baums, die nicht nur dieselben Knotenwerte, sondern auch dieselbe Hierarchie enthält.
public void PreOrderTraversal (Aktionsaktion) PreOrderTraversal (Aktion, _head); private void PreOrderTraversal (Aktionsaktion, BinaryTreeNode-Knoten) if (node! = null) action (node.Value); PreOrderTraversal (Aktion, node.Left); PreOrderTraversal (Aktion, node.Right);
| Verhalten | Führt die bereitgestellte Aktion für jeden Wert in der Nachbestellung durch (siehe folgende Beschreibung).. |
| Performance | Auf) |
| Auftrag | 1, 3, 2, 6, 8, 7, 5, 4 |
Der Postorder-Durchlauf besucht das linke und rechte untergeordnete Element des Knotens rekursiv und führt dann die Aktion auf dem aktuellen Knoten aus, nachdem die untergeordneten Elemente abgeschlossen sind.
Postorder-Traversals werden häufig zum Löschen eines gesamten Baums verwendet, z. B. in Programmiersprachen, in denen jeder Knoten freigegeben werden muss, oder zum Löschen von Unterbäumen. Dies ist der Fall, da der Wurzelknoten zuletzt verarbeitet (gelöscht) wird und seine untergeordneten Elemente so verarbeitet werden, dass der Arbeitsaufwand minimiert wird Löschen Algorithmus muss durchführen.
public void PostOrderTraversal (Aktionsaktion) PostOrderTraversal (Aktion, _head); private void PostOrderTraversal (Aktionsaktion, BinaryTreeNode-Knoten) if (node! = null) PostOrderTraversal (action, node.Left); PostOrderTraversal (Aktion, node.Right); Aktion (node.Value);
| Verhalten | Führt die angegebene Aktion für jeden Wert in aus in Ordnung (siehe nachfolgende Beschreibung). |
| Performance | Auf) |
| Auftrag | 1, 2, 3, 4, 5, 6, 7, 8 |
Beim Durchlauf der Reihenfolge werden die Knoten in der Sortierreihenfolge verarbeitet. Im vorherigen Beispiel würden die Knoten in numerischer Reihenfolge vom kleinsten zum größten sortiert. Dazu wird der kleinste (am weitesten links liegende) Knoten gefunden und anschließend bearbeitet, bevor die größeren (rechten) Knoten verarbeitet werden.
Inorder-Traversierungen werden immer dann verwendet, wenn die Knoten in Sortierreihenfolge verarbeitet werden müssen.
Das folgende Beispiel zeigt zwei verschiedene Methoden zur Durchführung einer Inorder-Traversierung. Der erste implementiert einen rekursiven Ansatz, der einen Rückruf für jeden durchquerten Knoten durchführt. Der zweite entfernt die Rekursion mithilfe der Stack-Datenstruktur und gibt eine zurück IEnumerator direkte Aufzählung zulassen.
Öffentlich void InOrderTraversal (Aktionsaktion) InOrderTraversal (Aktion, _head); private void InOrderTraversal (Aktionsaktion, BinaryTreeNode-Knoten) if (node! = null) InOrderTraversal (action, node.Left); Aktion (node.Value); InOrderTraversal (Aktion, node.Right); public IEnumerator InOrderTraversal () // Dies ist ein nichtrekursiver Algorithmus, der einen Stack verwendet, um das Entfernen von // Rekursion zu demonstrieren. if (_head! = null) // Speichern Sie die Knoten, die wir in diesem Stack übersprungen haben (vermeidet Rekursion). Stapel> Stapel = neuer Stapel> (); BinaryTreeNode current = _head; // Wenn wir die Rekursion entfernen, müssen wir nachverfolgen, ob // wir als nächstes zum linken Knoten oder zum rechten Knoten gehen sollten. bool goLeftNext = true; // Beginne damit, den Kopf auf den Stapel zu drücken. Stack.Push (Strom); while (stack.Count> 0) // Wenn wir nach links gehen ... if (goLeftNext) // Schiebe alles außer dem ganz linken Knoten zum Stapel. // Nach diesem Block geben wir am weitesten links. while (current.Left! = null) stack.Push (current); Strom = Strom.Links; // Reihenfolge ist links-> Ertrag-> rechts. Rendite Rücklaufstrom.Wert; // Wenn wir es richtig machen können, dann mach es. if (current.Right! = null) current = current.Right; // Sobald wir einmal rechts gegangen sind, müssen wir // noch einmal nach links gehen. goLeftNext = true; else // Wenn wir nicht richtig gehen können, müssen wir den übergeordneten Knoten // abspringen, damit wir ihn verarbeiten können und dann zu seinem rechten Knoten gehen können. current = stack.Pop (); goLeftNext = false;
| Verhalten | Gibt einen Enumerator zurück, der mithilfe des InOrder-Traversalalgorithmus aufgelistet wird. |
| Performance | O (1), um den Enumerator zurückzugeben. Aufzählen aller Elemente ist O (n). |
public IEnumerator GetEnumerator () return InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return GetEnumerator ();
Accentsconagua