Inorder-Traversierung eines Baums ist die Art und Weise, jeden Knoten des Baums in der Reihenfolge zu besuchen, dass der Knoten ganz links zuerst besucht wird, dann die Wurzel und zuletzt der Knoten ganz rechts. Durchlaufen ist die Art und Weise, wie wir jedes der Werteelemente der gegebenen Datenstruktur besuchen. Jede der linearen Datenstrukturen hat nur eine Möglichkeit, ihre Elemente zu durchlaufen. Lineare Datenstrukturen sind Arrays, Stapel, Warteschlangen und verknüpfte Listen. Bei einer nichtlinearen Datenstruktur wie einem Baum gibt es jedoch mehrere Möglichkeiten und Reihenfolgen, in denen die Knoten besucht werden können. Es gibt drei grundlegende Order-Traversal-Methoden: Inorder, Preorder und Postorder.
Starten Sie Ihren kostenlosen Softwareentwicklungskurs
Webentwicklung, Programmiersprachen, Softwaretests und andere
In diesem Artikel untersuchen wir die In-Order-Traversal-Methode und wie sie im Binärbaum funktioniert. Wir werden auch eines der Beispiele sehen, wie die Reihenfolge-Traversierung mit der Programmiersprache C implementiert werden kann.
Der Algorithmus oder die Schritte, die beim Durchlaufen eines Baums mithilfe der Inorder-Traversierung verwendet werden, sind unten aufgeführt –
Stellen Sie sich einen Baum vor, in dem die Knoten wie in der Abbildung dargestellt sind –
Im oben gegebenen Beispiel des Baums beginnt die Durchquerung zunächst am Knoten oder Blatt der Pflanze ganz links, also 3, und dann durchqueren wir ihren unmittelbaren Hauptelternteil, der 6 ist. Danach geht es weiter für die Suche nach seinem richtigen Kind, aber wie wir sehen können, gibt es kein richtiges Kind der 6 Knoten, daher werden wir nun den unmittelbaren Elternteil des 6. Knotens besuchen, der 12 ist, und auf diese Weise unsere Reise des Durchquerens fortsetzen. Schließlich wird die resultierende Durchlaufreihenfolge wie unten gezeigt aussehen –
3 -> 6 -> 12 -> 13 -> 14 -> 15 -> 20 -> 17 -> 23 -> 27
Der Inorder-Traversal wird hauptsächlich in binären Suchbäumen verwendet. Der umgekehrte Algorithmus der Inorder-Traversierung wird verwendet, um eine nicht aufsteigende Reihenfolge der Knotenwerte zu erhalten. Wenn wir möchten, dass die Knoten im nicht abnehmenden Format abgerufen werden, ist es nicht erforderlich, eine Variation der Inorder-Traversierung zu verwenden. Wir können dieselbe oben beschriebene Inorder-Traversal-Methode verwenden, um nicht abnehmende Werte des Binärbaums zu erhalten.
Um den Ablauf des Inorder-Traversal und seine Implementierung in der Programmiersprache Java zu verstehen, müssen Sie Java-Methoden und -Klassen sowie Objektkonzepte kennen. Das folgende Programm verwendet einen rekursiven Aufruf der Methode der Inorder-Traversierung, zunächst für den Teilbaum auf der linken Seite, danach den Besuch des Wurzelknotens und dann für den Teilbaum auf der rechten Seite. Beim Besuch jedes Knotens im Durchlauf stellt das Programm sicher, dass der Wert desselben besuchten Knotens gedruckt wird. Daher können wir in der Ausgabe sehen, wie alle Knoten besucht werden und in welcher Reihenfolge sie besucht werden.
Code:
import java.util.Stack;
/*
* Implementation of inorder traversal of the binary tree.
* Inorder traversal involves travelling to he left most leaf or node of the
* tree and then the root node of the tree. The last node to be traversed is
* the rightmost node or leaf of the binary tree.
*
* input:
* 43
* / \
* 23 32
* / \ \
* 13 32 95
* / / \
* 3 49 67
*
* Resulting output: 3 13 23 32 43 32 95 49 67
*/
public class Main {
public static void main(String[] args) throws Exception {
// Firstly, we will create the binary tree as displayed in the comments
BinaryTreeToTraverse bt = BinaryTreeToTraverse.create();
// With the help of recursion that means calling the same function again and again,
// we will do inorder traversal of the binary tree
System.out
.println("Using recursion, display all the nodes of the binary tree that are resulted\n by following inorder traversal :- ");
bt.inOrderTraversal();
}
}
class BinaryTreeToTraverse {
static class binaryTreeNode {
String data;
binaryTreeNode leftNode, rightNode;
binaryTreeNode(String value) {
this.data = value;
leftNode = rightNode = null;
}
}
// Root node of the considered binary tree
binaryTreeNode rootNode;
/**
* Use the inorder algorithm for traversing through the nodes in binary tree
*/
public void inOrderTraversal() {
inOrderTraversal(rootNode);
}
private void inOrderTraversal(binaryTreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.leftNode);
System.out.printf("%s ", node.data);
inOrderTraversal(node.rightNode);
}
/**
* Consider the sample data to test the order in which the nodes are traversed in Java program
*
* @return a sample binary binaryTree for testing
*/
public static BinaryTreeToTraverse create() {
BinaryTreeToTraverse binaryTree = new BinaryTreeToTraverse();
binaryTreeNode rootNode = new binaryTreeNode("43");
binaryTree.rootNode = rootNode;
binaryTree.rootNode.leftNode = new binaryTreeNode("23");
binaryTree.rootNode.leftNode.leftNode = new binaryTreeNode("13");
binaryTree.rootNode.leftNode.leftNode.leftNode = new binaryTreeNode("3");
binaryTree.rootNode.leftNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode.rightNode = new binaryTreeNode("95");
binaryTree.rootNode.leftNode.rightNode.leftNode = new binaryTreeNode("49");
binaryTree.rootNode.leftNode.rightNode.rightNode = new binaryTreeNode("67");
return binaryTree;
}
}Ausgabe:
Die Ausgabe der Ausführung des obigen Programms ist wie folgt:
Die Inorder-Traversierung ist eine der Tiefen-zuerst-Traversierungsmethoden, bei der alle Knoten auf die Art und Weise durchlaufen werden, bei der zuerst der linke Knoten und dann die Wurzel und dann der rechte Teilbaum durchlaufen werden. Das Blatt ganz links im Baum ist der erste Knoten, der besucht wird, während das Blatt ganz rechts das letzte ist, das bei der Inorder-Traversierung durchlaufen wird. Die Inorder-Traversing-Methode wird häufig in binären Suchbäumen verwendet, um nicht absteigende oder nicht aufsteigende Reihenfolge von Werten zu erhalten. Die Java-Implementierung kann entweder im rekursiven Format oder im iterativen Format erfolgen. Die Rekursionsmethode wird hier zur Implementierung verwendet, wobei dieselbe Methode immer wieder aufgerufen wird, um die Inorder-Traversierung zu implementieren.
Das obige ist der detaillierte Inhalt vonInorder Traversal Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
