将父/子关系的java arrayList转换为树？
我有一堆父/子对，我想尽可能转变为分层树结构。 例如，这些可能是配对：
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）层次结构树：
D ├── E │ ├── A │ │ └── B │ └── C └── G | ├── F | └── H | X | └── Y | └──Z
在Java中，我如何从包含child => parent对的arrayList转到像那样的Tree？
我需要这个操作的输出是arrayList包含两个元素D和X依次每个都有它的子列表，其中又包含子列表等等
public class MegaMenuDTO { private String Id; private String name; private String parentId; private List childrenItems=new ArrayList(); 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 getChildrenItems() { return childrenItems; } public void setChildrenItems(List childrenItems) { this.childrenItems = childrenItems; } }
我的第一次尝试是
private void arrangeMegaMenuTree(MegaMenuDTO grandParent, MegaMenuDTO parent, List 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 arrangeMegaMenuTree(MegaMenuDTOparent,ListmenuItems) { 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 tempList = new ArrayList(); tempList.add(child); return tempList; } } return null; } private boolean hasChildren(MegaMenuDTO parent, List children) { for (MegaMenuDTO child : children) { if (child.getParentId().equals(parent.getId())) { return true; } } return false; }
这是基于第一个答案和问题更新的替代解决方案…… 🙂
主要方法
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 pairs = new ArrayList (); 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 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 DX = new ArrayList (); 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); } } }
配对类：
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 childrenItems; public MegaMenuDTO() { this.Id = ""; this.name = ""; this.parentId = ""; this.childrenItems = new ArrayList (); } 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 getChildrenItems() { return childrenItems; } public void setChildrenItems(List 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 + "]"; } }
假设您的Node结构类似于：
class Node { Object id; List children; Node parent; public Node(Object id) { this.id = id; children = new LinkedList<>(); } }
然后你首先开始迭代你的输入列表，并从ids-> Nodes创建一个映射（这用于在树仍然是非结构化时获取节点）;
Map 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; } }
此代码假定您的数据“有效”（没有重复的子条目，单根等）。否则您可以轻松地对其进行调整。
取决于@Diego Martinoia解决方案和@OSryx解决方案，我的问题的最终解决方案
private List dooo(List input) { Map hm = new HashMap(); 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 DX = new ArrayList (); for (MegaMenuDTO mmd : hm.values()) { if (mmd.getParentId() == null || mmd.getParentId().equals("") || mmd.getParentId().equals("0")) DX.add(mmd); } return DX; }
}