Сравнение соседних детей в дереве не происходит?

Question

Что не так с этим методом?кажется, но я не уверен, что сравнение соседних дочерних элементов в дереве не имеет места.

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

public static int MAX(BST B) {
  int m = ((Integer) B.root.data).intValue();
  return call(B.root, m);
}

public static int call(node current, int max) {   
  //first helper method gets the max from two different levels in the tree
  if(current == null)
    return -1;
  if(current.left == null && current.right == null)
    return max;
  else {
    if(((Integer) current.data).intValue()>max)
      max = ((Integer) current.data).intValue();
    return compare(call(current.left,max),call(current.right,max));
  }
}

//second helper method gets the max
static int compare(int m1, int m2) {
  if(m1>m2)
    return m1;
  else 
    return m2;
}

Answer 1

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

Ошибка в функции вызова с:

 if(current.left==null&&current.right==null) return max;

Представьте себеу вас есть дерево с корнем с двумя листовыми узлами (всего три узла).Корень имеет значение 3, правый имеет значение 2, а левый имеет значение 5. Алгоритм должен вернуть 5, но ваш код вернет 3. Это потому, что вы игнорируете значение любого листа (узла без «потомков») сэта строка кода.Таким образом, ваш код игнорирует значение 5, в этом примере, и возвращает максимальное значение, равное 3.

. Это можно исправить, возвращая сравнение (current.value, max), когда левый и правый значения равны нулю.

Answer 2

... Понятия не имею, как работает рекурсия ...

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

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

Этот метод не рекурсивен: хотя и имеет плохое имя.

static int compare(int m1, int m2) {
  if(m1>m2)
    return m1;
  else 
    return m2;
}

и может быть записан (и переименован) как

static int min(final int m1, final int m2)
{
    return Math.min(m1,m2);
}

или просто inlined в

return Math.min(call(current.left,max),call(current.right,max));

в любом случае, вы получаете minimumдва значения, на самом деле не сравнивая их, что подразумевает другую логику и другое возвращаемое значение.

В любом случае этот метод не является рекурсивным, и если логика m1 > m2 является подходящей, это не может быть проблемой,больше похоже на вклад в это еunction - не то, что вы ожидаете.

Пошаговая отладка - это мощный инструмент, который каждый опытный разработчик использует каждый день!

Answer 3

Я думаю (не на 100%), что у вас может быть проблема, потому что вы проверяете, являются ли ОБА дочерние элементы нулевыми, если, например, право равно нулю, а левое - нет, вы попытаетесь вызвать метод call как справа, так и.Возможно, добавьте проверку случая, если один дочерний элемент равен нулю, и если да, верните call ненулевого дочернего элемента.