C++二叉树的层序遍历 |21xrx.com

C++二叉树的层序遍历

2023-07-07 18:14:46 深夜i 23 0

C++ 二叉树层序遍历

二叉树是计算机科学中非常重要的数据结构之一。它是由若干个节点组成的树形结构，每个节点最多只有两个子节点。C++是一种常用的编程语言，也可以用来实现二叉树。在二叉树的遍历过程中，层序遍历是一种常用的方法。

层序遍历是指从根节点开始，按照从上到下、从左到右的顺序遍历每一层的节点。层序遍历可以用队列来实现，具体过程如下：

1. 将根节点入队。

2. 当队列不为空时，取出队列的第一个节点，并处理这个节点。

3. 将该节点的左子节点和右子节点入队。

4. 重复步骤2和步骤3，直到队列为空。

下面是C++实现二叉树的层序遍历的示例代码：

#include <iostream>
#include <queue>
using namespace std;
// 二叉树的数据结构
struct Node {
  int val;
  Node* left;
  Node* right;
  Node(int x) : val(x), left(NULL), right(NULL) {}
};
// 层序遍历函数
void levelOrder(Node* root) {
  if (!root) return;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    Node* cur = q.front();
    q.pop();
    cout << cur->val << " "; // 处理节点
    if (cur->left) q.push(cur->left); // 左子节点入队
    if (cur->right) q.push(cur->right); // 右子节点入队
  }
}
// 主函数
int main() {
  // 构建二叉树
  Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->right->left = new Node(6);
  root->right->right = new Node(7);
  // 层序遍历
  levelOrder(root);
  return 0;
}

在这个示例代码中，我们首先构建了一棵具有7个节点的二叉树，并对这个二叉树进行了层序遍历。层序遍历的结果是：1 2 3 4 5 6 7，表示从根节点开始，先访问了第一层的1，然后访问了第二层的2和3，最后访问了第三层的4、5、6和7。

总之，层序遍历是一种非常常用的二叉树遍历方法，它可以用队列来实现，可以帮助我们快速地遍历二叉树中的所有节点，并对这些节点进行处理。

上一篇: idea打包java可执行jar包

下一篇: Node.js实现文件和文件夹重命名

评论区

相似文章