假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树,并写出后序序列。用C语言写
时间: 2024-02-27 12:55:50 浏览: 27
根据二叉树的先序序列和中序序列可以唯一确定一棵二叉树,可以按照以下步骤构造二叉树:
1. 先序序列的第一个元素为根节点,即E。
2. 在中序序列中找到根节点的位置,根节点前面的为左子树的中序序列,后面的为右子树的中序序列,即:
左子树中序序列:ABCDEF
右子树中序序列:GHIJK
3. 根据左子树中序序列的长度,在先序序列中找到左子树的先序序列,右边的为右子树的先序序列,即:
左子树先序序列:BADCF
右子树先序序列:HGIKJ
4. 递归构造左子树和右子树。
根据上述步骤,可以画出该二叉树:
```
E
/ \
/ \
/ \
B H
/ \ / \
/ \ / \
A D F K
/ / \
/ / \
C G J
```
后序序列为:ACFBDJIKGHHE。下面是用C语言实现构建二叉树和输出后序序列的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体
typedef struct TreeNode {
char data; // 节点数据
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 递归构建二叉树
TreeNode* buildTree(char* preorder, int preStart, int preEnd, char* inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL; // 递归结束条件
}
char rootVal = preorder[preStart]; // 先序序列的第一个元素为根节点
int rootIndex;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); // 创建根节点
root->data = rootVal;
int leftSize = rootIndex - inStart; // 左子树的节点个数
root->left = buildTree(preorder, preStart+1, preStart+leftSize, inorder, inStart, rootIndex-1); // 递归构建左子树
root->right = buildTree(preorder, preStart+leftSize+1, preEnd, inorder, rootIndex+1, inEnd); // 递归构建右子树
return root;
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left); // 后序遍历左子树
postorderTraversal(root->right); // 后序遍历右子树
printf("%c", root->data); // 输出节点数据
}
int main() {
char preorder[] = "EBADCFHGIKJ";
char inorder[] = "ABCDEFGHIJK";
TreeNode* root = buildTree(preorder, 0, 10, inorder, 0, 10);
postorderTraversal(root); // 输出后序序列
return 0;
}
```