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

  • 11
  • Недоступна
Любое дерево начинается с корня, поэтому не забудь в класс CustomTree добавить поле root типа Entry<String> c модификатором доступа по умолчанию. Инициируй его в конструкторе CustomTree, имя (elementName) не важно. Итак, основа дерева создана, пора тебе поработать немного самому. Вспомним как должно выглядеть наше дерево.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (128)
  • популярные
  • новые
  • старые
Для того, что бы оставить комментарий вы должны авторизоваться
Aleksandr35 уровень
2 января, 00:23
Я как почитал и посмотрел различные решения у коллег учащихся, просто ужаснулся. Зачем вы так все усложняете? Зачем эти все мапы и очереди, куча переменных и списков? Я добавил только одну переменную для подсчета элементов в дереве и один лист для хранения всех элементов, остальное все у нас есть. Посмотрите внимательно наши методы и те переменные, которые есть в классе class Entry<T>. Не ищите сложных путей, идите от простого к сложному, а не наоборот. У меня решение заняло пол часа и пол часа читал комменты, да смотрел решения, чтоб узнать, как делали другие, для общего развития.
11 декабря 2018, 03:48
нужно внимательность там где ожидают конструктор без параметров не создайте нечаянно его с параметрами - ошибки будут но указывать они будут просто в потолок
Valeriy2937 уровень
7 декабря 2018, 19:40
Обидно, сделал все правильно с первой попытки, но не принимало... приняло с такой инициализацией:
public CustomTree() {
    this.root = new Entry<>("0");
}
Katya Petrushenko29 уровень, Санкт-Петербург
16 ноября 2018, 22:01
ArrayList<Entry>
Anonymous #101375640 уровень
15 ноября 2018, 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(), который все обсуждали в комментариях, а потом оказалось, что его мы пишем в следующей части задачи.
Алексей Грищенко29 уровень, Санкт-Петербург
27 ноября 2018, 21:36
Для получения размера дерева, адекватней завести поле int size, чтобы метод являлся типичным геттером: public int size() { return size; } тогда в методе add(String e) при добавлении нового узла достаточно делать this.size++; Адекватней это на мой взгляд потому, что размер коллекции должен быть получен за О(1). Это нужно в том числе для того, чтобы(в теории) тот кто будет пользоваться вашей коллекцией к примеру в конструкции типа while (list.size() > 0) не офигевал от того, почему цикл работает так медленно(перед каждой итерацией заново обходит все дерево). Да и на данном этапе проще реализовать именно так. А вот на следующем когда придется реализовывать метод remove(Object o), дополнительно нужно будет реализовать метод прохода по дереву, который будет вызываться внутри remove(Object o), чтобы узнать сколько узлов было стерто и обновить size.
Anonymous #101375640 уровень
3 декабря 2018, 09:31
На самом деле, да. В TreeMap именно так: /** * The number of entries in the tree */ private transient int size = 0; и дальше тот самый геттер для size. UPD ConcurrentSkipListMap в своем методе size() обходит все элементы. (При этом указано, что во время исполнения этого метода количество элементов может поменяться, соответственно, возвращенный функцией результат будет неверным; поэтому метод "для concurrent-приложений не очень полезен" :) Многопоточность такая многопоточность.)
NodeOne36 уровень
3 ноября 2018, 14:20
Походу структура дерева такова, что добавление происходит всегда с лева на право горизонтально начиная с самого нижнего самого левого узла. При удалении удаляется вся ветка за удаляемым узлом.
NodeOne36 уровень
3 ноября 2018, 11:06
почему элемент 16 добавляется левым чилдреном на 9. В чем логика?
Rodriguez32 уровень
4 ноября 2018, 18:05
Раз на картинке 16 элемент вставлен наследником 9, а не наследником 1, из этого четко следует, что нельзя вставить элемент в пустое место, если ниже по уровню есть элементы со значением меньшим чем у добавляемого, а следовательно, при вставке нужно сравнивать значения, что я и делал - парсил строку в int и сравнивал. В итоге - 4 попытки и продолбался целый день, пытаясь понять что не устраивает валидатор. На самом деле нужно вставлять новый элемент в любое свободное место в направлении слева-направо, а названия элементов вообще никакого значения не имеют. То есть картинка неверная, и вводит в заблуждение. 16 элемент должен быть вставлен потомком 1, а не потомком 9. Условие составлял явный неадекват.
NodeOne36 уровень
5 ноября 2018, 17:52
т.е. если левый чилдрен первого ранее был удален это не служит поводом ничего не добавлять на его место? и при обнаружении отсутствующего левого чилдрена нет смысла проверять есть ли ряды ниже? Можно сразу отсюда начинать рости?
Rodriguez32 уровень
5 ноября 2018, 19:17
Да. На рисунке ошибка, либо намеренный ввод в заблуждение - мне непонятно зачем его так нарисовали. На третьем рисунке 16 элемент должен быть левым потомком 1-го, хотя в условии следующей задачи, в проверке через sout указано что ожидается, будто он должен быть потомком 9-го.
Rodriguez32 уровень
3 ноября 2018, 03:29
Почему во всем дереве нечетные элементы добавляются слева, а четные справа, и вдруг элемент 16 добавляется слева? В чем тогда логика?
Сергей Мурин41 уровень
17 октября 2018, 08:57
1. Имена узлов уникальные, поэтому для хранения можно использовать HashMap 2. Очередь такая как PriorityQueue требует реализации comparable, поэтому чтобы не делать лишней работы можно использовать ArrayList и его метод remove(0) вместо очереди :) 3. Хранение узлов в HashMap позволит быстро найти любой узел и размер дерева 4. При удалении узла, нужно удалить его и всего его дочерние узлы из HashMap 5. Не забываем обновить статус родителя удаляемого узла через checkChildren() P.S. одна попытка. Всего эту задачу решили 841 учеников.
Сергей Мурин41 уровень
17 октября 2018, 09:10
С использованием HashMap есть проблема в следующем задании, так как по условию понятно, что имена узлов не уникальные :) Для следующей задачи, эту пришлось переписывать. Кто бы знал :D
Ilya Sakharov41 уровень, Москва
16 октября 2018, 16:21
Сделал где-то за час с первой попытки. Люблю рекурсии, куда деваться. В size root элемент не должен учитываться. Вижу, что многие делали через очереди :O. Дайте пож-та ссылку на материал или пример, как это сделать через очереди. Даже не представляю как это.
Сергей Мурин41 уровень
17 октября 2018, 09:05
"Первый зашел, первый вышел" - один из принципов очередей. Используя этот принцип, алгоритм следующий: 1. Помещаем в очередь родительский объект 2. Вызываем функцию перебора, которая будет выполняться до тех пор, пока очередь не пустая. Также её всегда можно прервать через return 3. Функция перебора, используя remove(), изымает первый элемент из очереди (el1) 4. Осуществляем некоторую работу с этим элементом 5. Если работу необходимо продолжить с дочерними элементами (el1_1 и el1_2) предыдущего элемента (el1), то добавляем их в очередь 6. Поскольку первоначальный элемент нас не удовлетворил (el1) и мы опять пополнили очередь, то она не пустая и алгоритм продолжит выполняться. P.S. постарался объяснить не прибегая к спойлерам :)