#-(and) "
P72 (*) Construct the bottom-up order sequence of the tree nodes
Write a predicate bottom-up(Tree,Seq) which constructs the
bottom-up sequence of the nodes of the multiway tree Tree. Seq
should be a Prolog list. What happens if you run your predicate
backwords?
"
;; "Bottom-up order sequence of tree nodes" is an idiosyncrasy
;; (google for it, there's no definition!).
;; Perhaps it means postfix order.
;; Right, it's the postfix order. The prolog solution gives:
;; ?- bottom_up(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])]),L).
;; L = [g, f, c, d, e, b, a].
(defun multiway-tree-postfix-order (tree)
"
Returns a list of node labels in the postfix order.
"
(reduce (function nconc)
(multiway-tree-children tree)
:key (function multiway-tree-postfix-order)
:initial-value (list (multiway-tree-label tree))
:from-end t))
;; :from-end is needed so that the initial-value is placed on the right.
;; It also proves beneficial since then the lists are walked only once per level.
;; (multiway-tree-postfix-order (parse-multiway-tree-string "AFG^^C^BD^E^^^"))
;; --> (G F C D E B A)
(defun bottom-up (tree)
(multiway-tree-postfix-order tree))
;;;; THE END ;;;;