给定一个二叉树的先序序列ABDEGCHF,中序序列DBEGAHCF,要求输出二叉树的后序序列,用c语言代码具体怎么实现?
时间: 2023-08-17 12:38:02 浏览: 114
下面是使用C语言实现根据二叉树的先序序列和中序序列构建二叉树,并输出二叉树的后序序列的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 二叉树节点 */
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
/* 根据先序序列和中序序列构建二叉树 */
TreeNode *buildTree(char *preorder, char *inorder, int preStart, int preEnd, int inStart, int inEnd) {
// 先序序列为空,返回NULL
if (preStart > preEnd) {
return NULL;
}
// 创建根节点
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = preorder[preStart];
root->left = root->right = NULL;
// 在中序序列中查找根节点的位置
int rootIndex;
for (rootIndex = inStart; rootIndex <= inEnd; rootIndex++) {
if (inorder[rootIndex] == root->val) {
break;
}
}
// 计算左子树的节点个数
int leftSize = rootIndex - inStart;
// 递归构建左子树和右子树
root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root->right = buildTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
/* 输出二叉树的后序序列 */
void postorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c", root->val);
}
int main() {
char preorder[] = "ABDEGCHF";
char inorder[] = "DBEGAHCF";
// 构建二叉树
TreeNode *root = buildTree(preorder, inorder, 0, strlen(preorder) - 1, 0, strlen(inorder) - 1);
// 输出二叉树的后序序列
printf("The postorder traversal of the binary tree is: ");
postorderTraversal(root);
printf("\n");
return 0;
}
```
上述代码中,`buildTree()`函数使用递归的方式根据先序序列和中序序列构建二叉树,`postorderTraversal()`函数使用递归的方式输出二叉树的后序序列。在`main()`函数中,先定义了二叉树的先序序列和中序序列,然后调用`buildTree()`函数构建二叉树,最后调用`postorderTraversal()`函数输出二叉树的后序序列。运行上述代码,将会输出如下结果:
```
The postorder traversal of the binary tree is: DGEBGHFCA
```
阅读全文