Не проходит ни один пункт. Хотя программа работает.
Любое дерево начинается с корня, поэтому не забудь в класс CustomTree добавить поле root типа Entry<String> c модификатором доступа по умолчанию.
Инициируй его в конструкторе CustomTree, имя (elementName) не важно.
Итак, основа дерева создана, пора тебе поработать немного самому.
Вспомним как должно выглядеть наше дерево.
Элементы дерева должны следовать так как показано на картинке:
Необходимо написать методы, которые бы позволили создать такую структуру дерева и проводить операции над ней.
Тебе необходимо:
1) переопределить метод add(String s) - добавляет элементы дерева, в качестве параметра принимает имя элемента (elementName), искать место для вставки начинаем слева направо.
2) переопределить метод size() - возвращает текущее количество элементов в дереве.
3) реализовать метод getParent(String s) - возвращает имя родителя элемента дерева, имя которого было полученного в качестве параметра.
Если необходимо, можешь вводить дополнительные методы и поля, не указанные в задании.
Требования:
- В классе CustomTree должно существовать поле root типа Entry.
- В классе CustomTree должны быть переопределены методы add(String s) и size().
- После добавления N элементов в дерево с помощью метода add, метод size должен возвращать N.
- Метод getParent должен возвращать имя родителя для любого элемента дерева.
package com.javarush.task.task20.task2028;
import java.io.Serializable;
import java.util.*;
/*
Построй дерево(1)
*/
public class CustomTree extends AbstractList<String> implements Cloneable, Serializable{
static Entry<String> root;
public static void main(String[] args) {
root = new Entry<>(String.valueOf(0));
root.parent = null;
//List<String> list = new CustomTree();
CustomTree list = new CustomTree();
for (int i = 1; i < 16; i++) {
list.add(String.valueOf(i));
}
list.printTree();
System.out.println("Count = " + list.size());
list.add("qwe");
list.printTree();
System.out.println("Count = " + list.size());
System.out.println("Parent 4 is " + list.getParent(String.valueOf(4)));
//System.out.println("Expected 3, actual is " + ((CustomTree) list).getParent("8"));
list.remove("3");
list.printTree();
System.out.println("Count = " + list.size());
//System.out.println("Expected null, actual is " + ((CustomTree) list).getParent("11"));
}
@Override
public String get(int index) throws UnsupportedOperationException {
throw new UnsupportedOperationException();
//return null;
}
@Override
public String set(int index, String element) {
return super.set(index, element);
}
@Override
public void add(int index, String element) {
}
@Override
public boolean add(String element) {
Queue<Entry> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
Entry<String> node = queue.poll();
if(node.isAvailableToAddChildren()){
if(node.availableToAddLeftChildren){
node.leftChild = new Entry<>(element);
node.leftChild.parent = node;
node.checkChildren();
return true;
}
else if (node.availableToAddRightChildren) {
node.rightChild = new Entry<>(element);
node.checkChildren();
node.rightChild.parent = node;
return true;
}
}else{
if(node.leftChild != null) queue.add(node.leftChild);
if(node.rightChild != null) queue.add(node.rightChild);
}
}
return false;
}
public static void printTree(){
Queue<Entry> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
//System.out.println("-------");
Entry<String> node = queue.poll();
System.out.print(" (" + node.elementName + ") ");
if(node.leftChild != null) queue.add(node.leftChild);
if(node.rightChild != null) queue.add(node.rightChild);
}
}
public boolean remove(Object o){
String remov = (String)o;
Queue<Entry> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
Entry<String> node = queue.poll();
if (node.elementName.equals(remov)) {
node.checkChildren();
if(node.parent != null){
if(node.parent.leftChild.elementName.equals(remov)){
node.parent.leftChild = null;
node.parent.availableToAddLeftChildren = false;
return true;
}
if(node.parent.rightChild.elementName.equals(remov)){
node.parent.rightChild = null;
node.parent.availableToAddRightChildren = false;
return true;
}
}
}
if(node.leftChild != null) queue.add(node.leftChild);
if(node.rightChild != null) queue.add(node.rightChild);
}
return false;
}
public String getParent(String s){
Queue<Entry> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
Entry<String> node = queue.poll();
if(node.parent != null) {
if (s.equals(node.elementName)) return node.parent.elementName;
}
if(node.leftChild != null) queue.add(node.leftChild);
if(node.rightChild != null) queue.add(node.rightChild);
}
return "no element";
}
@Override
public String remove(int index) {
return super.remove(index);
}
@Override
public boolean addAll(int index, Collection<? extends String> c) {
throw new UnsupportedOperationException();
// return super.addAll(index, c);
}
@Override
public List<String> subList(int fromIndex, int toIndex) {
throw new UnsupportedOperationException();
//return super.subList(fromIndex, toIndex);
}
protected void removeRange(int fromIndex, int toIndex){
throw new UnsupportedOperationException();
}
@Override
public int size() {
if (root == null) {
return 0;
}
int count = 0;
Queue<Entry> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
count++;
Entry<String> node = queue.poll();
if(node.leftChild != null) queue.add(node.leftChild);
if(node.rightChild != null) queue.add(node.rightChild);
}
return count-1;
}
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;
this.availableToAddLeftChildren = true;
this.availableToAddRightChildren = true;
}
void checkChildren(){
if(this.leftChild != null) this.availableToAddLeftChildren = false;
if(this.rightChild != null) this.availableToAddRightChildren = false;
}
boolean isAvailableToAddChildren(){
return availableToAddLeftChildren || availableToAddRightChildren;
}
}
}