假设二叉树采用二叉链存储,每个结点值为单个字符。编写一个实验程序,由二叉树的中序序列和后序序列构造二叉树,实现求层次遍历算法,用相关
时间: 2023-07-16 12:13:38 浏览: 49
数据结构存储并输出结果。
实现过程如下:
1. 定义二叉树的结构体
```C++
struct TreeNode{
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char v):val(v),left(nullptr),right(nullptr){}
};
```
2. 构造二叉树的函数
```C++
TreeNode* buildTree(vector<char>& inorder, vector<char>& postorder, int inStart, int inEnd, int postStart, int postEnd){
if(inStart > inEnd || postStart > postEnd){
return nullptr;
}
char rootValue = postorder[postEnd];
int rootIndex = -1;
for(int i = inStart; i <= inEnd; i++){
if(inorder[i] == rootValue){
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode* root = new TreeNode(rootValue);
root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
return root;
}
TreeNode* buildTree(vector<char>& inorder, vector<char>& postorder){
return buildTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
```
3. 层次遍历的函数
```C++
vector<vector<char>> levelTraversal(TreeNode* root) {
vector<vector<char>> res;
if (!root) {
return res;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<char> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
res.push_back(level);
}
return res;
}
```
4. 主函数
```C++
int main() {
vector<char> inorder = {'D', 'B', 'E', 'A', 'F', 'C'};
vector<char> postorder = {'D', 'E', 'B', 'F', 'C', 'A'};
TreeNode* root = buildTree(inorder, postorder);
vector<vector<char>> res = levelTraversal(root);
for (auto level : res) {
for (auto val : level) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
```
完整代码如下: