logo标签列表

将Java的父/子关系ArrayList转换为树形结构？

java
7
我是一名有用的助手，可以为您翻译文本。

我有许多父/子对，我想尽可能将它们转化为分层树结构。例如，这些可以是配对：

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

需要转换成（一个）分层树：
   D
    ├── E
    │   ├── A
    │   │   └── B
    │   └── C   
    └── G
    |   ├── F
    |   └── H
    |
    X
    |
    └── Y
        |
        └──Z

在Java中，我如何从包含child=>parent对的arrayList转换为像那样的Tree？
我需要这个操作的输出是包含两个元素D和X的arrayList，依次每个元素都有其子节点列表，它们又包含一个子节点列表，以此类推。
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;
}
你的第一次代码尝试是什么？你打算如何用Java表示这个树形结构？ - user813853
通过“树”，我指的是元素具有元素列表，每个元素都包含元素列表，依此类推。 - Melad Basilius
1
抱歉打扰您了，但请不要传递所有的getter和setter，尽可能精确明确。 - user813853
这个解决方案https://dev59.com/Covda4cB1Zd3GeqPZ3tD#30570416看起来是合法的！ - user813853
5个回答
10
假设您的节点结构类似于：
class Node {
  Object id;
  List<Node> children;
  Node parent;

  public Node(Object id) {
    this.id = id;
    children = new LinkedList<>();      
  }
}

首先，您需要在输入列表上进行迭代，并创建一个从id到Nodes的映射（这用于在树仍未结构化时获取节点）。

Map<Object, Node> temp = new HashMap<>();
for (Pair pair: inputList) {
  Node parent = temp.getOrDefault(pair.parent.id, new Node(pair.parent.id));
  Node child = temp.getOrDefault(pair.child.id, new Node(pair.child.id));
  parent.children.add(child);
  child.parent = parent;
  temp.put(parent.id, parent);
  temp.put(child.id, child);
}

现在，您可以迭代地搜索地图以查找树的根节点。
for (Node n: temp.values()) {
  if (n.parent==null) {
    root = n; break;
  }
}

这段代码假定您的数据是“有效”的（没有重复的子项，单个根等）。您可以很容易地进行适应。

由于我们经常使用 get，所以最好使用 ArrayList 而不是 LinkedList，请查看此链接以确认我是否正确：https://dev59.com/Y3RC5IYBdhLWcg3wW_tk - user813853
我只是选择了我能想到的第一个集合。孩子们更可能是一个集合而不是列表。或者，如果您需要有关链接的其他信息，您可以从ID到Info进行映射。我没有其他信息可以做出更明智的选择（我的代码没有在孩子列表上执行单个获取操作 :)）。 - Diego Martinoia
抱歉，我在看我的代码...(看到了get和comment) - user813853
精确解决方案 - Melad Basilius
6
这里是基于第一个答案和问题更新的另一种解决方案... :)

主要方法

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

    }

}

Pair类：

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类已更新

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 + "]";
    }

}
完美。 - Melad Basilius
如果您的输入包含根节点，那么此解决方案将导致堆栈溢出异常。输入：H：Ga F：G G：D E：D A：E B：C C：E D：D请注意输入内容。 - Ajay Jayavarapu
我必须在成对之前进入一步。由于我有一个共同的列表，其中每个条目都包含父级ID，因此我必须先将其成对，然后再进行下一步解决方案。 - Ravi Yadav
@MeladBasilius 你好，我该如何将这个应用到RecyclerView中呢？能帮我一下吗？ - Handelika
3

试一试

只需根据您的ID进行哈希，建立您的关系。

完成后找到树的根。

    private MegaMenuDTO getRoot(Map<String, MegaMenuDTO> tree) {
        return tree.values().stream().filter(node -> Objects.isNull(node.getParentId())).findFirst().orElse(null);
    }

    public MegaMenuDTO createTree(List<MegaMenuDTO> list) {
        Map<String, MegaMenuDTO> tree = new HashMap<>();
        list.forEach(current -> tree.put(current.getId(), current));
        list.forEach(current -> {
            String parentId = current.getParentId();
            if (tree.containsKey(parentId)) {
                MegaMenuDTO parent = tree.get(parentId);
                current.setParentId(parentId);
                parent.addChildrenItem(current);
                tree.put(parentId, parent);
                tree.put(current.getId(), current);
            }
        });
        return getRoot(tree);
    }
0

根据@Diego Martinoia 的解决方案和@OSryx的解决方案，最终解决了我的问题

private List<MegaMenuDTO> dooo(List<MegaMenuDTO> input) {
    Map<String, MegaMenuDTO> hm = new HashMap<String, MegaMenuDTO>();
    MegaMenuDTO child = null;
    MegaMenuDTO mmdParent = null;

    for (MegaMenuDTO item : input) {

        // ------ Process child ----
        if (!hm.containsKey(item.getId())) {
            hm.put(item.getId(), item);
        } 
        child = hm.get(item.getId());

        // ------ Process Parent ----
        if (item.getParentId() != null && !item.getParentId().equals("")
                && !item.getParentId().equals("0")) {
            if (hm.containsKey(item.getParentId())) {
                mmdParent = hm.get(item.getParentId());
                mmdParent.getChildrenItems().add(child);
            }
        }

    }

    List<MegaMenuDTO> DX = new ArrayList<MegaMenuDTO>();
    for (MegaMenuDTO mmd : hm.values()) {
        if (mmd.getParentId() == null || mmd.getParentId().equals("")
                || mmd.getParentId().equals("0"))
            DX.add(mmd);
    }
    return DX;
}
我不相信如果你的节点在列表中是随机或自下而上排序的，这种方法会起作用。你将拥有一堆无法链接到其父级节点的孤立节点。例如，第一个被处理的节点将没有其父级节点在图中，因此它将永远成为孤儿节点。 - patelb
0

这是我的解决方案：

  • 将MegaMenuDTO列表转换为Map：

    public static  Map<String, MegaMenuDTO> buildIdMap(Collection<MegaMenuDTO> targets){
    Map<String, MegaMenuDTO> result = new HashMap<>();
    if(targets!=null && !targets.isEmpty()){
        final Iterator<MegaMenuDTO> iterator = targets.iterator();
        while (iterator.hasNext()){
            final MegaMenuDTO next = iterator.next();
            if(StringUtils.isNotBlank(next.getId())){
                result.put(next.getId(),next);
            }
        }
    }
    return result;
}

  • 然后将Map转换为树结构：

    public List<MegaMenuDTO> getTree(List<MegaMenuDTO> all ){
    final List<MegaMenuDTO> result = new ArrayList<>();
    final Map<String, MegaMenuDTO> allMap = buildIdMap(all);
    final Iterator<MegaMenuDTO> iterator = all.iterator();
    while (iterator.hasNext()){
        final MegaMenuDTO next = iterator.next();
        final String parentId = next.getParentId();
        if(StringUtils.isNotBlank(parentId)){
            final MegaMenuDTO node = allMap.get(next.getId());
            final MegaMenuDTO nodeP = allMap.get(parentId);
            if(nodeP != null){
                nodeP.getChildren().add(node);
            }
        }else{
            next.setOpen(true);
            result.add(next);
        }
    }
    return result;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接