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.
PO(n,F) = PO(F) n |
PO(є) = є (liste vide), PO(T,F) = PO(T) PO(F) |
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.