假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树,并用c语言写出后序序列
时间: 2024-01-23 12:14:04 浏览: 93
根据二叉树的先序序列和中序序列可以唯一确定一个二叉树,因此可以通过以下步骤构建该二树:
1. 先序序列的第一个元素 E 为根节点。
2. 在中序序列中找到根节点 E 的位置,其左侧为左子树的中序序列,右侧为右子树的中序序列。
3. 根据左子树的中序序列长度,可以得知左子树的先序序列为 BADC,右子树的先序序列为 FHGIKJ。
4. 递归重复上述步骤,构建左子树和右子树。
构建完成后的二叉树如下所示:
```
E
/ \
B F
/ \ \
A D H
/ \ / \
C G I J
\
K
```
使用 C 语言实现后序遍历的代码如下:
```c
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void postorderTraversal(TreeNode* root, char* res, int* index) {
if (root == NULL) {
return;
}
postorderTraversal(root->left, res, index);
postorderTraversal(root->right, res, index);
res[(*index)++] = root->val;
}
char* getPostOrder(char* preorder, char* inorder) {
int len = strlen(preorder);
int rootIndex = -1;
for (int i = 0; i < len; i++) {
if (inorder[i] == preorder[0]) {
rootIndex = i;
break;
}
}
if (rootIndex == -1) {
return "";
}
TreeNode* root = (TreeNode*) malloc(sizeof(TreeNode));
root->val = preorder[0];
root->left = getPostOrder(preorder + 1, inorder);
root->right = getPostOrder(preorder + rootIndex + 1, inorder + rootIndex + 1);
char* res = (char*) malloc(len + 1);
int index = 0;
postorderTraversal(root, res, &index);
res[len] = '\0';
free(root);
return res;
}
```
调用该函数,将先序序列和中序序列作为参数传入,即可得到后序序列 ACGBDKJIFHE。
阅读全文