Итерация через рекурсивные объекты

Question

Я пытаюсь выполнить итерацию через рекурсивный объект, но Java не поддерживает эту информацию из того, что я знаю.

Например, если объект Item:

public class Item { 

    Long uuid; 
    List<Item> children; 
} 

С for петли я мог перебирать children, но так как children будет содержать более children, которая будет содержать больше children и так далее, нет никакого способа, чтобы автоматически определить глубина и петля, основанные на этой глубине.

Есть ли способ итерации через рекурсивные объекты?

Answer 1

Если дерево очень глубокое, используйте поиск вперёд, предложенный Эраном. Если дерево очень широко используется в глубину поиска, которые могли бы выглядеть примерно так:

class ItemVisitor { 
    public void accept(Item item) { 
     // Do something 
     for (Item i : item.getChildren()) { 
      this.accept(i); 
     } 
    } 
} 

EDIT:

Для вдоха первого поиска, используйте очереди и добавить все ребенок тока узел на нем.

public void visitTree(Item head) { 
    Queue<Item> queue = new PriorityQueue<Item>(); 
    while (queue.size() > 0) { 
     Item curr = queue.poll(); 
     // Do something 
     for (Item i : curr.getChildren()) 
      queue.add(i); 
    } 
} 

Answer 2

Если у вас нет циклов внутри родитель-потомок дерева вы можете использовать простую рекурсивную функцию, чтобы определить число потомков:

public class Item { 
    ... 

    public int getDescendantCount() { 
     int count = 0; 
     if (children != null) { 
      count += children.size(); 
      for (Item child : children) 
        count += child.getDescendantCount(); 
     } 
     return count; 
    } 
} 

Answer 3

что-то похожее на это?

void read(Item item) { 
    if (item == null) { 
     //do something with the uuid ? 
     return; 
    } else { 
     for (Item i : item.children) { 
      read(i); 
     } 
    } 
} 

Answer 4

Если вы можете сохранить глубину в виде отдельного элемента данных и обеспечения его с помощью класса дизайн/инкапсуляция, вы хорошо там.

Что вы предлагаете - это узел какого-либо дерева неопределенной глубины. Вы можете реализовать любой обычный метод поиска по глубине или по ширине; искать его в любых стандартных структурах данных и алгоритмах учебника/веб-ссылки и реализовывать на Java. Решение, которое было опубликовано во время ввода текста, было стандартным методом поиска по глубине, если вы используете Stack (последняя очередь в первом случае или LIFO-очередь) или поиск по ширине, если вы используете очередь FIFO. Это хорошие и чистые методы, но не самые простые.

Самый наивный метод был бы простой рекурсивной функции для поиска в глубину:

public void recurseIntoChildren(Item item) { 
    if(item.children.size() == 0) { 
     // you are now at a leaf node: do something 
    } 
    for(Item child : item.children) { 
     recurseIntoChildren(child); 
    } 
} 

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

Это не самый эффективный метод (если компилятор не оптимизирует хвостовую рекурсию в простой цикл).

Answer 5

Я не знаю, какова цель цели, но вы всегда можете циклически рекурсивно проходить через дочерние элементы.

Например

public void loopChildren(List<Item> items) { 
    for (Item i : items) { 
     System.out.println(i.uuid); 
     loopChildren(i.children);   
    }  
} 

Это просто продолжайте цикл до конца списка. Если у ребенка нет детей, список должен быть пустым, поэтому он заканчивается для этой итерации.

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