Java List 生成 树（转）

 

文章出自：http://www.cnblogs.com/dingyingsi/p/3699870.html

 

maven pom.xml

 

<dependency>
	<groupId>commons-collections</groupId>
	<artifactId>commons-collections</artifactId>
	<version>3.2.1</version>
</dependency>

 

 

TreeBuilder.java

 

package com.yusj;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.collections.CollectionUtils;

public class TreeBuilder {

    @SuppressWarnings("unchecked")
    private List<Node> buildListToTree(List<Node> dirs) {
        List<Node> roots = findRoots(dirs);
        List<Node> notRoots = (List<Node>) CollectionUtils
                .subtract(dirs, roots);
        for (Node root : roots) {
            root.setChildren(findChildren(root, notRoots));
        }
        return roots;
    }

    public List<Node> findRoots(List<Node> allNodes) {
        List<Node> results = new ArrayList<Node>();
        for (Node node : allNodes) {
            boolean isRoot = true;
            for (Node comparedOne : allNodes) {
                if (node.getParentId() == comparedOne.getId()) {
                    isRoot = false;
                    break;
                }
            }
            if (isRoot) {
                node.setLevel(0);
                results.add(node);
                node.setRootId(node.getId());
            }
        }
        return results;
    }

    @SuppressWarnings("unchecked")
    private List<Node> findChildren(Node root, List<Node> allNodes) {
        List<Node> children = new ArrayList<Node>();

        for (Node comparedOne : allNodes) {
            if (comparedOne.getParentId() == root.getId()) {
                comparedOne.setParent(root);
                comparedOne.setLevel(root.getLevel() + 1);
                children.add(comparedOne);
            }
        }
        List<Node> notChildren = (List<Node>) CollectionUtils.subtract(allNodes, children);
        for (Node child : children) {
            List<Node> tmpChildren = findChildren(child, notChildren);
            if (tmpChildren == null || tmpChildren.size() < 1) {
                child.setLeaf(true);
            } else {
                child.setLeaf(false);
            }
            child.setChildren(tmpChildren);
        }
        return children;
    }
    
    private List<Node> getLeafChildren(List<Node> resultList, List<Node> children){
    	for(Node node : children){
    		if(node.isLeaf()){
    			resultList.add(node);
    		}else{
    			getLeafChildren(resultList, node.getChildren());
    		}
    	}
    	return resultList;
    }

    public static void main(String[] args) {
        TreeBuilder tb = new TreeBuilder();
        List<Node> allNodes = new ArrayList<Node>();
        allNodes.add(new Node(1, 0, "节点1"));
        allNodes.add(new Node(2, 0, "节点2"));
        allNodes.add(new Node(3, 0, "节点3"));
        allNodes.add(new Node(4, 1, "节点4"));
        allNodes.add(new Node(5, 1, "节点5"));
        allNodes.add(new Node(6, 1, "节点6"));
        allNodes.add(new Node(7, 4, "节点7"));
        allNodes.add(new Node(8, 4, "节点8"));
        allNodes.add(new Node(9, 5, "节点9"));
        allNodes.add(new Node(10, 5, "节点10"));
        allNodes.add(new Node(11, 7, "节点11"));
        allNodes.add(new Node(12, 7, "节点12"));
        // 显示所有节点
        List<Node> roots = tb.buildListToTree(allNodes);
        for (Node n : roots) {
            System.out.println(n);
        }
        System.out.println("------------------");
		// 查找所有子节点
        List<Node> children = tb.findChildren(new Node(1, 0, "节点1"), allNodes);
        for (Node n : children) {
        	System.out.println(n);
        }
        // 查找所有叶子节点
        System.out.println("------------------");
        List<Node> resultList = tb.getLeafChildren(new ArrayList<Node>(), children);
        for (Node n : resultList) {
        	System.out.println(n);
        }
        
    }
}

 

 

Node.java

 

package com.yusj;

import java.util.List;

public class Node implements java.io.Serializable {
    private static final long serialVersionUID = -2721191232926604726L;

    private int id;

    private int parentId;

    private Node parent;

    private List<Node> children;

    private String name;

    private int level;

    private int sort;

    private int rootId;

    private String type;

    private boolean isLeaf;

    private String description;

    public Node() {
        super();
    }

    public Node(int id, int parentId, String name) {
        super();
        this.id = id;
        this.parentId = parentId;
        this.name = name;
    }

    public String getDescription() {
        return description;
    }

    public void setDescription(String description) {
        this.description = description;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Node getParent() {
        return parent;
    }

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

    public int getParentId() {
        return parentId;
    }

    public void setParentId(int parentId) {
        this.parentId = parentId;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getLevel() {
        return level;
    }

    public void setLevel(int level) {
        this.level = level;
    }

    public String getType() {
        return type;
    }

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

    public void setChildren(List<Node> children) {
        this.children = children;
    }

    public void setType(String type) {
        this.type = type;
    }

    public boolean isLeaf() {
        return isLeaf;
    }

    public void setLeaf(boolean isLeaf) {
        this.isLeaf = isLeaf;
    }

    public int getSort() {
        return sort;
    }

    public void setSort(int sort) {
        this.sort = sort;
    }

    public int getRootId() {
        return rootId;
    }

    public void setRootId(int rootId) {
        this.rootId = rootId;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + id;
        result = prime * result + parentId;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node other = (Node) obj;
        if (id != other.id)
            return false;
        if (parentId != other.parentId)
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Node {id=" + id + ", parentId=" + parentId + ", children="
                + children + ", name=" + name + ", level =" + level + ", isLeaf =" + isLeaf + "}";
    }
}

 

 

 

shell

---------所有节点---------
Node {id=1, parentId=0, children=[Node {id=4, parentId=1, children=[Node {id=7, parentId=4, children=[Node {id=11, parentId=7, children=[], name=节点11, level =3, isLeaf =true}, Node {id=12, parentId=7, children=[], name=节点12, level =3, isLeaf =true}], name=节点7, level =2, isLeaf =false}, Node {id=8, parentId=4, children=[], name=节点8, level =2, isLeaf =true}], name=节点4, level =1, isLeaf =false}, Node {id=5, parentId=1, children=[Node {id=9, parentId=5, children=[], name=节点9, level =2, isLeaf =true}, Node {id=10, parentId=5, children=[], name=节点10, level =2, isLeaf =true}], name=节点5, level =1, isLeaf =false}, Node {id=6, parentId=1, children=[], name=节点6, level =1, isLeaf =true}], name=节点1, level =0, isLeaf =false}
Node {id=2, parentId=0, children=[], name=节点2, level =0, isLeaf =false}
Node {id=3, parentId=0, children=[], name=节点3, level =0, isLeaf =false}
---------<节点1>子节点---------
Node {id=4, parentId=1, children=[Node {id=7, parentId=4, children=[Node {id=11, parentId=7, children=[], name=节点11, level =3, isLeaf =true}, Node {id=12, parentId=7, children=[], name=节点12, level =3, isLeaf =true}], name=节点7, level =2, isLeaf =false}, Node {id=8, parentId=4, children=[], name=节点8, level =2, isLeaf =true}], name=节点4, level =1, isLeaf =false}
Node {id=5, parentId=1, children=[Node {id=9, parentId=5, children=[], name=节点9, level =2, isLeaf =true}, Node {id=10, parentId=5, children=[], name=节点10, level =2, isLeaf =true}], name=节点5, level =1, isLeaf =false}
Node {id=6, parentId=1, children=[], name=节点6, level =1, isLeaf =true}
--------<节点1>叶子节点----------
Node {id=11, parentId=7, children=[], name=节点11, level =3, isLeaf =true}
Node {id=12, parentId=7, children=[], name=节点12, level =3, isLeaf =true}
Node {id=8, parentId=4, children=[], name=节点8, level =2, isLeaf =true}
Node {id=9, parentId=5, children=[], name=节点9, level =2, isLeaf =true}
Node {id=10, parentId=5, children=[], name=节点10, level =2, isLeaf =true}
Node {id=6, parentId=1, children=[], name=节点6, level =1, isLeaf =true}