欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java List 生成 树(转)

程序员文章站 2022-06-18 08:55:06
...

 

文章出自: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}