设计递归算法分别对该二叉树做先序、中序、后序遍历,要求输出这三种遍历序列
时间: 2024-02-01 15:02:48 浏览: 80
二叉树的基本运算
假设二叉树的节点类为Node,含有三个成员变量:值(value),左子节点(left),右子节点(right)。
先序遍历:
1. 访问当前节点。
2. 递归遍历左子树。
3. 递归遍历右子树。
递归代码实现:
```python
def preorder_traversal(root):
if root is None:
return []
result = [root.value]
result += preorder_traversal(root.left)
result += preorder_traversal(root.right)
return result
```
中序遍历:
1. 递归遍历左子树。
2. 访问当前节点。
3. 递归遍历右子树。
递归代码实现:
```python
def inorder_traversal(root):
if root is None:
return []
result = inorder_traversal(root.left)
result.append(root.value)
result += inorder_traversal(root.right)
return result
```
后序遍历:
1. 递归遍历左子树。
2. 递归遍历右子树。
3. 访问当前节点。
递归代码实现:
```python
def postorder_traversal(root):
if root is None:
return []
result = postorder_traversal(root.left)
result += postorder_traversal(root.right)
result.append(root.value)
return result
```
以上三个函数均返回一个列表,列表中的元素为遍历结果。
阅读全文