Понимание обхода дерева BFS по уровням в образце

Я учусь проходить дерево по уровням. Метод, который я использую, должен брать уровень номера дерева и печатать узлы на текущем уровне. Я смотрел это руководство - "Печатать узлы на заданном уровне", но до сих пор не могу понять, как рекурсия работает в этом конкретном примере. Так что, пожалуйста, помогите мне понять.

// Java program for Inserting a node
class GFG1 {

    static class node {
        int key;
        node left, right;
    }

    static node newNode(int item)
    {
        node temp = new node();
        temp.key = item;
        temp.left = temp.right = null;
        return temp;
    }

    // Function to insert a new node
    static node insert(node node, int key)
    {
        // If the tree is empty, return a new node
        if (node == null)
            return newNode(key);

        // Otherwise, recur down the tree
        if (key < node.key) {
            node.left = insert(node.left, key);
        }
        else if (key > node.key) {
            node.right = insert(node.right, key);
        }
        return node;
    }

    static void printGivenLevel(node root, int level)
    {
        if (root == null)
            return;
        if (level == 1) {
            System.out.print(" " + root.key);
        }
        else if (level > 1) {
            printGivenLevel(root.left, level - 1);
            printGivenLevel(root.right, level - 1);
        }
    }

    public static void main(String[] args)
    {
        node root = null;
        root = insert(root, 50);insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);insert(root, 80);
        printGivenLevel(root,2);

    }
}

Метод обхода по уровням printGivenLevel:
Так почему же требуется писать level-1 в printGivenLevel(root.left, level - 1) и не работает, например, с «уровнем +1»? Как мы приходим к базовому состоянию, например на 3-й или 2-й уровень?

Дерево похоже

   50
  30 70
20 40 60 80 
level означает, сколько уровней осталось от того, который мы хотим напечатать. if (level == 1) означает, что мы находимся на том уровне, который хотим напечатать.
MrSmith42 24.01.2023 14:12
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
1
50
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

level здесь неоднозначный термин, в printGivenLevel он начинается с верхнего «уровня», который технически является level 1, и мы возвращаемся вниз, пока не достигнем желаемого «уровня».

    Actual level       "level" inside printGivenLevel(root, level)    
        1          50              3
        2        30   70           2
        3      20 40 60 80         1

Давайте посмотрим, как выполняется printGivenLevel(root, 2), переименовав printGivenLevel в print:

 1. print(root, 2) -> print(root.left(30), 1) and print(root.right(70), 1)
 2. print(root(30), 1) -> we are at "level 1", print the value 30.
 3. print(root(70), 1) -> we are at "level 1", print the value 70.

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

Так почему же требуется писать level-1 в printGivenLevel(root.left, level - 1) и не работает, например, с level +1? Как мы приходим к базовому состоянию, например на 3-й или 2-й уровень?

Если level всегда увеличивается, он будет продолжать увеличиваться и не достигнет уровня 1, значение не будет напечатано, и это приведет к переполнению стека.

Другие вопросы по теме

Структура данных/алгоритм для поиска текущей позиции идентификатора в массиве после множества вставок
Я написал код для линейного поиска на питоне (рекурсивный). Может кто-нибудь сказать мне, почему это не работает? ОШИБКА – превышена максимальная глубина рекурсии
Как проще всего изменить элемент в списке Kotlin?
Упрощенный способ представления древовидных данных?
Алгоритм постоянного рабочего пространства для триангуляции набора точек
JavaScript: изменять серию каждый N-й раз (всегда начинать с 1)?
Приоритетная очередь с использованием сортировки вставками - лучший сценарий O (n)?
Учитывая строку s, найти длину самой длинной подстроки без повторяющихся символов? (Мне нужно найти ошибку в коде, который я написал)
Найдите триплеты из массива, такие что i<j<k, A[i]<A[j]<A[k] и B[i]+B[j]+B[k] максимальны
Выведите количество возможных непустых последовательностей букв