如何算出python二叉树的前序遍历和中序遍历
前序遍历和中序遍历是二叉树遍历的两种常见方式。在Python中,可以使用递归来实现二叉树的前序遍历和中序遍历。
## 前序遍历 (Preorder Traversal)
前序遍历定义为:首先访问根节点,然后递归地前序遍历左子树,最后递归地前序遍历右子树。
### 1. 定义节点类
首先,我们定义一个节点类来表示二叉树的节点:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
```
### 2. 实现前序遍历函数
实现前序遍历函数,可以按照前序遍历的定义,先访问根节点,然后递归地前序遍历左子树和右子树:
```python
def preorder_traversal(root):
if root:
print(root.data) # 1. 访问根节点的值
preorder_traversal(root.left) # 2. 递归前序遍历左子树
preorder_traversal(root.right) # 3. 递归前序遍历右子树
```
### 3. 示例代码
下面是一个示例代码,演示了如何构建一个二叉树,并进行前序遍历:
```python
# 构建二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# 前序遍历
print("前序遍历:")
preorder_traversal(root)
```
输出结果:
```
前序遍历:
1
2
4
5
3
```
## 中序遍历 (Inorder Traversal)
中序遍历定义为:先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。
### 1. 实现中序遍历函数
实现中序遍历函数,可以按照中序遍历的定义,先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树:
```python
def inorder_traversal(root):
if root:
inorder_traversal(root.left) # 1. 递归中序遍历左子树
print(root.data) # 2. 访问根节点的值
inorder_traversal(root.right) # 3. 递归中序遍历右子树
```
### 2. 示例代码
下面是一个示例代码,演示了如何构建一个二叉树,并进行中序遍历:
```python
# 构建二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# 中序遍历
print("中序遍历:")
inorder_traversal(root)
```
输出结果:
```
中序遍历:
4
2
5
1
3
```
以上就是Python中实现二叉树的前序遍历和中序遍历的方法。通过递归,我们可以按照定义遍历二叉树的各个节点。希望这个解答对您有帮助!
猜您想看
-
树莓派上如何使用LCD1602显示基本状态
使用LCD16...
2023年07月04日 -
分库分表和NewSQL数据库的原理对比是什么
分库分表和Ne...
2023年07月22日 -
Spark的failover容错机制是什么
1. 什么是S...
2023年05月25日 -
如何在 CentOS 7 上配置 SSH 证书登录?
CentOS ...
2023年04月24日 -
使用PHP实现Web爬虫的技巧
随着网络技术的...
2023年05月14日 -
Disruptor的原理是什么
Disrupt...
2023年07月23日