Application des fonctions récursives C++ dans les structures de données arborescentes ?

Les fonctions récursives ont les applications suivantes lors du traitement des structures de données arborescentes : Concept de base : les fonctions récursives s'appellent elles-mêmes pour décomposer les gros problèmes en petits problèmes. Parcours d'une arborescence : parcours de pré-commande : visite des nœuds enfants avant de visiter les nœuds. Parcours post-commande : après avoir visité les nœuds, visitez les nœuds enfants. Cas pratique : Parcours de précommande d'un arbre binaire et valeurs des nœuds de sortie dans l'arbre binaire.

Application des fonctions récursives C++ dans les structures de données arborescentes

Les fonctions récursives sont très utiles lors du traitement des structures de données arborescentes. Une structure arborescente est une structure de données non linéaire dans laquelle chaque nœud peut avoir plusieurs nœuds enfants. En raison de la nature des structures arborescentes, les fonctions récursives peuvent facilement parcourir et manipuler ces structures.

Concept de base

Une fonction récursive est une fonction qui s'appelle elle-même. Cela permet à la fonction de décomposer un problème et de le transformer en sous-problèmes plus petits. Le processus se poursuit jusqu'à ce qu'un scénario de base soit atteint, puis les appels récursifs commencent à revenir.

Traverser des structures arborescentes

Les fonctions récursives peuvent être utilisées pour parcourir des structures arborescentes. Ceci peut être réalisé de deux manières principales :

• Parcours de précommande : Avant de visiter un nœud, ses enfants sont d'abord visités.
• Parcours post-commande : Après avoir visité un nœud, visitez ses nœuds enfants.

Cas pratique : Parcours précommandé d'un arbre binaire

Supposons que nous ayons un arbre binaire dans lequel chaque nœud contient un entier. Le code C++ suivant montre comment utiliser une fonction récursive pour le parcours de précommande :

struct Node {
    int data;
    Node* left;
    Node* right;
};

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    
    // 访问当前节点
    cout << root->data << " ";
    
    // 递归遍历左子树
    preorderTraversal(root->left);
    
    // 递归遍历右子树
    preorderTraversal(root->right);
}

int main() {
    // 创建二叉树结构：
    //    1
    //   / \
    //  2   3
    // / \
    //4   5
    Node root = {1, nullptr, nullptr};
    Node left1 = {2, nullptr, nullptr};
    Node right1 = {3, nullptr, nullptr};
    Node left2 = {4, nullptr, nullptr};
    Node right2 = {5, nullptr, nullptr};

    root.left = &left1;
    root.right = &right1;
    left1.left = &left2;
    left1.right = &right2;

    // 前序遍历二叉树
    preorderTraversal(&root);
    
    return 0;
}

Sortie :

1 2 4 5 3

Conclusion

Les fonctions récursives sont des outils puissants pour travailler avec des structures de données arborescentes. Ils permettent plusieurs appels à la même fonction, permettant un parcours et une manipulation pratiques et efficaces.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!