【问题描述】 打印二叉树从根结点到叶子结点的所有路径 【输入形式】 二叉树的先序扩展序列(字符串,以#填充空结点) 【输出形式】 路径1 路径2 路径n 【样例输入】 ABC##DE#G##F### 【样例输出】 ABC ABDEG ABDF
时间: 2023-11-30 08:05:09 浏览: 109
您好,根据您的要求,我已经了解到您需要一个能够打印二叉树从根结点到叶子结点的所有路径的程序。以下是基于Python语言实现的代码,希望能够帮到您:
```python
# 树的结点定义
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 打印所有从根结点到叶子结点的路径
def print_all_path(root, path):
if not root:
return
# 添加当前结点到路径中
path.append(root.val)
# 若当前结点为叶子结点,则打印路径
if not root.left and not root.right:
print(" ".join(path))
# 若当前结点有左子树,则递归遍历左子树
if root.left:
print_all_path(root.left, path)
# 若当前结点有右子树,则递归遍历右子树
if root.right:
print_all_path(root.right, path)
# 回溯,移除当前结点
path.pop()
# 通过先序扩展序列构建二叉树
def construct_tree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == "#":
return None
root = TreeNode(val)
root.left = construct_tree(preorder)
root.right = construct_tree(preorder)
return root
# 主函数
if __name__ == "__main__":
# 读入先序扩展序列
preorder = input().strip().split()
# 构建二叉树
root = construct_tree(preorder)
# 打印所有从根结点到叶子结点的路径
print_all_path(root, [])
```
您可以将上述代码保存到名为`print_all_path.py`的文件中,并在命令行中执行以下命令来运行程序:
```
python print_all_path.py
```
接着,您可以输入先序扩展序列(例如`ABC##DE#G##F###`),程序会自动构建对应的二叉树,并打印所有从根结点到叶子结点的路径(例如`ABC ABDEG ABDF`)。
阅读全文