Как решить проблему с неизвестным источником в списке массивов?

Question

Мне нужно получить всех потомков узла дерева. Для этого я написал функцию, которая нуждается в вспомогательной функции. Когда я хочу получить результаты, я получаю следующие ошибки:

в java.base / java.util.ArrayList $ Itr.checkForComodification (неизвестный источник) в java.base / java.util.ArrayList $ Itr.next (неизвестный источник)

У меня уже была эта ошибка, поэтому я создал разные списки для каждого метода: дочерние элементы, потомки, предки, элементы и позиции. Теперь у меня везде ошибки.

public List<Position<E>> descendants(Position<E> p) throws InvalidPositionException {
    if(p == null || isEmpty())
            throw new InvalidPositionException();
    // remove all positions from list
    descendantList.removeAll(descendantList);
    return descendantsList(p);
}

public List<Position<E>> descendantsList(Position<E> p) {
    if(isInternal(p)) {
        // add child to list and check if the child has also children
        for(Position<E> child : children(p)) {
            descendantList.add(child);
            // if child has also children
            if(isInternal(child))
                descendantsList(child);
        }
    }
    return descendantList;
}

Функция детей выглядит так:

public List<Position<E>> children(Position<E> p) throws InvalidPositionException {
    if(p == null || isEmpty())
        throw new InvalidPositionException();
    else {
        BinaryTreeNode<E> node = (BinaryTreeNode<E>) p;
        childrenList.removeAll(childrenList);
        // add left child first
        if(node.leftChild != null)
            childrenList.add(node.leftChild);
        if(node.rightChild != null)
            childrenList.add(node.rightChild);
        return childrenList;
    }
}

Для этого я создал разные списки:

- ArrayList for children: childrenList
- ArrayList for descendants: descendantsList

Как я могу решить эту ошибку?

Редактировать: я заменил все removeAll на clear. Он работал для потомков этого метода, но в качестве примера у меня все еще есть та же ошибка для моего метода высоты:

public int height() throws EmptyTreeException {
    if(isEmpty())
        throw new EmptyTreeException();
    else
        return heightOf(root);
}

private int heightOf(Position<E> p) {
    if(isExternal(p))
        return 0;
    else {
        int h = 0;
        for(Position<E> child : children(p)) {
            h = Math.max(h,heightOf(child));
        }
        return h + 1;
    }
}

Answer 1

Я решил это так: Я создал новый список для каждого метода, который использует список детей. При этом я не получил следующую ошибку:

в java.base / java.util.ArrayList $ Itr.checkForComodification (неизвестный источник) в java.base / java.util.ArrayList $ Itr.next (неизвестный источник)

Answer 2

Не используйте removeAll(childrenList).Используйте clear().Во-первых, это быстрее, во-вторых, это может быть там, где вы получаете свою ошибку.removeAll() пошагово просматривает предоставленную коллекцию и удаляет элементы в коллекции, которые ее вызвали.В вашем случае это та же коллекция.

РЕДАКТИРОВАТЬ: ОК.Я вижу, что происходит.Я должен был реализовать это сам, чтобы увидеть.

В основном, что происходит, вы звоните height(root).Он выполняет итерацию по дереву и находит heightOf каждого узла и возвращает его.

в вашем heightOf методе у вас есть цикл for, который использует рекурсию.

вызовы цикла for children(node)который очищает список childrenList и затем заполняет его.

Проблема в первой итерации childrenList присваивается несколько значений.Затем вы снова вызываете heightOf, продолжая ссылаться на Position<E>, расположенный в childrenList (вы называете это Position<E> child).Когда heightOf вызывается снова для потомка, childrenList снова изменяется.Поскольку вы по-прежнему удерживаете ссылку на Position<E> в childrenList и пытаетесь удалить или изменить эту ссылку, вы получаете ConcurrentModificationException.

. Это можно исправить, изменив метод children на что-тонапример:

public List<Position<E>> children(Position<E> p) throws InvalidPositionException {
    List<Position<E>> returnList = new ArrayList<>();
    if(p == null || isEmpty()) {
        throw new InvalidPositionException();
    }else {
        BinaryTreeNode<E> node = (BinaryTreeNode<E>) p;
        // add left child first
        if(node.leftChild != null) {
            returnList.add(node.leftChild);
        }
        if(node.rightChild != null) {
            returnList.add(node.rightChild);
        }
        return returnList;
    }
}

Чтобы поддерживать childrenList всех узлов в дереве, вам, вероятно, потребуется создать новый метод и просто вызвать его один раз.Этот метод будет очень похож на ваш текущий children метод, но вы можете вызывать его рекурсивно для каждого левого и правого дочернего узла.