Как алгоритм обхода предзаказов рекурсии возвращается к родительскому?

Question

public static void preorder(Node root) { 
    if(root == null) return; 

    root.printValue(); 
    preorder(root.getLeft()); 
    preorder(root.getRight()); 
} 

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

Answer 1

Там в неявной return в конце вашего метода void:

public static void preorder(Node root) { 
    if(root == null) return; 

    root.printValue(); 
    preorder(root.getLeft()); 
    preorder(root.getRight()); 
    return; 
} 

Вы всегда вернуться к методу, который призвал вас. Итак, если вызов метода parent вызывает другой вызов для дочернего элемента, тогда, когда вызов метода child возвращается, он возвращается к родительскому. Правильно?

Надеюсь, что имеет смысл. Как сказал Кон, вы должны просто запустить алгоритм на бумаге. Или, еще лучше, если вы знаете, как использовать отладчик, вы можете просто выполнить свой код в отладчике и посмотреть, как он работает.

Answer 2

Когда обход достиг узлового листа, его левые и правые дети будут NULL. И preorder (root.getLeft()) пройдет NULL и вернется. Точно так же право также вернет NULL. Затем стек появляется и возвращается к родительскому.

Я думаю, было бы лучше, если бы вы могли высушить это с помощью стека, тогда вы сможете лучше понять его.