Starting MyTreeNode

Data Structure Overview

In the first three parts of this lab, we will be creating our own implementation of the general tree data structure to better understand its implementation and behavior.

Unlike for Labs 3 and 4 that implemented different versions of the List ADT, Java does not provide an interface or abstract class that represents a tree. Thus, we will build the general tree data structure entirely from scratch following the descriptions we used in lecture. Weā€™ll again be using generics for the implementation so that the tree can store any type of data as elements.

README

Even though Java does not provide a general tree implementation, it does use trees behind the scenes in some of its most popular implementations of other data structures, such as TreeSet and TreeMap, which we will talk about later this semester.

Getting Started

In Visual Studio Code, create a new file in your GitHub repository called MyTreeNode.java. Within this file, you should create a new class called MyTreeNode<T> that does not have any inheritance. Recall that throughout the semester, we are including the prefix My in your class name to reference our own implementations of the data structures.

README

As you are implementing your solutions, do not forget to include documentation using Javadocs! This is important practice to get into the habit of, and it will be a small portion of your solution grade for the remainder of the semester.

Instance Variables

Your MyTreeNode<T> inner class should have three private instance variables:

  1. item: the item of type T that is stored by the tree node
  2. parent: the parent MyTreeNode<T> of this tree node (which will be null for the root node)
  3. children: a List of children MyTreeNode<T>

All of the instance variables should be private so that their access (especially assigning values) can be controlled through the MyTreeNode class.

Constructors

The MyTreeNode class should have two constructors:

  1. The first private constructor is for non-root nodes ā€“ it should take as parameters an item to store in the node and a parent MyTreeNode to save as the parent of the new node. The children should be a new empty ArrayList.
  2. The second public constructor is for the root node ā€“ it should take as a single parameter the item to store in the node. This constructor should call the other constructor, instead of duplicating its work.
Hint

Recall that we had one constructor call another in Lab 3, if you need a refresher of how that process works.

README

Only the second constructor is public because outside of this class, a developer can only make new root nodes for trees. Non-root children should only be created through the addChild method that we will develop below, which will call the first private constructor.

Getter Methods

Since we made our instance variables private, we can add ā€œgetterā€ methods in order to still be able to retrieve values from outside of the class. You should add three such methods:

  1. public T getItem(), which returns the value of the item instance variable
  2. public MyTreeNode<T> getParent(), which returns the value of the parent instance variable
  3. public List<MyTreeNode<T>> getChildren(), which returns a deep copy of the children instance variable
README

If we were to simply return the List stored as the children instance variable, it could be modified outside of the class (by adding or removing child MyTreeNode<T> objects), which would defeat the purpose of making the instance variable private in the first place. We can make a deep copy by using the code:

List<MyTreeNode<T>> childrenCopy = new ArrayList<MyTreeNode<T>>(this.children);

which will contain all the same children nodes, but if someone were to try to add or remove nodes from the returned list, it would be different from and therefore not affect the list stored in this.children.

Adding Children

The last method we will implement in this part of the lab allows us to add children to a given MyTreeNode<T> so that we can start to build up the structure. You should implement a public method called addChild that:

  1. Takes as a parameter an item of type T to add to the tree
  2. Creates a new MyTreeNode<T> storing the given item and the current node (i.e., this) as its parent by using the first (private) constructor
  3. Adds the new node to the list of children
  4. Returns the new node

Testing Our Progress

Before moving on to the next part of the lab, we should create unit tests to verify our implementation so far and help us find and remove any bugs. As in previous labs, we can create a Java file that will contain our unit tests by right clicking anywhere in the MyTreeNode.java file and selecting ā€œSource Actionā€ from the right click menu. Then, select ā€œGenerate Testsā€. Use the default name proposed by the IDE of MyTreeNodeTest. Next, it will prompt you with what methods you want to create tests for. Select the getItem method for now.

Inside the newly created MyTreeNodeTest.java file, create unit tests verifying:

  1. The getItem method works properly
  2. The addChild method works properly
  3. The getParent method works properly (e.g., after calling addChild, the returned node has the correct parent)
  4. The getChildren method works properly (e.g., after calling addChild, the list returned by getChildren contains the correct number of children)

Committing Your Progress

Donā€™t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.