java - 如何从平面树结构中找到所有后代

Question

我有一个表示层次关系的平面数据，如下所示:

ID    Name    PID
0     A       NULL
1     B       0
2     C       0
4     D       1
5     E       1
6     F       4
3     G       0

此表代表'数据表'，其中PID表示父元素。例如，在第一行中我们看到 A 的 PID 为 null 而 B 的 PID 为 0，这意味着 B 的父元素是 A，因为 0 是 A 的 ID，而 A 是根元素，因为它没有 PID .同样，C 有父 A，因为 C 也有 PID 0，而 0 是 A 的 ID。

我创建了一个类 RecordHolder 来表示上表。我还实现了方法 processRecordHolder

public Map<String, List<String>> processRecordHolder()

返回的映射使用元素作为键，并将后代节点的集合作为值。例如，映射中的第一项对应于元素 A，它有很多后代，而元素 C 没有后代。输出中成员的顺序并不重要。

public static void main(String[] args) {

     RecordHolder dt = new RecordHolder();

     dt.addRow(0, "A", null);
     dt.addRow(1, "B", 0);
     dt.addRow(2, "C", 0);
     dt.addRow(4, "D", 1);
     dt.addRow(5, "E", 1);
     dt.addRow(6, "F", 4);
     dt.addRow(3, "G", 0);

     System.out.println("Output:");
     System.out.println(dt.processRecordHolder());
 }

Output:
{D=[F], A=[B, C, G, D, E, F], B=[D, E, F]}
or
{D=[F], E=null, F=null, G=null, A=[B, C, G, D, E, F], B=[D, E, F], C=null}

下面是我目前能够实现的 Record 的实现:

public class Record {

    public Integer id;
    public String name;
    public Integer parentId;
    public Record parent;
    public Collection<Record> children;

    public Record(Integer id, String name, Integer parentId) {
        this();
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }

    public Record() {
       children = Collections.newSetFromMap(new ConcurrentHashMap<Record, Boolean>())
    }

    public Collection<Record> getChildren() {
       return children;
    }

    public Record getParent() {
       return parent;
    }

    public Integer getParentId() {
       return parentId;
    }

    @Override
    public String toString() {
        return "Record{" + "id=" + id + ", name=" + name + ", parentId=" + parentId + '}';
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
       final int prime = 31;
       int result = 1;
       result = prime * result + ((id == null) ? 0 : id.hashCode());
       result = prime * result + ((name == null) ? 0 : name.hashCode());
       result = prime * result  + ((parentId == null) ? 0 : parentId.hashCode());
       return result;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (obj == null) {
        return false;
    }
    if (!(obj instanceof Record)) {
        return false;
    }
    Record other = (Record) obj;
    if (id == null) {
        if (other.id != null) {
        return false;
        }
    } else if (!id.equals(other.id)) {
        return false;
    }
    if (name == null) {
        if (other.name != null) {
        return false;
        }
    } else if (!name.equals(other.name)) {
        return false;
    }
    if (parentId == null) {
        if (other.parentId != null) {
        return false;
        }
    } else if (!parentId.equals(other.parentId)) {
        return false;
    }
    return true;
    }    
}

现在我无法理解其他步骤该怎么办？

Answer 1

尝试:

public class RecordHolder {

    Map<Integer,String> namesById = new HashMap<>();
    Map<Integer,List<Integer>> childrenById = new HashMap<>();

    public void addRow(Integer id, String name, Integer parent) {
        namesById.put(id, name);
        List<Integer> children = childrenById.get(parent);
        if (children == null) {
            children = new ArrayList<>();
            childrenById.put(parent, children);
        }
        children.add(id);
    }

    public Map<String,List<String>> processRecordHolder() {
        Map<String,List<String>> results = new HashMap<>();
        descendants(null, results);
        return results;
    }

    private List<String> descendants(Integer id, Map<String, List<String>> results) {
        final List<String> childrenNames = new ArrayList<>();

        final List<Integer> childrenIds = childrenById.get(id);
        if (childrenIds != null && childrenIds.size() > 0) {
            for (Integer childrenId : childrenIds) {

                final String childName = namesById.get(childrenId);
                childrenNames.add(childName);

                final List<String> grandchildrenNames = descendants(childrenId, results);
                childrenNames.addAll(grandchildrenNames);
            }

            if (id != null) {
                results.put(namesById.get(id), childrenNames);
            }
        }

        return childrenNames;
    }
}