Java crea múltiples estructuras tipo árbol usando la identificación principal del archivo plano

Tengo datos como abajo

CategoryId  CategoryName  CategoryParentId
123         XYZ           111
111         ABC           
222         PQR           
555         DEF           111
321         IJK           222

Si ve esto, se leen datos desordenados de un archivo plano que puede estar en cualquier orden.

Quiero crear árboles como a continuación:

111
|  \
123 555  

y

222
\
321

Tengo estos datos en un objeto, que se ve a continuación:

public class Category {
    private String id = null;
    private String name = null;
    private String parentId = null;

    public Category(String id, String name, String parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }
}

Estoy tratando de procesar estos datos para crear una lista de árbol de categorías.

public class CategoryTree {
    private String name     = null;
    private String id       = null;

    private CategoryTree<String, CategoryTree> children = new TreeMap<String, CategoryTree>();


    public CategoryTree() {
    }

    public CategoryTree(String name, String id) {
        setName(name);
        setId(id);
    }

    public TreeMap<String, CategoryTree> getChildren() {
        return this.children;
    }

    public CategoryTree getChild(String childId) {
        return this.children.get(childId);
    }

    public void setChild(CategoryTree child) {
        this.children.put(child.getId(), child);
    }

    public boolean hasChild(String childId) {
        TreeMap<String, CategoryTree> set = this.children;
        boolean result =  set.containsKey(childId);
        return result;
    }
}

A continuación se muestra lo que estoy tratando de hacer:

public void processData(List categoryList) {
    List<CategoryTree> roleObjectList = new ArrayList<CategoryTree>();

    Iterator<Category> itr = categoryList.iterator();
    while (itr.hasNext()) {
        Category entry = itr.next();
        String id = entry.getId();
        String name = entry.getName();
        String parentId = entry.getParentId();

        // i am confused here
        // CategoryTree parent = new CategoryTree(name,  id);
           parent.addChild(entry);
    }
}

Estoy confundido en esta parte. Cómo comenzar el árbol. Dado que la entrada en la primera iteración del bucle tiene padre pero aún no está presente en la lista final. Cómo agregar la primera entrada a su padre.

Puedes construir tu árbol de forma recursiva. El primer paso será extraer las raíces de tus árboles. Luego, cree una función que obtenga los hijos directos de cada nodo ejecutando en la lista ( O(n)): dentro habrá una llamada recursiva para cada uno de los hijos.

Supongo que mi JAVAsintaxis es pequeña pero oxidada, así que este es el pseudocódigo:

function getChildren(nodeID, listOfNodes):
    childrenList = empty list 
    for each node in listOfNodes:
        if node.parentId == nodeID: // if node is direct child
            node.children = getChildren(node.id, listOfNodes); //recursively get all his children 
            childrenList.add(node) // add it to the children list
    return childrenList;

main:
     listOfNodes = get list from your file
     listOfRoots = init empty list
     for each node in listOfNodes:
         if (node.parentId is empty) //not parent
             listOfRoots.add(node)
     // now listOfRoots is has all the roots
     for each node in listOfRoots:
         node.children = getChildren(node.id, listOfNodes)

Esto será en O(n^2)complejidad. 2 mejora inmediata que puede hacer es guardar el listOfNode en el objeto y usarlo thispara no tener que sobrecargar la memoria. En segundo lugar, puede modificar la lista cada vez y eliminar el nodo que asigna (ya que no se puede asignar dos veces ...)

¡Espero que ayude!