编写算法建立一棵二叉树的二叉链表 输出而二叉树的三种遍历序列 统计二叉树结点数 叶子数 深度

### 构建二叉树的二叉链表表示 为了实现二叉树的二叉链表结构及其相关功能，可以按照以下方法设计算法。以下是完整的解决方案： #### 前序遍历递归建立二叉树 通过输入先序遍历序列中的数据动态构建二叉树[^1]。如果遇到字符 `#` 表示为空节点，则停止当前分支的构建。 ```python class TreeNode: def __init__(self, value=None): self.value = value self.left = None self.right = None def build_tree(preorder_iter): try: current_value = next(preorder_iter) if current_value == '#': return None node = TreeNode(current_value) node.left = build_tree(preorder_iter) node.right = build_tree(preorder_iter) return node except StopIteration: return None ``` #### 输出三种遍历序列 利用递归方式分别实现前序、中序和后序遍历。 ```python def preorder_traversal(node, result=None): if result is None: result = [] if node: result.append(node.value) preorder_traversal(node.left, result) preorder_traversal(node.right, result) return result def inorder_traversal(node, result=None): if result is None: result = [] if node: inorder_traversal(node.left, result) result.append(node.value) inorder_traversal(node.right, result) return result def postorder_traversal(node, result=None): if result is None: result = [] if node: postorder_traversal(node.left, result) postorder_traversal(node.right, result) result.append(node.value) return result ``` #### 统计结点数、叶子数和深度 定义辅助函数计算二叉树的相关属性[^1]。 ```python def count_nodes(node): if not node: return 0 return 1 + count_nodes(node.left) + count_nodes(node.right) def count_leaves(node): if not node: return 0 if not node.left and not node.right: return 1 return count_leaves(node.left) + count_leaves(node.right) def tree_depth(node): if not node: return 0 left_depth = tree_depth(node.left) right_depth = tree_depth(node.right) return max(left_depth, right_depth) + 1 ``` #### 主程序设计 提供菜单驱动界面完成各项操作需求。 ```python if __name__ == "__main__": input_data = input("请输入先序遍历序列（用逗号分隔，'#'代表空节点）：").split(',') root = build_tree(iter(input_data)) print(f"前序遍历结果: {preorder_traversal(root)}") print(f"中序遍历结果: {inorder_traversal(root)}") print(f"后序遍历结果: {postorder_traversal(root)}") total_nodes = count_nodes(root) leaf_count = count_leaves(root) depth = tree_depth(root) print(f"总节点数: {total_nodes}") print(f"叶子节点数: {leaf_count}") print(f"树的高度: {depth}") ``` 以上代码实现了二叉树的构建、遍历以及统计功能。其中，二叉链表作为基础存储结构被广泛应用于非完全二叉树的操作中[^2]。