Как вычислить узлы листа во вложенной структуре данных в Java?

Question

У меня есть такая структура, как мы будем называть объектами Box.

Box--+---Box----Box 
    | 
    +---Box-+--Box 
      | 
      +--Box 
      | 
      +--Box 

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

Объект box имеет список его дочерних элементов в переменной экземпляра типа Вектор, называемый дочерними.

Число детей может быть неограниченным.

Я пытался написать один рекурсивный метод для этого, но безуспешно.

Answer 1

Один из способов сделать это будет рекурсивным обходом структуры. Идея такова:

1. В пустом дереве нет листовых узлов.
2. В дереве с корнем r без детей, тогда r является единственным листом.
3. В дереве с корнем r, если у r есть дети, то листья дерева являются листьями этих детей.

Вы можете написать рекурсивный обход с таким родом псевдокод:

void findChildren (Box current, List<Box> found) { 
    /* Case 1. */ 
    if (current == null) return; 

    /* Case 2. */ 
    if (current.children.isEmpty()) { 
     found.add(current); 
     return; 
    } 

    /* Case 3. */ 
    for (Box child: current.children) 
     findChildren(child, found); 
} 

Надеются, что это помогает!

Answer 2

Прошло некоторое время с тех пор, как я сделал Java, поэтому я уверен, что этот код содержит множество синтаксических ошибок, и я надеюсь, что никто не помечает меня; просто пытаюсь дать вам некоторые идеи алгоритма. Надеюсь, что это помогает:

vector<Box> getLeaves(Box root) 
{ 
    vector<Box> tempList; //vector to hold nodes to check 
    vector<Box> tempList2; //vector to hold nodes' children 
    vector<Box> leafList; 
    bool goflag = true; 

    tempList.add(root); 

    while(goflag){ 
     for(int i = 0; i < tempList.size; i++){ 
      if(tempList[i].children.isEmpty()){ 
       leafList.add(tempList[i]); 
      } 
      else{ 
       //add all children to tempList2 
       for(int c = 0; c < tempList[i].children.size; c++){ 
        tempList2.add(tempList[i].children[c]) 
      } 
     } 
     if(tempList2.isEmpty()) //no more childs 
      goflag = false; 
     else 
      tempList = tempList2; 
     tempList2.clear(); 
    } 
    return leafList; 
} 

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

Answer 3

Существует несколько способов написания такой функции. Вот один из подходов к работе.

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

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