函数名为 char* getpost(char preA[],char inA[],int N)
时间: 2023-12-18 08:04:31 浏览: 54
剑桥少儿英语预备级 PreA UPPT课件.pptx
好的,那么以下是函数名为 `char* getpost(char preA[], char inA[], int N)` 的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int find_idx(char *inorder, int start, int end, char target) {
for (int i = start; i <= end; i++) {
if (inorder[i] == target) {
return i;
}
}
return -1;
}
TreeNode* buildTree(char* preorder, int preStart, int preEnd, char* inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[preStart];
root->left = NULL;
root->right = NULL;
int rootIdx = find_idx(inorder, inStart, inEnd, preorder[preStart]);
int leftLen = rootIdx - inStart;
int rightLen = inEnd - rootIdx;
root->left = buildTree(preorder, preStart + 1, preStart + leftLen, inorder, inStart, rootIdx - 1);
root->right = buildTree(preorder, preEnd - rightLen + 1, preEnd, inorder, rootIdx + 1, inEnd);
return root;
}
void postorder(TreeNode *root, char *result, int *idx) {
if (root == NULL) {
return;
}
postorder(root->left, result, idx);
postorder(root->right, result, idx);
result[*idx] = root->val;
(*idx)++;
}
char* getpost(char preA[], char inA[], int N) {
TreeNode *root = buildTree(preA, 0, N - 1, inA, 0, N - 1);
char *result = (char*)malloc(sizeof(char) * (N + 1));
memset(result, 0, sizeof(char) * (N + 1));
int idx = 0;
postorder(root, result, &idx);
return result;
}
int main() {
char preA[] = "ABDEGCHF";
char inA[] = "DBEGAHCF";
int N = sizeof(preA) / sizeof(preA[0]);
char *postA = getpost(preA, inA, N);
printf("%s", postA);
free(postA);
return 0;
}
```
其中,`getpost`函数根据先序遍历序列和中序遍历序列构造出二叉树,并返回二叉树的后序遍历序列。`postorder`函数实现后序遍历二叉树,并将结果存储在`result`数组中,`idx`变量表示存储结果的数组下标。
阅读全文