将父/子关系的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
需要将其转换为（多个）分层树：
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<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;
}
问题答案：
这是基于第一个答案和问题的更新的替代解决方案… :)
主要方法
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);
}
}
}
双人课：
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 + "]";
}
}
