树形结构

    最近看程序日志发现有一个DAO层的statement有问题，后来发现是在数据库中递归时发生的，索性今天做了个树形的模型，把数据库的东东查出来统统放到里边去。然后自己输出树形结构。
     最终得到是一个已经排序的list，里边的model包含深度。

     问题有如下：
     1.该树型结构只是简单用了java中的集合类，性能还有待进一步提高，但是如果你想处理一般问题比如菜单，模块授权之类的东东那么一点问题都没有（我一千多个主题区非常快，建议用缓存如memcached、coherence）。
     2.我发现在排序字段都一样的情况下，数据库递归出来的顺序和该模型出来的顺序是有细微差别的，因为数据库在排序字段一致的情况下又按照某种规则来排序的。

      先让大家拍拍砖，后期会重构下。

     为了更好的扩展，id和父id都用了String类型。
代码如下：

public interface INode{
	
	public String getNodeId();
	
	public String getParentNodeId();

	public int getNodeDepth();

	public void setNodeDepth(int depth);
	
	public int getNodeSort();
	
	public String getNodeName();

	public List<INode> getChildren();
	
	public void addChildNode(INode node);
	
	public boolean equals(INode obj);
}

package treemodel;

public class NodeRepository {

	private List<INode> rootNodes = new ArrayList<INode>();//根节点集合用于递归开始
	private List<INode> nodes     = new ArrayList<INode>();//所有节点的集合

	private String rootKey        = null;//根节点null表示自己寻找根节点

	private Map<String, String> ids  = new HashMap<String, String>();//适合没有指定根节点的情况

	private List<INode> _nodes    = new ArrayList<INode>();//结果可以直接在视图迭代

	public boolean addNode(INode new_node) {
		if (null == new_node) {
			return false;
		}
		
		if (nodes.contains(new_node)) {
			return false;
		}

		for (INode cur_node : nodes) {
			//新节点是当前节点的子节点
			if ( new_node.getParentNodeId().equals(cur_node.getNodeId()) ) {
				new_node.setNodeDepth(cur_node.getNodeDepth() + 1);
				cur_node.addChildNode(new_node);
			}
			//新节点是当前节点的父节点
			if ( new_node.getNodeId().equals(cur_node.getParentNodeId()) ) {
				if (cur_node.getNodeDepth() > 0) {
					new_node.setNodeDepth(cur_node.getNodeDepth() - 1);
				} else {
					//如果当前节点的深度还是0那么必须递归更改子节点的深度
					buildDepth(cur_node);
				}
				new_node.addChildNode(cur_node);
			}
		}

		nodes.add(new_node);
		ids.put(new_node.getNodeId(), "0");

		if (rootKey != null) {
			//如果指定根节点，则直接加入根节点集合
			if ( rootKey.equals(new_node.getParentNodeId()) ) {
				rootNodes.add(new_node);
			}
		}

		return true;
	}

	public List<INode> generateTree() {
		if (rootKey == null) {
			//如果没有指定根节点，则必须判断根节点
			generateRootNodes();
		}

		sort(rootNodes);//根节点排序
		Iterator<INode> iter_nodes = rootNodes.listIterator();
		while (iter_nodes.hasNext()) {
			//开始递归节点
			buildTree(iter_nodes.next());
		}
		return _nodes;
	}

	private void generateRootNodes() {
		Iterator<INode> iter_nodes = nodes.listIterator();
		INode node = null;
		while (iter_nodes.hasNext()) {
			node = iter_nodes.next();
			if (!ids.containsKey(node.getParentNodeId())) {
				rootNodes.add(node);
			}
		}
	}

	//递归深度
	private void buildDepth(INode node) {
		node.setNodeDepth(node.getNodeDepth() + 1);
		if (node.getChildren().size() > 0) {
			for (INode n : node.getChildren()) {
				buildDepth(n);
			}
		}
	}

	private void buildTree(INode a_node) {
		_nodes.add(a_node);//加入结果集合
		List<INode> childen = a_node.getChildren();
		if (childen.size() > 0) {
			sort(childen);
			for (INode node : childen) {
				buildTree(node);
			}
		}
	}
	
	//子节点排序
	private void sort(List<INode> items) {
		Collections.sort(items, new Comparator<INode>() {
			public int compare(INode o1, INode o2) {
				if (o1.getNodeSort() > o2.getNodeSort()) {
					return 1;
				} else if (o1.getNodeSort() < o2.getNodeSort()) {
					return -1;
				} else {
					return 0;
				}
			}
		});
	}

	public void setRootKey(String rootKey) {
		this.rootKey = rootKey;
	}
}