Я учусь проходить дерево по уровням. Метод, который я использую, должен брать уровень номера дерева и печатать узлы на текущем уровне. Я смотрел это руководство - "Печатать узлы на заданном уровне", но до сих пор не могу понять, как рекурсия работает в этом конкретном примере. Так что, пожалуйста, помогите мне понять.
// 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
здесь неоднозначный термин, в 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, значение не будет напечатано, и это приведет к переполнению стека.
level
означает, сколько уровней осталось от того, который мы хотим напечатать.if (level == 1)
означает, что мы находимся на том уровне, который хотим напечатать.