Traversée d'arbre Java

La traversée de l'arbre Java est définie comme un algorithme implémenté dans le langage de programmation Java, qui comprend l'arbre en tant que structure de données et intègre les principes fondamentaux de la visite de tous les nœuds de l'arbre grâce à la mise en œuvre de l'algorithme. La traversée dans la terminologie de la structure de données informatique indique que tous les nœuds de la structure de données doivent être visités afin d'accomplir la tâche la plus importante à accomplir. Les composants d'un arbre sont des nœuds racine et enfants, dont certains se terminent à ce nœud particulier et sont nommés feuilles et les autres créent davantage de sous-arbres. Dans cet article, nous passerons en revue l'implémentation de la traversée d'arbres en Java et examinerons les différentes méthodes grâce auxquelles nous pouvons y parvenir.

Commencez votre cours de développement de logiciels libres

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

Syntaxe

Déclaration de classe en Java :

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

Définir une méthode en Java :

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

Déclarer le nœud en Java :

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

Accédez au droit du nœud en Java :

<variable name>.right

Comment effectuer une traversée d'arbre en Java ?

Avant de commencer à discuter des différentes manières de parcourir un arbre en Java, nous devons d'abord savoir comment un arbre est structuré car c'est l'un des composants essentiels pour construire l'arbre en tant que classe en Java. L'arbre a des nœuds et nous définissons donc une classe de nœuds. Cette classe aura des champs comme données qui représentent les données du nœud, un pointeur gauche qui pointe vers la gauche du nœud et un autre pointeur qui pointe vers la droite du nœud. Tous ces champs constituent la classe Node. Vous trouverez ci-dessous un schéma de l'apparence d'un arbre :

Une fois que nous avons défini la classe d'arbre qui constitue les nœuds et le pointeur, il est maintenant temps de se pencher sur les 3 types de parcours qui sont implémentés en Java et chacun d'entre eux ayant sa propre signature de parcours :

1 Traversée dans l'ordre

La façon dont ce parcours est défini est que nous visitons les éléments du sous-arbre de gauche, suivis du nœud du sous-arbre, puis parcourons enfin le sous-arbre de droite. Le pseudocode est le suivant :

• Appelez récursivement la fonction en passant le nœud gauche jusqu'à ce que nous atteignions le nœud comme nul.
• Afficher les données
• Appelez récursivement la fonction en passant le bon nœud jusqu'à ce que nous atteignions le nœud comme nul.

Le chemin de parcours de l'algorithme In-order sera : Nœud 1.1 → Nœud 1 → Nœud 1.2 → Racine → Nœud 2.

2. Précommander Traversal

La façon dont ce parcours est défini est de visiter les éléments du nœud racine, de parcourir le sous-arbre de gauche, puis enfin de parcourir le sous-arbre de droite. Le pseudocode est le suivant :

• Traversez d'abord le nœud racine.
• Appelez récursivement la fonction en passant le nœud gauche jusqu'à ce que nous atteignions le nœud comme nul.
• Appelez récursivement la fonction en passant le bon nœud jusqu'à ce que nous atteignions le nœud comme nul.

Le chemin de parcours de l'algorithme de pré-commande sera : Racine → Nœud 1 → Nœud 1.1 → Nœud 1.2 → Nœud 2.

3. Traversée post-commande

La façon dont ce parcours est défini est que nous visitons les éléments du sous-arbre de gauche, suivis du sous-arbre de droite, puis traversons enfin le nœud du sous-arbre jusqu'à atteindre le nœud de base. Le pseudocode est le suivant :

• Appelez récursivement la fonction en passant le nœud gauche jusqu'à ce que nous atteignions le nœud comme nul.
• Appelez récursivement la fonction en passant le bon nœud jusqu'à ce que nous atteignions le nœud comme nul.
• Afficher les données

Le chemin de parcours de l'algorithme de post-commande sera : Nœud 1.1→Nœud 1.2→ Nœud 1→Nœud 2→ Racine.

Exemples de traversée d'arbre Java

Vous trouverez ci-dessous des exemples de traversée d'arbres Java :

Exemple n°1

Parcours dans l'ordre par récursivité

Syntaxe

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

Sortie :

Exemple n°2

Parcours de précommande par récursivité

Syntaxe

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

Sortie :

Exemple #3

Parcours de post-commande par récursivité

Syntaxe

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

Sortie :

Conclusion

Cet article a examiné toutes les différentes manières d'implémenter la traversée d'arbres en Java, ainsi que des exemples tirés du monde réel. Les lecteurs sont encouragés à examiner le parcours en ajoutant plus de nœuds dans le code et en voyant les résultats du parcours !

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!