帮我写一段根据前序遍历和中序遍历输出后序遍历的代码
时间: 2023-10-24 11:12:36 浏览: 35
好的,以下是根据前序遍历和中序遍历输出后序遍历的代码,希望能对你有所帮助:
```
#include <cstdio>
#include <cstring>
const int MAXN = 1000010;
int pre[MAXN], idx[MAXN], n;
void dfs(int l1, int r1, int l2, int r2) { // l1 r1代表前序遍历在序列中的位置,l2 r2代表中序遍历在序列中的位置
if (l1 > r1) return;
int root = pre[l1]; // 前序遍历的第一个数是根节点
int p = idx[root];
dfs(l1 + 1, l1 + p - l2, l2, p - 1); //递归遍历左子树
dfs(l1 + p - l2 + 1, r1, p+1, r2); //递归遍历右子树
printf("%d ", root); //输出根节点
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &pre[i]);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
idx[x] = i; //记录中序遍历每个节点在序列中的位置
}
dfs(1, n, 1, n);
return 0;
}
```
记得要考虑边界情况哦!
相关问题
用C++编写一段代码实现前序遍历、中序遍历、后序遍历二叉树
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建节点
TreeNode* createNode(int data) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 前序遍历
void preorderTraversal(TreeNode *root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// 中序遍历
void inorderTraversal(TreeNode *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// 后序遍历
void postorderTraversal(TreeNode *root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}
int main() {
// 创建二叉树
TreeNode *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("前序遍历:");
preorderTraversal(root);
printf("\n中序遍历:");
inorderTraversal(root);
printf("\n后序遍历:");
postorderTraversal(root);
return 0;
}
帮我写出c++代码:给出一个二叉树的前序遍历和中序遍历求这个二叉树的后序遍历
当然可以!下面是一个用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`函数中,我们给出了一个示例的前序遍历和中序遍历序列,你可以根据自己的需要进行修改。最后,代码会输出后序遍历的结果。
希望能够帮到你!如果有任何疑问,请随时提出。