The sole purpose of this assignment is to let you implement algorithms on linked-node based trees (see the given TreeNode class) and singly-linked nodes (see the given SLLNode class), from scratch, without the aid of any other data structures (e.g., primitive arrays) or library classes.
Therefore, to complete this assignment, it is strictly forbidden for you to use any of the following:
This assignment requires the more intermediate use of generics. Study carefully the TestGeneralTrees class given to you (in the tests package), which contains how the following two classes work together:
Expression.java
package tests;
/*
* A class used by the StarterTests.
* You must use this class as is without modifying it.
*/
public abstract class Expression {
}
Operand.java
package tests;
/*
* A class used by the StarterTests.
* Operands store integer value.
* You must use this class as is without modifying it.
*/
public class Operand extends Expression {
private int value;
public Operand(int value) {
this.value = value;
}
public void setValue(int value) {
this.value = value;
}
public int getValue() {
return this.value;
}
}
Operator.java
package tests;
/*
* A class used by the StarterTests.
* Operators (e.g., `+` for addition) manipulate integer operands.
* You must use this class as is without modifying it.
*/
public class Operator extends Expression {
private char op;
public Operator(char op) {
this.op = op;
}
public void setOperator(char op) {
this.op = op;
}
public char getOperator() {
return this.op;
}
}
SLLNode.java
package tests;
/*
* Template for nodes in a singly-linked list.
* You must use this class as is without modifying it.
*/
public class SLLNode< E > {
private E element;
private SLLNode< E > next;
public SLLNode(E e, SLLNode< E > n) {
element = e;
next = n;
}
public E getElement() {
return element;
}
public SLLNode< E > getNext() {
return next;
}
public void setNext(SLLNoden) {
next = n;
}
public void setElement(E e) {
element = e;
}
}
StarterTests.java
package tests;
import static org.junit.Assert.*;
import org.junit.Test;
import model.TreeUtilities;
/*
* Study carefully the test methods below. They suggest:
* - the required class(es) and method(s) to be implement in the `model` package
* - how the required class(es) and method(s) should be implemented
*
* Requirements:
* + Do ***not*** create any new class that is not required by the starter tests.
* All such classes will be ***disregarded*** when grading.
*
* + Any classes you create must reside in the `model` package and be imported properly.
* For example, creating a new class `Foo` in the `model` package should result in:
* import model.Foo;
*
* + For this assignment, you should not need to declare attributes.
* But if you really want to, all attributes you declare in the model classes must be private.
*
* + If necessary, you may define private helper methods.
*/
public class StarterTests {
/*
* Programming Requirements:
*
* - This assignment focuses on the manipulation of:
* + linked-node based trees (see the given TreeNode class)
* + singly-linked nodes (see the given SLLNode class)
*
* Therefore, you are forbidden to use primitive arrays (e.g., Integer[], int[], String[])
* for declaring attributes or local variables. Use only the TreeNode and SLLNode classes given to you.
*
* - In addition, any use of a Java library class or method is also forbidden
* (that is, use selections and loops to build your solution from scratch instead):
*
* - Here are some examples of forbidden classes/methods:
* - Arrays class (e.g., Arrays.copyOf)
* - System class (e.g., System.arrayCopy)
* - ArrayList class
* - String class (e.g., substring).
*
* - The use of some library classes does not require an import statement,
* but these classes are also forbidden to be used.
* - Here are the exceptions (library methods which you are allowed to use if needed):
* - String class (equals, format, length, charAt)
*
* Violating the above programming requirements will result in a penalty (see the assignment instructions for details).
*
* Tests included in this class serve as documentation on how instances of Tree Utilities operate.
*
* Before attempting this assignment,
* it is expected that you already completed background study materials as outlined in the assignment instructions.
*
* Be sure to also read the following sections from your Assignment 1 instructions PDF:
* - The `Requirements of this Assignment` section (page 3)
* - Sections 0 and 1 on the background studies
*/
/*
* Be sure to study how the TreeNode and SLLNode classes are supposed to work together
* as illustrated in the TestGeneralTrees JUnit class.
*/
/*
* Tests related to getInfixTree
*/
@Test
public void test_getInfixTree_00() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
/* Create a postfix expression "23" */
SLLNode< Expression > expression = new SLLNode< >(operand1, null);
/*
* Input of `getInfixTree`: a chain of SLLNode objects representing a postfix expression
* Output: a TreeNode object, which is the root of a tree whose in-order-traversal corresponds to an infix expression that is equivalent to the input postfix expression
*
* Assumptions:
* + Only these operators will appear on inputs: `+` (addition), `-` (subtraction), `*` (multiplication).
* + Operand values are integers (negative, zero, positive).
* + The input postfix expression is not null and it is valid: no error handling is needed.
* + An inheritance hierarchy exists among the given classes `Expression`, `Operator`, and `Operand` in the `tests` package.
*
* Requirements:
* + You must use the provided classes SLLNode and TreeNode (without modifying them) in the `tests` package.
* + No extra external/internal classes beyond what is required by the StarterTests (i.e., TreeUtilities) are allowed.
*
* Background:
* + Refer to the lecture materials on how postfix expressions should be calculated.
* + If you wish to use a stack or queue in the TreeUtilities, the programming requirements apply:
* - No primitive arrays
* - No library classes
* - No additional inner/external classes
* Instead, use helper methods or attributes/variables for implementation.
*/
/*
* Expected to return a tree storing the infix expression `23`
*/
TreeNode< Expression > root = u.getInfixTree(expression);
/*
* Hint: Visualize what tree structure is being asserted by the tests.
* See TestGeneralTrees on how to use SLLNode and TreeNode.
*/
assertTrue(root.getElement() == operand1);
assertNull(root.getParent());
assertNull(root.getChildren());
}
@Test
public void test_getInfixTree_01() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operator1 = new Operator('+');
/* Create a postfix expression "23 46 +" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operator1, null)));
/*
* Expected to return a tree storing the infix expression `23 + 46`
*/
TreeNode< Expression > root = u.getInfixTree(expression);
/*
* Hint: Visualize what tree structure is being asserted by the tests.
* See TestGeneralTrees on how to use SLLNode and TreeNode.
*/
SLLNode< TreeNode< Expression > > levelOneChild1 = root.getChildren();
SLLNode< TreeNode< Expression > > levelOneChild2 = levelOneChild1.getNext();
assertNull(levelOneChild2.getNext());
assertTrue(root.getElement() == operator1);
assertTrue(levelOneChild1.getElement().getElement() == operand1);
assertTrue(levelOneChild2.getElement().getElement() == operand2);
assertNull(root.getParent());
assertTrue(root == levelOneChild1.getElement().getParent());
assertTrue(root == levelOneChild2.getElement().getParent());
assertNull(levelOneChild1.getElement().getChildren());
assertNull(levelOneChild2.getElement().getChildren());
}
@Test
public void test_getInfixTree_02() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operand3 = new Operand(69);
Expression operator1 = new Operator('+');
Expression operator2 = new Operator('*');
/* Create a postfix expression "23 46 + 69 *" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operator1,
new SLLNode< >(operand3,
new SLLNode< >(operator2, null)))));
/*
* Expected to return a tree storing the infix expression `(23 + 46) * 69`
* Note: The parentheses here are only meant to indicate the order of evaluation: they need not be stored in the output tree.
*/
TreeNode< Expression > root = u.getInfixTree(expression);
/*
* Hint: Visualize what tree structure is being asserted by the tests.
* See TestGeneralTrees on how to use SLLNode and TreeNode.
*/
SLLNode< TreeNode< Expression > > levelOneChild1 = root.getChildren();
SLLNode< TreeNode< Expression > > levelOneChild2 = levelOneChild1.getNext();
assertNull(levelOneChild2.getNext());
SLLNode< TreeNode< Expression > > levelTwoChild1 = levelOneChild1.getElement().getChildren();
SLLNode< TreeNode< Expression > > levelTwoChild2 = levelTwoChild1.getNext();
assertNull(levelTwoChild2.getNext());
assertTrue(root.getElement() == operator2);
assertTrue(levelOneChild1.getElement().getElement() == operator1);
assertTrue(levelTwoChild1.getElement().getElement() == operand1);
assertTrue(levelTwoChild2.getElement().getElement() == operand2);
assertTrue(levelOneChild2.getElement().getElement() == operand3);
assertNull(root.getParent());
assertTrue(root == levelOneChild1.getElement().getParent());
assertTrue(root == levelOneChild2.getElement().getParent());
assertTrue(levelOneChild1.getElement() == levelTwoChild1.getElement().getParent());
assertTrue(levelOneChild1.getElement() == levelTwoChild2.getElement().getParent());
assertNull(levelTwoChild1.getElement().getChildren());
assertNull(levelTwoChild2.getElement().getChildren());
assertNull(levelOneChild2.getElement().getChildren());
}
@Test
public void test_getInfixTree_03() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operand3 = new Operand(69);
Expression operator1 = new Operator('+');
Expression operator2 = new Operator('*');
/* Create a postfix expression "23 46 69 * +" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operand3,
new SLLNode< >(operator2,
new SLLNode< >(operator1, null)))));
/*
* Expected to return a tree storing the infix expression `23 + (46 * 69)`
* Note: The parentheses here are only meant to indicate the order of evaluation: they need not be stored in the output tree.
*/
TreeNode< Expression > root = u.getInfixTree(expression);
/*
* Hint: Visualize what tree structure is being asserted by the tests.
* See TestGeneralTrees on how to use SLLNode and TreeNode.
*/
SLLNode< TreeNode< Expression > > levelOneChild1 = root.getChildren();
SLLNode< TreeNode< Expression > > levelOneChild2 = levelOneChild1.getNext();
assertNull(levelOneChild2.getNext());
SLLNode< TreeNode< Expression > > levelTwoChild1 = levelOneChild2.getElement().getChildren();
SLLNode< TreeNode< Expression > > levelTwoChild2 = levelTwoChild1.getNext();
assertNull(levelTwoChild2.getNext());
assertTrue(root.getElement() == operator1);
assertTrue(levelOneChild1.getElement().getElement() == operand1);
assertTrue(levelOneChild2.getElement().getElement() == operator2);
assertTrue(levelTwoChild1.getElement().getElement() == operand2);
assertTrue(levelTwoChild2.getElement().getElement() == operand3);
assertNull(root.getParent());
assertTrue(root == levelOneChild1.getElement().getParent());
assertTrue(root == levelOneChild2.getElement().getParent());
assertTrue(levelOneChild2.getElement() == levelTwoChild1.getElement().getParent());
assertTrue(levelOneChild2.getElement() == levelTwoChild2.getElement().getParent());
assertNull(levelOneChild1.getElement().getChildren());
assertNull(levelTwoChild1.getElement().getChildren());
assertNull(levelTwoChild2.getElement().getChildren());
}
@Test
public void test_getInfixTree_04() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operand3 = new Operand(69);
Expression operand4 = new Operand(92);
Expression operator1 = new Operator('-');
Expression operator2 = new Operator('+');
Expression operator3 = new Operator('*');
/* Create a postfix expression "23 46 - 69 92 * +" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operator1,
new SLLNode< >(operand3,
new SLLNode< >(operand4,
new SLLNode< >(operator3,
new SLLNode< >(operator2, null)))))));
/*
* Expected to return a tree storing the infix expression `(23 - 46) + (69 * 92)`
* Note: The parentheses here are only meant to indicate the order of evaluation: they need not be stored in the output tree.
*/
TreeNode< Expression > root = u.getInfixTree(expression);
/*
* Hint: Visualize what tree structure is being asserted by the tests.
* See TestGeneralTrees on how to use SLLNode and TreeNode.
*/
SLLNode< TreeNode< Expression > > levelOneChild1 = root.getChildren();
SLLNode< TreeNode< Expression > > levelOneChild2 = levelOneChild1.getNext();
assertNull(levelOneChild2.getNext());
SLLNode< TreeNode< Expression > > levelTwoChild1 = levelOneChild1.getElement().getChildren();
SLLNode< TreeNode< Expression > > levelTwoChild2 = levelTwoChild1.getNext();
assertNull(levelTwoChild2.getNext());
SLLNode< TreeNode< Expression > > levelTwoChild3 = levelOneChild2.getElement().getChildren();
SLLNode< TreeNode< Expression > > levelTwoChild4 = levelTwoChild3.getNext();
assertNull(levelTwoChild4.getNext());
assertTrue(root.getElement() == operator2);
assertTrue(levelOneChild1.getElement().getElement() == operator1);
assertTrue(levelTwoChild1.getElement().getElement() == operand1);
assertTrue(levelTwoChild2.getElement().getElement() == operand2);
assertTrue(levelOneChild2.getElement().getElement() == operator3);
assertTrue(levelTwoChild3.getElement().getElement() == operand3);
assertTrue(levelTwoChild4.getElement().getElement() == operand4);
assertNull(root.getParent());
assertTrue(root == levelOneChild1.getElement().getParent());
assertTrue(root == levelOneChild2.getElement().getParent());
assertTrue(levelOneChild1.getElement() == levelTwoChild1.getElement().getParent());
assertTrue(levelOneChild1.getElement() == levelTwoChild2.getElement().getParent());
assertTrue(levelOneChild2.getElement() == levelTwoChild3.getElement().getParent());
assertTrue(levelOneChild2.getElement() == levelTwoChild4.getElement().getParent());
assertNull(levelTwoChild1.getElement().getChildren());
assertNull(levelTwoChild2.getElement().getChildren());
assertNull(levelTwoChild3.getElement().getChildren());
assertNull(levelTwoChild4.getElement().getChildren());
}
/*
* Tests related to getInfixSequence
*/
@Test
public void test_getInfixSequence_00() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
SLLNode< Expression > expression = new SLLNode< >(operand1, null);
/*
* Input of `getInfixSequence`: a chain of SLLNode objects representing a postfix expression
* Output: a string of an infix expression that is equivalent to the input postfix expression
*
* Assumptions:
* + Only these operators will appear on inputs: `+` (addition), `-` (subtraction), `*` (multiplication).
* + Operand values are integers (negative, zero, positive).
* + The input postfix expression is not null and it is valid: no error handling is needed.
* + An inheritance hierarchy exists among the given classes `Expression`, `Operator`, and `Operand` in the `tests` package.
*
* Requirements:
* + You must use the provided classes SLLNode and TreeNode (without modifying them) in the `tests` package.
* + No extra external/internal classes beyond what is required by the StarterTests (i.e., TreeUtilities) are allowed.
*
* Background:
* + Refer to the lecture materials on how postfix expressions should be calculated.
* + If you wish to use a stack or queue in the TreeUtilities, the programming requirements apply:
* - No primitive arrays
* - No library classes
* - No additional inner/external classes
* Instead, use helper methods or attributes/variables for implementation.
*/
/* Expected to return a string storing the infix expression `23` */
assertEquals("23", u.getInfixSequence(expression));
/*
* When the expression only involves a single operand, no parentheses are to be included.
*/
}
@Test
public void test_getInfixSequence_01() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operator1 = new Operator('+');
/* Create a postfix expression "23 46 +" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operator1, null)));
/* Expected to return a string storing the infix expression `23 + 46` */
assertEquals("(23 + 46)", u.getInfixSequence(expression));
/*
* When the expression involves at least an operator, an outer-most pair of parentheses is to be included.
*/
}
@Test
public void test_getInfixSequence_02() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operand3 = new Operand(69);
Expression operator1 = new Operator('+');
Expression operator2 = new Operator('*');
/* Create a postfix expression "23 46 + 69 *" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operator1,
new SLLNode< >(operand3,
new SLLNode< >(operator2, null)))));
/* Expected to return a string storing the infix expression `(23 + 46) * 69`
* Note: The parentheses here are meant to indicate the order of evaluation: they need to be stored in the output string.
*/
assertEquals("((23 + 46) * 69)", u.getInfixSequence(expression));
/*
* When the expression involves at least an operator, an outer-most pair of parentheses is to be included.
*/
}
@Test
public void test_getInfixSequence_03() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operand3 = new Operand(69);
Expression operator1 = new Operator('+');
Expression operator2 = new Operator('*');
/* Create a postfix expression "23 46 69 * +" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operand3,
new SLLNode< >(operator2,
new SLLNode< >(operator1, null)))));
/* Expected to return a string storing the infix expression `23 + (46 * 69)`
* Notes:
* + The parentheses here are meant to indicate the order of evaluation: they need to be stored in the output string.
* + For this task, we disregard operator precedences: always put a pair or parentheses to explicitly indicate the order of evaluation.
*/
assertEquals("(23 + (46 * 69))", u.getInfixSequence(expression));
/*
* When the expression involves at least an operator, an outer-most pair of parentheses is to be included.
*/
}
@Test
public void test_getInfixSequence_04() {
TreeUtilities u = new TreeUtilities();
Expression operand1 = new Operand(23);
Expression operand2 = new Operand(46);
Expression operand3 = new Operand(69);
Expression operand4 = new Operand(92);
Expression operator1 = new Operator('-');
Expression operator2 = new Operator('+');
Expression operator3 = new Operator('*');
/* Create a postfix expression "23 46 - 69 92 * +" */
SLLNode< Expression > expression =
new SLLNode< >(operand1,
new SLLNode< >(operand2,
new SLLNode< >(operator1,
new SLLNode< >(operand3,
new SLLNode< >(operand4,
new SLLNode< >(operator3,
new SLLNode< >(operator2, null)))))));
/* Expected to return a string storing the infix expression `(23 - 46) + (69 * 92)`
* Notes:
* + The parentheses here are meant to indicate the order of evaluation: they need to be stored in the output string.
* + For this task, we disregard operator precedences: always put a pair or parentheses to explicitly indicate the order of evaluation.
*/
assertEquals("((23 - 46) + (69 * 92))", u.getInfixSequence(expression));
/*
* When the expression involves at least an operator, an outer-most pair of parentheses is to be included.
*/
}
/*
* Jackie's suggestion:
* + For both tasks, you may want to test your implemented method(s) for more sophisticated input postfix expressions.
* Hint. First think of the output infix expression (e.g., 3 + 4 * 5),
* then work out backwards the corresponding input postfix expression (i.e., 3 4 5 * +)
*/
}
TestGeneralTrees.java
package tests;
import static org.junit.Assert.*;
import org.junit.Test;
/*
* This test illustrates how the two classes SLLNode and TreeNode may be used together.
*/
public class TestGeneralTrees {
@Test
public void test_general_trees_construction_strings() {
TreeNode< String > jonathan = new TreeNode< >("Jonathan");
TreeNode< String > alan = new TreeNode< >("Alan");
TreeNode< String > mark = new TreeNode< >("Mark");
TreeNode< String > tom = new TreeNode< >("Tom");
/* Initially, no child nodes for jonathan */
assertNull(jonathan.getChildren());
/* Add the first child node for jonathan */
jonathan.addChild(alan);
alan.setParent(jonathan);
assertNull(jonathan.getParent());
assertTrue(jonathan == alan.getParent());
SLLNode< TreeNode< String > > childList = jonathan.getChildren();
assertTrue(childList.getElement() == alan);
/*
* childList returns a SLLNode< TreeNode< String > >
* childList.getElement() returns a TreeNode< String >
* childList.getElement().getElement() returns a String
*/
assertTrue(childList.getElement().getElement().equals("Alan"));
assertNull(childList.getNext());
/* Add the second child node for jonathan */
jonathan.addChild(mark);
mark.setParent(jonathan);
assertNull(jonathan.getParent());
assertTrue(jonathan == alan.getParent());
assertTrue(jonathan == mark.getParent());
childList = jonathan.getChildren();
assertTrue(childList.getElement() == alan);
assertTrue(childList.getElement().getElement().equals("Alan"));
assertTrue(childList.getNext().getElement() == mark);
/*
* childList.getNext() returns a SLLNode< TreeNode< String > >
* childList.getNext().getElement() returns a TreeNode< String >
* childList.getNext().getElement().getElement() returns a String
*/
assertTrue(childList.getNext().getElement().getElement().equals("Mark"));
assertNull(childList.getNext().getNext());
/* Add the third child node for jonathan */
jonathan.addChild(tom);
tom.setParent(jonathan);
assertNull(jonathan.getParent());
assertTrue(jonathan == alan.getParent());
assertTrue(jonathan == mark.getParent());
assertTrue(jonathan == tom.getParent());
childList = jonathan.getChildren();
assertTrue(childList.getElement() == alan);
assertTrue(childList.getElement().getElement().equals("Alan"));
assertTrue(childList.getNext().getElement() == mark);
assertTrue(childList.getNext().getElement().getElement().equals("Mark"));
assertTrue(childList.getNext().getNext().getElement() == tom);
assertTrue(childList.getNext().getNext().getElement().getElement().equals("Tom"));
assertNull(childList.getNext().getNext().getNext());
}
@Test
public void test_general_trees_construction_integers() {
TreeNode< Integer > i0 = new TreeNode< >(0);
TreeNode< Integer > i1 = new TreeNode< >(1);
TreeNode< Integer > i2 = new TreeNode< >(2);
TreeNode< Integer > i3 = new TreeNode< >(3);
/* Initially, no child nodes for i0 */
assertNull(i0.getChildren());
/* Add the first child node for i0 */
i0.addChild(i1);
i1.setParent(i0);
assertNull(i0.getParent());
assertTrue(i0 == i1.getParent());
SLLNode< TreeNode< Integer > > childList = i0.getChildren();
assertTrue(childList.getElement() == i1);
/*
* childList returns a SLLNode< TreeNode< Integer > >
* childList.getElement() returns a TreeNode< Integer >
* childList.getElement().getElement() returns a Integer
*/
assertTrue(childList.getElement().getElement().equals(1));
assertNull(childList.getNext());
/* Add the second child node for i0 */
i0.addChild(i2);
i2.setParent(i0);
assertNull(i0.getParent());
assertTrue(i0 == i1.getParent());
assertTrue(i0 == i2.getParent());
childList = i0.getChildren();
assertTrue(childList.getElement() == i1);
assertTrue(childList.getElement().getElement().equals(1));
assertTrue(childList.getNext().getElement() == i2);
/*
* childList.getNext() returns a SLLNode< TreeNode< Integer > >
* childList.getNext().getElement() returns a TreeNode< Integer >
* childList.getNext().getElement().getElement() returns a Integer
*/
assertTrue(childList.getNext().getElement().getElement().equals(2));
assertNull(childList.getNext().getNext());
/* Add the third child node for i0 */
i0.addChild(i3);
i3.setParent(i0);
assertNull(i0.getParent());
assertTrue(i0 == i1.getParent());
assertTrue(i0 == i2.getParent());
assertTrue(i0 == i3.getParent());
childList = i0.getChildren();
assertTrue(childList.getElement() == i1);
assertTrue(childList.getElement().getElement().equals(1));
assertTrue(childList.getNext().getElement() == i2);
assertTrue(childList.getNext().getElement().getElement().equals(2));
assertTrue(childList.getNext().getNext().getElement() == i3);
assertTrue(childList.getNext().getNext().getElement().getElement().equals(3));
assertNull(childList.getNext().getNext().getNext());
}
}
TreeNode.java
package tests;
/*
* Template for nodes in a general tree.
* You must use this class as is without modifying it.
* Notes:
* + This version of TreeNode is different from what's covered in the lecture.
* Specifically, the list of child nodes is implemented via a chain of singly-linked nodes (see the SLLNode class).
* + See the TestGeneralTrees class for how the TreeNode and SLLNode classes are supposed to work together.
*/
public class TreeNode< E > {
private E element; /* data object */
private TreeNode< E > parent; /* unique parent node */
private SLLNode< TreeNode< E > > headOfChildList; /* head of list of child nodes */
private SLLNode< TreeNode< E > > tailOfChildList; /* tail of list of child nodes */
public TreeNode(E element) {
this.element = element;
this.parent = null;
this.headOfChildList = null;
this.tailOfChildList = null;
}
public E getElement() {
return this.element;
}
public void setElement(E element) {
this.element = element;
}
public TreeNode< E > getParent() {
return this.parent;
}
public void setParent(TreeNode< E > parent) {
this.parent = parent;
}
public SLLNode< TreeNode< E > > getChildren() {
SLLNode< TreeNode< E > > result = null;
SLLNode< TreeNode< E > > currentResult = null;
SLLNode< TreeNode< E > > currentChild = headOfChildList;
while (currentChild != null) {
SLLNode< TreeNode< E > > n = new SLLNode< >(currentChild.getElement(), null);
if(result == null) {
result = n;
currentResult = result;
}
else {
currentResult.setNext(n);
currentResult = currentResult.getNext();
}
currentChild = currentChild.getNext();
}
return result;
}
public void addChild(TreeNode< E > child) {
SLLNode< TreeNode< E > > n = new SLLNode< >(child, null);
if(headOfChildList == null) {
headOfChildList = n;
tailOfChildList = headOfChildList;
}
else {
tailOfChildList.setNext(n);
tailOfChildList = tailOfChildList.getNext();
}
}
}