设计递归算法分别对该二叉树做先序、中序、后序遍历,要求输出这三种遍历序列的实验思路
时间: 2024-06-11 14:05:38 浏览: 9
实验思路:
1. 先序遍历:以根节点为起点,先访问根节点,再递归访问左子树和右子树。因此,递归算法的实现步骤如下:
- 如果当前节点为空,返回。
- 访问当前节点。
- 递归遍历左子树。
- 递归遍历右子树。
2. 中序遍历:以根节点为起点,先递归访问左子树,再访问根节点,最后递归访问右子树。因此,递归算法的实现步骤如下:
- 如果当前节点为空,返回。
- 递归遍历左子树。
- 访问当前节点。
- 递归遍历右子树。
3. 后序遍历:以根节点为起点,先递归访问左子树,再递归访问右子树,最后访问根节点。因此,递归算法的实现步骤如下:
- 如果当前节点为空,返回。
- 递归遍历左子树。
- 递归遍历右子树。
- 访问当前节点。
递归算法实现时,可以使用递归函数来实现遍历,具体实现代码如下:
```python
# 先序遍历
def pre_order(root):
if root is None:
return
print(root.val)
pre_order(root.left)
pre_order(root.right)
# 中序遍历
def in_order(root):
if root is None:
return
in_order(root.left)
print(root.val)
in_order(root.right)
# 后序遍历
def post_order(root):
if root is None:
return
post_order(root.left)
post_order(root.right)
print(root.val)
```
其中,root表示当前节点,root.left表示左子树,root.right表示右子树。在访问节点时,输出节点的值即可。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)