Implémentation d'un arbre binaire en Java

1. Introduction

Dans cet article, nous aborderons l'implémentation d'un arbre binaire en Java.

Pour les besoins de cet article, nous utiliserons un arbre binaire trié qui contiendra des valeurs int .

2. Arbre binaire

Un arbre binaire est une structure de données récursive où chaque nœud peut avoir 2 enfants au maximum.

Un type commun d'arbre binaire est un arbre de recherche binaire, dans lequel chaque nœud a une valeur supérieure ou égale aux valeurs de nœud dans le sous-arbre gauche, et inférieure ou égale aux valeurs de nœud dans le sous-arbre droit. arbre.

Voici une représentation visuelle rapide de ce type d'arbre binaire:

Pour l'implémentation, nous utiliserons une classe Node auxiliaire qui stockera les valeurs int et conservera une référence à chaque enfant:

class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }

Ensuite, ajoutons le nœud de départ de notre arbre, généralement appelé root:

public class BinaryTree { Node root; // ... }

3. Opérations communes

Voyons maintenant les opérations les plus courantes que nous pouvons effectuer sur un arbre binaire.

3.1. Insertion d'éléments

La première opération que nous allons couvrir est l'insertion de nouveaux nœuds.

Tout d'abord, nous devons trouver l'endroit où nous voulons ajouter un nouveau nœud afin de garder l'arbre trié . Nous suivrons ces règles à partir du nœud racine:

  • si la valeur du nouveau nœud est inférieure à celle du nœud courant, on passe à l'enfant de gauche
  • si la valeur du nouveau nœud est supérieure à celle du nœud courant, on passe au bon enfant
  • lorsque le nœud actuel est nul, nous avons atteint un nœud feuille et nous pouvons insérer le nouveau nœud à cette position

Tout d'abord, nous allons créer une méthode récursive pour faire l'insertion:

private Node addRecursive(Node current, int value) { if (current == null) { return new Node(value); } if (value  current.value) { current.right = addRecursive(current.right, value); } else { // value already exists return current; } return current; }

Ensuite, nous allons créer la méthode publique qui démarre la récursivité à partir du nœud racine :

public void add(int value) { root = addRecursive(root, value); }

Voyons maintenant comment nous pouvons utiliser cette méthode pour créer l'arborescence à partir de notre exemple:

private BinaryTree createBinaryTree() { BinaryTree bt = new BinaryTree(); bt.add(6); bt.add(4); bt.add(8); bt.add(3); bt.add(5); bt.add(7); bt.add(9); return bt; }

3.2. Trouver un élément

Ajoutons maintenant une méthode pour vérifier si l'arbre contient une valeur spécifique.

Comme précédemment, nous allons d'abord créer une méthode récursive qui parcourt l'arbre:

private boolean containsNodeRecursive(Node current, int value) { if (current == null) { return false; } if (value == current.value) { return true; } return value < current.value ? containsNodeRecursive(current.left, value) : containsNodeRecursive(current.right, value); }

Ici, nous recherchons la valeur en la comparant à la valeur du nœud actuel, puis continuons dans l'enfant gauche ou droit en fonction de cela.

Ensuite, créons la méthode publique qui commence à la racine :

public boolean containsNode(int value) { return containsNodeRecursive(root, value); }

Maintenant, créons un test simple pour vérifier que l'arbre contient vraiment les éléments insérés:

@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(6)); assertTrue(bt.containsNode(4)); assertFalse(bt.containsNode(1)); }

Tous les nœuds ajoutés doivent être contenus dans l'arborescence.

3.3. Supprimer un élément

Une autre opération courante est la suppression d'un nœud de l'arborescence.

Tout d'abord, nous devons trouver le nœud à supprimer de la même manière que nous l'avons fait auparavant:

private Node deleteRecursive(Node current, int value) { if (current == null) { return null; } if (value == current.value) { // Node to delete found // ... code to delete the node will go here } if (value < current.value) { current.left = deleteRecursive(current.left, value); return current; } current.right = deleteRecursive(current.right, value); return current; }

Une fois que nous avons trouvé le nœud à supprimer, il y a 3 cas principaux différents:

  • un nœud n'a pas d'enfants - c'est le cas le plus simple; il suffit de remplacer ce nœud par null dans son nœud parent
  • un nœud a exactement un enfant - dans le nœud parent, nous remplaçons ce nœud par son seul enfant.
  • un nœud a deux enfants - c'est le cas le plus complexe car il nécessite une réorganisation de l'arborescence

Voyons comment nous pouvons implémenter le premier cas lorsque le nœud est un nœud feuille:

if (current.left == null && current.right == null) { return null; }

Continuons maintenant avec le cas où le nœud a un enfant:

if (current.right == null) { return current.left; } if (current.left == null) { return current.right; }

Ici, nous retournons l' enfant non nul afin qu'il puisse être affecté au nœud parent.

Enfin, nous devons gérer le cas où le nœud a deux enfants.

Tout d'abord, nous devons trouver le nœud qui remplacera le nœud supprimé. Nous utiliserons le plus petit nœud du nœud à supprimer du sous-arbre droit:

private int findSmallestValue(Node root) { return root.left == null ? root.value : findSmallestValue(root.left); }

Ensuite, nous attribuons la plus petite valeur au nœud à supprimer et après cela, nous le supprimerons du sous-arbre droit:

int smallestValue = findSmallestValue(current.right); current.value = smallestValue; current.right = deleteRecursive(current.right, smallestValue); return current;

Enfin, créons la méthode publique qui démarre la suppression depuis la racine :

public void delete(int value) { root = deleteRecursive(root, value); }

Maintenant, vérifions que la suppression fonctionne comme prévu:

@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(9)); bt.delete(9); assertFalse(bt.containsNode(9)); }

4. Traverser l'arbre

Dans cette section, nous verrons différentes façons de parcourir un arbre, couvrant en détail les recherches en profondeur d'abord et en largeur d'abord.

Nous utiliserons le même arbre que nous avons utilisé auparavant et nous montrerons l'ordre de parcours pour chaque cas.

4.1. Recherche en profondeur d'abord

La recherche en profondeur d'abord est un type de parcours qui approfondit autant que possible chaque enfant avant d'explorer le frère suivant.

Il existe plusieurs façons d'effectuer une recherche en profondeur d'abord: dans l'ordre, en précommande et en post-ordre.

Le parcours dans l'ordre consiste à visiter d'abord le sous-arbre gauche, puis le nœud racine, et enfin le sous-arbre droit:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.value); traverseInOrder(node.right); } }

Si nous appelons cette méthode, la sortie de la console affichera le parcours dans l'ordre:

3 4 5 6 7 8 9

Le parcours de précommande visite d'abord le nœud racine, puis le sous-arbre gauche et enfin le sous-arbre droit:

public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Et vérifions le parcours de pré-commande dans la sortie de la console:

6 4 3 5 8 7 9

Le parcours post-ordre visite le sous-arbre gauche, le sous-arbre droit et le nœud racine à la fin:

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); } }

Voici les nœuds en post-ordre:

3 5 4 7 9 8 6

4.2. Recherche en largeur d'abord

Il s'agit d'un autre type de parcours courant qui visite tous les nœuds d'un niveau avant de passer au niveau suivant .

Ce type de parcours est également appelé ordre des niveaux et visite tous les niveaux de l'arbre en partant de la racine et de gauche à droite.

Pour l'implémentation, nous utiliserons une file d' attente pour maintenir les nœuds de chaque niveau dans l'ordre. Nous allons extraire chaque nœud de la liste, imprimer ses valeurs, puis ajouter ses enfants à la file d'attente:

public void traverseLevelOrder() { if (root == null) { return; } Queue nodes = new LinkedList(); nodes.add(root); while (!nodes.isEmpty()) { Node node = nodes.remove(); System.out.print(" " + node.value); if (node.left != null) { nodes.add(node.left); } if (node.right != null) { nodes.add(node.right); } } }

Dans ce cas, l'ordre des nœuds sera:

6 4 8 3 5 7 9

5. Conclusion

Dans cet article, nous avons vu comment implémenter un arbre binaire trié en Java et ses opérations les plus courantes.

Le code source complet des exemples est disponible à l'adresse over sur GitHub.