python二叉树的创建与遍历
时间: 2024-09-28 09:15:40 浏览: 26
在Python中,我们可以使用类来创建二叉树结构。二叉树是一种每个节点最多有两个子节点的数据结构,通常分为左子节点和右子节点。以下是创建二叉树的基本步骤和常见的遍历方法:
**创建二叉树**
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# 创建一个二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
```
这里我们定义了一个Node类,每个节点包含值、左子节点和右子节点。
**二叉树遍历**
1. **前序遍历(Preorder Traversal)**: 先访问根节点,然后递归地遍历左子树和右子树。
```python
def preorder_traversal(node):
if node is not None:
print(node.value)
preorder_traversal(node.left)
preorder_traversal(node.right)
```
2. **中序遍历(Inorder Traversal)**: 先递归地遍历左子树,然后访问根节点,最后遍历右子树。
```python
def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.value)
inorder_traversal(node.right)
```
3. **后序遍历(Postorder Traversal)**: 先递归地遍历左子树和右子树,最后访问根节点。
```python
def postorder_traversal(node):
if node is not None:
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.value)
```