Creating the tree is pretty simple. Here is a snippet:
[sourcecode=java]
/*
We're building a tree that looks like this:
I am root!
/\
A B
/\
C D
\
E
*/
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childD.addChild(childE);
childB.addChild(childC);
childB.addChild(childD);
root.addChild(childA);
root.addChild(childB);
tree.setRoot(root);
[/sourcecode]
Of course, simply writing a data structure is not enough. We need tests!
TestGenericTreeNode.java
[sourcecode="java"]
import org.testng.annotations.Test;
import java.util.ArrayList;
import java.util.List;
import static org.testng.Assert.*;
public class TestGenericTreeNode {
@Test
public void TestNodeDataIsNullOnNewNodeCreation() {
GenericTreeNode
assertNull(node.getData());
}
@Test
public void TestNodeHasNonNullChildrenListOnNewNodeCreation() {
GenericTreeNode
assertNotNull(node.getChildren());
}
@Test
public void TestNodeHasZeroChildrenOnNewNodeCreation() {
GenericTreeNode
assertEquals(node.getNumberOfChildren(), 0);
}
@Test
public void TestNodeHasChildrenReturnsFalseOnNewNodeCreation() {
GenericTreeNode
assertFalse(node.hasChildren());
}
@Test
public void TestNodeDataIsNonNullWithParameterizedConstructor() {
GenericTreeNode
assertNotNull(node.getData());
}
@Test
public void TestNodeSetAndGetData() {
GenericTreeNode
String data = "data";
node.setData(data);
assertEquals(node.getData(), data);
}
@Test
public void TestNodeSetAndGetChildren() {
GenericTreeNode
GenericTreeNode
List
children.add(child);
node.setChildren(children);
assertEquals(node.getChildren(), children);
}
@Test
public void TestNodeRemoveChildren() {
GenericTreeNode
GenericTreeNode
List
children.add(child);
node.setChildren(children);
node.removeChildren();
assertEquals(node.getChildren().size(), 0);
}
@Test
public void TestNodeAddChildHasOneChild() {
GenericTreeNode
GenericTreeNode
node.addChild(child);
assertEquals(node.getNumberOfChildren(), 1);
}
@Test
public void TestNodeAddChildHasChildrenIsTrue() {
GenericTreeNode
GenericTreeNode
node.addChild(child);
assertTrue(node.hasChildren());
}
@Test
public void TestNodeAddAndGetChildAt() {
GenericTreeNode
GenericTreeNode
GenericTreeNode
node.addChild(child1);
node.addChildAt(1, child2);
assertEquals(node.getChildAt(1).getData(), child2.getData());
}
@Test
public void TestNodeAddAndRemoveChildAt() {
GenericTreeNode
GenericTreeNode
GenericTreeNode
node.addChild(child1);
node.addChildAt(1, child2);
node.removeChildAt(0);
assertEquals(node.getNumberOfChildren(), 1);
}
@Test(expectedExceptions = java.lang.IndexOutOfBoundsException.class)
public void TestNodeAddChildAtThrowsException() {
GenericTreeNode
GenericTreeNode
node.addChildAt(5, child);
}
@Test(expectedExceptions = java.lang.IndexOutOfBoundsException.class)
public void TestNodeRemoveChildAtThrowsException() {
GenericTreeNode
node.removeChildAt(1);
}
@Test
public void TestNodeToString() {
GenericTreeNode
node.setData("data");
assertEquals(node.toString(), "data");
}
@Test
public void TestNodeToStringVerboseNoChildren() {
GenericTreeNode
node.setData("data");
assertEquals(node.toStringVerbose(), "data:[]");
}
@Test
public void TestNodeToStringVerboseOneChild() {
GenericTreeNode
node.setData("data");
GenericTreeNode
child.setData("child");
node.addChild(child);
assertEquals(node.toStringVerbose(), "data:[child]");
}
@Test
public void TestNodeToStringVerboseMoreThanOneChild() {
GenericTreeNode
node.setData("data");
GenericTreeNode
child1.setData("child1");
GenericTreeNode
child2.setData("child2");
node.addChild(child1);
node.addChild(child2);
assertEquals(node.toStringVerbose(), "data:[child1, child2]");
}
}
[/sourcecode]
TestGenericTree.java
[sourcecode lang="java"]
import org.testng.annotations.Test;
import java.util.*;
import static org.testng.Assert.*;
public class TestGenericTree {
@Test
public void TestRootIsNullOnNewTreeCreation() {
GenericTree
assertNull(tree.getRoot());
}
@Test
public void TestNumberOfNodesIsZeroOnNewTreeCreation() {
GenericTree
assertEquals(tree.getNumberOfNodes(), 0);
}
@Test
public void TestIsEmptyIsTrueOnNewTreeCreation() {
GenericTree
assertTrue(tree.isEmpty());
}
@Test
void TestExistsIsFalseOnNewTreeCreation() {
GenericTree
GenericTreeNode
assertFalse(tree.exists(nodeToFind));
}
@Test
void TestFindReturnsNullOnNewTreeCreation() {
GenericTree
GenericTreeNode
assertNull(tree.find(nodeToFind));
}
@Test
void TestPreOrderBuildReturnsNullListOnNewTreeCreation() {
GenericTree
assertNull(tree.build(GenericTreeTraversalOrderEnum.PRE_ORDER));
}
@Test
void TestPostOrderBuildReturnsNullListOnNewTreeCreation() {
GenericTree
assertNull(tree.build(GenericTreeTraversalOrderEnum.POST_ORDER));
}
@Test
void TestPreOrderBuildWithDepthReturnsNullMapOnNewTreeCreation() {
GenericTree
assertNull(tree.buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER));
}
@Test
void TestPostOrderBuildWithDepthReturnsNullMapOnNewTreeCreation() {
GenericTree
assertNull(tree.buildWithDepth(GenericTreeTraversalOrderEnum.POST_ORDER));
}
@Test
void TestToStringReturnsEmptyStringOnNewTreeCreation() {
GenericTree
assertEquals(tree.toString(), "");
}
@Test
void TestToStringWithDepthReturnsEmptyStringOnNewTreeCreation() {
GenericTree
assertEquals(tree.toStringWithDepth(), "");
}
@Test
void TestSetRootGetRoot() {
GenericTree
GenericTreeNode
tree.setRoot(root);
assertNotNull(tree.getRoot());
}
@Test
void TestNumberOfNodesIsOneWithNonNullRoot() {
GenericTree
GenericTreeNode
tree.setRoot(root);
assertEquals(tree.getNumberOfNodes(), 1);
}
@Test
void TestEmptyIsFalseWithNonNullRoot() {
GenericTree
GenericTreeNode
tree.setRoot(root);
assertFalse(tree.isEmpty());
}
@Test
void TestPreOrderBuildListSizeIsOneWithNonNullRoot() {
GenericTree
GenericTreeNode
tree.setRoot(root);
assertEquals(tree.build(GenericTreeTraversalOrderEnum.PRE_ORDER).size(), 1);
}
@Test
void TestPostOrderBuildListSizeIsOneWithNonNullRoot() {
GenericTree
GenericTreeNode
tree.setRoot(root);
assertEquals(tree.build(GenericTreeTraversalOrderEnum.POST_ORDER).size(), 1);
}
@Test
void TestPreOrderBuildWithDepthSizeIsOneWithNonNullRoot() {
GenericTree
GenericTreeNode
tree.setRoot(root);
assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER).size(), 1);
}
@Test
void TestPostOrderBuildWithDepthSizeIsOneWithNonNullRoot() {
GenericTree
GenericTreeNode
tree.setRoot(root);
assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.POST_ORDER).size(), 1);
}
/*
Tree looks like:
A
/ \
B C
\
D
For the following tests
*/
@Test
void TestNumberOfNodes() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
assertEquals(tree.getNumberOfNodes(), 4);
}
@Test
void TestExistsReturnsTrue() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
GenericTreeNode
assertTrue(tree.exists(nodeToFindD));
}
@Test
void TestFindReturnsNonNull() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
GenericTreeNode
assertNotNull(tree.find(nodeToFindD));
}
@Test
void TestExistsReturnsFalse() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
GenericTreeNode
assertFalse(tree.exists(nodeToFindE));
}
@Test
void TestFindReturnsNull() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
GenericTreeNode
assertNull(tree.find(nodeToFindE));
}
// Pre-order traversal will give us A B C D
@Test
void TestPreOrderBuild() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
List
preOrderList.add(new GenericTreeNode
preOrderList.add(new GenericTreeNode
preOrderList.add(new GenericTreeNode
preOrderList.add(new GenericTreeNode
// Instead of checking equalities on the lists themselves, we can check equality on the toString's
// they should generate the same toString's
assertEquals(tree.build(GenericTreeTraversalOrderEnum.PRE_ORDER).toString(), preOrderList.toString());
}
//Post-order traversal will give us B D C A
@Test
void TestPostOrderBuild() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
List
postOrderList.add(new GenericTreeNode
postOrderList.add(new GenericTreeNode
postOrderList.add(new GenericTreeNode
postOrderList.add(new GenericTreeNode
// Instead of checking equalities on the lists themselves, we can check equality on the toString's
// they should generate the same toString's
assertEquals(tree.build(GenericTreeTraversalOrderEnum.POST_ORDER).toString(), postOrderList.toString());
}
//Pre-order traversal with depth will give us A:0, B:1, C:1, D:2
@Test
void TestPreOrderBuildWithDepth() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
Map
preOrderMapWithDepth.put(new GenericTreeNode
preOrderMapWithDepth.put(new GenericTreeNode
preOrderMapWithDepth.put(new GenericTreeNode
preOrderMapWithDepth.put(new GenericTreeNode
// Instead of checking equalities on the maps themselves, we can check equality on the toString's
// they should generate the same toString's
assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER).toString(), preOrderMapWithDepth.toString());
}
//Post-order traversal with depth will give us B:1, D:2, C:1, A:0
@Test
void TestPostOrderBuildWithDepth() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
Map
postOrderMapWithDepth.put(new GenericTreeNode
postOrderMapWithDepth.put(new GenericTreeNode
postOrderMapWithDepth.put(new GenericTreeNode
postOrderMapWithDepth.put(new GenericTreeNode
// Instead of checking equalities on the maps themselves, we can check equality on the toString's
// they should generate the same toString's
assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.POST_ORDER).toString(), postOrderMapWithDepth.toString());
}
//toString and toStringWithDepth both use pre-order traversal
@Test
void TestToString() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
List
preOrderList.add(new GenericTreeNode
preOrderList.add(new GenericTreeNode
preOrderList.add(new GenericTreeNode
preOrderList.add(new GenericTreeNode
assertEquals(tree.toString(), preOrderList.toString());
}
@Test
void TestToStringWithDepth() {
GenericTree
GenericTreeNode
GenericTreeNode
GenericTreeNode
GenericTreeNode
childC.addChild(childD);
rootA.addChild(childB);
rootA.addChild(childC);
tree.setRoot(rootA);
Map
preOrderMapWithDepth.put(new GenericTreeNode
preOrderMapWithDepth.put(new GenericTreeNode
preOrderMapWithDepth.put(new GenericTreeNode
preOrderMapWithDepth.put(new GenericTreeNode
assertEquals(tree.toStringWithDepth(), preOrderMapWithDepth.toString());
}
}
[/sourcecode]
That's pretty much it. Hope you found this useful!
This looks great! Just added to my project… you’re a life saver Vivin!
How do we get parent of a child ?