[정처기 2과목] 자료구조 트리구조 순회

2024. 5. 2. 15:26기타/정처기

이진 나무 순회(Tree Traverse)
# 이진 트리 예시
#      1
#    /   \
#   2     3
#  / \   / \
# 4   5 6   7

 

 

  • 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
    • 전위 순회: 뿌리 -> 왼쪽 자식 -> 오른쪽 자식
    • 1 - 2- 4 - 5 - 3 - 6 - 7
  • 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
    • 중위 순회: 왼쪽자식 -> 뿌리 -> 오른쪽 자식
    • 4 - 2 - 5 - 1 - 6 - 3 - 7
  • 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문
    • 후위 순회: 왼쪽자식 -> 오른쪽 자식 -> 뿌리
    • 4 - 5 - 2 - 6 - 7 - 3 -1
  • 층별 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문
    • 층별 순회: 노드 순서대로 위부터 왼쪽부터
    • 1 - 2 - 3 - 4 - 5 - 6 - 7