如何算出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中实现二叉树的前序遍历和中序遍历的方法。通过递归,我们可以按照定义遍历二叉树的各个节点。希望这个解答对您有帮助!
猜您想看
-
使用 pyppeteer碰到的错误怎么解决
如何解决pyp...
2023年07月04日 -
Node.js如何实现桌面应用
一、Node....
2023年05月25日 -
Python3.9有哪些新特性
新特性一:标准...
2023年07月20日 -
LeetCode中怎么拆分数组
拆分数组是在给...
2023年07月20日 -
如何在Edge浏览器中使用"播放列表"功能
如何在Micr...
2023年05月13日 -
Ubuntu下mongodb的安装方法
前言Mongo...
2023年07月22日