Inverser un arbre binaire en Java

1. Vue d'ensemble

L'inversion d'un arbre binaire est l'un des problèmes que l'on pourrait nous demander de résoudre lors d'un entretien technique .

Dans ce rapide didacticiel, nous verrons différentes façons de résoudre ce problème.

2. Arbre binaire

Un arbre binaire est une structure de données dans laquelle chaque élément a au plus deux enfants , appelés enfant gauche et enfant droit. L'élément supérieur de l'arbre est le nœud racine, tandis que les enfants sont les nœuds intérieurs .

Cependant, si un nœud n'a pas d'enfant, on l'appelle une feuille.

Cela dit, créons notre objet qui représente un nœud:

public class TreeNode { private int value; private TreeNode rightChild; private TreeNode leftChild; // Getters and setters }

Ensuite, créons notre arbre que nous utiliserons dans nos exemples:

 TreeNode leaf1 = new TreeNode(1); TreeNode leaf2 = new TreeNode(3); TreeNode leaf3 = new TreeNode(6); TreeNode leaf4 = new TreeNode(9); TreeNode nodeRight = new TreeNode(7, leaf3, leaf4); TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2); TreeNode root = new TreeNode(4, nodeLeft, nodeRight); 

Dans la méthode précédente, nous avons créé la structure suivante:

En inversant l'arbre de gauche à droite, nous finirons par avoir la structure suivante:

3. Inverser l'arbre binaire

3.1. Méthode récursive

Dans le premier exemple, nous utiliserons la récursivité pour inverser l'arborescence .

Tout d'abord, nous appellerons notre méthode en utilisant la racine de l'arbre, puis nous l'appliquerons respectivement sur les enfants gauche et droit jusqu'à ce que nous atteignions les feuilles de l'arbre:

public void reverseRecursive(TreeNode treeNode) { if(treeNode == null) { return; } TreeNode temp = treeNode.getLeftChild(); treeNode.setLeftChild(treeNode.getRightChild()); treeNode.setRightChild(temp); reverseRecursive(treeNode.getLeftChild()); reverseRecursive(treeNode.getRightChild()); }

3.2. Méthode itérative

Dans le deuxième exemple, nous inverserons l'arborescence en utilisant une approche itérative. Pour cela, nous allons utiliser une LinkedList , que nous initialisons à la racine de notre arbre .

Ensuite, pour chaque nœud que nous interrogeons dans la liste, nous ajoutons ses enfants à cette liste avant de les permuter .

Nous continuons d'ajouter et de supprimer de la LinkedList jusqu'à ce que nous atteignions les feuilles de l'arbre:

public void reverseIterative(TreeNode treeNode) { List queue = new LinkedList(); if(treeNode != null) { queue.add(treeNode); } while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(node.getLeftChild() != null){ queue.add(node.getLeftChild()); } if(node.getRightChild() != null){ queue.add(node.getRightChild()); } TreeNode temp = node.getLeftChild(); node.setLeftChild(node.getRightChild()); node.setRightChild(temp); } }

4. Conclusion

Dans cet article rapide, nous avons exploré les deux façons d'inverser un arbre binaire. Nous avons commencé par utiliser une méthode récursive pour l'inverser. Ensuite, nous avons fini par utiliser une méthode itérative pour obtenir le même résultat.

Le code source complet de ces exemples et cas de test unitaires peut être trouvé à l'adresse over sur Github.