ツリー構造リストを親子順にソート

package com.naydog;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *   ：            ，                
 *             ，       
 *    id，   pid  ，        
 */
public class SortByParentAndChild {

    public static List sortParentAndChild(List entities) {
        // 1.            
        Map> pMap = new HashMap>(); //     key
        Set ids = new HashSet(); //     id
        Set pids = new HashSet(); //     id
        for (E entity : entities) {
            ids.add(entity.getId());
            String pid = entity.getPid();
            pids.add(pid);
            if(null == pMap.get(pid)) {
                pMap.put(pid, new ArrayList());
            }
            pMap.get(pid).add(entity);
        }
        pids.removeAll(ids); //      

        // [OPTIONAL]   id  ，  
        if (ids.size() < entities.size()) {
            return null;
        }

        // 2.     
        List sortedList= new ArrayList();
        for (String rootPid : pids) {
            List queue = pMap.remove(rootPid);
            if (null != queue) {
                while(queue.size() > 0) {
                    E entity = queue.remove(0);
                    sortedList.add(entity);
                    List tmpList = pMap.remove(entity.getId());
                    if (null != tmpList) {
                        queue.addAll(tmpList);
                    }
                }
            }
        }
        return sortedList;
    }

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(new E("A2", "A1"));
        list.add(new E("A1", "0"));
        list.add(new E("A3", "A1"));
        list.add(new E("C1", "1"));
        list.add(new E("B3", "B2"));
        list.add(new E("B2", "B1"));
        list.add(new E("B1", "0"));
        System.out.println(sortParentAndChild(list));
    }
}

/**
 *   
 */
class E {
    private String id;
    private String pid;

    public E(String id, String pid) {
        this.id = id;
        this.pid = pid;
    }

    public String getId() {
        return id;
    }
    public void setId(String id) {
        this.id = id;
    }
    public String getPid() {
        return pid;
    }
    public void setPid(String pid) {
        this.pid = pid;
    }

    @Override
    public String toString() {
        return "E [id=" + id + ", pid=" + pid + "]";
    }

}