Das Konzept des binären Baumes
Ein binärer Baum ist ein endlicher Satz von N (n> = 0) Knoten. Dieser Satz ist entweder ein leerer Satz (leerer binärer Baum) oder besteht aus einem Wurzelknoten und zwei binären Bäumen, die sich nicht gegenseitig überschneiden, die als Wurzelknoten bzw. der rechte Teilbaum bezeichnet werden.
Eigenschaften von binären Bäumen
Jeder Knoten hat höchstens zwei Unterbäume, so dass es keine Knoten mit einem Grad von mehr als 2 im binären Baum gibt. Jeder Knoten im binären Baum ist ein Objekt, und jeder Datenknoten hat drei Zeiger, nämlich Hinweise auf das Eltern-, das linke Kind und das rechte Kind. Jeder Knoten ist über einen Zeiger miteinander verbunden. Die Beziehung zwischen den vernetzten Zeigern ist eine Vater-Sohn-Beziehung.
Definition von binären Baumknoten
Der binäre Baumknoten ist wie folgt definiert:
Die Codekopie lautet wie folgt:
Struct BinaryTreenode
{
int m_nvalue;
BinaryTreenode* m_pleft;
BinaryTreenode* m_pright;
};
Fünf grundlegende Formen von Binärbäumen
Leerer binärer Baum
Es gibt nur einen Wurzelknoten
Der Stammknoten hat nur den linken Subtree
Der Stammknoten hat nur den richtigen Teilbaum
Der Stammknoten hat sowohl einen linken als auch einen rechten Teilbaum
Es gibt nur zwei Fälle für normale Bäume mit drei Knoten: zwei oder drei. Da der binäre Baum jedoch links und rechts unterscheiden muss, wird er sich in die folgenden fünf Formen entwickeln:
Spezialer binärer Baum
Schräger Baum
Wie in der zweiten und dritten kleinen Bildern im vorletzten Unterbild oben gezeigt.
Voller binärer Baum
Wenn in einem binären Baum alle Zweigknoten links und rechte Unterbäume haben und alle Blätter auf derselben Schicht befinden, wird ein solcher binärer Baum als vollständiger binärer Baum bezeichnet. Wie in der Abbildung unten gezeigt:
Kompletter binärer Baum
Ein vollständig binärer Baum bedeutet, dass die letzte Schicht links voll ist, die rechte Seite voll ist oder nicht und der Rest der Schichten voll ist. Ein binärer Baum mit einer Tiefe von k und einer Reihe von Knoten von 2^k - 1 ist ein vollständiger binärer Baum (vollständiger binärer Baum). Es ist ein Baum mit einer Tiefe von K und ohne Raum.
Die Eigenschaften eines völlig binären Baumes sind:
Blattknoten können nur in den niedrigsten zwei Schichten auftreten.
Das niedrigste Blatt muss in einer kontinuierlichen Position links konzentriert sein.
In der vorletzten Schicht müssen sie auf der rechten Seite in kontinuierlichen Positionen sein.
Wenn der Knotengrad 1 ist, hat der Knoten nur das linke Kind.
Für binäre Bäume mit demselben Knotenbaum hat der komplette binäre Baum die kleinste Tiefe.
Hinweis: Ein vollständiger binärer Baum muss ein völlig binärer Baum sein, aber ein vollständig binärer Baum ist möglicherweise kein vollständiger binärer Baum.
Der Algorithmus lautet wie folgt:
Die Codekopie lautet wie folgt:
bool is_complete (Baum *root)
{
Warteschlange Q;
Baum *ptr;
// Prioritätsquelle mit Breite durchführen (hierarchische Durchfahrten) und auch Nullknoten in die Warteschlange geben
Q.Push (Wurzel);
while ((ptr = q.pop ())! = null)
{
Q.Push (ptr-> links);
Q.push (ptr-> rechts);
}
// Bestimmen Sie, ob noch nicht zugegriffen wurden, auf die noch nicht zugegriffen wurden
While (! Q.is_eMpty ())
{
ptr = q.pop ();
// Wenn nicht zugegriffene Knoten nicht zugegriffen werden, hat der Baum eine Hohlraum und ist ein nicht vollständiger Binärbaum.
if (null! = ptr)
{
false zurückgeben;
}
}
zurückkehren;
}
Eigenschaften von Binärbäumen
Eigenschaft 1 des Binärbaum
Eigenschaft 2 von Binärbaum: Binärbaum mit Tiefe k hat höchstens 2^k-1-Knoten (k> = 1)
Sequentielle Lagerstruktur von Binärbäumen
Die sequentielle Speicherstruktur eines Binärbaums besteht darin, ein eindimensionales Array zu verwenden, um jeden Knoten im binären Baum zu speichern, und die Speicherstelle der Knoten kann die logische Beziehung zwischen Knoten widerspiegeln.
Binärverbindungsliste
Da die sequentielle Speichermethode nicht sehr anwendbar ist, müssen wir die Kettenspeicherstruktur berücksichtigen. Laut internationaler Praxis wird im Allgemeinen eine Kettenspeicherstruktur angewendet.
Jeder Knoten eines binären Baums hat höchstens zwei Kinder, daher ist es eine natürliche Idee, ein Datenfeld und zwei Zeigerfelder dafür zu entwerfen. Wir nennen eine so verknüpfte Liste eine binäre verknüpfte Liste.
Durchqueren von Binärbäumen
Das Durchqueren von Binärbaum bezieht sich auf den Zugriff auf alle Knoten im binären Baum in einer bestimmten Reihenfolge vom Wurzelknoten, so dass auf jeden Knoten nur einmal zugegriffen wird.
Es gibt drei Möglichkeiten, binäre Bäume wie folgt zu durchqueren:
(1) Vorbestellungsquellen (DLR), zuerst auf den Wurzelknoten zugreifen, dann den linken Subtree durchqueren und schließlich den rechten Subtree durchqueren. Abkürzte Wurzel - links - rechts.
. Abgekürzte Anmerkung: linksgerecht.
(3) Nach der Bestellung durch-Ordnung (LRD), zuerst den linken Unterbaum durchqueren, dann den rechten Subtree durchqueren und schließlich auf den Stammknoten zugreifen. Abgekürzte links-rechts-Root.
Vorverstärker -Traversal:
Wenn der binäre Baum leer ist, kehrt die leere Operation zurück. Andernfalls zuerst zuerst auf den Stammknoten zugreifen, dann den linken Subtree in der vorherigen Reihenfolge durchqueren und dann den rechten Subtree in der vorherigen Reihenfolge durchqueren.
Die Reihenfolge des Traversals lautet: Abdhiejcfkg
Die Codekopie lautet wie folgt:
// präzise Traversal
Funktion vorbestellt (Knoten) {
if (! node == null) {
putstr (node.show ()+ "");
vorbestellt (node.left);
Vorbestellung (Knoten.Right);
}
}
In-Ordnung-Traversal:
Wenn der Baum leer ist, kehrt die leere Operation zurück, ansonsten startet er vom Stammknoten (beachten Sie, dass der Stammknoten nicht zuerst zugegriffen wird), und auf den linken Unterbaum des Stammknotens wird in der mittleren Reihenfolge durchquert, dann wird auf den Wurzelknoten auf den rechten Teilbaum in der mittleren Reihenfolge durchquert.
Die Reihenfolge des Traversals lautet: hdibejafkcg
Die Codekopie lautet wie folgt:
// Verwenden Sie eine rekursive Methode, um die Durchführung mittlerer Ordnung zu implementieren
Funktion entschlüsselt (Knoten) {
if (! (node == null)) {
in der Regel (node.left); // Zuerst zum linken Subtree hinzufügen
putstr (node.show ()+ ""); // wieder zum Stammknoten hinzufügen
in der Order (Knoten.Right); // Letzten Zugriff auf den richtigen Subtree
}
}
Nach der Bestellung Traversal:
Wenn der Baum leer ist, kehrt die leere Operation zurück. Andernfalls werden die linken und rechten Unterbaume von links nach rechts überquert, um auf die linken und rechten Unterbälde zuzugreifen und schließlich auf den Wurzelknoten zuzugreifen.
Die Reihenfolge des Traversals lautet: hidjebkfgca
Die Codekopie lautet wie folgt:
// Nachbestellung durch-Order
Funktion Postorder (Knoten) {
if (! node == null) {
postorder (node.left);
Postorder (Knoten.Right);
putstr (node.show ()+ "");
}
}
Binärer Suchbaum implementieren
Der binäre Suchbaum (BST) besteht aus Knoten, sodass wir ein Knotenknotenobjekt wie folgt definieren:
Die Codekopie lautet wie folgt:
Funktionsknoten (Daten, links, rechts) {
this.data = Daten;
this.left = links; // Link des linken Knotens speichern
this.Right = rechts;
this.show = show;
}
Funktion show () {
Geben Sie dies zurück.
}
Finden Sie maximale und minimale Werte
Das Finden der minimalen und maximalen Werte auf der BST ist sehr einfach, da die kleineren Werte immer auf dem linken Kinderknoten liegen und nach dem Mindestwert auf der BST suchen, durchqueren Sie einfach den linken Kinderbaum, bis der letzte Knoten gefunden wird
Finden Sie den Mindestwert
Die Codekopie lautet wie folgt:
Funktion getmin () {
var curr Current = this.root;
while (! (current.left == null)) {
current = current.left;
}
Return Current.data;
}
Diese Methode durchquert einzeln entlang des linken Teilbaums von BST, bis sie zum linken linken Knoten von BST durchquert, was definiert ist:
Die Codekopie lautet wie folgt:
current.left = null;
Zu diesem Zeitpunkt ist der auf dem aktuelle Knoten gespeicherte Wert der Mindestwert
Finden Sie den Maximalwert
Das Finden des Maximalwerts auf BST erfordert nur das Durchqueren des rechten Unterbaums, bis der letzte Knoten gefunden wurde, und der auf diesem Knoten gespeicherte Wert ist der Maximalwert.
Die Codekopie lautet wie folgt:
Funktion getMax () {
var curr Current = this.root;
while (! (current.right == null)) {
Strom = Strom.Right;
}
Return Current.data;
}