Parcours préfixe en Lisp

Description

Voici un exemple de code en Lisp pour parcourir un arbre en profondeur de manière préfixe.

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)
    (funcall fun tree)
    (loop for subtree in (subtrees tree)
          do (prefix-tree-traversal subtree fun))))

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)
    (funcall fun tree)
    (prefix-tree-traversal (left-subtree tree) fun)
    (prefix-tree-traversal (right-subtree tree) fun)))