C语言给出一个按照“扩展遍历序列”的扩展后序遍历序列字符串,'#' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并按教材所示的横向显示的树状打印的二叉树
时间: 2024-05-14 15:16:48 浏览: 11
请编写算法重建原二叉树。
这道题目是经典的二叉树重建问题。根据扩展后序遍历的特点,可以得知最后一个字符为根节点的值,然后在扩展后序遍历中找到该节点的位置,划分出左右子树的字符串,递归重建左右子树即可。具体步骤如下:
1.找到根节点的值,即扩展后序遍历序列的最后一个元素。
2.在扩展后序遍历序列中找到该元素的位置,以此分割出左右子树的扩展后序遍历序列。
3.根据左右子树的扩展后序遍历序列递归重建左右子树。
4.返回根节点,作为整棵树的根节点。
下面是代码实现:
```c
typedef struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode *buildTree(char *str)
{
int len = strlen(str);
if (len == 0) return NULL; // 空字符串返回 NULL
// 找到根节点的值
int i = len - 1;
while (i >= 0 && str[i] != ',') i--;
int val = atoi(str + i + 1);
// 分割左右子树的扩展后序遍历序列
int j = 0;
while (j < i && str[j] != ',') j++;
char *left_str = str;
char *right_str = str + j + 1;
// 递归重建左右子树
TreeNode *left = buildTree(left_str);
TreeNode *right = buildTree(right_str);
// 返回根节点
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = val;
root->left = left;
root->right = right;
return root;
}
```
需要注意的是,这里使用了一个辅助函数 atoi(),用于将字符串转化为整数。在使用之前需要引入 stdlib.h 头文件。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)