C语言已知二叉树的先序遍历序列、中序遍历序列,请画出该二叉树,并给出其后序遍历序列。
时间: 2025-01-23 12:13:36 浏览: 43
### 构造二叉树并求解后序遍历
为了根据给定的先序遍历和中序遍历序列构造二叉树,并求解其后序遍历序列,在C语言中的实现可以分为几个部分来完成。首先,定义二叉树节点的数据结构[^3]:
```c
struct TreeNode {
char val;
struct TreeNode *left, *right;
TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};
```
接着,编写用于创建二叉树以及执行不同方式遍历的方法。对于构建二叉树而言,核心在于利用先序遍历的第一个元素作为根节点,并通过查找此元素在中序遍历的位置将其分割成左右两棵子树,再递归处理这两部分直到全部节点都被加入到对应的分支上。
下面展示了一个完整的程序框架,它接收两个字符串参数分别代表先序与中序遍历的结果,并返回最终形成的二叉树对象及其相应的后序遍历输出[^1][^2]:
```c
#include <stdio.h>
#include <string.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} Node;
Node* buildTree(const char* preorder, const char* inorder);
void postorderTraversal(Node*);
int main() {
// 示例输入:假设 "pre" 是先序遍历结果,“in” 是中序遍历结果
const char pre[] = "abdecfg";
const char in[] = "dbeafc";
printf("Pre-order sequence: %s\n", pre);
printf("In-order sequence : %s\n", in);
Node* root = buildTree(pre, in);
printf("\nPost-order traversal:\n");
postorderTraversal(root);
return 0;
}
// 辅助函数:寻找目标字符在数组中的位置
static inline int findIndex(const char* str, size_t length, char target){
for (size_t i=0 ;i<length;i++)
if(str[i]==target)return i;
return -1;
}
// 创建二叉树的核心逻辑
Node* buildTree(const char* preorder, const char* inorder) {
static unsigned index = 0; // 当前正在处理的先序索引
if (!strlen(inorder)) return NULL;
// 获取当前根节点值
char currentRootValue = preorder[index++];
// 初始化新节点
Node* newNode = malloc(sizeof(*newNode));
memset(newNode, 0, sizeof(*newNode));
newNode->val = currentRootValue;
// 查找根节点在中序遍历中的位置
int pos = findIndex(inorder,strlen(inorder),currentRootValue);
// 左子树由中序遍历左侧部分构成
char leftSubtree[strlen(inorder)];
strncpy(leftSubtree,inorder,pos);
leftSubtree[pos]='\0';
newNode->left = buildTree(preorder,leftSubtree);
// 右子树由中序遍历右侧剩余部分构成
char rightSubtree[strlen(inorder)-pos];
strcpy(rightSubtree,&inorder[pos+1]);
newNode->right = buildTree(preorder,rightSubtree);
return newNode;
}
// 执行后序遍历打印
void postorderTraversal(Node* node) {
if(node != NULL){
postorderTraversal(node->left);
postorderTraversal(node->right);
putchar(node->val);
}
}
```
上述代码实现了基于先序和中序遍历重建二叉树的功能,并展示了如何获取该树的后序遍历顺序。
阅读全文
相关推荐

















