Baumdurchquerung Java

Java Tree Traversal ist als ein in der Programmiersprache Java implementierter Algorithmus definiert, der den Baum als Datenstruktur umfasst und die Grundlage des Besuchs aller Knoten des Baums durch die Implementierung des Algorithmus beinhaltet. Traversal bedeutet in der Datenstrukturterminologie der Informatik, dass alle Knoten in der Datenstruktur besucht werden müssen, um die größere Aufgabe zu erledigen. Die Komponenten eines Baums sind Wurzel- und untergeordnete Knoten, von denen einige an diesem bestimmten Knoten enden und als Blätter bezeichnet werden, während andere weitere Unterbäume bilden. In diesem Artikel werden wir die Implementierung der Baumdurchquerung in Java durchgehen und uns die verschiedenen Methoden ansehen, mit denen wir dasselbe erreichen können.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Syntax

Klassendeklaration in Java:

class <class name> {
// List the fields (variables) for the class
// Define the methods of the class to perform the specified operations
}

Eine Methode in Java definieren:

returnType <method name>() {
// Body of the method that constitutes the steps that will fulfill the assigned task
}

Deklarieren des Knotens in Java:

Node<{ Data Type }> <variable name> = new Node<{ Data Type }>(" <Value>");
Access the left of the node in Java:
<variable name>.left

Zugriff auf die rechte Seite des Knotens in Java:

<variable name>.right

Wie führt man eine Baumdurchquerung in Java durch?

Bevor wir beginnen, die verschiedenen Möglichkeiten zum Durchlaufen eines Baums in Java zu diskutieren, müssen wir zunächst wissen, wie ein Baum strukturiert ist, da dies eine der wesentlichen Komponenten ist, um den Baum als Klasse in Java zu erstellen. Der Baum hat Knoten und daher definieren wir eine Knotenklasse. Diese Klasse verfügt über Felder als Daten, die die Daten des Knotens darstellen, einen linken Zeiger, der auf die linke Seite des Knotens zeigt, und einen weiteren Zeiger, der auf die rechte Seite des Knotens zeigt. Alle diese Felder bilden die Node-Klasse. Unten sehen Sie schematisch, wie ein Baum aussieht:

Sobald wir die Baumklasse definiert haben, die die Knoten und den Zeiger bildet, ist es nun an der Zeit, einen Blick auf die drei Arten von Durchquerungen zu werfen, die in Java implementiert sind und von denen jede ihre eigene Durchquerungssignatur hat:

1 Durchlauf in der richtigen Reihenfolge

Diese Durchquerung ist so definiert, dass wir die Elemente des linken Teilbaums besuchen, gefolgt vom Knoten des Teilbaums und schließlich den rechten Teilbaum durchqueren. Der Pseudocode lautet wie folgt:

• Rufen Sie die Funktion rekursiv auf, indem Sie den linken Knoten übergeben, bis wir den Knoten als Null erreichen.
• Zeigen Sie die Daten an
• Rufen Sie die Funktion rekursiv auf, indem Sie den rechten Knoten übergeben, bis wir den Knoten als Null erreichen.

Der Durchlaufpfad des In-Order-Algorithmus ist: Knoten 1.1 → Knoten 1 → Knoten 1.2 → Wurzel → Knoten 2.

2. Traversal vorbestellen

Die Definition dieser Durchquerung besteht darin, die Elemente des Wurzelknotens zu besuchen, den linken Teilbaum zu durchqueren und schließlich den rechten Teilbaum zu durchqueren. Der Pseudocode lautet wie folgt:

• Durchqueren Sie zuerst den Wurzelknoten.
• Rufen Sie die Funktion rekursiv auf, indem Sie den linken Knoten übergeben, bis wir den Knoten als Null erreichen.
• Rufen Sie die Funktion rekursiv auf, indem Sie den rechten Knoten übergeben, bis wir den Knoten als Null erreichen.

Der Durchlaufpfad des Vorbestellungsalgorithmus ist: Wurzel→Knoten 1→Knoten 1.1→Knoten 1.2→Knoten 2.

3. Durchquerung nach der Bestellung

Diese Durchquerung ist so definiert, dass wir die Elemente des linken Teilbaums besuchen, gefolgt vom rechten Teilbaum, und dann schließlich den Knoten des Teilbaums durchlaufen, bis wir den Basisknoten erreichen. Der Pseudocode lautet wie folgt:

• Rufen Sie die Funktion rekursiv auf, indem Sie den linken Knoten übergeben, bis wir den Knoten als Null erreichen.
• Rufen Sie die Funktion rekursiv auf, indem Sie den rechten Knoten übergeben, bis wir den Knoten als Null erreichen.
• Zeigen Sie die Daten an

Der Durchlaufpfad des Post-Order-Algorithmus ist: Knoten 1.1 → Knoten 1.2 → Knoten 1 → Knoten 2 → Wurzel.

Beispiele für die Baumdurchquerung in Java

Im Folgenden finden Sie Beispiele für die Baumdurchquerung in Java:

Beispiel #1

Um die Reihenfolge mithilfe der Rekursion zu durchlaufen

Syntax

class NodeClass {
int value;
NodeClass left, right;
public NodeClass(int key) {
value = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void inOrderFunc(NodeClass node) {
if (node == null)
return;
inOrderFunc(node.left);
System.out.print(node.value + "->");
inOrderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("In Order traversal");
tree.inOrderFunc(tree.base);
}
}

Ausgabe:

Beispiel #2

Vorbestellungsdurchquerung mit Rekursion

Syntax

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void preorderFunc(NodeClass node) {
if (node == null)
return;
//First the node:
System.out.print(node.item + "->");
//Recursively look at the left side of the tree
preorderFunc(node.left);
//Recursively look at the right side of the tree
preorderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
// preorderFunc tree traversal
System.out.println("Preorder traversal: ");
tree.preorderFunc(tree.base);
}
}

Ausgabe:

Beispiel #3

Postorder-Traversal durch Rekursion

Syntax

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void postorderFunc(NodeClass node) {
if (node == null)
return;
postorderFunc(node.left);
postorderFunc(node.right);
System.out.print(node.item + "->");
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("Postorder traversal: ");
tree.postorderFunc(tree.base);
}
}

Ausgabe:

Fazit

In diesem Artikel wurden die verschiedenen Möglichkeiten zur Implementierung von Tree Traversal in Java sowie Beispiele aus der realen Welt vorgestellt. Den Lesern wird empfohlen, sich die Durchquerung anzusehen, indem sie dem Code weitere Knoten hinzufügen und die Durchquerungsergebnisse sehen!

Das obige ist der detaillierte Inhalt vonBaumdurchquerung Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!