Понимание стека раскручивание в рекурсии (дерево обхода)

Question

Я пишу программу для обхода двоичного поиска tree.Here в мой код:

Main.java

public class Main { 

public static void main(String[] args) { 
BinaryTree binaryTree = new BinaryTree(); 
binaryTree.add(50); 
binaryTree.add(40); 
binaryTree.add(39); 
binaryTree.add(42); 
binaryTree.add(41); 
binaryTree.add(43); 
binaryTree.add(55); 
binaryTree.add(65); 
binaryTree.add(60); 
binaryTree.inOrderTraversal(binaryTree.root); 
} 
} 

Node.java

public class Node { 
int data; 
Node left; 
Node right; 
Node parent; 


public Node(int d) 
{ 
data = d; 
left = null; 
right = null; 
} 
} 

BinaryTree.java

public class BinaryTree { 
Node root = null; 
public void add(int d) 
{ 
Node newNode = new Node(d); 
if(root!=null) 
{ 


    Node futureParent = root; 
    while(true) 
    { 
    if(newNode.data < futureParent.data)  //going left 
    { 
     if(futureParent.left == null) 
     { 
      futureParent.left = newNode; 
      newNode.parent = futureParent; 
      break; 
     } 
     futureParent = futureParent.left; 

    } 
    else 
    { 
     if(futureParent.right == null) 
     { 
      futureParent.right = newNode; 
      newNode.parent = futureParent; 
      break; 
     } 
     futureParent = futureParent.right; 
    } 

    } 

} 
else 
{ 
    root = newNode; 
} 
} 
public void inOrderTraversal(Node node) 
{ 
if(node!=null) 
{ 
inOrderTraversal(node.left); 
System.out.println(node.data); 
inOrderTraversal(node.right); 
} 
} 
} 

Я понимаю процесс добавления отлично, но у меня проблемы с пониманием обхода. Теперь дерево я работаю, для лучшего ведения заключается в следующем:

Первое утверждение в функции визитов в inOrderTraversal() 50,40 затем 39 и, наконец, попадает нуль делает, если условие ложно, после чего 39 печатается и выполняется поиск подходящего ребенка. После этого первый оператор прекращает выполнение, и стек разматывается для 2-го и 3-го операторов (inOrderTraversal(node.right) и print(node.data)), что приводит к печати 40 и пересечению до 41, которая является той частью, которую я не понимаю, т.е. как компилятор перезапускает оператор 1 (inOrderTraversal(node.left)) после того, как он прекратил выполнение, как только в стеке будут свежие вещи.

Answer 1

Ваш код не работает так, как он есть, он будет итерировать навсегда над узлом 39. Метод inOrderTraversal() действительно отправится на левый узел, но будет циклически перебирать его навсегда из-за времени. Каждый кадр стека имеет свою собственную копию переменных. При вводе метода переменный узел получает копию ссылки на объект, переданную как аргумент.

Один из способов думать о рекурсии - это то, что похоже на использование цикла while, но вместо этого у вас есть if. Вот как метод должен выглядеть следующим образом:

public void inOrderTraversal(Node node) { 
    if (node != null) { 
     inOrderTraversal(node.left); 
     System.out.println(node.data); 
     inOrderTraversal(node.right); 
    } 
} 

При обходе дерева, вы хотите, чтобы напечатать первые меньшее значение, которое хранится в левом основном узле, так что вы используете inOrderTraversal(node.left); добраться, если. Когда вы приходите к нулевому узлу, это означает, что его родитель - самый левый узел, поэтому вы его печатаете. После этого вы перейдете к правильному узлу и повторите этот процесс. Это похоже на разделение дерева на более мелкие под деревья, пока вы больше не сможете их разделить и распечатать их значение.

Каждый раз, когда вы вызываете метод (рекурсивный или нет), выделяется новый стек стека (нажимается на стек), а после завершения метода стек удаляется (поп), освобождая пространство для сбора мусора. Эти кадры стеков являются лишь временным пространством, в котором живут локальные переменные. Переменные объекта объекта находятся в другом месте, называемом кучей, который имеет большую продолжительность жизни, чем стек.

JVM обрабатывает распределение этих пространств, и сборщик мусора освобождает их в зависимости от срока службы объектов/переменных. В зависимости от того, насколько они живут, существует несколько поколений (это то, что они называются). Все начинаются с эдинкого (молодого) поколения, и если сборщик мусора не освобождает пространство, так как они все еще живы, они перемещаются в поколение выживших, после чего, если они все еще не собраны, они переходят к последнему , поколение поколений. Чем дольше объекты живут, тем реже они проверяются GC. Это означает, что, хотя объекты в eden собраны довольно быстро, остальные поколения проверяются не так часто. Существует также другое пространство, называемое постоянным поколением (permgen), где константы жили (например, строковые литералы) и где хранятся классы.

Answer 2

Прежде всего, заявление while в inOrderTraversal неверно. Ни одно из операторов в цикле while не изменяет переменную node, так что если бы это было null, это всегда будет, и если бы это было не так, это никогда не будет. Измените его на if.

Имея это, способ взглянуть на рекурсию часто по индукции. Я утверждаю следующее предположение индукции:

Учитывая дерево T с корнем node, inOrderTraversal(node) печатает обход упорядоченных из T и возвращается.

Мы можем показать по индукции, что это действительно так. Простой случай: node == null. В этом случае inOrderTraversal ничего не печатает и возвращает напрямую, что соответствует гипотезе.

Теперь предположим, что мы пропускаем непустое дерево. По индукции inOrderTraversal(node.left) печатает левое поддерево и возвращает. Затем печатается node.data. Наконец, снова по индукции, inOrderTraversal(node.right) печатает правильное поддерево и возвращает. Обратите внимание, что до сих пор текущее дерево было напечатано в обходном порядке. Поскольку я изменил while на if, метод возвращается, тем самым удовлетворяя гипотезе индукции.

Ответит ли это на ваш вопрос?

Answer 3

Вы можете получить более четкое представление о рекурсии и стеке, подумав о классическом примере рекурсии, factorial.

int factorial(x) { 
    int result; 
    if(x==1) 
     result = 1; 
    else 
     result = x * factorial(x - 1); 
    return result; 
} 

(я использовал переменную result, чтобы сделать его легче отметить положение, ступая вручную через код)

Запуск через выполнение factorial(5) вручную, используя кусочки бумаги.

Начните с написания функции на одном листе бумаги, заменив «x» на 5. Затем прочитайте его, а когда вы перейдете к вызову функции, поместите метку карандаша в точку выполнения и получите новый лист бумаги для вашего нового вызова функции.

Каждый раз, когда вы делаете это, положите новый лист бумаги поверх предыдущего листа. Это, буквально, стопку бумаги, и она точно представляет компьютер стек. Каждый лист бумаги представляет собой столбец , и он записывает, где вы были в коде, и каковы значения локальных переменных, когда вы его создаете.

Важно понимать, что это не относится к рекурсивным вызовам функций. Таким образом, все вызовы функций создают запись стека.

Выполнение программы не позволяет просматривать стек. Доступен только верхний лист бумаги - последний, сначала (LIFO). Когда вы доберетесь до factorial(1), он снова не называет себя, и вы попадаете в return.Когда это произойдет, отбросьте верхний лист бумаги, напишите возвращаемое значение в новый верхний слой, затем продолжайте выполнять функцию на верхнем слое, начиная с точки, где вы помещаете метку карандаша.

Продолжайте так, и в итоге вы отбросьте последний лист. Это означает, что ваша программа закончена, и у вас есть конечный результат.

Кстати, если что-то не так с вашим кодом, такого нет, когда функция не называет себя, у вас закончится бумага (или ваш стек бумаги достигнет потолка) - то есть переполнение стека, после которого назван этот сайт. Стек становится больше, чем наложенный максимум, и среда выполнения отказывается снова вызвать функцию (в Java, путем исключения исключения). Вероятно, вы столкнетесь с этим в своей карьере программирования - обычными причинами являются плохо закодированное условие остановки или округление круговой структуры данных.

С реализацией выше factorial(0), вероятно, вызовет переполнение стека. Вы можете понять, почему?

Так работают все обычные компьютерные программы. Вы помещаете один элемент в стек (на C и Java, это main()). Каждый раз, когда выполняется вызов функции, стек растет, и каждый раз, когда функция завершается, стек сжимается. Стек растет и сжимается до тех пор, пока он не скроется до нуля, после чего программа будет выполнена.

Для таких программ, как ваш, с двумя рекурсивными вызовами в одной и той же функции, ничего не изменилось. Это хорошее упражнение, чтобы выполнить небольшой поиск двоичного дерева вручную с листами бумаги так же, как и с factorial(), чтобы увидеть, как он работает.

Также рекомендуется приостановить Java-код в отладчике, чтобы посмотреть состояние текущего стека - или если вы не можете этого сделать (научитесь использовать отладчик в ближайшее время!) Введите Thread.dumpStack() где-нибудь в вашем коде чтобы узнать, что он выводит.