There are multiple ways of storing Tree structure in database. The most prominent and not so efficient way is
key parentkey
1 0
2 1
3 2
4 3
Lots of people generally have requirement where in they have to build tree given any node in the whole chain. The above tree as you is a multidimentional tree as in there can be 0-n parents and 0-n children for any given node. If we have build it in C or C++ we would have taken an approach of Multi-Linked List.
It Has become much simpler in java with advent of Generic in Java 5. I ‘m going to show you a very generic version of buildign tree which can be used any where
Basic element of any tree is the Node
import java.util.ArrayList;
import java.util.List;
/**
* Represents a node of the Tree class. The Node is also a container, and
* can be thought of as instrumentation to determine the location of the type T
* in the Tree.
*
* @author kumara
*/
public class Node {
public T data;
public List<Node> children;
public List<Node> parents;
/**
* Default ctor.
*/
public Node() {
super();
}
/**
* Convenience ctor to create a Node with an instance of T.
*
* @param data
* an instance of T.
*/
public Node(T data) {
this();
setData(data);
}
/**
* Return the children of Node. The Tree is represented by a single
* root Node whose children are represented by a List<Node>. Each of
* these Node elements in the List can have children. The getChildren()
* method will return the children of a Node.
*
* @return the children of Node
*/
public List<Node> getChildren() {
if (this.children == null) {
return new ArrayList<Node>();
}
return this.children;
}
/**
* Sets the children of a Node object. See docs for getChildren() for
* more information.
*
* @param children
* the List<Node> to set.
*/
public void setChildren(List<Node> children) {
this.children = children;
}
/**
* Returns the number of immediate children of this Node.
*
* @return the number of immediate children.
*/
public int getNumberOfChildren() {
if (children == null) {
return 0;
}
return children.size();
}
/**
* Adds a child to the list of children for this Node. The addition of
* the first child will create a new List<Node>.
*
* @param child
* a Node object to set.
*/
public void addChild(Node child) {
if (children == null) {
children = new ArrayList<Node>();
}
children.add(child);
}
/**
* Inserts a Node at the specified position in the child list. Will *
* throw an ArrayIndexOutOfBoundsException if the index does not exist.
*
* @param index
* the position to insert at.
* @param child
* the Node object to insert.
* @throws IndexOutOfBoundsException
* if thrown.
*/
public void insertChildAt(int index, Node child)
throws IndexOutOfBoundsException {
if (index == getNumberOfChildren()) {
// this is really an append
addChild(child);
return;
} else {
children.get(index); // just to throw the exception, and stop here
children.add(index, child);
}
}
/**
* Remove the Node element at index index of the List<Node>.
*
* @param index
* the index of the element to delete.
* @throws IndexOutOfBoundsException
* if thrown.
*/
public void removeChildAt(int index) throws IndexOutOfBoundsException {
children.remove(index);
}
/**
* Return the parents of Node. The Tree is represented by a single
* root Node whose parents are represented by a List<Node>. Each of
* these Node elements in the List can have parents. The getparent()
* method will return the parents of a Node.
*
* @return the children of Node
*/
public List<Node> getParents() {
if (this.parents == null) {
return new ArrayList<Node>();
}
return this.parents;
}
/**
* Sets the parents of a Node object. See docs for getparent() for
* more information.
*
* @param parents
* the List<Node> to set.
*/
public void setParents(List<Node> parent) {
this.parents = parent;
}
/**
* Returns the number of immediate parents of this Node.
*
* @return the number of immediate parents.
*/
public int getNumberOfParents() {
if (parents == null) {
return 0;
}
return parents.size();
}
/**
* Adds a child to the list of children for this Node. The addition of
* the first child will create a new List<Node>.
*
* @param child
* a Node object to set.
*/
public void addParent(Node parent) {
if (parents == null) {
parents = new ArrayList<Node>();
}
parents.add(parent);
}
/**
* Inserts a Node at the specified position in the child list. Will *
* throw an ArrayIndexOutOfBoundsException if the index does not exist.
*
* @param index
* the position to insert at.
* @param child
* the Node object to insert.
* @throws IndexOutOfBoundsException
* if thrown.
*/
public void insertParentAt(int index, Node parent)
throws IndexOutOfBoundsException {
if (index == getNumberOfChildren()) {
// this is really an append
addParent(parent);
return;
} else {
parents.get(index); // just to throw the exception, and stop here
parents.add(index, parent);
}
}
/**
* Remove the Node element at index index of the List<Node>.
*
* @param index
* the index of the element to delete.
* @throws IndexOutOfBoundsException
* if thrown.
*/
public void removeParentAt(int index) throws IndexOutOfBoundsException {
parents.remove(index);
}
/**
* @return
*/
public T getData() {
return this.data;
}
/**
* @param data
*/
public void setData(T data) {
this.data = data;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(this.data.toString());
/* sb.append("{").append(getData().toString()).append(",[");
int i = 0;
boolean addComma = false;
for (Node e : getParents()) {
if (i > 0) {
addComma = true;
sb.append(",");
}
sb.append(e.getData().toString());
i++;
}
i = 0;
for (Node e : getChildren()) {
if (addComma || i > 0) {
sb.append(",");
}
sb.append(e.getData().toString());
i++;
}
sb.append("]").append("}");*/
return sb.toString();
}
}
And tree is List of Node’s
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
/**
* Represents a Tree of Objects of generic type T. The Tree is represented as a
* single rootElement which points to a List<Node> of children. There is no
* restriction on the number of children that a particular node may have. This
* Tree provides a method to serialize the Tree into a List by doing a pre-order
* traversal. It has several methods to allow easy updation of Nodes in the
* Tree.
*
* @author kumara
*/
public class Tree {
private Node rootElement;
/**
* Default ctor.
*/
public Tree() {
super();
}
/**
* Return the root Node of the tree.
*
* @return the root element.
*/
public Node getRootElement() {
return this.rootElement;
}
/**
* Set the root Element for the tree.
*
* @param rootElement
* the root element to set.
*/
public void setRootElement(Node rootElement) {
this.rootElement = rootElement;
}
/**
* Returns the Tree as a List of Node objects. The elements of the
* List are generated from a pre-order traversal of the tree.
*
* @return a List<Node>.
*/
public List<Node> toList() {
List<Node> list = new ArrayList<Node>();
walk(rootElement, list);
return list;
}
/**
* Returns a String representation of the Tree. The elements are generated
* from a pre-order traversal of the Tree.
*
* @return the String representation of the Tree.
*/
public String toString() {
return toList().toString();
}
/**
* Walks the Tree in pre-order style. This is a recursive method, and is
* called from the toList() method with the root element as the first
* argument. It appends to the second argument, which is passed by reference
* * as it recurses down the tree.
*
* @param element
* the starting element.
* @param list
* the output of the walk.
*/
private void walk(Node element, List<Node> list) {
for (Node data : element.getParents()) {
walk(data, list);
}
list.add(element);
for (Node data : element.getChildren()) {
walk(data, list);
}
}
public String toBranch(List branches) {
return toBranches(branches).toString();
}
public List<Node> toBranches(List branches) {
List<Node> list = new ArrayList<Node>();
List pathList = new ArrayList();
branch(rootElement, list,pathList,branches);
return list;
}
private void branch(Node element, List<Node> list,List pathList,List branches) {
for (Node data : element.getParents()) {
parentBranch(data, list,pathList);
}
// Add to path
pathList.add(element.getData().toString());
list.add(element);
for (Node data : element.getChildren()) {
childBranch(data, list,pathList,branches);
pathList.remove(pathList.size()-1);
}
if(element.getChildren().isEmpty()){
printArray(pathList,branches);
}
//System.out.println(path);
}
/**
* @param element
* @param list
* @param pathList
*/
private void childBranch(Node element, List<Node> list,List pathList,List branches) {
// Add to path
pathList.add(element.getData().toString());
list.add(element);
for (Node data : element.getChildren()) {
childBranch(data, list,pathList,branches);
pathList.remove(pathList.size()-1);
}
if(element.getChildren().isEmpty()){
printArray(pathList,branches);
}
}
/**
* @param element
* @param list
* @param pathList
*/
private void parentBranch(Node element, List<Node> list,List pathList) {
for (Node data : element.getParents()) {
parentBranch(data, list,pathList);
}
// Add to path
pathList.add(element.getData().toString());
list.add(element);
}
/**
* @param array
*/
private void printArray(Collection array,List branches){
StringBuffer sb = new StringBuffer();
for(String pathElement :array){
sb.append(pathElement).append(",");
}
branches.add(sb.toString());
//System.out.println(sb.toString());
}
}
Lets create a Task class for which we will build a tree
import java.io.Serializable;
import org.apache.commons.lang.builder.ReflectionToStringBuilder;
import org.apache.commons.lang.builder.ToStringStyle;
/**
* @author kumara
*
*/
public class GenericTask implements Serializable {
private Long id = 0L;
private Long parentId = 0L;
public GenericTask() {
super();
}
public GenericTask(Long taskId) {
this();
setId(taskId);
}
public GenericTask(Long taskId,Long parentTaskId) {
this();
setId(taskId);
setParentId(parentTaskId);
}
/**
* @return the id
*/
public Long getId() {
return id;
}
/**
* @param id
* the id to set
*/
public void setId(Long id) {
this.id = id;
}
/**
* @return the parentId
*/
public Long getParentId() {
return parentId;
}
/**
* @param parentId
* the parentId to set
*/
public void setParentId(Long parentId) {
this.parentId = parentId;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
public String toString() {
/*return ReflectionToStringBuilder.reflectionToString(this,
ToStringStyle.DEFAULT_STYLE);*/
//return "["+id+","+parentId+"]";
return id+"";
}
}
Above code is Generic code which can be implemented any where. For example let us assume we have some tasks for which we have to build this tree. We will just implement Tree and Node for that task like this
/**
* Non-generic subclass of Tree
*
* @author kumara
*/
public class TaskTree extends Tree {
public TaskTree() {
super();
}
}
/**
* Non-generic subclass of Node
*
* @author kumara
*/
public class TaskNode extends Node {
public TaskNode() {
super();
}
}
Now the task is to load data from Database to javaObjects. We shall use TaskDAO to do that
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;
import org.springframework.jdbc.support.rowset.SqlRowSet;
/**
* Dao for the Task POJO.
*
* @author kumara
*/
public class TaskDAO extends AbstractDAO {
private String childColumnName = "";
private String parentColumnName = "";
private String tableName = "";
private final static Logger log = Logger
.getLogger(TaskDAO.class.toString());
public TaskDAO() {
}
/**
* @return the childColumnName
*/
public String getChildColumnName() {
return childColumnName;
}
/**
* @param childColumnName
* the childColumnName to set
*/
public void setChildColumnName(String childColumnName) {
this.childColumnName = childColumnName;
}
/**
* @return the parentColumnName
*/
public String getParentColumnName() {
return parentColumnName;
}
/**
* @param parentColumnName
* the parentColumnName to set
*/
public void setParentColumnName(String parentColumnName) {
this.parentColumnName = parentColumnName;
}
/**
* @return the tableName
*/
public String getTableName() {
return tableName;
}
/**
* @param tableName
* the tableName to set
*/
public void setTableName(String tableName) {
this.tableName = tableName;
}
/**
* Remove a Task object from the database.
*
* @param task
* the Task to remove.
*/
public void remove(GenericTask task) {
}
/**
* Saves a Task to the database if it is a new one, else updates it.
*
* @param task
* the Task to insert or update.
* @return the task id.
*/
public Long saveOrUpdate(GenericTask task) {
return 1L;
}
/**
* Returns the Task pointed to by the task id. Returns a NULL if the Task is
* not found in the database.
*
* @param taskId
* the task id to look up.
* @return the Task object corresponding to the id.
*/
public GenericTask get(Long taskId) {
return new GenericTask(taskId);
}
/**
* Returns all the children of the Task which has the specified parents id.
*
* @param parentId
* the id of the parents Task.
* @return a List of Tasks which are children of the Task specified.
*/
@SuppressWarnings("unchecked")
public List findByParentId(Long parentId) {
if(parentId == null){
return Collections.EMPTY_LIST;
}
try {
getJdbcTemplate().execute(
"set lockmode session where readlock = nolock");
} catch (Exception e) {
}
String sql = "SELECT * FROM " + getTableName() + " WHERE "
+ getParentColumnName() + " = " + parentId;
SqlRowSet resultSet = (SqlRowSet) getJdbcTemplate().queryForRowSet(sql);
List returnList = new ArrayList();
while (resultSet.next()) {
GenericTask genericTask = new GenericTask(
resultSet.getLong(getChildColumnName()));
genericTask.setParentId(resultSet.getLong(getParentColumnName()));
returnList.add(genericTask);
}
return returnList;
}
/**
* Returns all the Parents of the Task which has the specified child id.
*
* @param childId
* the id of the child Task.
* @return a List of Tasks which are parent of the Task specified.
*/
@SuppressWarnings("unchecked")
public List findByChildId(Long childId) {
if(childId == null){
return Collections.EMPTY_LIST;
}
try {
getJdbcTemplate().execute(
"set lockmode session where readlock = nolock");
} catch (Exception e) {
}
String sql = "SELECT * FROM " + getTableName() + " WHERE "
+ getChildColumnName() + " = " + childId;
SqlRowSet resultSet = (SqlRowSet) getJdbcTemplate().queryForRowSet(sql);
List returnList = new ArrayList();
while (resultSet.next()) {
GenericTask genericTask = new GenericTask(
resultSet.getLong(getChildColumnName()));
genericTask.setParentId(resultSet.getLong(getParentColumnName()));
returnList.add(genericTask);
}
return returnList;
}
}
Now Lets build Tree using TaskTreeDAO
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.logging.Logger;
/**
* @author kumara
*
* Data Access Object for the TaskTree object. This is not a true Dao, since it
* delegates to the TaskDao object for any database operations.
*/
public class TaskTreeDAO {
private static final Logger log = Logger.getLogger(TaskTreeDAO.class
.toString());
public TaskTreeDAO() {
super();
}
private TaskDAO taskDao;
public void setTaskDao(TaskDAO taskDao) {
this.taskDao = taskDao;
}
/**
* Saves a TaskTree object.
*
* @param taskTree
* a TaskTree object.
*/
public void saveOrUpdate(TaskTree taskTree) {
List<Node> tasks = taskTree.toList();
// save the tree in reverse order, starting from the leaf nodes
// and going up to the root of the tree.
int numberOfNodes = tasks.size();
for (int i = numberOfNodes - 1; i >= 0; i--) {
Node taskElement = tasks.get(i);
GenericTask task = taskElement.getData();
// taskDao.saveOrUpdate(task);
Long parentId = task.getId();
for (Iterator<Node> it = taskElement.getChildren()
.iterator(); it.hasNext();) {
Node childElement = it.next();
GenericTask childTask = childElement.getData();
childTask.setParentId(parentId);
// taskDao.saveOrUpdate(childTask);
}
}
}
/**
* Gets a single TaskTree by id. This is the head of a recursive method call
* to getRecursive().
*
* @param id
* the id of the TaskTree.
* @return a TaskTree for that id.
*/
public TaskTree get(Long id) {
TaskTree taskTree = new TaskTree();
Node rootElement = new Node(new GenericTask(id,id));
getRecursiveChildren(rootElement, taskTree);
getRecursiveParents(rootElement, taskTree);
taskTree.setRootElement(rootElement);
return taskTree;
}
/**
* Recursively descends the Tree and populates the TaskTree object.
*
* @param taskElement
* the root Node.
* @param tree
* the TaskTree object to populate.
*/
private void getRecursiveChildren(Node taskElement, TaskTree tree) {
List children = taskDao.findByParentId(taskElement
.getData().getId());
List<Node> childElements = new ArrayList<Node>();
for (Iterator it = children.iterator(); it.hasNext();) {
GenericTask childTask = it.next();
Node childElement = new Node(childTask);
childElements.add(childElement);
childElement.addParent(taskElement);
getRecursiveChildren(childElement, tree);
}
taskElement.setChildren(childElements);
}
/**
* Recursively descends the Tree and populates the TaskTree object.
*
* @param taskElement
* the root Node.
* @param tree
* the TaskTree object to populate.
*/
private void getRecursiveParents(Node taskElement, TaskTree tree) {
List parents = taskDao.findByChildId(taskElement
.getData().getParentId());
List<Node> parentElements = new ArrayList<Node>();
for (Iterator it = parents.iterator(); it.hasNext();) {
GenericTask parentTask = it.next();
Node parentElement = new Node(parentTask);
parentElements.add(parentElement);
parentElement.addChild(taskElement);
getRecursiveParents(parentElement, tree);
}
taskElement.setParents(parentElements);
}
/**
* @param id
* @return
*/
public TaskTree buildTree(Long id) {
TaskTree taskTree = new TaskTree();
Node rootElement = new Node(taskDao.get(id));
getRecursiveChildren(rootElement, taskTree);
getRecursiveParents(rootElement, taskTree);
taskTree.setRootElement(rootElement);
return taskTree;
}
}
And some Utility Classes as i use Spring-JDBC here
import org.springframework.jdbc.core.JdbcTemplate;
import endoworks.dwutility.framework.util.ServiceLocator;
import endoworks.dwutility.framework.util.spring.SpringInitilizer;
/**
* @author kumara
*
*/
public class AbstractDAO {
private static SpringInitilizer springInitilizer = null;
static {
springInitilizer = new SpringInitilizer();
}
private JdbcTemplate jdbcTemplate;
/**
* @return the jdbcTemplate
*/
public JdbcTemplate getJdbcTemplate() {
if (jdbcTemplate == null) {
jdbcTemplate = (JdbcTemplate) ServiceLocator
.getService("jdbcTemplate");
}
return jdbcTemplate;
}
}
A class to load/Initialize spring beans
import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;
/**
* @author Ashwin
*
*/
public class SpringInitilizer {
private static ApplicationContext context = null;
static {
context = new ClassPathXmlApplicationContext(
new String[] { "applicationContext-dbMigrate.xml" });
}
}
And finally data base table can be of form
create table test (key integer,parentkey integer);
Njoy creating any tree easily
Technology Portal 