JavaRush/Помощь по Java задачам/Не проходит по 3 и 4 пунктам.

39 уровень

31.01.2022
743просмотров
7комментариев

Не проходит по 3 и 4 пунктам.

Вопрос по задаче

Построй дерево(4)

Java Collections, 1 уровень, 15 лекция

Решен

Уже сделал проверку всего, что только возможно. Не хочу смотреть в готовое решение, хочу разобраться.

Любое дерево начинается с корня, поэтому не забудь в класс 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.util.Arrays; public class Solution { public static void main(String[] args) { CustomTree list = new CustomTree(); for (int i = 1; i < 200; i++) { list.add(String.valueOf(i)); } String parent; String Lchild; String Rchild; for (CustomTree.Entry<String> entry: list.entries) { if (entry.parent != null) { parent = entry.parent.elementName; } else{ parent = "null"; } if (entry.leftChild != null) { Lchild = entry.leftChild.elementName; } else{ Lchild = "null"; } if (entry.rightChild != null) { Rchild = entry.rightChild.elementName; } else{ Rchild = "null"; } System.out.println("Name: " + entry.elementName + ", Level: " + entry.elementLevel + ", Parent: " + parent + ", L_child: " + Lchild + ", R_child: " + Rchild); } System.out.println("Elements on each level " + Arrays.toString(list.countOfElementsOnLevel)); System.out.println("The list size is " + list.size()); System.out.println("The expected parent is 3. The actual parent is " + list.getParent("129")); System.out.println("The expected parent is null. The actual parent is " + list.getParent("20")); } }

Комментарии (7)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Павел Безумный учёный

Expert

31 января 2022, 22:01

полезный

При определении общего количества элементов в дереве корневой узел не должен учитываться. К примеру, дерево, изображённое в верхней части рисунка в условии, содержит 15 элементов (не 16). Возможно, также стоит предусмотреть обработку случая, когда производится попытка определить родителя корневого узла, чтобы избежать NPE. Подсказка "Родителем 129 элемента должен являться 64 элемент" справедлива лишь для частного случая, когда все 129 элементов добавляются в дерево последовательно в порядке возрастания их значений. В общем случае узлы должны добавляться в дерево слева направо в ближайшее подходящее место, последовательно заполняя уровни (поколения) в дереве. Предположим, мы добавляем в пустое дерево следующие узлы:

add 1
add 3
add 10
add 15
add 12
add 5
add 100
add 50
add 7
add 1000

Тогда полученное дерево будет иметь такой вид:

Произвольный порядок следования значений добавляемых узлов не влияет на их расположение в дереве.

Catharsis

Уровень 39

1 февраля 2022, 10:59

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

Жора Нет

Уровень 39

3 апреля 2022, 13:11

Скажите, пожалуйста, согласно Вашему комментарию, новый элемент должен добавляться в первый свободный элемент(слева-направо и сверху вниз), если я правильно понял. Но тогда вопрос относительно рисунка, приведенного в задании, где новый элемент добавляется не в первый свободный(1), а в элемент нижнего уровня(9)! Так как все таки правильно???

Catharsis

Уровень 39

3 апреля 2022, 19:47

Да, по всей видимости, в 3 рисунке задания элемент 16 должен был добавиться слева внизу от 1.

Павел Безумный учёный

Expert

4 апреля 2022, 11:33

Между логикой добавления нового элемента и рисунком в задании нет противоречия. Если последовательно добавлять элементы в пустое дерево, то они будут распределяться равномерно, образуя максимально симметричное дерево. Но поведение дерева меняется, если ранее была произведена операция удаления узла. В частности, из дерева на рисунке в здании удаляется узел "3", при этом следующий добавляемый узел "16" присоединяется к узлу "9". Такое поведение обусловлено алгоритмом поиска первого подходящего узла, к которому можно присоединить потомка: производится обход узлов дерева, и у каждого узла проверяются значения полей availableToAddLeftChildren и availableToAddRightChildren. Как только найдено подходящее значение (true), новый узел присоединяется в эту позицию. Узел "1" после удаления узла "3" по-прежнему содержит в поле availableToAddLeftChildren значение false (которое было установлено ранее при добавлении узла "3"). Следовательно, при поиске подходящего места узел "1" будет пропущен как неподходящий. Поведение дерева будет зависеть от того, в какой момент значение поля availableToAddLeftChildren должно меняться на true. Заданием предполагается, что это должно происходить лишь в крайнем случае, когда во всём дереве не осталось ни одного узла, к которому можно было бы присоединить потомка. Например, такая ситуация может возникнуть при удалении из дерева узлов "3", "4", "5" и "6". В этом случае нужно для узлов "1" и "2" восстановить возможность иметь потомков, то есть установить их полям availableToAddLeftChildren и availableToAddRightChildren значения true.

Павел Безумный учёный

Expert

4 апреля 2022, 11:33

С другой стороны, можно восстанавливать возможность иметь потомка сразу при удалении узла. Такое решение гарантирует, что в дереве всегда будет подходящее место для нового узла. И хотя оно не вполне соответствует логике рисунка в задании, в некоторых случаях успешно проходило валидацию.

Жора Нет

Уровень 39

8 апреля 2022, 09:10

Да,спасибо за ответ. Очень долго пытался разобраться с пониманием того, куда же все таки добавлять новый элемент после удаления. Комментарии тоже запутали, олни глворят так, другие иначе. Я все же думал, что после удаления элемента, его родителю сразу нужно присвоить возможность availableToAddLeft(Right)Children. И поэтому не мог понять, почему же на рисунке элемент добавляется в 9... Прочитав все комментарии у кого то увидел, что валидатор принимает и с добавлением в 1