[plt-scheme] Binary tree traversal, infix breadth first order

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Wed Nov 19 21:15:48 EST 2008

Let's see

On Nov 18, 2008, at 11:16 AM, Derk wrote:

> hi,
> I want to make a function that walks through a tree in infix order and
> in breath first order. I have made a function that uses depth first
> order, but breadth first is more difficult I think.
> The tree is represented in the following way: ’( (b) a ( ((f) d (g)) c
> (() e (h)) ) ). The function should then return ’(a b c d e f g h)

Let's see. From what you have told us so far, there is a  
straightforward solution:

;; Tree -> [Listof Symbol]
;; return elements of tree in infix order
(define (infix t)
     [(equal? '((b) a ( ((f) d (g)) c (() e (h)))) t) '(a b c d e f g  
     [else (error 'infix "tree expected, given ~e\n" t)]))

As you can see, I have added documentation and quasi-header like  
you'd do in other languages.

Is this enough?

> my code, not very much:
> (define (leaf? node)
>    (not (list? node))
> )
> (define (treewalk tree)
>    (cond
>       ((leaf? tree) tree)
>       .....
>    )
> )
> thanks,
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.