Tree Traversal   트리 순회

(2021-07-26)

트리 탐색, Pre-order Traversal, 전위 순회, In-order Traversal, 중위 순회, Post-order Traversal, 후위 순회


1.  트리 순회 (Tree Traversal)

  ㅇ 모든 정점을 한번씩 만 방문하거나, 목표 정점을 찾아가는 방법

  ㅇ 트리 순회의 특징
     - 그래프 순회의 일종
     - 각 노드의 하부들을 각각 독립된 서브 트리(subtree,부분 트리)로써 순회
        . 재귀적(순환적)인 방법으로 서브 트리를 정의하며 순회할 수 있음

  ㅇ 트리 순회의 종류
     - 전위 순회 (Preorder Traversal)
     - 중위 순회 (Inorder Traversal)
     - 후위 순회 (Postorder Traversal)
     - 레벨 순회 (Level Traversal)


2. 전위 순회 (Preorder Traversal)

  ㅇ 순회 방식
     - 루트 노드를 시작으로, 
     - 왼쪽 서브 트리를 먼저 순회하고,
     - 오른쪽 서브 트리를 그다음 순회
     * 부모(루트)가 제일 먼저 방문됨
     * 깊이 우선, 전위 순회 (Depth First, Preorder Traversal) 라고도 함
       알고리즘 구현 例) (C 언어, 재귀적 구현)
      
void preorder(struct BinaryTreeNode *parent) {
    if(parent) {
        printf("%d ", parent->value);
        preorder(parent->leftChild);
        preorder(parent->rightChild);
    }
}
3. 중위 순회 (Inorder Traversal) ㅇ 순회 방식 - 제일 왼쪽 최하위 노드를 시작으로, - 왼쪽 서브 트리를 먼저 순회하고 - 부모(루트)를 거쳐, - 오른쪽 서브 트리들을 차례대로 순회 * 부모(루트)가 서브트리 방문 중간(사이)에 방문됨 4. 후위 순회 (Postorder Traversal) ㅇ 순회 방식 - 제일 왼쪽 최하위 노드를 시작으로, - 왼쪽 서브 트리를 먼저 순회하고, - 오른쪽 서브 트리들을 차례대로 순회하고, - 부모(루트)를 순회 * 부모(루트)가 양쪽 서브트리 후에 방문됨 5. 레벨 순회 방식 (너비 우선 순회 방식) ㅇ 순회 방식 - 루트 노드를 시작으로, - 현재 깊이의 모든 노드를 순회하고, - 그 다음 깊이의 모든 노드들을 순회 * 형제 노드 방문 위주 ㅇ 특징 - 자료구조를 사용

트리
   1. 트리   2. 트리 용어   3. 트리 종류   4. 트리 순회   5. 스패닝 트리   6. 이진 트리   7. 이진 트리 종류   8. 이진 탐색 트리   9. B 트리 (균형 트리)   10. 이진 힙   11. 멀티캐스트 트리   12. 결정 트리  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"