Непонимание понимания рекурсивных функций обхода дерева

Question

У меня возникли проблемы с пониманием рекурсивных функций, связанных с обходом предзаказов, по порядку и по порядку. У меня есть некоторые сведения о рекурсии (но, по общему признанию, это не мой сильный костюм). Кажется, что все называют себя дважды, сначала делая звонок с левым ребенком корня, а затем с правильным ребенком. Но как это возможно? Разве вызов функции preOrder с левым дочерним элементом не вернет поток управления в начало, а следующий вызов никогда не будет выполнен?

void preOrder (Node* root) 
{ 
    if (root == NULL) return; 
    cout<<root->val<<", "; 
    preOrder(root->left); 
    preOrder(root->right); 
} 

Answer 1

Не будет ли вызов функции PREORDER с левым ребенком вернуть поток управления обратно к вершине, и следующий вызов не будет выполнен?

Конечно нет. Рекурсивный вызов работает так же, как и любой другой вызов функции: после завершения функции элемент управления возвращается в место вызова. «Место» означает не только точку в коде, но и точку в стеке вызовов, что означает, что снова доступен тот же набор переменных. Так же, как после возвращения из любой другой функции.

Например, если у вас есть дерево

 A 
    /\ 
     X Y 

и вы называете preorder на A узле, то он первым печатает A содержимое, а затем вызывает preorder на X и по возвращении он вернулся в preorder(A), так он продолжает звонить по телефону preorder по телефону Y.

Answer 2

Preorder: Обработать узел, переходят к левому ребенку, перейти к правому ребенку

void preorder(Node *root) 
{ 
    if (root == NULL) //<- Check if the currently passed node is empty 
     return; //<- if it is, return from the function back down the stack 

    cout << root->val << ", "; //<- if it wasn't empty, print its value 

    if (root->left != NULL) //<- check if the node to the left is empty 
     preorder(root->left); //<- if not recurse to the left child 

    if (root->right != NULL) //<- check if the node to the right is empty 
     preorder(root->right); //<- if not recurse to the right child 
} 

Симметричного: шаг влево, обрабатывает узел, перемещаются вправо

void inorder(Node *root) 
{ 
    if (root == NULL) 
     return; 

    if (root->left != NULL) //<- check if the node to the left is empty 
      inorder(root->left); //<- if not recurse to the left child 

    cout << root->val << ", "; 

    if (root->right != NULL) //<- check if the node to the right is empty 
      inorder(root->right); //<- if not recurse to the right child 
} 

Postorder: Переход к левому узлу, перейти к правый узел, процесс узел

void postorder(Node *root) 
{ 
    if (root == NULL) 
     return; 

    if (root->left != NULL) //<- check if the node to the left is empty 
      postorder(root->left); //<- if not recurse to the left child 

    if (root->right != NULL) //<- check if the node to the right is empty 
      postorder(root->right); //<- if not recurse to the right child 

    cout << root->val << ", " 
} 

Answer 3

void preorder(node *p) { 
    if(p) { 
    cout << p->val <<"\n"; 
    preorder(p->left); 
    preorder(p->right); 
    } 
}