Итеративный обход дерева, чтобы найти размер - PullRequest
6 голосов
/ 21 ноября 2011

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

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

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

// Start the counter at 1 because the root node counts
int size = 1;

for(ITree child1 : root) {
    size++;
    for(ITree child2 : child1) {
        size++;
        for(ITree child3 : child2) {
            size++;
            for(ITree child4 : child3) {
                size++;
                for(ITree child5 : child4) {
                    size++;
                }
            }
        }
    }
}
return size;

Ответы [ 3 ]

11 голосов
/ 21 ноября 2011

Концептуально, сохраняйте стек (LinkedList и т. Д.).Для каждого дочернего элемента (теперь вашего дочернего цикла) добавьте в стек.Продолжайте проходить по стеку до тех пор, пока он окончательно не опустеет.

Это не проверено, но это должно делать именно то, что вы ищете.Я просто использую java.io.File вместо вашего "ITree", так как я могу скомпилировать его:

int sizeOfTree(File root){
    // Start the counter at 1 because the root node counts

    int size = 1;

    LinkedList<File> stack = new LinkedList<File>();
    stack.add(root);

    while(!stack.isEmpty()){
        File f = stack.remove();
        for(File child : f.listFiles()){
            size++;
            stack.add(child);
        }
    }

    return size;
}
1 голос
/ 21 ноября 2011

Ключевое слово для вашей задачи - рекурсия.Дерево - это классическая рекурсивная структура, поэтому вы должны написать рекурсивный метод, который принимает корневые узлы, подсчитывает размер этого узла и затем вызывает себя для всех дочерних элементов.Вот псевдокод:

public int getSize(ITree root) {
    return getSize(root, 0);
}

private int getSize(ITree node, int size) {
    size++;
    for(ITree child : node.children()) {
        size += getSize(child, size)
    }
    return size;
}
1 голос
/ 21 ноября 2011

Использование рекурсивной структуры данных

Практически невозможно итеративно пройти по рекурсивной структуре данных, например дереву с указателями - это из-за того, что объекты "скрывают"«их базовые элементы данных.

Использование другой структуры данных

Все деревья могут быть сохранены / реализованы как линейные структуры данных массива, где индексы могут быть рассчитаны с использованием экспоненциальной математики:

Например, дерево [0, 1, 2, 3, null, 4, null] будет описывать дерево с 0 в корне, где 0 имеет прямые дочерние элементы 1 и 2. А затем 1 оставил дочерний элемент "3", а 2 оставили дочерний элемент" 4 ".

Таким образом, если вы храните дерево таким образом, количество элементов, естественно, равно количеству ненулевых элементов в массиве.

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

...