Вопрос из теста (рекурсивное проектирование) - Деревья - Java - PullRequest
Новая
       4

Вопрос из теста (рекурсивное проектирование) - Деревья - Java

0 голосов
/ 27 июня 2011

Я попытался ответить на следующие 2 вопроса, они взяты из теста курса Java, но это немного сбивает с толку из-за рекурсии, которую мне, вероятно, нужно использовать.

Первый - этометод, который получает корень двоичного дерева и возвращает максимальное значение для дерева.(пример на рисунке A).

Этот вопрос (и второй) гласит только завершено в пропущенных строках: 

public static int maxInTree (Node root)
{
    if (root == null)
        return 0;
    if ((root.getLeftSon() == null) && (root.getRightSon() == null))
        ______________________    // I think that here: *return 1*;
    if (root.getLeftSon() == null)
    return _________________
    if (___________ == null)    // I think that here: *root.getRightSon()*
    _______________________________-
    return max______________________________
}

Второй вопрос говорит: сделатьтак же, как и первый вопрос, НО для сортированного бинарного дерева поиска . 

public static int maxInSearchTree (Node r)
{
    if (r == null)
        return 0;
    if (r.getRightSon() == null)
        __________________________
    return _______________________________
}

Можно предположить, что существует метод извлечения отца: getNumber () .

Thnx !!

Ответы [ 3 ]

1 голос
/ 27 июня 2011

Не полный ответ, так как Томас охватил многое из того, что я уже сказал.Однако несколько дополнительных советов:

Левый и правый дочерние узлы вашего корневого узла сами являются корневыми узлами левого и правого поддеревьев.Учитывая это, чтобы получить максимальное значение левого и правого поддеревьев, вам нужно вызвать рекурсивный метод maxInTree(Node node) с левым или правым дочерним элементом в качестве аргумента.

Если ваше неупорядоченное дерево имеет тольколевое ИЛИ правое поддерево, тогда максимальное значение будет больше значения корневых узлов и максимального значения в левом или правом поддереве.

1 голос
/ 27 июня 2011

Я предполагаю, что getNumber () дает значение (не отца). 

public static int maxInTree (Node root)
{
    if (root == null)
        return 0;
    if ((root.getLeftSon() == null) && (root.getRightSon() == null))
        return root.getNumber();
    if (root.getLeftSon() == null)
        return max(root.getNumber(), maxInTree(root.getRightSon()));
    if (root.getRightSon() == null)
        return max(root.getNumber(), maxInTree(root.getLeftSon()));
    return max(root.getNumber(),
        max(maxInTree(root.getLeftSon()),maxInTree(root.getRightSon())));
}

public static int maxInSearchTree (Node r)
{
    if (r == null)
        return 0;
    if (r.getRightSon() == null)
        return r.getNumber();
    return maxInSearchTree(r.getRightSon());
}
1 голос
/ 27 июня 2011

Вы должны подумать о макете дерева, а также о желаемом результате. Некоторые подсказки:

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