I am working on a homework project where I read a list of connecting stations from a file and create a hashmap in the format (key = String station, value = ArrayList connecting stations) so far so good.
The user can then select a home station at which point I am trying to create a tree to represent all accessible stations from home. The tree could for example look like:
HomeStation
/ \
station1 station2
/ | \
station3 station4 station 5
But I can not wrap my head around how to add these stations to the tree beyond just the root and its children. So can anyone give me some pointers as to what I should be doing/looking at.
My TreeNode class so far:
/**
* TreeNode class
* Represents a N-ary tree node
* Uses ArrayList to hold the children.
* @author Ásta B. Hansen (11038973)
*
*/
public class TreeNode {
private String station;
private TreeNode parent;
private List<TreeNode> children;
/**
* Constructor
* @param station - the station to be stored in the node
*/
public TreeNode(String station) {
this.station = station;
parent = null;
children = new ArrayList<TreeNode>(); //Empty list of children
}
/**
* Sets the station in this node
* @param station - the station to be stored
*/
public void setStation(String station) {
this.station = station;
}
/**
* Returns the station in this node
* @return station
*/
public String getStation() {
return station;
}
/**
* Sets the parent of this node
* @param parent - the parent node
*/
public void setParent(TreeNode parent) {
this.parent = parent;
}
/**
* Returns the parent of this node or null if there is no parent
* @return parent
*/
public TreeNode getParent() {
return parent;
}
/**
* Adds a single child to this node
* @param newChild - the child node to be added
*/
public void addChild(TreeNode newChild) {
children.add(newChild);
newChild.setParent(this);
}
/**
* Returns a list of the children of this node
* @return children - the children of the node
*/
public List<TreeNode> getChildren() {
return children;
}
/**
* Returns the number of children this node has
* @return number of children
*/
public int getNumberOfChildren() {
return children.size();
}
/**
* Indicates whether this is a leaf node (has no children)
* @return true if the node has no children
*/
public boolean isLeaf() {
return children.isEmpty();
}
/**
* TODO print preOrder tree
*/
public void printPreOrder() {
}
/**
* TODO print postOrder tree
*/
public void printPostOrder() {
}
}
And in Main:
private static void selectHome() {
if(network != null) {
System.out.print("Please enter the name of the home station> ");
homeStation = scan.next();
if(!network.hasStation(homeStation)) { //if station does not exist
System.out.println("There is no station by the name " + homeStation + "\n");
homeStation = null;
} else {
//create the tree with homeStation as root
createTree(homeStation);
}
} else {
System.out.println("You must load a network file before choosing a home station.\n");
}
}
private static void createTree(String homeStation) {
root = new TreeNode(homeStation); //create root node with home station
//TODO Construct the tree
//get list of connecting stations from network (string[])
//and add the stations as children to the root node
for(String stationName : network.getConnections(homeStation)) {
TreeNode child = new TreeNode(stationName);
root.addChild(child);
//then for every child of the tree get connecting stations from network
//and add those as children of the child.
//TODO as long as a station doesn't already exist in the tree.
}
}
EDIT: The station input file
Connection: Rame Penlee
Connection: Penlee Rame
Connection: Rame Millbrook
Connection: Millbrook Cawsand
Connection: Cawsand Kingsand
Connection: Kingsand Rame
Connection: Millbrook Treninnow
Connection: Treninnow Millbrook
Connection: Millbrook Antony
Connection: Antony Polbathic
Connection: Polbathic Rame
This is a basic problem (I'm guessing this must be a some kind of homework), I think a simple recursion could help you solve it.
Make a function that finds every child of a node, and call this function on every child:
private static void addNodesRecursive(TreeNode node) {
for(String stationName : network.getConnections(node)) {
TreeNode child = new TreeNode(stationName);
node.addChild(child);
addNodesRecursive(child);
}
}
This only works if the graph we are making is a DAG. If the graph has any cycles in it (even a two way edge), it will fail.
It will fail because we do not yet store if a node was added to our graph before. The parent will be the connected to the child and vica-versa, they are going to be added infinitely as neighbours to each other.
The thing you can do is: make a list that stores what is added yet.
private static void addNodesRecursive(TreeNode node, List<TreeNode> addedList) {
for(String stationName : network.getConnections(node)) {
TreeNode child = new TreeNode(stationName);
node.addChild(child);
addedList.add(child);
addNodesRecursive(child, addedList);
}
}
And only add the new node if it's not on the addedList yet:
private static void addNodesRecursive(TreeNode node, List<String> addedList) {
for(String stationName : network.getConnections(node)) {
if (!addedList.contains(stationName)) {
TreeNode child = new TreeNode(stationName);
node.addChild(child);
addedList.add(child);
addNodesRecursive(child, addedList);
}
}
}
You just need to call this on the root node, so your createTree will be:
private static void createTree(String homeStation) {
root = new TreeNode(homeStation);
List<String> addedList = new ArrayList<String>();
addedList.add(homeStation);
addNodesRecursive(root, addedList);
}
And BAM you are finished. Calling createTree will create the tree starting from the root.
P.S. I'm writing this on the fly, and I did not try my code, also my Java is a little rusty, so you could expect it to contain syntax errors (like I have corrected all my strings with small s to capital S just now).
EDIT:
It is very important to be able to figure out a recursive problem on your own if you have any plans on being a programmer. A little help on how to figure out something recursive.
At least this is how I do it (and also did it while answering this :) ).