请用C语言代码编写程序输入二叉树的先序遍历序列和中序遍历序列,采用二叉链表建立该二叉树,并输出该二叉树的后序遍历序列。
时间: 2023-07-24 22:16:30 浏览: 71
好的,以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode *buildTree(char *preorder, char *inorder, int len) {
if (len == 0) {
return NULL;
}
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->data = *preorder;
int rootIndex = 0;
for (int i = 0; i < len; i++) {
if (*(inorder + i) == *preorder) {
rootIndex = i;
break;
}
}
root->left = buildTree(preorder + 1, inorder, rootIndex);
root->right = buildTree(preorder + rootIndex + 1, inorder + rootIndex + 1, len - rootIndex - 1);
return root;
}
void postorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->data);
}
int main() {
char preorder[20], inorder[20];
printf("请输入二叉树的先序遍历序列:");
scanf("%s", preorder);
printf("请输入二叉树的中序遍历序列:");
scanf("%s", inorder);
int len = strlen(preorder);
TreeNode *root = buildTree(preorder, inorder, len);
printf("二叉树的后序遍历序列为:");
postorderTraversal(root);
printf("\n");
return 0;
}
```
解释一下代码:
首先定义一个二叉树节点的结构体 `TreeNode`,包括节点的数据 `data`、指向左子树的指针 `left` 和指向右子树的指针 `right`。
然后定义一个递归函数 `buildTree`,用于根据先序遍历序列和中序遍历序列构建二叉树。函数接受三个参数,分别是先序遍历序列、中序遍历序列和序列长度。如果序列长度为0,直接返回NULL。否则,取出先序遍历序列中的第一个元素作为根节点,然后在中序遍历序列中找到根节点的位置,将序列分为左子树和右子树两部分,递归调用 `buildTree` 函数构建左右子树,最后返回根节点。
接着定义一个递归函数 `postorderTraversal`,用于后序遍历二叉树并输出节点数据。函数接受一个参数,即二叉树的根节点。如果根节点为空,直接返回。否则,先递归遍历左子树,再递归遍历右子树,最后输出根节点的数据。
最后在 `main` 函数中,读入先序遍历序列和中序遍历序列,调用 `buildTree` 函数构建二叉树,然后调用 `postorderTraversal` 函数输出后序遍历序列。