C语言给出一个按照“扩展遍历序列”的扩展后序遍历序列字符串,'#' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并按教材所示的横向显示的树状打印的二叉树
时间: 2024-05-04 11:16:36 浏览: 14
我们需要如何将其转换为原二叉树?
通过对给出的“扩展遍历序列”的扩展后序遍历序列字符串进行观察并结合二叉树的后序遍历特性,可以发现:每个节点在字符串中出现的位置相当于它在二叉树中被遍历的顺序。具体来说,每个节点在字符串中出现的位置,将其分为三个区域:左子树区域、右子树区域和父节点区域。其中,左子树区域的节点都在右子树区域和父节点区域之前出现,右子树区域的节点都在父节点区域之前出现。因此,我们可以根据这个特性,递归地构建原二叉树,具体过程如下:
1. 如果字符串为空,则返回 NULL。
2. 在字符串中找到最后一个节点,即为根节点。
3. 找到根节点之后,将其从字符串中删除,然后递归地构建右子树和左子树,直到字符串为空。
在递归构建左子树和右子树时,需要注意剩余字符串的顺序已经发生了变化,因此需要按照新的顺序继续构建子树。另外,由于给出的是“扩展遍历序列”的扩展后序遍历序列字符串,因此需要区分叶子节点和非叶子节点,递归构建的时候需要对其进行判断。
最终,递归完成后就可以得到原二叉树。
示例代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
char val;
struct node *left;
struct node *right;
} Node;
// 从扩展后序遍历序列字符串中构建二叉树
Node* build_tree(char *s, int len) {
if (len == 0) return NULL;
Node *root = (Node*)malloc(sizeof(Node));
root->val = s[len-1];
root->left = root->right = NULL;
int idx = len - 2;
while (idx >= 0 && s[idx] != '#') {
idx--;
}
int right_end = idx - 1;
root->right = build_tree(s, right_end + 1);
int left_end = idx - 1;
root->left = build_tree(s, left_end + 1);
return root;
}
// 中序遍历二叉树,用于验证是否构建成功
void in_order_traversal(Node *root) {
if (root == NULL) return;
in_order_traversal(root->left);
printf("%c ", root->val);
in_order_traversal(root->right);
}
void main() {
char *s = "acf#m#qow##em###b##n#y##lz##g##d##";
int len = strlen(s);
Node *root = build_tree(s, len);
in_order_traversal(root);
}
```
相关推荐
![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)