二分探索木

(defun kv (key val)
  (cons key val))

(defun tree (val left right)
  (list val left right))

(defun tree->val (tree)
  (car tree))

(defun tree->left (tree)
  (cadr tree))

(defun tree->right (tree)
  (caddr tree))

(defun leafp (tree)
  (and (null (tree->left tree))
       (null (tree->right tree))))

(defun walk (tree)
  (cond ((null tree) nil)
        ((leafp tree)
         (format t "Visit: ~A~%" (tree->val tree)))
        (t
         (progn
           (walk (tree->left tree))
           (format t "Visit: ~A~%" (tree->val tree))
           (walk (tree->right tree))))))

(defun tree-search (val tree)
  (cond 
    ((null tree) nil)
    ((= val (tree->val tree))
     tree)
    (t
     (if (< val (tree->val tree))
       (tree-search val (tree->left tree))
       (tree-search val (tree->right tree))))))

(defun %tree-search (val tree)
  (let ((search nil))
    (loop while (not (null tree))
          do
          (if (= val (tree->val tree))
            (progn
              (setf search tree)
              (setf tree nil))
            (if (< val (tree->val tree))
              (setf tree (tree->left tree))
              (setf tree (tree->right tree)))))
    search))