Уже запуталась немного как восстанавливать возможность иметь детей. Сделала так: если больше не осталось вершин,способных иметь детей,то в дереве нахожу все бездетные вершины и добавляю их в главную очередь (leaves).
public boolean add(String s) {
Entry<String> entry = new Entry<>(s);
if (currentNode==null){ //восстановление потомков, если currentNode == null, значит очередь leaves пуста, надо ее восстановить и
recoverLeaves(root);
currentNode = leaves.poll();
}
if (!currentNode.isAvailableToAddChildren()) {
currentNode = leaves.poll();
}
addChild(entry,currentNode);
size++;
return true;
}
private void recoverLeaves(Entry<String> rootNode){
Queue<Entry<String>> queue = new LinkedList<>();
Entry<String> elem = rootNode;
do{
if (queue.size()!=0) elem = queue.poll();
if (elem.isChildFree()) {
elem.availableToAddLeftChildren = true;
elem.availableToAddRightChildren = true;
leaves.add(elem);
} else {
if (elem.leftChild!=null) queue.add(elem.leftChild);
if (elem.rightChild!=null) queue.add(elem.rightChild);
};
}while (queue.size()!=0);
}
Пример работает вроде норм.Но видно, что -то я упустила.
package com.javarush.task.task20.task2028;
import java.util.List;
public class Solution {
public static void main(String[] args) {
List<String> list = new CustomTree();
for (int i = 1; i < 16; i++) {
list.add(String.valueOf(i));
}
// System.out.println("The list size is " + list.size());
// System.out.println("The expected parent is 3. The actual parent is " + ((CustomTree) list).getParent("8"));
//System.out.println("The expected parent is null. The actual parent is " + ((CustomTree) list).getParent("20"));
// list.remove("6");
list.remove("3");
System.out.println("The expected parent is null. The actual parent is " + ((CustomTree) list).getParent("8"));
list.add("16");
System.out.println("The expected parent is 9. The actual parent is " + ((CustomTree) list).getParent("16"));
list.remove("4");
list.remove("5");
list.remove("6");
// list.remove("4");
// list.remove("5");
// list.remove("3");
System.out.println("Expected: true. Actual: " + list.add("20"));
System.out.println("The expected parent is 1. The actual parent is " + ((CustomTree) list).getParent("20"));
}
}