[plt-scheme] Re: Help: I want to travel a binary tree?

Dear Zeng,

I am also new to Scheme/LISP but what I found was that recursive algorithms
tend to make more sense in LISP than in C/C++/Java. This was my attemp at a
binary tree ...


(define null '())

; ---- node object ----
(define (make-node data)
  (cons data (cons null null)))
; ---- node object setters ----
(define (set-data! node data)  (set-car! node data))
(define (set-lnode! node lnode)(set-car! (cdr node) lnode))
(define (set-rnode! node rnode)(set-cdr! (cdr node) rnode))
; ---- node object getters ----
(define (get-data node) (car node))
(define (get-lnode node)(cadr node))
(define (get-rnode node)(cddr node))
; ---- node predicates ----
(define (leaf? node)
  (if (null? (and (get-lnode node)
                  (get-rnode node)))
      #t
      #f))

(define (make-btree)
  (let ((root null))
    ; ---- data inserter ----
    (define (insert! data)
      (define (inserter cur-node)
        (let ((new-node (make-node data)))
          (cond ((null? cur-node)
                 (set! root new-node))
                ((> data (get-data cur-node))
                 (if (null? (get-rnode cur-node))
                     (set-rnode! cur-node new-node)
                     (inserter (get-rnode cur-node))))
                ((< data (get-data cur-node))
                 (if (null? (get-lnode cur-node))
                     (set-lnode! cur-node new-node)
                     (inserter (get-lnode cur-node)))))))
      (inserter root))
    ; ---- traversals ----
    (define (pre-order-traversal)
      (define (traverse node)
        (if (not (null? node))
            (begin
              (display (get-data node))
              (traverse (get-lnode node))
              (traverse (get-rnode node)))
            (display "")))
      (traverse root))

    (define (post-order-traversal)
      (define (traverse node)
        (if (not (null? node))
            (begin
              (traverse (get-lnode node))
              (traverse (get-rnode node))
              (display (get-data node)))
            (display "")))
      (traverse root))

    (define (in-order-traversal)
      (define (traverse node)
        (if (not (null? node))
            (begin
              (traverse (get-lnode node))
              (display (get-data node))
              (traverse (get-rnode node)))
            (display "")))
      (traverse root))

    (define (dispatch op)
      (cond ((eq? op 'insert) insert!)
            ((eq? op 'root) root)
            ((eq? op 'pre-order-traversal) (pre-order-traversal))
            ((eq? op 'post-order-traversal) (post-order-traversal))
            ((eq? op 'in-order-traversal) (in-order-traversal))))
    ; object interface
    dispatch))

; export tree interface
(define (insert! tree data) ((tree 'insert) data))
(define (root tree) (tree 'root))
(define (pre-order-traversal tree) (tree 'pre-order-traversal))
(define (post-order-traversal tree) (tree 'post-order-traversal))
(define (in-order-traversal tree) (tree 'in-order-traversal))

.... and to find the depth of a tree I use this

(define (depth tree)
  (define (counter node)
    (cond ((null? node) 0)
          ((leaf? node) 1)
          (else (+ 1 (max (counter (get-lnode node))
                          (counter (get-rnode node)))))))
  (counter (root tree)))

which I translated from this Haskell code

depth :: Tree -> Int
depth Empty      = 0
depth (Leaf n)   = 1
depth (Node l r) = 1 + max (depth l) (depth r)

Hope it helps

Joshua Ewulo
On 31/07/07, Marco Morazan <morazanm at gmail.com> wrote:
>
> Dear Zeng,
>
> May I suggest that you define, precisely, what you mean by a tree
> first? This may be done by defining a BNF grammar for trees. Once you
> have a grammar for your trees, you can design code for performing your
> favorite traversal of trees.
>
> Let me get you started:
>
> <tree> --> empty
> <tree> --> ( ?????? )
>
> Marco
>
> On 7/31/07, Zeng Fucen <zengfucen at gmail.com> wrote:
> > I'm wrong!!!
> >
> > That's a binary tree,,,should be defined like this:((4 2 5) 1 (6 3 7))
> >
> >                1
> >                |
> >      ---------------------
> >      2                   3
> >      |                   |
> > ------------         ------------
> > 4         5          6         7
> >
> > I want result of the traversal is : 1 2 3 4 5 6 7  ,,, how to?
> >
> >
> > On 7月31日, 下午10时56分, "Hans Oesterholt-Dijkema" <hdn... at gawab.com>
> > wrote:
> > > Why don't you define a tree like this
> > >
> > > (1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ()))
> > >
> > > ?
> > >
> > > --Hans
> > >
> > > Op 31/7/2007 schreef "Zeng Fucen" <zengfu... at gmail.com>:
> > >
> > > >I'm a scheme novice,
> > >
> > > >I want to travel a binary tree, how to ? (depth first)
> > >
> > > >Thanks for your tips , first!
> > >
> > > >I define a tree like this:  (1 (2 4 5) (3 6 7))
> > >
> > > >_________________________________________________
> > > >  For list-related administrative tasks:
> > > >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> > >
> > > _________________________________________________
> > >   For list-related administrative tasks:
> > >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >
> > _________________________________________________
> >  For list-related administrative tasks:
> >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >
>
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20070731/f5efca76/attachment.html>