JavaRush/Помощь по Java задачам/4 пункт - Родителем 16 элемента должен являться 7 элемент...

33 уровень

23.08.2021
442просмотров
10комментариев

4 пункт - Родителем 16 элемента должен являться 7 элемент.

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

Решен

раньше я читал что валя писал про 129 и 64 (в других вопросах о помощи) - но и там я не нашел ответа)) не пойму где может быть ошибка) со стороны все как часы, за исключением (уникальности элементов) - но не пропускает ни с ней и без нее) родителей выдает верно)

Любое дерево начинается с корня, поэтому не забудь в класс 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.List; public class Solution { public static void main(String[] args) { List<String> list = new CustomTree(); for (int i = 1; i < 16; i++) { // int s = ((int)(5 + Math.random() * 30)); // проверял разные способы заполнения)) // System.out.println(s + "- random"); // System.out.println(i+s ); list.add(String.valueOf(i)); //System.out.println(((CustomTree)list).getParent(String.valueOf(i+s)) +" - CHILD "+(i+s)); } // list.add("1"); System.out.println("The list size is " + list.size()); System.out.println("The expected parent is 3. The actual parent is " + ((CustomTree) list).getParent("8")); System.out.println("The expected parent is null. The actual parent is " + ((CustomTree) list).getParent("20")); } }

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

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

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

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

Expert

23 августа 2021, 10:13

Попробуйте при создании корневого узла передать в конструктор Entry какую-либо строку вместо null.

Waumok Backend Developer

23 августа 2021, 14:34

public CustomTree() {
    this.root = new Entry<>("");
}

и в методе add соответственно

if (x.elementName.isEmpty()) {

песня та же)) вариант с конструктором и null - это уже результат танцев с бубном)) у меня до этого был перегруженный конструктор, - поменял на этот вариант так как подглядел это в другой просьбе о помощи пока ковырялся

Waumok Backend Developer

23 августа 2021, 14:57

Единственно что пришло в голову сейчас, может конструкция

public boolean isAvailableToAddChildren() {
           return availableToAddRightChildren || availableToAddLeftChildren;
       }

для будущего remove() - типа проверки на отрубленные ветки т.е. я в очередь получается добавляю то что никогда не станет веткой Валя может уже сейчас проверять реализацию list.add("16"); (см рис) после "воображаемого" remove()

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

Expert

23 августа 2021, 15:23

В методе add() из очереди извлекается элемент без предварительной проверки наличия элементов в очереди. Теоретически это может привести к тому, что в переменную x попадёт null (если очередь уже была пуста). Конечно, на данном этапе задачи сложно представить ситуацию, когда ни один из элементов не может присоединять потомков, но полагаю, такой случай всё же стоит обработать.

Waumok Backend Developer

23 августа 2021, 20:23

@Override
public boolean add(String s) {
    if (s == null) return false;
    Queue<Entry<String>> queue = new LinkedList<>();
    Entry<String> x = root;
    if (x.elementName.isEmpty()) {
        x.elementName = s;
        return true;
    }
    while (true) {
        if (x.elementName.equals(s)) return false;
        if (x.leftChild == null && x.availableToAddLeftChildren) {
            x.leftChild = new Entry<>(s);
            x.leftChild.parent = x;
            return true;
        } else if (x.rightChild == null && x.availableToAddRightChildren) {
            x.rightChild = new Entry<>(s);
            x.rightChild.parent = x;
            return true;
        }
        if (x.availableToAddLeftChildren) queue.add(x.leftChild);
        if (x.availableToAddRightChildren) queue.add(x.rightChild);
        if ((x = queue.poll()) == null) return false;
    }
}

public String getParent(String s) {
    if (s == null) return null;
    if (root.elementName.equals(s)) return null;
    Entry<String> x = root;
    Queue<Entry<String>> queue = new LinkedList<>();
    while (true) {
        if (x.elementName.equals(s)) {
            return x.parent.elementName;
        } else {
            if (x.leftChild != null) queue.add(x.leftChild);
            if (x.rightChild != null) queue.add(x.rightChild);
            x = queue.poll();
            if (x == null) return null;
        }
    }
}

Waumok Backend Developer

23 августа 2021, 20:23

public boolean remove(String s) {
    if (s == null) return false;
    Entry<String> x = root;
    Queue<Entry<String>> queue = new LinkedList<>();
    while (true) {
        if (x.elementName.equals(s)) {
            x.availableToAddRightChildren = false;
            x.availableToAddLeftChildren = false;
            if (x == x.parent.leftChild) {
                x.parent.availableToAddLeftChildren = false;
                x.parent.leftChild = null;
            }
            if (x == x.parent.rightChild) {
                x.parent.availableToAddRightChildren = false;
                x.parent.rightChild = null;
            }
            return true;
        } else {
            if (x.leftChild != null && x.availableToAddLeftChildren) queue.add(x.leftChild);
            if (x.rightChild != null && x.availableToAddRightChildren) queue.add(x.rightChild);
            x = queue.poll();
            if (x == null) return false;
        }
    }
}

@Override
public int size() {
    int result = 0;
    Entry<String> x = root;
    Queue<Entry<String>> queue = new LinkedList<>();
    while (x != null) {
        if (x.elementName != null && !x.elementName.isEmpty()) result++;
        if (x.availableToAddLeftChildren) queue.add(x.leftChild);
        if (x.availableToAddRightChildren) queue.add(x.rightChild);
        x = queue.poll();
    }
    return result;
}

для чистоты эксперимента написал remove, и переделал size - тупо обход дерева (так как при удалении элемента удаляются и все его ветки, так проще в общем) результат, все работает валя - не пускает)

Waumok Backend Developer

23 августа 2021, 20:29

"В методе add() из очереди извлекается элемент без пр...."

это верно- поправил) ~~хотя не, - что то не так...~~ - не все норм работает вроде)

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

Expert

23 августа 2021, 21:57

решение

В методе add() инвертируйте условие оператора if на 6 строке. Иначе первый добавляемый в дерево элемент всегда будет записываться на место корневого узла, поскольку имя последнего - пустая строка. Другой вариант - задать иное имя для корневого узла, например, "root". Проверка в 11 строке того же метода гарантирует уникальность имени добавляемого узла, но только в родительской ветке. Например, в пустое дерево вполне можно добавить два узла "1". Но, думаю, проверку на уникальность имени узла делать не обязательно (во всяком случае, раньше этого не требовалось).

Waumok Backend Developer

24 августа 2021, 08:41

Стоп😂, поясните пожалуйста))) я не должен был в корень записывать значение???? Валя не пускал, потому что надо было все это время 1 элемент класть не в корень???)))) а я еще думаю что за странная реализация, почему в Entry<T> нет конструктора без параметров)) и зачем нужен весь этот колхоз с именем корня при создании new CustomTree(); а еще цикл смущал все время в solution начинающийся с 1, хотя соотношение ветви и листа требовало как на картинке) теперь все на место встало) Благодарю за потраченное время 🤝

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

Expert

24 августа 2021, 09:52

Рад, что помог! 🙂