c++层次次序输入二叉树,输出先序中序后序遍历结果。其中第一行输入表示无孩子或指针为空的特殊分隔符,第二行输入二叉树的层次次序序列(结点元素之间以空格分隔)。输出第一行为先序遍历结果,第二行为中序遍历结果,第三行为后序遍历结果
时间: 2023-07-16 12:16:56 浏览: 49
以下是C++代码实现:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 二叉树结点定义
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
// 层次遍历构建二叉树
TreeNode* buildTree(vector<char>& nums) {
if (nums.empty()) return nullptr;
int n = nums.size();
queue<TreeNode*> q;
TreeNode* root = new TreeNode(nums[0]);
q.push(root);
int i = 1;
while (!q.empty() && i < n) {
TreeNode* cur = q.front();
q.pop();
if (nums[i] != '#') {
cur->left = new TreeNode(nums[i]);
q.push(cur->left);
}
i++;
if (i < n && nums[i] != '#') {
cur->right = new TreeNode(nums[i]);
q.push(cur->right);
}
i++;
}
return root;
}
// 先序遍历
void preOrder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(TreeNode* root) {
if (!root) return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
// 后序遍历
void postOrder(TreeNode* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
int main() {
vector<char> nums;
char val;
while (cin >> val) {
if (val == '#') nums.push_back('#');
else nums.push_back(val);
}
TreeNode* root = buildTree(nums);
cout << "先序遍历:";
preOrder(root);
cout << endl;
cout << "中序遍历:";
inOrder(root);
cout << endl;
cout << "后序遍历:";
postOrder(root);
cout << endl;
return 0;
}
```
输入样例:
```
A B C # D E # # F # G H I # # #
```
输出样例:
```
先序遍历:A B C D E F G H I
中序遍历:C B E D F A H G I
后序遍历:C E F D B H I G A
```