The wonderful use of recursion in C++ data structures: implementation of stacks and trees

Application of recursion in C data structures: Stack: Stack is implemented recursively through the last-in-first-out (LIFO) structure. Tree: Tree is implemented recursively through a hierarchical structure, supporting operations such as insertion and depth calculation. Recursion provides a concise and efficient solution for processing nested structures, making the implementation of data structures more intuitive and easier to maintain.

The wonderful use of recursion in C data structures: the implementation of stacks and trees

Recursion is a powerful programming technology. It allows functions to call themselves to solve problems. Recursion is very useful in the implementation of data structures, especially for processing tree structures and linear structures.

Recursive implementation of the stack

The stack is a last-in-first-out (LIFO) data structure. We can use recursion to implement the stack, as shown below:

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

Practical case: printing linked list in reverse order

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

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

Recursive implementation of tree

Tree is a hierarchical data structure. We can use recursion to implement the tree, as shown below:

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

Practical case: Calculate the depth of the binary tree

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

Through recursion, we can implement the stack and sum simply and efficiently Key data structures such as trees. Recursion provides powerful tools for processing complex nested structures, making the implementation of data structures more intuitive and easier to maintain.

The above is the detailed content of The wonderful use of recursion in C++ data structures: implementation of stacks and trees. For more information, please follow other related articles on the PHP Chinese website!