对于给定的二叉树，输出其先序序列、中序序列、后序序列并输出叶子结点数。输入格式: 二叉树的先序遍历序列。 提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。 输出格式: 若是非空二叉树，则输出四行内容 第一行是二叉树的先序遍历序列； 第二行是二叉树的中序遍历序列； 第三行是二叉树的后序遍历序列； 第四行是叶子结点数； 若是空二叉树 只需输出叶子数0

### 实现二叉树的先序、中序、后序遍历并统计叶子节点数量 为了完成这一目标，可以基于给定的先序序列（使用 `'#'` 表示空树），通过递归方式构建二叉树，并进一步实现先序、中序和后序遍历功能，同时统计叶子节点的数量。 以下是完整的 Python 实现： #### 构建二叉树类 定义一个简单的二叉树节点结构 `Node` 和辅助函数用于重建二叉树[^1]。 ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def build_tree(preorder): """根据先序序列 (使用 '#' 表示空树) 重建二叉树""" if not preorder or preorder[0] == '#': preorder.pop(0) return None root = Node(preorder[0]) preorder.pop(0) root.left = build_tree(preorder) root.right = build_tree(preorder) return root ``` #### 遍历算法 实现先序、中序和后序遍历逻辑。这些遍历均可以通过递归来完成[^2]。 ```python def preorder_traversal(root, result=None): """先序遍历""" if result is None: result = [] if root: result.append(root.data) preorder_traversal(root.left, result) preorder_traversal(root.right, result) return result def inorder_traversal(root, result=None): """中序遍历""" if result is None: result = [] if root: inorder_traversal(root.left, result) result.append(root.data) inorder_traversal(root.right, result) return result def postorder_traversal(root, result=None): """后序遍历""" if result is None: result = [] if root: postorder_traversal(root.left, result) postorder_traversal(root.right, result) result.append(root.data) return result ``` #### 统计叶子节点数量 通过递归的方式判断当前节点是否为叶子节点来统计总数[^3]。 ```python def count_leaves(root): """统计叶子节点数量""" if root is None: return 0 if root.left is None and root.right is None: return 1 return count_leaves(root.left) + count_leaves(root.right) ``` #### 主程序调用 将以上模块组合起来形成最终解决方案。 ```python if __name__ == "__main__": # 输入先序序列 input_preorder = list(input("请输入先序序列（使用 '#' 表示空树）：").split()) # 建立二叉树 tree_root = build_tree(input_preorder.copy()) # 使用副本防止修改原始输入 # 获取各种遍历结果 preorder_result = preorder_traversal(tree_root) inorder_result = inorder_traversal(tree_root) postorder_result = postorder_traversal(tree_root) # 计算叶子节点数量 leaf_count = count_leaves(tree_root) # 输出结果 print(f"先序遍历序列: {' '.join(preorder_result)}") print(f"中序遍历序列: {' '.join(inorder_result)}") print(f"后序遍历序列: {' '.join(postorder_result)}") print(f"叶子节点数量: {leaf_count}") ``` 此代码实现了从先序序列生成二叉树的功能，并提供了先序、中序、后序遍历的结果以及叶子节点数量的统计。 ---