Получение всех детей на одном уровне двоичного дерева - PullRequest
Новая
       31

Получение всех детей на одном уровне двоичного дерева

0 голосов
/ 22 мая 2018

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

            A
   B        C        D
 E   F    G   H    I   J

, например, уровень 3 вернул бы узлы E, F, G, H, I и J.У меня есть метод внутри TreeNode класса, который возвращает всех потомков данного узла, поэтому я подумал сделать что-то вроде этого: 

static Collection<ITreeNode<IProduct>> getOnLevel(ITree<IProduct> tree, int level)
{
    Collection<ITreeNode<IProduct>> temp;
    int i;
    Iterator<ITreeNode<IProduct>> iterator = tree.getRoot().getChildren().iterator();
    for(i=0; i<=(level); i++) 
    {       
        while(iterator.hasNext())
        {                   
            ITreeNode<IProduct> elem = iterator.next();
            if(i == (level)) 
            {
                temp = elem.getChildren();
                return temp;
            }
        }
    }
    return tree.getRoot().getChildren(); 

}

, но потом я понял, что просто перебираю потомки первого уровня, поэтомуЯ, наверное, должен сделать это как-то рекурсивно?Заранее спасибо, Амар!

1 Ответ

0 голосов
/ 22 мая 2018

Вы можете сделать это рекурсивно или с помощью итераций, решать только вам.

Я считаю, что рекурсивное решение немного легче читать.Это выглядело бы так: 

static Collection<ITreeNode<IProduct>> getOnLevel(
    ITree<IProduct> tree
,   int desiredLevel
) {
    List<ITreeNode<IProduct>> result = new ArrayList<>();
    findOneLevel(tree.getRoot(), desiredLevel, 0, result);
    return result;
}

static void findOnLevel(
    ITreeNode<IProduct> node
,   int desiredLevel
,   int currentLevel
,   List<ITreeNode<IProduct>> result
) {
    if (currentLevel == desiredLevel) {
        result.add(node);
        return;
    }
    Iterator<ITreeNode<IProduct>> iterator = node.getChildren().iterator();
    while(iterator.hasNext()) {
       getOneLevel(iterator.next(), desiredLevel, currentLevel+1, result);
    }
}

Подход очень прост: метод верхнего уровня создает список для сохранения результата и вызывает рекурсивный findOnLevel.Рекурсивный метод проверяет, достигли ли мы желаемого уровня, и добавляет текущий узел к результату, если мы это сделали.В противном случае мы пропускаем все дочерние элементы текущего узла в рекурсивном вызове, передавая currentLevel+1 для нового текущего уровня.

...