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

在二叉链表中实现二叉树，首先我们需要创建一个节点结构，包含数据域、指向前一个节点的指针以及指向下一个节点的指针。下面是基本步骤： 1. **构建二叉树**：从层序序列开始，每一层代表树的一个层次，可以使用队列辅助操作。遍历序列，每次取出一个元素作为根节点，然后将其左右子节点（如果有）分别加入队列对应的位置。 ```python 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. **交换左右子树**：对每个节点，临时保存其原左子节点和右子节点，然后更新左右子节点。 ```python 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. **获取新的序列**：交换后的先序、中序、后序序列与原始树类似，只需要考虑访问顺序的变化。 ```python 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)) ```