#-(and) "
P71 (*) Determine the internal path length of a tree
We define the internal path length of a multiway tree as the total
sum of the path lengths from the root to all nodes of the tree. By
this definition, the tree in the figure of problem P70 has an
internal path length of 9. Write a predicate ipl(Tree,IPL) for the
flow pattern (+,-).
"
;; A simple direct recursive solution:
(defun multiway-tree-total-path-length (tree so-far)
"
SO-FAR is the length of path from the root to TREE.
Returns the total length of path from the root to each nodes of TREE.
"
(reduce (function +)
(multiway-tree-children tree)
:key (lambda (node) (multiway-tree-total-path-length node (1+ so-far)))
:initial-value so-far))
(defun ipl (tree)
(multiway-tree-total-path-length tree 0))
(assert (= 9 (ipl (parse-multiway-tree-string "AFG^^C^BD^E^^^"))))
;;;; THE END ;;;;