Programming Assignment 3

Tree Matching

Data Structures & Algorithms, Fall 2010

Due Date

This assignment is due by 11:30 p.m. on Wednesday, 1 December.

See the assignment turn-in page (last modified on 23 February 2010) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 3 is Saturday, 4 December at 11:30 p.m. It is not possible to turn-in Assignment 3 after the absolute deadline.

Background

Tree matching determines if one tree appears in another tree. Two trees match each other if either
  1. Both trees are empty, or
  2. both trees are non-empty and
    1. both root nodes have the same value,
    2. each root has the same number of children, and
    3. the corresponding children in each root node match.

The Problem

Write the method match() that accepts a source binary tree and a pattern binary tree, and returns the root of an occurrence of the pattern in the source, if it exists. The pattern tree may occur anywhere in the source tree.

match() is defined in the interface

/export/home/class/cs-305/pa3/TreeMatch.java

The BinaryTree interface used in TreeMatch does not need an implementation. The BinaryTree interface has already been implemented, and is part of the jar file.

Implementing

Once you’ve got your implementation far enough along, you can try it out using the jar file
/export/home/class/cs-305/pa3/pa3.jar
by typing 

$ java -classpath jar-path/pa3.jar:. main class-name

where jar-path is the path to pa3.jar and class-name is the name of the class implementing the TreeMatcher interface. For example, if the class MatchTree implements TreeMatcher and you’re using pa3.jar in the public class directory, you would type 

$ java -classpath /export/home/class/cs-305/pa3/pa3.jar:. main MatchTree

This page last modified on 27 November 2010.