What is it about recursion that makes it a useful tool when

Question

JAVA lab

Questions

1. What is it about recursion that makes it a useful tool when working with trees?
2. Explain in a few sentences how you can manually look through the nodes of a tree using the debugger after reaching a breakpoint?
3. Can you think of a reason why the make() method is declared to be private?
4. When is it ok to declare the instance variables of a class to be public?
5. Give two advantages of using dynamic memory and a tree to maintain a list of phone numbers.
6. What is a practical use of inorder traversal? How about pre-order and post-order? You might do some Internet searching for an answer.
7. Suppose we have a BST of 1000 items. How many nodes would you expect to have to visit to determine if a given node is present?

Description

1. For this lab, I suggest that you use the debugger facilities for breakpoints and watching variable values. Otherwise it's much harder to get programs to work that use recursion and dynamic memory.
2. This project's main class finds a solution to a maze problem. We need to find a path from row 0, column 0 of a two dimension array to the bottom right row and column. The following array declares the array that we will use.

 

int[][] grid = { {1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1},

{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1},

{0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},

{1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},

{1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1},

{1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},

{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} };

Starting at row 0, and column 0, we want to travel along all cells that contain a value of one to the bottom right cell. The problem is to print the solution, which is the path of rows and columns one would take to get to the destination.

In this lab we first create a tree from the two dimensional array given in the program. Next we perform a depth first search of the tree to find the path through the maze.

The steps in the implementation are as follows:
Create a TreeNode class with the following signature.

class TreeNode

{ public int row, column;

public TreeNode north, south, east, west;

public TreeNode(int row, int column);

public String toString();

}

Notice that everything is public. This class is used as a data structure that is only useful to the tree class that we will be creating. It's common for this kind of structure to allow public access and avoid implementing small get and put methods. However, we still provide a constructor so Nodes can easily be instantiated.
i. The TreeNode constructor serves the purpose that DefaultMutableTree node did to the Java JTree that we implemented in lab5. The constructor sets the row, and column fields to the values passed to it; the four child pointers are set to null.
ii. The toString() method returns the row and column as a formatted string. A statement such as:

return "("+row+","+column+")\n"; will suffice.
The MazeTree class that will represent the tree that we will be using is created next. The class signature follows:

class MazeTree

{ private TreeNode root;

public MazeTree(int[][] grid);

private void make(int[][] grid, TreeNode parent);

private boolean valid(int[][] grid, int row, int column);

private String depthFirstSearch(TreeNode thisNode);

public String depthFirstSearch();

}

i. The constructor creates the tree from the array and consists of the following statements.

Instantiate the root (root= new TreeNode(0,0);)

Mark that the root in the grid has been visited

Call the private make method.

Note: each time a node is added to the tree, modify the two dimensional grid row and column with a value other than 0 or 1. In this way, the algorithm described below will not get into a loop repeatedly visiting the same nodes.

ii. The make method performs the bulk of the work of creating the tree in a recursive manner. Its signature line is requires a Node to be passed; this is the parent node to which we will attach child nodes. The pseudo code for the make method follows:

FOR each adjacentNode to parent in the array

IF adjacentNode is valid

Instantiate a node for adjacentNode

Link adjacentNode to parent

FOR each adjacentNode that was successfully created

Recursively call make(adjacentNode)

iii. The public depthFirstSearch() method traverses the tree to find a solution and is called by the main() method. It calls the private depthFirstSearch(Treenode node) method.

iv. The private depthFirstSearch() method does the actual work of searching for a maze solution and is programmed recursively. Note that the depthFirstSearch() method no longer uses the grid array; that information is now part of the tree. The depthFirstSearch() pseudocode follows:

node = thisNode formatted as a string

IF thisNode is the final destination THEN Return node

FOR each child of thisNode

IF child exists

path = depthFirstSearch(child)

IF path != "" RETURN node + path

RETURN the empty string

The main() method's logic is straight forward. It instantiates the MazeTree from the grid and then calls the depth first search method. Upon return from the depth first search, an appropriate message if no solution was found ("" returned). Otherwise, the returned path is printed with System.out.println().