编写一个程序,在自定义函数中完成下列功能并在主函数进行测试:(1)由树的先序遍历序列和中序遍历序列创建一棵二叉树。(2)输出二叉树的后序遍历序列。测试数据:先序遍历序列:ABDGCEF中序遍历序列:DGBAECF。用c语言实现
时间: 2024-10-24 18:16:35 浏览: 29
为了实现这个功能,我们需要首先定义一个二叉树节点结构,然后编写辅助函数来根据先序和中序遍历序列构造二叉树。接着,我们会实现一个递归函数来获取后序遍历序列。以下是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 辅助函数,用于找到根节点在中序遍历中的位置
int findRootInOrder(int inOrder[], int low, int high) {
for (int i = low; i <= high; i++) {
if (inOrder[i] == inOrder[high]) {
return i;
}
}
return -1;
}
// 根据先序遍历和中序遍历构造二叉树
TreeNode* buildTreeFromTraversal(char preorder[], int preStart, int preEnd,
int inOrder[], int inStart, int inEnd) {
if (preStart >= preEnd || inStart >= inEnd)
return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = preorder[preStart];
int index = findRootInOrder(inOrder, inStart, inEnd);
root->left = buildTreeFromTraversal(preorder, preStart + 1, preStart + index - inStart,
inOrder, inStart, index);
root->right = buildTreeFromTraversal(preorder, preStart + index - inStart + 1,
preEnd, inOrder, index + 1, inEnd);
return root;
}
// 后序遍历
void postorderTraversal(TreeNode* root, char result[], int index) {
if (root == NULL) {
return;
}
postorderTraversal(root->left, result, index);
postorderTraversal(root->right, result, index);
result[index++] = root->data;
}
// 主函数,测试数据
int main() {
char preorder[] = {'A', 'B', 'D', 'G', 'C', 'E', 'F'};
char inOrder[] = {'D', 'G', 'B', 'A', 'E', 'C', 'F'};
int preStart = 0, preEnd = sizeof(preorder) - 1, inStart = 0, inEnd = sizeof(inOrder) - 1;
TreeNode* root = buildTreeFromTraversal(preorder, preStart, preEnd, inOrder, inStart, inEnd);
if (root == NULL) {
printf("Error: Could not construct tree.\n");
return 1;
}
char postResult[50];
int resultIndex = 0;
postorderTraversal(root, postResult, resultIndex);
printf("后序遍历序列: ");
for (int i = 0; i < resultIndex; i++) {
printf("%c", postResult[i]);
}
printf("\n");
free(root); // 释放内存
return 0;
}
```
这个程序首先通过`findRootInOrder`找到中序遍历中的根节点位置,然后根据位置将先序和中序遍历分割成左子树和右子树部分,递归地创建完整的二叉树。最后,`postorderTraversal`函数计算后序遍历序列。在`main`函数中,我们用给定的测试数据进行演示。
阅读全文