代码之家 › 专栏 › 技术社区 › rapadura

从根节点到所有子节点的n-树遍历

traversal parent tree list java

rapadura · 技术社区 · 14 年前

我有一个列表,其中有些表来自一个数据库,其中每一行都包含一个引用另一行的父字段。这样地

标题,父级
A、空的
B、一个
C、一个
D、 C类
E、乙
F、空的

这里A和F是根节点,B和C是A的子节点,D是C的子节点,E依次是B的子节点。

从这个列表中生成树结构的最佳方法是什么?

一种方法是在列表上递归,找到根(没有父级的标题),然后为每个根再次在列表上循环并附加根节点。然后,对于这些节点,再次在完整列表上循环以附加它们自己的任何子节点。

例子:

private Node getNode(SomeData d) {
    List<SomeData> tmp = getChildren(d);
    if (tmp == null OR empty) return new Node(d);

    Node n = new Node(d);
    for (SomeData m : tmp) {
        n.addChild(getNode(m)); // recurse
    }
    return n;
}

private List<SomeData> getChildren(SomeData parent) {
    List<SomeData> tmp = new ArrayList<SomeData>();
    for (SomeData candidateChild : myBigFlatDataList.values()) {
        if (parent.equals(candidateChild)) {
            tmp.add(candidateChild);
        }
    }
    return tmp;
}

有更好的办法吗?

5 回复 | 直到 14 年前

Mark Peters 14 年前

这是一个很好的方法,但它比必须的更天真。

另一条路线只需要线性时间。SomeData是否具有唯一标识它的特性?我假设是这样;这可能是某些数据本身正确地实现了equals()和hashCode()。

假设有一种方法 int SomeData.getID() . 然后我们可以在HashMap中保留以前看到的节点。

Map<Integer, Node> visitedNodes = new HashMap...

然后我们把这些行向前读:

for ( SomeData data : ... ) {
    SomeData parent = data.getParent();
    Node<SomeData> parentNode = getOrCreateNode(parent);
    Node<SomeData> childNode = getOrCreateNode(data);
    parentNode.addChild(childNode);
}

private Node<SomeData> getOrCreateNode(SomeData data) {
    Node<SomeData> node = visitedNodes.get(data.getID());
    if ( node == null ) {
       node = new Node<SomeData>(data);
       visitedNodes.put(data.getID(), node);
    }
    return node;
}

Sagar V 14 年前

为每个节点重新读取整个文件(或者更糟的是查询数据库)相当昂贵。我宁愿你边看单子边建树。这是我的2美分

让Root Nodes是所有根节点的集合(最初是一个空集合)。
对于每对节点(N1,N2):
1. 对于每个N in(N1,N2),如果N不在节点中,则创建N并插入到节点中。
2. 如果N2==null,也可以将N2插入RootNodes(此外,还可以从节点中删除它)
3. 标记N2.child=N1。

如果您遵循这一点,在列表上的迭代结束时,您应该拥有:

RootNodes = {A,F}
Nodes = {B,C,D,E}

A.child = B
A.child = C
C.child = D
B.child = E

希望这有帮助。

Keith Randall 14 年前

你可以一次建树。您可以对表执行第一次传递以生成所有节点(从名称到节点构建哈希表),然后执行另一次传递,在其中可以在两个节点之间添加父子关系(将父指针添加到子节点,并将子节点添加到父节点中的子节点列表)。

slosd 14 年前

从数据库中获取数据后,可以根据起源属性。这样,在每次搜索节点的子节点时,就不需要遍历整个列表。

编辑: 当列表被排序时,当您找到您要查找的所有子项时,可以停止对列表的迭代。例如,当拥有根“A”并开始在此列表中搜索其子级时:

B, A
C, A
E, B  <- when you reach "B" you can assume that there are no
D, C     other nodes which are children of "A" and stop the iteration

Ashis Kumar 11 年前

List<User> list = new ArrayList<User>();
User blankNode;
class User{
    String userid;      
    User child;     
    public User() {
        //blankNode 
    }
    public User(String userid) {
        this.userid = userid; 
    }
    @Override
    public int hashCode(){
        return userid.hashCode();
    }
}
public void addUser(User parent,String userid){
    if(null == userid)return;
    User child = new User(userid);
    parent.child = child;
    list.add(child);        
}
public void removeUser(User child){
    if(null == child)return;        
    list.remove(child);
}
/* move the rank to up - assume
 * secParent - assign to new child
 */
public void boubbleUp(User secParent,  User oldParent, User child){
    if(null == child || null == secParent)return;
    secParent.child = child;
    oldParent.child = null;
}
public List<User> getTopUser(int num){
    if(num <1)return null;
    Map<Integer, List<User>> map = new HashMap<Integer, List<User>>();
    for(User usr : list){
        int count =0;
        User temp = usr.child;
        while(null != temp){
            count++;temp=temp.child;
        }           
        if(map.get(count)== null){
            List<User>  sameNoOfChildren = new ArrayList<User>()    ;
            sameNoOfChildren.add(usr);
            map.put(count, sameNoOfChildren);
        }else{
            map.get(count).add(usr);                
        }
    }
    Integer[] arr = (Integer[]) map.keySet().toArray();
    Arrays.sort(arr);
    List<User> result = new ArrayList<User>();
    for(int i = arr.length-1; i <=arr.length-num; i-- ){
        result.addAll(map.get(i));
    }       
    return result;      
}