CODEWITHSUNDEEP
treeschemebinary-treeracketmit-scheme
Alan
Alan

Reputation: 21

Using scheme to build a tree and print node of the in_order traversal

I understand the algorithm but cannot get the code work using scheme. I'm building a binary search tree. A node is a pair of (key value). in java, the code works fine:

public void inOrder(BinaryNode n) {
    if (n != null) {
        inOrder(n.left);
        System.out.println(n.value);
        inOrder(n.right);
    }
}

in scheme, my starting code as follows: 

(define empty ())

(define empty? null?)

(define (node_key tn) (list-ref tn 0))

(define (node_val tn) (list-ref tn 1))

(define (node_left tn) (list-ref tn 2))

(define (node_right tn) (list-ref tn 3))

(define (tree-node key value left right) (list key value left right))

(define (get-key tn) (node_key tn))

(define (get-val tn) (node_val tn))

(define (get-left tn) (node_left tn))

(define (get-right tn) (node_right tn))

(define (get-pair tn) (list (get-key tn) (get-val tn)))

(define (atom? tn) (and (empty? (get-left tn)) (empty? (get-right tn))))

(define (printInOrder  t)
  (if (not (empty? t))       
      (begin
        (printInOrder (get-left t))
        (get-pair t)
        (printInOrder (get-right t))
        )
      )
  )

However, if we test the printInOrder:

(define a (tree-node 3 30 empty empty))

(define b (tree-node 1 10 empty empty))

(define c (tree-node 2 20 b a))

(printInOrder  c)

it should print:

1 10
2 20
3 30

but it doesn't work, print out nothing.

Could anyone help with this matter? Thanks.

Upvotes: 2

Views: 2496

Answers (2)

itsbruce
itsbruce

Reputation: 4843

Alan, for a java coder, you're littering your top level environment with many functions. Consider a node object like this:

    (define make-node
      (lambda (key value)
        (let ((left '()) (right '()))
          (lambda (m)
            (cond
              ((eq? m 'key) key)
              ((eq? m 'value) value)
              ((eq? m 'left) left)
              ((eq? m 'right) right)
              ((eq? m 'set-left) (lambda (x) (set! left x)))
              ((eq? m 'set-right) (lambda (x) (set! right x)))
              (else (error "Error (make-node): unknown op " m)) )))))

You'd need a little more than this to make a fully-fledged tree, of course; you'd want a list object with at least an insert method (doing it manually, as you are doing, means you could accidentally put the wrong node into "left" or "right" at any point in the tree). I'd also add a list-in-order method to the tree object, returning a list of key->value pairs, and then you could do anything with the list (including display it).

I'm not saying that's the best way to build the tree, but it's cleaner.

Upvotes: 0

dyoo
dyoo

Reputation: 12023

The code you've written is roughly equivalent to:

public void inOrder(BinaryNode n) {
    if (n != null) {
        preOrder(n.left);
        n.value;
        preOrder(n.left);
    }
}

(... except that Java will probably treat the naked n.value as a syntax error since isn't being used for anything interesting.)

Expressions do not automatically print out their values unless their values reach the toplevel. Otherwise, you've got to print the values explicitly. You can use display and newline to get the effect of System.out.println. If you're using Racket, you've also got printf to work with.

Upvotes: 1

Related Questions