Traversée en ordre Java

Le parcours ordonné d'un arbre est la manière de visiter chacun des nœuds de l'arbre dans l'ordre où le nœud le plus à gauche est visité en premier, puis la racine et enfin le nœud le plus à droite. Le parcours est la manière dont nous visitons chacun des éléments de valeurs de la structure de données donnée. Chacune des structures de données linéaires n'a qu'une seule façon de parcourir ses éléments. Les structures de données linéaires sont des tableaux, des piles, des files d'attente et des listes chaînées. Mais dans le cas d'une structure de données non linéaire comme un arbre, il existe plusieurs manières et ordres possibles dans lesquels les nœuds peuvent être visités. Il existe trois méthodes de traversée des commandes de base, de précommande et de post-commande.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Dans cet article, nous étudierons la méthode de parcours dans l'ordre et son fonctionnement dans l'arbre binaire. Nous verrons également l'un des exemples de la façon dont le parcours d'ordre peut être implémenté à l'aide du langage de programmation C.

Fonctionnement de la traversée en ordre

L'algorithme ou les étapes utilisées lors de la traversée d'un arbre à l'aide du parcours dans l'ordre sont répertoriés ci-dessous –

• La première chose à faire est de parcourir tous les nœuds du sous-arbre gauche de la manière où le premier nœud gauche est visité puis le nœud principal puis le nœud droit.
• Maintenant, visitez le nœud racine de l'arbre.
• Il est temps de visiter le sous-arbre droit après la traversée du sous-arbre gauche et la visite de la racine.

Considérons un arbre dans lequel les nœuds sont comme indiqué sur la figure –

Dans l'exemple d'arbre donné ci-dessus, le parcours commencera d'abord à partir du nœud ou de la feuille le plus à gauche de la plante qui est 3, puis nous traverserons son parent principal immédiat qui est 6. Après cela, nous irons pour rechercher son bon enfant, mais, comme nous pouvons le voir, il n'y a pas d'enfant droit des 6 nœuds, nous allons donc maintenant visiter le parent immédiat du 6 nœud qui est 12, et de cette manière nous poursuivrons notre voyage de traversée. Enfin, l'ordre de parcours résultant sera celui indiqué ci-dessous –
3 -> 6 -> 12 -> 13 -> 14 -> 15 -> 20 -> 17 -> 23 -> 27

Applications du parcours dans l'ordre

Le parcours inorder est principalement utilisé dans les arbres de recherche binaires. L'algorithme inversé de parcours dans l'ordre est utilisé pour obtenir un ordre non croissant des valeurs des nœuds. Dans le cas où nous souhaitons que les nœuds soient récupérés dans un format non décroissant, il n'est pas nécessaire d'utiliser une variante du parcours dans l'ordre. Nous pouvons utiliser la même méthode de parcours dans l'ordre décrite ci-dessus pour obtenir des valeurs non décroissantes de l'arbre binaire.

Implémentation du parcours Inorder en Java

Pour comprendre le flux du parcours inorder et son implémentation dans le langage de programmation Java, vous devez connaître les méthodes, classes et concepts d'objet Java. Le programme suivant utilise un appel récursif à la méthode de parcours dans l'ordre d'abord pour le sous-arbre du côté gauche, puis en visitant le nœud racine, puis pour le sous-arbre du côté droit. Lors de la visite de chacun des nœuds du parcours, le programme s'assure d'imprimer la valeur du même nœud visité. Par conséquent, nous pouvons voir dans le résultat comment tous les nœuds sont visités et dans quel ordre ils sont visités.

Exemple

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;
}
}

Sortie :

Le résultat de l'exécution du programme ci-dessus est le suivant :

Conclusion

Le parcours dans l'ordre est l'une des méthodes de parcours en profondeur dans laquelle tous les nœuds sont parcourus de la manière où le nœud gauche est traversé, puis la racine, puis le sous-arbre droit. La feuille la plus à gauche de l'arbre est le premier nœud à être visité tandis que la feuille la plus à droite est la dernière à être parcourue dans le parcours dans l'ordre. La méthode de parcours dans l'ordre est largement utilisée dans les arbres de recherche binaires pour obtenir un ordre de valeurs non décroissant ou non croissant. L'implémentation Java peut être effectuée soit au format récursif, soit au format itératif. La méthode de récursivité est utilisée ici pour l'implémentation où la même méthode est appelée encore et encore pour implémenter le parcours dans l'ordre.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!