Написал дополнительный метод для использования рекурсии при добавлении элемента. Метод add(String element) возвращает true или false в зависимости от того, изменился ли размер дерева. Программу тестировал, всё работает. Не пойму что не нравится валидатору.
Любое дерево начинается с корня, поэтому не забудь в класс 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.AbstractList;
import java.util.Collection;
import java.util.List;
public class CustomTree extends AbstractList<String> implements Cloneable, Serializable {
public Entry<String> root;
private int size = 0;
public CustomTree(Entry<String> root) {
this.root = new Entry<>("0");
}
@Override
public String get(int index) {
throw new UnsupportedOperationException();
}
@Override
public int size() {
return size;
}
@Override
public String set(int index, String element) {
throw new UnsupportedOperationException();
}
@Override
public boolean add(String element) {
int isSizeChanged = size;
myAddMethod(element, root);
return isSizeChanged != size;
}
// написал дополнительный метод для использования рекурсии
public void myAddMethod(String element, Entry<String> root) {
if (root.isAvailableToAddChildren()) {
if (Integer.parseInt(element) > Integer.parseInt(root.elementName)) {
if (root.availableToAddRightChildren) {
root.rightChild = new Entry<>(element);
root.availableToAddRightChildren = false;
root.rightChild.parent = root;
size++;
} else {
myAddMethod(element, root.rightChild);
}
} else if (Integer.parseInt(element) < Integer.parseInt(root.elementName)) {
if (root.availableToAddLeftChildren) {
root.leftChild = new Entry<>(element);
root.availableToAddLeftChildren = false;
root.leftChild.parent = root;
size++;
} else {
myAddMethod(element, root.leftChild);
}
}
} else {
if (Integer.parseInt(element) > Integer.parseInt(root.elementName)) {
myAddMethod(element, root.rightChild);
} else if (Integer.parseInt(element) < Integer.parseInt(root.elementName)) {
myAddMethod(element, root.leftChild);
}
}
}
public String getParent(String s) {
Entry<String> tmpEntry = root;
String result = "";
while (tmpEntry != null) {
if (Integer.parseInt(tmpEntry.elementName) == Integer.parseInt(s)) {
result = tmpEntry.elementName;
break;
} else {
if (Integer.parseInt(tmpEntry.elementName) > Integer.parseInt(s)) {
tmpEntry = tmpEntry.leftChild;
} else {
tmpEntry = tmpEntry.rightChild;
}
}
}
return result;
}
@Override
public String remove(int index) {
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();
}
@Override
public boolean addAll(int index, Collection<? extends String> c) {
throw new UnsupportedOperationException();
}
static class Entry<T> implements Serializable, Comparable<Entry<String>> {
public String elementName;
public boolean availableToAddLeftChildren;
public boolean availableToAddRightChildren;
public Entry<T> parent;
public Entry<T> leftChild;
public Entry<T> rightChild;
public Entry(String elementName) {
this.elementName = elementName;
availableToAddLeftChildren = true;
availableToAddRightChildren = true;
}
public boolean isAvailableToAddChildren() {
return availableToAddLeftChildren || availableToAddRightChildren;
}
@Override
public int compareTo(Entry<String> o) {
return Integer.parseInt(elementName) - Integer.parseInt(o.elementName);
}
}
}
0
Комментарии (1)
популярные
новые
старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
