1. Selon la définition inductive, il n'y a pas d'arbre vide. Mais les forêts (qui ne sont rien d'autre que des listes d'arbres) peuvent être vides. Par conséquent un objet de la classe Tree ne sera jamais null, mais un objet de la classe Forest si. Notons que les enfants d'une feuille d'un arbre sont effectivement une forêt vide.
  2. Pour un arbre :
    PO(n,F)  =  PO(F)   n
    Et une forêt :
    PO(є) = є    (liste vide),     PO(T,F) = PO(T)   PO(F)
  3. En théorie, nous avons pris quelques libertés avec les listes de sommets. En pratique, il faut concaténer nos amies les listes. La possibilité de forêt vide conduit à choisir une méthode statique pour les forêts. Ce n'est pas obligatoire, mais le code est alors particulièrement compact.
    class Tree { … List postOrder() { return List.concat(Forest.postOrder(children), new List (node,null)) ; } … } class Forest { … static List postOrder(Forest f) { return List.concat(first.postOrder(), postOrder(next)) ; } … }

    En fait, on peut se passer des concaténations en ajoutant un argument aux méthodes postOrder.

    class Tree { … List postOrder(List k) { return Forest.postOrder(children, new List(node,k)) ; } List postOrder() { return postOrder(null) ; } … } class Forest { … static List postOrder(Forest f, List k) { if (f == null) return k ; else return f.first.postOrder(postOrder(f.next,k)) ; } static List postOrder(Forest f) { return postOrder(f,null) ; } … }

    On notera l'utilisation de la surcharge pour définir, dans la même classe deux méthodes homonymes, mais distinctes.