帮我写出c++代码:给出一个二叉树的前序遍历和中序遍历求这个二叉树的后序遍历
时间: 2023-07-24 19:57:38 浏览: 138
给出先序遍历和中序遍历,求二叉树后序遍历
5星 · 资源好评率100%
当然可以!下面是一个用C++编写的求解二叉树后序遍历的代码:
```cpp
#include<iostream>
using namespace std;
struct Node {
char data;
Node* left;
Node* right;
};
Node* buildTree(string preorder, string inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
Node* root = new Node;
root->data = preorder[preStart];
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root->data) {
inIndex = i;
break;
}
}
root->left = buildTree(preorder, inorder, preStart + 1, preStart + (inIndex - inStart), inStart, inIndex - 1);
root->right = buildTree(preorder, inorder, preStart + (inIndex - inStart) + 1, preEnd, inIndex + 1, inEnd);
return root;
}
void postorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
int main() {
string preorder = "ABDECFG";
string inorder = "DBEAFCG";
Node* root = buildTree(preorder, inorder, 0, preorder.length() - 1, 0, inorder.length() - 1);
cout << "后序遍历结果为:";
postorderTraversal(root);
return 0;
}
```
这段代码实现了根据给定的前序遍历和中序遍历构建二叉树,并输出后序遍历的结果。在`main`函数中,我们给出了一个示例的前序遍历和中序遍历序列,你可以根据自己的需要进行修改。最后,代码会输出后序遍历的结果。
希望能够帮到你!如果有任何疑问,请随时提出。
阅读全文