Rice University - Comp 212 - Intermediate Programming

Fall 2002

Lecture #28 - Binary Tree Traversal

<< Under Construction>>

Today's menu:

1. Discuss BST deletion

2. Discuss ILambda and "currying".

3. Discuss tree traversal.

package brs.visitor;

import brs.*;
import utils.fp.*; // ILambda

/**
 * Traverses the host tree in some order and process it using the given input and the
 * given processing IVisitor and ILambda.  The ILambda determines the order in which
 * the tree is traversed and processed: In order, Pre order, Post Order.
 * @author DXN
 * @since Copyright 2002 - by Dung X. Nguyen - All rights reserved
 */
public class IPPOrderTraverse implements IVisitor {
    /**
     * To process the host tree with the given input.
     */
    private IVisitor _processTree;
    /**
     * A function of type Object -> (Object -> (Object -> Object)),
     * to combine the result from the recursive traversal computation of the
     * left subtree, the computation at the root, and the recursive computation
     * of the right subtree.
     * This is the key variant: the order in which one combines the results is
     * the traversal order.
     */
    private ILambda _combine;

    public IPPOrderTraverse(IVisitor pt, ILambda cr) {
        _processTree = pt;
        _combine = cr;
    }

    /**
     * @param inp input needed by _processTree;
     */
    public Object emptyCase(BiTree host, Object inp) {
        return host.execute(_processTree, inp);
    }

    /**
     * Recursively processes the left subtree, the root, and the right subtree,
     * and combine the results.
     * @param inp input needed by _processTree;
     */
    public Object nonEmptyCase(BiTree host, Object inp) {
        Object left = host.getLeftSubTree().execute(this, inp);
        Object root = host.execute(_processTree, inp);
        Object right = host.getRightSubTree().execute(this, inp);
        return
            ((ILambda)((ILambda)_combine.apply(left)).apply(root)).apply(right);
    }
}