c语言和c++实现层序遍历_c++ 层序遍历

层序遍历是一种二叉树的遍历方式，也称为广度优先遍历，它的遍历顺序是：从上到下，从左到右，一层一层地遍历整棵树。在 C 语言中，我们可以使用队列来实现层序遍历。

具体实现步骤如下：

1. 将根节点入队列。
2. 当队列不为空时，重复以下步骤：
   • 从队头弹出一个节点，访问该节点。
   • 如果该节点有左子树，则将左子树入队列。
   • 如果该节点有右子树，则将右子树入队列。

1.下面是使用队列实现层序遍历的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int val;
    struct Node* left;
    struct Node* right;
};
 
struct Node* createNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}
 
void levelOrderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    struct Node* queue[1000];
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        struct Node* node = queue[front++];
        printf("%d ", node->val);
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
}
 
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    levelOrderTraversal(root);
    return 0;
}

在上面的代码中，我们首先定义了一个结构体 Node 来表示二叉树的节点，以及一个函数 createNode 来创建新的节点。然后，我们实现了 levelOrderTraversal 函数来实现层序遍历。在函数中，我们首先定义了一个队列和两个指针 front 和 rear，用于记录队头和队尾的位置。然后，将根节点入队列，进入循环。在循环中，我们首先从队头弹出一个节点，访问该节点，然后依次将其左子节点和右子节点入队列。循环结束后，我们完成了整棵树的层序遍历。

struct Node* queue[1000];
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        struct Node* node = queue[front++];
        printf("%d ", node->val);
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
}

这段代码使用了一个数组 queue 来辅助进行二叉树的层序遍历，是一种不使用 C++ 标准库的实现方式。我们首先定义了一个 queue 数组，其大小为 1000，存储的元素是指向 Node 类型的指针。然后，定义了两个整数变量 front 和 rear 分别表示队首和队尾的下标。

接下来，我们将根节点指针 root 存储在 queue 数组的队尾，并将 rear 的值加一，表示入队操作完成。然后，进入一个循环，只要队列不为空，就一直执行循环。在循环内部，我们首先从队列中取出队首元素，即二叉树中当前层的最左边的节点，将其存储在名为 node 的指针变量中。然后，我们输出 node 的值，即该节点的 val 属性。

接下来，我们判断该节点的左右子节点是否存在，如果存在，就将它们的指针存储在 queue 数组的队尾，并将 rear 的值加一，表示入队操作完成。这样，队列中存储的元素就是下一层的所有节点。当当前层的所有节点都被取出并输出后，循环继续执行，取出队列中的下一个节点，重复上述步骤，直到遍历完整个二叉树。

这个算法的时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点数。因为我们需要遍历每个节点一次，而每个节点最多进队一次出队一次，所以队列的操作次数也是 $O(n)$ 级别的。

2.下面是使用队列实现层序遍历的 C++ 代码：

#include <iostream>
#include <queue>
using namespace std;
 
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
 
void levelOrderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left != nullptr) {
            q.push(node->left);
        }
        if (node->right != nullptr) {
            q.push(node->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);
    levelOrderTraversal(root);
    return 0;
}

在上面的代码中，我们首先定义了一个结构体 Node 来表示二叉树的节点，并且在结构体中使用了构造函数来方便创建新的节点。然后，我们实现了 levelOrderTraversal 函数来实现层序遍历。在函数中，我们首先定义了一个队列 q，将根节点入队列，进入循环。在循环中，我们首先从队头弹出一个节点，访问该节点，然后依次将其左子节点和右子节点入队列。循环结束后，我们完成了整棵树的层序遍历。

queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left != nullptr) {
            q.push(node->left);
        }
        if (node->right != nullptr) {
            q.push(node->right);

这段代码使用了 C++ 的标准库中的 queue 来辅助进行二叉树的层序遍历。我们首先定义了一个名为 q 的队列，队列中存储的元素是指向 Node 类型的指针。然后，将根节点指针 root 压入队列中，表示从根节点开始遍历。

接下来，我们进入一个循环，只要队列不为空，就一直执行循环。在循环内部，我们首先从队列中取出队首元素，即二叉树中当前层的最左边的节点，将其存储在名为 node 的指针变量中。然后，我们输出 node 的值，即该节点的 val 属性。

接下来，我们判断该节点的左右子节点是否存在，如果存在，就将它们的指针压入队列中。这样，队列中存储的元素就是下一层的所有节点。当当前层的所有节点都被取出并输出后，循环继续执行，取出队列中的下一个节点，重复上述步骤，直到遍历完整个二叉树。

这个算法的时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点数。因为我们需要遍历每个节点一次，而每个节点最多进队一次出队一次，所以队列的操作次数也是 $O(n)$ 级别的。空间复杂度为 $O(w)$，其中 $w$ 是二叉树的最大宽度，也就是某一层节点数的最大值。因为我们需要使用队列来存储每一层的节点，所以空间复杂度取决于二叉树的最大宽度。