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

Question

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

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

Я пытаюсь попросить у объекта top box список листовых узлов Box, который являетсяв этом случае объекты box.

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

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

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

Answer 1

прошло много времени с тех пор, как я сделал 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 2

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

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

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

Answer 3

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

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

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