Binärbaum ist eine gängige Datenstruktur in der Informatik und eine häufig verwendete Datenstruktur in der Java-Programmierung. In diesem Artikel wird die Binärbaumstruktur in Java ausführlich vorgestellt.
1. Was ist ein Binärbaum?
In der Informatik ist ein Binärbaum eine Baumstruktur, bei der jeder Knoten höchstens zwei untergeordnete Knoten hat. Unter diesen ist der linke untergeordnete Knoten kleiner als der übergeordnete Knoten und der rechte untergeordnete Knoten größer als der übergeordnete Knoten. In der Java-Programmierung werden Binärbäume häufig verwendet, um das Sortieren und Suchen darzustellen und die Effizienz der Datenabfrage zu verbessern.
2. Binärbaum-Implementierung in Java
In Java verwendet die Binärbaum-Implementierung normalerweise die Knotenklasse und die Binärbaumklasse. Die Knotenklasse stellt jeden Knoten im Binärbaum dar und kann Bytes und Attribute zum Speichern von Daten enthalten. Die Binärbaumklasse repräsentiert die gesamte Binärbaumdatenstruktur und verfügt über Funktionen wie das Einfügen von Knoten, das Löschen von Knoten und das Durchlaufen. Das Folgende ist eine einfache Implementierung eines Java-Binärbaums:
public class Node {
int key;
String value;
Node leftChild, rightChild;
public Node(int key, String value) {
this.key = key;
this.value = value;
}
}
public class BinaryTree {
Node root;
public void insert(int key, String value) {
Node newNode = new Node(key, value);
if (root == null) {
root = newNode;
} else {
Node current = root;
while (true) {
if (key < current.key) {
if (current.leftChild == null) {
current.leftChild = newNode;
return;
}
current = current.leftChild;
} else {
if (current.rightChild == null) {
current.rightChild = newNode;
return;
}
current = current.rightChild;
}
}
}
}
public Node find(int key) {
Node current = root;
while (current.key != key) {
if (key < current.key) {
current = current.leftChild;
} else {
current = current.rightChild;
}
if (current == null) {
return null;
}
}
return current;
}
public void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.leftChild);
System.out.println(node.key + ": " + node.value);
inOrderTraversal(node.rightChild);
}
}
public void preOrderTraversal(Node node) {
if (node != null) {
System.out.println(node.key + ": " + node.value);
preOrderTraversal(node.leftChild);
preOrderTraversal(node.rightChild);
}
}
public void postOrderTraversal(Node node) {
if (node != null) {
postOrderTraversal(node.leftChild);
postOrderTraversal(node.rightChild);
System.out.println(node.key + ": " + node.value);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(50, "John");
tree.insert(25, "Alice");
tree.insert(75, "Bob");
tree.insert(15, "Chris");
tree.insert(33, "Diana");
tree.insert(60, "Emily");
tree.insert(90, "Fred");
Node node = tree.find(33);
System.out.println("Find key: " + node.key + ", value: " + node.value);
System.out.println("In-order traversal:");
tree.inOrderTraversal(tree.root);
System.out.println("Pre-order traversal:");
tree.preOrderTraversal(tree.root);
System.out.println("Post-order traversal:");
tree.postOrderTraversal(tree.root);
}
}Der obige Binärbaumcode enthält drei Hauptfunktionen: Knoten einfügen, Knoten suchen und drei verschiedene Durchlaufmethoden. Der Einfügungsknoten verwendet eine While-Schleife, um Daten in der Reihenfolge des Binärbaums einzufügen. Der Suchknoten verwendet eine While-Schleife, um den Baum zu durchlaufen und nach Zieldaten zu suchen.
3. Binärbaum-Traversal-Methoden
Im obigen Java-Code implementiert das Programm drei verschiedene Binärbaum-Traversal-Methoden: In-Order-Traversal, Pre-Order-Traversal und Post-Order-Traversal. In diesem Abschnitt werden diese drei Traversierungsmethoden einzeln vorgestellt.
In-Order-Traversal durchläuft die Knoten im Baum in der Reihenfolge von klein nach groß. Im Java-Code verwendet die Implementierung der In-Order-Traversierung eine Rekursion: Rufen Sie für jeden Knoten zuerst seinen eigenen linken Knoten auf, drucken Sie dann die Knotendaten aus und rufen Sie schließlich seinen eigenen rechten Knoten auf. Auf diese Weise können alle Knoten im Baum in der Reihenfolge von klein nach groß durchlaufen werden.
Durchquerung vor der Bestellung durchläuft die Knoten im Baum in der Reihenfolge des übergeordneten Knotens, des linken Knotens und des rechten Knotens. Im Java-Code verwendet die Implementierung von Preorder Traversal auch Rekursion: Für jeden Knoten werden zuerst die Knotendaten gedruckt, dann der eigene linke Knoten aufgerufen und schließlich der eigene rechte Knoten aufgerufen. Auf diese Weise können alle Knoten im Baum in der Reihenfolge Elternknoten, linker Knoten und rechter Knoten durchlaufen werden.
Post-Order-Traversal durchläuft die Knoten im Baum in der Reihenfolge linker Knoten, rechter Knoten und übergeordneter Knoten. Im Java-Code verwendet die Implementierung von Post-Order-Traversal auch Rekursion: Rufen Sie für jeden Knoten zuerst seinen eigenen linken Knoten auf, dann seinen eigenen rechten Knoten und drucken Sie schließlich die Knotendaten aus. Auf diese Weise können alle Knoten im Baum in der Reihenfolge linker Knoten, rechter Knoten und übergeordneter Knoten durchlaufen werden.
4. Häufig verwendete Binärbaumalgorithmen
Der Binärbaum ist eine flexible und sehr nützliche Datenstruktur. In der Java-Programmierung wird häufig der Binärbaumalgorithmus verwendet. Die folgenden Binärbaumalgorithmen werden häufig verwendet:
Suchen ist eine der grundlegendsten Funktionen von Binärbäumen und wird auch häufig verwendet. Im Java-Code ist die Implementierung der Suche sehr einfach: Für jeden Knoten wird durch Vergleich der Größe des Knotenwerts und des Zielwerts Schicht für Schicht nach unten gesucht, bis der Zielwert gefunden oder der gesamte Baum durchlaufen wird.
Einfügung ist die Funktion zum Hinzufügen neuer Knoten zum Binärbaum. Gleichzeitig folgen die eingefügten neuen Knoten auch der Sortierreihenfolge des Binärbaums. Im Java-Code ist die Implementierung des Einfügens ebenfalls relativ einfach: Vergleichen Sie die Größe des einzufügenden Knotens mit der des aktuellen Knotens und fügen Sie einen neuen Knoten ein, wenn eine geeignete Position gefunden wird.
Löschen ist die Funktion zum Entfernen von Knoten aus einem Binärbaum. In Java-Code ist die Implementierung des Löschens komplizierter und erfordert mehr Überlegungen. Wenn der gelöschte Knoten keine untergeordneten Knoten hat, löschen Sie ihn einfach. Wenn es nur einen untergeordneten Knoten gibt, verschieben Sie den untergeordneten Knoten einfach an die Position des gelöschten Knotens. Wenn der gelöschte Knoten zwei untergeordnete Knoten hat, müssen Sie das Minimum finden Wert des rechten untergeordneten Knotens und ersetzen Sie ihn durch den Speicherort des gelöschten Knotens.
5. Zusammenfassung
In diesem Artikel wird die Binärbaum-Datenstruktur in Java ausführlich vorgestellt, einschließlich der Definition von Binärbäumen, der Implementierung von Knoten und Binärbaumklassen, drei verschiedenen Durchlaufmethoden und häufig verwendeten Binärbaumalgorithmen. Binärbäume sind eine weit verbreitete Datenstruktur, und Java bietet viele Funktionen und Klassenbibliotheken, die bei der Implementierung von Binärbäumen helfen. Wenn Sie in Java programmieren, können Kenntnisse in der Verwendung und Implementierung von Binärbäumen die Programmeffizienz und die Genauigkeit von Datenabfragen verbessern.
Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der binären Baumstruktur in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
