#-(and) " P61 (*) Count the leaves of a binary tree A leaf is a node with no successors. Write a predicate count-leaves/2 to count them. % count-leaves(T,N) :- the binary tree T has N leaves " (load "p54a") (load "p55") (load "p56") (load "p57") (defun binary-tree-leaf-p (node) (and (binary-tree-p node) (binary-tree-empty-p (binary-tree-left node)) (binary-tree-empty-p (binary-tree-right node)))) ;; Simple recursive solution: (defun count-leaves (tree) (cond ((binary-tree-empty-p tree) 0) ((binary-tree-leaf-p tree) 1) (t (+ (count-leaves (binary-tree-left tree)) (count-leaves (binary-tree-right tree)))))) ;; For very deep trees, here is a solution avoiding stack use: (defun count-leaves (tree) (if (binary-tree-empty-p tree) 0 (loop :with stack = (list tree) :for node = (pop stack) :then (if (binary-tree-empty-p (binary-tree-left node)) (pop stack) (binary-tree-left node)) :while node :unless (binary-tree-empty-p (binary-tree-right node)) :do (push (binary-tree-right node) stack) :when (binary-tree-leaf-p node) :count 1))) ;;;; THE END ;;;;