python语言编写程序，实现： 1 二叉树的链式存储结构； 2 二叉树的递归算法。 [实验要求] 1 定义二叉树的数据类型，要求用二叉链实现； 2 创建二叉树的存储结构，要求用两种方法实现： （1） 根据输入的字符串创建 （2） 根据二叉树的后序和中序遍历序列创建 3 实现二叉树的递归算法： （1） 先序、中序、后序遍历二叉树，并输出遍历序列； （2） 求二叉树的叶子结点数； （3） 交换二叉树上所有结点的左右子树； （4） 判断两棵二叉树是否相同； （5） 复制二叉树。 4 输出二叉树的图形结构

以下是一个Python实现二叉树的代码，包括二叉树的链式存储结构和递归算法： ```python class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None class BinaryTree: def __init__(self): self.root = None # 根据输入的字符串创建二叉树 def build_tree_from_string(self, s): nodes = s.split(',') self.root = self.build_tree_from_string_helper(nodes, 0) def build_tree_from_string_helper(self, nodes, i): if i >= len(nodes) or nodes[i] == 'None': return None root = TreeNode(int(nodes[i])) root.left = self.build_tree_from_string_helper(nodes, 2*i+1) root.right = self.build_tree_from_string_helper(nodes, 2*i+2) return root # 根据二叉树的后序和中序遍历序列创建二叉树 def build_tree_from_postorder_and_inorder(self, postorder, inorder): if not postorder or not inorder: return None root = TreeNode(postorder[-1]) idx = inorder.index(postorder[-1]) root.left = self.build_tree_from_postorder_and_inorder(postorder[:idx], inorder[:idx]) root.right = self.build_tree_from_postorder_and_inorder(postorder[idx:-1], inorder[idx+1:]) return root # 先序遍历二叉树 def preorder_traversal(self, root): if not root: return [] return [root.val] + self.preorder_traversal(root.left) + self.preorder_traversal(root.right) # 中序遍历二叉树 def inorder_traversal(self, root): if not root: return [] return self.inorder_traversal(root.left) + [root.val] + self.inorder_traversal(root.right) # 后序遍历二叉树 def postorder_traversal(self, root): if not root: return [] return self.postorder_traversal(root.left) + self.postorder_traversal(root.right) + [root.val] # 求二叉树的叶子结点数 def count_leaves(self, root): if not root: return 0 if not root.left and not root.right: return 1 return self.count_leaves(root.left) + self.count_leaves(root.right) # 交换二叉树上所有结点的左右子树 def swap_left_and_right(self, root): if not root: return root.left, root.right = root.right, root.left self.swap_left_and_right(root.left) self.swap_left_and_right(root.right) # 判断两棵二叉树是否相同 def is_same_tree(self, p, q): if not p and not q: return True if not p or not q: return False if p.val != q.val: return False return self.is_same_tree(p.left, q.left) and self.is_same_tree(p.right, q.right) # 复制二叉树 def copy_tree(self, root): if not root: return None new_root = TreeNode(root.val) new_root.left = self.copy_tree(root.left) new_root.right = self.copy_tree(root.right) return new_root # 输出二叉树的图形结构 def print_tree(self): levels = self.get_tree_levels(self.root) height = len(levels) width = 2**(height-1) * 3 - 1 res = [[' ']*width for _ in range(height)] self.fill_tree_levels(res, levels, 0, 0, width-1) for row in res: print(''.join(row)) def get_tree_levels(self, root): if not root: return [] res = [] queue = [(root, 0)] while queue: node, level = queue.pop(0) if len(res) <= level: res.append([]) res[level].append(node) if node: queue.append((node.left, level+1)) queue.append((node.right, level+1)) return res def fill_tree_levels(self, res, levels, level_idx, left, right): if level_idx >= len(levels): return level = levels[level_idx] gap = (right - left + 1) // (len(level)+1) for i, node in enumerate(level): if node: mid = left + (i+1)*gap res[level_idx][mid] = str(node.val) if level_idx < len(levels) - 1: self.fill_tree_levels(res, levels, level_idx+1, left, mid-1) self.fill_tree_levels(res, levels, level_idx+1, mid+1, right) # 测试 tree = BinaryTree() tree.build_tree_from_string('1,2,3,None,None,4,5') print(tree.preorder_traversal(tree.root)) # [1, 2, 3, 4, 5] print(tree.inorder_traversal(tree.root)) # [2, 1, 4, 3, 5] print(tree.postorder_traversal(tree.root)) # [2, 4, 5, 3, 1] print(tree.count_leaves(tree.root)) # 2 tree.swap_left_and_right(tree.root) tree.print_tree() ``` 该代码中，`TreeNode`表示二叉树的节点，`BinaryTree`表示二叉树，包含了创建树、遍历树、修改树、比较树、复制树、输出树等方法。其中，输出树使用了递归遍历树并记录节点深度和坐标的方法。