6. Arbres binaires

On présente ici les arbres

6.1. Quelques exemples

Le premier exemple qui vient en tête est celui de l’organisation des fichiers sous les systèmes POSIX.

!tree -L 1 -d /

/
├── bin -> usr/bin
├── boot
├── builds
├── dev
├── etc
├── home
├── lib -> usr/lib
├── lib64 -> usr/lib64
├── logs-30-168067
├── media
├── mnt
├── opt
├── proc
├── root
├── run
├── sbin -> usr/sbin
├── scripts-30-168067
├── srv
├── sys
├── tmp
├── usr
└── var

23 directories

!tree -L 1 -d /usr

/usr
├── bin
├── games
├── include
├── lib
├── lib64
├── libexec
├── local
├── sbin
├── share
└── src

11 directories

On peut présenter des calculs comme un arbre :

Les arbres sont des cas particuliers des graphes :

Au delà de ces quelques exemples, on peut noter quelques points pertinents sur les arbres.

Un autre exemple d’arbre : https://stackoverflow.com/questions/42621190/display-this-decision-tree-with-graphviz

6.2. Définitions

• Le point de départ d’un arbre est la racine

• Les points nommés sont des nœuds

• Les arêtes entre deux nœuds sont des branches

• si un nœud ne comporte aucune arête qui «descende» vers un autre nœud, on dit que c’est une feuille

La profondeur d’une feuille (nœud) est le nombre de nœuds traversé de la racine jusqu’à la feuille (nœud). Par exemple, la profondeur de '^' dans le deuxième graphe est 3.

La hauteur d’un arbre est le maximum des profondeurs.

La taille d’un arbre est le nombre de ses nœuds.

Lorsque chaque nœud ne comporte qu’au plus deux branches, on dit que l’arbre est binaire.

6.3. Arbres binaires

On peut développer un arbre en considérant, pour chaque nœud autre que les feuilles qu’il se découpe en un sous arbre gauche et un sous arbre droit.

On peut ici considérer deux sous-arbres (à gauche en rouge et à droite en bleu) du nœud '-', qui sont ici des arbres binaires eux aussi. Cette propriété possède son importance, pour permettre des parcours récursifs sur les arbres.