#-(and) " Binary Trees A binary tree is either empty or it is composed of a root element and two successors, which are binary trees themselves. [p67] In Lisp we represent the empty tree by 'nil' and the non-empty tree by the list (X L R), where X denotes the root node and L and R denote the left and right subtree, respectively. The example tree depicted opposite is therefore represented by the following list: (a (b (d nil nil) (e nil nil)) (c nil (f (g nil nil) nil))) Other examples are a binary tree that consists of a root node only: (a nil nil) or an empty binary tree: nil. You can check your predicates using these example trees. They are given as test cases in p54.lisp. P54A (*) Check whether a given term represents a binary tree Write a predicate istree which returns true if and only if its argument is a list representing a binary tree. Example: * (istree (a (b nil nil) nil)) T * (istree (a (b nil nil))) NIL " ;; Notice that there are a lot of ways to represent trees. ;; Therefore it important to use a functional abstraction, to avoid ;; writing code dependant on a specific representation. ;; ;; Also, in the following problems, references to prolog terms are not ;; translated to lisp, and terms for trees are given as: ;; ;; T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;; ;; We could translate this as having the symbol BINARY-TREE prefixing the ;; lists representing tree nodes: ;; ;; (BINARY-TREE a (BINARY-TREE b nil nil) (BINARY-TREE c nil (BINARY-TREE f nil))) ;; ;; This can be trivially implemented by adding the :NAMED option to defstruct, in which ;; case an implementation of BINARY-TREE-P is provided by destruct. (defstruct (binary-tree (:type list) :named) label left right) ;; This defstruct defines the following functional abstraction: ;; (make-binary-tree :label label :left left :right right) ;; (binary-tree-label node) ;; (binary-tree-left node) ;; (binary-tree-right node) ;; (copy-binary-tree node) ; shallow copy. ;; We add: (defun make-empty-binary-tree () 'nil) (defun binary-tree-empty-p (node) (null node)) (defun binary-tree-p (node) (or (binary-tree-empty-p node) (let ((nodes '())) (labels ((check-node (node) (and (listp node) (not (member node nodes)) ; check circular structures. (progn (push node nodes) t) (eql 3 (list-length node)) (or (null (second node)) (check-node (second node))) (or (null (third node)) (check-node (third node)))))) (check-node node))))) ;; We add: (defun binary-tree-from-sexp (sexp) sexp) ;; it would be good form to use it, so that if we change the ;; implementation of the above functional abstraction, we can still ;; use the tree sexps defined by for these problems: ;; (binary-tree-p (binary-tree-from-sexp '(a (b (d nil nil) (e nil nil)) (c nil nil)))) (defun binary-tree-height (tree) (if (binary-tree-empty-p tree) 0 (+ 1 (max (binary-tree-height (binary-tree-left tree)) (binary-tree-height (binary-tree-right tree)))))) (defparameter *tree-0* 'nil) (defparameter *tree-1* '(a nil nil)) (defparameter *tree-2* '(a (b (d nil nil) (e nil nil)) (c nil (f (g nil nil) nil)))) ;; Solution: (defun istree (object) (binary-tree-p object)) (assert (equal (mapcar (function istree) (list *tree-0* *tree-1* *tree-2* '(a b c) '(a (nil 1 2) (nil 3 4) d) '(a (nil nil nil) (nil nil nil) d))) '(T T T NIL NIL NIL))) ;;;; THE END ;;;;