A. Intro

Download files for lab 14 and make a new Eclipse project out of them.

In earlier labs, we were discussing and implementing different variants of Linked Lists. In this lab and the next few, we will talk about a data structure called a tree. The meaning of the tree data structure originates from the notion of a tree in real life.

Below is a conceptual visualization of a tree. It's not really a box and pointer diagram and should not be interpreted as a literal implementation in Java.

Note that while a tree in real life starts small at the bottom and branches out upwards, trees in computer science are typically drawn such that they start small at the top and branch out downwards.

Some Vocabulary

Below is some useful terminology.

In our example, if we consider each box as a node, then 1, 2, 3, 4, 5, 6, and 7 are all nodes. There is a direct edge from 1 to 2. There is no direct edge from 1 to 7, but there is a path from 1 to 7, which consists of edges 1 -> 3 and 3 -> 7. 1 is the root node. 4, 5, and 7 are all leaf nodes.

Relationships

These terms are defined in relationship to a particular node. In other words, they only make sense when defined with respect to a particular current node.

We can also define the height of a tree and the depth of a tree, and it is usually assumed that this refers to the height of the root node and the depth of the deepest leaves respectively.

Definition

For a linked structure to be considered a tree, no node can be a direct child of multiple nodes. Further, there can be no cycles in the nodes, that is, paths that start at and return to the same node. Finally, all nodes must be a descendent of the root (except the root itself).

Discussion: Examples of Trees

Discuss with your partner whether the following examples would be considered trees as we've introduced them. Then add a post to the discussion.

• Linked List
• Family Tree
• Amoeba Family Tree (instead of a man and a woman creating any number of children, we have a single entity that creates any number of children)

B. Amoeba Family Tree

An amoeba family tree is an example of our above definition of a tree. It is simpler than a normal family tree because amoebas do not get married. An amoeba has one parent, many (zero or more) siblings, and many (zero or more) children. An amoeba also has a name.

Below is the skeleton code for an Amoeba. The full code is located at lab14/AmoebaFamily.java.

class Amoeba {
	String myName;
	Amoeba myParent;
	ArrayList<Amoeba> myChildren;
}

And below is a box and pointer diagram.

Amoebas (or amoebae) live dull lives. All they do is reproduce. So all we need to keep track of them are the following methods:

// A constructor that starts an Amoeba family with an amoeba with the given name. 
public AmoebaFamily(String name); 

// Add a new amoeba named childName as the youngest child of the amoeba named parentName. 
// Precondition: the amoeba family contains an amoeba named parentName. 
public void addChild(String parentName, String childName);

// Print the amoeba family tree. 
public void print(); 

Void Recursive Methods

In the AmoebaFamily class we provided the method addChild to add a new Amoeba to the AmoebaFamily tree. The method implements a general traversal of the tree using a void recursive method. You are going to write three other traversals that use a void recursive method. Your goal is to make the solution to the three methods as similar as possible to addChild.

Exercise: Make All Names Lowercase

// Makes all Amoeba names only lower case letters.
public void makeNamesLowercase();

Exercise: Replace the Name of an Amoeba

// Replaces the name of an amoeba named currentName with the name newName.
// Precondition: the amoeba family contains exactly one amoeba named currentName. 
public void replaceName(String currentName, String newName);

Exercise: Print the Names of All Amoebas in the Family.

// Print the names of all the amoebas in the family, one on each line
public void printFlat();

Exercise: Pretty Print

You're going to write a more interesting print method. It should print the root amoeba's name and the names of all its descendants. One name should be printed per line. The names of the children of each descendant Amoeba should be printed on the lines immediately following; they should be indented four spaces more than the name of their parent. Thus the output should appear in the form

amoeba_name
    child_name
        grandchild_name
            great_grandchild_name
                great_great_grandchild_name
        grandchild_name
    child_name
        grandchild_name
    child_name
    child_name
        grandchild_name

You will probably need a helper method whose argument keeps track of the indenting level, but the form should still be almost identical to addChild and the other three examples you worked with.

Non-void Recursive Methods

All of the methods we have written for the AmoebaFamily class have not returned anything! We will be able to do cooler things if we can return values. The next example will take advantage of this.

Longest Name

First, switch which partner is coding for this lab, if you haven't already.

We've provided the following method:

// returns the length of the longest name in the Amoeba Family
public int longestNameLength();

Your goal is to write a method longestName that is as similar to longestNameLength as possible. The goal is to try to identify the pattern in these non-void recursive methods. You will use the patterns here in the next two exercises.

// this method should return the name that is longest of all names in the tree.
public String longestName(); 

Amoeba Counting

Write and test an AmoebaFamily method named size that returns the number of amoebas in this family.

OPTIONAL: Finding the Busiest Amoeba

Consider an AmoebaFamily method named busiest, which returns the name of the amoeba with the most children.

If there are more than one amoeba with the same maximum number of children, you may return the name of any of them. If the tree is empty, return null.

Hint: The longestName method is a good model for busiest. Depending on your implementation, you may find that you need to keep track of two sets of information, but your helper method can only return one thing. Think flexibly and consider what you can return that will help keep track of those two sets of information.

Computing the Height

The height of a node in a tree is the maximum length of a downward path from that node to a leaf. For now, we'll define the height of a leaf as 1, and the height of a null tree as 0. Sometimes you'll see a different convention, defining the height of a leaf as 0, and the height of a null tree as -1.

The following code is an incorrect implementation of the height method. Discuss with your partner what the bug is.

//In Amoeba
private int height() {
    if (myChildren.isEmpty()) {
    	return 1;
    } else {
        int bestSoFar = 1;
        for (Amoeba a : myChildren) {
            bestSoFar = 1 + Math.max(a.height(), bestSoFar);
        }
        return bestSoFar;
    }
}

Then write a JUnit test that includes the case you identified and one other case. Then fix the implementation of the height method. This means include a height method in the AmoebaFamily class, similarly to all the other AmoebaFamily methods you've written so far.

C. Binary Trees

As noted earlier, a common special case is a binary tree, one in which each node has at most two children. Rather than store the children in an ArrayList as was done in Amoeba nodes, one normally just has two separate variables myLeft and myRight for the left and right children.

Three processing sequences for nodes in a binary tree occur commonly enough to have names:

• preorder: process the root, process the left subtree (in preorder), process the right subtree (in preorder)
• postorder: process the left subtree (in postorder), process the right subtree (in postorder), process the root
• inorder: process the left subtree (in inorder), process the root, process the right subtree (in inorder)

Exercises with Processing Sequences

With your partner, determine the preorder, inorder, and postorder processing sequence for the tree below. Then, verify your answers below.

preorder:

inorder:

postorder:

A BinaryTree Class

The file lab14/BinaryTree.java defines a BinaryTree class and a TreeNode class. First, read the code, and predict what output will be produced by the statement

print(t, "sample tree 2"); 

in the main method. Run the program to verify your answer.

Then provide a fillSampleTree3 method that initializes the BinaryTree version of the tree pictured below.

Run the program to verify your answer.

Height Method

First, switch which partner is coding if you haven't recently.

Add a height method to the BinaryTree class, similar to the AmoebaFamily height method you worked with earlier. The height of an empty tree is 0; the height of a one-node tree is 1; the height of any other tree is 1 + the greater of the heights of the two children. You can use the buggy version as a starting point. Test your method on the various sample trees.

Is Completely Balanced

Then provide an isCompletelyBalanced method for the BinaryTree class. An empty tree and a tree containing just one node are both completely balanced; any other tree is completely balanced if and only if the height of its left child is equal to the height of its right child, and its left and right children are also completely balanced. Test your method on the various sample trees, as well as a completely balanced tree of height 3.

D. Conclusion

Submission

You will submit your JUnit test, AmoebaFamily.java and BinaryTree.java.

Make sure you have completed the following methods in 'AmoebaFamily.java':

public void makeNamesLowercase();
public void replaceName(String currentName, String newName);
public void printFlat();
public void print();
public String longestName();
public int size();
public int height();

and in 'BinaryTree.java':

public void fillSampleTree3();
public int height();
public boolean isCompletelyBalanced();

In addition, please fill out this self-reflection form before this lab is due, as a part of your homework assignment. Self-reflection forms are to be completed individually, not in partnership.