Tree Traversal   트리 순회

(2021-04-04)

트리 탐색, 전위 순회, 중위 순회, 후위 순회

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. B 트리 9. 10. 멀티캐스트 트리 11. 결정 트리

 
        최근수정     요약목록     참고문헌