java使用平面文件中的父ID创建多个树状结构 [英] java create multiple tree like structure using parent id from flat file

问题描述

我有如下数据

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

如果您看到这是从可以按任何顺序读取的平面文件中读取的无序数据.

If you see this a unordered data read from a flat file which can be in any order.

我想创建如下树:

111
|  \
123 555  

和

222
\
321

我将这些数据放在一个对象中，如下所示:

I have this data in an object, which looks like below:

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

我正在尝试处理此数据以创建类别树列表.

I am trying to process this data to create list of categories tree.

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

我对这部分感到困惑.如何启动树.由于循环的第一次迭代中的条目具有父级，但它的父级尚未出现在最终列表中.如何将第一个条目添加到其父条目.

I am confused on this part. How to start the tree. Since entry in the first iteration of loop has parent but it's parent is not present in the final list yet. How to add first entry to it's parent.

推荐答案

您可以递归地构建树.第一步是提取树的根.然后创建一个函数，该函数通过在列表上运行来获取每个节点的直接子节点 (O(n)) - 内部将对每个子节点进行递归调用.

You can build your tree recursively. First step will be to extract the roots of your trees. Then create a function who get the direct children of each node by running on the list (O(n)) - inside there will be recursive call for each of the children.

我想我的 JAVA 语法很少但很生疏，所以这是伪代码:

I guess my JAVA syntax is little but rusty so this is the pseudo code:

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，这样您就不需要超载内存.其次，您可以每次修改列表并删除分配的节点(因为他不能分配两次......)

This will be in O(n^2) complexity. 2 immediate improvement you can do is save the listOfNode in object and used it as this so you won't need to overload the memory. Second, you can modify the list each time and remove the node that assign (as he cannot be assign twice...)

希望有帮助！

这篇关于java使用平面文件中的父ID创建多个树状结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！