La merveilleuse utilisation de la récursivité dans les structures de données C++ : implémentation de piles et d'arbres

Application de la récursion dans les structures de données C++ : Pile : La pile est implémentée de manière récursive via la structure dernier entré, premier sorti (LIFO). Arbre : L'arbre est implémenté de manière récursive via une structure hiérarchique, prenant en charge des opérations telles que l'insertion et le calcul de profondeur. La récursion fournit une solution concise et efficace pour traiter les structures imbriquées, rendant la mise en œuvre des structures de données plus intuitive et plus facile à maintenir.

La merveilleuse utilisation de la récursion dans les structures de données C++ : implémentation de piles et d'arbres

La récursion est une technique de programmation puissante qui permet aux fonctions de s'appeler pour résoudre des problèmes. La récursivité est très utile dans la mise en œuvre de structures de données, notamment pour le traitement des structures arborescentes et des structures linéaires.

Implémentation récursive de la pile

La pile est une structure de données dernier entré, premier sorti (LIFO). Nous pouvons utiliser la récursivité pour implémenter la pile, comme indiqué ci-dessous :

struct Node {
  int data;
  Node* next;
};

class Stack {
private:
  Node* head;

public:
  void push(int data) {
    head = new Node{data, head};
  }

  int pop() {
    if (head == nullptr) {
      throw exception("Stack is empty");
    }
    int data = head->data;
    head = head->next;
    return data;
  }

  bool empty() {
    return head == nullptr;
  }
};

Cas pratique : impression d'une liste chaînée dans l'ordre inverse

void printLinkedListInReverseOrder(Node* head) {
  if (head == nullptr) {
    return;
  }

  printLinkedListInReverseOrder(head->next);
  cout << head->data << " ";
}

Implémentation récursive de tree

Tree est une structure de données hiérarchique. Nous pouvons utiliser la récursivité pour implémenter des arbres, comme indiqué ci-dessous :

struct Node {
  int data;
  vector<Node*> children;
};

class Tree {
private:
  Node* root;

public:
  void insert(int data) {
    if (root == nullptr) {
      root = new Node{data, {}};
    } else {
      insertHelper(root, data);
    }
  }

private:
  void insertHelper(Node* node, int data) {
    for (auto& child : node->children) {
      if (child == nullptr) {
        child = new Node{data, {}};
        return;
      }
    }

    node->children.push_back(new Node{data, {}});
  }

  void printTree() {
    printTreeHelper(root);
  }

private:
  void printTreeHelper(Node* node) {
    cout << node->data << " ";
    for (auto& child : node->children) {
      printTreeHelper(child);
    }
  }
};

Cas pratique : Calculer la profondeur d'un arbre binaire

int calculateTreeDepth(Node* root) {
  if (root == nullptr) {
    return 0;
  }

  int maxDepth = 0;
  for (auto& child : root->children) {
    maxDepth = max(maxDepth, calculateTreeDepth(child));
  }

  return maxDepth + 1;
}

Grâce à la récursivité, nous pouvons implémenter des structures de données clés telles que des piles et des arbres de manière concise et efficace. La récursion fournit des outils puissants pour traiter des structures imbriquées complexes, rendant la mise en œuvre de structures de données plus intuitive et plus facile à maintenir.

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!