트리(Tree)의 순회 (전위/중위/후위 순회)

2023. 8. 10. 10:28·CS 공부/자료구조

트리의 순회

 

트리의 순회는 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회가 있다. 

※ 여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉, 왼쪽 서브 트리, 노드 방문, 오른쪽 서브 트리를 의미한다. 

 

 

 

중위 순회(inorder traversal)

 

중위 순회는 LVR 탐색이 이루어진다. 즉, 왼쪽 서브 트리-루트 노드-오른쪽 서브 트리 탐색이 재귀적으로 이루어진다.

 

 

 

가장 먼저 루트 노드를 기준으로 왼쪽 서브 트리로의 탐색이 시작된다. 즉, 왼쪽 서브 트리에서 또다시 중위 순회가 재귀적으로 이루어진다. 

 

 

 

B노드가 루트 노드인 것처럼 되고, 왼쪽 서브 트리인 A노드로의 중위 탐색이 진행된다. 이후 A노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다. 

 

출력 : A

 

B가 루트 노드인 것처럼 될 때 , 왼쪽 서브 트리의 탐색을 마쳤으니, 루트 노드인 B의 방문(Visit)이 진행된다.

 

출력 : A B

 

이후 B의 오른쪽 서브 트리로의 중위 탐색이 다시 진행된다. 이때는 D노드가 마치 루트 노드인 것처럼 된다.

 

 

D가 루트 노드일 때, 왼쪽 서브 트리인 C노드로의 중위 탐색이 진행된다. 이후 C노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다. 

 

출력 : A B C

 

 

이후 루트 노드인 D노드를 방문하게 된다.

 

출력 : A B C D

 

 

D 노드가 루트 노드 일 때 , 오른쪽 서브 트리인 E노드로의 중위 탐색이 진행되고, 왼쪽 서브 트리가 없으므로 바로 E노드를 방문한다.

 

출력 : A B C D E

 

 

F 노드가 루트 노드일 때 왼쪽 서브 트리의 탐색이 모두 완료되었으니, 루트 노드인 F를 방문한다.

 

출력 : A B C D E F

 

 

이후 오른쪽 서브 트리에서 중위 탐색이 진행된다. 이때 G노드가 루트 노드처럼 된다. G노드가 루트노드 일 때, 왼쪽 서브 트리가 없으므로 루트 노드인 G노드를 방문한다.

출력 : A B C D E F G

 

이후 오른쪽 서브 트리로 다시 중위 탐색이 진행된다. 이때 I 노드가 루트 노드인 것처럼 된다.

왼쪽 서브 트리인 H노드로의 중위 탐색이 진행되고 왼쪽 서브 트리가 없으므로 H노드를 방문하게 된다.

출력 : A B C D E F G H

 

이후 루트 노드인 I노드의 방문이 진행되고 오른쪽 서브 트리가 없으므로 탐색이 종료된다.

출력 : A B C D E F G H I

 

 

 

중위 순회(inorder traversal)

 

전위 순회는 VLR 탐색이 이루어진다. 즉, 루트 노드-왼쪽 서브 트리-오른쪽 서브 트리 순으로 탐색이 재귀적으로 진행된다.

 

1. 루트 노드인 F를 방문

2. F의 왼쪽 서브 트리의 루트 노드 B 방문

3. B의 왼쪽 서브 트리의 루트 노드 A 방문

4. B의 오른쪽 서브 트리의 루트 노드 D 방문

5. D의 왼쪽 서브 트리의 루트 노드 C 방문

6. D의 오른쪽 서브 트리의 루트 노드 E 방문

7. F의 오른쪽 서브 트리의 루트 노드 G 방문

8. G의 오른쪽 서브 트리의 루트 노드 I 방문

9. I의 왼쪽 서브 트리의 루트 노드 H 방문

 

출력 : F B A D C E G I H

 

 

 

후위 순회(Postorder Traversal)

 

후위 순회는 LRV 탐색이 이루어진다. 즉 왼쪽 서브 트리-오른쪽 서브 트리-루트 노드 순으로 탐색이 재귀적으로 진행된다.

 

 

 

1. F의 왼쪽 서브트리 탐색

2. B의 왼쪽 서브트리 탐색

3. A노드 방문

4. B의 오른쪽 서브트리 탐색

5. D의 왼쪽 서브트리 탐색

6. C노드 방문

7. D의 오른쪽 서브트리 탐색

8. E노드 방문

9. D노드 방문

10. B노드 방문

11. F의 오른쪽 서브트리 탐색

12. G의 오른쪽 서브트리 탐색

13. I의 왼쪽 서브트리 탐색

14. H노드 방문

15. I노드 방문

16. G노드 방문

17. F노드 방문

 

출력 : A C E D B H I G F

 

 

 

'CS 공부 > 자료구조' 카테고리의 다른 글

AVL 트리 - 성질/삽입방법/활용  (0) 2023.08.10
이진 탐색 트리 (BST-Binary Search Tree)  (0) 2023.08.10
여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리)  (0) 2023.08.09
힙(Heap)이란?  (0) 2023.08.09
원형큐(Circular Queue)란?  (0) 2023.08.07
'CS 공부/자료구조' 카테고리의 다른 글
  • AVL 트리 - 성질/삽입방법/활용
  • 이진 탐색 트리 (BST-Binary Search Tree)
  • 여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리)
  • 힙(Heap)이란?
횰쓰
횰쓰
개발 성장 블로그입니다
  • 횰쓰
    횰쓰토리
    횰쓰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • CS 공부
        • 운영체제
        • 네트워크
        • 컴퓨터구조
        • 데이터베이스
        • 알고리즘
        • 소프트웨어공학
        • 자료구조
        • 웹
      • 프로그래밍
        • Python
        • NodeJS
      • 개발도구
        • Git
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    멀티 스레드
    스택
    둘만의 암호
    AVL트리
    SQL/NOSQL
    tcp
    프로세스 주소공간
    RB트리
    포화이진트리
    4 way handshake
    경쟁상태(Race Condition)
    Max힙
    Min힙
    최태성인강
    Push-force
    Git
    전이진트리
    운영체제
    멀티 프로세스
    큐
    RB Tree
    페이지 교체
    이진탐색트리
    chrome
    카드뭉치
    한국사능력검정시험 심화
    자가균형 이진탐색트리
    3 Way Handshake
    Sync/Async
    리스트정렬여부
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
횰쓰
트리(Tree)의 순회 (전위/중위/후위 순회)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.