4(补上虚结点后的先序序列输入创建二叉链表) 二叉树的层次遍历 分数 10 全屏浏览 切换布局 作者 王宇 单位 集美大学诚毅学院 以字符串的形式定义一棵二叉树的先序序列，若字符是‘#’, 表示该二叉树是空树，否则该字符是相应结点的数据元素。读入相应先序序列，建立二叉树，然后按层次遍历该二叉树并输出结点数据。 输入格式: 字符串形式的先序序列（即结点的数据类型为单个字符） 输出格式: 按层次遍历二叉树的结果 输入样例1: 在这里给出一组输入。例如： abd###c#e## 输出样例1: 在这里给出相应的输出。例如： abcde 输入样例2: 在这里给出一组输入。例如： # 输出样例2: 在这里给出相应的输出。例如： 空树

### 如何通过先序序列创建二叉链表并进行层次遍历 #### 创建二叉链表 为了基于字符串形式的先序序列（`'#'` 表示空树）构建二叉链表，可以采用递归方法来解析该序列。以下是具体实现： ```cpp #include <iostream> #include <queue> using namespace std; typedef struct TreeNode { char data; TreeNode *left, *right; } Node; // 构建二叉树节点函数 TreeNode* buildTree(string preOrder, int& index) { if (index >= preOrder.length() || preOrder[index] == '#') { index++; return nullptr; } TreeNode* root = new TreeNode(); root->data = preOrder[index++]; root->left = buildTree(preOrder, index); root->right = buildTree(preOrder, index); return root; } ``` 在此部分代码中，定义了一个 `buildTree` 函数用于递归地根据先序序列创建二叉链表[^1]。 --- #### 层次遍历算法 对于二叉树的层次遍历，通常会借助队列的数据结构完成广度优先搜索（BFS）。下面是具体的实现方式： ```cpp void levelOrderTraversal(TreeNode* root) { if (!root) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* current = q.front(); q.pop(); if (current != nullptr) { cout << current->data << " "; if (current->left) q.push(current->left); if (current->right) q.push(current->right); } } } ``` 此段代码实现了二叉树的层次遍历功能，其中使用了标准库中的 `std::queue` 来管理待访问的节点[^2]。 --- #### 完整程序示例 将以上两个模块组合起来形成完整的解决方案如下所示： ```cpp #include <iostream> #include <queue> #include <string> using namespace std; typedef struct TreeNode { char data; TreeNode *left, *right; } Node; // 构建二叉树节点函数 TreeNode* buildTree(string preOrder, int& index) { if (index >= preOrder.length() || preOrder[index] == '#') { index++; return nullptr; } TreeNode* root = new TreeNode(); root->data = preOrder[index++]; root->left = buildTree(preOrder, index); root->right = buildTree(preOrder, index); return root; } // 层次遍历函数 void levelOrderTraversal(TreeNode* root) { if (!root) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* current = q.front(); q.pop(); if (current != nullptr) { cout << current->data << " "; if (current->left) q.push(current->left); if (current->right) q.push(current->right); } } } int main() { string preOrderStr; cin >> preOrderStr; int index = 0; TreeNode* root = buildTree(preOrderStr, index); cout << "Level Order Traversal: "; levelOrderTraversal(root); return 0; } ``` 这段完整代码展示了如何从先序序列创建一棵二叉树以及对其进行层次遍历的操作过程[^3]。 ---