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

  • 11
  • Недоступна
Любое дерево начинается с корня, поэтому не забудь в класс CustomTree добавить поле root типа Entry<String> c модификатором доступа по умолчанию. Инициируй его в конструкторе CustomTree, имя (elementName) не важно. Итак, основа дерева создана, пора тебе поработать немного самому. Вспомним как должно выглядеть наше дерево.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (123)
  • популярные
  • новые
  • старые
Для того, что бы оставить комментарий вы должны авторизоваться
Katya Petrushenko23 уровень, Санкт-Петербург
пятница, 22:01
ArrayList<Entry>
Anonymous #101375636 уровень
четверг, 09:24
Читайте комментарии, господа. Спасибо всем написавшим про инициализацию корня, неправильную картинку в условии, метод size. Внутри класса отдельных структур для хранения элементов дерева не использую. Есть root, всё остальное крепится к нему через ссылки leftChild и rightChild. Методами checkChildren(), isAvailableToAddChildren() не пользуюсь. Все проверки, касающиеся потомков, провожу непосредственно при обходе. В методе add (внутри прикручена вспомогательная очередь) прохожусь при помощи Breadth-first search по слоям дерева, слева направо, вставляю в первый свободный слот. Внутри size() использую отдельный рекурсивный метод, который считает размер поддерева (включая текущий элемент), - запускаю его с параметром root и потом от общего результата отнимаю единицу (сам корень). Помогли ссылки: https://learnc.info/adt/binary_tree_traversal.html - обход дерева в ширину, там псевдокод, использую для метода add() http://www.devinline.com/2013/10/find-size-of-binary-tree-in-java.html - короткий рекурсивный способ для нахождения размера дерева Масса времени была потрачена на попытки корректной реализации метода remove(), который все обсуждали в комментариях, а потом оказалось, что его мы пишем в следующей части задачи.
NodeOne32 уровень
3 ноября, 14:20
Походу структура дерева такова, что добавление происходит всегда с лева на право горизонтально начиная с самого нижнего самого левого узла. При удалении удаляется вся ветка за удаляемым узлом.
NodeOne32 уровень
3 ноября, 11:06
почему элемент 16 добавляется левым чилдреном на 9. В чем логика?
Rodriguez32 уровень
4 ноября, 18:05
Раз на картинке 16 элемент вставлен наследником 9, а не наследником 1, из этого четко следует, что нельзя вставить элемент в пустое место, если ниже по уровню есть элементы со значением меньшим чем у добавляемого, а следовательно, при вставке нужно сравнивать значения, что я и делал - парсил строку в int и сравнивал. В итоге - 4 попытки и продолбался целый день, пытаясь понять что не устраивает валидатор. На самом деле нужно вставлять новый элемент в любое свободное место в направлении слева-направо, а названия элементов вообще никакого значения не имеют. То есть картинка неверная, и вводит в заблуждение. 16 элемент должен быть вставлен потомком 1, а не потомком 9. Условие составлял явный неадекват.
NodeOne32 уровень
5 ноября, 17:52
т.е. если левый чилдрен первого ранее был удален это не служит поводом ничего не добавлять на его место? и при обнаружении отсутствующего левого чилдрена нет смысла проверять есть ли ряды ниже? Можно сразу отсюда начинать рости?
Rodriguez32 уровень
5 ноября, 19:17
Да. На рисунке ошибка, либо намеренный ввод в заблуждение - мне непонятно зачем его так нарисовали. На третьем рисунке 16 элемент должен быть левым потомком 1-го, хотя в условии следующей задачи, в проверке через sout указано что ожидается, будто он должен быть потомком 9-го.
Rodriguez32 уровень
3 ноября, 03:29
Почему во всем дереве нечетные элементы добавляются слева, а четные справа, и вдруг элемент 16 добавляется слева? В чем тогда логика?
Сергей Мурин34 уровень
17 октября, 08:57
1. Имена узлов уникальные, поэтому для хранения можно использовать HashMap 2. Очередь такая как PriorityQueue требует реализации comparable, поэтому чтобы не делать лишней работы можно использовать ArrayList и его метод remove(0) вместо очереди :) 3. Хранение узлов в HashMap позволит быстро найти любой узел и размер дерева 4. При удалении узла, нужно удалить его и всего его дочерние узлы из HashMap 5. Не забываем обновить статус родителя удаляемого узла через checkChildren() P.S. одна попытка. Всего эту задачу решили 841 учеников.
Сергей Мурин34 уровень
17 октября, 09:10
С использованием HashMap есть проблема в следующем задании, так как по условию понятно, что имена узлов не уникальные :) Для следующей задачи, эту пришлось переписывать. Кто бы знал :D
Ilya Sakharov41 уровень, Москва
16 октября, 16:21
Сделал где-то за час с первой попытки. Люблю рекурсии, куда деваться. В size root элемент не должен учитываться. Вижу, что многие делали через очереди :O. Дайте пож-та ссылку на материал или пример, как это сделать через очереди. Даже не представляю как это.
Сергей Мурин34 уровень
17 октября, 09:05
"Первый зашел, первый вышел" - один из принципов очередей. Используя этот принцип, алгоритм следующий: 1. Помещаем в очередь родительский объект 2. Вызываем функцию перебора, которая будет выполняться до тех пор, пока очередь не пустая. Также её всегда можно прервать через return 3. Функция перебора, используя remove(), изымает первый элемент из очереди (el1) 4. Осуществляем некоторую работу с этим элементом 5. Если работу необходимо продолжить с дочерними элементами (el1_1 и el1_2) предыдущего элемента (el1), то добавляем их в очередь 6. Поскольку первоначальный элемент нас не удовлетворил (el1) и мы опять пополнили очередь, то она не пустая и алгоритм продолжит выполняться. P.S. постарался объяснить не прибегая к спойлерам :)
Nikita Krutov37 уровень
8 октября, 18:53
Посмотрел ссылки, которые любезно предоставили сокурсники - очень помогло. Решил через Queue без рекурсий. На удивление прошло с первой попытки, я 822.
Mark34 уровень, Санкт-Петербург
5 октября, 11:50
С очередью все огонь, красиво. Cам сразу не догадался как с ней сделать, пришлось гуглить . 813 с одной попытки.
29 сентября, 18:08
Вы решили задачу лучше, чем 80% учеников. Вам удалось ее решить с 1 попытки. Среднее количество попыток для этой задачи 5.48. Всего эту задачу решили 803 учеников. На задачу потратил примерно 5,5 часов, но я её все таки решил! Попутно вспомнил про бинарные деревья и способы их обхода. В нашем случае используется алгоритм BFS - обход дерева в ширину. Я рекурсии тут не использовал, использовал очередь для обхода дерева. И да, а что так мало народу то решило эту задачу? Да, она не простая, соглашусь, но всё же, это очень пригодиться. Так же почитайте про оценку сложности алгоритмов, тоже пригодиться.