写一段C语言代码,要求已知中序序列和后序序列求前序序列
时间: 2023-06-20 17:06:38 浏览: 95
以下是一段求解中序序列和后序序列求前序序列的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
int search(int arr[], int start, int end, int value) {
int i;
for (i = start; i <= end; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
void printPreorder(int inorder[], int postorder[], int inStart, int inEnd, int *postIndex) {
if (inStart > inEnd) {
return;
}
int curr = postorder[*postIndex];
(*postIndex)--;
if (inStart == inEnd) {
printf("%d ", curr);
return;
}
int inIndex = search(inorder, inStart, inEnd, curr);
printPreorder(inorder, postorder, inIndex + 1, inEnd, postIndex);
printPreorder(inorder, postorder, inStart, inIndex - 1, postIndex);
printf("%d ", curr);
}
void printPreorderWrapper(int inorder[], int postorder[], int n) {
int postIndex = n - 1;
printPreorder(inorder, postorder, 0, n - 1, &postIndex);
}
int main() {
int inorder[] = {4, 2, 5, 1, 3};
int postorder[] = {4, 5, 2, 3, 1};
int n = sizeof(inorder) / sizeof(inorder[0]);
printf("Preorder traversal of the constructed tree: ");
printPreorderWrapper(inorder, postorder, n);
return 0;
}
```
这段代码中,`printPreorder` 函数递归地构建前序序列。它首先从后序序列中取出当前的根节点,然后在中序序列中查找这个根节点的位置,将中序序列分成左子树和右子树两部分,再分别递归地构建左子树和右子树。每次递归都会先构建右子树,再构建左子树,最后输出当前节点的值,这就是前序遍历。`printPreorderWrapper` 函数是一个包装函数,用于初始化 `postIndex` 变量并调用 `printPreorder` 函数。
阅读全文