树形结构
最近看程序日志发现有一个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;}}