如何算出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中实现二叉树的前序遍历和中序遍历的方法。通过递归,我们可以按照定义遍历二叉树的各个节点。希望这个解答对您有帮助!
猜您想看
-
如何使用iKuai软路由进行端口转发
使用iK...
2023年04月17日 -
Java程序启动脚本startup.sh怎么编写
一、编写Jav...
2023年07月22日 -
AopContext.currentProxy()如何解决cache不生效问题
问题描述在使用...
2023年07月20日 -
如何让 Siri 识别我的快捷指令?
如何让Siri...
2023年04月17日 -
C++11标准库mem_fn类模板怎么使用
1. 什么是m...
2023年05月26日 -
Windows XP 如何进行语言和输入法设置
如何在 Win...
2023年04月15日