(defclass node () ((%data :initarg :data :accessor data) (%left :initarg :left :accessor left) (%right :initarg :right :accessor right))) (defun make-node (data left right) (make-instance 'node :data data :left left :right right)) (defmethod print-object ((node node) stream) (print-unreadable-object (node stream :type t) (format stream "~s ~s ~s" (data node) (left node) (right node)))) (define-condition tree-condition (condition) ()) (define-condition object-already-in-tree (error tree-condition) ((%object :initarg :object :reader object)) (:report (lambda (condition stream) (format stream "the object ~s is already in the tree" (object condition))))) (defun insert (obj tree &key (key #'identity) (< #'<)) (cond ((null tree) (make-node obj nil nil)) ((funcall < (funcall key obj) (funcall key (data tree))) (setf (left tree) (insert obj (left tree) :key key :< <)) tree) ((funcall < (funcall key (data tree)) (funcall key obj)) (setf (right tree) (insert obj (right tree) :key key :< <)) tree) (t (with-simple-restart (replace "replace the object" ) (error (make-condition 'object-already-in-tree :object (data tree)))) (setf (data tree) obj) tree)))