Implémenter l'arborescence en Java

1. Implémenter un arbre à l’aide de la méthode de récursivité
2. Créer un arbre en Java à l’aide de la méthode générique et de ArrayList

Dans ce tutoriel, nous allons voir deux manières de faire une arborescence en Java. Une arborescence peut être utile de plusieurs manières, comme la création d’un répertoire de dossiers et de noms de fichiers.

Implémenter un arbre à l’aide de la méthode de récursivité

Dans cet exemple, nous créons un arbre binaire avec deux enfants au maximum, un à gauche et un autre à droite. Le nœud racine est le parent de tous les nœuds enfants. Chaque nœud stocke une valeur. Ci-dessous, nous prenons deux classes; l’un est Node représentant un nœud dans l’arbre, et l’autre est la classe JavaTree qui effectue des opérations sur les nœuds.

La classe Node a trois variables, la première est la valeur à stocker dans le nœud qui est de type de données int. Ensuite, nous prenons deux variables, pour les nœuds enfants left et right ; les deux variables sont de type Node. Nous créons un constructeur de la classe Node et initialisons la value à partir du paramètre ; les variables de gauche et de droite sont définies comme null.

Dans la classe JavaTree, nous prenons une variable de type Node et l’appelons root. Ensuite, nous créons une méthode traverseRecursionTree() qui prend un Node en paramètre, et à l’intérieur de la méthode, nous vérifions si le Node est null ; si ce n’est pas le cas, alors nous appelons la méthode traverseRecursionTree() à partir d’elle-même et passons la partie left de Node. Après cela, nous imprimons la value du Node et appelons à nouveau la méthode à partir de lui-même en passant la partie droite du noeud. Le processus d’appel de la fonction à partir d’elle-même est appelé récursion.

Dans la méthode main(), nous créons un objet de javaTree puis initialisons toutes les variables comme la racine, l’enfant gauche de la racine et l’enfant droit. Nous faisons également un enfant gauche de l’enfant de la racine. Nous imprimons l’arbre entier en utilisant javaTree.root qui contient tous les enfants.

class Node {
  int value;
  Node left;
  Node right;

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

public class JavaTree {
  Node root;

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

  public static void main(String[] args) {
    JavaTree javaTree = new JavaTree();

    javaTree.root = new Node(10);
    javaTree.root.left = new Node(6);
    javaTree.root.right = new Node(5);
    javaTree.root.left.left = new Node(3);

    System.out.print("Binary Tree: ");

    javaTree.traverseRecursionTree(javaTree.root);
  }
}

Production:

Binary Tree:  3 6 10 5

Créer un arbre en Java à l’aide de la méthode générique et de ArrayList

Dans la méthode précédente, nous étions limités à un seul type de données comme valeur dans les nœuds int. Dans ce programme, nous utilisons la méthode générique qui nous permet d’utiliser n’importe quel type de données de notre choix. Nous avons une classe Node<T>, ici <T> indique que nous pouvons utiliser n’importe quel type de données en tant que chaîne. Dans la classe, nous déclarons trois variables, d’abord la root qui est de type <T>, puis nous avons parent de type Node<T> et enfin une ArrayList de Node<T> nommée children.

Dans le constructeur de Node, nous prenons root de type T et le définissons sur la variable de classe root. Ensuite, nous initialisons l’ArrayList children. Maintenant, pour ajouter des enfants dans le parent, nous créons une fonction addChild() qui prend un enfant de type T. Dans la fonction addChild(), nous créons un objet de Node<T> - childNode et définissons le contexte de son parent comme le contexte de la classe actuelle en utilisant le mot-clé this. Ensuite, nous prenons le ArrayList children, ajoutons le childNode et renvoyons le childNode.

Nous avons plusieurs méthodes dans la classe Node<T> que nous pouvons utiliser pour effectuer des opérations comme la méthode getRoot() qui renvoie la root, la fonction isRoot() vérifie si le nœud actuel est un root. Nous créons une fonction getLevel() qui renvoie le niveau du nœud dans l’arbre. Enfin, on surcharge une méthode toString() pour retourner l’arbre entier s’il n’est pas nul.

Nous créons maintenant la classe Javatree qui a la méthode main(). Nous créons x et y de Node<String> dans la classe. Ici, nous utilisons String comme type. Dans les deux constructeurs, nous passons la racine de chaque arbre. On imprime la root en utilisant getRoot() puis on crée un objet de Node<String> nommé child1 et on appelle la méthode addChild() en utilisant l’objet x, ici on passe la valeur de child1 comme argument. Dans le bloc de child1, nous créons trois enfants de child1 en utilisant son objet et appelons addChild().

Nous utilisons le même processus pour créer un autre arbre avec le nom child2.

import java.util.ArrayList;

class Node<T> {
  private final T root;
  private Node<T> parent;
  private final ArrayList<Node<T>> children;

  public Node(T root) {
    this.root = root;
    children = new ArrayList<>();
  }

  public Node<T> addChild(T child) {
    Node<T> childNode = new Node<T>(child);
    childNode.parent = this;
    this.children.add(childNode);
    return childNode;
  }

  public T getRoot() {
    return root;
  }

  public boolean isRoot() {
    return parent == null;
  }

  public boolean isLeaf() {
    return children.size() == 0;
  }

  public int getLevel() {
    if (this.isRoot())
      return 0;
    else
      return parent.getLevel() + 1;
  }

  @Override
  public String toString() {
    return root != null ? root.toString() : "null";
  }
}

public class JavaTree {
  public static void main(String[] args) {
    Node<String> x = new Node<String>("parent1");
    Node<String> y = new Node<String>("parent2");

    System.out.println(x.getRoot());

    Node<String> child1 = x.addChild("child1");
    {
      Node<String> innerChild1 = child1.addChild("innerChild1OfChild1");
      Node<String> innerChild2 = child1.addChild("innerChild2OfChild1");
      Node<String> innerChild3 = child1.addChild("innerChild3OfChild1");

      System.out.println("-" + child1);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child1.getLevel());
      System.out.println("Level of innerChild2 in Child1: " + innerChild2.getLevel());
    }

    System.out.println();

    System.out.println(y.getRoot());

    Node<String> child2 = x.addChild("child2");
    {
      Node<String> innerChild1 = child2.addChild("innerChild2OfChild2");
      Node<String> innerChild2 = child2.addChild("innerChild3OfChild2");
      Node<String> innerChild3 = child2.addChild("innerChild4OfChild2");
      {
        Node<String> innerChild4 = innerChild3.addChild("innerChild4OfChild3");
        System.out.println(innerChild4.getLevel());
        System.out.println("\nIs inner Child4 Leaf? " + innerChild4.isLeaf());
      }

      System.out.println("-" + child2);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child2.getLevel());
      System.out.println("Level of innerChild2 in Child2: " + innerChild2.getLevel());
    }
  }
}

Production:

parent1
-child1
--innerChild1OfChild1
--innerChild2OfChild1
--innerChild3OfChild1
Level of child1: 1
Level of innerChild2 in Child1: 2

parent2
3

Is inner Child4 Leaf? true
-child2
--innerChild2OfChild2
--innerChild3OfChild2
--innerChild4OfChild2
Level of child1: 1
Level of innerChild2 in Child2: 2