печать двоичного дерева поиска рекурсивно

Question

У меня есть код для печати содержимого двоичного дерева поиска по порядку (по возрастанию) с использованием рекурсии. Я понимаю, что вспомогательный метод вызывает рекурсивный метод с корнем в качестве значения начального узла. Но я не понимаю, как рекурсивный код работает концептуально. Может ли кто-нибудь объяснить?

//ascend method that prints values in the tree in ascending order 
//recursive method below 
public void printAscending() { 
    printAscending(root); 
} 
private void printAscending(Node node) { 
    if(node != null) { 
     printAscending(node.left); 
     System.out.println(node.data); 
     printAscending(node.right); 
    } 
} 

Answer 1

Рассмотрим следующий (тривиальное) дерево:

1 

Вы бы вызов функции на одной (корень), и это очевидно, чтобы увидеть, что результат 1 ,

Теперь рассмотрим следующее (немного больше) дерево:

2 
1 

Корень теперь 2 и выход (вручную прослежена вручную) дает 1 2. (пробелы добавлены для ясности)

Похожие ручной трассировка на следующих дает нам 1 2 3:

2 
1 3 

Так теперь мы можем видеть, что для малых testcases, кажется, работает хорошо.

Давайте попробуем проверить его на более крупные тестовые корпуса.

Для любого нулевого узла (т. Е. Если мы находимся в несуществующем дереве/поддереве), мы просто выходим.

Для любого непустого узла сначала вызывается линия printAscending(node.left). Эта строка ДОЛЖНА завершить выполнение до того, как что-нибудь еще запустится. Это вызывает функцию printAscending(), используя node.left как параметр, который эквивалентен простому левому поддереву текущего узла, завершая работу там, а затем продолжая код. Мы можем продолжать движение вниз, пока не достигнем нулевого узла. В этот момент он движется назад вверх, возобновляя оттуда, где он остановился. Он запускает System.out.println(node.data), который дает выход одного узла, а затем запускает printAscending(node.right). Это заставляет его вводить правое поддерево текущего узла. Обратите внимание, что в этом поддереве он запускает полный код (т. Е. Запускает левую, центральную, а затем правую части). Как только это выполняется через правильное поддерево, оно возвращается из поддерева и текущего узла. Это заставляет узел чуть выше (родительский) перейти к следующей части кода.

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

Answer 2

// public entry point, reuses the recursive function 
public void printAscending() { 
    printAscending(root); 
} 

// print this node and all of its descendants 
private void printAscending(Node node) { 
    // is there actually a node here 
    // or was this called from a node with no children 
    if(node != null) { 
     // print everything that's earlier than this node 
     printAscending(node.left); 

     // print this node's value 
     System.out.println(node.data); 

     // print everything that's afterthan this node 
     printAscending(node.right); 
    } 
}