【问题描述】 打印二叉树从根结点到叶子结点的所有路径 【输入形式】 二叉树的先序扩展序列(字符串,以#填充空结点) 【输出形式】 路径1 路径2 路径n 【样例输入】 ABC##DE#G##F### 【样例输出】 ABC ABDEG ABDF
时间: 2023-11-30 18:05:09 浏览: 83
二叉树上机作业-二叉树讲义
好的,根据您的要求,以下是基于C语言实现的代码,希望能够帮到您:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 树的结点定义
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 打印所有从根结点到叶子结点的路径
void print_all_path(TreeNode *root, char *path, int path_len) {
if (!root) {
return;
}
// 添加当前结点到路径中
path[path_len] = root->val;
path_len++;
// 若当前结点为叶子结点,则打印路径
if (!root->left && !root->right) {
path[path_len] = '\0';
printf("%s ", path);
}
// 若当前结点有左子树,则递归遍历左子树
if (root->left) {
print_all_path(root->left, path, path_len);
}
// 若当前结点有右子树,则递归遍历右子树
if (root->right) {
print_all_path(root->right, path, path_len);
}
}
// 通过先序扩展序列构建二叉树
TreeNode* construct_tree(char *preorder, int *index) {
char val = preorder[(*index)++];
if (val == '#') {
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = construct_tree(preorder, index);
root->right = construct_tree(preorder, index);
return root;
}
// 主函数
int main() {
// 读入先序扩展序列
char preorder[100];
scanf("%s", preorder);
// 构建二叉树
int index = 0;
TreeNode *root = construct_tree(preorder, &index);
// 打印所有从根结点到叶子结点的路径
char path[100];
print_all_path(root, path, 0);
return 0;
}
```
您可以将上述代码保存到名为`print_all_path.c`的文件中,并使用C编译器进行编译和运行。例如,您可以使用gcc编译器来编译代码:
```
gcc print_all_path.c -o print_all_path
```
接着,您可以输入先序扩展序列(例如`ABC##DE#G##F###`),程序会自动构建对应的二叉树,并打印所有从根结点到叶子结点的路径(例如`ABC ABDEG ABDF`)。
阅读全文