用C语言编写程序,利用拓展的后序遍历创建二叉树,拓展的后序遍历序列为AB.DF..GC.E.H..,.表示空树
时间: 2024-03-20 19:41:28 浏览: 20
以下是用C语言编写的程序,利用拓展的后序遍历创建二叉树,拓展的后序遍历序列为AB.DF..GC.E.H..,.表示空树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点的结构体
typedef struct TreeNode {
char val; // 节点的值
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 递归创建二叉树的函数
TreeNode* createTree(char *postorder, int *index) {
// 取出当前节点的值
char val = postorder[(*index)--];
// 如果当前节点为空树,返回空节点
if (val == '.') {
return NULL;
}
// 创建一个新节点
TreeNode *node = (TreeNode*) malloc(sizeof(TreeNode));
node->val = val;
// 递归构建右子树
node->right = createTree(postorder, index);
// 递归构建左子树
node->left = createTree(postorder, index);
return node;
}
int main() {
// 定义拓展的后序遍历序列
char postorder[] = "AB.DF..GC.E.H..";
// 定义节点索引
int index = strlen(postorder) - 1;
// 创建二叉树
TreeNode *root = createTree(postorder, &index);
return 0;
}
```
该程序首先定义了二叉树节点的结构体,然后定义了一个递归创建二叉树的函数createTree。该函数的参数包括拓展的后序遍历序列和节点索引,其中节点索引从末尾开始,每次递归时会自减。函数的执行过程与前面介绍的算法相同。
最后,在main函数中调用createTree函数创建二叉树,并返回0表示程序正常结束。