?????
Добавлять в дерево элементы мы можем, теперь займись удалением:
необходимо реализовать метод remove(Object o) для удаления элемента дерева, имя которого было получено в качестве параметра.
Если переданный объект не является строкой, метод должен бросить UnsupportedOperationException.
Если в дереве присутствует несколько элементов с переданным именем - можешь удалить только первый найденный.
Не забывай сверять поведение своего дерева с картинкой:
Что будет, если удалить из дерева элементы "3", "4", "5" и "6", а затем попытаться добавить новый елемент?
В таком случае элементы "1" и "2" должны восстановить возможность иметь потомков (возможно, придется внести изменения в метод add()).Требования:
- После удаления последнего добавленного элемента из дерева с помощью метода remove, метод size должен возвращать N-1.
- После удаления второго элемента добавленного в дерево, метод size должен возвращать N/2 + 1 (для случаев где N > 2 и является степенью двойки), N - размер дерева до удаления.
- Если переданный объект не является строкой, метод remove() должен бросить UnsupportedOperationException.
- Если ни один элемент не способен иметь потомков, необходимо восстановить такую возможность.
package com.javarush.task.task20.task2028;
import java.io.Serializable;
import java.util.*;
/*
Построй дерево(1)
*/
public class CustomTree extends AbstractList<String> implements Cloneable, Serializable {
Entry<String> root;
private int size;
public CustomTree() {
root = new Entry<>("0", null, 0);
}
@Override
public boolean add(String s) {
Entry<String> entry = getEntryForAdd();
entry.addChild(new Entry<>(s, entry, entry.lineNumber + 1));
size++;
return true;
}
@Override
public int size() {
return size;
}
public String getParent(String s) {
Queue<Entry<String>> queue = new LinkedList<>();
queue.add(root);
Entry<String> entry;
String parentName = null;
while (!queue.isEmpty()) {
entry = queue.poll();
if (s.equals(entry.elementName)) {
parentName = (entry.parent != null) ? entry.parent.elementName : null;
break;
} else {
if (entry.leftChild != null) queue.add(entry.leftChild);
if (entry.rightChild != null) queue.add(entry.rightChild);
}
}
return parentName;
}
@Override
public boolean remove(Object o) {
if (o.getClass() != String.class) throw new UnsupportedOperationException();
String elementName = (String) o;
Queue<Entry<String>> queue = new LinkedList<>();
queue.add(root);
Entry<String> entry = null;
while (!queue.isEmpty()) {
entry = queue.poll();
if (elementName.equals(entry.elementName)) {
break;
} else {
if (entry.leftChild != null) queue.add(entry.leftChild);
if (entry.rightChild != null) queue.add(entry.rightChild);
}
}
if (entry == null) return false;
if (entry == entry.parent.leftChild) entry.parent.leftChild = null;
else entry.parent.rightChild = null;
queue.clear();
Deque<Entry<String>> stack = new LinkedList<>();
queue.add(entry);
while (!queue.isEmpty()) {
entry = queue.poll();
stack.add(entry);
if (entry.leftChild != null) queue.add(entry.leftChild);
if (entry.rightChild != null) queue.add(entry.rightChild);
}
while (!stack.isEmpty()) {
entry = stack.pollLast();
entry = null;
size--;
}
return true;
}
@Override
public String get(int index) {
throw new UnsupportedOperationException();
}
@Override
public String set(int index, String element) {
throw new UnsupportedOperationException();
}
@Override
public void add(int index, String element) {
throw new UnsupportedOperationException();
}
@Override
public String remove(int index) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(int index, Collection<? extends String> c) {
throw new UnsupportedOperationException();
}
@Override
public List<String> subList(int fromIndex, int toIndex) {
throw new UnsupportedOperationException();
}
@Override
protected void removeRange(int fromIndex, int toIndex) {
throw new UnsupportedOperationException();
}
static class Entry<T> implements Serializable {
String elementName;
int lineNumber;
boolean availableToAddLeftChildren, availableToAddRightChildren;
Entry<T> parent, leftChild, rightChild;
public Entry(String elementName) {
this.elementName = elementName;
availableToAddLeftChildren = true;
availableToAddRightChildren = true;
}
public Entry(String elementName, Entry<T> parent, int lineNumber) {
this.elementName = elementName;
this.parent = parent;
this.lineNumber = lineNumber;
availableToAddLeftChildren = true;
availableToAddRightChildren = true;
}
void checkChildren() {
if (leftChild != null) availableToAddLeftChildren = false;
if (rightChild != null) availableToAddRightChildren = false;
}
public boolean isAvailableToAddChildren() {
checkChildren();
return availableToAddLeftChildren || availableToAddRightChildren;
}
public void addChild(Entry<T> child) {
if (availableToAddLeftChildren) leftChild = child;
else rightChild = child;
}
}
Entry<String> getEntryForAdd() {
// очередь для обхода дерева, ищем узел куда можно добавить новый
Queue<Entry<String>> queue = new LinkedList<>();
queue.add(root);
Entry<String> entry = null;
while (!queue.isEmpty()) {
entry = queue.poll();
if (entry.isAvailableToAddChildren()) {
break; // узел найден, выход
} else {
if (entry.leftChild != null) queue.add(entry.leftChild);
if (entry.rightChild != null) queue.add(entry.rightChild);
entry = null;
}
}
if (entry == null) { // ни одного узла не найдено
// еще раз обходим дерево, восстанавливаем возможность добавления детей всем узлам
queue.add(root);
while (!queue.isEmpty()) {
entry = queue.poll();
if (entry.leftChild == null) entry.availableToAddLeftChildren = true;
else queue.add(entry.leftChild);
if (entry.rightChild == null) entry.availableToAddRightChildren = true;
else queue.add(entry.rightChild);
}
// снова ищем узел куда можно добавить новый
queue.add(root);
while (!queue.isEmpty()) {
entry = queue.poll();
if (entry.isAvailableToAddChildren()) {
break;
} else {
if (entry.leftChild != null) queue.add(entry.leftChild);
if (entry.rightChild != null) queue.add(entry.rightChild);
}
}
}
return entry;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Queue<Entry<String>> queue = new LinkedList<>();
queue.add(root);
int level = root.lineNumber;
while (!queue.isEmpty()) {
Entry<String> entry = queue.poll();
if (entry.lineNumber > level) {
sb.append(String.format("%n"));
level = entry.lineNumber;
}
sb.append(String.format("%s ", entry.elementName));
if (entry.leftChild != null) queue.add(entry.leftChild);
if (entry.rightChild != null) queue.add(entry.rightChild);
}
return sb.toString();
}
}