<div>Dear Zeng,</div> <div> </div> <div>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 ...</div> <div> </div> <div> (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</div> <div>On 31/07/07, Marco Morazan <<a href="mailto:morazanm@gmail.com">morazanm@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">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 <<a href="mailto:zengfucen@gmail.com">zengfucen@gmail.com</a>> 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" <<a href="mailto:hdn...@gawab.com">hdn...@gawab.com</a>> > 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" <<a href="mailto:zengfu...@gmail.com">zengfu...@gmail.com</a>>: > > > > >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: > > >  <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a> > > > > _________________________________________________ > >   For list-related administrative tasks: > >  <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a> > > _________________________________________________ >  For list-related administrative tasks: >  <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a> > _________________________________________________ For list-related administrative tasks: <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a> </blockquote></div>