Java Tree Debugging

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 для узла и верните это значение.

КПП. почему у вас есть как tree, так и root атрибутов в классе ArrayTree? Не достаточно корневой узел? Почему у вас есть отдельный класс ArrayTree? ArrayTreeNode для себя уже является деревом.

Где вы устанавливаете атрибут parent вашего класса ArrayTreeNode? Не было бы лучше, если бы вы установили родительский элемент внутри метода addChild(), чтобы гарантировать, что parent всегда действителен?

Update:

Хорошо, вы просили пример. Я думаю, что если вы не привыкли к рекурсии, не так-то просто обдумать ее.

Это метод класса 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; 
}