Предварительный порядок на двоичном дереве поиска

Question

Для двоичного дерева поиска: 7 - корень 1, являющийся левым дочерним элементом, а 10 - правильным.

         7 
             1 10 

Я попытался отладить эту функцию, чтобы увидеть, как она работает, и я не могу понять одну вещь. После того, как функция проверит и увидит, что левый дочерний и правый дочерние элементы 1 равны нулю, он переходит к узлу 10, а затем проверяет, имеет ли правильный ребенок значение null. Может кто-то объяснить рекурсивный шаблон и почему метод не выходит после первоначальной проверки узла 1.

private void preOrderTraversal(Node node) 
{  
    if(node == null) return; 
    System.out.println(node.data); 
    preOrderTraversal(node.leftChild); 
    preOrderTraversal(node.rightChild); 
} 

Answer 1

Метод preOrderTraversal (вызываются с Node = 1 в качестве аргумента, то есть с левым ребенком) действительно существует, но то управляющий поток возвращается к методу, который вызвал его, и это снова preOrderTraversal (называемый с Node = 7, корень в качестве аргумента). Так что все в порядке.

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

private void preOrderTraversal(Node node) 
{ 
    System.out.println("Now in preOrderTraversal with " + 
         (node==null ? "null." : node.data + ".")); 
    if(node == null) { 
     System.out.println("Done. Exit 1 taken."); 
     return; 
    } 
    System.out.println(node.data); 
    preOrderTraversal(node.leftChild); 
    preOrderTraversal(node.rightChild); 
    System.out.println("Done. Exit 2 taken."); 
} 

Answer 2

Добро пожаловать в мир рекурсии, поэтому давайте начнем с очень простой пример Calculating Factorial

Теперь, как вы видите стек вызовов методов был создан, пункт преломлении эта рекурсия factorial(0) whose result is 1, которая является первым значением, которое мы получаем

Теперь в этот момент программа не выйдет, вместо этого пятый вызов верните результат (i.e. 0) в четвертый вызов и т. Д., Чтобы вы могли получить окончательный результат. И как только любой метод возвращает результат он получил удален из стека рекурсивных вызовов

Теперь Приходя к вашему примеру обходе дерева

System.out.println(node.data); // prints 7 for first time 
preOrderTraversal(node.leftChild); // Now the function is called with 7->left 
preOrderTraversal(node.rightChild);// here is is called with 7->right 

Так создается таким же образом, стек рекурсивного вызова и тому Программа вместо выхода из 1 вернется к методу, который называет его (т.е. 7-> слева) и сейчас (7-> справа) будет выполняться

---

Теперь Рекурсия в неспециалиста тер мс

Кто-то в кинотеатре спрашивает вас, что ряд вы сидите. Вы не хотите рассчитывать, так что вы спросите человека, перед вами, что ряд они сидят в, зная, что вы ответите на один ответ, превышающий . Перед лицом спрашивает лицо перед . Это будет продолжаться до тех пор, пока слово не достигнет первого ряда, и легко ответить: «Я в строке 1!» Оттуда правильное сообщение (увеличивается на один каждый ряд строк) в конце концов вернется к задающемуся .