02.遍历树
# 01.树的遍历
# 1.1 生成树结构
- 1.前序遍历: DBACEGF(根节点排最先,然后同级先左后右)
- 2.中序遍历: ABCDEFG (先左后根最后右)
- 3.后序遍历: ACBFGED (先左后右最后根)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 1.2 先根遍历
- 前序遍历: DBACEGF(根节点排最先,然后同级先左后右)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def preTraverse(root):
'''
前序遍历
'''
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('前序遍历:')
preTraverse(root) # DBACEGF
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
先根遍历步骤推演
前序排列原理:
#####此时执行preTraverse(root.left) 函数
'''
1、第一步 root=Node(D) print D,D入栈[D]
2、第二步 root=Node(D).left=Node(B) print B, B入栈[D,B]
3、第三步 root=Node(B).left=Node(A) print A, A入栈[D,B,A]
4、第四步 root=Node(A).left=None,没有进入递归,顺序执行preTraverse(root.right)
5、第五步 Node(A).right==None,也没有进入递归,此时preTraverse(A) 函数才会正真返回,A出栈[D,B]
6、第六步 A的上级调用函数为:preTraverse(B.left),所以接着会顺序执行preTraverse(B.right),B的左右节点访问后B出栈[D]
7、第七步 Node(B).right==Node(C) print C,C入栈[D,C]
8、第八步 Node(C).left==None, Node(C).right==None,访问完C的左右节点后函数返回C出栈,返回上级调用[D]
9、第九步 此时返回上级调用执行preTraverse(D.right)=Node(E) print E,D出栈,E入栈[E]
'''
'''此时输出结果:DBACE'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 1.3 中根遍历
- ABCDEFG (先左后根最后右)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def midTraverse(root):
'''
中序遍历
'''
if root == None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('中序遍历:')
midTraverse(root) # ABCDEFG (先左后根最后右)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 1.4 后根遍历
- 后序遍历: ACBFGED (先左后右最后根)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def afterTraverse(root):
'''
后序遍历
'''
if root == None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('后序遍历:')
afterTraverse(root) # ACBFGED
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 1.5 分层打印二叉树
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
def layer(root):
curLayer = [root] # 当前层的节点
while curLayer: # 只要当前层有节点就循环
layerValue = [] # 当前层节点对应的值
nextLayer = [] # 下一层节点
for node in curLayer: # 循环当前节点
layerValue.append(node.value) # 添加当前层节点的值
if node.left:
nextLayer.append(node.left) # 添加下一层节点左节点
if node.right:
nextLayer.append(node.right) # 添加下一层节点右节点
print(layerValue) # 打印当前层的值
curLayer = nextLayer # 移动到下一层
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
layer(root)
'''
['D']
['B', 'E']
['A', 'C', 'G']
['F']
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 02.广度优先
- D B E A C G F
# 2.1 栈实现BFS
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
# 广度优先搜索
def bfs(root):
res = []
q = [root] # 先把根节点放进队列中
while q: # 当队列不为空时进入循环体
current_node = q.pop(0) # 取出队列的第一个节点
print(current_node.value)
if current_node.left: # 如果左子树不为空,就加入队列
q.append(current_node.left)
if current_node.right: # 如果右子树不为空,就加入队列
q.append(current_node.right)
return res
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
bfs(root) # D B E A C G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 2.2 分层思想
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
def bfs(root):
curLayer = [root] # 当前层的节点
while curLayer: # 只要当前层有节点就循环
nextLayer = [] # 下一层节点
for node in curLayer: # 循环当前节点
print(node.value)
if node.left:
nextLayer.append(node.left) # 添加下一层节点左节点
if node.right:
nextLayer.append(node.right) # 添加下一层节点右节点
curLayer = nextLayer # 移动到下一层
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
bfs(root) # D B E A C G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 03.深度优先
- D B A C E G F
# 3.1 栈实现DFS
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
# 深度优先搜索
def dfs(root):
res = []
q = [root] # 先把根节点放进栈中
while q: # 当栈不为空时进入循环体
current_node = q.pop() # 取出栈顶节点
print(current_node.value)
if current_node.right: # 如果右子树不为空,就压入栈
q.append(current_node.right)
if current_node.left: # 如果左子树不为空,就压入栈
q.append(current_node.left)
return res
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
dfs(root) # D B A C E G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 3.2 递归实现DFS
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
# 深度优先搜索
# 使用递归实现深度优先搜索
def dfs_recur(node):
if not node: # 递归结束的条件是当该节点为None时
return
print(node.value)
dfs_recur(node.left) # 对左子树进行递归
dfs_recur(node.right) # 对右子树进行递归
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
dfs_recur(root) # D B A C E G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10