I am developing a Java application to create a backup of multiple directories into another location, in order to do some optimizations I needed to extract some information from the directory tree and keep it in memory.

Java I/O provides a nice bidirectional structure (the tree can be traversed either starting from the root or the leaves), but in my backup program I needed additional attributes to each node, and be able to add events. Due to its ability to represent hierarchies such as a file system, an n-ary tree was elected as the data structure to hold the file structure and additional information.

Essentially, I had to introduce only one new data structure in order to model an n-ary tree, the Node class, its source code is shown in Figure 1. A Node holds a generic payload object, a List of children Nodes, and a reference to the parent Node. This way the resulting tree can be traversed in both directions.

[code language=’java’ start=’1′] import java.util.List;

/**
* N-Ary tree node.
*
* @author Ivan Zilotti Alencar
* @param <P> Payload type.
*/
public class Node<P> {

/** Payload */
private P payload;

/** Parent */
private Node<P> parent;

/** Children */
private List<Node<P>> children;

public Node(P payload) {
super();
this.payload = payload;
}

public P getPayload() {
return payload;
}

public void setPayload(P payload) {
this.payload = payload;
}

public Node<P> getParent() {
return parent;
}

public void setParent(Node<P> parent) {
this.parent = parent;
}

public List<Node<P>> getChildren() {
return children;
}

public void setChildren(List<Node<P>> children) {
this.children = children;
}
}
[/code] Figure 1 – Node.java

Building the tree is quite simple, since the “navigation” mechanisms provided by java.io.File resemble the ones available in the Node class. I used the java.io.File class as payload in the example below, but obviously anything can be carried by the Node.payload reference.

[code language=’java’ start=’1′] import java.io.File;
import java.util.LinkedList;
import java.util.List;

public class TreeLoader {

private static final String STARTING_PATH = "J:\Test_Folder";

public static void main(String[] args) {
TreeLoader tt = new TreeLoader();
Node<File> rootNode = tt.getTree(STARTING_PATH);
tt.printTree(rootNode);
}

/**
* Traverses the tree starting from the root node and
* prints out the paths to files and directories associated
* each node.
*
* @param rootNode Tree’s root node.
*/
private void printTree(Node<File> rootNode) {
for(Node<File> node : rootNode.getChildren()) {
System.out.println(node.getPayload().getPath());
if(node.getPayload().isDirectory()) {
printTree(node);
}
}
}

/**
* Loads the tree representing the directory structure under the starting directory path specified.
*
* @param startingDirPath Base directory.
* @return A Node<File> representing.
*/
private Node<File> getTree(String startingDirPath) {
Node<File> rootNode = new Node<File>(new File(startingDirPath));
rootNode.setChildren(this.getSubTree(rootNode));
return rootNode;
}

/**
* Gets all sub-trees under the node passed.
*
* @param dirNode A directory tree node.
* @return A list of Nodes<File> containing the whole sub-tree.
*/
private List<Node<File>> getSubTree(Node<File> dirNode) {
List<Node<File>> children = new LinkedList<Node<File>>();
for(File entry : getFilesDirsDir(dirNode.getPayload())) {
Node<File> node = new Node<File>(new File(entry.getPath()));
node.setParent(dirNode);
children.add(node);
if(entry.isDirectory()) {
node.setChildren(getSubTree(node));
}
}
return children;
}

/**
* Obtains files and directories under the specified directory.
*
* @param dir
* @return
*/
private List<File> getFilesDirsDir(File dir) {
List<File> filesDirs = new LinkedList<File>();
for(File f : dir.listFiles())
filesDirs.add(new File(f.getPath()));
return filesDirs;
}
}
[/code] Figure 2 – TreeLoader.java