### 如何用Python实现交换二叉树中的两个子树 在Python中，可以通过操作二叉树的节点指针来实现两个子树的交换。具体来说，我们需要找到两个子树的根节点，并调整它们与父节点之间的连接关系。以下是一个完整的实现方案： #### 方法描述 1. 定义一个二叉树节点类 `Node`，包含节点值和左右子树指针。 2. 创建一个二叉树类 `BiTree`，支持添加节点和查找节点的操作。 3. 编写一个函数 `swap_subtrees`，用于根据指定的节点值交换两个子树。 以下是代码实现： ```python class Node: """定义二叉树的节点""" def __init__(self, value): self.value = value self.left = None self.right = None class BiTree: """定义二叉树""" def __init__(self, root=None): self.root = root def add(self, value): """按层次遍历顺序添加节点""" node = Node(value) if self.root is None: self.root = node return temp_queue = [self.root] while temp_queue: cur_node = temp_queue.pop(0) if cur_node.left is None: cur_node.left = node return else: temp_queue.append(cur_node.left) if cur_node.right is None: cur_node.right = node return else: temp_queue.append(cur_node.right) def find_node(tree, value): """查找值为value的节点及其父节点""" if tree.root is None: return None, None queue = [(None, tree.root)] # (父节点, 当前节点) while queue: parent, current = queue.pop(0) if current.value == value: return parent, current if current.left: queue.append((current, current.left)) if current.right: queue.append((current, current.right)) return None, None def swap_subtrees(tree, value1, value2): """交换二叉树中以value1和value2为根的子树""" parent1, node1 = find_node(tree, value1) parent2, node2 = find_node(tree, value2) if node1 is None or node2 is None: print("无法找到指定的节点") return # 如果node1是根节点 if parent1 is None: tree.root, node2 = node2, tree.root else: if parent1.left == node1: parent1.left = node2 else: parent1.right = node2 # 如果node2是根节点 if parent2 is None: tree.root, node1 = node1, tree.root else: if parent2.left == node2: parent2.left = node1 else: parent2.right = node1 def inorder_traversal(node): """中序遍历打印二叉树""" if node is not None: inorder_traversal(node.left) print(node.value, end=" ") inorder_traversal(node.right) # 测试代码 if __name__ == "__main__": tree = BiTree() values = [1, 2, 3, 4, 5, 6, 7] for val in values: tree.add(val) print("原始二叉树中序遍历：") inorder_traversal(tree.root) print("\n交换子树后：") swap_subtrees(tree, 2, 3) # 交换以2和3为根的子树 inorder_traversal(tree.root) ``` #### 代码解释 1. **节点查找**：通过 `find_node` 函数找到指定值的节点及其父节点[^4]。 2. **子树交换**：在 `swap_subtrees` 函数中，调整父节点的左右子树指针，完成子树的交换[^4]。 3. **测试**：通过中序遍历验证交换结果。 #### 注意事项 - 如果要交换的节点之一是根节点，则需要特别处理根节点的替换逻辑。 - 确保输入的两个节点值都存在于二叉树中，否则会报错或无效果。 ###