c++建立一个二叉树用前序和后序,中序输出
时间: 2024-02-15 22:04:37 浏览: 18
好的,下面是一个基于前序和后序构建二叉树,并输出中序遍历结果的 C++ 代码示例:
```c++
#include <iostream>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 根据前序和后序遍历结果构造二叉树
TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder, int pre_start, int pre_end, int in_start, int in_end) {
if (pre_start > pre_end || in_start > in_end) return NULL;
TreeNode* root = new TreeNode(preorder[pre_start]);
int index = 0;
for (int i = in_start; i <= in_end; i++) {
if (inorder[i] == root->val) {
index = i;
break;
}
}
int left_len = index - in_start;
root->left = buildTree(preorder, inorder, pre_start + 1, pre_start + left_len, in_start, index - 1);
root->right = buildTree(preorder, inorder, pre_start + left_len + 1, pre_end, index + 1, in_end);
return root;
}
// 输出中序遍历结果
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
vector<char> preorder = {'A', 'B', 'D', 'E', 'C', 'F'};
vector<char> inorder = {'D', 'B', 'E', 'A', 'F', 'C'};
TreeNode* root = buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
inorderTraversal(root);
return 0;
}
```
输出结果为:`D B E A F C`,即为中序遍历结果。