;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                           TREE
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define node (make-record-type "node" '(label descendants)))
(define make-node (record-constructor node '(label descendants)))

(define node? (record-predicate node))

(define empty '())

(define (empty? node) (null? node))
(define (leaf? node) (empty? (descendants node)))

(define label (record-accessor node 'label))
(define descendants (record-accessor node 'descendants))

(define label! (record-modifier node 'label))
(define descendants! (record-modifier node 'descendants))

(define (show node)
  (display (format nil "~S " (label node))))

(define (preorder node)
  (cond ((not (empty? node))
	 (show node)
	 (do ((nodes (descendants node) (cdr nodes)))
	     ((null? nodes))
	   (preorder (car nodes))))))

(define (inorder node)
  (cond ((leaf? node) (show node))
	(else (inorder (car (descendants node)))
	      (show node)
	      (do ((nodes (cdr (descendants node)) (cdr nodes)))
	       ((null? nodes))
	       (inorder (car nodes))))))

(define (postorder node)
  (do ((nodes (descendants node) (cdr nodes)))
      ((null? nodes))
    (postorder (car nodes)))
  (show node))
;
; Example
; My family tree (my Dad as root, Denis Patrick Boyd Prosser)
;

(define n (make-node "DPBP" empty))
(define n.1 (make-node "Denis" empty))
(define n.1.1 (make-node "Julie" empty))
(define n.1.1.1 (make-node "Lee" empty))
(define n.1.2 (make-node "David" empty))
(define n.2 (make-node "Susie" empty))
(define n.2.1 (make-node "Sally" empty))
(define n.2.2 (make-node "Graeme" empty))
(define n.2.3 (make-node "Tom" empty))
(define n.3 (make-node "Patrick" empty))
(define n.3.1 (make-node "Zoe" empty))
(define n.4 (make-node "Stan" empty))
(define n.4.1 (make-node "Laura" empty))
(define n.4.2 (make-node "Martyn" empty))
(define n.4.3 (make-node "Katie" empty))
(define n.5 (make-node "Louise" empty))

(descendants! n (list n.1 n.2 n.3 n.4 n.5))
(descendants! n.1 (list n.1.1 n.1.2))
(descendants! n.1.1 (list n.1.1.1))
(descendants! n.2 (list n.2.1 n.2.2 n.2.3))
(descendants! n.3 (list n.3.1))
(descendants! n.4 (list n.4.1 n.4.2 n.4.3))


(define (make-tree l)
  (cond ((null? l) empty)                          ; (1)
	((list? l)                                 ; (2)
	 (let ((d (map make-tree (cdr l))))        ; (3)
	   (make-node (car l) d)))                 ; (4)
	(else (make-node l empty))))               ; (5)
;;;
;;; Given a list l, make a tree from it
;;; the first element of the list is the root
;;; the remaining elements of the list are the descendants
;;; ... where the descendants themselves can be lists
;;;
;;;
;;; (1) if the list is null deliver the empty node
;;; (2) we have a list l, where first element of list is
;;;     the label of a node, and the rest of the list (ie (cdr l))
;;;     is a list of descendants
;;; (3) d is the subtree rooted on the node with label (car l)
;;;     Or in other words, d is the list of descendants
;;; (4) Make the node with label and descendants
;;; (5) At this point l is not a list, and corresponds to the 
;;;     label of a leaf node, so make the leaf node
;;;

;;;
;;; For example, we can make an EXPRESSION tree x
;;; as follows

(define x (make-tree '(* (+ a b) (+ c d) (+ e f))))

;;;
;;; Now do traversals of this tree to see prefix and postfix notation
;;;