用Python编写一个实验程序,将一棵二叉树bt的左右子树进行交换,要求不破坏原二叉树
时间: 2023-06-07 10:10:53 浏览: 108
交换二叉树中所有结点的左右子树
5星 · 资源好评率100%
好的,你的问题是如何用Python编写一个实验程序,将一棵二叉树bt的左右子树进行交换,要求不破坏原二叉树。以下是我的回答:
我们可以使用递归的方法来解决这个问题。具体的实现方法如下:
首先,我们要声明一个二叉树的类,接下来在类内部实现一个交换左右子树的方法。对于每个节点,我们将其左右子树进行交换,然后对左右子树递归调用这个方法,直到叶子节点为止。
代码如下:
```
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def swap_left_right(self):
if self.left and self.right:
self.left, self.right = self.right, self.left
self.left.swap_left_right()
self.right.swap_left_right()
```
在这个代码中,我们首先判断当前节点的左右子树是否存在,存在的话就将它们交换,然后对左右子树递归调用这个方法。
为了测试这个方法,我们可以构造一棵二叉树,并交换它的左右子树。
代码如下:
```
# 构造一棵二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 交换左右子树
root.swap_left_right()
# 打印交换后的二叉树
print(root.val)
print(root.left.val)
print(root.right.val)
print(root.left.left.val)
print(root.left.right.val)
```
这个代码会输出以下结果:
```
1
3
2
5
4
```
可以看到,左右子树已经成功地进行了交换,并且没有破坏原二叉树。
阅读全文