递归在 C++ 数据结构中的妙用：栈和树的实现-C++-PHP中文网

递归在 C++ 数据结构中的妙用：栈和树的实现

WBOY

发布： 2024-05-04 13:54:01

原创

1304人浏览过

递归在 c++++ 数据结构中的应用：栈：通过后进先出 (lifo) 结构递归实现栈。树：通过分层结构递归实现树，支持插入和深度计算等操作。递归为处理嵌套结构提供了简洁高效的解决方案，使数据结构的实现更加直观和易于维护。

递归在 C++ 数据结构中的妙用：栈和树的实现

递归在 C++ 数据结构中的妙用：栈和树的实现

递归是一种强大的编程技术，它允许函数调用自身来解决问题。在数据结构的实现中，递归非常有用，特别是对于处理树形结构和线形结构。

栈的递归实现

立即学习“C++免费学习笔记（深入）”；

栈是一种后进先出 (LIFO) 数据结构。我们可以使用递归实现栈，如下所示：

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

登录后复制

实战案例：逆序打印链表

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

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

登录后复制

树的递归实现

树是一种分层数据结构。我们可以使用递归来实现树，如下所示：

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

登录后复制

实战案例：计算二叉树的深度

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

登录后复制

通过递归，我们可以简洁高效地实现栈和树等关键数据结构。递归为处理复杂嵌套结构提供了强大的工具，使数据结构的实现变得更加直观和易于维护。

以上就是递归在 C++ 数据结构中的妙用：栈和树的实现的详细内容，更多请关注php中文网其它相关文章！