假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树,并写出后序序列。C语言代码
时间: 2024-03-17 13:39:48 浏览: 69
二叉树先序和中序求后序
二叉树的节点结构体定义如下:
```c
struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
};
```
可以通过递归构建二叉树,具体实现如下:
```c
struct TreeNode* buildTree(char* preorder, int preorderSize, char* inorder, int inorderSize) {
return build(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1);
}
struct TreeNode* build(char* preorder, int preStart, int preEnd, char* inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
char rootVal = preorder[preStart];
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = rootVal;
root->left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
root->right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
```
构建完成后,可以进行后序遍历,得到后序序列:
```c
void postorder(struct TreeNode* root, char* result, int* returnSize) {
if (root == NULL) {
return;
}
postorder(root->left, result, returnSize);
postorder(root->right, result, returnSize);
result[(*returnSize)++] = root->val;
}
char* postorderTraversal(struct TreeNode* root, int* returnSize) {
char* result = (char*)malloc(sizeof(char) * 1000);
*returnSize = 0;
postorder(root, result, returnSize);
return result;
}
```
阅读全文