[plt-scheme] Excersise 14.2.3 - HtDP - Ordered list of binary tree nodes

Charlie, you're getting fantastic advice from Dave and Marco.

Here is one small supplement:

1. Take two or three examples for the complete function.

2. Arrange them like this:

BT |  Desired Output  | (node-left BT) | (inorder (node-left BT)) |  
(node-right BT) | (inorder (node-right BT)) | (node-ssn BT)
------------------------------------------------------------------------ 
----------------------------------------------------------
ex1|   ...            |  ..            |  ...                      
| ...             | ...                        |...
ex2|   ...            |  ..            |  ...                      
| ...             | ...                        |...
ex3|   ...            |  ..            |  ...                      
| ...             | ...                        |...

QUESTION: what tells you the entries for columns (inorder ..)?

3. Now try to guess how to combine these pieces so that you get the  
desired output. THIS and only this is where creativity comes in.

-- if you know of a Scheme function that does it all, great. Use IT! 
-- if not, specify a function that does the work for you. 

Oh and do listen to David and Marco -- Matthias









On Feb 20, 2009, at 3:54 PM, Charlie Turner wrote:

> The design recipes are fine, but it's the theory of ordering these
> nodes that I don't understand. I'm sorry for not posting my full
> Design Recipe,
>
> ;; inorder : BT -> list
> ;; to ouput the nodes of BT in an order of
> ;; left to right
>
> ;; Examples
>  ; (inorder false) -> empty
>
>
>  ; (inorder (make-node 1 'a false false)) -> (list 1)
>
>
>  ; (inorder (make-node 1 'a (make-node 2 'b false false) (make-node 3
> 'c false false false)))
> ;   -> (list 2 1 3)
>
>
>  ; (inorder (make-node 1 'a (make-node 2 'b (make-node 3 'c false  
> false)
> ;                                           (make-node 4 'd false  
> false))
> ;                           (make-node 5 'e (make-node 6 'f false  
> false)
> ;                                           (make-node 7 'g false  
> false))))
> ;   -> (list 3 2 4 1 6 5 7)
>
>
> ;; Template
> ; (define (inorder BT)
> ;   (cond
> ;     [(false? BT) ...]
> ;     [else (... (node-ssn BT) ...)
> ;           (... (inorder (node-left BT)) ...)
> ;           (... (inorder (node-right BT)) ...)]))
>
> Maybe the template is whats getting me into trouble. I struggle on
> occasion to decide where I should put the "natural recursions".
>
> Marco. Thank you for your input. I tried very hard to see how these
> examples exploded into the bigger picture, I just couldn't find a
> recursion that did what I wanted.
>
> David. I don't know what (inorder (node-left BT)) should do and I
> believe what Veer said has a lot of truth, in that I really just don't
> understand how to navigate these tree's (I haven't looked at the link
> as instructed!). I have a vision that I should keep on checking
> (node-left bt) until it becomes false, and them I'm at the start of
> the list I want. However, when I try to crawl back across the right, I
> just get stuck, and my list just end ups with one or two items from
> the lowest left "triangle".
>
> I just don't see a way of not getting stuck underneath the
> branches(?). From the data definition, it would appear to me that you
> have to stay at the top of the tree and do all the work, but I don't
> see how.
>
> Matthias. I hope my fuller definition above will reveal the problems
> in my understanding of this question.
>
> I really appreciate the input I'm receiving.
>
> -- 
> Charlie Turner.