将父/子关系的java arrayList转换为树？ [英] Convert java arrayList of Parent/child relation into tree?

问题描述

我有一堆父/子对，我想尽可能转变为分层树结构。例如，这些可能是配对：

I have a bunch of parent/child pairs, that I'd like to turn into hierarchical tree structures as possible. So for example, these could be the pairings:

Child : Parent
    H : Ga
    F : G
    G : D
    E : D
    A : E
    B : C
    C : E
    D : NULL
    Z : Y
    Y : X
    X: NULL

哪些需要转换为（ a）层次结构树：

Which needs to be transformed into (a) heirarchical tree(s):

   D
    ├── E
    │   ├── A
    │   │   └── B
    │   └── C   
    └── G
    |   ├── F
    |   └── H
    |
    X
    |
    └── Y
        |
        └──Z

如何在Java中使用包含子节点的arrayList =>父对，到那样一棵树？

How, in Java, would I go from an arrayList containing child=>parent pairs, to a Tree like that one?

我需要这个操作的输出是arrayList包含两个元素D和X
依次每一个有孩子的列表，其中还包含一个孩子的列表等等

i need the output of this operation is arrayList contains two elements D and X in turn each one have list of its children which in turn also contains a list of children and so on

public class MegaMenuDTO {
    private String Id;
    private String name;
    private String parentId;
    private List<MegaMenuDTO> childrenItems=new ArrayList<MegaMenuDTO>();

    public String getId() {
        return Id;
    }
    public void setId(String id) {
        Id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getParentId() {
        return parentId;
    }
    public void setParentId(String parentId) {
        this.parentId = parentId;
    }
    public List<MegaMenuDTO> getChildrenItems() {
        return childrenItems;
    }
    public void setChildrenItems(List<MegaMenuDTO> childrenItems) {
        this.childrenItems = childrenItems;
    }
}

我的第一次尝试是

private void arrangeMegaMenuTree(MegaMenuDTO grandParent,
        MegaMenuDTO parent, List<MegaMenuDTO> children) {

    for (MegaMenuDTO child : children) {
        if (child.getParentId().equals(parent.getId())) {
            arrangeMegaMenuTree(parent, child, children);
        }
    }

    if (!grandParent.getId().equals(parent.getId())) {
        grandParent.getChildrenItems().add(parent);
        // children.remove(parent);
    }

}

再试一次

private List<MegaMenuDTO> arrangeMegaMenuTree(MegaMenuDTOparent,List<MegaMenuDTO>menuItems) {

    for (MegaMenuDTO child : menuItems) {

        if (parent.getId().equals(child.getId())) {
            continue;
        }
        if (hasChildren(child, menuItems)) {
            parent.setChildrenItems(arrangeMegaMenuTree(child, menuItems
                    .subList(menuItems.indexOf(child), menuItems.size())));
        } else {
            List<MegaMenuDTO> tempList = new ArrayList<MegaMenuDTO>();
            tempList.add(child);
            return tempList;
        }
    }
    return null;
}

private boolean hasChildren(MegaMenuDTO parent, List<MegaMenuDTO> children) {
    for (MegaMenuDTO child : children) {

        if (child.getParentId().equals(parent.getId())) {
            return true;
        }
    }
    return false;
}

推荐答案

这是一个替代解决方案在第一个答案和问题的更新...... :)

Here is an alternative solution based on the first answer and the update of the question ... :)

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

public class Main2 {

    public static void main(String[] args) {

        // input
        ArrayList<Pair> pairs = new ArrayList<Pair>();
        pairs.add(new Pair( "H" , "G"));
        pairs.add(new Pair( "F" , "G"));
        pairs.add(new Pair( "G" , "D"));
        // ...


        // Arrange
        // String corresponds to the Id
        Map<String, MegaMenuDTO> hm = new HashMap<>();


        // you are using MegaMenuDTO as Linked list with next and before link 

        // populate a Map
        for(Pair p:pairs){

            //  ----- Child -----
            MegaMenuDTO mmdChild ;
            if(hm.containsKey(p.getChildId())){
                mmdChild = hm.get(p.getChildId());
            }
            else{
                mmdChild = new MegaMenuDTO();
                hm.put(p.getChildId(),mmdChild);
            }           
            mmdChild.setId(p.getChildId());
            mmdChild.setParentId(p.getParentId());
            // no need to set ChildrenItems list because the constructor created a new empty list



            // ------ Parent ----
            MegaMenuDTO mmdParent ;
            if(hm.containsKey(p.getParentId())){
                mmdParent = hm.get(p.getParentId());
            }
            else{
                mmdParent = new MegaMenuDTO();
                hm.put(p.getParentId(),mmdParent);
            }
            mmdParent.setId(p.getParentId());
            mmdParent.setParentId("null");                              
            mmdParent.addChildrenItem(mmdChild);


        }

        // Get the root
        List<MegaMenuDTO> DX = new ArrayList<MegaMenuDTO>(); 
        for(MegaMenuDTO mmd : hm.values()){
            if(mmd.getParentId().equals("null"))
                DX.add(mmd);
        }

        // Print 
        for(MegaMenuDTO mmd: DX){
            System.out.println("DX contains "+DX.size()+" that are : "+ mmd);
        }

    }

}

< h2>对类：

Pair class :

public class Pair {
    private String childId ;
    private String parentId;

    public Pair(String childId, String parentId) {
        this.childId = childId;
        this.parentId = parentId;
    }
    public String getChildId() {
        return childId;
    }
    public void setChildId(String childId) {
        this.childId = childId;
    }
    public String getParentId() {
        return parentId;
    }
    public void setParentId(String parentId) {
        this.parentId = parentId;
    }

}

MegaMenuDTO类已更新

MegaMenuDTO Class Updated

import java.util.ArrayList;
import java.util.List;

public class MegaMenuDTO {

    private String Id;
    private String name;
    private String parentId;
    private List<MegaMenuDTO> childrenItems; 

    public MegaMenuDTO() {
        this.Id = "";
        this.name = "";     
        this.parentId = "";
        this.childrenItems = new ArrayList<MegaMenuDTO>();
    }

    public String getId() {
        return Id;
    }
    public void setId(String id) {
        Id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getParentId() {
        return parentId;
    }
    public void setParentId(String parentId) {
        this.parentId = parentId;
    }
    public List<MegaMenuDTO> getChildrenItems() {
        return childrenItems;
    }
    public void setChildrenItems(List<MegaMenuDTO> childrenItems) {
        this.childrenItems = childrenItems;
    }
    public void addChildrenItem(MegaMenuDTO childrenItem){
        if(!this.childrenItems.contains(childrenItem))
            this.childrenItems.add(childrenItem);
    }

    @Override
    public String toString() {
        return "MegaMenuDTO [Id=" + Id + ", name=" + name + ", parentId="
                + parentId + ", childrenItems=" + childrenItems + "]";
    }

}

这篇关于将父/子关系的java arrayList转换为树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！