[알고리즘 이론] 5. 트리순회

트리순회

• 트리순회는 이진트리에 속하는 모든 노드를 한 번씩 방문하여 모드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.
• 루트 : V, 왼쪽 서브 트리(트리 중 왼쪽 전체(루트 제외)) : L, 오른쪽 서브 트리(트리 중 오른쪽 전체(루트 제외)) : R
• 이진트리에서 각각의 서브 트리 역시 이진트리이다.
• 전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다. -> 순환(재귀) 적용

1. 전위순회 (Preordfer Traversal) : VLR

• 루트(V) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순서대로 방문하는 것이다.

2. 중위순회 (Inorder Traversal) : LVR

• 왼쪽 서브트리(L) -> 루트(V) -> 오른쪽 서브트리(R) 순서대로 방문하는 것이다.

3. 후위순회 (Postorder Traversal) : LRV

• 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) -> 루트(V) 순서대로 방문하는 것이다.

4. 반복적순회

• 반복을 이용하는 트리순회.

• 스택을 이용하여 자식 노드들을 저장하고 꺼내면서 순회를 한다. -> 중위순회와 결과가 동일하다.

• 순서

  1. 이진트리의 왼쪽 노드들을 null 노드에 도달할 때까지 스택에 추가한다.
  2. null 노드에 도달하면 스택에서 하나씩 pop()을 통해 삭제한다.
  3. 삭제된 노드를 방문한다. -> 방문했다는 의미로 출력한다.
  4. 방문 후 삭제된 노드의 오른쪽 노드로 이동한다.
  • 오른쪽 노드도 다시 현재 노드로 스택이 빌 때까지 1~4를 반복을 하면 이진트리를 중위순회할 수 있다.

5. 레벨순회

• 각 노드를 레벨 순으로 검사하는 순회 방법
• 루트 노드의 레벨이 1이고 아래로 내려갈수록 레벨이 증가한다.
• 동일한 레벨의 경우 좌에서 우로 이동한다. -> BFS
• 큐를 사용한다.

코드

트리 입력

- 첫 번째 줄에 트리의 노드 개수 n이 주어진다. (1 <= n <= 100)
- 두 번째 줄부터 트리의 정보가 주어진다. -> a,b,c로 이루어지며 a 노드의 왼쪽 자식 노드(b), 오른쪽 자식 노드(c) 를 의미한다.
- 자식 노드가 존재하지 않을 경우에는 -1이 주어진다.

예시

6
0 1 2
1 3 4
2 -1 5
3 -1 -1
4 -1 -1
5 -1 -1

    0
   1 2
  3 4 5

트리 표현하기

• 트리를 표현할 노드가 클래스 구조체로 표현된다.
• 하나의 노드는 데이터를 저장하는 필드, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 필드 총 3개의 필드를 가진다
  • 노드 클래스 생성

class Node {
    int data; // 노드 값
    Node left; // 왼쪽 자식 노드 참조 값
    Node right; // 오른쪽 자식 노드 참조 값

    Node(int data) { // 추가할 때 자식 노드가 있는지 없는지 모르니까 data 값을 기반으로 Node 객체 생성
        this.data = data;    
    }
}

• 트리 클래스의 메소드
  1. 값을 추가하는 createNode() 메소드
  2. 값을 어느 위치에 추가할 것인지 찾기 위한 searchNode() 메소드
  3. 전위순회, 중위순회, 후위순회 메소드

public class TreeOrderClass {
    public Node root; // 초기 root는 null

    // 값을 추가하는 createNode() 메소드
    public void createNode(int data, int left, int right) {
        if(root == null) { // 초기에 루트 노드 생성
            root = new Node(data);

            if(left != -1) {
                root.left = new Node(left); // 왼쪽 자식 노드 값을 가지면 Node 인스턴스 생성
            }
            if(right != -1) {
                root.right = new Node(right); // 오른쪽 자식 노드 값을 가지면 Node 인스턴스 생성
            }
        } else { // 초기 상태가 아니라면 처음 노드를 찾고, 자식 노드 삽입
            searchNode(root, data, left, right);
        }        
    }

    // 값을 어느 위치에 추가할 것인지 찾기 위한 searchNode() 메소드
    public void searchNode(Node node, int data, int left, int right) {
        if(node == null) { // 도착한 노드가 null이면 재귀 종료 -> 찾을 노드 없음
             return;
        } else if(node.data == null) { // 들어갈 위치를 찾았다면 -> 현재 노드의 값이 처음 노드 값과 같을 때
            if(left != -1) {
                node.left = new Node(left);
            }
            if(right != -1) {
                node.right = new Node(right);
            }
        } else { // 아직 못찾고 탐색할 노드가 남아 있다면
            searchNode(node.left, data, left, right); // 왼쪽 재귀 탐색
            searchNode(node.right, data, left, right); // 오른쪽 재귀 탐색
        }
    }

    // 전위순회 (Preorder) : Root -> Left -> Right
    public void preOrder(Node node) {
        if(node != null) {
            System.out.println(node.data + " "); // 루트 부터 출력
            if(node.left != null) { // 왼쪽 노드가 있을 때 재귀 -> 왼쪽 출력
                preOrder(node.left);
            }
            if(node.right != null) { // 오른쪽 노드가 있을 때 재귀 -> 오른쪽 출력
                preOrder(node.right);
            }
        }
    }

    // 중위순회 (Inorder) : Left -> Root -> Right
    public void inOrder(Node node) {
        if(node != null) {
            if(node.left != null) { // 왼쪽부터 재귀
                inOrder(node.left);
            }
            System.out.println(node.data + " "); // 루트 출력
            if(node.right != null) { // 오른쪽 재귀
                inOrder(node.right);
            }
        }
    }

    // 후위순회 (Postorder) : Left -> Right -> Root 
    public void postOrder(Node node) {
        if(node != null) {
            if(node.left != null) { // 왼쪽부터 재귀
                postOrder(node.left);
            }
            if(node.right != null) { // 오른쪽 재귀
                postOrder(node.right);
            }
            System.out.println(node.data + " "); // 루트 마지막에
        }
    }

    // 반복순회
    public void iterativeOrder(Node node) {
        Stack<Node> stack = new Stack<>(); // 스택 생성

        // 처음엔 루트 노드부터 시작
        while(node != null || !stack.isEmpty()) {

            // 현재 노드의 왼쪽 노드들을 null에 도달할 때까지(마지막 왼쪽 자식 노드까지) 스택에 추가한다.
            while(node != null) {
                 stack.push(node);
                 node = node.left;
            }

                // null 노드에 도달하면 스택에서 하나씩 삭제한다.
            node = stack.pop();
            System.out.println(node.data + " "); // 삭제된 노드 방문 -> 노드 삭제하고 출력.

            // 삭제된 노드를 방문한 후에 이 노드의 오른쪽 노드로 이동한다.
            node = node.right;
            // 다시 이 노드를 기준으로 왼쪽 노드들을 null에 도달할 때까지 스택에 추가한다.
            // 이를 스택이 빌 때까지 반복하면 이진트리를 중위순회할 수 있다.
        }
    }

    // 레벨순회
    public void levelOrder(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.data + " ");

            if(node.left != null) queue.offer(node.left); // 왼쪽 자식 노드가 있다면 추가 
            if(node.right != null) queue.offer(node.right); // 오른쪽 자식 노드가 있다면 추가 
        }
    }

    // 노드의 개수 구하기
    public static int getNodeCount(Node root) {
        int count = 0;

        if(root != null) {
            count = 1 + getNodeCount(root.left) + getNodeCount(root.right);
        }

        return count;
    }

    // 단말 노드 개수 구하기 -> 자식이 없는 노드 개수
    public static int getLeafCount(Node root) {
        int count = 0;

        if(root != null) {
            if(root.left == null && root.right) {
                return 1;
            } else {
                count = getLeafCount(root.left) + getLeafCount(root.right);
            }
        }

        return count;
    }

    // 높이 구하기
    public static int getHeight(Node root) {
        int height = 0;

        if(root != null) {
            height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }

        return height;
    }
}

알고리즘 문제 추천

1. 트리 순회 (실버 1)

• https://www.acmicpc.net/problem/1991

2. 트리 순회 (골드 4)

• https://www.acmicpc.net/problem/22856

참고 자료

https://minhamina.tistory.com/83