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

好的，我记录下来了。以下是使用 Python 实现二叉树的链式存储结构和递归算法的代码：

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def create_tree_from_input(self, input_str):
        input_list = input_str.split()
        node_list = []
        for i in range(len(input_list)):
            if input_list[i] != '#':
                node = TreeNode(int(input_list[i]))
                node_list.append(node)
                if i == 0:
                    self.root = node
                else:
                    if i % 2 == 1:
                        node_list[(i-1)//2].left = node
                    else:
                        node_list[(i-1)//2].right = node

    def create_tree_from_post_and_inorder(self, postorder, inorder):
        if not postorder or not inorder:
            return None
        root_val = postorder[-1]
        root = TreeNode(root_val)
        index = inorder.index(root_val)
        root.left = self.create_tree_from_post_and_inorder(postorder[:index], inorder[:index])
        root.right = self.create_tree_from_post_and_inorder(postorder[index:-1], inorder[index+1:])
        self.root = root
        return root

    def preorder(self, root):
        if root:
            print(root.data, end=' ')
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(root.data, end=' ')
            self.inorder(root.right)

    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            print(root.data, end=' ')

    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 root:
            temp = root.left
            root.left = root.right
            root.right = temp
            self.swap_left_and_right(root.left)
            self.swap_left_and_right(root.right)

    def is_same_tree(self, root1, root2):
        if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        if root1.data != root2.data:
            return False
        return self.is_same_tree(root1.left, root2.left) and self.is_same_tree(root1.right, root2.right)

    def copy_tree(self, root):
        if not root:
            return None
        new_root = TreeNode(root.data)
        new_root.left = self.copy_tree(root.left)
        new_root.right = self.copy_tree(root.right)
        return new_root

    def draw_tree(self, root):
        if not root:
            return None
        node_list = [(root, 0)]
        cur_level = 0
        res = ''
        while node_list:
            node, level = node_list.pop(0)
            if level > cur_level:
                res += '\n'
                cur_level = level
            res += str(node.data) + ' '
            if node.left:
                node_list.append((node.left, level+1))
            if node.right:
                node_list.append((node.right, level+1))
        print(res)

其中，`TreeNode` 类表示二叉树的节点，`BinaryTree` 类表示二叉树，其中包含了二叉树的创建、遍历、节点数、交换左右子树、判断是否相同、复制、绘制等功能。

例如，使用 `create_tree_from_input` 方法创建二叉树：

tree = BinaryTree()
tree.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
tree.draw_tree(tree.root)

输出：

5 
3 8 
1 4 10 

使用 `create_tree_from_post_and_inorder` 方法根据后序遍历和中序遍历创建二叉树：

tree = BinaryTree()
tree.create_tree_from_post_and_inorder([1, 4, 3, 10, 8, 5], [1, 3, 4, 5, 8, 10])
tree.draw_tree(tree.root)

输出：

5 
3 8 
1 4 10 

使用 `preorder`、`inorder`、`postorder` 方法遍历二叉树：

tree = BinaryTree()
tree.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
tree.preorder(tree.root) # 5 3 1 4 8 10
tree.inorder(tree.root) # 1 3 4 5 8 10
tree.postorder(tree.root) # 1 4 3 10 8 5

使用 `count_leaves` 方法计算二叉树的叶子节点数：

tree = BinaryTree()
tree.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
print(tree.count_leaves(tree.root)) # 3

使用 `swap_left_and_right` 方法交换二叉树的左右子树：

tree = BinaryTree()
tree.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
tree.swap_left_and_right(tree.root)
tree.draw_tree(tree.root)

输出：

5 
8 3 
# 10 4 1 

使用 `is_same_tree` 方法判断两棵二叉树是否相同：

tree1 = BinaryTree()
tree1.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
tree2 = BinaryTree()
tree2.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
tree3 = BinaryTree()
tree3.create_tree_from_input('5 3 8 1 4 # 10 # # # # # 7')
print(tree1.is_same_tree(tree2.root, tree3.root)) # False

使用 `copy_tree` 方法复制二叉树：

tree1 = BinaryTree()
tree1.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
tree2 = BinaryTree()
tree2.root = tree2.copy_tree(tree1.root)
tree2.draw_tree(tree2.root)

输出：

5 
3 8 
1 4 10 

使用 `draw_tree` 方法绘制二叉树：

tree = BinaryTree()
tree.create_tree_from_input('5 3 8 1 4 # 10 # # # # # #')
tree.draw_tree(tree.root)

输出：

5 
3 8 
1 4 10