Java создать несколько древовидной структуры, используя родительский идентификатор из плоского файла

Question

У меня есть данные, как показано ниже

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

Если вы видите это неупорядоченные данные, считанные из плоского файла, который может быть в любом порядке.

Я хочу создать деревья, как показано ниже:

111
|  \
123 555  

и

222
\
321

У меня есть эти данные в объекте, который выглядит следующим образом:

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;
    }
}

Я пытаюсь обработать эти данные для создания списка дерева категорий.

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;
    }
}

Ниже я пытаюсь сделать следующее:

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);
    }
}

Я запутался в этой части. Как запустить дерево. Поскольку запись в первой итерации цикла имеет родителя, но его родитель еще не представлен в окончательном списке. Как добавить первую запись к своему родителю.

Answer 1

Кажется, что parent.id < child.id выполняется, то есть родитель создается первым. Хотя это и не обязательно, иногда это может облегчить ситуацию.

Здесь это не нужно.

public void processData(List<Category> categoryList) {
    Map<String, CategoryTree> map = categoryList.collect(
            Collectors.toMap(cat -> cat.id,
                             cat -> new CategoryTree(id, name)));
    List<CategoryTree> treeRoots = new ArrayList<>(); // Forrest if more than one root.
    categoryList.forEach(cat -> {
        CategoryTree node = map.get(cat.id);
        if (cat.parentId != null) {
            CategoryTree parent = map.get(cat.parentId)
            parent.children.add(node );
        } else {
            treeRoots.add(node );
        }
    });
    List<CategoryTree> roleObjectList = new ArrayList<>(map.values());
    ...

Хотя, возможно, он быстрее алгоритма, следующего за путем (который может использовать порядок идентификаторов), ему требуется дополнительная память: дополнительная карта.

Answer 2

Вы можете построить свое дерево рекурсивно. Первым шагом будет извлечение корней ваших деревьев. Затем создайте функцию, которая получает прямых дочерних элементов каждого узла, запустив список (O(n)) - внутри будет рекурсивный вызов для каждого из дочерних элементов.

Я думаю, мой синтаксис JAVA немного, но ржавый, так что это псевдокод:

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)

Это будет в O(n^2) сложности. 2 немедленное улучшение, которое вы можете сделать, это сохранить listOfNode в объекте и использовать его как this, чтобы вам не пришлось перегружать память. Во-вторых, вы можете каждый раз изменять список и удалять назначаемый узел (так как его нельзя назначить дважды ...)

Надеюсь, это поможет!