Обход n-дерева от корневого узла до всех детей - PullRequest
Новая
       30

Обход n-дерева от корневого узла до всех детей

1 голос
/ 06 октября 2010

У меня есть список с некоторыми таблицами из базы данных, где каждая строка содержит родительское поле, ссылающееся на другую строку. Как это

заголовок, родитель
A, ноль
Б, А
С, А
D, C
E, B
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 ]

1 голос
/ 12 марта 2013 
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;      
}
1 голос
/ 06 октября 2010

Это довольно хороший способ, но он более наивен, чем должен быть.

Другой маршрут требует только линейного времени.Есть ли что-то в SomeData, которое однозначно идентифицирует это?Я бы так предположил;это может быть сама 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;
}
1 голос
/ 06 октября 2010

Перечитывание всего файла (или, что еще хуже, запросов к базе данных) для каждого узла довольно дорого. Я бы предпочел, чтобы вы строили дерево, когда читаете список. Вот мои 2 цента

  1. Пусть Nodes - это набор узлов (изначально пустой набор).
  2. Пусть RootNodes - это набор всех корневых узлов (изначально пустой набор).
  3. Для каждой пары узлов (N1, N2):
    1. Для каждого N в (N1, N2), если N не в Узлах, создайте N и вставьте в Узлы.
    2. Если N2 == ноль, также вставьте N2 в корневые узлы (дополнительно вы также можете удалить его из узлов)
    3. Mark N2.child = N1.

Если вы выполните это, в конце итерации по списку у вас должно быть: 

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

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

Надеюсь, это поможет.

1 голос
/ 06 октября 2010

Вы можете построить свое дерево сразу.Вы можете сделать первый проход по таблице, чтобы построить все узлы (построить хеш-таблицу от имени к узлу), а затем сделать еще один проход, чтобы добавить отношения родитель-потомок между двумя узлами (добавить указатель родителя к потомку и добавить потомка ксписок детей у родителей).

1 голос
/ 06 октября 2010

Поскольку вы получаете данные из БД, вы можете сортировать строки в соответствии с атрибутом parent .Тогда вам не нужно будет перебирать весь список каждый раз, когда вы будете искать дочерние элементы узла.

РЕДАКТИРОВАТЬ: Когда список отсортирован, вы можете прекратить итерацию по списку, когда вы нашли все искомые дети.Например, если у вас есть корень «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
...