Использование рекурсивного метода для поиска наименьшего элемента в поддереве с заданным корнем: что я здесь не так делаю?

Question

Итак, у меня есть вопрос по домашней задаче, где я должен использовать рекурсивный метод, чтобы «найти минимальный элемент в поддереве с корнем в указанном узле»

И тогда мне дают это в качестве моего начальноготочка:

   public TreeNode
{
    int data;
    TreeNode left;
    TreeNode right;
}

и

/**
Finds the minimum value for the subtree that is 
rooted at a given node
@param n The root of the subtree
@return The minimum value 
PRECONDITION: n is not null.
*/
int min(TreeNode n)
{
  // COMPLETE THE BODY OF THIS METHOD
}

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

int min(TreeNode n){      
if(n.left != null) {
  n = n.left;
  min(n);
  System.out.println("N is now " + n.value);
 }
    return n.value;
   }

Вывод моего кода:

Building tree with rootvalue 25
  =================================
  Inserted 11 to left of node 25
  Inserted 15 to right of node 11
  Inserted 16 to right of node 15
  Inserted 23 to right of node 16
  Inserted 79 to right of node 25
  Inserted 5 to left of node 11
  Inserted 4 to left of node 5
  Inserted 2 to left of node 4
    Root is 25
    N is now 2
    N is now 4
    N is now 5
    N is now 11
    The minimum integer in the given nodes subtree is: 11

Может кто-нибудь, пожалуйста, объясните мне, почему этоне работает?

Answer 1

Примечание: все это предполагает, что вы находитесь в бинарном дереве поиска, поэтому возвращение минимального элемента означает возврат самого левого элемента.

Это означает, что ваш рекурсивный вызов довольно прост:

min(node):
  if this node has a left node:
    return min(node.left)
  if this node does not have a left node:
    return this node's value

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

Теперь на Java:

int min(TreeNode n){
  if (n.left == null)
    return n.value;
  return min(n.left); // n.left cannot be null here
}

Теперь, чтобы объяснить ваши результаты, рассмотрим, как работает этот метод. Он вызывает метод на следующем узле (min(n.left)) перед продолжением. В вашем случае у вас был println после этого рекурсивного вызова. Поэтому println внутри рекурсивный вызов пошел первым. Таким образом, ваши отпечатки начались с нижней части дерева и вернулись обратно. Это объясняет печать в обратном порядке.
Затем ваш метод возвратил 11 как ваш результат, потому что (как объяснил другой ответ) ваш n = n.left не влиял ни на один из ваших рекурсивных суб-вызовов, только на один в текущем вызове функции. Это означает, что вы вернули левый узел корня, а не самого дальнего левого потомка.

Надеюсь, это имеет смысл. Если вам нужно что-то разъяснить, оставьте комментарий или что-то. Поначалу рекурсия может оказаться довольно сложной задачей.

Answer 2

Проблема в том, что Java является вызовом по значению, не по ссылке, хотя ссылки передаются по значению. Но в данном случае это действительно означает, что вызов min(n) делает , а не изменяет то, к чему относится переменная n - он вообще ничего не делает. Что вы, вероятно, должны делать, это return min(n).

Answer 3

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

Следующий код должен сделать это:

int min(final Tree n){
    int result;
    if(n == null){
        result = Integer.MAX_VALUE;
    } else {
        result = n.value;
        final int leftResult = min(n.left);
        if(leftResult < result){
          result = leftResult;
        }
        final int rightResult = min(n.right);
        if(rightResult < result){
          result = rightResult;
        }
    }
    return result;
}

Или вы можете использовать шаблон «Посетитель» (тогда вам нужно сделать дерево итеративным и передать значения посетителю один за другим):

interface TreeVisitor {
    void accept(int value);
}

class MinTreeVisistor implements TreeVisitor {
    int min = Integer.MAX_VALUE;

    @Override
    public void accept(int value) {
        if(value < this.min) {
          this.min = value;
        }
    }
}

Answer 4

public static void main(String[] args) throws IOException, NoSuchMethodException, InitializationError {
    Logger.getRootLogger().addAppender(new ConsoleAppender(new SimpleLayout(), "System.out"));
    Logger.getRootLogger().setLevel(Level.ALL);

    TreeNode n1 = new TreeNode();
    TreeNode n2 = new TreeNode();
    TreeNode n3 = new TreeNode();
    TreeNode n4 = new TreeNode();
    TreeNode n5 = new TreeNode();
    TreeNode n6 = new TreeNode();
    n1.data = 110;
    n1.left = n2;
    n1.right = n3;
    n2.data = 15;
    n2.left = n4;
    n2.right = null;
    n3.data = 3;
    n3.left = null;
    n3.right = null;
    n4.data = 4;
    n4.left = null;
    n4.right = n5;
    n5.data = 12;
    n5.left = n6;
    n5.right = null;
    n6.data = 19;
    n6.left = null;
    n6.right = null;

    System.out.print("min=" + min(n1));
}

static public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
}

static int min(TreeNode n) {
    return min(n, n.data);
}

static int min(TreeNode n, int min) {
    System.out.println("N is now " + n.data);
    int currentMin = min;
    if (n.left != null && n.right != null) {
        final int left = min(n.left);
        final int right = min(n.right);

        if (left < right) {
            currentMin = left;
        } else {
            currentMin = right;
        }
    } else if (n.left != null) {
        currentMin = min(n.left);
    } else if (n.right != null) {
        currentMin = min(n.right);
    }
    if (currentMin < min) {
        return currentMin;
    } else {
        return min;
    }
}

ВЫХОД:

N is now 110
N is now 15
N is now 4
N is now 12
N is now 19
N is now 3
min=3

Вам необходимо использовать алгоритм обхода дерева для проверки каждого узла дерева. Также вам нужно хранить текущий найденный минимум. Передайте этот минимум в рекурсивную функцию. Он называет «аккумулятор».