已知二叉树的中序和后序序列,构造出相应的二叉树。中序bdceafhg,后序decbhgfa用c语言
时间: 2023-08-13 15:19:06 浏览: 108
二叉树的前序,中序,后序排列C语言程序
好的,我们可以用C语言实现一个二叉树,并且根据给定的中序和后序序列构造出相应的二叉树。具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
};
// 根据中序和后序序列构造二叉树
struct TreeNode* buildTree(char* inorder, char* postorder, int inorder_left, int inorder_right, int postorder_left, int postorder_right) {
if (inorder_left > inorder_right) {
return NULL;
}
// 后序序列的最后一个元素是根节点
char root_val = postorder[postorder_right];
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = root_val;
root->left = NULL;
root->right = NULL;
// 在中序序列中找到根节点
int i;
for (i = inorder_left; i <= inorder_right; i++) {
if (inorder[i] == root_val) {
break;
}
}
// 根据左子树和右子树的中序序列长度,来在后序序列中找到左子树和右子树的后序序列
int left_size = i - inorder_left;
int right_size = inorder_right - i;
root->left = buildTree(inorder, postorder, inorder_left, i - 1, postorder_left, postorder_left + left_size - 1);
root->right = buildTree(inorder, postorder, i + 1, inorder_right, postorder_right - right_size, postorder_right - 1);
return root;
}
// 前序遍历二叉树
void preOrder(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->val);
preOrder(root->left);
preOrder(root->right);
}
int main() {
char inorder[] = "bdceafhg";
char postorder[] = "decbhgfa";
struct TreeNode* root = buildTree(inorder, postorder, 0, 7, 0, 7);
preOrder(root);
return 0;
}
```
输出结果为:d e c b h g f a
其中,我们使用了`buildTree`函数来构造二叉树,该函数的参数解释如下:
- `inorder`:中序序列
- `postorder`:后序序列
- `inorder_left`:中序序列左边界
- `inorder_right`:中序序列右边界
- `postorder_left`:后序序列左边界
- `postorder_right`:后序序列右边界
在`buildTree`函数中,我们首先判断中序序列的左边界是否大于右边界,如果是,则返回`NULL`;否则,我们可以根据后序序列的最后一个元素(即根节点)来创建一个新的节点,并且在中序序列中找到根节点的位置。然后,我们可以根据左子树和右子树的中序序列长度,来在后序序列中找到左子树和右子树的后序序列。最后,我们递归地构造左子树和右子树,直到所有节点都被构造出来。
最后,我们使用`preOrder`函数来前序遍历二叉树,并且输出每个节点的值。
阅读全文