c语言代码:已知一个二叉树的中序遍历和后序遍历,求这棵树的前序遍历序列
时间: 2023-06-10 15:04:40 浏览: 124
二叉树的先序,中序,后序遍历(程序源码)
5星 · 资源好评率100%
可以通过以下步骤求解:
1. 后序遍历的最后一个元素为根节点,将后序遍历序列的最后一个元素取出作为根节点。
2. 在中序遍历中找到根节点的位置,那么根节点左边的元素都是左子树的节点,右边的元素都是右子树的节点。
3. 根据中序遍历的左右子树节点数量,可以将后序遍历序列分为左子树和右子树的后序遍历序列。
4. 对于左右子树的后序遍历序列,可以递归地进行求解,得到左子树和右子树的前序遍历序列。
5. 最终的前序遍历序列为:根节点 + 左子树的前序遍历序列 + 右子树的前序遍历序列。
下面是一个示例代码实现:
```c
#include<stdio.h>
#include<stdlib.h>
int findPos(int *arr, int n, int key) {
int i;
for (i = 0; i < n; ++i) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
void post_to_pre(int *post, int *in, int n) {
if (n <= 0) {
return;
}
int root = post[n - 1];
int pos = findPos(in, n, root);
printf("%d ", root);
post_to_pre(post, in, pos);
post_to_pre(post + pos, in + pos + 1, n - pos - 1);
}
int main() {
int post[] = {4, 5, 2, 6, 3, 1};
int in[] = {4, 2, 5, 1, 3, 6};
int n = sizeof(post) / sizeof(int);
printf("The preorder traversal sequence is: ");
post_to_pre(post, in, n);
return 0;
}
// Output: The preorder traversal sequence is: 1 2 4 5 3 6
```
其中,findPos函数用于在中序遍历序列中查找根节点的位置,post_to_pre函数递归求解前序遍历序列。对于示例输入的二叉树,输出的前序遍历序列为1 2 4 5 3 6。
阅读全文