Как работают рекурсивные вызовы и печать в почтовом порядке (двоичное дерево)?

Question

Допустим, у нас есть двоичное дерево с этим кодом пост-заказа (это не код на любом конкретном c языке, это больше похоже на псевдокод)

postorder(node)
{
if(node==null)
return

postorder(left)
postorder(right)
print(node)
}

Я понимаю, что при первом вызове рекурсия будет продолжаться до тех пор, пока не будет достигнут левый лист, что тогда? Как он возвращает и печатает другой элемент? не звонит postorder(right) заставляет нас звонить postorder(left) так же, как и до него?

Answer 1

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

Если вы видите код, для этой цели используется оператор return . Как только узел становится нулевым, мы просто возвращаемся к вызывающей стороне в стеке функций

Разве вызов postorder (справа) не заставляет нас вызывать postorder (left) так же, как он предшествует ему?

Идея здесь очень проста. Возьмите root. если root ноль -> возврат. В противном случае execute postorder(left) Следующая строка, подлежащая выполнению, отслеживается в стеке функций. Этот процесс продолжается до тех пор, пока стек не опустеет. Наконец узел печатается.