On trouve diverses options selon la façon dont on choisit de stocker les liens entre nœuds.

Un arbre est composé de nœuds. Chaque nœud peut contenir des données et avoir des enfants. Dans le cas des arbres binaires, il ne peut y avoir que deux enfants mais en général il peut y en avoir plus.

Cas où chaque nœud contient les attributs a, b, c, … Les nœuds peuvent avoir plus de 2 enfants.

node = {
    "a":...,
    "b":...,
    "c":...,
    etc
    "children": [tableaux contenant les enfants]
}

Une variante.

node = {
    "data": {"a":..., etc },
    "children": [ ... ]
}

Et dans un cas avec seulement 2 enfants :

node = {
    "data": {"a":..., etc },
    "child_left": ...,
    "child_right": ...
}

Cette option est possible mais pas tellement lisible :

node = [
    valeur de a,
    valeur de b,
    valeur de c,
    ...,
    [tableaux contenant les enfants]
]

C'est la meilleure solution car elle permet de faire ce que l'on veut.

class Node:
    def __init__(self, a, b, c,...):
        self.a = a
        self.b = b
        self.c = c
        children = []
    def add_child(c):
        children.append(c)
        # il faut faire attention avec l'enfant ajouté :
        # un nœud ne peut pas être enfant de lui-même,
        # un nœud ne peut pas être son propre ancêtre !

Certains langages non orientés objet comme C permettent de définir des types de données personnalisables : des struct. On définira :

typedef struct Node Node; // un peu verbeux. Permet de prévenir qu'il y aura un type nommé Node
struct Node
{
    int a;
    int b;
    int c;
    Node *left_child; // pointe vers l'enfant gauche
    Node *right_child; // pointe vers l'enfant droit
};

Une grande différence entre un struct et un objet est que le struct ne peut contenir de méthode. Les fonctions devront donc être à l'extérieur du struct

#include <stdbool.h>
#include <stdlib.h>

bool has_left_child(Node *n) {
    if (n == NULL){
        exit(EXIT_FAILURE);
    }
    if (n->left_child != NULL){
        return true;
    } else {
        return false;
    }
}

Dans le cas d'un arbre binaire, il est possible de numéroter toutes les positions de l'arbre et donc de placer le nœuds dans un tableau. Un exemple en est donné dans cet exercice.

Cela ne fonctionnera que pour un arbre binaire. De plus, si l'arbre n'est pas complet, il faudra réserver en mémoire un tableau avec beaucoup de cases vides.

'''
exemple : on prévoit de la place pour un arbre complet de 10 étages, soit 1023
la première case contient la taille de l'arbre. Cela ne sert pas à grand chose
mais le système de numérotation des noeuds est plus simple si numérote à partir de 1
donc la case 0 du tableau est laissée inutilisée.
'''
arbre = [None]*1024
arbre[0] = 0

def has_left_child(arbre, i_noeud):
    '''
    arbre: tableau représentant l'arbre
    i_noeud: indice du noeud recherché
    renvoie True si le noeud a un enfant gauche
    '''
    assert i_noeud < arbre[0] and arbre[i_noeud] != None, "noeud inexistant"
    i_gauche = 2*i_noeud
    return i_gauche < arbre[0] and arbre[i_gauche] != None

def get_value(arbre, i_noeud):
    '''
    arbre: tableau représentant l'arbre
    i_noeud: indice du noeud recherché
    renvoie la valeur du noeud
    '''
    assert i_noeud < arbre[0] and arbre[i_noeud] != None, "noeud inexistant"
    return arbre[i_noeud]

# etc

Avec cette approche, comme vous le voyez, on est dans la situation des tableaux : on doit en permanence bien distinguer l'indice d'un nœud et sa valeur, c'est à dire la position et le contenu.

Au contraire, quand on a défini un arbre avec une classe, quand on désigne un objet Node, on désigne le nœud lui même. C'est plus facile à lire.

D'un point de vue théorique, le concept d'arbre se distingue des nœuds. Mais une fois qu'on a défini les relations que les nœuds doivent avoir les uns avec les autres, on sait tout ce qu'il y a à savoir : après tout, un arbre est juste un ensemble de nœuds, si on sait ce qu'est un nœud, on sait ce qu'est un arbre !

Il sera donc fréquent que l'on se contente d'une classe Node.

Pourtant, il peut être utile de définir une classe Tree qui gère l'ensemble des nœuds. Voici quelques arguments :

• pour définir des fonctions qui concernent l'ensemble de l'arbre. C'est plus lisible de les placer dans la définition de celui qui gère l'arbre dans son entier que dans la définition des nœuds eux-mêmes ;
• pour prendre en charge des arbres vides : si tout le fonctionnement est défini dans les nœuds et qu'on n'a pas de nœud, comment faire ?
• quand il s'agit de modifier le nœud racine. Un exemple ci-dessous :

# on suppose un arbre binaire qui contient des lettres
# je ne donne pas la définition des classes, les noms des méthodes sont explictes
r = Node('R') # racine
a = Node('A')
b = Node('B')
c = Node('C')
r.set_left_child(a)
r.set_right_child(b)
a.set_left_child(c)

On peut donc juger que cela suffit.On atteint l'arbre par sa racine r. Donc, avec cette approche, r désigne à la fois la racine et l'arbre lui-même. Voyons quel problème cela pose :

def fonction_qui_modifie_racine(r, valeur):
    '''
    ajoute un noeud au-dessus de la racine.
    r devient l'enfant gauche de ce noeud.
    '''
    n = Node(valeur)
    n.set_left_child(r)

Suite à l'exécution de fonction_qui_modifie_racine(r, 10) par exemple, r n'est plus la racine, c'est juste un nœud parmi d'autres dans l'arbre.