asked on

Binary trees in Scheme

I'm taking a computer class that uses Scheme and I'm having tons of trouble with the language. I've programmed with C++ and visual basic before so I understand the general idea of programming but I can never get the Scheme syntax right and a lot of the language is downright clunky. These are a few of the problems:

function 1
Develop the function inorder. It consumes a binary tree and produces a list of all the ssn numbers in the tree. The list contains the numbers in the left-to-right order

I don't know where to start with this one. I understand the physical aspect of the binary tree but not how to make one, much less put one in order.

I realize scheme is a icky old language, so if you need a point of reference, we're using an online book at
http://www.htdp.org/2003-09-26/

and I'm using the compiler Dr. scheme with the language beginning student with list abbreviations, if that's relevant at all. it's available at
http://download.plt-scheme.org/

;;class notes from for a binary tree. this is just an example of a binary tree, but I don't think it's applicable for this question. the example sort've helped me so I thought I'd post it
 
(define-struct bst (ssn left right))
 
(make-ssn 312045678)
(make-ssn 312012793)
(make-ssn 312459012)
(make-ssn 342147890)
 
(define (merge alon1 alon2)
  (cond
    [(empty? alon1) alon2]
    [(empty? alon2) alon1]
    [(< (first alon1) (first alon2))
     (cons (first alon1) (merge (rest alon1) alon2))]
    [else
     (cons (first alon2) (merge alon1 (rest alon2)))]))
 
(define (make-singles l)
  (cond
    [(empty? l) '()]
    [else (cons (list (first l)) (make-singles (rest l)))]))
 
(define (merge-neighbors alol)
  (cond
    [(empty? alol) '()]
    [(empty? (rest alol)) alol]
    [else (cons
           (merge (first alol) (second alol))
                  (merge-neighbors (cddr alol)))]))
 
(define (merge-sort l)
  (cond
    [(empty? l) '()]
    [else (repeat-merge (make-singles l))]))
 
(define (repeat-merge l)
  (cond [(empty? (rest l)) (first l)]
        [else (repeat-merge (merge-neighbors l))]))
 
(check-expect (merge-sort
               '(5 3 4 9 2)) '(2 3 4 5 9))

Open in new window

ASKER CERTIFIED SOLUTION

Markus Fischer

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

Markus Fischer

I'm playing a little with Scheme, and I rediscovered the 'append' function. Here is another version of 'makelist'.

This is fun!
(°v°)

Markus Fischer

oops!

; transform a binary tree into a list
(define (makelist l)
  (if (empty? l)
      empty
      (append
       (makelist (node-left l))
       (list (node-ssn l))
       (makelist (node-right l))
       )
      )
  )

Open in new window