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

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

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

我创建一个class RecordHolder来表示上面的table。我还实现了方法 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

以防万一您想尝试我的更简单的实现想法，此处提供了简要的详细信息。这样，您可以决定是要使用当前的想法还是尝试重新开始使用这个想法。（注意下面的代码是伪 Java 大纲，它不会编译也没有经过测试）：

int numNodes = 7;
Node[] nodes = new Node[numNodes];
//Read in your file here using a Scanner/FileReader or something
int ID = 0;
char value = 0;
int PID = 0;
while(scanner.hasNextLine()){
    ID = scan.next();
    value = scan.next();
    PID = scan.next();
    nodes[ID] = new Node(value, PID);
}

然后是一个节点class:

class Node{
    char value;
    Node parent;
    public Node(value, parentID){
        this.value = value;
        if(parentID == -1)
            parent = null;
        else
            parent = nodes[parentID]; //nodes will have to be a global array or get passed to the constructor
    }
}

请注意，此构造函数仅在 nodes[parentID] 中的项目先前已初始化时才有效。（这是您当前的输入文件顺序的情况，但在其他情况下可能不是。）

祖先：

要通过此方法使用 ID 查找节点的祖先，只需执行以下操作：

printAncestry(nodes[ID]);

void printAncestry(Node n){
    System.out.println("Child: " + n.value);
    System.out.println("Ancestry: ");
    while(n.parent != null){
        n = n.parent;
        System.out.println(n.value);
    }
}

Answer 2

尝试：

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;
    }
}

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

How to find all descendants from flat tree structure

java

algorithm

tree

祖先：