用c语言写一段代码,完成下题,假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树,并写出后序序列,不要用你上面给出的答案,因为那个答案是错误的
时间: 2024-03-13 19:45:59 浏览: 51
好的,以下是用C语言实现的代码,可以构建二叉树并输出其后序遍历序列:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据先序序列和中序序列构建二叉树
TreeNode* buildTree(char* preorder, char* inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd) {
return NULL;
}
char rootVal = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = rootVal;
root->left = buildTree(preorder, inorder, preStart+1, preStart+leftSize, inStart, rootIndex-1);
root->right = buildTree(preorder, inorder, preStart+leftSize+1, preEnd, rootIndex+1, inEnd);
return root;
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c", root->val);
}
int main() {
char preorder[] = "EBADCFHGIKJ";
char inorder[] = "ABCDEFGHIJK";
int len = sizeof(preorder) / sizeof(preorder[0]);
TreeNode* root = buildTree(preorder, inorder, 0, len-1, 0, len-1);
postorderTraversal(root);
return 0;
}
```
根据先序序列和中序序列构建出的二叉树如下所示:
```
E
/ \
B J
/ \ / \
A D I K
/ \
C F
\
H
```
该二叉树的后序遍历序列为:`ADCFHIGKJEB`
希望能够帮到您!
阅读全文