java使用平面文件中的父ID创建多个树状结构

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

您可以递归地构建树。第一步是提取树的根。然后创建一个函数，通过在列表上运行来获取每个节点的直接子节点(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) 复杂度。您可以做的第二个直接改进是将 listOfNode 保存在对象中并将其用作 this 这样您就不需要重载内存。其次，您可以每次修改列表并删除分配的节点(因为他不能分配两次......)

希望有帮助!