Tree Traversal   트리 순회

1.  트리 순회 (Tree Traversal)

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


2. 트리 순회의 특징

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


3. 트리 순회의 종류

  ㅇ 전위 순회 (Preorder Traversal)
  ㅇ 중위 순회 (Inorder Traversal)
  ㅇ 후위 순회 (Postorder Traversal)
  ㅇ 레벨 순회 (Level Traversal)


4. 전위 순회 (Preorder Traversal)

  ㅇ 순회 방식
     - 루트 노드를 시작으로, 
     - 왼쪽 서브 트리를 먼저 순회하고,
     - 오른쪽 서브 트리를 그다음 순회
     * 부모(루트)가 제일 먼저 방문됨
     * 깊이 우선, 전위 순회 (Depth First, Preorder Traversal) 라고도 함
       

  ㅇ 알고리즘 구현 例) (C 언어, 재귀적 구현)
      
void preorder(struct BinaryTreeNode *parent) {
    if(parent) {
        printf("%d ", parent->value);
        preorder(parent->leftChild);
        preorder(parent->rightChild);
    }
}


5. 중위 순회 (Inorder Traversal)

  ㅇ 순회 방식
     - 제일 왼쪽 최하위 노드를 시작으로,
     - 왼쪽 서브 트리를 먼저 순회하고
     - 부모(루트)를 거쳐,
     - 오른쪽 서브 트리들을 차례대로 순회
     * 부모(루트)가 서브트리 방문 중간(사이)에 방문됨
       


6. 후위 순회 (Postorder Traversal)

  ㅇ 순회 방식
     - 제일 왼쪽 최하위 노드를 시작으로,
     - 왼쪽 서브 트리를 먼저 순회하고,
     - 오른쪽 서브 트리들을 차례대로 순회하고,
     - 부모(루트)를 순회
     * 부모(루트)가 양쪽 서브트리 후에 방문됨
       


7. 레벨 순회 방식 (너비 우선 순회 방식)

  ㅇ 순회 방식 
     - 루트 노드를 시작으로,
     - 현재 깊이의 모든 노드를 순회하고,
     - 그 다음 깊이의 모든 노드들을 순회
     * 형제 노드 방문 위주
        

  ㅇ 특징
     - 큐 자료구조를 사용