[plt-scheme] Binary tree Traversals

From: Shrutarshi Basu (technorapture at gmail.com)
Date: Thu Oct 9 21:40:01 EDT 2008

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


Posted on the users mailing list.