이진 트리의 순회(Traversal)
- 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산합니다.
- 순회 종류는 4가지가 있습니다.
- 전위 순회(Preorder Traversal)
- 중위 순회(Inorder Traversal)
- 후위 순회(Postorder Traversal)
- 레벨 순회(Level Traversal)
DFS(Depth-First Search) or Depth-First Traversal : 다음 하위 항목으로 이동하기 전에 하위 항목의 모든 하위 항목을 처리합니다.
- 스택(Stack)이 사용됩니다.
전위 순회(Preorder Traversal)
- 방문 순서 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
위 그림의 방문 순서 : A->B->C->D->E->F
중위 순회(Inorder Traversal)
- 방문 순서 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
위 그림의 방문 순서 : C-> B -> D -> A -> E -> F
후위 순회(Postorder Traversal)
방문 순서 : 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
BFS(Breadth-First Search) or Breadth-First Traversal : 각 레벨은 다음 레벨이 시작되기 전에 완전히 처리됩니다.
- 큐(Queue)가 사용됩니다.
레벨 순회(Level Traversal)
방문 순서 : 위쪽 레벨 부터 왼쪽 노드 -> 오른쪽 노드
이진 트리 구현
배열(Array)을 이용한 구현
- 레벨 순회 순으로 배열에 구성합니다.
연결 리스트(Linked List)을 이용한 구현
- 값과 간선을 관리하기 위한 노드로 연결리스트에 구성합니다.
참조하면 좋은 내용
https://iq.opengenus.org/perfect-binary-tree/
References
- Chapter 6. Introduction to Trees, Data Structures: A Pseudocode Approach with C, Second Edition, Richard F. Gilberg Behrouz A. Forouzan.
'Computer Science > Data Structure' 카테고리의 다른 글
| 이진 트리(Binary Tree) (0) | 2023.05.01 |
|---|---|
| 트리(Tree) (2) | 2023.05.01 |
| 힙(Heap) (0) | 2023.04.18 |
| 연결 리스트(Linked List) (0) | 2023.04.18 |
| 해시 테이블(Hash Table) (0) | 2023.04.14 |