Parcours postfixe en Lisp

Description

Voici un exemple de code en Lisp pour parcourir un arbre en profondeur de manière postfixe.

Parcours d'un arbre d'arité arbitraire

Le code suivant ne fait pas de supposition de l'arité de l'arbre. On suppose l'existence d'une fonction subtrees qui, étant donné le sommet d'un arbre, renvoie une liste des sous arbres du sommet.

(defun prefix-tree-traversal (tree fun)
  (unless (null tree)
    (loop for subtree in (subtrees tree)
          do (prefix-tree-traversal subtree fun))
    (funcall fun tree)))

Parcours d'un arbre binaire

Lorsque l'arbre est binaire, on suppose plutôt l'existence de deux fonctions left-subtree et right-subtree de la manière suivante :

(defun prefix-tree-traversal (tree fun)
  (unless (null tree)
    (prefix-tree-traversal (left-subtree tree) fun)
    (prefix-tree-traversal (right-subtree tree) fun)
    (funcall fun tree)))