迭代遍历树找到大小

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

我的方法是从根节点开始，访问子节点，然后访问这些子节点的子节点，等等。

这是我写的代码，适用于一棵小树，但并不是真正的解决办法，因为我需要添加一个额外的块的每一个层次：

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

来源

2011-11-21 Matt

我认为这是你的一个类似的问题：http://stackoverflow.com/questions/547622/counting-nodes-in-a-tree-in-java你或许可以找到有些答案在那里。 –

我之前读过的文章很有帮助，但这棵树不是二元的，我需要迭代地做。 – Matt

概念，保留一个堆栈（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; 
}

来源

2011-11-21 17:11:35 ziesemer

使用LinkedList将提供请求的“迭代”遍历，而不是使用递归 - 这可能会导致堆栈溢出。 – ziesemer

仍然不明白发生了什么，但通过选票来判断你是正确的，所以非常感谢:) – Matt

感谢接受 - 但我想帮助消除你有任何困惑。我可以详细说明一下吗？ – ziesemer

使用递归数据结构

它实际上不可能反复地遍历的递归数据结构，就像带指针的树 - 这是因为对象“隐藏”了其基础数据元素。

使用不同的数据结构

，所有的树可以被存储/为线性，阵列的数据结构，其中索引可以用指数数学计算实现：

例如，一棵树[0 ，1，2，3，null，4，null]将描述一棵在根上具有0的树，其中0具有直接的孩子1和2.然后1离开孩子“3”，并且2离开孩子“4” 。因此，如果以这种方式存储树，则元素的数量自然就是数组中非空元素的数量。

更简单：将树存储在一个线性结构中，并且您可以在任何给定时间知道长度，而无需制作任何类型的花式算法。

来源

2011-11-21 17:14:44 jayunit100

您的任务的关键词是递归。树是一个经典的递归结构，因此您应该编写接受根节点的递归方法，计算此节点的大小，然后为所有子节点调用自身。下面是伪代码：

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

来源

2011-11-21 17:15:07 AlexR

但这不仅是递归的，它也是迭代的。我可以使用递归吗？或者只是迭代？（不是两个） – Matt

请解释当你说“互动”时你的意思是什么 – AlexR

迭代遍历树找到大小

回答

相关问题