Racket Tree Travesal

Question

I have the following problem with Racket.

I'm trying to implement tree pre-order, post-order traversal for a generic tree.

The struct definition is:

(define-struct eempty [])
(define-struct branch [left value right])

I can't use the unless/when operator, just if and cond. I can't really come up with a solution. I've looked at the wikipedia pseudocode but it's not really helping due to racket programming paradigm.

(define (inorder tree x)
  (cond [(and (branch? tree) (branch? (branch-left tree))) (inorder (branch-left tree) x)]
        [(and (branch? tree) (branch? (branch-right tree))) (inorder (branch-right tree) x)]

This is what I've done until now, but it has problems when matching an empty struct.

Update:

What I am trying to do is display / printing node value in-order or/and post-order.

I know I have to implement (somehow) 2 more conditions:

(and (branch? tree) (empty? (branch-left tree))) do-something x)
(and (branch? tree) (empty? (branch-right tree))) do-something x)

What do I have to do in do-something? I think I'm missing this point.

Any help?

Answer 1

We start with what we have:

#lang racket
(define-struct empty [])                     ; no fields
(define-struct branch [left value right])    ; three fields

We can try to make some trees:

(define t1 (empty))
(define t2 (branch t1 7 t1))

Now we can try playing with it a little:

> t2
#<branch>
> (branch-left t2)
#<empty>
> (branch-left t1)
branch-left: contract violation
  expected: branch?
  given: #<empty>
> (branch? t2)
#t
> (branch? t1)
#f
> (empty? t2)
#f
> (empty? t1)
#t
>

So that is our repertoire. Racket's struct macro defines various functions for us to use -- constructors, accessors, predicates, ... .

How to print a value? Say,

(define (display-value v)
  (display #\ )
  (display v))

So now we can

> (display-value (branch-value t2))
 7

empty has no value field, only branch does:

(define (display-tree-inorder t)
    (cond
        ((empty? t)
           (display-empty) )                       ; define it later
        ((branch? t)
           (display-branch-inorder                 ; define it later
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

In defining this, we have followed the type: our trees are either empty, or a branch. This is how we defined them, with those two struct definitions.

All that's left is to complete the missing definitions for display-empty and display-branch-inorder.

But before we do this, we can also have

(define (display-tree-preorder t)
    (cond
        ((empty? t)
           (display-empty) )
        ((branch? t)
           (display-branch-preorder
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

(define (display-tree-postorder t)
    (cond
        ((empty? t)
           (display-empty) )
        ((branch? t)
           (display-branch-postorder
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

So what is display-empty doing? It does nothing:

(define (display-empty)
    #f)

And what about display-branch-inorder?

(define (display-branch-inorder lt val rt)

according to Wikipedia I'm sure, it starts by displaying its left sub-tree,

    (display-tree-inorder .... ) 

then it gets to display its value

    (display-value .... )

and it finishes up by displaying the right sub-tree:

    .... )

Same for the other two variants.

After you've done all this, you'll feel the urge to abstract, and to generalize, by following the principle of separation of concerns. Good. Our display-tree-inorder lumps together several things: it traverses a tree, according to this or that notion of order, and it does something with each node's value. All these can be abstracted over and made into arguments to a generalized procedure, say, traverse-tree.

So you see, it's quite simple: follow the types! and everything will fall in line for you.