java - 迭代遍历树以查找大小

Question

我需要使用迭代算法查找树中元素的数量，但我发现代码在概念上很难编写。

我的做法是从根节点开始访问子节点，然后是这些子节点的子节点，以此类推。

这是我为一棵小树编写的代码，但不是真正的解决方案，因为我需要为每个深度级别添加一个额外的 block :

// 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;

Answer 1

概念上，保持一个栈(LinkedList等)。对于每个 child (现在，你的 child 循环)，添加到堆栈。继续遍历堆栈，直到它最终为空。

这没有经过测试，但这应该完全符合您的要求。我只是使用 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;
}