J'ai de la difficulté à comprendre les fonctions récursives de la traversée de l'arbre

Question

J'ai de la difficulté à comprendre les fonctions récursives impliquées dans la traversée de l'arbre de précommande, d'inorder et postorder. J'ai une certaine connaissance de la récursivité (mais il est vrai que ce n'est pas mon fort). Tous semblent s'appeler deux fois d'abord en faisant un appel avec l'enfant gauche de la racine et ensuite avec l'enfant droit. Mais comment est-ce possible? L'appel de la fonction preOrder avec l'enfant de gauche ne retournerait-il pas le flux de contrôle en haut, et l'appel suivant ne serait jamais exécuté?

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

Answer 1

Ne serait-appel à la fonction de pré-commande avec l'enfant gauche retourner le flux de contrôle de retour vers le haut, et le prochain appel ne sera jamais exécuté?

Bien sûr que non. L'appel récursif fonctionne comme n'importe quel autre appel de fonction: après la fin de la fonction, le contrôle revient au lieu d'appel. 'L'endroit' signifie non seulement le point dans le code mais aussi le point sur la pile d'appels, ce qui signifie que le même ensemble de variables est à nouveau disponible. Tout comme après le retour de toute autre fonction.

Par exemple, si vous avez un arbre

 A 
    /\ 
     X Y 

et que vous appelez preorder sur le nœud A, il imprime d'abord les A contenu, puis appelle preorder sur X et sur le retour, il est de retour dans preorder(A), donc il continue à appeler preorder sur Y.

Answer 2

Preorder: Traiter le noeud, passer à l'enfant gauche, passer à l'enfant droit

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 
} 

Inorder: déplacement vers la gauche, le processus du noeud, déplacer vers la droite

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: déplacer vers le noeud gauche, passer à le noeud droit, le nœud processus

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); 
    } 
}