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

Dear Joshua,

Is there a need for all those assignment statements in your code?

What are the domain and range of and?

> (define (leaf? node)
>   (if (null? (and (get-lnode node)
>                   (get-rnode node)))
>       #t
>       #f))

How do you "and" two nodes? How do you apply null? to a boolean?

Furthermore, is the value of leaf? not the same as the value of the
null? in the body of the function? Why the use of an if statement?

I think things would be easier is you used define-struct to define
what a tree is.

Just some suggestions for thought.....

Marco


On 7/31/07, Joshua Ewulo <jewulo at gmail.com> wrote:
> 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
> >
> >
>
>