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

  • 28
  • Недоступна
Любое дерево начинается с корня, поэтому не забудь в класс CustomTree добавить поле root типа Entry<String> c модификатором доступа по умолчанию. Инициируй его в конструкторе CustomTree, имя (elementName) не важно. Итак, основа дерева создана, пора тебе поработать немного самому. Вспомним как должно выглядеть наше дерево.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (354)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Олег
Уровень 33, Москва, Russian Federation
5 августа, 08:44
Месяц ушел на решение. Прочитал книгу Грокаем алгоритмы. Посмотрел на ютубе все про деревья. Потом еще раз посмотрел. Несколько раз просмотрел готовое решение. В итоге до меня, наконец, дошло, что все дерево по сути это двухсвязный список (вниз 2 ссылки, обратно одна), потом долго доходило, а чем обусловлены сами эти ссылки. Дошло, что ссылка похожа на матрешку, где каждое энтри находится внутри другого энтри. Дошло чем обусловлен обход в ширину самого дерева и правильная последовательность добавления. В конце провозился еще 2 часа с NullPointerExeption. В итоге все получилось гораздо лаконичней, чем в решении от джавараш.
Сергей Смирнов
Уровень 35
12 мая, 11:40
1. Создаем список, в который добавляем созданные элементы дерева. 2. В методе add проходясь по списку, спрашиваем у каждого элемента, есть ли у него потомки. 3. Если потомка нет - добавляем.
Александр
Уровень 38, Челябинск, Russian Federation
19 июля, 18:20
Молвил как боженька, 3 строчки и сразу понятно что делать!
Игорь PM в Москва
10 мая, 07:56
Прикольная задачка! Добавлял, всё норм, а size() возвращает либо 16, либо 0, хоть убейся. Если size() делать возврат стандартный size() - 1, то добавляются только нули. Собака оказалась в том, что при добавлении надо не обращаться к size(), а перебирать все элементы, пока не найдётся возможности добавить.
Евгений Т.
Уровень 34, Москва, Россия
27 апреля, 05:09
Пересмотрел видео из комментов почитал и сделал, не могу сказать что очень просто, с одной стороны вроде все понятно с другой стороны надо все это уместить у себя в голове. В целом задача интересная.
Александр Горохов
Уровень 25, Дятьково, Россия
13 апреля, 13:25
Оххохо, 4700 =)
Тимофей
Уровень 51, Москва, Россия
3 марта, 14:37
Много часов ломал голову, часов 8 мб. Строил схемы где считал что если элемент меньше то идет в лефтЧайлд, больше в райтЧайлд. В итоге вчитался в комменты, одурел от того что требуется, по комментам написал за пару мин.
fedyaka
Уровень 36, Кострома, Россия
29 января, 13:17
Посмотрел сначала в решение, понял что там чёрт ногу сломит, сделал по своему, в 10 раз короче и во столько же проще, по факту мы создаём List куда записываем все элементы древа вместе с рутовым(его записываем при инициализации древа). При добавлении нового элемента мы просто проходим по списку проверяя каждый элемент на if(есть ли левый элемент?){ добавляем новый элемент ему новому элементу передаём в родители ссылку на элемент с итерации добавляем новый элемент в список List возвращаем true } else if (есть ли правый элемент?){ делаем тоже самое только для rightChild } Тем самым мы добиваемся того что каждый элемент будет идти в своём порядке. Остальные методы я думаю понятны. Ну и код если совсем не понятно или плохо объясняю😄 ! КАПИТАЛЬНЫЙ СПОЙЛЕР!!!! !
public CustomTree(){
        root = new Entry<String>("df");
        listTree.add(root);

    }

    @Override
    public boolean add(String elementName) {
        for (Entry<String> element : listTree){
            if (element.availableToAddLeftChildren){
                Entry<String> newElement = new Entry<String>(elementName);
                newElement.parent = element;
                element.leftChild = newElement;
                element.availableToAddLeftChildren = false;
                listTree.add(newElement);
                return true;
            } else if (element.availableToAddRightChildren){
                Entry<String> newElement = new Entry<String>(elementName);
                newElement.parent = element;
                element.rightChild = newElement;
                element.availableToAddRightChildren = false;
                listTree.add(newElement);
                return true;
            }
        }
        return false;
    }
fedyaka
Уровень 36, Кострома, Россия
29 января, 13:18
ну и остальные методы, кому интересно
@Override
    public int size() {
        return listTree.size() - 1;
    }

    public String getParent(String s){
        for (Entry<String> element : listTree){
            if (element.elementName != null) {
                if (element.elementName.equals(s)) {
                    if (element.parent.elementName != null) {
                        return element.parent.elementName;
                    } else {
                        return "у него совсем никого нет :\"(";
                    }
                }
            }
        }
        return null;
    }
hidden #2595317
Уровень 45
9 февраля, 10:19
Я тоже так замутил, только, учитывая. что дерево у нас безразмерное, а значит элемент в любом случае добавится, создание нового Entry стоит вынести из фора в самое начало. А из ифов вынести повторяющийся код присвоения ссылки на родителя, добавления в список и возврата тру. А в получении родителя, если у тебя есть в списке элемент с искомым именем, то он просто не может быть null или не иметь родителей. Тут ты как монашка перестраховался излишне.)))
Евгений Т.
Уровень 34, Москва, Россия
27 апреля, 05:07
Тогда уж если выносить повторяющийся код, то надо будет добавить условие проверки есть ли возможность у текущего элемента добавлять чайлда и если нет то пропускать текущий элемент а не всем подряд назначать одного и того же парента. Про метод гет согласен. Сделал так же.
JewArnold
Уровень 46, Russian Federation
5 августа, 12:06
Не мог понять, почему у меня не проходит size и увидел в вашем комментарии что на возврат идет (size -1). С чем это связано?
Александр
Уровень 41, Рыбинск, Россия
23 декабря 2021, 19:48
В принципе задача не сложная. Долго не понимал, что не так. Всё вроде правильно написано, но выдает при getParent(3) null. Оказывается ошибка была в том, что пытался найти подходящий элемент из списка использую List indexOf(). А нужно было пройтись по всему списку и сравнить заданное с полученным.
LuneFox инженер по сопровождению в BIFIT Expert
20 декабря 2021, 16:34
3-4 часа пытался решить через рекурсию, сломал голову, потому что рекурсионно у дерева растёт только одна часть (например, одна левая ветка или две правых ветки), заставить распределять цифры как на картинке не получилось. Однако размер и родители искались через рекурсию вполне нормально. Тем не менее, пришлось все труды стереть и решить через дополнительный LinkedList...
Максим Дудин
Уровень 39, Калининград
18 декабря 2021, 12:08
Оооо вот тут оно и начнётся... 18.12 14:08 18:21 - да ладно, прошло, но.... странно... фиг с ним пока идём дальше, потом вернусь 19,12 13:46 закончил... что бы тут хотелось бы...... 1. Основная сложность была для меня, вот этот момент List<String> list = new CustomTree(); тут не знаю почему и как это работает (видимо потому что CustomTree() наследник AbstractList<String>), но опытным путём выяснил, что: - при вызове всех методов List из main add(), size() и т.д. буду вызываться переопределённые методы из класса CustomTree(). - если в CustomTree() организовать transient List<Entry<String>> entries = new ArrayList<>();, то при вызове list.add(String.valueOf(i)) из main через переопределённый метод add класса CustomTree(), элементы будут добавляться именно в entries (пока этот момент не подсмотрел в готовом решении было не понятно как связать List в mane вычислениями в CustomTree()). - если вызвать для entries эти методы в самом CustomTree(), то они будут стандартные (т.е. при вызове list.get(i) из main получим UnsupportedOperationException(), потому что мы сами его так переопределили, но при вызове entries.get(i) нормально получим i-тый элемент списка ). - несмотря на то что для создания древовидной структуры логично было бы использовать пару индекс - значение (а это прямо наталкивает на Map), где по индексу определяется положение элемента (с каким-то значением) в дереве, здесь все они хранятся в обычном списке. Но список не <String> имён как в main а объектов<Entyr<String>> в которых есть переменные указывающие на то, есть ли у данного элемента списка левый или правый потомок и какой из элементов для него родительский, на чём и строится дальнейшая логика.
Максим Дудин
Уровень 39, Калининград
19 декабря 2021, 12:35
едем дальше... метод add. первое что... сразу - это не тот метод который мы уже переопределили, (он так и останется до конца ненужной заглушкой), а метод boolean add(String element), который там в списке Override тоже был. второе элементы добавляются, согласно рисунку просто с лева на право к первому элементу у которого есть возможность такой элемент добавить, а не между значениями индекса как в правильном дереве (что потом ускорило бы поиск элемента), у нас дерево вот такое, зачем? такое задание. как сделал я: - пробежал по списку entries (там как минимум есть один элемент "корень" который мы должны были положить туда в конструкторе класса CustomTree ) - для каждого элемента списка проверяю может ли данный элемент иметь потомков (такой метод у нас уже есть availableToAddLeftChildren) - если нет , следующий, если да, то создаю новый элемент с именем поданным на вход метода add, новому элементу в качестве родительского присваиваю текущий элемент из списка - и проверяю куда влево или вправо его можно добавить на основании значения availableToAddLeftChildren или vailableToAddRightChildren. сначала для "лево" ( у нас добавление слева на право по условию) если там true, ну значит: - текущему элементу списка в качестве левого потомка добавляю новый элемент entry.leftChild = newEntry; - текущему элементу списка закрываем возможность иметь левых детей =) entry.availableToAddLeftChildren = false; - добавляем новый элемент в список entries.add(newEntry); - и раз дело сделано выходим из метода... return true; если с "лево" не получилось делаем тоже для "право". если вообще ни у кого из узлов нет возможности добавить потомка выходим из метода с false; Это кстати интересный момент/вопрос, что в таком случае делать, решить который вам предложат в следующей задаче
Максим Дудин
Уровень 39, Калининград
19 декабря 2021, 12:46
что там ещё.... метод int size() - Я делал и так и сяк добавлял счетчик при добавлении в add убирал при вычитании в remove, там не всё складывалось потом в итоге... в конце концов решил каждый раз при вызове прогонять цикл по элементам текущего на момент вызова метода списка for (Entry<String> entry : entries) count++ а при выводе убирать корневой элемент (так положено по условию, что корневой не считаем) return count - 1; (пока писал понял ,что и это не нужно просто return entries.size()-1; в нутре-то всё работает в штатном режиме )😀 String getParent(String s) - тут тоже всё просто - прогоняем по списку и если имя элемента списка соответствует поданной на вход строке выводим return entry.parent.elementName;