将父/子关系的java arrayList 转换为树？

Convert java arrayList of Parent/child relation into tree?

提问by Melad Basilius

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

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

需要将其转换为（a）层次树：

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

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

在 Java 中，我如何从包含 child=>parent 对的 arrayList 转到像这样的 Tree？

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

我需要这个操作的输出是 arrayList 包含两个元素 D 和 X 依次每个元素都有其子项列表，而子项列表又包含子项列表等等

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

my first try was

我的第一次尝试是

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

}

another try

再试一次

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

采纳答案by Diego Martinoia

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

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

Main Method

主要方法

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 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 Class Updated

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

}

回答by Diego Martinoia

Suppose your Node structure is something like:

假设您的 Node 结构类似于：

class Node {
  Object id;
  List<Node> children;
  Node parent;

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

Then you first start iterating on your input list, and create a map from ids->Nodes (this is used to fetch the nodes while the tree is still unstructured);

然后你首先开始迭代你的输入列表，并从 ids->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);
}

Now you can iterate on your map searching for the root of your tree

现在您可以在地图上迭代搜索树的根

for (Node n: temp.values()) {
  if (n.parent==null) {
    root = n; break;
  }
}

This code assumes that your data is "valid" (no duplicated children entries, single root, etc.) You can easily adapt it otherwise.

此代码假定您的数据是“有效的”（没有重复的子条目、单根等）。否则您可以轻松地对其进行调整。

回答by Melad Basilius

depending on @Diego Martinoia solution and @OSryx solution ,the final solution to my problem

取决于@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;
}

回答by alan9uo

Here is my solution:

这是我的解决方案：

• Convert MegaMenuDTO list to 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;
  }
  

• then convert the map to tree:

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

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

• 然后将地图转换为树：

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