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

Answer 2

为了以防万一，您想尝试一下我的更简单的实现思想，这里有一些简单的细节。通过这种方式，你可以决定是使用你目前的想法，还是尝试重新使用这个想法。（注意，下面的代码是作为伪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 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
    }
}

请注意，只有在节点[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);
    }
}