Un simple algorithme de construction d’un arbre6 min read

Je présente ici un algorithme très simple, en JavaScript, pour construire un arbre, en utilisant la programmation fonctionnelle.

Durant ce périple qu’est le développement de Naept, j’ai rencontré le besoin de représenter des données sous forme d’arbre. Pour donner un exemple de ce que j’appelle un arbre, pensez aux chapitres d’un document. Le document lui-même est le tronc de cet arbre, et tous les grands chapitres en sont les branches. Et chacune des branches est divisée en sous-chapitres, à leur tour éventuellement divisés en sous-sous-chapitres, et cætera…

Dans la base de données

Le plus simple pour enregistrer en base de données des objets qui constituent un arbre est de donner à chaque objet un lien vers son parent.

Chaque chapitre se retrouve donc avec un attribut parent_id. Et si la valeur de parent_id est null cela signifie que c’est un chapitre à la “racine” du document, un chapitre de haut niveau.

Avec ces informations, en théorie, nous sommes capables de construire un arbre. Ce que j’entends par là est d’obtenir une représentation logicielle de cet arbre :

Oui, je sais que mon arbre est étrange, il a poussé de gauche à droite plutôt que de bas en haut comme dans la nature. Mais vous comprenez l’idée !

Une approche par la programmation fonctionnelle

Je n’ai pas toujours été un développeur JavaScript. En réalité j’ai commencé ma carrière très bas, en terme d’abstraction logicielle. Langage assembleur, C, et même VHDL. J’ai commencé à m’intéresser à la programmation orientée objet avec le C++ il y a plus de dix ans et ça a longtemps été une grande passion. Mais avec le JavaScript, je me suis découvert un intérêt pour la programmation fonctionnelle, et je voulais l’utiliser aujourd’hui pour résoudre ce problème de construction d’arbre.

Revenons à nos moutons !

Chacun des objets Chapter a potentiellement des enfants (sous-chapitres) qui sont aussi des objets Chapter. Et chacun des ces enfants peut avoir lui-même des enfants, et ainsi de suite… En lisant ces lignes, peut-être voyez-vous émerger un motif ? La récursion !

J’adore la récursion. Ça fait partie des charmes de la programmation. Et pour une fois ce n’est pas inspiré de la nature. On ne trouve la récursion que dans la programmation. Elle ne peut pas être trouvée à l’état naturel (ou peut-être que le concept de fractales touche la récursion du doigt ?).

Donc, l’idée derrière notre algorithme sera d’utiliser la récursion et la programmation fonctionnelle afin de construire un arbre, sous-arbre par sous-arbre.

Codons un peu !

Tout d’abord, les chapitres. Représentons ses chapitres comme un tableau (array) d’objets, chaque objet étant un chapitre :

let chapters = [
  {
    id: 1,
    parent_id: null,
    text: 'Chapter 1',
  },
  {
    id: 2,
    parent_id: null,
    text: 'Chapter 2',
  },
  {
    id: 3,
    parent_id: null,
    text: 'Chapter 3',
  },
  {
    id: 4,
    parent_id: 1,
    text: 'Chapter 1.1',
  },
  {
    id: 5,
    parent_id: 1,
    text: 'Chapter 1.2',
  },
  {
    id: 6,
    parent_id: 1,
    text: 'Chapter 1.3',
  },
  {
    id: 7,
    parent_id: 3,
    text: 'Chapter 3.1',
  },
  {
    id: 8,
    parent_id: 3,
    text: 'Chapter 3.2',
  },
  {
    id: 9,
    parent_id: 5,
    text: 'Chapter 1.2.1',
  },
  {
    id: 10,
    parent_id: 5,
    text: 'Chapter 1.2.2',
  },
  {
    id: 11,
    parent_id: 7,
    text: 'Chapter 3.1.1',
  },
  {
    id: 12,
    parent_id: 7,
    text: 'Chapter 3.1.2',
  },
]

Le but est d’obtenir la structure suivante à la sortie de l’algorithme :

[
  {
    id: 1,
    parent_id: null,
    text: "Chapter 1",
    children: [
      {
        id: 4,
        parent_id: 1,
        text: "Chapter 1.1",
        children: []
      },
      {
        id: 5,
        parent_id: 1,
        text: "Chapter 1.2",
        children: [
          {
            id: 9,
            parent_id: 5,
            text: "Chapter 1.2.1",
            children: []
          },
          {
            id: 10,
            parent_id: 5,
            text: "Chapter 1.2.2",
            children: []
          }
        ]
      },
      {
        id: 6,
        parent_id: 1,
        text: "Chapter 1.3",
        children: []
      }
    ]
  },
  {
    id: 2,
    parent_id: null,
    text: "Chapter 2",
    children: []
  },
  {
    id: 3,
    parent_id: null,
    text: "Chapter 3",
    children: [
      {
        id: 7,
        parent_id: 3,
        text: "Chapter 3.1",
        children: [
          {
            id: 11,
            parent_id: 7,
            text: "Chapter 3.1.1",
            children: []
          },
          {
            id: 12,
            parent_id: 7,
            text: "Chapter 3.1.2",
            children: []
          }
        ]
      },
      {
        id: 8,
        parent_id: 3,
        text: "Chapter 3.2",
        children: []
      }
    ]
  }
]

Chaque nœud (chapitre) se voit donné un nouvel attribut children. Cet attribut est un tableau (array) qui contient les nœuds enfants (sous-chapitres).

Donc notre algorithme, avec comme données d’entrée le tableau contenant l’ensemble des nœuds et l’id du nœud parent, pourra :

1. filtrer le tableau pour n’en garder que les nœuds pour lesquels la valeur de parent_id est égale à l’id donné en paramètre;
2. renvoyer un tableau de ces nœuds modifiés. On ajoute à chaque nœud un attribut children, qui est un tableau (array) construit en utilisant une fonction qui, ayant pour données d’entrée le tableau contenant l’ensemble des nœuds et l’id du nœud parent, pourra :
   1. filtrer le tableau pour n’en garder que les nœuds pour lesquels la valeur de parent_id est égale à l’id donné en paramètre;
   2. renvoyer un tableau de ces nœuds modifiés. On ajoute à chaque nœud un attribut children, qui est un tableau (array) construit en utilisant une fonction qui, ayant pour données d’entrée le tableau contenant l’ensemble des nœuds et l’id du nœud parent, pourra :
      1. filtrer le tableau pour n’en garder que les nœuds pour lesquels la valeur de parent_id est égale à l’id donné en paramètre;
      2. renvoyer un tableau de ces nœuds modifiés. On ajoute à chaque nœud un attribut children, qui est un tableau (array) construit en utilisant une fonction qui, ayant pour données d’entrée le tableau contenant l’ensemble des nœuds et l’id du nœud parent, pourra :
         • … bref, vous avez compris…

Voilà ce que ça donne en JavaScript :

function makeTree(nodes, parentId) {
  return nodes
    .filter((node) => node.parent_id === parentId)
    .reduce(
      (tree, node) => [
        ...tree,
        {
          ...node,
          children: makeTree(nodes, node.id),
        },
      ],
      [],
    )
}

En utilisant la fonction reduce, qui est emblématique de la programmation fonctionnelle, on construit le tableau de nœuds d’un premier niveau, en ajoutant à chaque nœud de ce niveau un nouveau tableau children rempli en appelant la fonction makeTree.

---

Merci d’avoir lu cet article. J’espère qu’il vous a plu.

N’hésitez pas à le commenter et à partager votre méthode de construction d’arbre qui peut être différente.

Bonne journée !