[plt-scheme] Binary tree Traversals
I've written some scheme code for traversing binary trees. Here is my code:
(define (atom? x)
(not (pair? x)))
;;Functions to manipulate a binary tree
(define (leaf? node) (atom? node))
(define (left node) (cadr node))
(define (right node) (caddr node))
(define (label node) (if (leaf? node) node (car node)))
;; Preorder Traversal
(define (pre-order node)
(cons
(label node)
(if (leaf? node)
'()
(append
(pre-order (left node))
(pre-order (right node))))))
;;Post-order traversal
(define (post-order node)
(list
(if (leaf? node) '()
(append
(post-order (left node))
(post-order (right node))))
(label node)))
;;in-order traversal
(define (in-order node)
(if (leaf? node) (label node)
(list
(in-order (left node))
(cons
(label node)
(in-order (right node))))))
(define tree '(A (B C D)(E (F G H) I)))
(pre-order tree)
(post-order tree)
(in-order tree)
Though they do work, the post and in-order traversals output as deeply
nested lists and not a simple flat list. Can someone how to get
results in flattened lists (without running a separate flatten routine
on the returned results)?
Thanks
Basu
--
The ByteBaker :
http://www.bytebaker.com