tree-example.lisp

; https://gigadom.wordpress.com/2012/06/18/working-with-binary-trees-in-lisp/


(defstruct (binary-tree (:conc-name tree-))
  "A structure for binary trees.
Creates functions: make-binary-tree, tree-data, tree-left, tree-right, ..."
  data left right)

(defun add-item (data tree)
  "Add some data to a binary tree. Uses numeric comparisons: =, < and >."
  (cond ((null tree)
         (make-binary-tree :data data :left nil :right nil))
        ((= data (tree-data tree))
         tree)
        ((< data (tree-data tree))
         (setf (tree-left tree)  (add-item data (tree-left tree)))
         tree)
        ((> data (tree-data tree))
         (setf (tree-right tree) (add-item data (tree-right tree)))
         tree)))

(defun create-tree (elements &aux tree)
  "Create a tree and add the number elements. Returns the tree."
  (dolist (item elements tree)
    (setf tree (add-item item tree))))

(defun traverse-tree-in-order (tree fn)
  "Applies a function on each element, traversing the tree in-order."
  (when tree
    (traverse-tree-in-order (tree-left tree)  fn)
    (funcall fn (tree-data tree))
    (traverse-tree-in-order (tree-right tree) fn)))

(defun traverse-tree-pre-order (tree fn)
  "Applies a function on each data element, traversing the tree pre-order."
  (when tree
    (funcall fn (tree-data tree))
    (traverse-tree-in-order (tree-left tree)  fn)
    (traverse-tree-in-order (tree-right tree) fn)))

(defun traverse-tree-post-order (tree fn)
  "Applies a function on each data element, traversing the tree post-order."
  (when tree
    (traverse-tree-in-order (tree-left tree)  fn)
    (traverse-tree-in-order (tree-right tree) fn)
    (funcall fn (tree-data tree))))

(defun example ()
  "Creates a tree from numbers and traverse it in different ways."
  (let ((tree (create-tree (list 23 12 1 4 5 28 4 9 10 45 89))))
    (print 'in-order)
    (traverse-tree-in-order   tree #'print)
    (print 'pre-order)
    (traverse-tree-pre-order  tree #'print)
    (print 'post-order)
    (traverse-tree-post-order tree #'print)))