순회
트리의 모든 노드를 중복 없이 모두 방문하기
예시 트리
전위순회
루트 -> 왼쪽 노드 -> 오른쪽 노드 순서
예) 위 트리를 전위순회로 탐방하면
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
중위순회
왼쪽 노드 -> 루트 -> 오른쪽 노드 순서
예) 위 트리를 중위순회로 탐방하면
4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
- 스택을 이용한 중위순회 구현
스택의 특성을 이용해 중위순회를 구현할 수 있다.- 리프노드까지 스택에 노드를 넣으면 왼쪽으로 탐색
- 스택에서 노드를 뺄 때 오른쪽 자식 노드 탐색
예) 위의 트리에서 스택 S로 중위순회를 한다 하면
S = {1, 2, 4}로 넣어놓고,
4를 pop하고 4는 리프노드이므로 오른쪽 자식 없음, S = {1, 2}
2를 pop하고 2의 오른쪽 자식 5를 스택에 집어넣음 S = {1, 5}
5를 pop하고 5는 리프노드이므로 오른쪽 자식 없음, S = {1}
1을 pop하고 2의 오른쪽 자식 3을 스택에 집어넣음 S = {3}
3의 왼쪽 자식 6을 집어넣음 S = {3, 6}
6을 pop하고 6은 리프노드이므로 오른쪽 자식 없음, S = {3}
3을 pop하고 5는 오른쪽 자식 7을 스택에 집어넣음, S = {7}
7을 pop하고 7은 리프노드이므로 오른쪽 자식 없음, S = {}
스택이 비었으므로 탐색 종료
pop한 것을 순서대로 나열하면
4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
후위순회
왼쪽 노드 -> 오른쪽 노드 -> 루트 순서
예) 위 트리를 후위순회로 탐방하면
4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
(루트 노드가 제일 마지막!)
레벨순회
레벨이 작은 순, 왼쪽 순으로 이동
예) 위 트리를 레벨순회로 탐방하면
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
- 큐를 이용한 레벨순회 구현
큐의 특성을 이용해 레벨순회를 구현할 수 있다.- dequeue하는 노드의 왼쪽자식, 오른쪽 자식 순으로 큐에 넣는다
예)위의 트리에서 큐 Q로 레벨순회를 한다 하면
Q = {1}로 넣어두고
1을 dequeue하고 자식노드 2, 3 enqueue Q = {2, 3}
2를 dequeue하고 자식노드 4, 5 enqueue Q = {3, 4, 5}
3을 dequeue하고 자식노드 6, 7 enqueue Q = {4, 5, 6, 7}
4를 dequeue하고 4는 리프노드이므로 Q = {5, 6, 7}
5를 dequeue하고 5는 리프노드이므로 Q = {6, 7}
6을 dequeue하고 6은 리프노드이므로 Q = {7}
7을 dequeue하고 7은 리프노드이므로 Q = {}
큐가 비었으므로 탐색 종료
dequeue한 것을 순서대로 나열하면
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
- dequeue하는 노드의 왼쪽자식, 오른쪽 자식 순으로 큐에 넣는다
728x90
반응형
'CS > 자료구조' 카테고리의 다른 글
[자료구조](13)[이진트리의 구현 2] (0) | 2025.05.07 |
---|---|
[자료구조](12)[이진트리의 구현 1] (0) | 2025.05.06 |
[자료구조](10)[이진탐색트리] (0) | 2025.04.23 |
[자료구조](9)[트리&이진트리] (0) | 2025.04.22 |
[자료구조](8)[정렬 알고리즘 2] (0) | 2025.04.14 |