用C语言实现下列算法:已知某二叉树的中序序列和后序序列分别是:中序:BFDGACHE;后序:FGDBHECA,设计算法构建该二叉树的二叉链表存储结构
时间: 2024-03-14 19:42:43 浏览: 85
以下是使用C语言实现该算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* buildTree(char* inorder, int inStart, int inEnd, char* postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = postorder[postEnd];
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root->val) {
index = i;
break;
}
}
int leftLen = index - inStart;
root->left = buildTree(inorder, inStart, index - 1, postorder, postStart, postStart + leftLen - 1);
root->right = buildTree(inorder, index + 1, inEnd, postorder, postStart + leftLen, postEnd - 1);
return root;
}
TreeNode* buildTreeWrapper(char* inorder, char* postorder, int n) {
return buildTree(inorder, 0, n - 1, postorder, 0, n - 1);
}
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}
}
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
}
int main() {
char inorder[] = "BFDGACHE";
char postorder[] = "FGDBHECA";
int n = sizeof(inorder) / sizeof(char);
TreeNode* root = buildTreeWrapper(inorder, postorder, n);
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");
printf("Postorder Traversal: ");
postorderTraversal(root);
printf("\n");
return 0;
}
```
运行结果为:
```
Inorder Traversal: B D F G A C H E
Postorder Traversal: G F D B H E C A
```
其中,buildTree函数递归构建二叉树,buildTreeWrapper函数作为包装函数方便调用。inorderTraversal和postorderTraversal函数分别实现中序遍历和后序遍历,用于验证构建出的二叉树是否正确。
阅读全文