遍写程序,实现对二叉树的层次遍历。 按先序序列建立二叉树的二叉链表(用#补齐空结点),然后借助队列对二叉树进行层次遍历,并输出遍历结果。 提示: 1. 循环顺序队列和链队列均可,涉及到的操作:初始化队列、

C++语言实现)

实现二叉树的层次遍历，需要用到队列这种数据结构。代码如下：

#include<iostream>
#include<queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 先序遍历建立二叉树
TreeNode* buildTree() {
    int val;
    cin >> val;
    if (val == -1) return NULL;
    TreeNode* root = new TreeNode(val);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

// 层次遍历二叉树
void levelTraversal(TreeNode* root) {
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

int main() {
    TreeNode* root = buildTree();
    levelTraversal(root);
    return 0;
}