用C实现:给定一个 二又树的先序序列ABDEGCHF,中序序列DBEGAHCF,要求输出二叉树的后续序列、
时间: 2023-12-08 07:27:00 浏览: 27
好的,以下是使用 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;
char root_val = *preorder;
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = root_val;
int root_index;
for (root_index = 0; root_index < len; root_index++) {
if (*(inorder + root_index) == root_val) break;
}
root->left = buildTree(preorder + 1, inorder, root_index);
root->right = buildTree(preorder + 1 + root_index, inorder + root_index + 1, len - root_index - 1);
return root;
}
/* 后序遍历二叉树 */
void postorder(TreeNode *root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%c", root->data);
}
int main() {
char preorder[] = "ABDEGCHF";
char inorder[] = "DBEGAHCF";
int len = sizeof(preorder) / sizeof(preorder[0]);
TreeNode *root = buildTree(preorder, inorder, len);
printf("二叉树的后序遍历序列为:");
postorder(root);
printf("\n");
return 0;
}
```
程序首先定义了二叉树的结构体,包含数据域和左右子树指针。随后定义了一个 `buildTree` 函数,该函数通过递归的方式根据给定的先序遍历序列和中序遍历序列构建二叉树。具体实现过程为:先根据先序序列的第一个元素确定根节点,然后在中序序列中查找根节点,可以将中序序列分成左子树序列和右子树序列。接下来,分别递归构建左右子树,最终得到一个完整的二叉树。程序中的 `postorder` 函数用于后序遍历二叉树,并输出遍历结果。主函数中,首先根据给定的先序遍历序列和中序遍历序列构建二叉树,然后调用 `postorder` 函数输出二叉树的后序遍历序列。