0

Не совсем понимаю как построить само дерево.

В данной задаче рассматриваются бинарные деревья. На рисунке ниже показан пример бинарного дерева, состоящего из семи узлов.

введите сюда описание изображения

Двоичное дерево-это либо пустое дерево, либо узел (называемый корнем), содержащий одно целое значение и связанный с двумя другими двоичными деревьями. Нас интересуют пути (последовательности связанных смежных узлов), которые начинаются в корне и следуют за краями дерева (отмечены стрелками на рисунке выше). Например, последовательность узлов A, B, D является допустимым путем, а последовательность a, B, G-нет.

Проблема

Мы хотим найти максимальное количество различных значений, которые появляются на пути, начиная от корня дерева. Например, на пути, состоящем из узлов A, B, D, G, есть два различных значения (4 и 5). На пути A, C, E есть три различных значения (1, 4 и 6). Не существует пути, содержащего четыре или более различных значений.

Написать функцию: решение класса { public int solution (Tree T); }

это, учитывая двоичное дерево T, состоящее из N узлов, возвращает максимальное количество различных значений, которые появляются на пути, начинающемся с корня дерева T. например, учитывая дерево, показанное выше, функция должна возвращать 3.

Технические подробности

Двоичное дерево задается с помощью структуры данных указателя. Предположим, что приведены следующие объявления:

public class Tree {
    public int x;
    public Tree l;
    public Tree r;
}

Пустое дерево представлено пустым указателем (обозначается null). Непустое дерево представлено указателем на объект, представляющий его корень. Атрибут x содержит целое число, содержащееся в корне, тогда как атрибуты l и r содержат левое и правое поддеревья двоичного дерева соответственно.

Предубеждения

Напишите эффективный алгоритм для следующих предположений: * N-целое число в диапазоне [1..50,000]; • высота дерева t (количество ребер на самом длинном пути от корня до листа) находится в диапазоне [0..3,500]; • каждое значение в дереве T является целым числом в диапазоне [1..Северный.]


@ИмяФамилия Думал вот таки образом

public void  preOrder(Tree tree){
        if (tree == null){
            return;
        }

//тут делать что нибудь со значением листка
        preOrder(tree.l);
        preOrder(tree.r);
    }
}
6
  • А в чём ваша проблема? Предоставьте свой вариант решения.
    – AvidCoder
    10 июл 2019 в 19:48
  • @ИмяФамилия проблема в том, что я не понимаю как построить дерево
    – damcha
    10 июл 2019 в 19:50
  • Вам уже дан класс, описывающий узел, создайте экземпляр узла и приравняйте его l и r к каким-то новым узлам, сделайте то же самое с этими l и r и так далее.
    – AvidCoder
    10 июл 2019 в 19:57
  • @ИмяФамилия то есть мне не нужно писать конструктор ? java Tree tree1 = new Tree(); Tree tree2 = new Tree(); Tree tree3 = new Tree(); tree1.x = 4; tree1.r = tree2; tree1.l = tree3; tree2.x= 6; tree3.x= 5; Таким образом? ,
    – damcha
    10 июл 2019 в 20:11
  • Да, затем ещё сколько вам нужно создаёте, и присоединяете уже к tree2 и tree3. Можете конструктор со всеми полями написать.
    – AvidCoder
    10 июл 2019 в 20:31

1 ответ 1

1

Для удобства вы можете сделать два конструктора: для создания узла с числом и узла со связанными с ним узлами.

public class Tree {
    public int x;
    public Tree l;
    public Tree r;

    public Tree(int x) {
        this.x = x;
    }

    public Tree(int x, Tree l, Tree r) {
        this.x = x;
        this.l = l;
        this.r = r;
    }
}

Создание дерева будет выглядеть так:

Tree tree = new Tree(4,
                new Tree(2, 
                        new Tree(5), null),
                new Tree(2,
                        new Tree(3,
                                new Tree(5),
                                new Tree(4)),
                        new Tree(2)));

Таким способом можно обойти всё дерево и получить максимальное количество различных номеров узлов в дереве:

HashSet<Integer> gatheredValues = new HashSet<>();

public int solution(Tree tree) {
    if(tree == null) return gatheredValues.size();

    boolean notContains = !gatheredValues.contains(tree.x);
    if(notContains) gatheredValues.add(tree.x);

    if(gatheredValues.size() == 3) return 3;

    // int maxValue = Math.max(solution(tree.l),solution(tree.r)). заменено для экономии времени (узлов всё-таки может быть до 50 тысяч!)
    int lValue = solution(tree.l);
    int rValue = solution(tree.r);
    int maxValue = (lValue >= rValue) ? lValue : rValue;

    if(notContains) gatheredValues.remove(tree.x);

    return maxValue;
}
11
  • а как мне его обходить если оно будет принимать такой вид?
    – damcha
    10 июл 2019 в 20:51
  • А это уже другой вопрос. Подумайте сами, если ничего не надумаете, напишите. Тут ещё вопрос, в каком виде поступают данные. В виде массива строк, состоящих из буква типа A B C ... Y Z AA AB ... AZ BA ... BZ CA CB ...?
    – AvidCoder
    10 июл 2019 в 21:01
  • Есть вариант запоминать список текущих узлов, чтобы по порядку подбирать их буквенный номер в процессе подсчёта. Ещё вопрос, есть ли ограничение по времени и памяти? И как, всё-таки, вводятся данные?
    – AvidCoder
    10 июл 2019 в 22:47
  • В теории, такой алгоритм сможет посчитать результат за несколько секунд, но надо ещё проверить.
    – AvidCoder
    11 июл 2019 в 9:34
  • Дерево вроде как я построил. Насколько я понимаю буквы даны нам , для наглядности. И теперь думаю о том, как теперь обойти мое дерево, для того чтобы найти найти максимальное количество различных значений, которые появляются на пути, начиная от корня дерева. если путь возможен, только если на пути встречаются три разных значения. Слишком много думал, ведь смысл задачи написание этой самой функции.
    – damcha
    11 июл 2019 в 10:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.