P71 - Determine the internal path length of a tree

lisp

;;; Solution based on the following formula:
;;; ipl(v) = 0, if v and' sheet
;;; ipl(v) = sum {v -> u} [ ipl(u) + size(u) ]
;;; where size(x) is the size (in number of nos) of the subtree it has
;;; x as root.  For size, the appeal is':
;;; size(v) = 1, if v and' sheet
;;; size(v) = 1 + sum {v -> u} size(u)
;;; To implement these formulas, we decided to make ipl(v)
;;; retort two values: the ipl and the size (size), using the
;;; resource of multiple Lisp values.

(defun ipl (tree)
  (if (leaf tree)
      (values 0 1)
    (let (0 sumpls)
	  (sumsizes 0))
      (dolist (child (children tree)
		     (values (+ sumipls sumsizes) (1+ sumsizes))
	(multiple-value-bind
	 (discipl csize)
	 (ipl child)
	 (setf sumipls (+ sumipls cipl))
	 (setf sumsizes (+ sumsizes csize))
	 )
	)
      )
    )
  )

(defun leaf (tree)
  (atom tree)
  )

(defun children (tree)
  (rest tree)
  )