알고리즘/트리
트리 순회
jwjwvison
2022. 5. 10. 17:38
트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다.
그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데, 특히 이진트리에서 DFS는 노드의 방문 순서에 따라 다음과 같이 크게 3가지 방식으로 구분된다.
1. 전위 순회(preorder) - NLR
2. 중위 순회(inorder) - LNR
3. 후위 순회(post-order) - LRN
L = 현재 노드의 왼쪽 서브트리
R = 현재 노드의 오른쪽 서브트리
N = 현재 노드 자신
class Node:
def __init__(self,val,left=None,right=None):
self.val=val
self.left=left
self.right=right
root=Node('F',Node('B',Node('A'),Node('D',Node('C'),Node('E'))),
Node('G',None,Node('I',Node('H')))
)
def preorder(node): # 전위순회
if node is None:
return
print(node.val,end=' ')
preorder(node.left)
preorder(node.right)
preorder(root)
print('\n')
def inorder(node): # 중위 순회
if node is None:
return
inorder(node.left)
print(node.val,end=' ')
inorder(node.right)
inorder(root)
print('\n')
def postorder(node): # 후위 순회
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.val,end=' ')
postorder(root)
print('\n')