使用Map和路径变量生成java层次结构

34gzjxbg 于 2021-07-03 发布在 Java

关注(0)|答案(1)|浏览(384)

我有一个从postgres数据库中提取数据的family类。这个班看起来像这样：

@Entity
public class Family(){
@Id
private long id;
private String firstName;
private String lastName;
private Long parentId;
private4 String familyPath;
private List<Family> children;

//getters and setters

在数据库中，它们之间的关系以句点分隔的字符串形式存储。因此，例如，如果bob是sue的孩子，那么树状列将显示为：“bob.sue”。此路径作为familypath变量中族对象的一部分存储。
家族路径是基于数据库中每一行的唯一ID的路径。因此路径可能看起来像“1.2.3”，其中最后一个数字是当前行。”1.2.4“是另一个潜在路径。所以ID为3和4的行是2的子行，以此类推。
在我的代码中，我在数据库中查询数据中的所有家庭成员，因此我在数据库中有一组家庭成员。我的目标是使用这个初始的平面集生成一个由所有家庭成员组成的层次结构集。所以，最后如果我打电话给鲍勃的getchildren，我会得到一个包含sue和其他孩子的列表。
我的解决方案：
首先，我遍历我的族列表，找到我所称的根成员——那些位于族路径顶层的成员——并将它们删除到一个单独的列表中。所以现在我有了一份顶级家庭成员的名单，一份其他所有人的名单。
然后，对于顶级列表中的每个成员，我调用以下递归方法：

private Family familyTree(Family root, List<Family> members) {
    List<Family> children = new ArrayList<>();

    for (Family f : members) {
        if (isChildOf(f, root)) {
            children.add(familyTree(f, resources));
        }
    }
    root.setChildren(children);
    return root;
}

private boolean isChildOf(Family a, Family b) {
    String pCPath = a.getFamilyPath();
    String pPPath = b.getFamilyPath();

    return pCPath.indexOf('.') >= 0
            && pCPath.substring(0, pCPath.lastIndexOf('.')).equals(pPPath);
}

并将输出保存到列表中。这将生成所需的结果。
然而，我的问题是，我觉得这种递归方法非常昂贵（n^2）。我认为使用集合、Map和family对象的familypath变量可能有一种更有效的方法来生成这个层次结构，但是我总是陷入多个迭代循环中。有人有什么想法吗？

Java HashMap Database Hierarchy recursion

来源：https://stackoverflow.com/questions/37140791/generating-hierarchy-using-maps-and-path-variable

1条答案

按热度按时间

gojuced71#

选项1-单程

private Family familyTree(Family root, List<Family> members) {
    Map<Long, List<Family>> parentMap = new HashMap<>();

    // Assuming root is not contained in members
    root.children  = new ArrayList<>();
    parentMap.put(root.id, root.children);

    // Assign each member to a child list
    for (Family member : members) {

        // Put the family member in the right child list
        Long parentId = member.getParentId();
        List<Family> parentChildren = parentMap.get(parentId);
        if (parentChildren == null) {
            parentChildren = new ArrayList<>();
            parentMap.put(parentId, parentChildren);
        }
        parentChildren.add(member);

        // Get or create the child list of the family member
        List<Family> ownChildren = parentMap.get(member.id);
        if (ownChildren == null) {
            ownChildren = new ArrayList<>();
            parentMap.put(member.id, ownChildren);
        }
        member.children = ownChildren;
    }
    return root;
}

private Long getParentId() {
    // left as an exercise...
}

选项1.b-对所有成员（包括根）进行单次传递

private List<Family> familyTree(List<Family> members) {
    List<Family> roots = new ArrayList<>();
    Map<Long, List<Family>> parentMap = new HashMap<>();

    // Assign each member to a child list
    for (Family member : members) {

        // Put the family member in the right child list
        Long parentId = member.getParentId();
        if (parentId == null) {
            // a root member
            roots.add(member);
        } else {
            // a non-root member
            List<Family> parentChildren = parentMap.get(parentId);
            if (parentChildren == null) {
                parentChildren = new ArrayList<>();
                parentMap.put(parentId, parentChildren);
            }
            parentChildren.add(member);
        }

        // Get or create the child list of the family member
        List<Family> ownChildren = parentMap.get(member.id);
        if (ownChildren == null) {
            ownChildren = new ArrayList<>();
            parentMap.put(member.id, ownChildren);
        }
        member.children = ownChildren;
    }
    return roots;
}

选项2-添加对父级的引用

你的 Family 班级应该有一个 private Family parent 属性。然后，您将能够对每个族“级别”执行单个查询。即：
把苏的所有孩子都带走
从（1）中获得所有人的子女，并将他们分配给适当的家长
等。

选项3-层次结构的嵌套集模型

可以修改数据库模式以在单个查询中检索整个子树。诀窍是给每个树节点一个“左”和一个“右”值。这些值为节点子节点的“左”和“右”值建立了一个范围。
选择一棵完整的树可以这样做：

SELECT child.id, ...
FROM family AS child, family AS parent
WHERE child.lft BETWEEN parent.lft AND parent.rgt
    AND parent.id = 111
ORDER BY child.lft;

有许多其他的层次化操作可以用这样的模式很容易地完成。有关更多信息，请参阅本文和joe celko在sql for smarties中的树和层次结构。
最后，您的模型只考虑每个家庭成员的单亲，这似乎很奇怪。

赞(0）回复(0）举报 2021-07-03

我来回答

使用Map和路径变量生成java层次结构

1条答案

选项1-单程

选项1.b-对所有成员（包括根）进行单次传递

选项2-添加对父级的引用

选项3-层次结构的嵌套集模型

相关问题

热门标签

最新问答