二叉树的操作 对二叉树,完成下列操作: 二叉树的复制 二叉树的比较 二叉树的镜像(左右子树互换位置) 提供菜单选择。写个代码
时间: 2024-08-13 13:07:42 浏览: 30
二叉树是一种常见的数据结构,用于表示具有递归层次关系的数据。在许多编程任务中,我们可能需要对二叉树执行各种操作,如复制、比较和镜像。下面是这些操作的简单概述:
1. **二叉树复制**:
- 对于每个节点,创建一个新的节点,将原始节点的值复制到新节点。
- 新节点的左子树复制原节点的左子树,右子树复制原节点的右子树。
- 使用递归方法遍历原始树。
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def clone_tree(root):
if root is None:
return None
else:
return TreeNode(root.val, clone_tree(root.left), clone_tree(root.right))
```
2. **二叉树比较**:
- 如果两个树的根节点值相同,然后递归地比较它们的左子树和右子树。
- 如果任意一棵树的左右子树与另一棵不相等或其中一个为空,返回 False;否则返回 True。
```python
def isSameTree(p, q):
if p is None and q is None:
return True
elif (p is not None and q is None) or (p is None and q is not None):
return False
else:
return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
```
3. **二叉树镜像(左右子树互换位置)**:
- 交换当前节点的左右子节点。
```python
def invertTree(root):
if root:
root.left, root.right = root.right, root.left
invertTree(root.left)
invertTree(root.right)
```
为了提供菜单选择,你可以使用一个简单的命令行交互或者 GUI 程序。用户可以选择一个操作并输入相应参数。例如,你可以这样设计:
```python
def menu():
while True:
print("1. 复制二叉树")
print("2. 比较二叉树")
print("3. 镜像二叉树")
choice = input("请选择操作 (1-3): ")
if choice in ['1', '2', '3']:
# 根据用户输入调用对应函数
break
menu()
```
然后在 `menu` 函数内部调用相应的函数处理用户输入。记得先定义好 `TreeNode` 类。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)