[개념 정리] 트리 순회

트리 순회가 뭘까요?

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

트리 순회

트리 순회는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정입니다.

순회 방식에는 깊이 우선 순회와 너비 우선 순회가 있고, 깊이 우선 순회는 전위 순회, 중위 순회, 후위 순회로 나뉩니다. 

 

깊이 우선 순회

• 전위 순회 : 부모노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
• 중위 순회 :  왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드
• 후위 순회 : 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드

 

예시 그림을 통해서 전위, 중위, 후위 순회, 레벨 순회의 순서를 알아보겠습니다.

전위 순회 : A  → B  → C  → D  → E

중위 순회 : B  → A  → D  → C  → E

후위 순회 : B  → D → E → C → A

레벨 순회 : A → B → C → D → E

 

전위 순회, 중위 순회, 후위 순회의 수도 코드를 알아보겠습니다.

 

 

후위 순회

자식들 노드를 방문하고 자신의 노드를 방문합니다.

 

수도 코드

postorder( node )
       if(node.visited == false)
       postorder( node -> left)
       postorder( node -> right)
       node.visited = true

 

전위 순회

자기 자신의 노드를 방문하고 다음 노드들을 방문합니다.

DFS와 동일합니다.

 

수도 코드

preorder( node )
    if(node.visited == false)
        node.visited = true
        preorder( node -> left)
        preorder( node -> right)

 

중위 순회

왼쪽 자식 노드를 먼저 방문하고 자신의 노드를 방문하고 그 다음 오른쪽 노드를 방문합니다.

 

수도 코드

inorder(node)
     if (node.visited == false)
         inorder( node -> left)
         node.visited = true
         inorder( node -> right)

 

레벨 순회

 

레벨 순회는 BFS와 동일합니다.

 

 

전위 순회, 중위 순회, 후위 순회를 코드로 구현해보겠습니다.

 

 

코드 구현

코드는 이진 트리로 가정하고 구현했습니다.

 

전위 순회

private static void preOrder(int curNode, boolean[] visited) { // 나 - 왼쪽 자식 - 오른쪽 자식

    print(curNode);

    if(tree.get(curNode).isEmpty()) {
        return;
    }

    if(!visited[curNode]) {
        visited[curNode] = true; // 자기 자신
        preOrder(tree.get(curNode).get(0), visited); // 왼쪽 자식
        preOrder(tree.get(curNode).get(1), visited); // 오른쪽 자식
     }
 }

 

현재 노드를 먼저 방문 처리하고, 왼쪽 자식 노드, 오른쪽 자식 노드를 방문하도록 구현합니다.

 

출력 결과는 다음과 같습니다.

 

중위 순회

private static void inOrder(int curNode, boolean[] visited) { // 중위 순회

    if(tree.get(curNode).isEmpty()) {
        print(curNode);
        return;
    }

    if(!visited[curNode]) {
        inOrder(tree.get(curNode).get(0), visited);
        print(curNode);
        visited[curNode] = true;
        inOrder(tree.get(curNode).get(1), visited);
    }
}

 

왼쪽 자식 노드를 방문하고, 현재 노드를 방문처리 한후, 오른쪽 자식 노드를 방문하도록 구현합니다.

 

출력 결과는 다음과 같습니다.

 

후위 순회

private static void postOrder(int curNode, boolean[] visited) { // 후위 순회 왼(자) - 오(자) - 중

    if(tree.get(curNode).isEmpty()) {
        print(curNode);
        return;
    }

    if(!visited[curNode]) {
        postOrder(tree.get(curNode).get(0),visited);
        postOrder(tree.get(curNode).get(1),visited);
        visited[curNode] = true;
        print(curNode);
    }
}

 

왼쪽 자식 노드를 방문하고, 오른쪽 자식 노드를 방문한 후, 현재 노드를 방문합니다.

 

출력 결과는 다음과 같습니다.

 

 

정리

이미지 출처 : 큰돌의 터전  10주 완성 C++ 코딩테스트 알고리즘 개념 교안