用python 设计一个算法,输出二叉树的先序序列、中序序列、后序序列
时间: 2023-12-08 07:54:25 浏览: 72
数据结构实验代码先序+中序序列构造树.rar
二叉树的先序、中序、后序遍历是常见的树的遍历方法,下面是使用 python 实现的算法:
```python
# 定义二叉树结构体
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 先序遍历
def preOrder(root):
if not root:
return []
res = []
res.append(root.val)
res = res + preOrder(root.left)
res = res + preOrder(root.right)
return res
# 中序遍历
def inOrder(root):
if not root:
return []
res = []
res = res + inOrder(root.left)
res.append(root.val)
res = res + inOrder(root.right)
return res
# 后序遍历
def postOrder(root):
if not root:
return []
res = []
res = res + postOrder(root.left)
res = res + postOrder(root.right)
res.append(root.val)
return res
```
使用方法如下:
```python
# 构建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 输出遍历结果
print("先序遍历结果:", preOrder(root))
print("中序遍历结果:", inOrder(root))
print("后序遍历结果:", postOrder(root))
```
输出结果如下:
```
先序遍历结果: [1, 2, 4, 5, 3]
中序遍历结果: [4, 2, 5, 1, 3]
后序遍历结果: [4, 5, 2, 3, 1]
```
阅读全文