当前位置: 首页 > 面试题库 >

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

孔宇
2023-03-14
问题内容

我有一堆父母/孩子对,我想尽可能地变成分层树结构。因此,例如,这些可能是配对:

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

}


 类似资料:
  • 问题内容: 我有一堆名称-父母名对,我想将其变成尽可能少的分层树结构。因此,例如,这些可能是配对: 需要将其转换为一个或多个分层树: 我想要的最终结果是一组嵌套元素,每个元素都包含孩子的名字。 配对中没有不一致的地方(子代是它自己的父代,父代是子代的子代,等等),因此可以进行大量优化。 在PHP中,如何从包含child => parent对的数组转到一组Nested ? 我感觉涉及到递归,但是我还

  • 我有一个场景,需要在一种情况下加载所有子值,在另一种情况下加载一些特定的子值。我对这两种情况都使用一个bean,并使用命名查询编写查询。 现在在我的查询2中,我只需要加载字符串A,而不需要加载字符串B和字符串C。我试过使用 但得到以下错误 那么,关于如何继续这方面的任何建议。。

  • 使用JPA(Hibernate)我试图实现以下关系,并想知道其他人是否对最佳方法有任何建议: 基本上是完全不相关的对象,每个对象都有一个公共子对象的集合;在对象模型中实现简单,在数据库中稍微麻烦些! 我确信这一定是常见的事情,但是我很难找到任何示例实现,因为我真的不知道正确的搜索词。 谢谢你的时间!

  • 问题内容: 如何将以下SQL查询转换为ActiveRecord关系,以便可以使用范围对其进行扩展? 这是我必须尝试直接使用Arel的东西吗? 我尝试将其分解为作用域/子查询,但是子查询上的选择最终在封闭查询中,因此引发PostgreSql错误,因为未在封闭语句中的GROUP BY或ORDER BY中指定该列。 更新: 您认为它是PostgreSql是正确的。我尝试了您的查询,但是对于直接查询和Ac

  • 问题内容: 我想知道如何将某些函数返回的父对象转换为子类。 我不能更改A类。如果可以的话,我可以对A类实现functionIneed,但是由于代码的结构,这是不可能的。 问题答案: Python不支持“广播”。您将需要编写代码,以便它可以适当地进行初始化。

  • 伪代码: 为什么大多数程序通常不允许这样做(我从未见过)? 程序不能识别出它何时进行了循环并停止执行任务吗? 对于实例: 假设这些对象是3d网格,我们想在x轴上转换对象A 2个单位。通常,父子关系会移动A的任何子级。所以它穿过子树,并用A翻译x轴上的每个子级2个单位。然后它到达树中的对象A,而不是移动它,为什么不让它检查身份,如果身份返回true,然后停止移动东西? 这只是软件开发人员的懒惰吗?