COMP1406 – Assignment #10

In this assignment you will practice using recursion with data structures.
(1) Consider the following BinaryTree class:
public class BinaryTree {
private String data;
private BinaryTree leftChild;
private BinaryTree rightChild;
public BinaryTree(String d) {
data = d;
leftChild = null;
rightChild = null;
}
public BinaryTree(String d, BinaryTree left, BinaryTree right) {
data = d;
leftChild = left;
rightChild = right;
}
}
Write a recursive method in this class called hasSameStructureAs(BinaryTree tree) that
returns whether or not a tree has the same structure as another tree. Two trees have the
same left/right children locations all the way through from the root to the leaves. The data at
each node need not be the same, however. You will not receive any marks if your code is
non-recursive or if it contains any loops. Use the following to test your code:
public class BinaryTreeTest {
public static void main(String[] args) {
BinaryTree[] trees = new BinaryTree[8];
trees[0] = new BinaryTree(“A”);
trees[1] = new BinaryTree(“A”, new BinaryTree(“B”), new BinaryTree(“C”));
trees[2] = new BinaryTree(“A”,
new BinaryTree(“B”, new BinaryTree(“C”), null), new BinaryTree(“D”));
trees[3] = new BinaryTree(“A”, null, new BinaryTree(“C”, new BinaryTree(“D”),
new BinaryTree(“E”,
new BinaryTree(“F”, new BinaryTree(“G”), null),
new BinaryTree(“H”))));
trees[4] = new BinaryTree(“A”,
new BinaryTree(“B”,
new BinaryTree(“C”,
new BinaryTree(“D”),
new BinaryTree(“E”,
new BinaryTree(“F”,
new BinaryTree(“G”),
new BinaryTree(“I”)),
new BinaryTree(“H”))),
new BinaryTree(“J”,
new BinaryTree(“K”,
null,
new BinaryTree(“L”,
null,
new BinaryTree(“M”))),
new BinaryTree(“N”,
null,
new BinaryTree(“O”)))),
new BinaryTree(“P”,
new BinaryTree(“Q”),
new BinaryTree(“R”,
new BinaryTree(“S”,
new BinaryTree(“T”),
null),
new BinaryTree(“U”))));
trees[5] = new BinaryTree(“A”, null, new BinaryTree(“P”, null,
new BinaryTree(“R”, null, new BinaryTree(“U”))));
trees[6] = new BinaryTree(“A”, null, new BinaryTree(“P”, null,
new BinaryTree(“R”, new BinaryTree(“W”), new BinaryTree(“U”))));
trees[7] = new BinaryTree(“A”,
new BinaryTree(“B”,
new BinaryTree(“C”,
null,
new BinaryTree(“E”,
new BinaryTree(“F”,
new BinaryTree(“G”),
new BinaryTree(“I”)),
new BinaryTree(“H”))),
new BinaryTree(“J”,
new BinaryTree(“K”,
null,
new BinaryTree(“L”,
null,
new BinaryTree(“M”))),
new BinaryTree(“N”,
null,
new BinaryTree(“O”)))),
null);
for (int i=0; i<8; i++) for (int j=0; j<8; j++) System.out.println("Tree[" + i + "] == trees[" + j + "]: " + trees[i].hasSameStructureAs(trees[j])); } } In this test case, the results should show that only a tree compared against itself will result in true and all the rest should be false. (2) Below is a RoomMaze class. This class represents a grid in which there are walls at various locations in an 8 x 8 grid. The walls separate rooms. Your task is to complete the identifyRooms() method (it MUST be recursive) and the traceRoomFrom() method so that it calculates and returns an integer indicating the number of rooms in the maze. The code must assign a unique color index to each room, starting with the number 1 (i.e., don't start at 0 because 0 represents a wall location). So, each location in the maze should be assigned an integer indicating the room that that grid location belongs to. These indices will be used to color the room in the test program. Note that if two wall locations are diagonally adjacent to one another (i.e., their corners touch) then this represents a separation between rooms. The image here shows walls (as red) and 7 rooms that have been uniquely identified: public class RoomMaze { public static byte ROWS = 8; private byte[][] wallTable; public RoomMaze() { wallTable = new byte[ROWS][ROWS]; resetWalls(); } public void resetWalls() { for (int r=0; r