我需要使用迭代算法找到树中元素的数量,但我发现代码在概念上很难编写.
我的方法是从根节点开始并访问子节点,然后访问这些子节点的子节点,依此类推.
这是我编写的适用于小树的代码,但不是真正的解决方案,因为我需要为每个深度级别添加一个额外的块:
// 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;
解决方法
从概念上讲,保持堆栈(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; }