Java 树调试

Question

我正在尝试实现一种方法来从根向下计数树的所有节点。基本上我计算根，然后添加每个根子列表的长度。

       public int size() 
       {
            int count = 1; //count the root node
            for (int i = 0; i < root.getChildren().size(); i++){
                count += (root.getChildren().get(i)).length() + 1;
            }
            return count;
        }

这是已解决的解决方案。

Answer 1

您可以将 size() 方法实现为 ArrayTreeNode 的成员。使用递归。节点的大小是 1 加上子节点大小的总和。

因此，在您的 size() 方法中，您有两种情况:

1. 如果节点是叶子，则返回1。这里没有递归调用。

2. 如果该节点有子节点，则调用所有子节点的 size() 方法，计算总和，为该节点加 1 并返回该值。

顺便说一句。为什么 ArrayTree 类中同时具有 tree 和 root 属性？根节点还不够吗？为什么你有一个单独的类ArrayTree？ ArrayTreeNode 本身已经是一棵树了。

在哪里设置 ArrayTreeNode 类的 parent 属性？如果您在 addChild() 方法中设置父级以确保 parent 始终有效，这不是最好吗？

更新:

好的，您要求提供一个示例。我认为如果您不习惯递归，那么理解它并不容易。

这是ArrayTreeNode类的方法:

public int size() {
  int sum = 1; // Count at least this node

  // Ask every child for its size. If this node is a leaf,
  // then no recursive call happens.
  // Otherwise call the size() method recursively for ervery 
  // child node. The child's size() method may also call its 
  // own childs size() method, adding another level of recursion.
  // But we can be sure that the recursion comes to an end because 
  // at every leaf the simple answer will be 1. 
  for(ArrayTreeNode<E> child: children) {
    sum += child.size();
  }

  // return our calculated size. 
  return sum;
}