.要求用二叉链表实现二叉树。根据与一棵二叉树对应的扩展二叉树的层序序列构造该 二叉树。输出该二叉树的先序、中序、后序和层序序列。交换该二叉树的所有结点的左、右 子树。输出新二叉树的先序、中序、后序和层序序列。

在二叉链表中实现二叉树，首先我们需要创建一个节点结构，包含数据域、指向前一个节点的指针以及指向下一个节点的指针。下面是基本步骤：

1. **构建二叉树**：从层序序列开始，每一层代表树的一个层次，可以使用队列辅助操作。遍历序列，每次取出一个元素作为根节点，然后将其左右子节点（如果有）分别加入队列对应的位置。

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

def build_binary_tree(layers):
    root = None
    for level in layers:
        node = Node(level[0])
        if root is not None:
            # 添加节点到当前层级
            queue.append(node)
        else:
            root = node
        # 更新下一层的节点位置
        for i in range(1, len(level)):
            node.left = Node(level[i])
            node.right = Node(level[i + 1]) if i < len(level) - 1 else None
            node = node.left
    return root

2. **输出先序、中序、后序序列**：递归遍历函数即可得到。先序遍历（根-左-右），中序遍历（左-根-右），后序遍历（左-右-根）。

3. **交换左右子树**：对每个节点，临时保存其原左子节点和右子节点，然后更新左右子节点。

def swap_subtrees(root):
    if root is not None:
        temp_left = root.left
        temp_right = root.right
        root.left, root.right = temp_right, temp_left
        swap_subtrees(root.left)
        swap_subtrees(root.right)

4. **获取新的序列**：交换后的先序、中序、后序序列与原始树类似，只需要考虑访问顺序的变化。

def print_sequences(root):
    sequences = {'preorder': [], 'inorder': [], 'postorder': []}
    helper(root, sequences)
    return sequences

def helper(node, sequences):
    if node is not None:
        helper(node.left, sequences)
        sequences['preorder'].append(node.data)
        helper(node.right, sequences)
        sequences['inorder'].insert(sequences['inorder'].index(node.data), node.data)
        sequences['postorder'].reverse()
        sequences['postorder'].append(node.data)

new_sequences = print_sequences(swap_subtrees(root))